WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

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

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

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

Теорема

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

Здесь — количество примеров схемы h на шаге t, а — то же на следующем шаге; — функция пригодности схемы на шаге t; — среднее значение ФП по всей популяции на том же шаге; — вероятность уничтожения схемы под действием генетических операторов. Эта вероятность равна:

где — определяющая длина схемы, — порядок, — вероятность скрещивания, а — вероятность мутации. Таким образом, полная форма записи теоремы выглядит так:

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

См. также

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии