ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ

А. Н. Скурихин

1. Стандартный генетический алгоритм

Стандартный вариант генетического алгоритма был предложен в работах Fraser [22,23], Bremermann [5,6], Reed [55] и Holland [37,38]. Как показали последующие исследования, данный метод оказался эффективным не только при решении реальных инженерных проблем, но и при исследовании биологических проблем, например, при моделировании иммунной системы. Канонический генетический алгоритм характеризуется следующими особенностями:

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

2) В соответствии с определенными ограничениями инициализируется исходная популяция потенциальных решений. Каждое решение кодируется как вектор х, который называется хромосомой. Его элементами являются части вектора - гены, изменяющиеся значения в определенных позициях которых называются аллелями. Наиболее часто используется двоичное представление переменных.

3) Каждая хромосома xi, i=l,...P, в популяции декодируется в необходимую форму для последующей оценки и затем ей присваивается значение эффективности m (xi) в соответствии с функцией оптимальности.

4) Каждой хромосоме присваивается вероятность воспроизведения r_i, i=l,...,P, которая зависит от эффективности данной хромосомы.

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

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

Формально генетический алгоритм можно описать следующим образом:

ГА = (P⁰, l, l, s, р, f, t) (1)

где P⁰ = (a⁰₁, ..., a⁰_l) - исходная популяция, где,

a⁰_i - решение задачи, представленное в виде хромосомы;

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

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

s - оператор отбора;

p - отображение, определяющее рекомбинацию (кроссинговер, мутация);

f - функция оптимальности;

t - критерий останоки.

Механизм работы генетического алгоритма может быть проиллюстрирован с помощью следующего примера. Пусть необходимо найти максимум некоторой функции одной переменной, показанной на рисунке 3. Гиперплоскость 0***...* покрывает первую половину пространства поиска, гиперплоскость 1***...* - вторую половину пространства поиска. Как видно из рисунка, оптимальность строк, принадлежащих 0***...*, в среднем выше, чем оптимальность строк, принадлежащих 1***...*. Поэтому было бы желательно иметь больше представителей первой гиперплоскости. Следовательно, отбор должен отдавать предпочтение таким строкам. На втором рисунке показана подобласть, соответствующая **1 **...* и пересечение **1**...* и 0***...* - подобласть 0*1**...* . Третий рисунок показывает подобласть 0*10*...*. Таким образом видно, что выбор определенных пoдoблacтeй пространства поиска может осуществляться независимо от наличия локальных минимумов. Одновременно, увеличение количества точек, соответствующих подобластям с относительно большей эффективностью, не может гарантировать сходимости к глобальному оптимуму. Тем не менее, всегда возможно найти решение, которое будет относительно эффективно по сравнению с альтернативными.

Точка кроссинговера

|

Родитель 1: 1 1 0 | 1 1 Потомок 1: 0 0 1 1 1

Родитель 2: 0 0 1 | 0 1 Потомок 2: 1 1 0 0 1

Рис. 1. Одноточечная схема кроссинговера.

Потомок 1 Потомок 2

До мутации: 00111 11001

После мутации: 10101 11000

Рис. 2. Мутация.

Рис. 3. Поиск оптимума функции с помощью генетического алгоритма

Как отмечалось ранее, наиболее часто используется бинарная кодировка для представления элемента популяции, выбор которой определяется тем, что двоичный алфавит позволяет обрабатывать максимальное количество информации по сравнению с другими схемами кодирования [27]. Существуют альтернативные двоичному кодированию схемы, например, использование представления с плавающей точкой [52]. В зависимости от свойств конкретной решаемой задачи обе схемы кодирования имеют свои достоинства и недостатки.

Для анализа генетического алгоритма используется также понятие шаблона, который является некоторым представлением подмножества строк, имеющих одинаковые значения в специфицированных позициях (шаблоны гиперплоскости различной размерности в l-мерном пространстве). Шаблоны определяются с помощью элементов множества {0,1,*}^l и для данного шаблона H Î {0,1,*}^l строка a является одним из представителей данного шаблона тогда и только тогда, когда биты в специфицированных позициях шаблона (то есть, биты, содержащие 0 или 1) идентичны соответствующим битам строки а. Символ "*" означает, что в данной позиции строки бит может принимать значение 1 или 0.

Выбор двоичного алфавита приводит к оценке O(l³) структур в течение одного поколения популяции, хотя в реальности популяция содержит только l индивидуумов. Этот эффект носит название неявный параллелизм [27,38].

