doi: 10.17586/2226-1494-2017-17-3-409-416


ТЕОРЕТИЧЕСКИЙ АНАЛИЗ МЕТОДА ВЫБОРА ПЕРЕКЛЮЧАЮЩИХСЯ ВСПОМОГАТЕЛЬНЫХ КРИТЕРИЕВ НА ЗАДАЧЕ XdivK

Петрова И.А., Буздалова А.С., Шалыто А.А.


Язык статьи - русский

Ссылка для цитирования: Петрова И.А., Буздалова А.С., Шалыто А.А. Теоретический анализ метода выбора переключающихся вспомогательных критериев на задаче 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. 11th 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. 12th Int. Conf. on Machine Learning and Applications. Miami, USA, 2013. V. 1. P. 203–208.doi: 10.1109/ICMLA.2013.42


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2024 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика