Метод генетического алгоритма

Генетические алгоритмы (ГА) - адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течении нескольких поколений, подчиняясь законам естественного отбора и по принципу " выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином.

ГА используют прямую аналогию с таким механизмом. Они работают с совокупностью " особей" - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь (хромосома, генотип) оценивается мерой ее " приспособленности" согласно тому, насколько " хорошо" соответствующее ей решение задачи. Например, мерой приспособленности могло бы быть отношение силы/веса для данного проекта моста. (В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы – воду и пищу.)

Рисунок 1 – Схема работы ГА

 

Наиболее приспособленные особи получают возможность " воспроизводить" потомство с помощью " перекрестного скрещивания" с другими особями популяции - хромосомы делятся на два (одноточечный кроссовер) или несколько сегментов (многоточечный кроссовер) и меняются полученными фрагментами. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Дополнительно особи-потомки могут мутировать (изменять один или несколько генов), что также изменяет их приспособленность. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. На каждом этапе эволюции в ГА отбираются самые приспособленные особи (рис. 1).

 

Разработано много способов реализации идеи биологической эволюции в рамках ГА. Традиционным, классическим считается ГА, представленный на схеме:

 

1. Создать начальную популяцию (случайным образом)

2.Оценить приспособленность каждой особи

3. Выбрать две особи с высокой приспособленностью для скрещивания

4. Скрестить выбранные особи и получить двух потомков с помощью кроссовера.

5. Провести мутацию потомка (потомков)

6. Оценить приспособленности потомков

7. Если популяция сошлась ТО останов, ИНАЧЕ перейти к п.4

 

ГА является достаточно мощным средством и может с успехом применяться для широкого класса прикладных задач, включая те, которые трудно, а иногда и невозможно, решить другими методам. Однако, ГА, как и другие методы эволюционных вычислений, не гарантирует обнаружения глобального решения за полиномиальное время, а остановиться на локальном экстремуме (рис. 2). ГА хороши для поиска " достаточно хорошего" решения задачи " достаточно быстро".

