«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма АДАПТИВНЫЙ ОПЕРАТОР МУТАЦИИ ДЛЯ НЕЙРОЭВОЛЮЦИОННОГО АЛГОРИТМА Цой Ю.Р., Спицын В.Г. Томский политехнический университет Кафедра вычислительной техники

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма СОДЕРЖАНИЕ 1.Введение 2.Алгоритм NEvA 3.Адаптивный оператор мутации 4.Результаты работы 5.Заключение

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма Использование ИНС включает: 1.Подготовка обучающих данных 2.Выбор архитектуры 3.Обучение 4.Дополнительные операции по оптимизации обученной ИНС 1. Введение (1/2) Генетические алгоритмы (ГА) и искусственные нейронные сети (ИНС) – две концепции, имеющие природные «прототипы».

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма 1. Введение (2/2) Эволюционные алгоритмы для настройки и обучения ИНС: 1.Настройка значений весов связей (F. Gomez, D. Whitley, Л. Комарцова, О. Мосалов) 2.Поиск структуры ИНС (A. Fiszelew, А. Хомич) 3.Одновременная настройка весов и структуры ИНС (C. Ferreira, F.Gruau, C. Igel, D. Moriarty, K. Stanley, X. Yao) Ограничиваемые параметры: - количество скрытых нейронов и топология ИНС; - количество входных связей нейронов; - «направление» эволюции сетей (усложнение/упрощение)

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма 2. Алгоритм NEvA (1/3) NEvA – NeuroEvolutionary Algorithm Настройка весов и структуры ИНС 1 особь = нейронная сеть Популяция = множество нейронных сетей

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма 2. Алгоритм NEvA (2/3) Пример скрещивания:

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма 2. Алгоритм NEvA (3/3) Начальная популяция – ИНС без скрытых нейронов. Усложнение структуры нейронных сетей в процессе эволюции. Нейроны с лог-сигмоидной функцией активации

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма N C – количество связей в сети, N I, N O, N N – соответственно количество входных, выходных нейронов и общее число нейронов в сети, FB – флаг, обозначающий, разрешено появление обратных связей (FB=1) или нет (FB=0) 3. Адаптивный оператор мутации (1/5)

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма f C – степень «связанности» ИНС f N – регуляция скорости усложнения структуры ИНС 3. Адаптивный оператор мутации (2/5) Нет обратных связей (FB = 0) Возможны обратные связи (FB = 1)

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма 3. Адаптивный оператор мутации (3/5) F C = f C 2 F N = F C * f N 2 СВ – случайная величина N H – число скры- тых нейронов СВ > F C Удаление случайного нейрона Добавление случайной связи СВ > F C N H > 0 нет СВ > F N да нет Удаление случайной связи Добавление случайного нейрона СВ > F C & N H > 0 да нет да нет

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма 3. Адаптивный оператор мутации (4/5) Пример СВ > F C Удаление случайного нейрона Добавление случайной связи СВ > F C N H > 0 нет СВ > F N да нет Удаление случайной связи Добавление случайного нейрона СВ > F C & N H > 0 да нет да нет x1x1 x2x2 y1y1 f C = 6 /(0,5*(5*4 – 2*1 – 1*0)) = 0,667 f N = 3/5 = 0,6 F C = f C 2 = 0,445, F N = F C * f N 2 = 0,160 p1p1 p2p2 p3p3p4p4 p1 = ( 1 - F C )(1-F C + F C ) = 0,308 p2 = 0,454, p3 = 0,071, p4 = 0,166

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма 3. Адаптивный оператор мутации (5/5) Вероятность мутации: «Уменьшение вероятности мутации в процессе эволюции улучшает результаты работы ГА» (Schаffer, Caruana, Eshelman, Das, 1989, Goldberg, 1989, Eiben, Hinterding, Michalewicz,1999, Igel, Kreutz, 2003 ) N C – количество связей в ИНС, представленной особью Вероятность мутации разыгрывается N I +N O раз для каждой особи. Таким образом, вероятность k-кратной мутации:

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма Исключающее ИЛИ 4. Результаты экспериментов (1/4) Количество вычислений целевой функции NHNH NCNC Размер популяции NEvA5642,14,9617,0613 NEvA (без адаптации P m ) 6026,264,816,2213 NEAT ,357,48150 NEAT266123,1211,72150 CGA13165, BP5338, BPM828,32417-

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма Балансирование 1 шеста 4. Результаты экспериментов (2/4) Алгоритм Количество попыток NHNH NCNC СреднееЛучшееХудшее GENITOR SANE ESP NEvA (без адаптации P m ) ,585,22 NEvA ,126,46,4

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма Балансирование 2 шестов 4. Результаты экспериментов (3/4) Алгоритм Ср. количество попыток Размер популяции NHNH NCNC Эволюционное программирование N/A SANE N/A ESP NEAT N/A (0–4) N/A (6–15) NEvA (без адаптации P m ) ,47,24 NEvA ,527,14

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма Удаление входных сигналов для задачи балансирования двух маятников: - 7 раз удален 1 вход с сигналом о движении тележки. - 1 раз удалено 2 входа с сигналами о движении тележки. 4. Результаты экспериментов (4/4) Удаление связей может привести к изоляции некоторых входных нейронов в полученной ИНС, и, следовательно, к уменьшению размерности проблемы.

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма 5. Заключение (1/2) Планы на будущее: -исследовать скорость работы алгоритма на задачах, требующих использование обратных связей; -исследовать обобщающие способности получаемых ИНС на примере данных из тестового набора Proben1; -реализовать адаптивную настройку размера популяции, что способно увеличить скорость работы алгоритма до 30%.

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма 5. Заключение (2/2) Использование адаптивной вероятности мутации позволило добиться улучшения скорости работы алгоритма (до 30% процентов в задаче балансирования двух маятников). В алгоритме NEvA нет явного ограничения на сложность структуры получаемых ИНС. Направление эволюции (упрощение или усложнение сетей) также не ограничивается.

«Современные техника и технологии 2005» Адаптивный оператор мутации для нейроэволюционного алгоритма Ваши вопросы Спасибо за внимание!