Введение

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

Описание

Рассмотрим двоичные строки длиной 6. Схема 1*10*1 описывает множество всех строк длиной 6 с единицами в позициях 1, 3 и 6 и нулем в позиции 4. Символ * является подстановочным знаком, что означает, что позиции 2 и 5 могут иметь значение либо 1, либо 0. Порядок схемы определяется как количество фиксированных позиций в шаблоне, а определяющая длина – расстояние между первой и последней фиксированной позицией. Порядок схемы 1*10*1 равен 4, а её определяющая длина равна 5. Пригодность схемы – это средняя пригодность всех строк, соответствующих данной схеме. Пригодность строки является мерой ценности закодированного решения задачи, вычисляемой с помощью специфической оценочной функции. Используя устоявшиеся методы и генетические операторы генетических алгоритмов, теорема о схемах утверждает, что короткие схемы низкого порядка с пригодностью выше средней увеличиваются экспоненциально из поколения в поколение. Это выражается уравнением:

Здесь – количество строк, принадлежащих схеме в поколении , – наблюдаемая средняя пригодность схемы, а – наблюдаемая средняя пригодность в поколении . Вероятность разрушения – это вероятность того, что кроссовер или мутация уничтожат схему. При предположении , она может быть выражена как:

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

Ограничение

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