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

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

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

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

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

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

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

• Схема - слово длины в алфавите , где имеет смысл любого из символов . В дальнейшем схема будет обозначаться ;
• Пример схемы - особь, удовлетворяющая схеме. Например, если схемой является , то особь является примером, а особь - нет. Число примеров схемы H в обрабатываемой алгоритмом популяции в момент времени (т. е. число особей популяции, удовлетворяющих схеме) будем обозначать как ;
• Порядок схемы - число символов в схеме, не равных ;
• Определяющая длина схемы - расстояние между крайними символами, не равными ;
• Степень приспособленности схемы - средняя степень приспособлености по всем примерам схемы в популяции в момент времени ;
• Средняя приспособленность всей популяции - ;
• - вероятность мутации;
• - вероятность кроссинговера.

Теорема

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

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

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

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

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

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

Критика

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

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

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

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

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