Генетический алгоритм представляет собой именно такой комбинированный метод. Механизмы скрещивания и мутации в каком-то смысле реализуют переборную часть метода, а отбор лучших решений - градиентный спуск. На рисунке показано, что такая комбинация позволяет обеспечить устойчиво хорошую эффективность генетического поиска для любых типов задач.
Итак, если на некотором множестве задана сложная функция от нескольких переменных, то генетический алгоритм - это программа, которая за разумное время находит точку, где значение функции достаточно близко к максимально возможному. Выбирая приемлемое время расчета, мы получим одно из лучших решений, которые вообще возможно получить за это время.
Определим теперь понятия, соответствующие мутации и кроссинговеру в генетическом алгоритме.
Мутация — это преобразование хромосомы, случайно изменяющее одну или несколько ее позиций (генов). Наиболее распространенный вид мутаций — случайное изменение только одного из генов хромосомы.
Кроссинговер (в литературе по генетическим алгоритмам также употребляется название кроссовер или скрещивание) — это операция, при которой из двух хромосом порождается одна или несколько новых хромосом. В простейшем случае кроссинговер в генетическом алгоритме реализуется так же, как и в биологии (см. рис. 1). При этом хромосомы разрезаются в случайной точке и обмениваются частями между собой. Например, если хромосомы (1, 2, 3, 4, 5) и (0, 0, 0, 0, 0) разрезать между третьим и четвертым генами и обменять их части, то получатся потомки (1, 2, 3, 0, 0) и (0, 0, 0, 4, 5).
Блок-схема генетического алгоритма изображена на рис. 1. Вначале генерируется начальная популяция особей (индивидуумов), т.е. некоторый набор решений задачи. Как правило, это делается случайным образом. Затем мы должны смоделировать размножение внутри этой популяции. Для этого случайно отбираются несколько пар индивидуумов, производится скрещивание между хромосомами в каждой паре, а полученные новые хромосомы помещаются в популяцию нового поколения. В генетическом алгоритме сохраняется основной принцип естественного отбора — чем приспособленнее индивидуум (чем больше соответствующее ему значение целевой функции), тем с большей вероятностью он будет участвовать в скрещивании. Теперь моделируются мутации — в нескольких случайно выбранных особях нового поколения изменяются некоторые гены. Затем старая популяция частично или полностью уничтожается и мы переходим к рассмотрению следующего поколения. Популяция следующего поколения в большинстве реализаций генетических алгоритмов содержит столько же особей, сколько начальная, но в силу отбора приспособленность в ней в среднем выше. Теперь описанные процессы отбора, скрещивания и мутации повторяются уже для этой популяции и т. д.
В каждом следующем поколении мы будем наблюдать возникновение совершенно новых решений нашей задачи. Среди них будут как плохие, так и хорошие, но благодаря отбору число хороших решений будет возрастать. Заметим, что в природе не бывает абсолютных гарантий, и даже самый приспособленный тигр может погибнуть от ружейного выстрела, не оставив потомства. Имитируя эволюцию на компьютере, мы можем избегать подобных нежелательных событий и всегда сохранять жизнь лучшему из индивидуумов текущего поколения — такая методика называется “стратегией элитизма”.
Чтобы использовать генетический алгоритм для решения практических задач, необходимо рассматривать более сложные варианты введенных выше понятий. Поясним это на примере задачи коммивояжера для 20 городов.
В качестве индивидуумов будем рассматривать маршруты обхода. Информацию о маршруте можно записать в виде одной хромосомы — вектора длины 20, где в первой позиции стоит номер первого города на пути следования, затем — номер второго города и т. д. Первое затруднение возникает, когда мы пытаемся определить мутации для таких хромосом — стандартная операция, изменяющая только одну позицию вектора, недопустима, так как приводит к некорректному маршруту. Но можно определить мутацию как перестановку значений двух случайно выбранных генов. При таком преобразовании путь следования меняется только в двух городах.
Найденный маршрут, вероятно, не является самым оптимальным, но близок к нему по длине — как правило, генетические алгоритмы “ошибаются” не более чем на 5—10%. Этот недостаток компенсируется для комбинаторных задач относительно высокой скоростью работы — в нашем примере ответ был получен за 25 секунд. На практике генетические алгоритмы нередко используют совместно с другими методами, которые позволяют повысить их точность.
Эксперименты показали, что погрешность разработанного алгоритма не зависит от погрешности начального решения и составляет (максимальные значения) для ориентированных графов - 5%, для неориентированных 1%. Причем в 90% случаев алгоритм находил точное решение. Эксперименты проводились для графов с количеством вершин, меньшим 75 (где было возможным нахождение точного решения).
1. В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования, 1998 г.
2. Н. Кристофидес. Теория графов: алгоритмический подход, Мир, 1978 г.
3. Ф.А. Новиков. Дискретная математика для программистов, Питер, 2001 г.
4. В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999 г.
5. О. Оре. Теория графов, Наука, 1982 г.
6. www.codenet.ru
7. www.algolist.ru
1000 76 43 38 51 42 19 80
42 1000 49 26 78 52 39 87
48 28 1000 36 53 44 68 61
72 31 29 1000 42 49 50 38
30 52 38 47 1000 64 75 82
66 51 83 51 22 1000 37 71
77 62 93 54 69 38 1000 26
42 58 66 76 41 52 83 1000