SOFTWARE SUBSYSTEM FOR SOLVING NP-COMPLEX COMBINATORIAL LOGIC PROBLEMS ON GRAPHS
Abstract
The paper is devoted to the development of the software for solving NP-hard and NP-hard
combinatorial-logical problems on graphs. The paper contains a description of graphs combinatorial-
logical problems. New multilevel search architectures such as simple combo, parallel combo,
two-levels, integrated, and hybrid are proposed to effectively address them. These architectures
are based on methods inspired by natural systems. The key difference between these architectures
is the division of search into two or three levels and the use of various algorithms for evolutionary
modeling and bioinspired search on them. This allows obtaining sets of quasi-optimal solutions to
perform parallel processing and partially eliminate the problem of premature convergence. The article
provides a detailed description of the developed software subsystem and its modules. As modules
in the subsystem, there are five developed architectures and a set of developed algorithms for evolutionary
modeling and bioinspired search, such as evolutionary, genetic, bee, ant, firefly and monkey.
Thanks to its modular structure, the subsystem has the ability to design more than 50 different search
combinations. This makes it possible to use all the advantages of bioinspired optimization methods
for efficiently solving NP-complex combinatorial-logical problems on graphs. To confirm the effectiveness
of the developed software subsystem, a computational experiment was carried out on test
examples. The series of tests and experiments carried out have shown the advantage of using a software
product for solving combinatorial-logical problems on graphs of large dimension, in comparison
with known algorithms, which indicates the prospects of using this approach. The time
complexity of the developed algorithms is O(nlogn)) at best, and O (n3) at worst.
References
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.
