ПРОГРАММНАЯ ПОДСИСТЕМА ДЛЯ РЕШЕНИЯ NP-СЛОЖНЫХ КОМБИНАТОРНО-ЛОГИЧЕСКИХ ЗАДАЧ НА ГРАФАХ
Аннотация
Работа посвящена созданию программной подсистемы для решения NP- трудных и
NP-сложных комбинаторно-логических задач на графах. В статье приведено описание
комбинаторно-логических задач на графах. Для эффективного их решения предлагаются
новые многоуровневые архитектуры поиска, такие как простая комбинированная, парал-
лельная комбинированная, двухуровневая, интегрированная и гибридная. Данные архитек-
туры основаны на методах, инспирированных природными системами. Ключевым отличием данных архитектур является разделение поиска на два или три уровня и применение на
них различных алгоритмов эволюционного моделирования и биоинспирированного поиска.
Это позволяет получать наборы квазиоптимальных решений выполнять параллельную
обработку и частично устранять проблему преждевременной сходимости. В статье при-
ведено подробное описание разработанной программной подсистемы и ее модулей. В каче-
стве модулей в подсистеме имеется пять разработанных архитектур и набор разрабо-
танных алгоритмов эволюционного моделирования и биоинспирированного поиска, таких
как эволюционный, генетический, пчелиный, муравьиный, светлячковый и обезьяний. Благо-
даря модульной структуре в подсистеме имеется возможность конструировать более 50
различных вариантов комбинаций поиска. Это позволяет использовать все достоинства
методов биоинспирированной оптимизации для эффективного решения NP-сложных ком-
бинаторно-логических задач на графах. Для подтверждения эффективности разработан-
ной программной подсистемы был проведен вычислительный эксперимент на тестовых
примерах. Проведенные серии тестов и экспериментов показали преимущество использо-
вания программного продукта для решения комбинаторно-логических задач на графах
большой размерности, по сравнению с известными алгоритмами, что говорит о перспек-
тивности применения такого подхода. Временная сложность разработанных алгоритмов
в лучшем случае O(nlogn), в худшем случае – О(n3).
Литература
and analysis]. Moscow: MTSMO, 2000.
2. De Jong K. Evolutionary Computation: Recent Development and Open Issues, Proceedings 1st
International conf., Evolutionary Computation and Its Application. Moscow, 1996, pp. 7-18.
3. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye
prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired
by nature: a textbook]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014, 446 p.
4. Abraham A., Ramos V., Grosan G. Swarm Intelligence in Data Mining. Berlin. Heidelberg:
Springer Verlag, 2007.
5. Hassanien E. Emary E. Swarm Intelligence. Principles Advances, and Applications. CRC
Press, 2015.
6. Mourelle M., Nedjah L. De. Swarm intelligent systems. Berlin: Heidelberg: Springer Verlag, 2006.
7. Rodzin S.I., Kureychik V.V. Sostoyanie, problemy i perspektivy razvitiya bioevristik [State, problems
and prospects of development of bio-heuristics], Programmnye sistemy i vychislitel'nye
metody [Software systems and computational methods], 2016, No. 2, pp. 158-172.
8. Kureychik V.V., Kureychik Vl.Vl. Bioispirirovannyy poisk pri proektirovanii i upravlenii
[Bioinspired search in design and management], Izvestiya YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2012, No. 11 (136), pp. 178-183.
9. Kureichik V., Kureichik Vl., Bova V. Placement of VLSI fragments based on a multilayered
approach, Advances in Intelligent Systems and Computing, 2016, Vol. 464, pp. 181-190.
10. Kuritskiy B.Ya. Optimizatsiya vokrug nas: uchebnik [Optimization around us: a tutorial]. Saint
Petersburg: Mashinostroenie, 1989.
11. Hendrickson B., Leland R. A Multilevel Algorithm for Partitioning Graphs, Proceedings of the
1995 ACM/IEEE conference on Super computing, pp. 626-657.
12. Schloegel K., Karypis G., Kumar V. Multilevel diffusion schemes for repartitioning of adaptive
meshes. University of Minnesota, Department of Computer Science, 1997, pp. 109-124.
13. Barnard S.T. Simon H.D. A fast multilevel implementation of recursive spectral bisection for
partitioning unstructured problems, Proceedings 6th SIAM Conf. Parallel Processing for Scientific
Computing, 1993, pp. 711-718.
14. Holland John H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with
Application to Biology, Control, and Artificial Intelligence. USA: University of Michigan,
1975, 183 p.
15. Kureychik, V.M., Kureychik V.V., Rodzin S.I. Modeli parallelizma evolyutsionnykh vychisleniy
[Models of parallelism of evolutionary calculations], Vestnik Rostovskogo gosudarstvennogo
universiteta putey soobshcheniya [Bulletin of the Rostov State University of Railway Engineering],
2011, No. 3 (43), pp. 93-97.
16. Bova V.V., Kureychik V.V. Integrirovannaya podsistema gibridnogo i kombinirovannogo
poiska v zadachakh proektirovaniya i upravleniya [Integrated subsystem of hybrid and combined
search in design and management tasks], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya
SFedU. Engineering Sciences], 2010, No. 12 (113), pp. 37-42.
17. Karaboga D. An idea based on honey bee swarm for numerical optimization. Erciyes University,
Engineering Faculty, Computer Engineering Department, 2005, 110 p.
18. Dorigo M., Maniezzo V., Colorni A. The Ant System: Optimization by a colony of cooperating
objects, IEEE Trans. on Systems, Man, and Cybernetics,1996, Part B, No. 26 (1), pp. 29-41.
19. Kureychik V.V., Kureychik, Vl.Vl. Razmeshcheniya fragmentov SBIS na osnove mekhanizma
agregatsii fraktalov [Placement of VLSI fragments based on the fractal aggregation mechanism],
Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015,
No. 2 (163), pp. 196-205.
20. Adya S.N. Markov I.L. ISPD02 IBM-MS Mixed-size Placement Benchmarks. Available at:
http://vlsicad.eecs.umich.edu/BK/ISPD02bench/.
21. Adya S.N., Markov I.L. Consistent placement of macro-blocks using floor planning and standard-
cell placement, In Proc. Intl. Symp. on Physical Design, 2002, pp. 12-17.
22. Wang M., Yang X., Sarrafzadeh M. Dragon 2000: Standard-cell Placement Tool for Large
Industry Circuits, ICCAD – 2000, pp. 260-263.
