Математика и математическое моделирование. 2018; : 59-89
Эволюционные операторы популяционных алгоритмов глобальной оптимизации. Опыт систематизации
https://doi.org/10.24108/mathm.0118.0000103Аннотация
Известно большое число примеров успешного решения с помощью популяционных алгоритмов (П-алгоритмов) сложных практических задач глобальной оптимизации, например, задач автоматизированного проектирования, синтеза сложных химических соединений, оптимального управления динамическими системами и т.д. П-алгоритмы также успешно используются в многокритериальной оптимизации, когда требуется предварительное построение некоторой аппроксимации множества (фронта) Парето этой задачи. П-алгоритмы многочисленны и весьма разнообразны – известно более 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
Mathematics and Mathematical Modeling. 2018; : 59-89
Evolutionary Operators for Global Optimization Population-Based Algorithms. Experience of Systematization
https://doi.org/10.24108/mathm.0118.0000103Abstract
There are a large number of examples of using the population-based algorithms (P-algorithms) to have a successful solution for complex practical tasks of global optimization, for instance, problems of computer-aided design, synthesis of complex chemical compounds, optimal control of dynamic systems, etc. P-algorithms are also successfully used in multi-criteria optimization, when a preliminary construction of some Pareto set (front) approximation is required. P-algorithms are numerous and very diverse – over 100 such algorithms are known, and new algorithms continue to appear. In this connection, the problem of systematizing expressive means of P-algorithms is of relevance. We consider one of the components of this problem that is the problem of classification of the search operators of P-algorithms.
The paper formulates a global optimization problem and a general scheme of the P-algorithms to solve it. This multilevel classification of the main search operators of P-algorithms at the highest level of the hierarchy identifies the following operators: initialization of the population and the end of the search; coding of individuals; randomization; selection; crossing; population management; local search.
These operators at the next hierarchical level are divided into deterministic and stochastic ones. Further, we distinguish static, dynamic program and dynamic adaptive operators. The following classification levels are "operator dependent", that is, generally speaking, different for each operator. We reveal the essence of these operators and give the use cases in various P-algorithms.
Although the paper uses the names of operators such as selection, crossing, our orientation is not only to evolutionary algorithms. A description scheme of operators presented in this paper can be used to determine any population-based algorithms.
The work development expects extending a set of operators presented, and, above all, using this set and a set of basic essences of population algorithms, the formalization of which was earlier proposed by the author, systematizing the most known algorithms of this class.
References
1. Karpenko A.P. Sovremennye algoritmy poiskovoi optimizatsii: uchebnoe posobie. M.: Izd-vo MGTU im. N.E. Baumana, 2014. 446 s.
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. Karpenko A.P. Osnovnye sushchnosti populyatsionnykh algoritmov global'noi optimizatsii. Opyt sistematizatsii // Internet-zhurnal «Naukovedenie». 2017. T. 9. № 6. Rezhim dostupa: https://naukovedenie.ru/PDF/46TVN617.pdf (data obrashcheniya 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. Rezhim dostupa: http://cs.gmu.edu/~sean/book/metaheuristics/ (data obrashcheniya 06.01.2018).
8. Brownlee J. Clever algorithms: Nature-inspired programming recipes. Rezhim dostupa: http://www.cleveralgorithms.com/nature-inspired/index.html (data obrashcheniya 06.01.2018).
9. Skobtsov Yu.A., Speranskii D.V. Evolyutsionnye vychisleniya: ucheb. posobie. M.: Nats. otkrytyi un-t INTUIT, 2015. 326 s.
10. De Jong K.A. Evolutionary somputation: 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. Rezhim dostupa: https://arxiv.org/abs/1408.5343 (data obrashcheniya 07.01.2018).
12. Lévy distribution. Rezhim dostupa: https://en.wikipedia.org/wiki/Lévy_distribution (data obrashcheniya 21.01.2018).
13. Sobol' I.M. Ravnomerno raspredelennye posledovatel'nosti s dopolnitel'nym svoistvom ravnomernosti // Zhurnal vychislitel'noi matematiki i matematicheskoi fiziki. 1976. T. 16. № 5. S. 1332-1337.
14. Mun F. Khaoticheskie kolebaniya: per. s angl. M.: Mir, 1990. 311 s. [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. Sidnyaev N.I. Teoriya planirovaniya eksperimenta i analiz statisticheskikh dannykh: ucheb. posobie. M.: Yurait, 2011. 399 s.
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. Rezhim dostupa: http://journals.hil.unb.ca/index.php/AOR (data obrashcheniya 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. Bioinspirirovannye metody v optimizatsii / L.A. Gladkov i dr. M.: Fizmatlit, 2009. 380 s.
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
