Пример 4.11

Пример 4.10

В условиях примера 4.5 рассмотрим схему

и проследим ее обработку при выполнении генетического алгоритма. Длина L = 5, а охват и порядок схемы S₃ составляют d(S₃) - 1 и o(S₃) = 2 соответственно. В исходной популяции из примера 4.5 этой схеме соответствуют три хромосомы

ch., = [10011]

ch₂ = [00011]

ch₃ = [00111]

В отличие от примеров 4.8 и 4.9 приспособленность схемы S₃ в исходной популяции оказывается меньше средней приспособленно­сти особей этой популяции F (0) = 589 и составляет F(S3, 0) = 280. Ожидаемое количество хромосом родительского пула, соответствую­щих схеме S₃ и рассчитанное по формуле (4.9), равно 3 * 280/589 = 1,426. В примере 4.5 в родительский пул была включена одна хромо­сома [10011], соответствующая схеме S₃. На основе формулы (4.10) получаем значение 1,068, определяющее количество представителей схемы S₃ в новой популяции. В примере 4.5 после скрещивания с ве­роятностью р_с = 1 (вероятность мутации р_т = 0) в новую популяцию была включена одна хромосома, соответствующая схеме S₃, т.е. Сп₂ = [10111].

В условиях примера 4.5 рассмотрим схему

S₄ = *10** и проследим ее обработку при выполнении генетического алгоритма.

Длина L = 5, а охват и порядок схемы S₄ составляют с1(Ь₄) = 1 и o(S₄) = 2 соответственно. В исходной популяции из примера 4.5 этой схеме соответствует только одна хромосома ch₅ = [01000]

Поэтому приспособленность схемы S₄ в исходной популяции равна значению функции приспособленности хромосомы ch₅ и со­ставляет 129. Аналогично примеру 4.10, она меньше средней приспо­собленности особей начальной популяции, которая равна 589. Ожи­даемое количество представителей схемы S₄ в родительском пуле составляет 129/589 = 0,22, что следует из формулы (4.9). В примере 4.5 родительский пул (после селекции) не содержит ни одной хромо­сомы, соответствующей схеме S₄. При расчете ожидаемого количест­ва представителей схемы S₄ в новой популяции по формуле (4.10) для вероятности скрещивания р_с = 1 и вероятности мутации р_т = 0 по­лучаем значение 0,165. В примере 4.5 после скрещивания в новую по­пуляцию не была включена ни одна хромосома, соответствующая схеме S₄.

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

Из примеров 4.7 - 4.11, посвященных обработке схем, можно сделать следующие выводы. Эти примеры иллюстрируют основную теорему генетических алгоритмов - теорему о схемах. Они затрагива­ют обработку схем низкого (малого) порядка с малым охватом. При­меры 4.7 - 4.9 демонстрируют увеличение количества представите­лей данной схемы в следующем поколении для случая, когда приспо­собленность этой схемы превышает среднюю приспособленность всех особей популяции. Примеры 4.10 и 4.11 показывают ситуацию, когда приспособленность схемы оказывается меньше средней при­способленности особей популяции Количество представителей таких схем в следующих поколениях не увеличивается, а наоборот - наблю­дается уменьшение количества соответствующих им хромосом.

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

Графическая интерпретация схем, обсуждавшихся в примерах 4.8 и 4.11, представлена на рис. 4.9; аналогичным образом можно проиллюстрировать схемы из примеров 4.9 и 4.10, равно как и любые другие. На рис. 4.9 видно, что к схеме 1**** (пример 4.8) в исходной популяции из примера 4.5 принадлежат хромосомы ch.,, ch₄ и ch₆ с фенотипами 19, 21, 29 соответственно, а после селекции и скрещи­вания к этой схеме уже принадлежат все включенные в новую попу­ляцию хромосомы, т.е. Ch.,, Ch₂, Ch₃, Ch₄, Ch₅, и Ch₆ с фенотипами 17, 23,21, 29,29, 29 соответственно. В то же время к схеме *10** (при­мер 4.11) в исходной популяции из примера 4.5 принадлежит только одна хромосома ch₅, фенотип которой равен 8; в следующей популя­ции уже нет ни одной хромосомы, принадлежащей этой схеме. Обра­тим внимание (рис. 4.9), что оптимальное решение, которое максими­зирует функцию, заданную выражением (4.1), принадлежит к схеме 1*^;' и не соответствует схеме *10**

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

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

4. Генетические алгоритмы

2600 2000

I 5 Ю 15 20 25 30 32 (целые числа 0,1,2,...31)

1 5 10 15 20 25 30 32

Схема 1 •'*•

II! IF

(целые числа 16,17,...31}

5 10 15 20 25 30 32

гема * * * * 1

елые числа 1.3 S.31}

1 S 10 15 20 25 30 32

Схема 0 * *"*

(целые чиста 0,1.2....15)

2S00 2000

I 5 10 15 20 25 30 32

Схема 1 О * *"

(цепь* числа 16,17, 23)

1 5 10 15 20 25 30 3 Схема МО** (целые числа 8,9,10,11 и 24,25,:

4.8. Модификации классического генетического алгоритма

Следует упомянуть о том, что в последнее время теорема Хол-ланда о схемах и следующие из нее оценки количества схем, обраба­тываемых генетическим алгоритмом, вызывают в научной среде оп­ределенные возражения [37].

4.8. Модификации классического генетического алгоритма

В классическом генетическом алгоритме (представленном в разд. 4.4 - 4.6 и в примерах 4.4 и 4.5) используется двоичное пред­ставление хромосом, селекция методом колеса рулетки и точечное скрещивание (с одной точкой скрещивания). Для повышения эффек­тивности его работы создано множество модификаций основного ал­горитма. Они связаны с применением других методов селекции, с мо­дификацией генетических операторов (в первую очередь оператора скрещивания), с преобразованием функции приспособленности (пу­тем ее масштабирования), а также с иными способами кодирования параметров задачи в форме хромосом. Существуют также версии ге­нетических алгоритмов, позволяющие находить не только глобаль­ный, но и локальные оптимумы. Это алгоритмы, использующие так называемые ниши, введенные в генетические алгоритмы по аналогии с природными экологическими нишами. Другие версии генетических алгоритмов служат для многокритериальной оптимизации, т.е. для одновременного поиска оптимального решения для нескольких функ­ций. Встречаются также специальные версии генетического алгорит­ма, созданные для решения проблем малой размерности, не требую­щих ни больших популяций, ни длинных хромосом. Их называют ге­нетическими микроалгоритмами.

Дата добавления: 2015-06-04