Язык статьи - русский
Ссылка для цитирования: Петрова И.А., Буздалова А.С., Шалыто А.А. Теоретический анализ метода выбора переключающихся вспомогательных критериев на задаче XdivK // Научно-технический вестник информационных технологий, механики и оптики. 2017. Т. 17. № 3. С. 409–416. doi: 10.17586/2226-1494-2017-17-3-409-416
Аннотация
Предмет исследования.Проведен анализ причин неэффективности метода EA+RL на задаче оптимизации XdivK с переключающимися критериями. Предложена модификация метода EA+RL. Метод EA+RL предназначен для повышения эффективности однокритериальных эволюционных алгоритмов путем введения вспомогательных критериев.Задача XdivK характеризуется большим числом локальных оптимумов.Переключающиеся критерии оказывают помощь на одних этапах оптимизации и позволяют избегать остановки процесса оптимизации в локальных оптимумах, но мешают на других этапах.Метод.Для проведения теоретического анализа метода EA+RL и предложенной его модификации построены марковские цепи, моделирующие процесс оптимизации XdivK. На основе анализа вероятностей переходов в марковских цепях произведена оценка числа вычислений функции приспособленности, необходимого для нахождения оптимума XdivK. Основные результаты. Произведен теоретический анализ метода EA+RL и предложенной его модификации на задаче XdivK с критериями, эффективность которых меняется в зависимости от этапа оптимизации. Приведено доказательство того, что предложенная модификация, в отличие от метода EA+RL, позволяет игнорировать критерий, являющийся мешающим на данном этапе оптимизации. Получена оценка времени работы предложенной модификации.
Ключевые слова: эволюционный алгоритм, обучение с подкреплением, марковские цепи, анализ времени работы
Благодарности. Исследование И.А. Петровой и А.С. Буздаловой выполнено при финансовой поддержке РФФИ в рамках научного проекта № 16-31-00380 мол_а.
Список литературы
1. Скобцов Ю.А., Федоров Е.Е. Метаэвристики. Донецк: Ноулидж, 2013. 426 с.
2. Neumann F., Wegener I. Can single objective optimization profit from multiobjective optimization? / In: Multiobjective Problem Solving from Nature: From Concepts to Applications. 2008. P. 115–130. doi:
10.1007/978-3-540-72964-8_6
3. Neumann F., Wegener I. Minimum spanning trees made easier via multi-objective optimization // Natural Computing. 2006. V. 5. N 3. P. 305–319. doi:
10.1007/s11047-006-9004-x
4. 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.
5. 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
6. Jensen M.T. Helper-objectives: using multi-objective evolutionary algorithms for single-objective optimisation: evolutionary computation combinatorial optimization // Journal of Mathematical Modelling and Algorithms. 2004. V. 3. N. 4. P. 323–347.
7. Lochtefeld D.F., Ciarallo F.W. Helper objective optimization strategies for the job-shop scheduling problem // Applied Soft Computing. 2011. V. 11. N 6. P. 4161–4174. doi:
10.1016/j.asoc.2011.03.007
8. Buzdalova A., Buzdalov M. Increasing efficiency of evolutionary algorithms by choosing between auxiliary fitness functions with reinforcement learning // Proc. 11
th Int. Conf. on Machine Learning and Applications. Boca Raton, USA, 2012. V. 1. P. 150–155.doi:
10.1109/ICMLA.2012.32
9. Буздалова А.С., Буздалов М.В. Метод повышения эффективности эволюционных алгоритмов с помощью обучения с подкреплением // Научно-технический вестник информационных технологий, механики и оптики. 2012. № 5 (81). С. 115–119.
10. Sutton R.S., Barto A.G. Reinforcement Learning: An Introduction. Cambridge: MIT Press, 1998.322 p.
11. Gosavi A. Reinforcement learning: a tutorial survey and recent advances // INFORMS Journal on Computing. 2009. V. 21. N 2. P. 178–192. doi:
10.1287/ijoc.1080.0305
12. 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
13. Buzdalov M., Buzdalova A. OneMax helps optimizing XdivK: theoretical runtime analysis for RLS and EA+RL // Proc. 16th Genetic and Evolutionary Computation Conference. Vancouver, Canada, 2014. P. 201–202.
14. Buzdalov M., Buzdalova A. Can OneMax Help Optimizing LeadingOnes using the EA+RL Method? // Proc. IEEE Congress on Evolutionary Computation. Sendai, Japan, 2015. P. 1762–1768. doi:
10.1109/CEC.2015.7257100
15. Buzdalov M., Buzdalova A., Shalyto A. A first step towards the runtime analysis of evolutionary algorithm adjusted with reinforcement learning // Proc. 12
th Int. Conf. on Machine Learning and Applications. Miami, USA, 2013. V. 1. P. 203–208.doi:
10.1109/ICMLA.2013.42