Аналіз алгоритму мурашиних колоній та його модифікацій на прикладі вирішення задачі комівояжера

Aртур Златкін; Ольга Марусик

Журнал: Том 22, № 4, 2017

Сторінки: 21 – 26

592 Перегляди

Аналіз алгоритму мурашиних колоній та його модифікацій на прикладі вирішення задачі комівояжера

Анотація

У статті проведено детальний аналіз алгоритму мурашиних колоній – системи, заснованої на агентах, які імітують природну поведінку реальних мурашок. Охарактеризовано основні модифікації мурашиного алгоритму: алгоритм Elitist Ant System, алгоритм Ant-Q, алгоритм Ant Colony System, алгоритм Max-min Ant System, алгоритм ASrank. Описано пропонований мурашиний алгоритм оптимізації для задачі комівояжера. Визначаючи алгоритм мурашиних колоній як один із найбільш перспективних напрямів «природних досліджень», наголошено, що використання детермінованої стратегії пошуку дозволило знайти оптимальний шлях значно швидше порівняно з ймовірнісною стратегією

Ключові слова

мурашині колонії; феромон; задача комівояжера; алгоритм; модифікація

Використані джерела

Subbotin, S. O., Oliynyk, A. O., Oliynyk, O. O. (2013) Non-iterative, evolutional and multi-agent methods of the synthesis of fuzzy logical and neuronet models: мonograph. In: S. O. Subbotin (ed.). Zaporizhhia: ZNTU, 375 p..
Ant colony optimization. URL: http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html
Goss, S., Aron, S. Deneubourg, J.-L., Pasteels, J.-M. (2016) Self-organized short-cuts in the Argentine ant, Naturwissens-chaften, vol. 76, pp. 579–581.
Kazharov, A. A., Kureychik, V. M. (2014) Ant algorithms for transport tasks solving. Izvestiya Rossiyskoy akademii nauk. Teoriya i sistemy upravleniya, № 1, pp. 32–45.
Shtovba, S. D. (2014) Ant algorithms, Exponenta Pro. Matematika v prilozheniyakh, № 4.
Dorigo, M. (2013) ant colony optimization. Scholarpedia.
Bonabeau, E. Dorigo, M.. Theraulaz, G. (2012) Swarm intelligence: from natural to artificial systems, Oxford University Press.
Vatutin, E. I., Titov, V. S. (2014) The analysis of the results of ant colony algorithm application in the task of the search of the way in the graph under constraints. Izvestiya Yuzhnogo federal'nogo universiteta. Tekhnicheskiye nauki, № 12 (161), pp. 111–120.

ЦИТУВАТИ

Zlatkin, A., & Marusik, O. (2017). Analysis of ant colonies algorithm and its modifications on the example of the solution of travelling salesman problem . Bulletin of Cherkasy State Technological University, 22(4), 21-26.

[1] Subbotin, S. O., Oliynyk, A. O., Oliynyk, O. O. (2013) Non-iterative, evolutional and multi-agent methods of the synthesis of fuzzy logical and neuronet models: мonograph. In: S. O. Subbotin (ed.). Zaporizhhia: ZNTU, 375 p..

[2] Ant colony optimization. URL: http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html

[3] Goss, S., Aron, S. Deneubourg, J.-L., Pasteels, J.-M. (2016) Self-organized short-cuts in the Argentine ant, Naturwissens-chaften, vol. 76, pp. 579–581.

[4] Kazharov, A. A., Kureychik, V. M. (2014) Ant algorithms for transport tasks solving. Izvestiya Rossiyskoy akademii nauk. Teoriya i sistemy upravleniya, № 1, pp. 32–45.

[5] Shtovba, S. D. (2014) Ant algorithms, Exponenta Pro. Matematika v prilozheniyakh, № 4.

[6] Dorigo, M. (2013) ant colony optimization. Scholarpedia.

[7] Bonabeau, E. Dorigo, M.. Theraulaz, G. (2012) Swarm intelligence: from natural to artificial systems, Oxford University Press.

[8] Vatutin, E. I., Titov, V. S. (2014) The analysis of the results of ant colony algorithm application in the task of the search of the way in the graph under constraints. Izvestiya Yuzhnogo federal'nogo universiteta. Tekhnicheskiye nauki, № 12 (161), pp. 111–120.