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

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

(Различия между версиями)

Текущая версия

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

Содержание

1 Формулировка теоремы
- 1.1 Предположения и обозначения
- 1.2 Теорема
2 Интерпретация теоремы
3 Гипотеза строительных блоков (building block hypothesis)
- 3.1 Критика
4 Задача выбора признаков с помощью ГА
5 См. также
6 Литература

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

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

Пусть используется простой генетический алгоритм, то есть ГА с одноточечным кроссинговером и одноточечной мутацией. Будем считать, что особью в популяции является бинарная строка длины $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$ — вероятность кроссинговера.

Теорема

$\mathbb{E} m(H,t+1) \ge m(H,t)\: \frac{f(H,t)}{f_e(t)} \: \left( 1-\frac{P_c\delta(H)}{l-1}-o(H)P_m \right).$

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

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

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

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

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

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

Критика

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

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

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

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

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

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

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

Данные порождались следующим образом (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 итерациях, а потом скачки. Эти скачки можно объяснить так: когда ГА сошелся к решению, все хромосомы очень похожы друг на друга в смысле Хеммингова расстояния, но если за счет мутации одна изменится, то расстояние до остальных станет одинаковым и ненулевым. Поэтому произойдет заметный скачок.
Видна закономерность в том, насколько резок спад: чем больше размер популяции, тем быстрее сходимость.

Выводы

Противоречий с гипотезой строительных блоков в данном случае нет. Наблюдается быстрое уменьшение диаметра популяции, что подтверждает сходимость к некоторой схеме.

См. также

Литература

Zbigniew Michalevicz, «Genetic Algorithms + Data Structures = Evolution Programs» (chapter 3: «GAs: Why Do They Work?»).
Melanie Mitchell, «An Introduction to Genetic Algorithms».

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

Студент: Участник:Nikolay Savinov

Преподаватель: V.V.Strijov

Срок: 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»

Категория: Эволюционные алгоритмы

@@ Строка 1: / Строка 1: @@
-'''Теорема схемы''' (англ. schema theorem) - теорема, описывающее действие генетического алгоритма (см. [[Генетический алгоритм]]) через понятие схемы. Каждой схеме соответствует некоторое подмножество особей в популяции. При определенных условиях, оговариваемых в теореме, будет выполняться экспоненциальный рост числа особей в этом подмножестве. Теорема была предложена Холландом, и это была первая успешная попытка объяснить действие генетического алгоритма.
+'''Теорема схемы''' (англ. schema theorem) — теорема, описывающее действие [[Генетический алгоритм|генетического алгоритма]]  через понятие схемы. Каждой схеме соответствует некоторое подмножество особей в популяции. При определенных условиях, оговариваемых в теореме, будет выполняться экспоненциальный рост числа особей в этом подмножестве. Теорема была предложена Холландом, и это была первая успешная попытка объяснить действие генетического алгоритма.
 __TOC__
-==Формулировка теоремы==
+== Формулировка теоремы ==
-===Предположения и обозначения===
-Пусть используется простой генетический алгоритм, т. е. ГА с одноточечным кроссинговером и одноточечной мутацией.
+=== Предположения и обозначения ===
+Пусть используется простой генетический алгоритм, то есть ГА с одноточечным кроссинговером и одноточечной мутацией.
 Будем считать, что особью в популяции является бинарная строка длины <tex>l</tex>. Если это не так, всегда можно закодировать ее нужным образом.
 Введем следующие понятия:
-* Схема - слово длины <tex>l</tex> в алфавите <tex>\{0,1,*\}</tex>, где <tex>*</tex> имеет смысл любого из символов <tex>\{0,1\}</tex>. В дальнейшем схема будет обозначаться <tex>H</tex>;
+* Схема — слово длины <tex>l</tex> в алфавите <tex>\{0,1,*\}</tex>, где <tex>*</tex> имеет смысл любого из символов <tex>\{0,1\}</tex>. В дальнейшем схема будет обозначаться <tex>H</tex>;
-* Пример схемы - особь, удовлетворяющая схеме. Например, если схемой является <tex>0*1</tex>, то особь <tex>001</tex> является примером, а особь <tex>000</tex> - нет. Число примеров схемы H в обрабатываемой алгоритмом популяции в момент времени <tex>t</tex> (т. е. число особей популяции, удовлетворяющих схеме) будем обозначать как <tex>m(H,t)</tex>;
+* Пример схемы — особь, удовлетворяющая схеме. Например, если схемой является <tex>0*1</tex>, то особь <tex>001</tex> является примером, а особь <tex>000</tex> — нет. Число примеров схемы H в обрабатываемой алгоритмом популяции в момент времени <tex>t</tex> (то есть число особей популяции, удовлетворяющих схеме) будем обозначать как <tex>m(H,t)</tex>;
-* Порядок схемы <tex>o(H)</tex> - число символов в схеме, не равных <tex>*</tex>;
+* Порядок схемы <tex>o(H)</tex> — число символов в схеме, не равных <tex>*</tex>;
-* Определяющая длина схемы <tex>\delta(H)</tex> - расстояние между крайними символами, не равными <tex>*</tex>;
+* Определяющая длина схемы <tex>\delta(H)</tex> — расстояние между крайними символами, не равными <tex>*</tex>;
-* Степень приспособленности схемы <tex>f(H,t)</tex> - средняя степень приспособлености по всем примерам схемы <tex>H</tex> в популяции в момент времени <tex>t</tex>;
+* Степень приспособленности схемы <tex>f(H,t)</tex> — средняя степень приспособлености по всем примерам схемы <tex>H</tex> в популяции в момент времени <tex>t</tex>;
-* Средняя приспособленность всей популяции - <tex>f_e(t)</tex>;
+* Средняя приспособленность всей популяции — <tex>f_e(t)</tex>;
-* <tex>P_m</tex> - вероятность мутации;
+* <tex>P_m</tex> — вероятность мутации;
-* <tex>P_c</tex> - вероятность кроссинговера.
+* <tex>P_c</tex> — вероятность кроссинговера.
-===Теорема===
-<tex>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)</tex>
+=== Теорема ===
-==Интерпретация теоремы==
+<tex>\mathbb{E} m(H,t+1) \ge m(H,t)\: \frac{f(H,t)}{f_e(t)} \: \left( 1-\frac{P_c\delta(H)}{l-1}-o(H)P_m \right).</tex>
-Пусть имеется какая-то начальная популяция. Рассмотрим некоторую схему небольшого порядка с небольшим определяющим расстоянием, степень приспособленности которой больше, чем в среднем по данной популяции. Тогда количество примеров этой схемы в последующих популяциях будет расти экспоненциально (конечно, не до бесконечности, но на протяжении некоторого числа популяций). Таким образом, "хорошие" в смысле приспособленности схемы (с дополнительными ограничениями на <tex>o(H)</tex> и <tex>\delta(H)</tex>) сохраняются и покрывают все большую часть популяции. При этом дополнительные ограничения диктуются следующими соображениями: мутации реже разрушают схемы меньшего порядка, а кроссинговер реже разрушает схемы с меньшей определяющей длиной.
-==Гипотеза строительных блоков (building block hypothesis)==
+== Интерпретация теоремы ==
-Была предложена Гольдбергом в 1989 году. Строительный блок - схема, обладающая следующими свойствами:
+Пусть имеется какая-то начальная популяция. Рассмотрим некоторую схему небольшого порядка с небольшим определяющим расстоянием, степень приспособленности которой больше, чем в среднем по данной популяции. Тогда количество примеров этой схемы в последующих популяциях будет расти экспоненциально на протяжении некоторого числа популяций. Таким образом, «хорошие» в смысле приспособленности схемы (с дополнительными ограничениями на <tex>o(H)</tex> и <tex>\delta(H)</tex>) сохраняются и покрывают все большую часть популяции. При этом дополнительные ограничения диктуются следующими соображениями: мутации реже разрушают схемы меньшего порядка, а кроссинговер реже разрушает схемы с меньшей определяющей длиной.
+== Гипотеза строительных блоков (building block hypothesis) ==
+Была предложена Гольдбергом в 1989 году. Строительный блок — схема, обладающая следующими свойствами:
 # Высокой приспособленностью
 # Низким порядком
 # Короткой определяющей длиной
