Русская Википедия:Теорема схем

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Теорема схем, или теорема шаблонов — основная теорема теории генетических алгоритмов, дающая обоснование их эффективности. Впервые сформулирована и доказана Дж. Холландом в 1975 году.

Понятие схемы

Схемой называется подмножество множества всех возможных генотипов, возможных в данной популяции, заданное в виде хромосомы с фиксированными значениями некоторых битов. Остальные биты могут принимать любые значения, образуя примеры схемы. Так, примерами схемы 00**1* являются хромосомы 000010, 000011, 000110, 000111, 001010, 001011, 001110 и 001111. Количество фиксированных битов называется порядком схемы, а расстояние между крайними фиксированными позициями (т.е. разность их номеров) — её определяющей длиной. Порядок вышеприведённой схемы равен 3, а определяющая длина 5 - 1 = 4. Функция пригодности (ФП) схемы — это среднее значение функции пригодности всех её примеров.

Теорема

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

<math>N(h,t+1) \geq N(h,t) { f(h, t) \over f(t)}[1-p].</math>

Здесь <math>N(h, t)</math> — количество примеров схемы h на шаге t, а <math>N(h, t+1)</math> — то же на следующем шаге; <math>f(h, t)</math> — функция пригодности схемы на шаге t; <math>f(t)</math> — среднее значение ФП по всей популяции на том же шаге; <math>p</math> — вероятность уничтожения схемы под действием генетических операторов. Эта вероятность равна:

<math>p = {\delta(h) \over l-1}p_c + o(h) p_m,</math>

где <math>\delta(h)</math> — определяющая длина схемы, <math>o(h)</math> — порядок, <math>p_c</math> — вероятность скрещивания, а <math>p_m</math> — вероятность мутации. Таким образом, полная форма записи теоремы выглядит так:

<math>N(h,t+1) \geq N(h,t) { f(h, t) \over f(t)}[1-{\delta(h) \over l-1}p_c - o(h) p_m].</math>

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

См. также

• Генетический алгоритм

Ссылки

• J. H. Holland. Adaptation in Natural and Artificial Systems. The MIT Press, reprint edition, 1992.
• Liles W. C. Introduction to Schema Theory : A survey lecture of pessimistic & exact schema theory / W. C. Liles, Wiegand R. P. - 2002 Summer Lecture Series, EC lab Activities, Computer Science Department, George Mason University. текст лекции слайды к лекции