Машинное обучение

Выбор вспомогательных критериев с помощью обучения с подкреплением

Эффективность оптимизации в некоторых случаях может быть повышена путем введения вспомогательных критериев. В последнее время ведутся активные исследования по применению вспомогательных критериев в задачах дискретной оптимизации, решаемых с помощью эволюционных алгоритмов.
 
Использование вспомогательных критериев позволяет избежать остановку процесса оптимизации в локальных оптимумах целевого критерия, а также расширяет исследуемую область пространства поиска, за счет чего оптимальное значение целевого критерия может быть найдено за меньшее число итераций эволюционного алгоритма.
 
Вспомогательные критерии, как правило, формулируются в ходе анализа задачи. Например, может проводиться декомпозиция целевого критерия на вспомогательные. Также существует пример автоматической генерации вспомогательных критериев для задачи о генерации тестов против решений олимпиадных задач.
 
Обычно об эффективности вспомогательных критериев довольно сложно судить заранее. Более того, один и тот же вспомогательный критерий на различных этапах процесса оптимизации может как ускорять поиск оптимального значения целевого критерия, так и замедлять его. В связи с этим возникает задача автоматического выбора вспомогательного критерия, наиболее эффективного на данном этапе оптимизации, из заранее подготовленного набора критериев.
 
Автоматический выбор вспомогательных критериев может производиться с помощью предложенного сотрудниками нашей лаборатории метода EA+RL, основанного на выборе критериев оптимизации для эволюционного алгоритма с помощью обучения с подкреплением (см. рис.). Агент обучения на каждой итерации эволюционного алгоритма выбирает критерий оптимизации из списка, состоящего из вспомогательных критериев и целевого. Выбранный критерий используется при формировании очередного поколения эволюционного алгоритма. Затем формируется некоторое представление состояния эволюционного алгоритма, а также награда, зависящая от роста целевого критерия. Награда используется для обновления оценки ожидаемой награды в данном состоянии. Выбирается критерий, максимизирующий оценку ожидаемой награды. В случае, когда оценка одинакова, критерии выбираются равновероятно.
 
Эффективность метода EA+RL была подтверждена экспериментально на примере решения ряда модельных задач, а также практической задачи генерации тестов. Также существуют теоретические результаты, показывающий на примере модельных задач, что метод EA+RL позволяет игнорировать неэффективный вспомогательный критерий и выбирать эффективный. 
 
 
Схема EA+RL метода выбора с помощью обучения с подкреплением функции приспособленности (ФП) для использования в эволюционном алгоритме, g(x) - целевая функция, которую необходимо оптимизировать, x - текущее поколение особей эволюционного алгоритма, t - номер поколения.

Информация © 2015-2017 Университет ИТМО
Разработка © 2015 Департамент информационных технологий