-Как показывает теорема схем, такие блоки экспоненциально увеличивают количество примеров по мере работы алгоритма. В связи с этим была высказана гипотеза, что "строительные блоки объединяются, чтобы сформировать лучшие блоки". Таким образом, рекомбинация и экспоненциальных рост примеров блоков ведет к формированию лучших блоков, которые в конечном итоге дадут решение (решение будет примером самой лучшей схемы-блока). Поэтому можно говорить о том, что ГА ведет поиск на множестве строительных блоков.
+Как показывает теорема схем, такие блоки экспоненциально увеличивают количество примеров по мере работы алгоритма. В связи с этим была высказана гипотеза, что «строительные блоки объединяются, чтобы сформировать лучшие блоки». Таким образом, рекомбинация и экспоненциальных рост примеров блоков ведет к формированию лучших блоков, которые в конечном итоге дадут решение (решение будет примером самой лучшей схемы-блока). Поэтому можно говорить о том, что ГА ведет поиск на множестве строительных блоков.
-===Критика===
+=== Критика ===
 Гипотеза строительных блоков не является формальным математическим утверждением. Вот некоторые аргументы, опровергающие ее:
 # Теорема схем описывает увеличение количества примеров только в следующем поколении. Далее может измениться приспособленность схемы и популяции, и увеличение может смениться уменьшением.
-# Строго говоря, утверждение теоремы схем носит вероятностный характер (в левой части неравенства стоит математическое ожидание). Поэтому возможны отклонения от этого закона, а насколько они велики и вероятны - в теореме не указано.
+# Строго говоря, утверждение теоремы схем носит вероятностный характер (в левой части неравенства стоит математическое ожидание). Поэтому возможны отклонения от этого закона, а насколько они велики и вероятны — в теореме не указано.
-# Комбинация двух "хороших" строительных блоков не всегда является "хорошей". Существуют примеры, когда такое комбинирование приводит к существенному снижению приспособленности схемы-блока.
+# Комбинация двух «хороших» строительных блоков не всегда является «хорошей». Существуют примеры, когда такое комбинирование приводит к существенному снижению приспособленности схемы-блока.
 Тем не менее, иногда гипотеза строительных блоков выполняется на практике. Далее следует пример.
-==Задача выбора признаков с помощью ГА==
-===Предварительные замечания===
+== Задача выбора признаков с помощью ГА ==
-Суть данной задачи ( см. [[Выбор признаков с помощью генетических алгоритмов (пример)]] ) позволяет предположить, что гипотеза строительных блоков выполняется. Действительно, схемы соответствуют наборам признаков. Тогда логично считать, что в большинстве случаев комбинация хороших наборов должна дать хороший набор.
+=== Предварительные замечания ===
-===Постановка вычислительного эксперимента===
+Суть данной задачи (см. [[Выбор признаков с помощью генетических алгоритмов (пример)]]) позволяет предположить, что гипотеза строительных блоков выполняется. Действительно, схемы соответствуют наборам признаков. Тогда в большинстве случаев комбинация хороших наборов должна дать хороший набор.
-Данные порождались следующим образом (D - дисперсия, D=100):
+=== Постановка вычислительного эксперимента ===
+Данные порождались следующим образом (D — дисперсия, D=100):
 <source lang="matlab">
 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 );
 </source>
-Выборка делилась на training и testing части в соотношении 60%:40% случайным образом.
+Выборка делилась на training и testing части в соотношении 60 %:40 % случайным образом.
 Использовался следующий набор порождающих функций (всего 12): <br />
 <tex>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).</tex> <br />
 В наборе не было следующих функций, участвовавших в порождении: <tex>sin(x),\; x^2*sin(x).</tex> <br />
-Задача решалась простым ГА. При этом менялось значение параметра Размер Популяции. Строились графики Диаметра Популяции от номера итерации. Под диаметром понимается первая норма (т. е. сумма модулей компонент) вектора попарных Хемминговых расстояний между хромосомами в популяции.
+Задача решалась простым ГА. При этом менялось значение параметра Размер Популяции. Строились графики Диаметра Популяции от номера итерации. Под диаметром понимается первая норма (то есть сумма модулей компонент) вектора попарных Хемминговых расстояний между хромосомами в популяции.
-===Результаты===
-[[Изображение:Diameter( number of generations ),PopulationSize=5.png|1000px]] <br />
-[[Изображение:Diameter( number of generations ),PopulationSize=10.png|1000px]] <br />
-[[Изображение:Diameter( number of generations ),PopulationSize=15.png|1000px]] <br />
-На всех 3 графиках четко виден резкий спад на первых 10-20 итерациях, а потом скачки. Эти скачки можно объяснить так: когда ГА сошелся к решению, все хромосомы очень похожы друг на друга, но если за счет мутации одна изменится, то расстояние до остальных станет одинаковым и ненулевым. Поэтому произойдет заметный скачок. <br />
-Видна закономерность в том, насколько резок спад: чем больше Размер Популяции, тем быстрее сходимость.
-===Выводы===
-Вероятно, гипотеза строительных блоков в данном случае выполняется.
-== Смотрите также ==
+=== Результаты ===
+[[Изображение:Diameter( number of generations ),PopulationSize=10N.png|600px]] <br />
+[[Изображение:Diameter( number of generations ),PopulationSize=15N.png|600px]] <br />
+[[Изображение:Diameter( number of generations ),PopulationSize=20N.png|600px]] <br />
+На всех 3 графиках четко виден резкий спад на первых 10-20 итерациях, а потом скачки. Эти скачки можно объяснить так: когда ГА сошелся к решению, все хромосомы очень похожы друг на друга в смысле Хеммингова расстояния, но если за счет мутации одна изменится, то расстояние до остальных станет одинаковым и ненулевым. Поэтому произойдет заметный скачок. <br />
+Видна закономерность в том, насколько резок спад: чем больше размер популяции, тем быстрее сходимость.
+=== Выводы ===
+Противоречий с гипотезой строительных блоков в данном случае нет. Наблюдается быстрое уменьшение диаметра популяции, что подтверждает сходимость к некоторой схеме.
+== См. также ==
 * [[Генетический алгоритм]]
 * [[Выбор признаков с помощью генетических алгоритмов (пример)]]
 == Литература ==
-* http://algolist.manual.ru/ai/ga/ga1.php
+* Zbigniew Michalevicz, «Genetic Algorithms + Data Structures = Evolution Programs» (chapter 3: «GAs: Why Do They Work?»).
-{{Задание|Николай Савинов|В.В. Стрижов|20 июня 2010}}
+* Melanie Mitchell, «An Introduction to Genetic Algorithms».
+{{ЗаданиеВыполнено|Nikolay Savinov|V.V.Strijov|20 июня 2010||strijov}}
+[[Категория:Эволюционные алгоритмы]]