Теорема схемы Холланда

Теорема о схеме Холланда , также называемая фундаментальной теоремой генетических алгоритмов , ^[1] представляет собой неравенство, которое получается в результате грубой детализации уравнения для эволюционной динамики . Теорема о схеме гласит, что короткие схемы низкого порядка с пригодностью выше средней экспоненциально увеличиваются в частоте в последовательных поколениях. Теорема была предложена Джоном Холландом в 1970-х годах. Первоначально она была широко принята в качестве основы для объяснения мощности генетических алгоритмов . Однако эта интерпретация ее последствий подверглась критике в нескольких публикациях, рассмотренных в ^[2] , где показано, что теорема о схеме является частным случаем уравнения Прайса с функцией индикатора схемы в качестве макроскопического измерения.

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

Описание

Рассмотрим двоичные строки длиной 6. Схема 1*10*1описывает набор всех строк длиной 6 с 1 в позициях 1, 3 и 6 и 0 в позиции 4. * — это подстановочный символ, который означает, что позиции 2 и 5 могут иметь значение 1 или 0. Порядок схемы определяется как количество фиксированных позиций в шаблоне, в то время как определяющая длина — это расстояние между первой и последней определенными позициями. Порядок равен 4, а его определяющая длина — 5. Приспособленность схемы — это средняя пригодность всех строк, соответствующих схеме. Приспособленность строки — это мера значения закодированного решения задачи, вычисляемая с помощью оценочной функции, специфичной для задачи. Используя установленные методы и генетические операторы генетических алгоритмов , теорема о схеме утверждает, что короткие схемы низкого порядка с пригодностью выше среднего увеличиваются экспоненциально в последовательных поколениях. Выражается в виде уравнения: ${\displaystyle o(H)}$ ${\displaystyle \delta (H)}$1*10*1

${\displaystyle \operatorname {E} (m(H,t+1))\geq {m(H,t)f(H) \over a_{t}}[1-p].}$

Здесь — число строк, принадлежащих схеме в поколении , — наблюдаемая средняя пригодность схемы , — наблюдаемая средняя пригодность в поколении . Вероятность нарушения — это вероятность того, что кроссинговер или мутация разрушит схему . При условии, что , ее можно выразить как: ${\displaystyle m(H,t)}$ ${\displaystyle H}$ ${\displaystyle t}$ ${\displaystyle f(H)}$ ${\displaystyle H}$ ${\displaystyle a_{t}}$ ${\displaystyle t}$ ${\displaystyle p}$ ${\displaystyle H}$ ${\displaystyle p_{m}\ll 1}$

${\displaystyle p={\delta (H) \over l-1}p_{c}+o(H)p_{m}}$

где — порядок схемы, — длина кода, — вероятность мутации, — вероятность кроссинговера. Таким образом, схема с более короткой определяющей длиной с меньшей вероятностью будет нарушена. Часто неправильно понимаемый момент — почему теорема о схеме является неравенством , а не равенством. Ответ на самом деле прост: теорема игнорирует малую, но ненулевую вероятность того, что строка, принадлежащая схеме, будет создана «с нуля» путем мутации одной строки (или рекомбинации двух строк), которая не принадлежала в предыдущем поколении. Более того, выражение для явно пессимистично: в зависимости от партнера по спариванию рекомбинация может не нарушить схему, даже если точка пересечения выбрана между первой и последней фиксированной позицией . ${\displaystyle o(H)}$ ${\displaystyle l}$ ${\displaystyle p_{m}}$ ${\displaystyle p_{c}}$ ${\displaystyle \delta (H)}$
${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle p}$ ${\displaystyle H}$

Ограничение

График многомодальной функции двух переменных.

Теорема о схеме справедлива при условии, что генетический алгоритм поддерживает бесконечно большую популяцию, но не всегда переносится на (конечную) практику: из-за ошибки выборки в начальной популяции генетические алгоритмы могут сходиться на схемах, которые не имеют селективного преимущества. Это происходит, в частности, в мультимодальной оптимизации , где функция может иметь несколько пиков: популяция может дрейфовать , предпочитая один из пиков, игнорируя другие. ^[3]

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

Ссылки

1. Бриджес, Клейтон Л.; Голдберг, Дэвид Э. (1987). Анализ воспроизведения и кроссинговера в двоично-кодированном генетическом алгоритме. 2-я Международная конференция по генетическим алгоритмам и их приложениям. ISBN 9781134989737.
2. Альтенберг, Л. (1995). Теорема о схеме и теорема Прайса. Основы генетических алгоритмов, 3, 23-49.
3. Дэвид Э., Голдберг; Ричардсон, Джон (1987). Генетические алгоритмы с разделением для оптимизации многомодальных функций. 2-я Международная конференция по генетическим алгоритмам и их приложениям. ISBN 9781134989737.

• Дж. Холланд, Адаптация в естественных и искусственных системах , Издательство MIT; Переиздание 1992 г. (первоначально опубликовано в 1975 г.).
• Дж. Холланд, Скрытый порядок: как адаптация создает сложность , Helix Books; 1996.