лекции ННТЗУ / Лекция_7_ГА_2

Основная теорема о генетических алгоритмах

Если допустить, что схема S имеет приспособленность на ε % выше средней

Получим

Из этого следует, что в процессе репродукции схемы, оказавшиеся лучше (хуже) средних, выбираются на очередных итерациях генетического алгоритма в показательно возрастающих (убывающих) количествах.

Основная теорема о генетических алгоритмах

Основная теорема генетических алгоритмов, иначе называемая теоремой о схемах:

Схемы малого порядка, с малым охватом и с приспособленностью выше средней формируют показательно возрастающее количество своих представителей в последующих поколениях генетического алгоритма.

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

Основная теорема о генетических алгоритмах

Генетический алгоритм стремится достичь близкого к оптимальному результата за счет комбинирования хороших схем (с приспособленностью выше средней) малого порядка и малого охвата Такие схемы называются кирпичиками (либо строительными блоками).

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

Основная теорема о генетических алгоритмах

Схемы малого порядка с малым охватом и приспособленностью выше средней выбираются, размножаются и комбинируются, в результате чего формируются всё лучшие кодовые последовательности. Поэтому решение строится путём объединения наилучших из полученных к текущему моменту частичных решений. Простое скрещивание не слишком часто уничтожает схемы с малым охватом, однако ликвидирует схемы с достаточно большим охватом.

Однако, невзирая на губительность операций скрещивания и мутации для схем высокого порядка и охвата, количество обрабатываемых схем настолько велико, что даже при относительно низком количестве хромосом в популяции достигаются весьма неплохие результаты выполнения генетического алгоритма.

Количество эффективно обрабатываемых схем, рассчитанное Холландом, составляет О(N3). Это означает, что для популяции мощностью N количество обрабатываемых в каждом поколении схем имеет порядок N3.