Математика и математическое моделирование. 2017; : 70-82
Исследование эффективности мульти-меметического алгоритма эволюции разума
https://doi.org/10.24108/mathm.0617.0000090Аннотация
При решении практически значимых задач глобальной оптимизации целевая функция зачастую имеет высокую размерность и вычислительную сложность, а также нетривиальный ландшафт. Исследования показывают, что зачастую одного метода оптимизации недостаточно для эффективного решения такого рода задач – необходима гибридизация нескольких методов оптимизации.
Одним из перспективных современных направлений в этой области являются меметические алгоритмы, МА, который можно рассматривать как сочетание популяционного поиска глобального оптимума и процедур локального уточнения решений (мемов), которое дает синергетический эффект. Поскольку существует относительно немного теоретических исследований, посвященных тому, какую конфигурацию МА рекомендуется использовать для решения black-box задач оптимизации, многие исследователи склоняются именно к адаптивным алгоритмам, которые в процессе поиска самостоятельно подбирают наиболее эффективные методы локальной оптимизации для определённых областей пространства поиска.
Авторами предложена мульти-меметическая модификация простого алгоритма SMEC, использующая случайную гиперэвристику. Представлена программная реализация алгоритма, а также используемых мемов (метод Нелдера-Мида, метод случайного поиска по поверхности гиперсферы, метод Хука-Дживса). Выполнено сравнительное исследование эффективности предложенного алгоритма в зависимости от набора и числа мемов. Исследование проводилось с использованием многомерных тестовых функций Растригина, Розенброка и Захарова. Вычислительные эксперименты проводились для всех возможных комбинаций мемов и для каждого мема в отдельности.
По результам исследования с использованием метода мульти-старта успешными оказались комбинации мемов, включающих в себя метод Хука-Дживса. Данные результаты свидетельствуют о быстрой сходимости метода к локальному оптимуму по сравнению с другими мемами, так как все методы выполняют не более фиксированного числа итераций.
Анализ среднего числа итераций показывает, что использование наиболее эффективных наборов мемов позволяет отыскать оптимальное решение за меньшее число итераций по сравнению с менее эффективными наборами. Дополнительно следует отметить, что не наблюдается зависимости общего числа итераций алгоритма от количества используемых мемов.
Результаты исследования демонстрируют, что метод Хука-Дживса оказался наиболее эффективным для выбранных функций, так как его наличие в наборе мемов позволяет существенно улучшить качество получаемого решения. При этом результаты статистических тестов показывают, что использование дополнительных методов в наборе мемов, зачастую не оказывает значительного влияния на результаты работы алгоритма.
Список литературы
1. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учеб. пособие. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 446 с.
2. Weise T. Global optimization algorithms: Theory and application. Kassel: Univ. of Kassel, 2008. 758 p.
3. Krasnogor N. Studies on the theory and design space of memetic algorithms: Doct. diss. Bristol: Univ. of the West of England, 2002.
4. Handbook of memetic algorithms / Ed. by Neri F., Cotta C., Moscato P. B.: Springer, 2012. 368 p. DOI: 10.1007/978-3-642-23247-3
5. Dawkins R. The selfish gene. N.Y.: Oxf. Univ. Press, 1976. 224 p.
6. Sakharov M.K., Karpenko A.P. New parallel multi-memetic MEC-based algorithm for loosely coupled systems // Optimization and applications: VII Intern. conf. on optimization methods and applications: OPTIMA-2016 (Petrovac, Montenegro, Sept. 25th - October 2nd, 2016): Proc. Moscow, 2016. Pp. 124-126.
7. Yew-Soon Ong, Meng-Hiot Lim, Ning Zhu, Kok-Wai Wong. Classification of adaptive memetic algorithms: A comparative study // IEEE Trans. on Systems, Man, and Cybernetics. Pt. B. 2006. Vol. 36. Iss. 1. Pp. 141-152. DOI: 10.1109/TSMCB.2005.856143
8. Handbook of test problems in local and global optimization / Floudas C.A. a.o. Dordrecht; Boston: Kluwer, 1999. 441 p.
9. Chengyi Sun, Yan Sun, Wanzhen Wang. A survey of MEC: 1998-2001 // 2002 IEEE intern. conf. on systems, man and cybernetics: IEEE SMC 2002 (Hammamet, Tunisia, October 6-9, 2002): Proc. Vol. 6. N.Y.: IEEE, 2002. Pp. 445-453. DOI: 10.1109/ICSMC.2002.1175629
10. Jing Jie, Jianchao Zeng, Youzhi Ren. Improved mind evolutionary computation for optimizations // 5th world congress on intelligent control and automation: WCICA 2004 (Hangzhou, China, June 15-19, 2004): Proc. N.Y.: IEEE, 2004. Pp. 2200 – 2204. DOI: 10.1109/WCICA.2004.1341978
11. Jing Jie, Chongzhao Han, Jianchao Zeng. An extended mind evolutionary computation model for optimizations // Applied Mathematics and Computation. 2007. Vol. 185. No. 2. Pp. 1038 – 1049. DOI: 10.1016/j.amc.2006.07.037
12. Sakharov M.K., Karpenko A.P. Performance investigation of mind evolutionary computation algorithm and some of its modifications // 1st intern. scientific conf. “Intelligent information technologies for industry”: IITI’16 (Sochi, Russia, May 20-31, 2016): Proc. Vol. 1. Z.: Springer, 2016. Pp. 475 – 486. DOI: 10.1007/978-3-319-33609-1_43
13. Nguyen Q.H., Ong Y.S., Krasnogor N. A study on the design issues of memetic algorithm // IEEE congress on evolutionary computation: CEC 2007 (Singapore, Singapore, September 25-28, 2007): Proc. N.Y.: IEEE, 2007. Pp. 2390-2397. DOI: 10.1109/CEC.2007.4424770
14. Карпенко А.П., Сахаров М.К. Мультимемеевая глобальная оптимизация на основе алгоритма эволюции разума // Информационные технологии. 2014. № 7. С. 23-30.
15. Nelder J.A., Mead R. A simplex method for function minimization // Computer J. 1965. Vol. 7. No. 4. Pp. 308-313. DOI: 10.1093/comjnl/7.4.308
16. Hooke R., Jeeves T.A. “Direct search" solution of numerical and statistical problems // J. of the Association for Computing Machinery (ACM). 1961. Vol. 8. No. 2. Pp. 212–229. DOI: 10.1145/321062.321069
17. Tukey J.W. Comparing individual means in the analysis of variance // Biometrics. 1949. Vol. 5. No. 2. Pp. 99–114. DOI: 10.2307/3001913
Mathematics and Mathematical Modeling. 2017; : 70-82
Investigating the Multi-memetic Mind Evolutionary Computation Algorithm Efficiency
https://doi.org/10.24108/mathm.0617.0000090Abstract
In solving practically significant problems of global optimization, the objective function is often of high dimensionality and computational complexity and of nontrivial landscape as well. Studies show that often one optimization method is not enough for solving such problems efficiently - hybridization of several optimization methods is necessary.
One of the most promising contemporary trends in this field are memetic algorithms (MA), which can be viewed as a combination of the population-based search for a global optimum and the procedures for a local refinement of solutions (memes), provided by a synergy. Since there are relatively few theoretical studies concerning the MA configuration, which is advisable for use to solve the black-box optimization problems, many researchers tend just to adaptive algorithms, which for search select the most efficient methods of local optimization for the certain domains of the search space.
The article proposes a multi-memetic modification of a simple SMEC algorithm, using random hyper-heuristics. Presents the software algorithm and memes used (Nelder-Mead method, method of random hyper-sphere surface search, Hooke-Jeeves method). Conducts a comparative study of the efficiency of the proposed algorithm depending on the set and the number of memes. The study has been carried out using Rastrigin, Rosenbrock, and Zakharov multidimensional test functions. Computational experiments have been carried out for all possible combinations of memes and for each meme individually.
According to results of study, conducted by the multi-start method, the combinations of memes, comprising the Hooke-Jeeves method, were successful. These results prove a rapid convergence of the method to a local optimum in comparison with other memes, since all methods perform the fixed number of iterations at the most.
The analysis of the average number of iterations shows that using the most efficient sets of memes allows us to find the optimal solution for the less number of iterations in comparison with the less efficient sets. It should be additionally noted that there is no dependence of the total number of the algorithm iterations on the number of memes used.
The study results demonstrate that the Hooke-Jeeves method proved to be the most efficient for the chosen functions, since its presence in a set of memes allows a significantly improving quality of the solution obtained. At the same time, the results of statistical tests show that the use of additional methods in a set of memes often has no significant effect on the results of the algorithm.
References
1. Karpenko A.P. Sovremennye algoritmy poiskovoi optimizatsii. Algoritmy, vdokhnovlennye prirodoi: ucheb. posobie. M.: Izd-vo MGTU im. N.E. Baumana, 2014. 446 s.
2. Weise T. Global optimization algorithms: Theory and application. Kassel: Univ. of Kassel, 2008. 758 p.
3. Krasnogor N. Studies on the theory and design space of memetic algorithms: Doct. diss. Bristol: Univ. of the West of England, 2002.
4. Handbook of memetic algorithms / Ed. by Neri F., Cotta C., Moscato P. B.: Springer, 2012. 368 p. DOI: 10.1007/978-3-642-23247-3
5. Dawkins R. The selfish gene. N.Y.: Oxf. Univ. Press, 1976. 224 p.
6. Sakharov M.K., Karpenko A.P. New parallel multi-memetic MEC-based algorithm for loosely coupled systems // Optimization and applications: VII Intern. conf. on optimization methods and applications: OPTIMA-2016 (Petrovac, Montenegro, Sept. 25th - October 2nd, 2016): Proc. Moscow, 2016. Pp. 124-126.
7. Yew-Soon Ong, Meng-Hiot Lim, Ning Zhu, Kok-Wai Wong. Classification of adaptive memetic algorithms: A comparative study // IEEE Trans. on Systems, Man, and Cybernetics. Pt. B. 2006. Vol. 36. Iss. 1. Pp. 141-152. DOI: 10.1109/TSMCB.2005.856143
8. Handbook of test problems in local and global optimization / Floudas C.A. a.o. Dordrecht; Boston: Kluwer, 1999. 441 p.
9. Chengyi Sun, Yan Sun, Wanzhen Wang. A survey of MEC: 1998-2001 // 2002 IEEE intern. conf. on systems, man and cybernetics: IEEE SMC 2002 (Hammamet, Tunisia, October 6-9, 2002): Proc. Vol. 6. N.Y.: IEEE, 2002. Pp. 445-453. DOI: 10.1109/ICSMC.2002.1175629
10. Jing Jie, Jianchao Zeng, Youzhi Ren. Improved mind evolutionary computation for optimizations // 5th world congress on intelligent control and automation: WCICA 2004 (Hangzhou, China, June 15-19, 2004): Proc. N.Y.: IEEE, 2004. Pp. 2200 – 2204. DOI: 10.1109/WCICA.2004.1341978
11. Jing Jie, Chongzhao Han, Jianchao Zeng. An extended mind evolutionary computation model for optimizations // Applied Mathematics and Computation. 2007. Vol. 185. No. 2. Pp. 1038 – 1049. DOI: 10.1016/j.amc.2006.07.037
12. Sakharov M.K., Karpenko A.P. Performance investigation of mind evolutionary computation algorithm and some of its modifications // 1st intern. scientific conf. “Intelligent information technologies for industry”: IITI’16 (Sochi, Russia, May 20-31, 2016): Proc. Vol. 1. Z.: Springer, 2016. Pp. 475 – 486. DOI: 10.1007/978-3-319-33609-1_43
13. Nguyen Q.H., Ong Y.S., Krasnogor N. A study on the design issues of memetic algorithm // IEEE congress on evolutionary computation: CEC 2007 (Singapore, Singapore, September 25-28, 2007): Proc. N.Y.: IEEE, 2007. Pp. 2390-2397. DOI: 10.1109/CEC.2007.4424770
14. Karpenko A.P., Sakharov M.K. Mul'timemeevaya global'naya optimizatsiya na osnove algoritma evolyutsii razuma // Informatsionnye tekhnologii. 2014. № 7. S. 23-30.
15. Nelder J.A., Mead R. A simplex method for function minimization // Computer J. 1965. Vol. 7. No. 4. Pp. 308-313. DOI: 10.1093/comjnl/7.4.308
16. Hooke R., Jeeves T.A. “Direct search" solution of numerical and statistical problems // J. of the Association for Computing Machinery (ACM). 1961. Vol. 8. No. 2. Pp. 212–229. DOI: 10.1145/321062.321069
17. Tukey J.W. Comparing individual means in the analysis of variance // Biometrics. 1949. Vol. 5. No. 2. Pp. 99–114. DOI: 10.2307/3001913
