АЛГОРИТМЫ РОЙНОЙ ОПТИМИЗАЦИИ

Основные идеи алгоритмов ройной оптимизации (Particle Swarm optimization) были получены вследствие наблюдений за социальным и биологическим поведением стаи птиц, находящейся в поисках источников пищи. При этом, основной идеей оптимизации является постоянное перемещение исследуемых объектов в поисках оптимального положения (глобальной позиции). Технология Particle Swarm Optimization (PSO) была разработана и подробно описана инженером-электриком Расселом С. Эберхарт в соавторстве с социальным психологом Джеймсом Кеннеди. Основные положения методологии были описаны и опубликованы в 1995 г этими двумя авторами в двух статьях [1,2]. Предложенная концепция имела (и имеет) глубокую связь с некоторыми общественными отношениями, понятиями и моделями поведения, которые появились в результате компьютерного исследования и моделирования упрощенной социальной модели птичьей стаи, ищущей пищу. Простота и надежность в поиске оптимальных решений при сложной организации пространства привели к тому, что PSO приобрел широкую известность в научном сообществе. Это послужило стимулом к углубленному изучению данной концепции.

---

Если вам понадобилось заказать контрольную в Челябинске , зайдите на сайт Work5.

---

За последние десятилетия появилось множество различных модификаций для решения широкого спектра прикладных задач. Именно эти факторы определяют практическую значимость алгоритма PSO. В данной работе рассматривается как основной алгоритм PSO, так и его различные модификации, направленные на улучшение характеристик алгоритма (улучшение сходимости, повышение точности описания взаимодействия частиц и т.д.). Также, рассматриваются вопросы совместного использования с другими алгоритмами и распараллеливания вычислений. В качестве источников информации о рассматриваемых алгоритмах, их модификациях и применении, были использованы публикации крупнейших ученых, занимающихся вопросами роевых алгоритмов с конца 1990-х (времени активной разработки данной темы).

Алгоритм PSO был вдохновлен некоторыми характеристиками коллективного поведения, наблюдаемого в природном мире, в котором элементы популяции сотрудничают друг с другом. В настоящее время PSO является одним из ведущих алгоритмов роевого интеллекта и лучшим по сравнению с другими алгоритмами оптимизации в некоторых областях применения. Безусловно, в исходном построении алгоритма присутствует ряд уязвимостей и недостатков, связанных со сходимостью, неточным определением взаимодействия частиц внутри роя, наличии набора параметров, при котором возможна стагнация алгоритма. Тем не менее, эти проблемные вопросы с течением времени исследовались, основные пути их решения рассмотрены в данной работе. Методология, примененная при построении алгоритма PSO, легла в основу множества других алгоритмов, применяемых для широчайшего круга задач: Муравьиный алгоритм, Пчелиный алгоритм, Алгоритм кукушки, алгоритм серых волков и т.д. Сам же исходный алгоритм PSO получил множество модификаций под конкретную задачу, доработок для ускорения вычислений и повышения характеристик с помощью параллельных вычислений и искусственного интеллекта. С развитием вычислительных мощностей и углублением ИИ, трансформации PSO будут, безусловно, продолжены. Все эти факторы лишний раз подчеркивают значимость подобных PSO, связанных с окружающим нас миром подходов к решению сложных комплексных задач.

