Эволюционные операторы популяционных алгоритмов глобальной оптимизации. Опыт систематизации
Аннотация
Известно большое число примеров успешного решения с помощью популяционных алгоритмов (П-алгоритмов) сложных практических задач глобальной оптимизации, например, задач автоматизированного проектирования, синтеза сложных химических соединений, оптимального управления динамическими системами и т.д. П-алгоритмы также успешно используются в многокритериальной оптимизации, когда требуется предварительное построение некоторой аппроксимации множества (фронта) Парето этой задачи. П-алгоритмы многочисленны и весьма разнообразны – известно более 100 таких алгоритмов, и продолжают появляться новые алгоритмы. В этой связи актуальной является проблема систематизации выразительных средств П-алгоритмов. Рассматриваем одну из составляющих этой проблемы – проблему систематизации поисковых операторов П-алгоритмов.
Представляем постановку задачи глобальной оптимизации и общую схему П-алгоритмов ее решения. Предлагаем многоуровневую классификацию основных поисковых операторов П-алгоритмов. Эта классификация на верхнем уровне иерархии выделяет следующие операторы: инициализация популяции и окончание поиска; кодирование особей; рандомизация; селекция; скрещивание; управление популяцией; локальный поиск. Указанные операторы на следующем иерархическом уровне подразделяются на детерминированные и стохастические. Далее различаем статические, динамические программные и динамические адаптивные операторы. Следующие классификационные уровни являются «операторозависимыми», то есть, вообще говоря, различны для каждого из операторов. Раскрываем суть этих операторов, приводим варианты использования в различных П-алгоритмах.
Хотя в работе используются такие наименования операторов, как селекция, скрещивание, мы ориентируемся не только на эволюционные алгоритмы. Представленная в работе схема описания операторов может быть использована для определения любых популяционных алгоритмов.
В развитие работы планируется расширить представленный набор операторов и, главное, с помощью этого набора и набора основных сущностей популяционных алгоритмов, формализация которых предложена автором ранее, систематизировать наиболее известные алгоритмы этого класса.
Список литературы
1. Карпенко А.П. Современные алгоритмы поисковой оптимизации: учебное пособие. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 446 с.
2. Onwubolu G.C., Babu B.V. New optimization techniques in engineering. B.; N.Y.: Springer, 2004. 712 p.
3. Bo Xing, Wen-Jing Gao. Innovative computational intelligence: A rough guide to 134 clever algorithms. Cham: Springer, 2014. 451 p.
4. Карпенко А.П. Основные сущности популяционных алгоритмов глобальной оптимизации. Опыт систематизации // Интернет-журнал «Науковедение». 2017. Т. 9. № 6. Режим доступа: https://naukovedenie.ru/PDF/46TVN617.pdf (дата обращения 05.01.2018).
5. Evolutionary computation 1. Basic algorithms and operators / Ed. by T. Back, D.B. Fogel and Z. Michalewicz. Bristol; Phil.: Inst. of Physics Publ., 2000. 339 p.
6. Evolutionary computation 2. Advanced algorithms and operators / Ed. by T. Back, D.B. Fogel and Z. Michalewicz. Bristol; Phil.: Inst. of Physics Publ., 2000. 270 p.
7. Luke S. Essentials of metaheuristics. Режим доступа: http://cs.gmu.edu/~sean/book/metaheuristics/ (дата обращения 06.01.2018).
8. Brownlee J. Clever algorithms: Nature-inspired programming recipes. Режим доступа: http://www.cleveralgorithms.com/nature-inspired/index.html (дата обращения 06.01.2018).
9. Скобцов Ю.А., Сперанский Д.В. Эволюционные вычисления: учеб. пособие. М.: Нац. открытый ун-т ИНТУИТ, 2015. 326 с.
10. De Jong K.A. Evolutionary сomputation: a unified approach. Camb., Mass.: MIT Press, 2006. 256 p.
11. Fister I.Jr., Yang X.S., Fister D., Fister I. Cuckoo search: A brief literature review. Режим доступа: https://arxiv.org/abs/1408.5343 (дата обращения 07.01.2018).
12. Lévy distribution. Режим доступа: https://en.wikipedia.org/wiki/Lévy_distribution (дата обращения 21.01.2018).
13. Соболь И.М. Равномерно распределенные последовательности с дополнительным свойством равномерности // Журнал вычислительной математики и математической физики. 1976. Т. 16. № 5. С. 1332-1337.
14. Мун Ф. Хаотические колебания: пер. с англ. М.: Мир, 1990. 311 с. [Moon F.C. Chaotic vibrations. N.Y.: Wiley, 1987. 309 p.].
15. Jianxia Liu, Nan Li, Keming Xie. Application of chaos mind evolutionary algorithm in antenna arrays synthesis // J. of Computers. 2010. Vol. 5. No. 5. Pp. 717-724. DOI: 10.4304/jcp.5.5.717-724
16. Xiao-Min Hu, Jun Zhang, Yun Li. Orthogonal methods based ant colony search for solving continuous optimization problems // J. of Computer Science and Technology. 2008. Vol. 23. No. 1. Pp. 2–18. DOI: 10.1007/s11390-008-9111-5
17. Сидняев Н.И. Теория планирования эксперимента и анализ статистических данных: учеб. пособие. М.: Юрайт, 2011. 399 с.
18. Koziel S., Ciaurri D.E., Leifsson L. Surrogate-based methods // Computational optimization, methods and algorithms. B.; Hdbl.: Springer, 2011. Pp. 33-59. DOI: 10.1007/978-3-642-20859-1_3
19. Filho C.J.A.B., De Lima Neto F.B., Lins A.J.C.C., Nascimento A.I.S., Lima M.P. Fish school search // Nature-inspired algorithms for optimization. B.: Springer, 2009. Pp. 261– 277. DOI: 10.1007/978-3-642-00267-0_9
20. Dréo J., Siarry P. Continuous interacting ant colony algorithm based on dense heterarchy // Future Generation Computer Systems. 2004. Vol. 20. No. 5. Pp. 841–856. DOI: 10.1016/j.future.2003.07.015
21. Karci A. Theory of saplings growing up algorithm // Adaptive and natural computing algorithms: 8th Intern. conf. on adaptive and natural computing algorithms: ICANNA 2007 (Warszaw, Poland, April 11-14, 2007): Proc. Pt. I. B.; Hdbl.: Springer, 2007. Pp. 450–460. DOI: 10.1007/978-3-540-71618-1_50
22. Dreo J., Siarry P. Hybrid continuous interacting ant colony aimed at enhanced global optimization // Algorithmic Operations Research. 2007. Vol. 2. No. 1. Pp. 52–64. Режим доступа: http://journals.hil.unb.ca/index.php/AOR (дата обращения 13.03.2018).
23. 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. Vol. 3. N.Y.: IEEE, 2004. Pp. 2200-2204. DOI: 10.1109/WCICA.2004.1341978
24. Krishnanand K.N., Ghose D. Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions // Swarm Intelligence. 2009. Vol. 3. No. 2. Pp. 87–124. DOI: 10.1007/s11721-008-0021-5
25. Биоинспирированные методы в оптимизации / Л.А. Гладков и др. М.: Физматлит, 2009. 380 с.
26. Pei-Wei Tsai, Jeng-Shyang Pan, Bin-Yih Liao, Ming-Jer Tsai, Vaci Istanda. Bat algorithm inspired algorithm for solving numerical optimization problems // Applied Mechanics and Materials. 2012. Vol. 148 & 149. Pp. 134–137. DOI: 10.4028/www.scientific.net/AMM.148-149.134
27. Xin-She Yang. A new metaheuristic bat-inspired algorithm // Nature inspired cooperative strategies for optimization: NISCO 2010. B.; Hdbl.: Springer, 2010. Pp. 65-74. DOI: 10.1007/978-3-642-12538-6_6
Рецензия
Для цитирования:
Карпенко А.П. Эволюционные операторы популяционных алгоритмов глобальной оптимизации. Опыт систематизации. Математика и математическое моделирование. 2018;(1):59-89. https://doi.org/10.24108/mathm.0118.0000103
For citation:
Karpenko A.P. Evolutionary Operators for Global Optimization Population-Based Algorithms. Experience of Systematization. Mathematics and Mathematical Modeling. 2018;(1):59-89. (In Russ.) https://doi.org/10.24108/mathm.0118.0000103
Просмотров: 822
Послать статью по эл. почте 