Если задача может быть решена специальными методами (например, известна функция управления – прибыль компании y = f(x₁, x₂, …, x_n) и нужно найти её максимум), то почти всегда такие методы будут эффективнее ГА и в быстродействии и в точности найденных решений. Главным же преимуществом ГА является то, что они могут применяться даже на сложных задачах, там, где не существует никаких специальных методов. Там, где хорошо работаю существующие методики, можно достигнуть улучшения сочетанием их с ГА. Специальные методы, напр., метод наискорейшего спуска или метод производных часто определяют не глобальный, а локальный экстремум, поскольку перебирают не все точки области определения (ОО) функции (т.е. области изменения её аргументов x₁, x₂, …, x_n. ГА основан на случайном выборе значений аргументов, поэтому перебирает всю ОО функции (хотя останов работы ГА при достижении локального экстремума не исключён).

Рисунок 2 – Глобальные и локальные экстремумы т.3 – глобальный максимум, т.2 – глобальный минимум, т.т.1, 5 – локальные максимумы, т.т.4, 6 – локальные минимумы

х

у=f(х)

Кроме того, с помощью ГА можно определять не только экстремумы функций, но и условия достижения ими конкретной величины, напр., найти значения x₁, x₂, …, x_n, при которых функция у= f(x₁, x₂, …, x_n) примерно равно 5.

Структура данных генетического алгоритма состоит из одной или более количества хромосом (обычно из одной). Как правило, хромосома - это битовая строка, так что термин " строка" часто заменяет понятие " хромосома". Один разряд хромосомы – это ген.

Шаблон – это хромосома, у которой некоторые гены фиксированы.

При реализации генетических алгоритмов на компьютере активно используется генератор случайных чисел (ГСЧ).

Пример 1. Определить максимум функции у=x₁³-x₂+4, (1)

если x₁ изменяется в диапазоне от 0 до 3, а х₂ – от 2 до 10.

 

Генетический алгоритм решения задачи имеет вид:

 

3 Перевод х1, х2 в 10-й код

1 Начало

12 Скрещивание х1, х2 в 2-м коде

13 Мутация х1 или х2 в 2-м коде (ГСЧ)

14 х1, х2 в диапазоне?

нет

да

5 Оценка приспособленности у = x13-x2+4

4 х1, х2 в диапазоне?

нет

да

6 ГА сходится?

да

нет

9 Конец

2 Ввод битовых кодов хромосом х1, х2 (ГСЧ)

7 Вывод у, х1, х2 (ГСЧ)

8 уi+1 > уi

да

10 Выбор хромосом х1, х2 с уi+1

11 Выбор хромосом х1, х2 с уi max

нет

 

 

Перед началом работы алгоритма представим параметры в виде битовых строк, для чего переведём десятичные числа в двоичные с помощью таблицы перевода (табл.1).

 

Определим длину строк – хромосом. Для записи параметра х₁ требуется два двоичных разряда (числа от 00 до 11, для x₂ – четыре двоичных разряда (числа от 0000 до 1010).

Хромосомы для ГА должны быть одинаковой длины, поэтому принимаем её равной 4, но для параметра х₁ используем шаблон хромосомы 00**. Это значит, что левые нули в строке фиксированы, а позиции со звёздочками могут принимать любые значения, 0 или 1.

Таблица 1 10-й код 2-й код

Описание работы алгоритма:

1. Блоки 2, 3. Создание начальной популяции (первого поколения) – случайным образом, с помощью ГСЧ, например:

х₁ = 0001₂ =1₁₀; х₂ = 0111₂ = 7₁₀.

Блок 4. Проверка – попали ли x₁ и x₂ в свои ОО – соответственно в [0; 3] и [2; 10]. Если нет, то хромосомы генерируются ГСЧ заново (одна или обе) – возврат в блок 2, если да, то:

Блок 5. Оценка приспособленности особей – переведём двоичные коды хромосом в десятичные по таблице 1 и вычислим значение функции (1): у_i = у₀ = x₁³-x₂+4 = 1³-7+4 = -2 (где i = 0 – номер итерации – цикла). При этом значения у_i и x₁, x₂ в двоичном коде сохраняются.

Блок 6. Проверка сходимости генетического алгоритма. ГА сходится, если после многократных итераций было получено несколько – до 5-6 примерно одинаковых экстремумов. Если да, то переход на блок 7 – Вывод у, х₁, х₂ и блок 9 – конец вычислений, если нет – переход на блок 8 (при первой итерации блок пропускается, т.к. пока известно одно значение y = у₀).

Блок 8. Выбор хромосом с наибольшим у. Если новый у_i+1 больше предыдущего у_i, то для дальнейших поколений используются его хромосомы (блок 10), если нет, то хромосомы c наибольшим из предыдущих функций приспособленности - у_{i max} (блок 11). При первой итерации блок также пропускается. Таким образом, в ГА производится отбор наиболее приспособленных поколений.

Блок 12. Скрещивание особей. Разделим хромосомы точкой кроссовера пополам на два одинаковых сегмента и поменяем местами правые сегменты хромосом – получим два новых генотипа:

х₁ = 0001 → 00.01 00.11

х₂ = 0111 → 01.11 01.01

проверку на диапазон пока не проводим, т.к. мутация может ещё раз изменить гены.

Блок 13. Проводим мутацию хромосом. Для этого в одной из особей нужно с помощью ГСЧ инвертировать один из генов в любом месте (выбор хромосомы также производит ГСЧ).

Допустим, ГСЧ изменил в новой особи х₁ четвёртый ген с 1 на 0:

х₁ = 001 0 = 2

х₂ = 0101 = 5

Блок 14. Проверка нахождения x₁ и x₂ в своих ОО, т.к. при мутации значения переменных могли выйти из диапазонов [0; 3] и [2; 10].

Если нет (хромосома вне диапазона) – возврат в блок 13 и новая мутация, если да – переход на блок 5 и оценка приспособленности новых особей по функции (1): у_i+1 = у₁ = 2³-5+4 = 7.

Дальнейшее описание работы ГА выполнено без указания блоков алгоритма:

2.Значение функции (у_i+1 = у₁ = 7) больше предыдущего (у_i = у₀ = -2), поэтому для следующего скрещивания выбираем новое поколение с у_i+1, скрещиваем его:

х₁ = 0010 → 00.10 00. 01

х₂ = 0101 → 01.01 01.10

и мутируем, например, согласно ГСЧ – первый ген в х₂:

х₁ = 0001

х₂ = 1 110

Полученное значение х₂ = 14, т.е. выходит за область определения функции (х₂ = 2…10), поэтому перезапускаем ГСЧ и получаем, например, мутацию 3-го гена в х₂:

х₁ = 0001 = 1

х₂ = 01 0 0 = 4

Функция приспособленности даёт значение у₂= 1³-4+4 = 1.

3. Значение функции у₂ = 1 меньше предыдущего (у₁ = 7), поэтому отбраковываем это поколение, для следующей итерации берём прежние хромосомы и мутируем их – ГСЧ выдал 3-й ген в х₁:

х₁ = 0010 → 00.10 00.01 → 00. 1 1 = 3

х₂ = 0101 → 01.01 01.10 → 01.10 = 6

Функция приспособленности равна у₃= 3³-6+4 = 25.

4. Значение функции у₃ = 25 больше у₁ = 7, поэтому цикл (скрещивание, мутация и вычисление функции приспособленности) повторяется для последнего поколения:

х₁ = 0011 → 00.11 00.10 → 00.10 = 2

х₂ = 0110 → 01.10 01.11 → 0 0. 11 = 3

мутации подвергся 2-й ген в х₂. Функция приспособленности у₄= 2³-3+4 = 9.

 

5. Функция у₄= 9 меньше 25, поэтому полученную популяцию не берём, используем снова прежние, наиболее приспособленные хромосомы с другой мутацией от ГСЧ – в 4-м гене х₁:

х₁ = 0011 → 00.11 00.10 → 00.1 1 = 3

х₂ = 0110 → 01.10 01.11 → 01.11 = 7

Функция приспособленности у₅ = 3³-7+4 = 24.

6. Значение у₅ меньше у₃ = 25, поэтому используем снова хромосомы из п.3 с другой мутацией от ГСЧ – во 2-м гене х₂:

х₁ = 0011 → 00.11 00.10 → 00.11 = 3

х₂ = 0110 → 01.10 01.11 → 0 0. 11 = 3

Функция приспособленности у₆ = 3³-3+4 = 28.

7. Значение у₆ больше 25, поэтому используем новый набор хромосом как самый приспособленный, скрещиваем его и мутируем (по ГСЧ – 4-й ген х₂):

х₁ = 0011 → 00.11 00.11 → 00.11 = 3

х₂ = 0011 → 00.11 00.11 → 00.1 0 = 2

 

Функция приспособленности у₇ = 3³-2+4 = 29.

8. Величина у₇ больше 28, поэтому скрещиваем новый набор хромосом и мутируем (по ГСЧ – 4-й ген х₁):

х₁ = 0011 → 00.11 00.10 → 00.1 1 = 3

х₂ = 0010 → 00.10 00.11 → 00.11 = 3

Снова функция приспособленности у₈= 3³-3+4 = 28.

9. Функция у₈ меньше 29, поколение отбрасываем, а скрещиваем и мутируем набор хромосом с функцией у₇ = 29 (мутация по ГСЧ – 3-й ген х₂):

х₁ = 0011 → 00.11 00.10 → 00.10 = 2

х₂ = 0010 → 00.10 00.11 → 00. 1 0 = 2

Функция приспособленности у= 2³-2+4 = 10.

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

х₁ = 0011 → 00.11 00.10 → 00. 1 1 = 3

х₂ = 0010 → 00.10 00.11 → 00.11 = 3

Снова получили функцию приспособленности у₁₀= 3³-3+4 = 28

…..и так далее…

 

В результате работы ГА в Примере 1 за 10 циклов были получены следующие результаты:

№ этапа	Параметр	Набор хромосом	Результат скрещивания	Результат мутации	Функция приспособленности
Начальная популяция	х1 x2		-	-	-2
	х1 x2		00.11 01.01	0010
	х1 x2		00.01 01.10	0100
	х1 x2		00.01 01.10	00.11 01.10
	х1 x2		00.10 01.11	00.10 00.11
	х1 x2		00.10 01.11	00.11 01.11
	х1 x2		00.10 01.11	00.11 00.11
	х1 x2		00.11 00.11	00.11 00.10
	х1 x2		00.10 00.11	00.11 00.11
	х1 x2		00.10 00.11	00.10 00.01
	х1 x2		00.10 00.11	00. 11 00.11

 

Процесс эволюции продолжается до тех пор, пока ГА не сойдётся, т.е. наибольшие значения функции приспособленности не повторятся несколько раз.

В примере 1 в циклах 6, 7, 8 и 10 стали повторяться результаты функции приспособленности в области 28-29 единиц, поэтому можно считать, что ГА сошёлся. При этом действительный максимум у= 3³-2+4 = 29 был достигнут на 7 этапе, хотя это не обязательно должно было произойти – так, на уровень в 28 единиц ГА выходил 3 раза.

В действительности для решения с помощью ГА сложной задачи требуется не 10, а около 100 – 500 итераций, но на современных компьютерах они просчитываются за несколько секунд.