МАСШТАБИРУЕМЫЙ БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧ МНОГОМЕРНОЙ ОПТИМИЗАЦИИ
Аннотация
Биоинспирированные алгоритмы представляют собой математические преобразо- вания, позволяющие трансформировать входной поток информации в выходной по прави- лам, основанным на имитации механизмов эволюции, а также на статистическом подходе к исследованию ситуаций и итерационном приближении к искомому решению. Биоинспири- рованные алгоритмы имеют определенные преимущества перед традиционными детерми- нированными методами оптимизации, лучше исследуя пространство поиска решений. Од- нако в эру больших данных пригодность биоинспирированных алгоритмов для их обработ- ки, как и большинства других методов, находится под вопросом. Большие данные создают новые вычислительные проблемы, в том числе из-за их очень высокой размерности и раз- реженности. Многомерные задачи вносят дополнительную сложность в исследование пространства поиска решения. Актуальной является задача разработки масштабируемо- го биоинспирированного алгоритма, способного поддерживать разнообразие популяции решений и находить баланс между скоростью сходимости алгоритма и диверсификацией поиска в пространстве решений. В работе представлен масштабируемый биоинспириро- ванный алгоритм, способный решать многомерные оптимизационные задачи высокой раз- мерности, используя иерархический мультипопуляционный подход. Масштабируемость алгоритма предполагает, что его вычислительные затраты растут прямо пропорцио- нально увеличению объема обрабатываемых данных, а также способность при этом вы- дать наилучшее по его настоящим возможностям решение в любое время вычисления, да- же если процесс вычислений не завершен естественным остановом. Масштабируемость также предполагает возможность проводить вычисления в пределах ограниченного объе- ма памяти используемого компьютера. Алгоритм использует специальный оператор му- тации для поддержки разнообразия популяции решений, расширения области поиска реше- ний за счет менее перспективных решений. Оценка эффективности предложенного алго- ритма производится на наборе многомерных оптимизационных функций-бенчмарок: Гри- ванка, Растригина, Розенброка, Швефеля. Показатели разработанного алгоритма сравни- ваются с показателями конкурирующих алгоритмов. Эксперименты свидетельствуют в пользу масштабируемого алгоритма, причем различия в значениях оптимизируемых функ- ций для разработанного алгоритма являются статистически значимыми по сравнению с конкурирующими алгоритмами, в особенности с возрастанием размерности задачи.
Список литературы
// Программные системы и вычислительные методы. – 2016. – № 2. – С. 158-172.
2. Курейчик В.В., Курейчик В.М. Родзин С.И. Теория эволюционных вычислений. – М.:
Физматлит, 2012. – 260 с.
3. Črepinšek M., Liu S.-H., Mernik M. Exploration and exploitation in evolutionary algorithms: a
survey // ACM Computing Surveys. – 2013. – Vol. 45, No. 3. – Р. 35-44.
4. Virginia Y., Analía A. A deterministic crowding evolutionary algorithm to form learning teams
in a collaborative learning context // Expert System Appl. – 2012. – Vol. 39, No. 10.
– Р. 8584-8592.
5. Jie Y., Nawwaf K., Grogono P. Bi-objective multi population genetic algorithm for multimodal
function optimization // IEEE Trans. Evol. Comput. – 2010. – Vol. 14, No. 1. – Р. 80-102.
6. Hui W., Zhijian W., Shahryar R. Enhanced opposition-based differential evolution for solving
high-dimensional continuous optimization problems // Soft. Computing. – 2011. – Vol. 15,
No. 11. – Р. 2127-2140.
7. Xiaodong L., Yao X. Tackling high dimensional nonseparable optimization problems by cooperatively
coevolving particle swarms // Proc. of the IEEE congress on evolutionary computation
(CEC'09). – 2009. – P. 1546-1553.
8. Koza J., et. al. Genetic programming III: Darwinian invention and problem solving. Cambridge.
– MA: MIT Press, 1999.
9. García-Pedrajas N., Castillo J., Ortiz-Boyer D. A cooperative coevolutionary algorithm for
instance selection for instance-based learning // Machine Learning. – 2010. – Vol. 78, No. 3.
– P. 381-420.
10. Родзин С.И., Курейчик В.В. Теоретические вопросы и современные проблемы развития
когнитивных биоинспирированных алгоритмов оптимизации // Кибернетика и програм-
мирование. – 2017. – № 3. – С. 51-79.
11. Bhattacharya M. Exploiting landscape information to avoid premature convergence in evolutionary
search // Proc. of the 2006 IEEE congress on evolutionary computation (CEC2006).
– IEEE Press, 2006. – P. 2575-2579.
12. Ursem R.K. Diversity-guided evolutionary algorithms // In: Proceedings of parallel problem
solving from nature VII (PPSN-2002). – 2002. – Р. 462-71.
13. Aranha C, Iba H. Modelling cost into a genetic algorithm-based portfolio optimization system
by seeding and objective sharing // Proc. of the IEEE congress on evolutionary computation,
CEC2007, 2007. – P. 196-203.
14. Aranha C, Iba H. The memetic tree-based genetic algorithm and its application to portfolio
optimization // Memeting Computer. – 2009. – No. 1 (2). – Р. 139-151.
15. Сергиенко А.Б. Тестовые функции для глобальной оптимизации. – Красноярск: Изд-во
СГАУ, 2015. – 112 с.
16. Антух А.Э., Карпенко А.П. Глобальная оптимизация на основе гибридизации методов
роя частиц, эволюции разума и клональной селекции // Наука и образование. – 2012.
– № 8. – С. 379-416.
17. Molga M., Smutnicki C. Test functions for optimization needs. – 2013. – http://www.zsd.ict.
pwr.wroc.pl/files/docs/functions.pdf.
18. Чернышев О., Борисов А. Сравнительный анализ решения задач оптимизации генетиче-
скими и градиентными методами // Transport and Telecommunication. – 2007. – Vol. 8,
No. 1. – P. 40-52.
19. Кравченко Ю.А. Задачи семантического поиска, классификации, структуризации и инте-
грации информации в контексте проблем управления знаниями // Известия ЮФУ. Тех-
нические науки. – 2016. – № 7 (180). – С. 5-18.
20. Bova V., Kureichik V., Zaruba D. Data and knowledge classification in intelligence informational
systems by the evolutionary method // Proc. of the 2016 6th Int. Conf. - Cloud System
and Big Data Engineering, Confluence, 2016. – P. 6-11.
21. Croucher M. Minimizing the Rosenbrock Function. – 2011. http://demonstrations.wolfram.
com/MinimizingTheRosenbrockFunction/Wolfram Demonstrations Project.
