Теорема схемы

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск

Kolt (Обсуждение | вклад)
(Новая: '''Теорема схемы''' (англ. schema theorem) - теорема, описывающее действие генетического алгоритма (см. [[Генетич...)
К следующему изменению →

Версия 13:18, 5 июня 2010

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

Содержание


Формулировка теоремы

Предположения и обозначения

Пусть используется простой генетический алгоритм, т. е. ГА с одноточечным кроссинговером и одноточечной мутацией. Будем считать, что особью в популяции является бинарная строка длины l. Если это не так, всегда можно закодировать ее нужным образом. Введем следующие понятия:

  • Схема - слово длины l в алфавите \{0,1,*\}, где * имеет смысл любого из символов \{0,1\}. В дальнейшем схема будет обозначаться H;
  • Пример схемы - особь, удовлетворяющая схеме. Например, если схемой является 0*1, то особь 001 является примером, а особь 000 - нет. Число примеров схемы H в обрабатываемой алгоритмом популяции в момент времени t (т. е. число особей популяции, удовлетворяющих схеме) будем обозначать как m(H,t);
  • Порядок схемы o(H) - число символов в схеме, не равных *;
  • Определяющая длина схемы \delta(H) - расстояние между крайними символами, не равными *;
  • Степень приспособленности схемы f(H,t) - средняя степень приспособлености по всем примерам схемы H в популяции в момент времени t;
  • Средняя приспособленность всей популяции - f_e(t);
  • P_m - вероятность мутации;
  • P_c - вероятность кроссинговера.

Теорема

Expectation(m(H,t+1)) \ge m(H,t)*\frac{f(H,t)}{f_e(t))}*(1-\frac{P_c*\delta(H)}{(l-1)}-o(H)*P_m)

Интерпретация теоремы

Данная статья является непроверенным учебным заданием.
Студент: Участник:Николай Савинов
Преподаватель: Участник:В.В. Стрижов
Срок: 20 июня 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D1%81%D1%85%D0%B5%D0%BC%D1%8B»
Личные инструменты