Статья

Название статьи ИСПОЛЬЗОВАНИЕ РОЕВОГО ИНТЕЛЛЕКТА В РЕШЕНИИ NP-ТРУДНЫХ ЗАДАЧ
Автор В.М. Курейчик, А.А. Кажаров
Рубрика РАЗДЕЛ I. ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ, ГЕНЕТИЧЕСКИЕ И БИОНИЧЕСКИЕ АЛГОРИТМЫ
Месяц, год 07, 2011
Индекс УДК 681.3
DOI
Аннотация Роевой интеллект описывает коллективное поведение децентрализованной самоорганизующейся системы. Рассматривается в теории искусственного интеллекта как метод оптимизации. Термин был введен Херардо Бени и Ван Цзином в 1989 году. Системы роевого интеллекта, как правило, состоят из множества агентов локально взаимодействующих между собой и с окружающей средой. Сами агенты обычно довольно просты, но все вместе, локально взаимодействуя, создают, так называемый, роевой интеллект. Ста- тья посвящена исследованию алгоритмов роевого интеллекта для решения NP-полных задач. Основная идея этих алгоритмов – моделирование поведения роя. В ходе данной работы были исследованы муравьиный, пчелиный и метод роя частиц. С использованием этих алгоритмов решены следующие задачи: задача коммивояжера, маршрутизации автотранспорта, разбиения графа, размещение элементов СБИС. Данные задачи без каких-либо изменений в ее интерпретации решаются для проектирования СБИС, логистических расчетов. В ходе проделанной работы была разработана программа на ЭВМ, реализующая описанные алгоритмы. Полученные результаты позволяют судить об оптимальном выборе параметров алгоритмов. Экспериментальные исследования доказали эффективность роевых алгоритмов по сравнению со стандартными итерационными, эвристическими и генетическими алгоритмами.

Скачать в PDF

Ключевые слова Роевой интеллект; муравьиные алгоритмы; МА; пчелиные алгоритмы; роевой алгоритм; задача о коммивояжере; ЗК; NP-задача; СБИС; генетические алгоритмы.
Библиографический список 1. Beni G., Wang J. Swarm Intelligence in Cellular Robotic Systems, Proceed. NATO Advanced Workshop on Robots and Biological Systems, Tuscany, Italy, June 26–30 (1989).
2. Штовба С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях. – 2003. – № 4. – С. 70-75.
3. Bonavear F., Dorigo M. Swarm Intelligence: from Natural to Artificial Systems. Oxford university Press. 1999.
4. Corne D., Dorigo M., Glover F. New Ideas in Optimization. McGrav-Hill. 1999.
5. Дориго М. Web-сайт Марко Дориго по оптимизации с помощью колонии муравьев, http://iridia.ulb.ac.be/dorigo/ACO/ACO.html.
6. Кажаров А.А., Курейчик В.М. Муравьиные алгоритмы для решения транспортных задач // Теория и системы управления. – М.: Наука, 2010. – № 1.
7. Лебедев О.Б. Покрытие методом муравьиной колонии // Двенадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2010. Труды конференции. Т. 2. – М.: Физматлит, 2010. – С. 423-431.
8. Лебедев О.Б. Гибридный алгоритм разбиения на основе метода муравьиной колонии и коллективной адаптации // Сборник научных трудов V Международной научно-практической конференции “Интегрированные модели и мягкие вычисления в искусственном интеллекте”. Т.2. – М.: Физматлит, 2009. – C. 620-627.
9. Лебедев О.Б. Трассировка в канале методом муравьиной колонии // Известия ЮФУ. Технические науки. – 2009. – № 4 (93). – С. 46-52.
10. Олейник А.А., Олейник А.А., Субботин С.А. Ч. III. Интеллектуальные мультиагентные методы.
11. Курейчик В.В., Полупанова Е.Е. Эволюционная оптимизация на основе алгоритма колонии пчёл. – 2009.
12. Лебедев Б.К., Лебедев В.Б. Размещение на основе метода пчелиной колонии // Известия ЮФУ. Технические науки. – 2010. – № 12 (113). – С. 12-19.
13. Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks IV. – 1995. – P. 1942-1948.
14. A modified particle swarm optimizer. Proceedings of IEEE International Conference on Evolutionary Computation. – 1998. – P. 69-73.
15. Poli R. (2007)."An analysis of publications on particle swarm optimisation applications". Department of Computer Science, University of Essex, UK.
16. Poli R. (2008). «Analysis of the publications on the applications of particle swarm optimisation» // Journal of Artificial Evolution and Applications: 1-10. DOI: 10.1155/2008/685175.
17. Mendes R, Kennedy J., Neves J. Watch thy neighbor or how the swarm can learn from its environment // Proceedings of Swarm Intelligence Symposium 2003. – IEEE, 2003. – P. 88-94.
18. Kennedy J., Mendes R. Population structure and particle swarm performance // Proceedings of the 2002 Evolutionary Computation Congress. – Washington, IEEE Computer Society. – P. 1671-1676.
19. Лебедев Б.К., Лебедев В.Б. Планирование на основе роевого интеллекта и генетической эволюции // Известия ЮФУ. Технические науки. – 2009. – № 4 (93) . – С. 25-33.
20. Гладков Л.А., Курейчик В.М., Курейчик В.В. Генетические алгоритмы. – Ростов-на-Дону: ООО «Ростиздат», 2004.

Comments are closed.