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

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

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

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

коммивояжера, раскраска, нахождение паросочетаний)
Настройка и обучение искусственной нейронной сети
Задачи компоновки
Составление

расписаний
Игровые стратегии
Теория приближений
Искусственная жизнь
Биоинформатика (фолдинг белков)

Применение

в виде вектора («генотипа») генов. Где каждый ген может быть

битом, числом или неким другим объектом.
Некоторым, обычно случайным, образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип им описываемый решает поставленную задачу.

решения (обычно лучшие особи имеют большую вероятность быть выбранными), к

которым применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.
Этот набор действий повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:
нахождение глобального, либо субоптимального решения;
исчерпание числа поколений, отпущенных на эволюцию;
исчерпание времени, отпущенного на эволюцию.

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

числа 7 и 8 в битовом представлении различаются в 4-х позициях, что затрудняет функционирование генетического алгоритма и увеличивает время, необходимое для его сходимости. Для того, чтобы избежать эту проблему лучше использовать кодирование, при котором соседние числа отличаются меньшим количеством позиций, в идеале значением одного бита. Таким кодом является код Грея

Кодирование признаков, представленных целыми числами

0110
5 - 0111
6 - 0101
7 - 0100
8 - 1100
9 -

1101
10 - 1111
11 - 1110
12 - 1010
13 - 1011
14 - 1001
15 - 1000

Код Грея

имеет те же недостатки, что и для целых чисел. Поэтому

на практике обычно применяют следующую последовательность действий:
1.Разбивают весь интервал допустимых значений признака на участки с требуемой точностью.
2.Принимают значение гена как целочисленное число, определяющее номер интервала (используя код Грея).
3.В качестве значения параметра принимают число, являющиеся серединой этого интервала.

Кодирование признаков

использовалось разбиение участка на 256 интервалов. Для кодирования их номера

нам потребуется таким образом 8 бит. Допустим значение гена: 00100101bG (заглавная буква G показывает, что используется кодирование по коду Грея).
Для начала, используя код Грея, найдем соответствующий ему номер интервала: 25hG->36h->54d.
Теперь посмотрим, какой интервал ему соответствует… После несложных подсчетов получаем интервал [0,20703125, 0,2109375].
Значит значение нашего параметра будет (0,20703125+0,2109375)/2=0,208984375.

Пример

описывающих объект) нам необходимо только знать значения генов, соответствующим этим

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

Определение фенотипа

популяцию
3. (Начало цикла)
A. Размножение (скрещивание)
B. Мутирование
C. Вычислить значение целевой функции

для всех особей
D. Формирование нового поколения (селекция)
E. Если выполняются условия останова, то (конец цикла), иначе на шаг 3.

Обобщенный алгоритм

если она окажется совершенно неконкурентоспособной, генетический алгоритм все равно достаточно

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

Создание начальной популяции

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

— оно, конечно, зависит от представления данных. Главное требование к размножению — чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом.
Почему особи для размножения обычно выбираются из всей популяции H, а не из выживших на первом шаге элементов H0 (хотя последний вариант тоже имеет право на существование)? Дело в том, что главный бич многих генетических алгоритмов — недостаток разнообразия (diversity) в особях. Достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом; один из них — выбор для размножения не самых приспособленных, но вообще всех особей.

Размножение (скрещивание)

случайным образом) точка разрыва;
3.потомок определяется как конкатенация части первого и

второго родителя.

Классический оператор скрещивания

тогда
Хромосома_1: 0000000000 >> 000 1111111 Результирующая_хромосома_1
Хромосома_2: 1111111111 >> 111

0000000 Результирующая_хромосома_2
Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.

Пример

размножению: есть некоторая доля мутантов m, являющаяся параметром генетического алгоритма,

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

Мутации

вероятностью инвертируется.
Кроме того, используется еще и так называемый оператор инверсии,

который заключается в том, что хромосома делится на две части, и затем они меняются местами.

долю, которая останется «в живых» на этом этапе эволюции. Есть

разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма, и ее просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.

Отбор

многоточечный, когда формируется несколько точек разрыва (чаще всего две). Кроме

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

Вариации операторов

состоящую из k особей. B0 = {A1,A2,…,Ak)
Вычислить приспособленность каждой

особи FAi = fit(Ai) , i=1…k и популяции в целом Ft = fit(Bt) (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
Выбрать особь Ac из популяции. Ac = Get(Bt)
С определенной вероятностью (вероятностью кроссовера Pc) выбрать вторую особь из популяции Аc1 = Get(Bt) и произвести оператор кроссовера Ac = Crossing(Ac,Ac1).
С определенной вероятностью (вероятностью мутации Pm) выполнить оператор мутации. Ac = mutation(Ac).
С определенной вероятностью (вероятностью инверсии Pi) выполнить оператор инверсии Ac = inversion(Ac).
Поместить полученную хромосому в новую популяцию insert(Bt+1,Ac).
Выполнить операции, начиная с пункта 3, k раз.
Увеличить номер текущей эпохи t=t+1.
Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Алгоритм

метода вероятность выбора хромосомы определяется ее приспособленностью, то есть PGet(Ai)~Fit(Ai)/Fit(Bt).

Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает.
Другой часто используемый метод – турнирный отбор. Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью.
Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма, которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

Этап отбора

эпох функционирования алгоритма, или определение его сходимости, обычно путем сравнивания

приспособленности популяции на нескольких эпохах и остановки при стабилизации этого параметра.

Определение критериев останова

int N = 1000;
int a[N]; //заполняем нулями
fill(a, a+N, 0);
for (;;)
{

//мутация в случайную сторону каждого элемента:
for (int i = 0; i < N; ++i)
if (rand()%2 == 1) a[i] += 1; else a[i] -= 1;
//теперь выбираем лучших, отсортировав по возрастанию...
sort(a, a+N);
//... и тогда лучшие окажутся во второй половине массива. //скопируем лучших в первую половину, куда они оставили потомство, а первые умерли:
copy(a+N/2, a+N, a /*куда*/);
//теперь посмотрим на среднее состояние популяции. Как видим, оно всё лучше и лучше.
cout << accumulate(a, a+N, 0) / N << endl;
}
}

Пример на C++

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

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

Проблемы двоичного кодирования

вектора-решения оптимизационной задачи, иначе говоря, каждый ген будет отвечать за

одну переменную. Генотип объекта становится идентичным его фенотипу.

Вещественное кодирование

в неизвестных), что трудно делать в случае двоичных генов, когда

увеличение пространства поиска сокращает точность решения при неизменной длине хромосомы.
Одной из важных черт непрерывных ГА является их способность к локальной настройке решений.
Использование RGA для представления решений удобно, поскольку близко к постановке большинства прикладных задач. Кроме того, отсутствие операций кодирования/декодирования, которые необходимы в BGA, повышает скорость работы алгоритма.

Преимущества

любые известные из BGA: рулетка, турнирный, случайный.
Операторы скрещивания и мутации

не годятся: в классических реализациях они работают с битовыми строками.

Особенности

C1=(c11,c21,…,cn1) и C2=(c12,c22,…,cn2) – две хромосомы, выбранные оператором селекции для

скрещивания. Предполагается, что ck1<=ck2 и f(C1)>=f(C2).

Оператор кроссовера

– случайное число из интервала [ck1,ck2].
Простейший кроссовер (simple crossover): случайным

образом выбирается число k из интервала {1,2,…,n-1} и генерируются два потомка H1=(c11,c21,…,ck1,ck+12,…,cn2) и H2=(c12,c22,…,ck2,ck+11,…,cn2).

Популярные операторы

hk1=w*ck1+(1-w)*ck2, hk2=w*ck2+(1-w)*ck1, k=1,…,n, w либо константа (равномерный арифметический кроссовер) из

интервала [0;1], либо изменяется с увеличением эпох (неравномерный арифметический кроссовер).


Геометрический кроссовер (geometrical crossover): создаются два потомка H1=(h11,…,hn1), H2=(h12,…,hn2), где hk1= (сk1)w*(ck2)1-w, (ck2)w*(ck1)1-w, w – случайное число из интервала [0;1].

hk – случайное число из интервала [cmin–I*alpha,cmax+I*alpha], cmin=min(ck1,ck2), cmax=max(ck1,ck2), I=cmax–cmin.

BLX-0.0 кроссовер превращается в плоский


Линейный кроссовер (linear crossover): создаются три потомка Hq=(h1q,…,hkq,…,hnq), q=1,2,3, где hk1=0.5*ck1+0.5*ck2, hk2=1.5*ck1-0.5*ck2, hk3=–0.5*сk1+1.5*ck2. На этапе селекции в этом кроссовере отбираются два наиболее сильных потомка.

равномерному закону из конечного множества {ck1,ck2}.


Расширенный линейчатый кроссовер (extended line

crossover): ген hk=ck1+w*(ck2–ck1), w – случайное число из интервала [-0.25;1.25].


Эвристический кроссовер (Wright’s heuristic crossover). Пусть C1 – один из двух родителей с лучшей приспособленностью. Тогда hk=w*(ck1-ck2)+ck1, w – случайное число из интервала [0;1].

H2=(h11,…,hn2). Вероятность того, что в i-том гене появится число vi

, задается распределением p(vi) {F(ck1),F(ck2)}, где F(ck1),F(ck2) – распределения вероятностей треугольной формы (треугольные нечеткие функции принадлежности) со следующими свойствами (ck1<=ck2 и I=|ck1–ck2|):

d=0.5




BLX-кроссовер с параметром alpha=0.5 – превосходит по эффективности большинство простых

кроссоверов.

mutation).
При случайной мутации ген, подлежащий изменению, принимает случайное значение из

интервала своего изменения. В неравномерной мутации значение гена после оператора мутации рассчитывается по формуле:

Оператор мутации

разработан в 1995 году исследовательской группой под руководством K. Deb’а.

Как следует из его названия, этот кроссовер моделирует принципы работы двоичного оператора скрещивания.
Для генерации потомков используется следующий алгоритм, использующий выражение для P(β). Создаются два потомка Hk=(h1k, …, hjk, …, hnk), k=1,2, где , – число, полученное по формуле:

SBX-кроссовер

n [2,5] – параметр кроссовера.
Эксперименты автора SBX кроссовера показали, что

он во многих случаях эффективнее BLX, хотя, очевидно, что не существует ни одного кроссовера, эффективного во всех случаях. Исследования показывают, что использование нескольких различных операторов кроссовера позволяет уменьшить вероятность преждевременной сходимости, т.е. улучшить эффективность алгоритма оптимизации в целом. Для этого могут использоваться специальные стратегии, изменяющие вероятность применения отдельного эволюционного оператора в зависимости от его «успешности», или использование гибридных кроссоверов