DEVELOPMENT OF BIOHEURISTICS FOR CREATING AN INTELLECTUAL SUBSYSTEM FOR MAKING EFFECTIVE DECISIONS OF NP-HARD AND NP-DIFFICULT COMBINATORY-LOGICAL PROBLEMS ON GRAPHS
Abstract
The article is devoted to the solution of new topical problems that have arisen in the conditions
of the modern development of information and nanometer technologies in the field of design,
as well as the development of new innovative methods that provide effective solutions in polynomial
time. The article deals with the problem of solving NP-hard problems. The description of the
procedure for measuring the complexity of the problem is presented the features of NP-hard and
NP-difficult combinatorial logic problems are described. The main differences between the tasks
are presented, as well as the problems that one has to face when solving this type of task. The general
decision-making scheme is presented, consisting of the problem formulation; decisionmaking;
signal in automatic systems and feedback. At the second stage (formation and selection of
solutions), the solution is based on a bioinspired algorithm for finding solutions to the traveling
salesman problem. To solve this problem, a modified bioinspired algorithm based on the behaviorof an ant colony was developed. Unlike other optimization methods, metaheuristic algorithms can
find global optimal solutions for problems where there are many local solutions due to their random
nature. These reasons have led to the widespread use of such algorithms in solving various
optimization problems. Bioinspired algorithms are becoming a new revolution in the field of solving
optimization problems. The statement of the traveling salesman problem is presented, as well
as the solution of the problem on the basis of the ant algorithm. Algorithms such as genetic algorithms
and PSO can be very useful, but they still have some disadvantages in solving multimodal
optimization problems. These algorithms can find optimal solutions regardless of the physical
nature of the problem. In the framework of experimental studies, the analysis of the work of
bioinspired algorithms was carried out: the algorithm of a flock of bats, the bacterial algorithm
and the ant algorithm.
References
design]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2010, 364 p.
2. Karpenko A.P. Sovremennye algoritmy poiskovoi optimizatsii. Algoritmy, vdokhnovlennye
prirodoi: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired
by nature: a textbook]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014, 474 p.
3. Kureichik V.V., Kureichik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychislenii [The theory
of evolutionary calculations]. Moscow: Fizmatlit, 2012, 260 p.
4. Shtovba D.S. Murav'inye algoritmy: teoriya i primenenie [Ant algorithms: theory and application],
Matematika v prilozheniyakh [Mathematics in applications], 2004, pp. 70-75.
5. Boroznov V.O. Issledovanie resheniya zadachi kommivoyazhera [Research of the solution of the
traveling salesman problem], Vestnik Astrakhanskogo gosudarstvennogo tekhnicheskogo universiteta.
Upravlenie, vychislitel'naya tekhnika i informatika [Bulletin of the Astrakhan State Technical University.
Management, computer engineering and computer science], 2009, pp. 147-151.
6. Kureichik V.M., Kureichik V.V. Geneticheskii algoritm razbieniya grafa [Genetic algorithm of
graph partitioning], Izvestiya Rossiiskoi akademii nauk. Teoriya i sistemy upravleniya
[Izvestiya Rossiyskoy akademii nauk. Theory and control systems], 1999, No. 4, pp. 79-87.
7. Kureichik V.M., Lebedev B.K., Lebedev O.K. Poiskovaya adaptatsiya: teoriya i praktika [Search
adaptation: theory and practice]. Moscow: Fizmatlit, 2006, 272 p. ISBN 5-9221-0749-6.
8. Kureichik V.V., Kureichik V.M., Gladkov L.A., Sorokoletov P.V. Bioinspirirovannye metody v
optimizatsii [Bioinspired methods in optimization]. Moscow: Fizmalit, 2009, 384 p.
9. Kureichik V.V., Zaruba D.V., Zaporozhets D.Yu. Bioinspirirovannyi algoritm komponovki
blokov EVA na osnove modifitsirovannoi raskraski grafa [Bioinspired algorithm for the layout
of EVA blocks based on a modified graph coloring], Izvestiya YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2015, No. 4 (165), pp. 6-14.
10. Kureichik V.V., Kureichik Vl.Vl., Bova V.V. Bioinspirirovannyi poisk v zadachakh
konstruktorskogo proektirovaniya i optimizatsii [Bioinspired search in the problems of design
design and optimization], Informatsionnye tekhnologii v nauke, obrazovanii i upravlenii [Information
technologies in science, education and management], ed. by prof. E. L. Gloriozova,
2015, pp. 427-432.
11. Kureichik V.V. Gibridnyi podkhod k resheniyu kombinatorno-logicheskikh zadach na grafakh
[A hybrid approach to solving combinatorial-logical problems on graphs], Tr. Mezhdunarodnogo
nauchno-tekhnicheskogo kongressa "Intellektual'nye sistemy i informatsionnye tekhnologii - 2019"
("IS & IT-2019", "IS&IT19"). Nauchnoe izdanie: v 2-kh t. [Proceedings of the International Scientific
and Technical Congress "Intelligent Systems and Information Technologies-2019" ("IS &
IT-2019", "IS&IT19"). Scientific publication: in 2 vol.], 2019, pp. 36-41.
12. Bova V.V., Lezhebokov A.A., Gladkov L.A. Problem-oriented algorithms of solutions search based
on the methods of swarm intelligence, World Applied Sciences Journal, 2013, Vol. 27 (9),
pp. 1201-1205.
13. Kureichik V., Kureichik V., Bova V. Placement of VLSI fragments based on a multilayered
approach, Advances in Intelligent Systems and Computing, 2016, Vol. 464, pp. 181-190.
14. Kureichik V.V., Zaruba D.V. The bioinspired algorithm of electronic computing equipment schemes
elements placement, Advances in Intelligent Systems and Computing, 2015, Vol. 347, pp. 51-58.
15. Gladkov L.A., Gladkova N.V., Gordienko V.N. Modifitsirovannyi geneticheskii algoritm
resheniya zadachi komponovki blokov EVA [Modified genetic algorithm for solving the problem
of EVA block layout], Informatika, vychislitel'naya tekhnika i inzhenernoe obrazovanie
[Informatics, computer engineering and engineering education], 2015, No. 4 (24), pp. 18-27.
16. Kureichik V.V., Kureichik Vl.Vl. Bioinspirirovannyi algoritm razbieniya skhem pri proektirovanii
SBIS [Bioinspired algorithm for splitting circuits in VLSI design], Izvestiya YuFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 23-29.
17. Kureichik V.V., Zaruba D.V. Dvukhurovnevyi algoritm razbieniya grafa na chasti [A twolevel
algorithm for splitting a graph into parts], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya
SFedU. Engineering Sciences], 2019, No. 2 (204), pp. 6-15.
18. Kureichik V.M., Logunova Yu.A. Ob algoritmakh resheniya zadachi kommivoyazhera v seti
internet [About algorithms for solving the traveling salesman problem on the Internet], Vestnik
Ryazanskogo gosudarstvennogo radiotekhnicheskogo universiteta [Bulletin of the Ryazan
State Radio Engineering University], 2019, No. 68, pp. 37-43.
19. Kuliev E.V., Kravchenko Yu.A., Loginov O.A., Zaporozhets D.Yu. Metod intellektual'nogo
prinyatiya effektivnykh reshenii na osnove bioinspirirovannogo podkhoda [The method of intellectual
making effective decisions based on a bioinspired approach], Izvestiya Kabardino-
Balkarskogo nauchnogo tsentra RAN [Izvestiya Kabardino-Balkar Scientific Center of the
Russian Academy of Sciences], 2017, No. 6-2 (80), pp. 162-169.
20. Zaporozhets D., Zaruba D., Kuliev E. Ant algorithm for determining of critical CONNECTIONS
IN VLSI, Proceedings of 2018 IEEE East-West Design and Test Symposium, EWDTS
2018. Electronic publication, 2018, pp. 8524709.
