Теорема схемы

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(→Результаты)
(→Результаты)
Строка 48: Строка 48:
Задача решалась простым ГА. При этом менялось значение параметра Размер Популяции. Строились графики Диаметра Популяции от номера итерации. Под диаметром понимается первая норма (т. е. сумма модулей компонент) вектора попарных Хемминговых расстояний между хромосомами в популяции.
Задача решалась простым ГА. При этом менялось значение параметра Размер Популяции. Строились графики Диаметра Популяции от номера итерации. Под диаметром понимается первая норма (т. е. сумма модулей компонент) вектора попарных Хемминговых расстояний между хромосомами в популяции.
===Результаты===
===Результаты===
-
[[Изображение:Diameter( number of generations ),PopulationSize=10N.png|1000px]] <br />
+
[[Изображение:Diameter( number of generations ),PopulationSize=10N.png|600px]] <br />
-
[[Изображение:Diameter( number of generations ),PopulationSize=15N.png|1000px]] <br />
+
[[Изображение:Diameter( number of generations ),PopulationSize=15N.png|600px]] <br />
-
[[Изображение:Diameter( number of generations ),PopulationSize=20N.png|1000px]] <br />
+
[[Изображение:Diameter( number of generations ),PopulationSize=20N.png|600px]] <br />
На всех 3 графиках четко виден резкий спад на первых 10-20 итерациях, а потом скачки. Эти скачки можно объяснить так: когда ГА сошелся к решению, все хромосомы очень похожы друг на друга, но если за счет мутации одна изменится, то расстояние до остальных станет одинаковым и ненулевым. Поэтому произойдет заметный скачок. <br />
На всех 3 графиках четко виден резкий спад на первых 10-20 итерациях, а потом скачки. Эти скачки можно объяснить так: когда ГА сошелся к решению, все хромосомы очень похожы друг на друга, но если за счет мутации одна изменится, то расстояние до остальных станет одинаковым и ненулевым. Поэтому произойдет заметный скачок. <br />
Видна закономерность в том, насколько резок спад: чем больше Размер Популяции, тем быстрее сходимость.
Видна закономерность в том, насколько резок спад: чем больше Размер Популяции, тем быстрее сходимость.

Версия 08:16, 12 июня 2010

Теорема схемы (англ. schema theorem) - теорема, описывающее действие генетического алгоритма (см. Генетический алгоритм) через понятие схемы. Каждой схеме соответствует некоторое подмножество особей в популяции. При определенных условиях, оговариваемых в теореме, будет выполняться экспоненциальный рост числа особей в этом подмножестве. Теорема была предложена Холландом, и это была первая успешная попытка объяснить действие генетического алгоритма.

Содержание


Формулировка теоремы

Предположения и обозначения

Пусть используется простой генетический алгоритм, т. е. ГА с одноточечным кроссинговером и одноточечной мутацией. Будем считать, что особью в популяции является бинарная строка длины l. Если это не так, всегда можно закодировать ее нужным образом. Введем следующие понятия:

  • Схема - слово длины l в алфавите \{0,1,*\}, где * имеет смысл любого из символов \{0,1\}. В дальнейшем схема будет обозначаться H;
  • Пример схемы - особь, удовлетворяющая схеме. Например, если схемой является 0*1, то особь 001 является примером, а особь 000 - нет. Число примеров схемы H в обрабатываемой алгоритмом популяции в момент времени t (т. е. число особей популяции, удовлетворяющих схеме) будем обозначать как m(H,t);
  • Порядок схемы o(H) - число символов в схеме, не равных *;
  • Определяющая длина схемы \delta(H) - расстояние между крайними символами, не равными *;
  • Степень приспособленности схемы f(H,t) - средняя степень приспособлености по всем примерам схемы H в популяции в момент времени t;
  • Средняя приспособленность всей популяции - f_e(t);
  • P_m - вероятность мутации;
  • P_c - вероятность кроссинговера.

Теорема

Expectation(m(H,t+1)) \ge m(H,t)*\frac{f(H,t)}{f_e(t))}*(1-\frac{P_c*\delta(H)}{(l-1)}-o(H)*P_m)

Интерпретация теоремы

