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

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

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

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

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

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

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

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