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

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

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

Описание

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

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

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

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

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

Ограничение

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

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

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

Ссылки

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

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

[1] Бриджес, Клейтон Л.; Голдберг, Дэвид Э. (1987). Анализ воспроизводства и скрещивания в бинарном генетическом алгоритме . 2-я Международная конференция. по генетическим алгоритмам и их приложениям. ISBN 9781134989737 .

[2] Альтенберг, Л. (1995). Теорема о схеме и теорема Прайса . Основы генетических алгоритмов, 3, 23-49.

[3] Дэвид Э., Голдберг; Ричардсон, Джон (1987). Генетические алгоритмы с разделением для оптимизации мультимодальных функций . 2-я Международная конференция. по генетическим алгоритмам и их приложениям. ISBN 9781134989737 .

[ 1 ]

[ 2 ]

[ 3 ]