НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o110.pdf (1513.93Кб)

УДК 519.6

1 МГТУ им. Н.Э. Баумана, Москва, Россия

Работу можно считать продолжением и развитием работы [3, 4], в которой рассмотрен способ организации процесса настройки параметров оптимизируемого алгоритма, программная реализация которого предполагает централизованный сбор информации о пространстве стратегий этого алгоритма на основе трехзвенной клиент-серверной архитектуры. Основной целью данной работы является разработка метода перманентной настройки параметров, свободного от большей части недостатков метода, предложенного в указанной публикации:
  -- от пользователя необходима информация о векторе характерных признаков (ВХП)  базовой задачи;
  -- использование клиент-серверной архитектуры требует стабильного подключения к серверу приложений и увеличивает время отклика мета-оптимизатора;
  -- вся вычислительная нагрузка мета-оптимизации ложится на сервер приложений, что предполагает его высокую надежность, повышает стоимость оборудования и затраты на поддержку работоспособности.
Основные особенности предложенного метода заключаются в следующем:
  -- аппроксимация показателей эффективности стратегий базового алгоритма с помощью суррогатных моделей этих показателей;
  -- ускорение процесса мета-оптимизации путем использования суррогатной модели, соответствующей классу базовых задач оптимизации, «близкого» к рассматриваемому классу.
В предложенном методе перманентной настройки для построения суррогатной модели показателя эффективности стратегий (ПЭС) используем метод регрессии на основе деревьев принятия решений, точнее говоря   метод случайного леса (Random Forest, RF). В процессе поиска класса базовых задач, наиболее «близкого» к рассматриваемому классу, используем двухступенчатый метод на основе оценки близости ВХП классов задач и оценки точности предсказания соответствующих суррогатных моделей ПЭС. Собственно задачу мета-оптимизации решаем генетическим алгоритмом с вещественным кодированием хромосом.
Для разработки расширяемой программной системы META_OPT, реализующей предложенный метод, использованы язык программирования Java и реляционная СУБД SQLite. Системы META_OPT также предоставляет различные варианты организации процесса мета-оптимизации: для одиночного, корпоративного пользователя и для компании-поставщика базового программного обеспечения.
Выполнено экспериментальное исследование эффективности разработанного алгоритмического и программного обеспечения. Вычислительный эксперимент выполнен с использованием в качестве базового алгоритма PSO, который имеет три вещественных настраиваемых параметра и один категориальный параметр (топология соседства частиц).
Результаты вычислительного эксперимента показывают, что после стагнации процесса мета-оптимизации первый ПЭС улучшен на 30-50%, а второй ПЭС – на 20-45% по сравнению со значениями этих показателей, которые обеспечивают рекомендуемые авторами алгоритма PSO стратегии.

1. Eiben A.E., Michalewicz Z., Schoenauer M., Smith J.E. Parameter Control in Evolutionary Algorithms // Parameter Setting in Evolutionary Algorithms. Springer Verlag. 2007. P. 19-46. (Ser. Studies in Computational Intelligence; vol. 54). DOI: 10.1007/978-3-540-69432-8_2
2. Smit S.K. Parameter tuning and scientific testing in evolutionary algorithms. Vrije Universiteit, Amsterdam, 2012. Available at: http://dspace.ubvu.vu.nl/bitstream/handle/1871/38404/dissertation.pdf, accessed 01.03.2016.
3. Карпенко А.П., Свианадзе З.О. Метод мета-оптимизации поисковых алгоритмов оптимизации // Наука и образование. МГТУ им . Н . Э . Баумана . Электрон . журн . 2011. № 1. DOI:10.7463/0111.0164546
4. Karpenko A.P., Svianadze Z.O. Meta-optimization based on self-organizing map and genetic algorithm // Optical Memory and Neural Networks. 2011. Vol. 20, iss. 4. P. 279-283. DOI:10.3103/S1060992X11040059
5. Pedersen M.E.H. Tuning & simplifying heuristical optimization. PhD Thesis. University of Southampton, Computational Engineering and Design Group, School of Engineering Sciences, 2010. Available at: http://eprints.soton.ac.uk/342792/1.hasCoversheetVersion/MEH_Pedersen_PhD_Thesis_2010.pdf, accessed 10.04.2016.
6. Hutter F., Hoos H. H., Leyton-Brown K. Sequential model-based optimization for general algorithm configuration // Learning and Intelligent Optimization. International Conference on Learning and Intelligent Optimization. Springer Berlin Heidelberg, 2011. P. 507–523. DOI: 10.1007/978-3-642-25566-3_40
7. Карпенко А . П ., Селиверстов Е . Ю . Обзор методов роя частиц для задачи глобальной оптимизации (particle swarm optimization) // Наука и образование . МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 3. DOI :10.7463/00309.0116072
8. Ugolotti R. Meta-optimization of Bio-inspired Techniques for Object Recognition. Diss. Università di Parma, Dipartimento di Ingegneria dell'Informazione, 2015. Available at: http://dspace-unipr.cineca.it/bitstream/1889/2827/1/TesiDottoratoUgolottiOnline.pdf, accessed 10.04.2016.
9. Friedman J.H. Stochastic gradient boosting // Computational Statistics and Data Analysis. 2002. Vol. 38, iss. 4. P. 367–378. DOI:10.1016/S0167-9473(01)00065-2
10. Breiman L. Random forests // Machine Learning. 2001. Vol. 45, iss. 1. P. 5-32. DOI: 10.1023/A:1010933404324
11. Michalewicz Z. Genetic algorithms, numerical optimization, and constraints // Proceedings of the sixth international conference on genetic algorithms. Vol. 195. Morgan Kaufmann, San Mateo. CA, 1995. P. 151-158. Available at: http://cs.adelaide.edu.au/users/zbyszek/Papers/p16.pdf, accessed 12.03.2016.
12. Blickle T., Thiele L. A comparison of selection schemes used in evolutionary algorithms // Evolutionary Computation. 1996. Vol . 4, no . 4. P . 361–394. DOI : 10.1162/evco.1996.4.4.361
13. Мясников А.С. Островной генетический алгоритм с динамическим распределением вероятностей выбора генетических операторов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2010. № 1. Режим доступа: http://technomag.neicon.ru/doc/136503.html (дата обращения 01.07.2016).
14. Deb K., Beyer H.G. Self-adaptive genetic algorithms with simulated binary crossover // Evolutionary Computation. 2001. Vol. 9, no. 2. P. 197–221. DOI: 10.1162/106365601750190406
15. Owens M. The Definitive Guide to SQLite. Apress, 2006. 464 p.
16. Poli R., Kennedy J., Blackwell T. Particle swarm optimization // Swarm Intelligence. 2007. Vol. 1, iss. 1. P. 33–57. DOI: 10.1007/s11721-007-0002-0
17. Hunter J.D. Matplotlib: A 2D Graphics Environment // Computing in Science and Engineering. 2007. Vol. 9, iss. 3. P. 90–95. DOI: 10.1109/MCSE.2007.55