Статья

Название статьи ИССЛЕДОВАНИЕ ЭВРИСТИЧЕСКИХ АЛГОРИТМОВ В ЗАДАЧАХ ПРОКЛАДКИ И ОПТИМИЗАЦИЯ МАРШРУТОВ В СРЕДЕ С ПРЕПЯТСТВИЯМИ
Автор Р.А. Нейдорф, В.В. Полях, И.В. Черногоров, О.Т. Ярахмедов
Рубрика РАЗДЕЛ III. КОНТРОЛЬ И УПРАВЛЕНИЕ В ТЕХНИЧЕСКИХ СИСТЕМАХ
Месяц, год 03, 2016
Индекс УДК 519.856/629.7.051/004.023
DOI
Аннотация Исследовано три возможных подхода к решению задачи о нахождении эффективного (кратчайшего, наиболее быстрого или безопасного и т.п.) пути в двумерном пространстве с препятствиями. В качестве инструментов решения рассматриваемой задачи использованы наиболее известные эвристические методы: муравьиный алгоритм (МА), метод роящихся частиц (МРЧ) и эволюционно-генетический алгоритм (ЭГА). Построены и исследованы модификации алгоритмов этих методов, адаптированные для решения сформулированной задачи. Для варианта использования МРЧ показано, что ближе всего к рассматриваемой задаче подходит гибрид элементов поведенческих моделей роя, стаи птиц и ряда других вариантов мультиагентного взаимодействия. В гибридный алгоритм органично входят базовые для прототипа основополагающие уравнения законов механики, тяготения и стохастического «размывания» параметров движения. При исследовании МА показано, что целесообразно применить классическое разбиение пространства поиска на несопоставимо мелкие по сравнению с препятствиями фрагменты. Агенты-муравьи используют как традиционную логику выбора перехода из фрагмента во фрагмент: память о наиболее популярных маршрутах на основе феромона, так и сформулированные под задачу элементы тактики принятия и ситуационно обоснованных, и случайных решений. Это приводит к эффективному улучшению и квазиоптимизации маршрута. Использование ЭГА, как одного из наиболее востребованных эвристических методов оптимизации, встречает значительные трудности, связанные с отличительными особенностями операторов формировании популяции, кроссинговера и мутации. Формализация под механизмы ЭГА среды поиска наилучшего пути, содержащей препятствия, вносит существенные коррективы в концептуальную и математическую модели ЭГА, в результате чего этот метод уступает МРЧ и МА по эффективности в этой задаче. В качестве тестового стенда исследования предложенных подходов и разработанных алгоритмов разработаны специальные программные средства «The evolutionary-genetic algorithm of route optimization in the environment obstacles», «Path planning with obstacle avoidance by ant colony optimization» и «The method of route optimization in the obstacles avoidance tasks by seekers particles». С их использованием проведены иллюстрирующие численные эксперименты по решению сформулированной задачи в условиях различных скоплений препятствий.

Скачать в PDF

