ВЫЧИСЛИТЕЛЬНАЯ МОДЕЛЬ КОЛЛЕКТИВНОГО ПОВЕДЕНИЯ ГРУППЫ ЖИВОТНЫХ: ЭФФЕКТИВНАЯ БИОЭВРИСТИКА ДЛЯ РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ

  • С.И. Родзин Южный федеральный университет
Ключевые слова: Биоэвристика, глобальная оптимизация, дифференциально-векторное движение, память, многомерная функция, агент, оператор, популяция, критерий Уилкоксона

Аннотация

Перспективным решением задач глобальной оптимизации являются метаэвристики, инспириро-
ванные природой, представляющие собой недетерминированные алгоритмы, исследующие простран-
ство поиска, решений, обучающиеся в процессе поиска, не привязанные к конкретной задаче, хотя и не
гарантирующие точное решений. Целью данного исследования является разработка эффективного
алгоритма для решения прикладных проблем глобальной оптимизации многомерных одномодальных и
мультимодальных функций, встречающихся в задачах инженерного проектирования, обработки изо-
бражений и компьютерного зрения, энергетики и энергоменеджмента, анализа данных и машинного
обучения, робототехники. Для достижения этой цели в статье предлагается вычислительная модель
коллективного поведения группы животных и эффективный алгоритм дифференциально-векторного
движения. Модель включает разнообразные паттерны поведения в группе животных: удерживать
текущую позицию; двигаться в направлении к ближайшим соседям или, наоборот, от ближайших со-
седей; двигаться случайным образом; конкурировать за позицию. В коллективной памяти хранится
информация о местоположении доминирующих особей группы и направлении движения группы, лучшие
позиции агентов с учетом механизмов конкуренции и доминирования в группе. Алгоритм был экспери-
ментально протестирован на семи известных многомерных одномодальных и мультимодальных функ-
циях. Результаты были сопоставлены с генетическим алгоритмом, алгоритмом роя частиц, гравита-
ционного поиска дифференциальной эволюции. Предлагаемый алгоритм показал лучшие результаты,
нежели конкурирующие алгоритмы, на всех тестовых функциях. Это объясняется лучшим балансом
нового алгоритма между скоростью сходимости и диверсификацией пространства поиска решений.
Проверка полученных результатов с использованием Т-критерия суммы рангов Уилкоксона для незави-
симых выборок показала, что результаты по алгоритму являются статистически значимыми. Также
проводилось сравнение с одним из наиболее эффективных алгоритмов непрерывной оптимизации BFGS
- квазиньютоновским итерационным алгоритмом численной оптимизации, предназначенным для на-
хождения локального экстремума одномодальных функций. Результаты оказались сопоставимы для
многомерных функций. Алгоритм также сравнивался с методом мультистарта в задаче глобальной
оптимизации мультиэкстремальных функций и доказал свое преимущество по времени и точности
найденных решений.

Литература

1. Kureychik V.V., Rodzin S.I. Vychislitel'nye modeli evolyutsionnykh i roevykh bioevristik (obzor)
[Computational models of evolutionary and swarm bioheuristics (review)], Informatsionnye
tekhnologii [Information Technology], 2021, Vol. 27, No. 10, pp. 507-520.
2. Kureychik V.V., Rodzin S.I. Vychislitel'nye modeli bioevristik, osnovannykh na fizicheskikh i
kognitivnykh protsessakh (obzor) [Computational models and bio heuristics based on physical and
cognitive processes (review], Informatsionnye tekhnologii [Information Technology], 2021, Vol. 27,
No. 11, pp. 563-574.
3. Dragoi E.N., Dafinescu V. Review of Metaheuristics Inspired from the Animal Kingdom, Mathematics,
2021, No. 9, pp. 2335.
4. Dragoi E.N., Dafinescu V. Review of Metaheuristics Inspired from the Animal Kingdom, Mathematics,
2021, No. 9, pp. 2335.
5. Rodzin S.I. Sovremennoe sostoyanie bioevristik: klassifikatsiya, benchmarking, oblasti primeneniya
[Computational models of bioeuristics based on physical and cognitive processes (review)], Izvestiya
YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2023, No. 2, pp. 280-298.
6. Global'naya optimizatsiya: Vikipediya. Svobodnaya entsiklopediya [Global optimization: Wikipedia.
The free encyclopedia]. Available at: https://ru.wikipedia.org/wiki/Global'naya optimizatsiya (accessed
20 January 2024).
7. Kureychik V.V., Rodzin S.I. Bioevristiki, inspirirovannye faunoy (obzor) [Bio heuristics inspired by
fauna (review)], Informatsionnye tekhnologii [Information Technology], 2023, Vol. 29, No. 11,
pp. 559-573.
8. Mirjalili S. Dragonfly algorithm: A new meta-heuristic optimization technique for solving singleobjective,
discrete, and multi objective problems, Neural Comput. Appl., 2015, Vol. 27,
pp. 1053-1073.
9. Kallioras N.A., et. al. Pity beetle algorithm – A new metaheuristic inspired by the behavior of bark
beetles, Adv. Eng. Softw., 2018, Vol. 121, pp. 147-166.
10. Couzin I.D. Collective minds, Nature, 2007, Vol. 445, pp. 715-728.
11. Bode N., Wood A., Franks D. The impact of social networks on animal collective motion, Anim.
Behav., 2011, Vol. 82 (1), pp. 29-38.
12. Broom M., Koenig A., Borries C. Variation in dominance hierarchies among group-living animals:
modeling stability and the likelihood of coalitions, Behav. Ecol., 2009, Vol. 20, pp. 844-855.
13. Long W., et. al. Solving high-dimensional global optimization problems using an improved sine cosine
algorithm, Expert systems with applications, 2019, Vol. 123, pp. 108-126.
14. Hamzaçebi C. Improving genetic algorithms’ performance by local search for optimization, Appl.
Math. Comput., 2008, Vol. 196 (1), pp. 309-317.
15. Kennedy J., Eberhart R.C. Particle swarm optimization, Proc. IEEE Inter. Conf. on Neural Networks,
1995, Vol. 4, pp. 1942-1948.
16. Rashedi E., Nezamabadi-pour H., Saryazdi S. GSA: a gravitational search algorithm, Inf. Sci., 2009,
Vol. 179, pp. 2232-2248.
17. Storn R., Price K. Differential evolution—a simple and efficient adaptive scheme for global optimization
over continuous spaces, Technical report TR-95–012. ICSI. Berkeley. CA, 1995.
18. Wilcoxon F. Individual comparisons by ranking methods Frank Wilcoxon, Bio-metrics Bulletin, 2006,
Vol. 1 (6), pp. 80-83.
19. Al-Baali M. On the behavior of bombined extra-updating/self-scaling BFGS method, Jour. Comput.
Appl. Math., 2001, Vol. 134, pp. 269-281.
20. art i ., et al. Intelligent multi-start methods, Handbook of Metaheuristics. Cham: Springer, 2019,
pp. 221-243.
Опубликован
2024-05-28
Выпуск
Раздел
РАЗДЕЛ I. СИСТЕМЫ УПРАВЛЕНИЯ И МОДЕЛИРОВАНИЕ