Эволюционное программирование Глава 5. A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming ЭП краткий обзор Разработано: - презентация

1 Эволюционное программирование Глава 5

2 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming ЭП краткий обзор Разработано: США, 1960 гг Разработчик: D. Fogel Обычно применяется: – традиционное ЭП: решение задач с помощью конечных машин – современное ЭП: (цифровая) оптимизация Возможности: – открытая структура: любое утверждение и изменение ops OK – гибрид с ES (современное ЭП) – следовательно, трудно сказать, что такое стандартное ЭП Особенности: – нет рекомбинации – автоматическая адаптация к стандартным параметрам (современное ЭП)

3 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming ЭП техническая сводка ПредставлениеВекторы действительных значений РекомбинацияОтсутствует Характер измененийВозмущение Гаусса Определение предковДетерминированное Определение потомков Вероятностное ( + ) ОсобенностиАвтоматическая адаптация к изменению размера шага (в meta- ЭП)

4 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming Историческая перспектива ЭП ЭП предназначено для программирования интеллекта Интеллект рассматривался как адаптивное поведение Прогнозирование окружающей среды рассматривалось как этап, предшествующий адаптивному Таким образом, способность прогнозировать – ключ к интеллекту

5 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming Прогнозирование машинами с ограниченными состояниями Машины с ограниченными состояниями (МОС): – Состояния S – Входные потоки I – Выходные потоки O – Функция перехода : S x I S x O – Трансформация входного потока в выходной поток Может использоваться для прогнозирования, то есть для предсказания следующего символа в последовательности

6 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming МОС пример Рассматривается МОС: – S = {A, B, C} – I = {0, 1} – O = {a, b, c} – определяется с помощью диаграммы

7 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming МОС как средство прогнозирования Рассматриваем нижеописанную МОС Задание: определить следующий ввод информации Качество: % вход (i+1) = выход i Задается начальное положение C Вводится последовательность На выходе: Качество: 3 из 5

8 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming Вводный пример: развитие МОС для прогнозирования начальных состояний P(n) = 1 если n – начальное состояние, иначе 0 I = N = {1,2,3,…, n, …} O = {0,1} Правильный прогноз: выход i = P(вход (i+1) ) Функция соответствия: – 1 очко за верное предсказание следующего введенного элемента – 0 очков за неверный прогноз – Штраф за слишком много состояний

9 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming Вводный пример: развитие МОС для прогнозирования начальных состояний Определение предка: каждый МОС изменяется только 1 раз Оператор изменения (выбирается случайным образом): – Изменяет выходной символ – Изменяет состояние перехода – Добавляет состояние – Удаляет состояние – Изменяет первоначальное состояние Определение потомка: ( + ) Результаты: после 202 входов лучшая МОС имела одно состояние и оба выхода были 0

10 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming Современное ЭП Нет предопределенной представительности в целом Соответственно, нет предопределенной мутации Обычно применяется самоадаптация параметров мутации Впоследствии мы представляем один вариант ЭП, не каноническое ЭП

11 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming Представление Для оптимизации непрерывных параметров Хромосомы состоят из двух частей: – Объектные переменные: x 1,…,x n – Размер шага мутации: 1,…, n Общий размер: x 1,…,x n, 1,…, n

12 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming Изменение Хромосомы: x 1,…,x n, 1,…, n i = i (1 + N(0,1)) x i = x i + i N i (0,1) 0.2 Условие границы: < 0 = 0 Другие варианты, предложенные и опробованные: – Логарифмическая схема в ES – Использование variance вместо стандартного отклонения – Изменение последнего – Другие изменения, например, Cauchy вместо Gaussian

13 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming Рекомбинация Отсутствует Обоснование: объект поиска – это вид, а не отдельный экземпляр и не может быть никаких скрещиваний между экземплярами разных видов Большие споры на тему мутация vs. скрещивание Прагматичное приближение превалирует в наше время

14 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming Определение предка Каждый отдельный создает одного потомка при мутации Соответственно: – Детерминированное – Не предопределяется соответствием

15 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming Определение потомков P(t): предки, P(t): потомки Парные соревнования (формат round-robin): – Каждое решение x из P(t) P(t) оценивается q по сравнению с решением, выбираемым случайно – Для каждого сравнения определяется «победа» если x лучше, чем оппонент – -решения с наибольшим числом побед запоминаются, чтобы быть предками в следующем поколении Параметр q позволяет настраивать сжатие выборки Типично q = 10

16 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming Пример приложения: функция Экли (Bäck et al 93) Функция Экли (The Ackley function) (при n =30): Репрезентация: – -30 < x i < 30 (coincidence of 30s!) – 30 variances as step sizes При мутации сначала изменяются объектные переменные ! Размер популяции = 200, выбор при q = 10 Завершение : после адекватных оценок Результаты: среднее лучшее решение –2

17 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming Пример приложения: развитие игроков-защитников (Fogel02) Нейронные сети для подсчета будущих значений передвижений Нейронные сети имеют фиксированную структуру весом 5046, + 1 вес для королей Репрезентация : – Вектор из 5046 действительных чисел для объектных переменных (веса) – Вектор из 5046 действительных чисел Мутация: – Гаусса, логарифмическая схема с первым – Плюс специальный механизм для «королевских» весов Размер популяции 15

18 A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Evolutionary Programming Пример приложения: развитие игроков-защитников (Fogel02) Размер турнира q = 5 Программы (с нейронными сетями внутри) играли с другими программами без людей-тренеров или каких-либо управляющих устройств После 840 поколений (6 месяцев!) лучшая стратегия была снова протестирована людьми через интернет Программа получила ранг эксперт-класс

19 Зорина Наталья Владимировна Группа