ЗАСТОСУВАННЯ МУРАШИНИХ АЛГОРИТМІВ В РIШЕННІ ЗАДАЧІ МАРШРУТИЗАЦІЇ
Ключові слова:
еволюційніалгоритми, задачамаршрутизації, мурашиніалгоритмиоптимізації
Анотація
Дослідження показують, що 85-95% загальної тривалості логістичного ланцюга виробничого циклу товарного руху становить очікування на обробку, транспортування та інші операції, включаючи зберігання. Мета логістики - побудувати процес доставки «від дверей до дверей» з мінімальними втратами на місцях з'єднання, з мінімальними накопичувальними витратами та часом для сприяння інтегрованому логістичному потоку. У статті розглядаються актуальні питання використання еволюційних алгоритмів для вирішення задачі маршрутизації. Мурашині алгоритми, як і більшість видів еволюційних алгоритмів, засновані на використанні популяції потенційних рішень і розроблені для вирішення завдань комбінаторної оптимізації, перш за все, пошуку різних шляхів на графах. Кооперація між особинами (штучними мурашками) тут реалізується на основі моделювання стігметріі. При цьому кожен агент, званий штучним мурахою, шукає рішення поставленого завдання. Штучні мурашки послідовно будують рішення завдання, пересуваючись по графу, відкладають феромон і при виборі подальшого ділянки шляху враховують концентрацію цього ферменту. Чим більше концентрація феромону в подальшому ділянці, тим більша ймовірність його вибору. Оскільки в основі мурашиного алгоритма лежить пересування мурах за деякими шляхах, то мурашині алгоритми ефективні, перш за все, при вирішенні завдань, які допускаю інтерпретацію у вигляді графа. Проведені комп'ютерні експерименти показали, що ефективність мурашиного алгоритма зростає при збільшенні розмірності задачі і для задач на графах високої розмірності вони працюють швидше, ніж інші еволюційні алгоритми. Відзначено також хороші результати при вирішенні нестаціонарних задач на графах зі змінною середовищем. В святи з цим пропонується реалізація мета - евристичного методу, як модифікації мурашиних алгоритмів оптимізації. Представлена схема роботи системи. Також представлена специфікація програмного продукту. Результатом дослідження стала розробка системи оптимізації перевезень, яка відповідає сучасним вимогам до програмного забезпечення. Програмне забезпечення адаптується до платформи AndroidЗавантаження
Дані про завантаження поки що недоступні.
Посилання
1. Kim, D.P. Automatic control theory. In 2 vols. Linear systems / D.P. Kim. - M .: FIZMATLIT, 2003. - 288 p.
2. Malhotra, R. Genetic Algorithms: Concepts, Design for Process Controller Optimization / R. Malhotra, N. Singh, Y. Singh // Computer and Information Science. - 2011. - Vol.4. - No2. - p. 39-54.
3. Hall, M. A Cumulative Multi-Niching Genetic Algorithm for Multimodal Function Optimization / M. Hall // International Journal of Advanced Research in Artificial Intelligence. - 2012. - Vol. 1. - No 9. - p. 6-13.
4. Jaen-Cuellar, A.Y. PID Controller Tuning Optimization with Genetic Algorithms in Servo Systems / A.Y. Jaen-Cuellar, R.de J. Romero-Troncoso, L. Morales-Velazquez, R. A. Osornio-Rios // International Journal of Advanced Robotic Systems. 2013. Vol. 10.
5. Jones, D.F. Multiobjective meta-heuristics: an overview of the current state-of-the-art / D.F. Jones, S.K. Mirrazavi, M. Tamiz // Europer Res, 2002. - 137 (1): 1-9.
6. Slavov, T. Application of Genetic Algorithm to Tuning a PID Controller for Glucose Oncentration Control / T. Slavov, O. Roeva // Electronic journal: Wsea Transaction on Systems. - 2012. - Vol. 11. - No 7. - p. 223-233. - URL: http://www.wseas.org/multimedia/journals/systems/2012/55-286.pdf
7. Konak, A. Multi-objective optimization using genetic algorithms: A tutorial / A. Konak, D.W. Soit, A.E. Smith // Reliability Engineering and System Safety 91 (2006). - P. 992-1007.
8. Horohorin, M.A. Genetic algorithm for constructing a fuzzy Pareto set / MA Horohorin, A.A. .Dolgov, Yu.V. Udodov, Yu.A. Gubskov // Devices and systems. Management, control, diagnostics. - M .: Nauchtechlitizdat, 2012. - No7. - P. 27–31.
9. Podlazova, A. B., Genetic algorithms on examples of solution of cutting problems / A. B. Podlazova // Management problems, 2008. - No 2. - P. 57–63.
10. Denisova, L.A. Automation of synthesis of fuzzy control system using multicriteria optimization and genetic algorithms. Denisova // Automation in Industry, 2014. - No3. – P. 54-62.
11. Dunaev, M.P. Parametric optimization of a pumping station control system using a genetic algorithm. Dunaev, N.N. Kutsiy, N.D. Lukyanov // Science and Education: an electronic scientific and technical publication (electronic journal). - 2014. - # 8 URL: http://technomag.bmstu.ru/doc/721172.html (accessed: 08/25/2014).
12. Skakalina, E. Evolutionary algorithms in solving logistical . // “Modelare matematica, optimizare si technologii informationale” , Materiale Conferintei Internationale, 19-24 martie 2018, vol.1,Chisinau.2018, P.310-315.
13. Skakalina, E. (2018), «Development of Methodological Foundations of Logistical Intellectual Control of Complex Systems Based on Hybrid Heuristic Algorithms» / International Journal of Engineering & Technology.- 2018.- Vol. 7, No (4.8). – P.534-538. DOI: 10.14419/ijet.v7i4.8.27301
14. Holland, J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence./ John H. Holland. - Cambridge: MIT Press, 1992. - 228p.
15. De Jong, K.A. Evolutionary computation a unified approach / K.A. De Jong. - Cambridge: A Bradford book, 2006. - 256 p.
2. Malhotra, R. Genetic Algorithms: Concepts, Design for Process Controller Optimization / R. Malhotra, N. Singh, Y. Singh // Computer and Information Science. - 2011. - Vol.4. - No2. - p. 39-54.
3. Hall, M. A Cumulative Multi-Niching Genetic Algorithm for Multimodal Function Optimization / M. Hall // International Journal of Advanced Research in Artificial Intelligence. - 2012. - Vol. 1. - No 9. - p. 6-13.
4. Jaen-Cuellar, A.Y. PID Controller Tuning Optimization with Genetic Algorithms in Servo Systems / A.Y. Jaen-Cuellar, R.de J. Romero-Troncoso, L. Morales-Velazquez, R. A. Osornio-Rios // International Journal of Advanced Robotic Systems. 2013. Vol. 10.
5. Jones, D.F. Multiobjective meta-heuristics: an overview of the current state-of-the-art / D.F. Jones, S.K. Mirrazavi, M. Tamiz // Europer Res, 2002. - 137 (1): 1-9.
6. Slavov, T. Application of Genetic Algorithm to Tuning a PID Controller for Glucose Oncentration Control / T. Slavov, O. Roeva // Electronic journal: Wsea Transaction on Systems. - 2012. - Vol. 11. - No 7. - p. 223-233. - URL: http://www.wseas.org/multimedia/journals/systems/2012/55-286.pdf
7. Konak, A. Multi-objective optimization using genetic algorithms: A tutorial / A. Konak, D.W. Soit, A.E. Smith // Reliability Engineering and System Safety 91 (2006). - P. 992-1007.
8. Horohorin, M.A. Genetic algorithm for constructing a fuzzy Pareto set / MA Horohorin, A.A. .Dolgov, Yu.V. Udodov, Yu.A. Gubskov // Devices and systems. Management, control, diagnostics. - M .: Nauchtechlitizdat, 2012. - No7. - P. 27–31.
9. Podlazova, A. B., Genetic algorithms on examples of solution of cutting problems / A. B. Podlazova // Management problems, 2008. - No 2. - P. 57–63.
10. Denisova, L.A. Automation of synthesis of fuzzy control system using multicriteria optimization and genetic algorithms. Denisova // Automation in Industry, 2014. - No3. – P. 54-62.
11. Dunaev, M.P. Parametric optimization of a pumping station control system using a genetic algorithm. Dunaev, N.N. Kutsiy, N.D. Lukyanov // Science and Education: an electronic scientific and technical publication (electronic journal). - 2014. - # 8 URL: http://technomag.bmstu.ru/doc/721172.html (accessed: 08/25/2014).
12. Skakalina, E. Evolutionary algorithms in solving logistical . // “Modelare matematica, optimizare si technologii informationale” , Materiale Conferintei Internationale, 19-24 martie 2018, vol.1,Chisinau.2018, P.310-315.
13. Skakalina, E. (2018), «Development of Methodological Foundations of Logistical Intellectual Control of Complex Systems Based on Hybrid Heuristic Algorithms» / International Journal of Engineering & Technology.- 2018.- Vol. 7, No (4.8). – P.534-538. DOI: 10.14419/ijet.v7i4.8.27301
14. Holland, J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence./ John H. Holland. - Cambridge: MIT Press, 1992. - 228p.
15. De Jong, K.A. Evolutionary computation a unified approach / K.A. De Jong. - Cambridge: A Bradford book, 2006. - 256 p.
Опубліковано
2019-12-28
Як цитувати
Skakalina E. Застосування мурашиних алгоритмів в рiшенні задачі маршрутизації / E. Skakalina // Системи управління, навігації та зв’язку. Збірник наукових праць. – Полтава: ПНТУ, 2019. – Т. 6 (58). – С. 75-83. – doi:https://doi.org/10.26906/SUNZ.2019.6.075.
Розділ
Інформаційні технології
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