Ключевые слова Цель; маршрут; препятствие; математическая модель; оптимизация; групповое поведение; эвристические методы; алгоритм роящихся частиц; муравьиный алгоритм; эволюционно-генетический алгоритм
Библиографический список 1. Пшихопов В.Х. Интеллектуальное планирование траекторий подвижных объектов в средах с препятствиями / под ред. В.Х. Пшихопова. – М.: Физматлит, 2014. – 350 с.
2. Заева К., Семенов А. Система поиска минимального пути в среде с полигональными препятствиями // 24-я Международная конференция по компьютерной графике и зрению: труды конференции. – Ростов-на-Дону, Академия архитектуры и искусств ЮФУ. ГрафиКон’2014. – C. 163-166.
3. Dutta S. Obstacle Avoidance of Mobile Robot using PSO-based Neuro Fuzzy Technique // International Journal of Computer Science and Engineering. – 2010. – Vol. 2, No. 2. – P. 301-304.
4. Koren Y., Borenstein J. Potential field methods and their inherent limitations for mobile robot navigation // Proceedings of the IEEE Int. Conf. on Robotics and Automation. – 1991. – P. 1398-1404.
5. Fujimori A., Nikiforuk P., and Gupta M. Adaptive navigation of mobile robots with obstacle avoidance // IEEE Transactions on Robotics and Automation. – 1997. – Vol. 13, No. 4. – P. 596-602.
6. Hansen E.A., Zilberstein S. LAO*: A heuristic search algorithm that finds solutions with loops // Artificial Intelligence. – 2001. – No. 129. – P. 35-62.
7. Engineer F. Fast Shortest Path Algorithms for Large Road Networks // In Proceedings of the 36th Annual ORSNZ Conference, Wellington, New Zealand. 2001.
8. Каляев И.А., Гайдук А.Р. Принципы построения систем планирования поведением интеллектуальных роботов на базе однородных нейроподобных структур // Материалы VIII конференции «Экстремальная робототехника». – СПб.: СПбГТУ, 1997. – С. 14-23.
9. Каляев А.В. Чернухин Ю.В. Носков В.Н., Каляев И.А. Однородные управляющие структуры адаптивных роботов. – М.: Наука, 1990. – 152 c.
10. Авотин E.B. и др. Динамика планетохода / под ред. Б Н. Петрова и А.Л. Кемурджиана. – М.: Наука, 1979. – 438 с.
11. Полуян А.Ю., Марейченко И.В. Построение бионического поиска для задач об экстремальном пути на основе стратегии адаптации // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 58-64.
12. Чернышев Ю.О., Полуян А.Ю. Применение бионических алгоритмов для решения задачи о назначении // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 14-22.
13. Запорожец Д.Ю., Курейчик В.В. Гибридный алгоритм решения задач транспортного типа // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 80-85.
14. Chen S., Eshaghian M.M. A fast recursive mapping algorithm // Department of computer and information science. – New Jersey, USA: New Jersey, 2013. – P. 219-227.
15. McLean A., Cameron S. Path planning and collision avoidance for redundant manipulators in 3D // Intelligent Autonomous Systems. – Karlsruhe, Germany: IOS Press, 1995. – P. 381-388.
16. Старостин Н.В., Панкратова М.А. Генетический алгоритм решения задачи отображения графа // Вестник ННГУ. – 2013. – № 5-1. – С. 204-209.
17. Hoefler T., Snir M. Generic Topology Mapping Strategies for Large-scale Parallel Architectures. – University of Illinois at Urbana-Champaign Urbana. – 2011. – Р. 75-85.
18. Нейдорф Р.А., Полях В.В. Локализация областей поиска эволюционно-генетического алгоритма при решении задач многоэкстремального характера // Международный научный журнал «Наука. Технологии. Производство». – 2015. – № 5 (9). – С.32-35.
19. Нейдорф Р.А. Полях В.В. Метод многоэкстремального поиска с использованием эволюционно-генетического алгоритма и выборочного критерия Cтьюдента // Международный научный журнал "Инновационная наука". – 2015. – № 3. – C. 135-139.
20. Нейдорф Р.А., Полях В.В. Исследование многоэкстремальных зависимостей с использованием эволюционно генетического метода и одновыборочного критерия Стьюдента // Труды XXVIII Международной научной конференции «Математические методы в технике и технологиях» – ММТТ-28. – 2015. – Т. 6. – С. 83-87.
21. Нейдорф Р.А., Черногоров И.В., Полях В.В., Ярахмедов О.Т. Обнаружение и оценка экстремальных особенностей пространства поиска эвристическими алгоритмами // Сборник тезисов II Всероссийской научно-технической конференции «Теоретические и при-
кладные проблемы развития и совершенствования автоматизированных системы управления военного назначения». – 2015. – С. 189-190.
22. Eberhart R.C., Kennedy J.A. New optimizer, using particle swarm theory // Proceedings of the Sixth International Symposium on Micromachine and Human Science, Nagoya, Japan, 1995. – P. 39-43.
23. Kennedy J., Eberhart R. Particle Swarm Optimization // Proceedings of IEEE International Conference on Neural Networks, Piscataway: New Jersey, 1995. – P. 1942-1948.
24. Shi Y., Eberhart R.C. A modified particle swarm optimizer // Proceedings of the IEEE Congress on Evolutionary Computation, Piscataway: New Jersey, 1998. – P. 69-73.
25. Clerc M., Kennedy J. The particle swarm-explosion, stability, and convergence in a multi-dimensional complex space // IEEE Transactions on Evolutionary Computation, 2002. – P. 58-73.
26. Mendes, J. Kennedy, J. Neves. The fully informed particle swarm: simpler, maybe better // IEEE Transactions on Evolutionary Computation. – 2004. – Vol. 8, Issue 3. – P. 204-210.
27. Нейдорф Р.А. Черногоров И.В. Параметрическая настройка алгоритма поисковой оптимизации методом роящихся частиц с использованием планирования эксперимента // Международный Научный Институт "Educatio". – 2015. – Т. 4, № 2 (9). – С. 44-49.
28. Нейдорф Р.А., Черногоров И.В. Расширение функционала метода роящихся частиц кинематической и динамической модификацией алгоритма его реализации // ООО "Aeterna": Сборник статей «Роль науки в развитии общества». – Секция СБ-17. – 2015. – Т. 1. – С. 24-28.
29. Нейдорф Р.А., Черногоров И.В. Параметрическое исследование алгоритма роящихся частиц в задаче поиска глобального экстремума // Труды XXVIII Международной научной конференции «Математические методы в технике и технологиях» – ММТТ-28. – 2015. – Т. 3. – С. 75-59.
30. Нейдорф Р.А., Черногоров И.В., Полях В.В., Ярахмедов О.Т. Экспериментальное исследование возможностей решения многоэкстремальных задач оптимизации эвристическими методами // Вестник ДГТУ. – 2015. – Т. 15, № 4 (83). – C. 82-93.
31. Нейдорф Р.А., Деревянкина А.А. Методология решения многоэкстремальных задач модифицированным методом роящихся частиц // Инновация, экология и ресурсосберегающие технологии на предприятиях машиностроения, авиастроения, транспорта и
сельского хозяйства: труды IX Международной научно-технической конференции. – Ростов-на-Дону: ИЦ ДГТУ, 2010. – С. 328-330.
32. Нейдорф Р.А., Деревянкина А.А. Решение многоэкстремальных задач методом делящихся роев // Вестник ДГТУ. – 2010. – Т. 10, № 4 (47). – С. 492-499.
33. Нейдорф Р.А., Деревянкина А.А. Решение задач распознавания методом роящихся частиц с делением роя // Известия ЮФУ, Технические науки. – 2010. – № 7 (108). – C. 21-28.
34. Нейдорф Р.А., Панков–Козочкин П.А. Применение эвристических методов оптимизации для задач нейросетевой оперативной коррекции САУ // Сборник трудов IV Международного научно-методического симпозиума "Современные проблемы многоуровневого образования" ММТТ-22. – 2009. – Т. 11. – C. 121-127.
35. Dorigo M., Gambardella L.M. Ant colony system: a cooperative learning approach to the traveling salesman problem // IEEE Transactions on Evolutionary Computation. – 1997. – Vol. 1, No. 1. – P. 53-66.
36. Dorigo M., Di Caro G. & Gambardella L.M. Ant Algorithms for Discrete Optimization // Artificial Life. – 1999. – No. 5 (2). – P. 137-172.
37. Кажаров А.А., Курейчик В.М. Муравьиные алгоритмы для решения транспортных задач // Теория и системы управления. – 2010. – № 1. – С. 30-43.
38. Штовба С.Д. Муравьиные алгоритмы // Математика в приложениях. – 2004. – № 4. – С. 70-75.
39. Toksari M.D. Ant Colony Optimization for finding the global minimum // Applied Mathematics and Computation. – 2006. – № 176. – P. 308-316.
40. Liu X., Fu H. An effective clustering algorithm with ant colony // Journal of Computers. – 2010. – Vol. 5, No. 4. – P. 598-605.
41. Pang C.Y., Li X. Apply Ant Colony Algorithm to Search All Extreme Points of Function // 5th IEEE Conf. on industrial Electronics and Applications. – 2009. – P. 1517-1521.
42. Нейдорф Р.А., Ярахмедов О.Т. Разработка, оптимизация и анализ параметров классического муравьиного алгоритма при решении задачи коммивояжера в полно-связном графе // Международный научный журнал «Наука. Технологии. Производство». – 2015. – Т. 2, № 3. – С. 18-22.
43. Нейдорф Р.А., Ярахмедов О.Т. Статистическое исследование оптимизационных свойств решения классическим муравьиным алгоритмом задачи коммивояжера // Международный Научный Институт "Educatio". – 2015. – № 4 (11). – C. 141-144.
44. Нейдорф Р.А., Ярахмедов О.Т. Исследование возможностей оптимального решения задачи коммивояжера параметрически оптимизированным муравьиным алгоритмом // Труды XXVIII Международной научной конференции «Математические методы в технике и технологиях» – ММТТ-28. – 2015. – Т. 6. – 108 с.
45. Fatemeh K.P., Fardad F., Reza S.N. Comparing the Performance of Genetic Algorithm and Ant Colony Optimization Algorithm for Mobile Robot Path Planning in the Dynamic Environments with Different Complexities // Journal of Academic and Applied Studies. – 2013. – Vol. 3 (2). – P. 29-44.

Comments are closed.