P⁰ является случайно сгенерированной исходной популяцией и параметры l и l описывают число индивидуумов одного поколения и длину (размер) каждого индивидуума популяции соответственно.

2. Методы отбора

Оператор отбора s порождает промежуточную популяцию Р^t из популяции Р^t посредством отбора и генерации новых копий элементов Р^t : Р^t = s(Р^t). Функция оптимальности f, обеспечивающая обратную связь от результатов оптимизации в течение поколения t, используется для отбора конкурентноспособных индивидуумов популяции.

При отборе часто используется ранг элементов популяции. Ранг элементов популяции, rank, задается следующим образом:

"i Î{l, ..., l}: rank(a^t_i) = i, (2)

если для "j Î {1, ..., l-1}: f(a^t_j) о f(a^t_j+1),

где

о - означает £ в случае минимизации и ³ в случае максимизации.

Следовательно, можно использовать индекс i для обозначения ранга элемента. В сооветствии с этим предполагается, что элементы сортируются согласно их конкурентноспособности (оптимальности) так, что a^t₁ будет лучшим элементом P^t.

Отбор производится на основании вероятностей p_s(a^t_i), вычисленных для каждого индивидуума популяции. В настоящее время применяются следующие основные схемы отбора (рис. 4):

o Пропорциональный отбор [38] :

(3)

o Линейное ранжирование [2] :

(4)

где h_min = 2 - h_max и £ h_max £ 2 .

o (m, l) - равномерное ранжирование [64]:

(5)

Наиболее часто используется пропорциональный отбор. Однако с его использованием связаны две проблемы: 1) зависимость от положительных значений, 2) простое добавление очень большой константы к целевой функции может уничтожить отбор, приводя к простому случайному выбору. Для устранения этих неприятностей используется либо масштабирование оценок оптимальности родителей относительно наименьшего значения оптимальности в популяции, либо используется ранжирование в пропорциональной схеме отбора.

Рис. 4 . Типы отбора.

Одна из математических проблем, связанных с пропорциональным отбором состоит в том, что данная процедура не может гарантировать асимптотическую сходимость к глобальному оптимуму [58]. Наилучшая хромосома в популяции может быть потеряна в любом поколения и нет какой-либо гарантии, что результаты эволюции, достигнутые в ряде поколений, не будут утрачены. Одним из способов преодоления этого является использование элитного отбора [32], который всегда сохраняет наилучшую хромосому популяции. Этот вид отбора гарантирует асимптотическую сходимость [15,19,58], но скорость сходимости при этом может существенно различаться в зависимости от вида конкретной решаемой задачи.

Анализ пропорционального отбора позволил получить теорему Холланда [38]. Пусть Н^t обозначает определенный шаблон, который присутствует в популяции Р^t и m(Н^t) - количество индивидуумов популяции Р^t, которые являются элементами Н^t. Тогда

где f ^t - средняя оптимальность Р^t ,

f(H^t) - средняя оптимальность индивидуумов, являющихся элементами H^t . Если предположить, что средняя оптимальность H^t выше средней по популяции, то есть

f(H^t) = f^t + cf^t , (9)

где c > 0 считается константой,

то в результате имеем

m(H^t+1) = m(H^t) (1+c) (10)

и после t поколений, начиная с t = 0 :

m(H^t+1) = m(H⁰) (1+c)^t (11)

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

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

1} порядок s(Н) шаблона Н Î {0,1,*}^l , определяемый количеством его зафиксированных позиций, то есть позиций, содержащих либо 1 либо 0.

2) длина d(H) шаблона Н Î {0,1,*}^l - дистанция между первой и последней зафиксированной позициями шаблона.

Пусть вероятность осуществления одноточечного кроссинговера равна P_c , а вероятность мутации - P_m . В итоге, используя сделанные предположения, получаем следующее утверждение.

Теорема о шаблоне (Холланда).

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

Для предельного случая, - популяция бесконечного размера, пространство поиска непрерывно и циклически применяется пропорциональный отбор, - доказана следующая теорема [75]:

Пусть выполняются условия:

(1) неотрицательная функция g(х) определена на ограниченном подмножестве F Î R^l и имеет единственный глобальный максимум при x=х*ÎF g*=g(x*);

(2) существует пространственно-односвязная окресность точки x*, внутри

которой g(х) непрерывна;

(3) o начальная плотность f₀ распределения ненулевая в точке х*.

Поиск по сайту: