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

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

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

Содержание 1 Формулировка теоремы 1.1 Предположения и обозначения 1.2 Теорема 2 Интерпретация теоремы

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

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

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

• Схема - слово длины в алфавите , где имеет смысл любого из символов . В дальнейшем схема будет обозначаться ;
• Пример схемы - особь, удовлетворяющая схеме. Например, если схемой является , то особь является примером, а особь - нет. Число примеров схемы H в обрабатываемой алгоритмом популяции в момент времени (т. е. число особей популяции, удовлетворяющих схеме) будем обозначать как ;
• Порядок схемы - число символов в схеме, не равных ;
• Определяющая длина схемы - расстояние между крайними символами, не равными ;
• Степень приспособленности схемы - средняя степень приспособлености по всем примерам схемы в популяции в момент времени ;
• Средняя приспособленность всей популяции - ;
• - вероятность мутации;
• - вероятность кроссинговера.

Теорема

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

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