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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: '''Теорема схемы''' (англ. schema theorem) - теорема, описывающее действие генетического алгоритма (см. [[Генетич...)
Строка 20: Строка 20:
<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>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>o(H)</tex> и <tex>\delta(H)</tex>) сохраняются и покрывают все большую часть популяции. При этом дополнительные ограничения диктуются следующими соображениями: мутации реже разрушают схемы меньшего порядка, а кроссинговер реже разрушает схемы с меньшей определяющей длиной.
 +
==Гипотеза строительных блоков (building block hypothesis)
 +
Была предложена Гольдбергом в 1989 году. Строительный блок - схема, обладающая следующими свойствами:
 +
# Высокой приспособленностью
 +
# Низким порядком
 +
# Короткой определяющей длиной
 +
Как показывает теорема схем, такие блоки экспоненциально увеличивают количество примеров по мере работы алгоритма. В связи с этим была высказана гипотеза, что "строительные блоки объединяются, чтобы сформировать лучшие блоки". Таким образом, рекомбинация и экспоненциальных рост примеров блоков ведет к формированию лучших блоков, которые в конечном итоге дадут решение (решение будет примером самой лучшей схемы-блока). Поэтому можно говорить о том, что ГА ведет поиск на множестве строительных блоков.
 +
===Критика===
 +
Гипотеза строительных блоков не является формальным математическим утверждением. Вот некоторые аргументы, опровергающие ее:
 +
# Теорема схем описывает увеличение количества примеров только в следующем поколении. Далее может измениться приспособленность схемы и популяции, и увеличение может смениться уменьшением.
 +
# Строго говоря, утверждение теоремы схем носит вероятностный характер (в левой части неравенства стоит математическое ожидание). Поэтому возможны отклонения от этого закона, а насколько они велики и вероятны - в теореме не указано.
 +
# Комбинация двух "хороших" строительных блоков не всегда является "хорошей". Существуют примеры, когда такое комбинирование приводит к существенному снижению приспособленности схемы-блока.
 +
Тем не менее, иногда гипотеза строительных блоков выполняется на практике.
 +
==Задача выбора признаков с помощью ГА==
{{Задание|Николай Савинов|В.В. Стрижов|20 июня 2010}}
{{Задание|Николай Савинов|В.В. Стрижов|20 июня 2010}}

Версия 14:19, 5 июня 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. Комбинация двух "хороших" строительных блоков не всегда является "хорошей". Существуют примеры, когда такое комбинирование приводит к существенному снижению приспособленности схемы-блока.

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

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

Данная статья является непроверенным учебным заданием.
Студент: Участник:Николай Савинов
Преподаватель: Участник:В.В. Стрижов
Срок: 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»
Личные инструменты