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

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

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

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

С помощью ГА получены решения следующих видов оптимизационных задач:

1. Задачи многомерной оптимизации с мультимодальными функциями, для которых по существу нет подходящих не эволюционных методов решения.

2. Стохастические задачи.

3. Динамические задачи с блуждающим оптимизмом.

4. Задача комбинаторной оптимизации большой размерности.

5. Задача прогнозирования и распознавания образов.

Каждое решение задачи (особь) в ГА представлено в виде хромосомы – стринга элементов (строки, генов). Хромосома может быть представлена в двоичном, десятичном (целом или вещественном) представлении, что делает его применимым для широкого спектра задач, для которых не применимы или не эффективны строгие математические методы.

ГА характеризуются следующими основными параметрами:

ГА = (Р⁰, λ, L, S, P, f, t), где

Р⁰ = (а⁰_i …а⁰_λ) – исходная популяция (одно поколение решений, представленное хромосомами);

а⁰_i – решение задачи в виде одной хромосомы;

λ – размер популяции (целое число);

L – длина каждой хромосомы популяции (целое число);

S – оператор отбора (репродукции);

Р – отображение, определяющее оператор рекомбинации;

f – целевая функция (fitness функция);

t – критерий остановки алгоритма.

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

Выделяют следующие особенности алгоритма:

1. Каждая новая популяция состоит только из жизнеспособных хромосом.

2. Каждая новая популяция лучше в смысле целевой функции, чем предыдущая.

3. В процессе эволюции последующая популяция зависит от предыдущей.

Простой генетический алгоритм использует 3 основных оператора:

1. Репродукция (оператор отбора);

2. Кроссинговер (скрещивание);

3. Мутация (воздействие внешней среды);

Простой ГА можно представить простой схемой:

1. Создание исходной популяции. На интервале поиска случайно формируется исходное решение.

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

3. Создание потомков выбранных пар. Оператор кроссинговера обычно выполняется в 3 этапа:

1-й этап. Две хромосомы А = а₁ а₂…а_n и В = b₁ b₂…b_n выбираются из текущей популяции с помощью оператора репродукции.

2-й этап. Случайно выбирается точка кроссинговера – число k, которая находится в пределах 1≤ k ≥ n, где n – длина хромосомы.

3-й этап. Хромосомы А и В обмениваются частями после k-позиции и образуют две новые хромосомы.

A' = a₁a₂…a_k b_k+1…b_L

B' = b₁b₂…b_k a_k+1…a_L

A = 101 10101

B = 110 01010

A' = 10101010

B' = 11010101

4. Оператор мутации. Случайным образом с заданной вероятностью изменяется 1ген в хромосоме. Оператор мутации выполняется в 2 этапа:

1-й этап. В хромосоме А = a₁a₂…a_L-k…a_L-1a_L определяется случайным образом позиция гена, который будет подвержен мутации, где L – длина хромосомы (количество генов в стринге), а k – случайная величина, которая изменяется в диапазоне 0 ≤ k ≥ L.

2-й этап. Значение гена соответственного выбранной позиции заменяют противоположным (инверсным) тем самым формируя новую хромосому А' = a₁a₂…a_L-k'…a_L-1a_L

A = 10010111

A' =10110111.

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

Далее происходит проверка условия остановки алгоритма. Самым простым критерием остановки алгоритма исполнение достижения количества повторений алгоритма.

Пример:

На отрезке от 0 до 31 найти экстремум функции (максимум) в функции y = x².

Начальный этап работы генетического алгоритма приведен в таблице:

№ хромосомы	Начальная популяция особей	Десятичное значение k	Значение f(x)		Среднее значение (x)	Максимальное значение
				0,14
				0,49
				0,06
				0,31

1. Сформирована исходная популяция хромосом случайным образом в заданном интервале. Количество хромосом на заданном интервале задается пользователем.

2. Переведем в десятичную систему каждую из хромосом и подставим в fitness – функцию, получив значение f(x).

3. Произведем оценку полученных хромосом с помощью вероятности попадания хромосомы в следующую популяцию

P(j) =

В нашем примере выбираются хромосомы для популяции кроссинговера (промежуточной), вращая колесо рулетки 4 раза, что соответствует мощности популяции. Ожидаемое количество копий j-хромосомы можно вычислить по формуле:

M = P_j * N, где P_j - вероятность, а N – мощность популяции.

Число копий хромосомы, переходящих в следующее поколение иногда определяется по следующей формуле:

= , где - среднее значение хромосом в популяции.

Расчетные значения копий хромосом:

1.) 0,56

2.) 1,97

3.) 0,22

4.) 1,23

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

Кроссинговер

№ хромосомы	Популяция после репродукции	Пары хромосом для кроссинговера	Популяция после кроссинговера	Значение f (x)	Среднее значение (x)	Максимальное значение fmax(x)
		1 - 2
		1 - 2
		3 - 4
		3 - 4

Одноточечный оператор кроссинговера выполняется с заданной вероятностью Р_с ≈ 0,5, т.е. отобранные хромосомы не обязательно подвергнуты кроссинговеру и образуют потомков. Хромосомы, которые должны пройти кроссинговер или не пройти, отбирают из отобранных пар.

Для хромосом 1 и 2:

А = 01101

В = 11000

1 ≤ k ≤ 4, k = 4 – точка перед пятой позицией

А' = 01100

В' = 11001

Пары хромосом для оператора кроссинговера формируют на стадии моделирования вращения колеса рулетки. При первом вращении получают первую хромосому – родителя, при втором – вторую.

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

№ хромосомы	Популяция кроссинговера	Новая популяция после мутации	Десятичное значение x	Значение f (x)	Среднее значение (x)	Максимальное значение fmax(x)
					496,5

Мутация произведена с третьей хромосомой с третьим разрядом. Оператор мутации также выполняется с заданной вероятностью Р_м ≈ 0,0001

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