РАЗРАБОТКА БИОЭВРИСТИК ДЛЯ СОЗДАНИЯ ИНТЕЛЛЕКТУАЛЬНОЙ ПОДСИСТЕМЫ ПРИНЯТИЯ ЭФФЕКТИВНЫХ РЕШЕНИЙ NP- ТРУДНЫХ И NP-СЛОЖНЫХ КОМБИНАТОРНО-ЛОГИЧЕСКИХ ЗАДАЧ НА ГРАФАХ

  • Д.В. Заруба Южный федеральный университет
  • Э.В. Кулиев Южный федеральный университет
  • Д. Ю. Запорожец Южный федеральный университет
  • М. М. Семенова Южный федеральный университет
Ключевые слова: Сложность задачи, NP-задачи, NP-полные задачи на графах, биоинспирированные алгоритмы, муравьиный алгоритм, алгоритм стаи летучих мышей

Аннотация

Статья посвящена решению новых актуальных проблем, возникших в условиях со-
временного развития информационных и нанометровых технологий в области проектиро-
вания, а также разработке новых инновационных методов, обеспечивающих получение
эффективных решений за полиномиальное время. В статье рассматривается проблема
решения NP-сложных задач. Приведено описание процедуры измерения сложности задачи.
Описаны особенности NP- трудных и NP-сложных комбинаторно-логических задач. При-
ведены основные различия между задачами, а также проблемы, с которыми приходится
сталкиваться при решении такого вида задач. Представлена общая схема принятия реше-
ний, состоящая из формулировки проблемы; принятие решения; сигнала в автоматических
системах и обратной связи. На втором этапе (формирование и выбор вариантов решений)
решение основывается на биоинспирированном алгоритме поиска решений задачи комми-
вояжёра. Для решения поставленной задачи был разработан модифицированный биоинспи-
рированный алгоритм, основанный на поведении муравьиной колонии. В отличие от других
методов оптимизации, метаэвристические алгоритмы могут находить глобальные опти-
мальные решения для задач, где существует много локальных решений из-за их случайного
характера. Эти причины привели к широкому использованию таких алгоритмов при реше-
нии различных задач оптимизации. Биоинспирированные алгоритмы становятся новой
революцией в области решений оптимизационных задач. Представлена постановка задачи
коммивояжера, а также решение поставленной задачи на основе муравьиного алгоритма.
Алгоритмы, такие как генетические алгоритмы и PSO могут быть очень полезными, но
они все еще имеют некоторые недостатки в решении проблем мультимодальной оптими-
зации. Эти алгоритмы способны находить оптимальные решения независимо от физиче-
ской природы проблемы. В рамках экспериментальных исследований был произведен анализ
работы биоинспирированных алгоритмов: алгоритм стаи летучих мышей бактериальный
алгоритм и муравьиный алгоритм.

Литература

1. Norenkov I.P. Osnovy avtomatizirovannogo proektirovaniya [Fundamentals of computer-aided
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.
Опубликован
2021-11-14
Выпуск
Раздел
РАЗДЕЛ III. СИСТЕМЫ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