ИНИЦИАЛИЗАЦИЯ РЕШЕНИЙ В ПОПУЛЯЦИОННЫХ АЛГОРИТМАХ НА ОСНОВЕ МЕТОДА МЕТРОПОЛИСА–ГАСТИНГСА
Аннотация
Наиболее важными задачами принятия оптимальных решений с использованием эвристиче- ских алгоритмов считаются повышение точности и предотвращение преждевременной сходимо- сти. Большинство исследований в этом направлении сосредоточено на разработке новых опера- торов, настройке параметров популяционной метаэвристики и гибридизации нескольких страте- гий поиска решений. Гораздо меньше внимания уделяется инициализации – важной операции в по- пуляционных алгоритмах, которая связана с созданием исходной популяции решений. Предлагает- ся новый подход к инициализации популяции для эвристических алгоритмов. При формировании множества начальных решений предлагается использовать метод Метрополиса–Гастингса. В соответствии с этим методом исходные решения в популяции принимают значения, близкие к глобальному или локальным оптимумам целевой функции. Это позволяет повысить точность получаемых решений. Чтобы продемонстрировать возможности предлагаемого подхода к ини- циализации, он была встроен в базовый алгоритм дифференциальный эволюции. Для оценки эф- фективности стратегии проведена экспериментальная проверка путем сравнения с такими из- вестными методами как случайная инициализация, обучение на основе методов оппозиции и хаоса, а также метода диагонального равномерного распределения. Сравнение проводилось на репрезен- тативном наборе мультимодальных, унимодальных и гибридных функций, включая функцию Рас- тригина, Квинга, Розенброка, Швефеля, квинтовую, ступенчатую, сферическую. Анализировались скорость сходимости алгоритмов и точность получаемых решений. В качестве показателей сравнения использовались среднее значение по лучшим решениям, медианное лучшее решение, стандартное отклонение от лучшего решения, количество вызовов функций, коэффициент ус- пешности, коэффициент ускорения. Значения показателей усреднялись по результатам 30 от- дельных запусков каждого алгоритма. Предлагаемый алгоритм работает быстрее, показывает лучшую сходимость и точность. Алгоритм дает лучшие результаты, поскольку стратегия ини- циализации позволяет выбирать перспективные решения, близкие к локальным или глобальным оптимумам. Статистическая проверка результатов работы алгоритмов по критерию Фридмана подтвердила, что предлагаемый подход к инициализации популяции решений обеспечивает лучший баланс скорость сходимости/точность решений
Список литературы
1. Родзин С.И. Современное состояние биоэвристик: классификация, бенчмаркинг, области при-
менения // Известия ЮФУ. Технические науки. – 2023. – № 2. – С. 280-298.
2. Wolpert D.H., Macready W.G. No free lunch theorems for optimization // IEEE Trans. Evol. Comput.
– 1997. – No. 1. – P. 67-82.
3. Dragoi E.N., Dafinescu V. Review of Metaheuristics Inspired from the Animal Kingdom // Mathematics.
– 2021. – No. 9. – P. 2335.
4. Родзин С.И., Родзина О.Н. Сравнение программных реализаций эволюционных вычислений для
задач многомерной оптимизации // Программная инженерия. – 2019. – Т. 10, № 11-12. – С. 451-456.
5. Tanabe R, Fukunaga A. Success-history based parameter adaptation for differential evolution // IEEE
Cong. on Evol. Comp. – 2013. – P. 71-78.
6. Wen J., Ma H., Zhang X. Optimization of the occlusion strategy in visual tracking // Tsinghua Sci.
Technol. – 2016. – Vol. 21 (2). – P. 221-230.
7. Rahnamayan S., et.al. A novel population initialization method for accelerating evolutionary algorithms
// Comput. Math. Appl. – 2007. – Vol. 53 (10). – P. 1605-1614.
8. Pan W., et. al. Adaptive randomness: a new population initialization method // Math. problems in engineering.
– 2014. – Vol. 2014. – 14 p.
9. Ahmad M., Isa N., Limb W., Ang K. Differential evolution with modified initialization scheme using chaotic
oppositional based learning strategy // Jour. Al. Engin. – 2022. – Vol. 61 (12). – P. 11835-11858.
10. Chib S, Greenberg E. Understanding the Metropolis–Hastings Algorithm // Am Stat. – 1995. – Vol. 49 (4).
– P. 327-335.
11. Chauveau D., Vandekerkhove P. Improving convergence of the Hastings-Metropolis algorithm with an
adaptive proposal // Scand. Jour. Stat. – 2002. – Vol. 29 (1). – P. 13-29.
12. Rodzin S., Rodzina O. New computational models for big data and optimization // Proc. 9th Int. Conf.
on Application of Information and Communication Technologies (AICT). – 2015. – P. 3-7.
13. Rahnamayan S., Tizhoosh H., Salama M. A novel population initialization method for accelerating
evolutionary algorithms // Comput. Math. Appl. – 2007. – Vol. 53 (10). – P. 1605-1614.
14. Ahmad M., Isa N., Limb W., Ang K. Differential evolution with modified initialization scheme using chaotic
oppositional based learning strategy // Alexan. Engin. Jour. – 2022. – Vol. 61 (12). – P. 11835-11858.
15. Li Q., Bai Y., Gao W. Improved Initialization Method for Metaheuristic Algorithms: A Novel Search
Space View // IEEE Access. – 2021. – Vol. 9. – P. 158508-158539.
16. Cuevas E., Escobar H., Sarkar R., Eid H. A new population initialization approach method // Applied
Intelligence. – 2023. – Vol. 53. – P. 16575-16593.
17. Wang H., Wu Z., Rahnamayan S. Enhanced opposition based differential evolution for solving highdimensional
continuous optimization problems // Soft. Comput. – 2011. – Vol. 15 (11). – P. 2127-2140.
18. Rodzin S., Rodzina L. Theory of bionic optimization and its application to evolutionary synthesis of
digital devices // Proc. of IEEE East-West Design and Test Symposium (EWDTS). – 2014.
– P. 7027058.
19. Курейчик В.В., Родзин С.И. Биоэвристики, инспирированные фауной (обзор) // Информацион-
ные технологии. – 2023. – Т. 29, № 11. – С. 559-573.
20. Родзин С.И., Скобцов Ю.А., Эль-Хатиб С.А. Биоэвристики: теория алгоритмы и приложения:
монография. – Чебоксары: ИД "Среда", 2019. – 224 с.
