Preview

Математика и математическое моделирование

Расширенный поиск

Эволюционные операторы популяционных алгоритмов глобальной оптимизации. Опыт систематизации

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


Для цитирования:


Карпенко А.П. Эволюционные операторы популяционных алгоритмов глобальной оптимизации. Опыт систематизации. Математика и математическое моделирование. 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

Просмотров: 221


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)