Article

Article title SWARM INTELLIGENCE USING FOR NP-TASKS SOLVING
Authors V.M. Kureichik, A.A. Kazharov
Section SECTION I. EVOLUTIONARY MODELLING, GENETIC AND BIONIC ALGORITHMS
Month, Year 07, 2011 @en
Index UDC 681.3
DOI
Abstract Swarm intelligence (SI) is the collective behaviour of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence. The expression was introduced by Gerardo Beni and Jing Wang in 1989. SI systems are typically made up of a population of simple agents or boids interacting locally with one another and with their environment. The agents follow very simple rules, and although there is no centralized control structure dictating how individual agents should behave, local, and to a certain degree random, interactions between such agents lead to the emergence of "intelligent" global behavior, unknown to the individual agents. This paper is dedicated to the developing of swarm intelligence algorithms for the solving of NP-complete tasks. Modeling of behavior of swarm is the main idea of these algorithms. Ant colony optimization, bee algorithms and particle swarm optimization was searched and developed during this work. Traveling salesman problem, vehicle routing problem, graph partition task, placement for the very-large-scale-integration (VLSI) was solved by using these algorithms. These tasks without any modifications in its interpretation is solved for designing VLSI and some logistic calculations. A computer program was created during this work. This program realizes the model of swarm’s behavior with modifications. Results of the investigations allow to judge about optimum choice of. Experimental researches have proved efficiency of the ACO, BCO, PSO in comparison with standard iteration algorithms, simple heuristic and genetic algorithms.

Download PDF

Keywords Swarm Intelligence; Ant colony optimization; ACO; Bee colony algorithms; particle swarm optimization; traveling salesman problem; TSP; NP task; VLSI; genetic algorithms.
References 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.