Теорема схемы
Материал из MachineLearning.
Теорема схемы (англ. schema theorem) - теорема, описывающее действие генетического алгоритма (см. Генетический алгоритм) через понятие схемы. Каждой схеме соответствует некоторое подмножество особей в популяции. При определенных условиях, оговариваемых в теореме, будет выполняться экспоненциальный рост числа особей в этом подмножестве. Теорема была предложена Холландом, и это была первая успешная попытка объяснить действие генетического алгоритма.
Содержание |
Формулировка теоремы
Предположения и обозначения
Пусть используется простой генетический алгоритм, т. е. ГА с одноточечным кроссинговером и одноточечной мутацией. Будем считать, что особью в популяции является бинарная строка длины . Если это не так, всегда можно закодировать ее нужным образом. Введем следующие понятия:
- Схема - слово длины в алфавите , где имеет смысл любого из символов . В дальнейшем схема будет обозначаться ;
- Пример схемы - особь, удовлетворяющая схеме. Например, если схемой является , то особь является примером, а особь - нет. Число примеров схемы H в обрабатываемой алгоритмом популяции в момент времени (т. е. число особей популяции, удовлетворяющих схеме) будем обозначать как ;
- Порядок схемы - число символов в схеме, не равных ;
- Определяющая длина схемы - расстояние между крайними символами, не равными ;
- Степень приспособленности схемы - средняя степень приспособлености по всем примерам схемы в популяции в момент времени ;
- Средняя приспособленность всей популяции - ;
- - вероятность мутации;
- - вероятность кроссинговера.
Теорема
Интерпретация теоремы
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |