Теорема схемы
Материал из MachineLearning.
Теорема схемы (англ. schema theorem) - теорема, описывающее действие генетического алгоритма (см. Генетический алгоритм) через понятие схемы. Каждой схеме соответствует некоторое подмножество особей в популяции. При определенных условиях, оговариваемых в теореме, будет выполняться экспоненциальный рост числа особей в этом подмножестве. Теорема была предложена Холландом, и это была первая успешная попытка объяснить действие генетического алгоритма.
Содержание |
Формулировка теоремы
Предположения и обозначения
Пусть используется простой генетический алгоритм, т. е. ГА с одноточечным кроссинговером и одноточечной мутацией.
Будем считать, что особью в популяции является бинарная строка длины . Если это не так, всегда можно закодировать ее нужным образом.
Введем следующие понятия:
- Схема - слово длины
в алфавите
, где
имеет смысл любого из символов
. В дальнейшем схема будет обозначаться
;
- Пример схемы - особь, удовлетворяющая схеме. Например, если схемой является
, то особь
является примером, а особь
- нет. Число примеров схемы H в обрабатываемой алгоритмом популяции в момент времени
(т. е. число особей популяции, удовлетворяющих схеме) будем обозначать как
;
- Порядок схемы
- число символов в схеме, не равных
;
- Определяющая длина схемы
- расстояние между крайними символами, не равными
;
- Степень приспособленности схемы
- средняя степень приспособлености по всем примерам схемы
в популяции в момент времени
;
- Средняя приспособленность всей популяции -
;
-
- вероятность мутации;
-
- вероятность кроссинговера.
Теорема
Интерпретация теоремы
Пусть имеется какая-то начальная популяция. Рассмотрим некоторую схему небольшого порядка с небольшим определяющим расстоянием, степень приспособленности которой больше, чем в среднем по данной популяции. Тогда количество примеров этой схемы в последующих популяциях будет расти экспоненциально (конечно, не до бесконечности, но на протяжении некоторого числа популяций). Таким образом, "хорошие" в смысле приспособленности схемы (с дополнительными ограничениями на и
) сохраняются и покрывают все большую часть популяции. При этом дополнительные ограничения диктуются следующими соображениями: мутации реже разрушают схемы меньшего порядка, а кроссинговер реже разрушает схемы с меньшей определяющей длиной.
Гипотеза строительных блоков (building block hypothesis)
Была предложена Гольдбергом в 1989 году. Строительный блок - схема, обладающая следующими свойствами:
- Высокой приспособленностью
- Низким порядком
- Короткой определяющей длиной
Как показывает теорема схем, такие блоки экспоненциально увеличивают количество примеров по мере работы алгоритма. В связи с этим была высказана гипотеза, что "строительные блоки объединяются, чтобы сформировать лучшие блоки". Таким образом, рекомбинация и экспоненциальных рост примеров блоков ведет к формированию лучших блоков, которые в конечном итоге дадут решение (решение будет примером самой лучшей схемы-блока). Поэтому можно говорить о том, что ГА ведет поиск на множестве строительных блоков.
Критика
Гипотеза строительных блоков не является формальным математическим утверждением. Вот некоторые аргументы, опровергающие ее:
- Теорема схем описывает увеличение количества примеров только в следующем поколении. Далее может измениться приспособленность схемы и популяции, и увеличение может смениться уменьшением.
- Строго говоря, утверждение теоремы схем носит вероятностный характер (в левой части неравенства стоит математическое ожидание). Поэтому возможны отклонения от этого закона, а насколько они велики и вероятны - в теореме не указано.
- Комбинация двух "хороших" строительных блоков не всегда является "хорошей". Существуют примеры, когда такое комбинирование приводит к существенному снижению приспособленности схемы-блока.
Тем не менее, иногда гипотеза строительных блоков выполняется на практике.
Задача выбора признаков с помощью ГА
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |