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

к аналитически неразрешимым или сложнорешаемым проблемам через последовательный подбор и

комбинирование искомых параметров с использованием механизмов, напоминающих биологическую эволюцию.

вычислениями, которые объединяют различные варианты использования эволюционных принципов для достижения

поставленной цели.
Также в ней выделяют следующие направления:
Эволюционные стратегии
Генетическое программирование
Эволюционное программирование
Было впервые предложено Л.Дж. Фогелем в 1960 году для моделирования эволюции как процесса обучения с целью создания искусственного интеллекта. Он использовал конечные автоматы, предсказывающие символы в цифровых последовательностях, которые, эволюционируя, становились более приспособленными к решению поставленной задачи.

на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
Настройка и обучение

искусственной нейронной сети
Задачи компоновки
Составление расписаний
Игровые стратегии
Аппроксимация функций
Искусственная жизнь
Биоинформатика

Дарвин опубликовал в 1859 году свою знаменитую работу "Происхождение видов",

где были провозглашены основные принципы эволюционной теории:
Наследственность (потомки сохраняют свойства родителей)
Изменчивость (потомки почти всегда не идентичны)
Естественный отбор (выживают наиболее приспособленные).
Тем самым было показано, какие принципы приводят к эволюционному развитию флоры и фауны под влиянием окружающей среды. Однако вопрос о том, как генетическая информация передается от родителей потомкам, долгое время оставался открытым.
В 1944 году Эйвери, Маклеод и Маккарти опубликовали результаты своих исследований, доказывавших, что за наследственные процессы ответственна "кислота дезоксирибозного типа". Однако о том, как работает ДНК, стало известно позднее.
В 1953 году в номере журнала "Nature" вышла статья Уотсона и Крика, которые впервые предложили модель двухцепочной спирали ДНК.
Таким образом, стали известны все необходимые компоненты для реализации эволюционной модели.

его интересовала, прежде всего, способность природных систем к адаптации, а

его мечтой было создание такой системы, которая могла бы приспосабливаться к любым условиям окружающей среды.
В 1975 году Холланд публикует свою самую знаменитую работу «Adaptation in Natural and Artificial Systems». В ней он впервые ввёл термин «генетический алгоритм» и предложил схему классического генетического алгоритма (canonical GA). В дальнейшем понятие «генетические алгоритмы» стало очень широким, и зачастую к ним относятся алгоритмы, сильно отличающиеся от классического ГА.
Ученики Холланда – Кеннет Де Йонг и Дэвид Голдберг – внесли огромный вклад в развитие ГА. Наиболее известная работа Голдберга – «Genetic algorithms in search optimization and machine learning» (1989).

существо — это некоторое решение нашей задачи. Будем считать особь

тем более приспособленной, чем лучше соответствующее решение (чем большее значение целевой функции оно дает). Тогда задача максимизации целевой функции сводится к поиску наиболее приспособленного существа.
Будем рассматривать много поколений, сменяющих друг друга. Если ввести в действие естественный отбор и генетическое наследование то полученный мир будет подчиняться законам эволюции. В соответствии с нашим определением приспособленности, целью этой искусственной эволюции будет как раз создание наилучших решений.
Принудительно остановив этот процесс через достаточно долгое время после его начала и выбрав наиболее приспособленную особь в текущем поколении, мы получим не абсолютно точный, но близкий к оптимальному ответ.
Для того чтобы говорить о генетическом наследовании, нужно снабдить наши существа хромосомами. В генетическом алгоритме хромосома — это некоторый числовой вектор, соответствующий изменяемым параметрам задачи, а набор хромосом данной особи определяет решение задачи. Какие именно векторы следует рассматривать в конкретной задаче, решает пользователь. Каждая из позиций вектора хромосомы называется геном.

Мутация — это преобразование хромосомы, случайно изменяющее одну или несколько

ее позиций (генов). Наиболее распространенный вид мутаций — случайное изменение только одного из генов хромосомы.
Кроссовер (cross-over, в литературе по генетическим алгоритмам также употребляется название кроссинговер или скрещивание) — это операция, при которой из двух хромосом порождается одна или несколько новых хромосом.
В простейшем случае кроссовер в генетическом алгоритме реализуется так же, как и в биологии. При этом хромосомы разрезаются в случайной точке и обмениваются частями между собой. Например, если хромосомы (1, 2, 3, 4, 5) и (0, 0, 0, 0, 0) разрезать между третьим и четвертым генами и обменять их части, то получатся потомки (1, 2, 3, 0, 0) и (0, 0, 0, 4, 5).

путем отбора (selection) текущего поколения
скрещивание (recombination) особей промежуточной популяции путем

кроссовера (crossover), что приводит к формированию нового поколения
мутация нового поколения

решений задачи. Как правило, это делается случайным образом.
2. Моделируется

размножение внутри этой популяции:
рассчитываются вероятности участия индивидуумов в скрещивании: чем приспособленнее индивидуум, то есть чем больше (меньше) соответствующее ему значение целевой функции, тем с большей вероятностью он будет участвовать в скрещивании,
с учетом рассчитанных вероятностей случайно составляется несколько пар индивидуумов,
производится скрещивание между хромосомами в каждой паре,
полученные новые хромосомы помещаются в популяцию нового поколения.
3. Моделируются мутации — в нескольких случайно выбранных особях нового поколения изменяются некоторые гены.
4. Старая популяция частично или полностью уничтожается и переходим к рассмотрению следующего поколения – к шагу 2.

Алгоритм работы

же особей, сколько начальная, но в силу отбора приспособленность в

ней в среднем выше. Описанные процессы отбора, скрещивания и мутации повторяются уже для этой популяции и т. д.
В каждом следующем поколении мы будем наблюдать возникновение совершенно новых решений нашей задачи. Среди них будут как плохие, так и хорошие, но благодаря отбору число хороших решений будет возрастать.
В природе не бывает абсолютных гарантий, и даже самый приспособленный тигр может погибнуть от ружейного выстрела, не оставив потомства. Имитируя эволюцию, мы можем избегать подобных нежелательных событий и всегда сохранять жизнь лучшему из индивидуумов текущего поколения — такая методика называется “стратегией элитизма”.

достижение требуемых значений целевой функции. Эффективность во многом определяется структурой

и составом начальной популяции.
При создании начального множества решений происходит формирование популяции на основе четырех основных принципов:
«одеяла» – генерируется полная популяция, включающая все возможные решения в некоторой заданной области;
«дробовика» – подразумевает случайный выбор альтернатив из всей области решений данной задачи.
«фокусировки» – реализует случайный выбор допустимых альтернатив из заданной области решений данной задачи.
Комбинирования – состоит в различных совместных реализациях первых трех принципов.

так называемая точка оператора кроссинговера, или разрезающая точка оператора crossover,

которая обычно определяется случайно. Эта точка определяет место в двух хромосомах, где они должны быть «разрезаны».

Одноточечный оператор crossover

Одноточечный оператор кроссинговера выполняется в три этапа:
Две хромосомы A = а1, а2,.., аL и B = a1, a2,.., aL выбираются случайно из текущей популяции.
Число k выбирается из {1,2,...,L-1} также случайно. Здесь L - длина хромосомы, k - точка оператора crossover (номер, значение или код гена, после которого выполняется разрез хромосомы).
Две новые хромосомы формируются из A и B путем перестановок элементов согласно правилу

Р1 : 1 1 | 1 1 1
Р2 : 0 0 | 0 0 0
________________
Р'1 : 1 1 | 0 0 0
Р'2 : 0 0 | 1 1 1

оператора crossover, и хромосомы обмениваются участками, расположенными между двумя точками

оператора crossover.

Р1 : 1 1 1 | 0 1 | 0 0
Р2 : 0 0 0 | 1 1 | 1 0
____________________
Р'1 : 1 1 1 | 1 1 | 0 0
Р'2 : 0 0 0 | 0 1 | 1 0

Пример двухточечного оператора crossover

Развитием двухточечного оператора crossover является многоточечный оператор crossover или N-точечный оператор crossover. Многоточечный оператор crossover выполняется аналогично двухточечному оператору crossover, хотя большое число «разрезающих» точек может привести к потере «хороших» родительских свойств.

Р1 : 1 | 1 1 |0 1 | 0 0
Р2 : 0 | 0 0 |1 0 | 1 1
____________________
Р'1 : 1| 0 0 | 0 1 | 1 1
Р'2 : 0| 1 1 | 1 0 | 0 0

Пример трехточечного оператора crossover

конструкция, позволяющая на основе преобразования родительской хромосомы (или ее части)

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

Р1 : 0 1 1 | 0 1 1
Р'1 : 0 1 0 | 1 1 1

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

Р : A | B C D | E F
P' : A E С D B F

Одноточечный оператор мутации

Р1 – родительская хромосома, а Р'1 – хромосома-потомок после применения одноточечного оператора мутации

Двухточечный оператор мутации

Р1 – родительская хромосома, а Р'1 – хромосома-потомок после применения двухточечного оператора мутации

где 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)

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
Так как меньшие значения ближе к 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%

1
5 2
3 5
2 5
5 3
Каждый потомок содержит информацию о генах и отца и от матери. Вообще говоря, это можно обеспечить различными способами, однако в нашем случае можно использовать одноточечный кроссовер. Пусть мать содержит следующий набор решений: 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,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)
Теперь мы можем вычислить коэффициенты выживаемости (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
Средняя приспособленность (fitness) потомков оказалась 38.8, в то время как у родителей этот коэффициент равнялся 59.4.
Следующее поколение может мутировать. Например, мы можем заменить одно из значений какой-нибудь хромосомы на случайное целое от 1 до 30.

может служить заданное количество поколений или схождение (convergence) популяции.

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

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

осуществляется синхронизация коллективной работы группы свидетелей или эффективная организация работы одного свидетеля по восстановлению фоторобота.

полигонами;
- Редактирование лица осуществляется 150 параметрами;
- Вращение и

перемещение головы в пространстве;
- Есть возможность проведения операций кроссинговера и
мутации фотороботов.

Modeller

решать широкий спектр задач.
Генетические алгоритмы имеют множество модификаций и

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