BIOINSPIRED ALGORITHM FOR SOLVING INVARIANT GRAPH PROBLEMS
Abstract
A bioinspired method for solving a set of invariant combinatorial-logical problems on graphs is proposed: the formation of a graph matching, the selection of an internally stable set of vertices, and the selection of a graph clique. A modified paradigm of the ant colony is described, which uses, in contrast to the canonical method, the mechanisms for generating solutions on the search space model in the form of a star graph. The problem of forming an internally stable set of vertices in a graph can be formulated as a partitioning problem. At the initial stage, the same (small) amount of pheromone ξ/m, where m=|E|, is deposited on all edges of the star graph H. The process of finding solutions is iterative. Each iteration l includes three stages. Agents have memory. At each step t, the memory of the agent ak contains the amount of pheromone фj(t) deposited on each edge of the graph H. At the first stage, each agent ak of the population uses a constructive algorithm to find the solution Ur 0k, calculates the estimate of the solution ξk(Ur 0k) and the value of the degree of suitability of the solution obtained by the agent φk (the amount of pheromone corresponding to the estimate). At the second stage, after the complete formation of solutions by all agents at the current iteration, the pheromone ωj accumulated in the j-th cell in the CEPб buffer array is added to each j-th cell of the main array Q2={qj|j=1,2,…,m} of the CEP0 collective evolutionary memory. At the third stage, the general evaporation of the pheromone occurs on the set of edges E of the star graph H. The time complexity of the algorithm, obtained experimentally, coincides with theoretical studies and for the considered test problems is O(n2).
References
combinatorics]. Moscow: Vil'yams, 2003.
2. Kormen K., Leyzerson Ch., Rivest R. Algoritmy postroenie i analiz [Algorithms construction
and analysis]. Moscow: MTSMNO, 2000.
3. Svami M., Tkhulasiraman K. Grafy, seti i algoritmy [Graphs, networks and algorithms]. Moscow:
Mir, 1984.
4. Lebedev B.K., Lebedev O.B. Gibridnyy bioinspirirovannyy algoritm razmeshcheniya bazovykh
standartnykh bibliotechnykh elementov pri proektirovanii topologii poluzakaznoy SBIS [Hybrid
bioinspired algorithm for placing basic standard library elements in the design of the topology
of a semi-custom VLSI], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering
Sciences], 2019, No. 3, pp. 97-110.
5. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye
prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired
by nature]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2016, 448 p.
6. Lebedev B.K., Lebedev O.B. Pokrytie na osnove metodov roevogo intellekta [Coverage based
on swarm intelligence methods // Problems of development of promising micro- and
nanoelectronic systems], Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh
sistem: Sb. trudov [Collection of works], under the total. ed. academician of the RAS
A.L. Stempkovskogo, 2016, pp. 187-193.
7. Lebedev O.B. Raspredelenie resursov na osnove gibridnykh modeley roevogo intellekta [Resource
distribution based on hybrid models of swarm intelligence], Nauchno-tekhnicheskiy
vestnik informatsionnykh tekhnologiy, mekhaniki i optiki [Scientific and technical bulletin of
information technologies, mechanics and optics], 2017, No. 6, pp. 1063-1073.
8. Lebedev O.B. Hybrid bioinspired algorithm of 1.5 dimensional bin-packing, Proceedings of
the Third International Scientific Conference «Intelligent Information Technologies for Industry
(IITI’18)», 2018, pp. 254-263.
9. Lebedev O.B. Modeli adaptivnogo povedeniya murav'inoy kolonii v zadachakh
proektirovaniya [Models of adaptive behavior of an ant colony in design problems]. Taganrog:
Izd-vo YuFU, 2013, 199 p.
10. Lebedev B.K., Lebedev O.B. Ko-evolyutsionnyy algoritm razbieniya [Co-evolutionary partitioning
algorithm], Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh sistem
[Problems of development of promising micro- and nanoelectronic systems], ed. by
A.L. Stempkovskogo, 2020, No. 3, pp. 79-86.
11. Lebedev B.K., Lebedev O.B. Murav'inye algoritmy razbieniya, ispol'zuyushchie predstavlenie
zadachi, otlichnye ot kanonicheskogo [Ant partitioning algorithms using problem representation other
than the canonical one], Vestnik Rostovskogo gosudarstvennogo universiteta putey soobshcheniya
[Bulletin of the Rostov State University of Communications], 2016, No. 3 (63), pp. 42-47.
12. Lebedev B.K., Lebedev O.B., Zhiglatyy A.A. Razmeshchenie elementov SBIS na osnove modeley
roevogo intellekta [Placement of VLSI elements based on swarm intelligence models], Problemy
razrabotki perspektivnykh mikro- i nanoelektronnykh sistem: Sb. trudov [Problems of development
of promising micro- and nanoelectronic systems. Collection of works], under the total. ed. academician
of the RAS A.L. Stempkovskogo. Moscow: IPPM RAN, 2020, pp. 118-126.
13. Cong J., Romesis M., Xie M. Optimality, Scalability and Stability Study of Partitioning and
Placement Algorithms, Proc. of the International Symposium on Physical Design. Monterey,
CA, pp. 88-94.
14. Sherwani N.A. Algorithms for VLSI Physical Design Automation. Third Edition, Kluwer Academic
Publisher. USA, 2013, 572 p.
15. Mourelle M. Swarm intelligent systems. Berlin: Heidelberg: Springer Verlag, 2006, 217 p.
16. Norenkov I.P. Osnovy avtomatizirovannogo proektirovaniya: uchebnik [Fundamentals of
computer-aided design: textbook]. Modvow: Izd-vo MGTU imeni N.E. Baumana, 2006, 336 p.
17. MCNC Electronic and Information Technologies (Online). Available: www.mcnc.org.
18. hMetis [Online]. Available: http://www-users.cs.umn.edu/karypis/metis/hmet300. HB
Floorplan Benchmarks [Online]. Available: http://cadlab.cs.ucla.edu/ cpmo/HBsuite.html.
19. IBM-PLACE 2.0 benchmark suits. Available at: http://er.cs.ucla.edu/benchmarks/-ibmplace2/
bookshelf/ibm-place2-all-bookshelf-nopad.tar.gz.
20. Adya, S.N. ISPD02 IBM-MS Mixed-size Placement Benchmarks. Available at:
http://vlsicad.eecs.umich.edu/BK/ISPD02bench/.
