3.3 Hybrid algorithm (L. "Dave" Davis)
Использование гибридного алгоритма позволяет объединить преимущества ГА с преимуществами классических методов. Дело в том, что ГА являются робастными алгоритмами, т.е. они позволяют находить хорошее решение, но нахождение оптимального решения зачастую оказывается намного более трудной задачей в силу стохастичности принципов работы алгоритма. Поэтому возникла идея использовать ГА на начальном этапе для эффективного сужения пространства поиска вокруг глобального экстремума, а затем, взяв лучшую особь, применить один из "классических" методов оптимизации. Характеристики алгоритма:
- Фиксированный размер популяции.
- Фиксированная разрядность генов.
- Любые комбинации стратегий отбора и формирования следующего поколения
- Ограничений на тип кроссовера и мутации нет.
- ГА применяется на начальном этапе, а затем в работу включается классический метод оптимизации.[23]
3.4 Island Model GA
Представим себе следующую ситуацию. В некотором океане есть группа близкорасположенных островов, на которых живут популяции особей одного вида. Эти популяции развиваются независимо, и только изредка происходит обмен представителями между популяциями. Островная модель ГА использует описанный принцип для поиска решения. Вариант, безусловно, интересный и является одной из разновидностей параллельных ГА. Данная модель генетического алгоритма обладает следующими свойствами:
- Наличие нескольких популяций, как правило, одинакового фиксированного размера.
- Фиксированная разрядность генов.
- Любые комбинации стратегий отбора и формирования следующего поколения в каждой популяции. Можно сделать так, что в разных популяциях будут использоваться разные комбинации стратегий, хотя даже один вариант дает разнообразные решения на различных "островах".
- Ограничений на тип кроссовера и мутации нет.
- Случайный обмен особями между "островами". Если миграция будет слишком активной, то особенности островной модели будут сглажены, и она будет не очень сильно отличаться от моделей ГА без параллелизма.[24]
3.5 CHC (Eshelman)
CHC расшифровываетсякак Cross-population selection, Heterogenous recombination and Cataclysmic mutation. Данный алгоритм довольно быстро сходится из-за того, что в нем нет мутаций, используются популяции небольшого размера, и отбор особей в следующее поколение ведется и между родительскими особями, и между их потомками. В силу этого после нахождения некоторого решения алгоритм перезапускается, причем лучшая особь копируется в новую популяцию, а оставшиеся особи подвергаются сильной мутации (мутирует примерно треть битов в хромосоме) существующих и поиск повторяется. Еще одной специфичной чертой является стратегия скрещивания: все особи разбиваются на пары, причем скрещиваются только те пары, в которых хромосомы особей существенно различны (хэммингово расстояние больше некоторого порогового плюс возможны ограничения на минимальное расстояние между крайними различающимися битами). При скрещивании используется так называемый HUX-оператор (Half Uniform Crossover) - это разновидность однородного кроссовера, но в нем к каждому потомку попадает ровно половина битов хромосомы от каждого родителя. Таким образом, модель обладает следующими свойствами:
- Фиксированный размер популяции.
- Фиксированная разрядность генов.
- Перезапуск алгоритма после нахождения решения.
- Небольшая популяция.
- Особи для скрещивания разбиваются на пары и скрещиваются при условии существенных отличий.
- Отбор в следующее поколение проводится между родительскими особями и потомками.
- Используется половинный однородный кроссовер (HUX).
- Макромутация при перезапуске.[25]
II. Практическая часть реализации генетических алгоритмов
В данной учебно-исследовательской работе приведен пример программы использующей генетический алгоритм. Программа создана посредством среды программирования С++. Алгоритм компонента представляет собой применение методов, известных в теории эволюции, для эвристического поиска решений переборных задач.
1. Математическое обоснование принципа работы программы
Проверим эффективность работы генетических алгоритмов на примере нахождения значений коэффициентов неизвестных в Диофа́нтовом уравнении.
Диофа́нтово уравнение или уравнение в целых числах — это уравнение с целыми коэффициентами и неизвестными, которые могут принимать только целые значения. Названы в честь древнегреческого математика Диофанта.[26]
Рассмотрим диофантово уравнение: a+2b+3c+4d=30, где a, b, c и d - некоторые положительные целые. Применение ГА за очень короткое время находит искомое решение (a, b, c, d).
Архитектура ГА-систем позволяет найти решение быстрее за счет более 'осмысленного' перебора. Мы не перебираем все подряд, но приближаемся от случайно выбранных решений к лучшим.
Для начала выберем 5 случайных решений: 1 =< a,b,c,d =< 30. Вообще говоря, мы можем использовать меньшее ограничение для b,c,d, но для упрощения пусть будет 30.
| Хромосома | (a,b,c,d) |
| 1 | (1,28,15,3) |
| 2 | (14,9,2,4) |
| 3 | (13,5,7,3) |
| 4 | (23,8,16,19) |
| 5 | (9,13,5,2) |
Таблица 1: 1-е поколение хромосом и их содержимое
Чтобы вычислить коэффициенты выживаемости (fitness), подставим каждое решение в выражение a+2b+3c+4d. Расстояние от полученного значения до 30 и будет нужным значением.
| Хромосома | Коэффициент выживаемости |
| 1 | |114-30|=84 |
| 2 | |54-30|=24 |
| 3 | |56-30|=26 |
| 4 | |163-30|=133 |
| 5 | |58-30|=28 |
Таблица 2: Коэффициенты выживаемости первого поколения хромосом (набора решений)
Так как меньшие значения ближе к 30, то они более желательны. В нашем случае большие численные значения коэффициентов выживаемости подходят, увы, меньше. Чтобы создать систему, где хромосомы с более подходящими значениями имеют большие шансы оказаться родителями, мы должны вычислить, с какой вероятностью (в %) может быть выбрана каждая. Одно решение заключается в том, чтобы взять сумму обратных значений коэффициентов, и исходя из этого вычислять проценты. (Заметим, что все решения были сгенерированы Генератором Случайных Чисел - ГСЧ)
| Хромосома | Подходящесть |
| 1 | (1/84)/0.135266 = 8.80% |
| 2 | (1/24)/0.135266 = 30.8% |
| 3 | (1/26)/0.135266 = 28.4% |
| 4 | (1/133)/0.135266 = 5.56% |
| 5 | (1/28)/0.135266 = 26.4% |
Таблица 3: Вероятность оказаться родителем
Для выбора 5-и пар родителей (каждая из которых будет иметь 1 потомка, всего - 5 новых решений), представим, что у нас есть 10000-стонняя игральная кость, на 880 сторонах отмечена хромосома 1, на 3080 - хромосома 2, на 2640 сторонах - хромосома 3, на 556 - хромосома 4 и на 2640 сторонах отмечена хромосома 5. Чтобы выбрать первую пару кидаем кость два раза и выбираем выпавшие хромосомы. Таким же образом выбирая остальных, получаем:
| Хромосома отца | Хромосома матери |
| 3 | 1 |
| 5 | 2 |
| 3 | 5 |
| 2 | 5 |
| 5 | 3 |
Таблица 4: Симуляция выбора родителей
Каждый потомок содержит информацию о генах и отца и от матери. Вообще говоря, это можно обеспечить различными способами, однако в нашем случае можно использовать т.н. "кроссовер" (cross-over). Пусть мать содержит следующий набор решений: a1,b1,c1,d1, а отец - a2,b2,c2,d2, тогда возможно 6 различных кроссоверов (| = разделительная линия):
| Хромосома-отец | Хромосома-мать | Хромосома-потомок |
| a1 | b1,c1,d1 | a2 | b2,c2,d2 | a1,b2,c2,d2 or a2,b1,c1,d1 |
| a1,b1 | c1,d1 | a2,b2 | c2,d2 | a1,b1,c2,d2 or a2,b2,c1,d1 |
| a1,b1,c1 | d1 | a2,b2,c2 | d2 | a1,b1,c1,d2 or a2,b2,c2,d1 |
Таблица 5: Кроссоверы между родителями
Есть достаточно много путей передачи информации потомку, и кроссовер - только один из них. Расположение разделителя может быть абсолютно произвольным, как и то, отец или мать будут слева от черты.
А теперь попробуем проделать это с нашими потомками
| Хромосома-отец | Хромосома-мать | Хромосома-потомок |
| (13 | 5,7,3) | (1 | 28,15,3) | (13,28,15,3) |
| (9,13 | 5,2) | (14,9 | 2,4) | (9,13,2,4) |
| (13,5,7 | 3) | (9,13,5 | 2) | (13,5,7,2) |
| (14 | 9,2,4) | (9 | 13,5,2) | (14,13,5,2) |
| (13,5 | 7, 3) | (9,13 | 5, 2) | (13,5,5,2) |
Таблица 6: Симуляция кросс-оверов хромосом родителей
Теперь мы можем вычислить коэффициенты выживаемости (fitness) потомков.
| Хромосома-потомок | Коэффициент выживаемости |
| (13,28,15,3) | |126-30|=96 |
| (9,13,2,4) | |57-30|=27 |
| (13,5,7,2) | |57-30|=22 |
| (14,13,5,2) | |63-30|=33 |
| (13,5,5,2) | |46-30|=16 |
Таблица 7: Коэффициенты выживаемости потомков (fitness)
Средняя приспособленность (fitness) потомков оказалась 38.8, в то время как у родителей этот коэффициент равнялся 59.4. Следующее поколение может мутировать. Например, мы можем заменить одно из значений какой-нибудь хромосомы на случайное целое от 1 до 30.