INITIALIZATION OF SOLUTIONS IN POPULATION METAHEURISTICS BASED ON THE METROPOLIS–HASTINGS METHOD
Abstract
The most important tasks of making optimal decisions using heuristic algorithms are considered to be improving accuracy and preventing premature convergence. Most of the research in this area focuses on the development of new operators, tuning the parameters of population metaheuristics, and hybridization of several solution search strategies. Much less attention is paid to initialization, an important operation in population algorithms that involves creating an initial population of solutions. A new approach to population initialization for heuristic algorithms is proposed. When forming a set of initial solutions, it is proposed to use the Metropolis–Hastings method. According to this method, the initial solutions in the population take values close to the global or local optima of the objective function. This makes it possible to increase the accuracy of the solutions obtained. To demonstrate the possibilities of the proposed initialization approach, it was integrated into the basic differential evolution algorithm. To assess the effectiveness of the strategy, an experimental test was carried out by comparing it with such well-known methods as random initialization, training based on opposition and chaos methods, as well as the method of diagonal uniform distribution. The comparison was carried out on a representative set of multimodal, unimodal, and hybrid functions, including Rastrigin, Quing, Rosenbrock, Schwefel, quintal, step, and spherical functions. The convergence rate of the algorithms and the accuracy of the obtained solutions were analyzed. The average value for the best solutions, the median best solution, the standard deviation from the best solution, the number of function calls, the success rate, and the acceleration coefficient were used as comparison indicators. The values of the indicators were averaged based on the results of 30 separate runs of each algorithm. The proposed algorithm works faster, shows better convergence and accuracy. The algorithm gives the best results because the initialization strategy allows you to choose promising solutions that are close to local or global optima. Statistical verification of the results of the algorithms using the Friedman criterion confirmed that the proposed approach to initializing a population of solutions provides a better balance of convergence rate/accuracy of solutions.
References
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 с.
