БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ РЕШЕНИЯ ИНВАРИАНТНЫХ ГРАФОВЫХ ЗАДАЧ
Аннотация
Предлагается биоинспирированный метод решения набора инвариантных комбина-
торно-логических задач на графах: формирования паросочетания графа, выделения внут-
ренне-устойчивого множества вершин, выделения клики графа. Описывается модифициро-
ванная парадигма муравьиной колонии использующая, в отличие от канонического метода,
механизмы формирования решений на модели пространства поиска в виде звездного графа.
Задача формирования в графе внутренне-устойчивого множества вершин может быть
сформулирована, как задача разбиения. На начальном этапе на всех ребрах звездного графа
H откладывается одинаковое (небольшое) количество феромона ξ/m, где m=|E|. Процесс
поиска решений итерационный. Каждая итерация l включает три этапа. Агенты облада-
ют памятью. На каждом шаге t в памяти агента ak имеется количество феромона фj(t),
отложенного на каждом ребре графа H. На первом этапе каждый агент ak популяции
конструктивным алгоритмом находит решение Ur
0k, рассчитывает оценку решения
ξk(Ur
0k) и значение степени пригодности полученного агентом решения φk (количество фе-
ромона, соответствующее оценке). На втором этапе, после полного формирования всеми
агентами решений на текущей итерации, феромон ωj, накопленный в j-ой ячейке в буфер-
ном массиве КЭПб, добавляется в каждую j-ю ячейку основного массива Q2={qj|j=1,2,…,m}
коллективной эволюционной памяти КЭПo. На третьем этапе происходит общее испаре-
ние феромона на множестве ребер E звездного графа H. Временная сложность алгоритма,
полученная экспериментальным путем, совпадает с теоретическими исследованиями и для
рассмотренных тестовых задач составляет О(n2).
Литература
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/.