1) Eberhart, R.; Kennedy, J. A new optimizer using particle swarm theory. In Proceedings of the 6th International Symposium on Micro Machine and Human Science (MHS), Nagoya, Japan, 4–6 October 1995; pp. 39–43. 2) Kennedy, J.; Eberhart, R. Particle swarm optimization. In Proceedings of the International Conference on Neural Networks (ICNN), Perth, Australia, 27 November–1 December 1995; Volume 4, pp. 1942–1948. 3) Bonyadi, M.R.; Michalewicz, Z. Particle swarm optimization for single objective continuous space problems: A review. Evol. Comput. 2017, 25, 1–54.10.1162/EVCO_r_00180. 4) Kennedy, J.; Eberhart, R.C. A discrete binary version of the particle swarm algorithm. In Proceedings of the IEEE International Conference on Systems, Man and Cybernetics (SMC), Orlando, FL, USA, 12–15 October 1997; Volume 5, pp. 4104–4108. 5) Rosendo, M.; Pozo, A. A hybrid particle swarm optimization algorithm for combinatorial optimization problems. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC), Barcelona, Spain, 18–23 July 2010; pp. 1–8. 6) Rosendo, M.; Pozo, A. Applying a discrete particle swarm optimization algorithm to combinatorial problems. In Proceedings of the 11th Brazilian Symposium on Neural Networks (SBRN), São Paulo, Brazil, 23–28 October 2010; pp. 235–240. 7) Junliang, L.; Wei, H.; Huan, S.; Yaxin, L.; Jing, L. Particle swarm algorithm based task scheduling for many-core systems. In Proceedings of the 12th IEEE Conference on Industrial Electronics and Applications (ICIEA), Siem Reap, Cambodia, 18–20 June 2017; pp. 1860–1864. 8) Ozcan, E.; Mohan, C.K. Analysis of a simple particle swarm optimization system. In Proceedings of the Intelligent Engineering Systems Through Artificial Neural Networks (ANNIE), St. Louis, MO, USA, 1–4 November 1998; Volume 8, pp. 253–258. 9) Ozcan, E.; Mohan, C.K. Particle swarm optimization: Surfing the waves. In Proceedings of the Congress on Evolutionary Computation (CEC), Washington, WA, USA, 6–9 July 1999; Volume 3, pp. 1939–1944. 10) Freitas, D.; Lopes, L.G.; Morgado-Dias, F. Particle Swarm Optimisation: A Historical Review Up to the Current Developments. Entropy 2020, 22, 362. 11) Shi, Y.; Eberhart, R.C. A modified particle swarm optimizer. In Proceedings of the IEEE World Congress on Computational Intelligence (WCCI), Anchorage, AK, USA, 4–9 May 1998; pp. 69–73. 12) Van den Bergh, F. An Analysis of Particle Swarm Optimizers. Ph.D. Thesis, University of Pretoria, Pretoria, South Africa, 2002. 13) Sengupta, S.; Basak, S.; Peters, R.A., II. Particle swarm optimization: A survey of historical and recent developments with hybridization perspectives. Mach. Learn. Knowl. Extr. 2018. 14) Chatterjee, A.; Siarry, P. Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization. Comput. Oper. Res. 2006, 33, pp. 859–871. 15) Shi, Y.; Eberhart, R.C. Fuzzy adaptive particle swarm optimization. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC), Seoul, Korea, 27–30 May 2001; Volume 1, pp. 101–106. 16) Clerc, M. The swarm and the queen: Towards a deterministic and adaptive particle swarm optimization. In Proceedings of the Congress on Evolutionary Computation (CEC), Washington, WA, USA, 6–9 July 1999; Volume 3, pp. 1951–1957. 17) Kar, R.; Mandal, D.; Bardhan, S.; Ghoshal, S.P. Optimization of linear phase FIR band pass filter using particle swarm optimization with constriction factor and inertia weight approach. In Proceedings of the IEEE Symposium on Industrial Electronics and Applications (ICIEA), Langkawi, Malaysia, 25–28 September 2011; pp. 326–331. 18) Kennedy, J. Small worlds and mega-minds: Effects of neighborhood topology on particle swarm performance. In Proceedings of the Congress on Evolutionary Computation (CEC), Washington, WA, USA, 6–9 July 1999; Volume 3, pp. 1931–1938. 19) Kennedy, J.; Mendes, R. Population structure and particle swarm performance. In Proceedings of the Congress on Evolutionary Computation (CEC), Honolulu, HI, USA, 12–17 May 2002; Volume 2, pp. 1671–1676. 20) Suganthan, P.N. Particle swarm optimiser with neighbourhood operator. In Proceedings of the Congress on Evolutionary Computation (CEC), Washington, WA, USA, 6–9 July 1999; Volume 3, pp. 1958–1962. 21) Kennedy, J. Stereotyping: Improving particle swarm performance with cluster analysis. In Proceedings of the Congress on Evolutionary Computation (CEC), La Jolla, CA, USA, 16–19 July 2000; Volume 2, pp. 1507–1512. 22) Veeramachaneni, K.; Peram, T.; Mohan, C.; Osadciw, L.A. Optimization using particle swarms with near neighbor interactions. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), Chicago, IL, USA, 12–16 July 2003; pp. 110–121. 23) Peram, T.; Veeramachaneni, K.; Mohan, C.K. Fitness-distance-ratio based particle swarm optimization. In Proceedings of the IEEE Swarm Intelligence Symposium (SIS), Indianapolis, IN, USA, 26 April 2003; pp. 174–181. 24) Van den Bergh, F.; Engelbrecht, A.P. A new locally convergent particle swarm optimiser. In Proceedings of the IEEE International Conference on Systems, Man and Cybernetics (SMC), Yasmine Hammamet, Tunisia, 6–9 October 2002; Volume 3, pp. 94–99. 25) Van den Bergh, F.; Engelbrecht, A.P. Cooperative learning in neural networks using particle swarm optimizers. S. Afr. Comput. J. 2000, 26, 84–90. 26) Van den Bergh, F.; Engelbrecht, A.P. A cooperative approach to particle swarm optimization. IEEE Trans. Evol. Comput. 2004, 8, pp. 225–239. 27) Zhan, Z.; Zhang, J.; Li, Y.; Chung, H.S. Adaptive particle swarm optimization. IEEE Trans. Syst. Man Cybern. 2009, 39, pp. 1362–1381.