Целью данной работы является исследование актуальной задачи поисковой оптимизации многоэкстремальных объектов, которая существенно сложнее одноэкстремальных задач. Показано, что для достижения поставленной цели пригодны лишь эвристические методы. Поэтому исследуются три наиболее известных и разработанных метода поисковой оптимизации: метод роящихся частиц, эволюционно-генетический подход и муравьиный алгоритм. Анализ проводится в среде общей для всех методов тестовой задачи исследования многоэкстремальной функции Растригина. Показано, что все указанные методы вполне пригодны для решения многоэкстремальных задач. Хотя в каждом из эвристических алгоритмов приходится использовать собственные специфические подходы к решению задачи обнаружения и идентификации локальных экстремумов, их объединяет необходимость осуществления кластеризации данных. Каждый метод может обеспечить любую заданную точность решения экстремальной задачи и использует приемлемый ресурс времени.
оптимизация, экстремум, многоэкстремальность, поисковая оптимизация, кластери-зация, эвристические методы, эволюционно-генетический подход, метод роящихся частиц, муравьиный алгоритм.
Многие современные проблемы науки, техники, экономики, военного дела и пр. связаны с решением задач поиска оптимальных характеристик объектов проектирования: конструкций, технологий, режимов и условий работы, динамических и статических состояний и т. д. Иными словами, разработчикам приходится решать задачи поисковой оптимизации (ПО) [1–3]. Характерно, что большинство известных на сегодня методов ПО разработано и эффективно используется для нахождения одного оптимума — чаще всего, глобального [3, 4]. Однако многие задачи планирования, сложные технологические комплексы, транспортные задачи и другие объекты оптимизации (особенно дискретной природы) характеризуются многоэкстремальностью (МЭ) [4–11]. Столь существенное отличительное свойство требует специфических методов решения таких задач. Вряд ли эти методы целесообразно искать в классе детерминированных методов ПО. Они слишком чувствительны к знакопеременности и разрывности функций отклика в континуальных факторных пространствах, а также описываются NP-полными алгоритмами в дискретных факторных пространствах. Для решения большинства реальных оптимизационных задач все чаще стремятся применять методы, получившие название «эвристические». Эти методы наиболее перспективны и для решения МЭ задач [5–11].
1. Boettcher, S. Extremal Optimization: Methods derived from Co-Evolution / S. Boettcher, A.-G. Percus // Proceedings of the Genetic and Evolutionary Computation Conference. — San Francisco, 1999. — P. 825–832.
2. Floudas, C.-A. Encyclopedia of Optimization / C. A. Floudas, P. M. Pardalos. — 2nd edition. — New York : Springer, 2009. — 4646 p.
3. Jones, K.-B. Search Engine Optimization / K.-B. Jones. — 2nd edition — Indianapolis : Wiley Publishing, 2010. — 336 p.
4. Shreves, R. Drupal Search Engine Optimization / R. Shreves. — Birmingham : Packt Publishing, 2012. — 116 p.
5. Математическая энциклопедия : в 5 т. Т. 4. / гл. ред. И. М. Виноградов. — Москва : Советская энциклопедия, 1984. — C. 135–140.
6. Strongin, R. G. Algorithms for multi-extremal mathematical programming problems employing the set of joint space-filling curves / R. G. Strongin // Journal of Global Optimization. — 1992. — Vol. 2, is. 4. — P. 357–378.
7. Нейдорф, Р. А. Перестановочный алгоритм биэкстремального решения однородной распределительной задачи / Р. А. Нейдорф, А. В. Филиппов, З. Х. Ягубов // Вестник Дон. гос. техн. ун-та. — 2011. — № 5 (56). — Т. 11. — С. 655–666.
8. Нейдорф, Р. А. Исследование свойств многоэкстремальности решения распределительных задач / Р. А. Нейдорф, А. А. Жикулин // Системный анализ, управление и обработка информации : сб. тр. 2-го Междунар. науч. семинара. — Ростов-на-Дону : ИЦ ДГТУ, 2011. — С. 377–380.
9. Нейдорф. Р. А. Методология решения многоэкстремальных задач модифицированным методом роящихся частиц / Р. А. Нейдорф, А. А. Деревянкина // Инновации, экология и ресурсосберегающие технологии на предприятиях машиностроения, авиастроения, транспорта и сельского хозяйства : тр. IX междунар. науч.-техн. конф. — Ростов-на-Дону : ИЦ ДГТУ, 2010. — С. 328–330.
10. Нейдорф, Р. А. Решение многоэкстремальных задач методом делящихся роев / Р. А. Нейдорф, А. А. Скляренко // Вестник Дон. гос. техн. ун-та. — 2010. — Т. 10, № 4 (47). — С. 492–499.
11. Нейдорф, Р. А. Решение задач распознавания методом роящихся частиц с делением роя / Р. А. Нейдорф, А. А. Деревянкина // Изв. ЮФУ. Техн. науки. — 2010. — № 7 (108). — C. 21–28.
12. Rastrigin, L. A. Systems of Extremal Control / L. A. Rastrigin. — Moscow : Nauka, 1974. — 316 p.
13. Eberhart, R. A New Optimizer Using Particle Swarm Theory / R.-C. Eberhart, J. Kennedy // Proceedings of the Sixth International Symposium on Micro Machine and Human Science. — Nagoya, 1995. — P. 39–43.
14. Kennedy, J.-A. Particle Swarm Optimization / J.-A. Kennedy , R.-C. Eberhart // Proceedings of IEEE International Conference on Neural Networks. — Piscataway, 1995. — P. 1942–1948.
15. Shi, Y. A modified particle swarm optimizer / Y. Shi, R.-C. Eberhart // Proceedings of the IEEE Congress on Evolutionary Computation. — Piscataway, 1998. — P. 69–73.
16. Clerc, M. The particle swarm-explosion, stability, and convergence in a multi-dimensional complex space / M. Clerc, J. Kennedy // IEEE Transactions on Evolutionary Computation. — 2002. — Vol. 6, is. 1. — P. 58–73.
17. Mendes, R. The fully informed particle swarm: simpler, maybe better / R. Mendes, J. Kennedy, J. Neves // IEEE Transactions on Evolutionary Computation. — 2004. — Vol. 8, is. 3. — P. 204–210.
18. Нейдорф, Р. А. Параметрическая настройка алгоритма поисковой оптимизации методом роящихся частиц с использованием планирования эксперимента / Р. А. Нейдорф, И. В. Черногоров // Международный научный институт «Educatio». — 2015. — Т. 4, № 2 (9). — С. 44–49.
19. Нейдорф, Р. А. Расширение функционала метода роящихся частиц кинематической и динамической модификацией алгоритма его реализации / Р. А. Нейдорф, И. В. Черногоров // ООО "Aeterna", Сб. статей "Роль науки в развитии общества", СБ-17. - том 1, 2015. - С. 24-28.
20. Нейдорф, Р. А. Параметрическое исследование алгоритма роящихся частиц в задаче поиска глобального экстремума / Р. А. Нейдорф, И. В. Черногоров // Математические методы в технике и технологиях — ММТТ-28 : сб. трудов XXVIII междунар. науч. конф. : в 12 т. Т. 3 / под общ. ред. А. А. Большакова. — Саратов : Саратов. гос. техн. ун-т ; Ярославль : Ярослав. гос. техн. ун-т ; Рязань : Рязанск. гос. радиотехн. ун-т. — 2015. — 108 с.
21. Fraser, A. Computer Models in Genetics / A. Fraser. — New York : McGraw-Hill, 1970. — 192 p.
22. Goldberg, D. Genetic Algorithms in Search, Optimization and Machine Learning / D. Goldberg. — Boston : Addison-Wesley, 1989. — 372 p.
23. Mühlenbein, H. The Parallel Genetic Algorithm as Function Optimizer / H. Mühlenbein, D. Schomisch, J. Born // Parallel Computing. — 1991. — Vol. 17. — P. 619–632.
24. Barricelli, N.-A. Esempi numerici di processi di evoluzione / N.-A. Barricelli // Methodos. —1954. — Vol. 6. — P. 45–68.
25. Boettcher S. Extremal Optimization — Heuristics via Co-Evolutionary Avalanches / S. Boettcher // Computing in Science & Engineering. — 2000.— Vol. 2, is. 6. — P. 75–82.
26. Boettcher, S. Extremal optimization of graph partitioning at the percolation threshold / S. Boettcher // Journal of Physics A: Mathematical and General. — 1999. — Vol. 32. — P. 5201–5211.
27. Нейдорф, Р. А. Метод многоэкстремального поиска с использованием эволюционно-генетического алгоритма и выборочного критерия Стьюдента / Р. А. Нейдорф, В. В. Полях // Инновационная наука. — 2015. — Т. 1, № 3. — С. 135–140.
28. Нейдорф, Р. А. Исследование многоэкстремальных зависимостей с использованием эволюционно генетического метода и одновыборочного критерия Стьюдента / Р. А. Нейдорф, В. В. Полях // Математические методы в технике и технологиях — ММТТ-28 : сб. трудов XXVIII междунар. науч. конф. : в 12 т. Т. 3 / под общ. ред. А. А. Большакова. — Саратов : Саратов. гос. техн. ун-т ; Ярославль : Ярослав. гос. техн. ун-т ; Рязань : Рязанск. гос. радиотехн. ун-т. — 2015. — 108 с.
29. Нейдорф, Р. А. Локализация областей поиска эволюционно-генетического алгоритма при решении задач многоэкстремального характера / Р. А. Нейдорф, В. В. Полях //Наука. Технологии. Производство. — 2015. —№ 5(9). —С. 32-35.
30. Gosset, W.-S. The probable error of a mean / W.-S. Gosset // Biometrika. — 1908. — № 6 (1). — P. 1–25.
31. Lovric, M. International encyclopedia of statistical science / M. Lovric. — Berlin : Springer-Verlag, 2011. — 1671 p.
32. Кажаров, А. А. Муравьиные алгоритмы для решения транспортных задач / А. А. Кажаров, В. М. Курейчик // Теория и системы управления. — 2010. — № 1. — С. 30–43.
33. Dorigo, M. Ant colony system: a cooperative learning approach to the traveling salesman problem / M. Dorigo, L.-M. Gambardella // IEEE Transactions on Evolutionary Computation. — 1997. — Vol. 1, № 1. — P. 53–66.
34. Liu, X. An effective clustering algorithm with ant colony / X. Liu, H. Fu // Journal of Computers. — 2010. — Vol. 5, № 4. — P. 598–605.
35. Toksari, M.-D. Ant Colony Optimization for finding the global minimum / M.-D. Toksari // Applied Mathematics and Computation. — 2006. — № 176. — P. 308–316.
36. Нейдорф, Р. А. Разработка, оптимизация и анализ параметров классического муравьиного алгоритма при решении задачи коммивояжера в полно-связном графе / Р. А. Нейдорф, О. Т. Ярахмедов // Наука. Технология. Производство. — 2015. — Т. 2, № 3. — С. 18–22.
37. Нейдорф, Р. А. Статистическое исследование оптимизационных свойств решения классическим муравьиным алгоритмом задачи коммивояжера / Р. А. Нейдорф, О. Т. Ярахмедов // Международный научный институт «Educatio». — 2015. — № 4 (11). — С. 141–144.
38. Нейдорф, Р. А. Исследование возможностей оптимального решения задачи коммивояжера параметрически оптимизированным муравьиным алгоритмом / Р. А. Нейдорф, О. Т. Ярахмедов // Математические методы в технике и технологиях — ММТТ-28 : сб. трудов XXVIII междунар. науч. конф. : в 12 т. Т. 3 / под общ. ред. А. А. Большакова. — Саратов : Саратов. гос. техн. ун-т ; Ярославль : Ярослав. гос. техн. ун-т ; Рязань : Рязанск. гос. радиотехн. ун-т. — 2015. — 108 с.
39. Apply Ant Colony Algorithm to Search All Extreme Points of Function [Электронный ресурс] / C. Y. Pang [et al.] — Режим доступа : http://www.cornell.edu/ arxiv.org/pdf/0911.3209v1.pdf (дата обращения : 17.10.15).