Пусть имеется какая-то начальная популяция. Рассмотрим некоторую схему небольшого порядка с небольшим определяющим расстоянием, степень приспособленности которой больше, чем в среднем по данной популяции. Тогда количество примеров этой схемы в последующих популяциях будет расти экспоненциально (конечно, не до бесконечности, но на протяжении некоторого числа популяций). Таким образом, "хорошие" в смысле приспособленности схемы (с дополнительными ограничениями на o(H) и \delta(H)) сохраняются и покрывают все большую часть популяции. При этом дополнительные ограничения диктуются следующими соображениями: мутации реже разрушают схемы меньшего порядка, а кроссинговер реже разрушает схемы с меньшей определяющей длиной.

Гипотеза строительных блоков (building block hypothesis)

Была предложена Гольдбергом в 1989 году. Строительный блок - схема, обладающая следующими свойствами:

  1. Высокой приспособленностью
  2. Низким порядком
  3. Короткой определяющей длиной

Как показывает теорема схем, такие блоки экспоненциально увеличивают количество примеров по мере работы алгоритма. В связи с этим была высказана гипотеза, что "строительные блоки объединяются, чтобы сформировать лучшие блоки". Таким образом, рекомбинация и экспоненциальных рост примеров блоков ведет к формированию лучших блоков, которые в конечном итоге дадут решение (решение будет примером самой лучшей схемы-блока). Поэтому можно говорить о том, что ГА ведет поиск на множестве строительных блоков.

Критика

Гипотеза строительных блоков не является формальным математическим утверждением. Вот некоторые аргументы, опровергающие ее:

  1. Теорема схем описывает увеличение количества примеров только в следующем поколении. Далее может измениться приспособленность схемы и популяции, и увеличение может смениться уменьшением.
  2. Строго говоря, утверждение теоремы схем носит вероятностный характер (в левой части неравенства стоит математическое ожидание). Поэтому возможны отклонения от этого закона, а насколько они велики и вероятны - в теореме не указано.
  3. Комбинация двух "хороших" строительных блоков не всегда является "хорошей". Существуют примеры, когда такое комбинирование приводит к существенному снижению приспособленности схемы-блока.

Тем не менее, иногда гипотеза строительных блоков выполняется на практике. Далее следует пример.

Задача выбора признаков с помощью ГА

Предварительные замечания

Суть данной задачи ( см. Выбор признаков с помощью генетических алгоритмов (пример) ) позволяет предположить, что гипотеза строительных блоков выполняется. Действительно, схемы соответствуют наборам признаков. Тогда логично считать, что в большинстве случаев комбинация хороших наборов должна дать хороший набор.

Постановка вычислительного эксперимента

Данные порождались следующим образом (D - дисперсия, D=100): 

x = [ 1:0.5:20 ]';
y = x + x.^2 + sin( x ) + log( x ) + x.*log( x ) + ( x.^2 ).*sin( x ) + sqrt( D ) * randn( size( x, 1 ), 1 );

Выборка делилась на training и testing части в соотношении 60%:40% случайным образом. Использовался следующий набор порождающих функций (всего 12):
1,\; x,\; x^2,\; log(x),\; x^3,\; x*log(x),\; x^4,\; x^2*log(x),\; x^2*cos(x),\; cos(x)*log(x),\; x*sin(x)*log(x),\; x^2*cos(x)*log(x).
В наборе не было следующих функций, участвовавших в порождении: sin(x),\; x^2*sin(x).
Задача решалась простым ГА. При этом менялось значение параметра Размер Популяции. Строились графики Диаметра Популяции от номера итерации. Под диаметром понимается первая норма (т. е. сумма модулей компонент) вектора попарных Хемминговых расстояний между хромосомами в популяции.

Результаты




На всех 3 графиках четко виден резкий спад на первых 10-20 итерациях, а потом скачки. Эти скачки можно объяснить так: когда ГА сошелся к решению, все хромосомы очень похожы друг на друга, но если за счет мутации одна изменится, то расстояние до остальных станет одинаковым и ненулевым. Поэтому произойдет заметный скачок.
Видна закономерность в том, насколько резок спад: чем больше Размер Популяции, тем быстрее сходимость.

Выводы

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

Смотрите также

Литература

Данная статья является непроверенным учебным заданием.
Студент: Участник:Николай Савинов
Преподаватель: Участник:В.В. Стрижов
Срок: 20 июня 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D1%81%D1%85%D0%B5%D0%BC%D1%8B»
Личные инструменты