Алгоритм мурашиної колонії для багатовимірної задачі про ранець
DOI:
https://doi.org/10.35681/1560-9189.2019.21.2.180014Ключові слова:
методи оптимізації, наближені ймовірнісні алгоритми, алгоритми мурашиної колонії, багатовимірна задача про ранець, складність обчисленьАнотація
Надано опис досить нового напряму в створенні методів і алгоритмів розв’язання оптимізаційних задач. Поведінку живих істот у природі вдається формалізувати, використовуючи наукові ідеї. Особливу увагу привертає поведінка мурах. Їхні колонії можна розглядати як багатоагентну систему, чиї агенти працюють окремо, але переслідують спільну мету. Вони мають можливість передавати інформацію, що дозволяє їм адаптуватись і змінювати свою поведінку. Принципи випадковості, багатократності, позитивний і негативний зворотній зв’язок у діях цих не інтелектуальних істот у живій природі подають ідеї створення своєрідних і досить ефективних методів оптимізації. Алгоритми мурашиної колонії вдало застосовуються при вирішенні багатьох завдань дискретної оптимізації. У статті наведено огляд вживаності мурашиних алгоритмів у різних предметних областях. Усі алгоритми цього типу є наближеними — ймовірнісними алгоритмами. Величина ймовірності прийняття певного рішення при формуванні варіанта залежить від параметрів a і b, які визначають наявність і випаровування феромонів. Значення цих параметрів у принципі і зумовлюють ефективність роботи алгоритму. Основний розробкою в статті є новий імовірнісний наближений алгоритм рішення багатовимірної задачі про ранець. В основі його розробки лежать ідеї алгоритмів мурашиної колонії, які вже застосовуються на практиці. Наведено результати комп’ютерного експериментального дослідження.
Результати порівняння точних рішень з рішеннями запропонованим алгоритмом, дають надію отримати способи вирішення завдань дискретної оптимізації для практичного використання, обчислювальна складність яких значно менше.
Надалі, якщо ці алгоритми вдасться привести до точних, то вони виведуть методи дискретної оптимізації з класу NP-складності.Посилання
Zaharov A.A. Muravej, sem'ja, kolonija. Moskva: Nauka. 2000. 132 s.
Shtovba S.D. Murav'inye algoritmy: teorija i primenenie. Programmirovanie. 2005. No. 4. S. 1–16.
Levanova E.V., Loresh M.A. Algoritmy murav'inoj kolonii i imitacii otzhiga dlja reshenija zadachi o p-mediane. Avtomatika i telemehanika. 2004. No. 3. S. 80–88.
Sigal I.H., Ivanova A.P. Vvedenie v prikladnoe diskretnoe programmirovanie. Moskva: Fizmatlit, 2007. 303 s.
Mihalevich V.S. Posledovatel'nye algoritmy optimizacii i ih primenenie. Chast' I, II. Kibernetika. 1965 No. 1, 2.
Djubin G.N., Korbut A.A. Zhadnye algoritmy dlja zadachi o rance: povedenie v srednem. Sibirskij zhurnal industrial'noj matematiki. 1999. T. 2. No. 2(4). S. 68–93.
Serbin D.A. Modifikacija metoda vetvej i granic dlja reshenija zadach celochislennogo linejnogo programmirovanija s bulevymi peremennymi. Persha Mіzhnarodna naukovo-praktichna konferencіja «Project, Program, Portfolio, Management». 2016. T. 1. S. 143–146.
Yukhymenko B.I. Uskorennyj algoritm odnostoronnego vetvlenija dlja reshenija zadach linejnogo programmirovanija s bulevymi peremennymi. Informatika i matematicheskie metody v modelirovanii. 2015. T. 5. No. 4. S. 389–395.
Yukhymenko B.I., Kozina Ju.Ju. Sravnitel'naja harakteristika algoritmov metoda vetvej i granic dlja reshenija zadach celochislennogo linejnogo programmirovanija. Trudy Odessk. poli-teh. un-ta. 2005. Vyp. 2. S. 199–204.
Yukhymenko B.I., Volkova N.P. Priblizhennye algoritmy reshenija zadach o mnogomernom rance. Doslidzhennya v matematytsi i mekhanitsi. 2017. T. 22. Vиp. 2(30). S. 104–113.
