МЕТОД ДИНАМИЧЕСКОГО ВЫБОРА ВСПОМОГАТЕЛЬНЫХ КРИТЕРИЕВ В МНОГОКРИТЕРИАЛЬНЫХ ЭВОЛЮЦИОННЫХ АЛГОРИТМАХ

Предмет исследования. Предложена модификация метода EA+RL, являющегося одним из методов повышения эффективности эволюционных алгоритмов при помощи вспомогательных критериев. Проведено сравнение предложенной модификации с существующими методами повышения эффективности эволюционных алгоритмов на примере задачи коммивояжера. Метод. В методе EA+RLобучение с подкреплением используется для выбора оптимизируемого критерия, целевого или одного из вспомогательных, на каждой итерации однокритериального эволюционного алгоритма. Предложенная модификация метода EA+RLпозволяет использовать данный подход в многокритериальных эволюционных алгоритмах. В отличие от метода EA+RL, в предложенной модификации на каждом шаге многокритериального эволюционного алгоритма оптимизируются целевой критерий и один из вспомогательных, выбираемый при помощи обучения с подкреплением. Основные результаты. Проведено сравнение предложенной модификации метода EA+RLcсуществующими методами повышения эффективности эволюционных алгоритмов с помощью вспомогательных критериев на примере задачи коммивояжера. В методах EA+RLи предлагаемой его модификации применялись алгоритмы обучения с подкреплением в стационарной и нестационарной средах. Показаны преимущества решения задачи с использованием предлагаемой модификации метода EA+RL, применяемой совместно с алгоритмом обучения с подкреплением в нестационарной среде, по сравнению с использованием ранее известных методов выбора вспомогательных критериев в эволюционных алгоритмах. Практическая значимость. Предложенный в работе подход позволяет повысить эффективность эволюционных алгоритмов, которые применяются для решения NP-трудных задач дискретной оптимизации. К таким задачам относятся, в частности, поиск оптимального маршрута и составление расписаний.

1. Segura C., Coello C.A.C., Miranda G., Leon C. Using multi-objective evolutionary algorithms for single-objective optimization // 4OR. 2013. V. 11. N 3. P. 201–228. doi: 10.1007/s10288-013-0248-x
2. Буздалова А.С., Буздалов М.В. Метод повышения эффективности эволюционных алгоритмов с помо-щью обучения с подкреплением // Научно-технический вестник информационных технологий, меха-ники и оптики. 2012. № 5 (81). С. 115–119.
3. Buzdalova A., Buzdalov M. Increasing efficiency of evolutionary algorithms by choosing between auxiliary fitness functions with reinforcement learning // Proc. 11th Int. Conf. on Machine Learning and Applications. Boca Raton, USA, 2012. V. 1. P. 150–155. doi: 10.1109/ICMLA.2012.32
4. Buzdalov M., Buzdalova A., Shalyto A. A first step towards the runtime analysis of evolutionary algorithm adjusted with reinforcement learning // Proc. 12th Int. Conf. on Machine Learning and Applications. Miami, USA, 2013. V. 1. P. 203–208. doi: 10.1109/ICMLA.2013.42
5. Buzdalov M., Buzdalova A. Adaptive selection of helper-objectives for test case generation // Proc. IEEE Congress on Evolutionary Computation. Cancun, Mexico, 2013. V. 1. P. 2245–2250. doi: 10.1109/CEC.2013.6557836
6. Buzdalov M., Buzdalova A., Petrova I. Generation of tests for programming challenge tasks using multi-objective optimization // Proc. Genetic and Evolutionary Computation Conference Companion. Amsterdam, Netherlands, 2013. P. 1655–1658. doi: 10.1145/2464576.2482746
7. Knowles J.D., Watson R.A., Corne D. Reducing local optima in single-objective problems by multi-objectivization // Lecture Notes in Computer Science. 2001. V. 1993. P. 269–283.
8. Petrova I., Buzdalova A., Buzdalov M. Improved selection of auxiliary objectives using reinforcement learn-ing in non-stationary environment // Proc. 13th Int. Conf. on Machine Learning and Applications. Detroit, USA, 2014. P. 580–583. doi: 10.1109/ICMLA.2014.99
9. Applegate D.L., Bixby R.E., Chvatal V., Cook W.J. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2007. 608 p.
10. Jensen M.T. Helper-objectives: using multi-objective evolutionary algorithms for single-objective optimisa-tion: evolutionary computation combinatorial optimization // Journal of Mathematical Modelling and Algo-rithms. 2004. V. 3. N. 4. P. 323–347.
11. Jähne M., Li X., Branke J. Evolutionary algorithms and multi-objectivization for the travelling salesman problem // Proc. 11th Annual Genetic and Evolutionary Computation Conference. Montreal, Canada, 2009. P. 595–602. doi: 10.1145/1569901.1569984
12. Скобцов Ю.А., Федоров Е.Е. Метаэвристики. Донецк: Ноулидж, 2013. 426 с.
13. Sutton R.S., Barto A.G. Reinforcement Learning: An Introduction. Cambridge: MIT Press, 1998. 322 p.
14. Afanasyeva A., Buzdalov M. Optimization with auxiliary criteria using evolutionary algorithms and reinforcement learning // Proc. 18th Int. Conf. on Soft Computing MENDEL. Brno, Czech Republic, 2012. P. 58–63.
15. Derrac J., Garcia S., Molina D., Herrera F. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms // Swarm and Evolutionary Computation. 2011. V. 1. N 1. P. 3–18. doi: 10.1016/j.swevo.2011.02.002
 

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License