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

Тема 7.

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

К этому классу алгоритмов относятся следующие виды:

Ø генетические алгоритмы (GA);

Ø эволюционные программы (EP);

Ø эволюционные стратегии (ES);

Ø системы классификации;

Ø нейронные сети.

Первые исследования в области GА относятся к 50-м годам (моделирование биологических систем).

В 60-70 годы Холланд в университете Мичигана развил теорию GА до того уровня, на котором они понимаются сегодня.

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

Решение задачи структурно можно изобразить следующим образом:

P - проблема

МР – модифицированная проблема

Эволюционные программы (ЕР) являются обобщением GА:

EP= GА+Data Structures

EP еще не достаточно обоснованы, но они дают во многих случаях более лучшие результаты, чем классические GA (например, TSP).

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

Для GA существует 2 классических генетических оператора:

1 – мутация – изменение какого-либо бита отдельного индивида;

2 – скрещивание – формирование нового индивида (потомка), наследующего часть ген (битов) от одного и часть битов от другого родителя.

Эволюционная стратегия (ES) – особый класс алгоритмов, которые имитируют принцип естественной эволюции при решении проблем оптимизации параметров, тогда как GA применяются для адаптивного поиска оптимального решения в задачах с экспоненциальной сложностью.

Эволюционная программа – это некоторый вероятностный алгоритм, поддерживающий популяцию индивидов на некотором интервале времени t.

P(t)={x^t₁, x^t₂,…, x^t_n}

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

На следующей итерации P(t+1) формируется новая популяция индивидов из наиболее подходящих предков.

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

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

В случае ЕР решение задачи сводится к следующему:

Таким образом, GA и EP содержат пять основных компонентов (шагов):

1. генетическое представление решения проблемы;

2. способ формирования начальной популяции решений;

3. функция оценки индивидов на предмет их пригодности;

4. генетические операторы, изменяющие наборы генов у потомков;

5. значения параметров алгоритма:

ü размер популяции;

ü вероятности применения генетических операторов

и др.

Общая структура программы на основе генетических алгоритмов выглядит следующим образом:

Procedure EP;

begin

t=0;

initialize P(t);

evaluate P(t);

while (not stop condition) do

begin

t=t+1;

select P(t) from P(t-1);

alter P(t);

evaluate P(t);

end;

end;

Пример 1:

Поиск графа, удовлетворяющего некоторым требованиям (оптимальная топология вычислительной сети в соответствии с некоторым критерием: длина соединения, стоимость посылки сообщения и т.д.)

Каждый индивид в такой программе – это граф. Начальная популяция P(0) формируется либо случайным образом, либо после эвристического алгоритма.

Функция оценки обычно дана и объединяет требования предметной области. Она возвращает результат оценки на предмет подходимости данного решения.

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

Очень часто такие генетические операторы объединяют значения специфики проблемы.

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

В общем случае множество задач, решаемых с помощью ЕР, могут быть сформулированы как в рассмотренном примере, хотя получающиеся программы могут быть различны:

§ по структуре данных;

§ по генетическим операторам преобразований индивидов;

§ по методам создания начальной популяции;

§ по условиям ограничений задачи и исходным параметрам.

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

Например:

010100 0 1

101010 1 0

мутация:

скрещивание:

Для ЕР, в отличие от GA, нет ограничения на исходную структуру данных и форму их представления.

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

Основным достоинством ЕР является:

q применимость во многих областях;

q их параллельность по природе.

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

Области применения GA:

v задачи планирования;

v задачи адаптивного управления;

v задачи теории игр;

v транспортные проблемы;

v оптимизация запросов к БД;

v задача коммивояжера

и др.

Пример 2:

Задача численной оптимизации функции.

Пусть задана функция вида

f(x)=x*sin(10px)+1.0

xÎ[-1, 2]

Требуется найти х₀, f(x₀)>f(x), "x.

Традиционно максимум находится по 1-ой производной: f ’(x)=0.

В этом случае исходная формула эквивалентна следующей записи:

tan(10px)=-10px

x_i=(2*i – 1)/20+d_i, i=1, 2, …

x₀=0

x_i=(2*i + 1)/20 - d_i, i=-1, -2, …

Максимум достигается при четных значениях, минимум – при нечетных.

Максимум будет достигнут итерационным процессом.

x₁₉=1,85+d₁₉

f(x₁₉)=2,85 – максимум.

Рассмотрим GA для данной задачи.

Возьмем разбиение исходного отрезка на 3 млн. отрезков.

2²¹<3*10⁶<2²²

(b₂₁ b₂₂ …b₀)=x’

x=-1+x’*3/(2²²-1)

(*)

Пусть начальная популяция состоит из одного решения.

Сгенерируем набор бит:

x’₀: 1000101110110101000111

(x’₀=2288967 – в десятичной системе счисления).

По формуле (*) получим:

x=0,637197

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

Генетические операторы здесь классические: мутация битов и скрещивание вариантов.

1) Мутация.

Пусть

x’₃: 1110000001111111000101

f(x₃)=2,250650

x’₄: 1110 1 00001111111000101

x₄=1,721638

f(x₄)=-0,082257

x’₅: 111000000 0 111111000101

x₅=1,630818

f(x₅)=2,34355

2) Скрещивание.

x’_K=(a, b) ® x’’_K

x’_N=(c, d) ® x’’_N

f(x’’_K)=2,4592

Т. о. получаем:

Р_m=0,01 – вероятность мутации.

x=1,85 – максимум, который найден за 150 шагов.

f(x)=2,2802275

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

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

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

Учитывая конечность происходящих в природе процессов, в модифицированном GA вводится понятие возраста индивидов в популяции, т. е. отбор лучших кандидатов проводится по возрастному критерию.

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

Формула изменения популяции на шаге (t+1):

P(t+1)=P(t)+AuxP(t)–D(t),

где P(t) – предки;

AuxP(t) – новые потомки;

D(t) - «умершие».

Procedure GAVAPS

begin

t=0;

initialize P(t);

evaluate P(t);

while (not stop condition) do

begin

t=t+1;

Age=Age+1;

Recompine P(t)

evaluate P(t);

Remove D(t);

end;

end;

Если жестко задать параметр время жизни константой (LifeTime=const), то получим экспоненциальный рост размера популяции. Кроме того, нужно учитывать, что разные индивиды имеют разное время жизни (более хорошие живут дольше).

Тогда параметр LifeTime (LT) для i-го индивида рассчитывается, например, по следующим оценкам:

1) Пропорциональная оценка:

min(MinLT+K*(f[i]/AvgFit), MaxLT)

K=1/2[MaxLT – MinLT]

Массив f[i] формируется с помощью функции оценки пригодности индивида

AvgFit, MinFit, MaxFit – значения пригодности.

2) Линейная оценка:

MinLT+2*K*

3) Билинейная оценка:

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

Кроме того, ES используют представление индивидов в виде вектора чисел с плавающей точкой, GA – только в виде битовой строки.

ES и GA различаются в процедуре селекции кандидатов и операторов скрещивания. Для ES, например, может использоваться следующий оператор скрещивания:

x₁, x₂

потомки

Пример 3:

Задача коммивояжера.

Каждый город представляется в виде строки битов размером log₂N (N – число городов), тогда полный набор городов N*log₂N.

Однако число городов может быть не кратно 2.

Общий принцип работы GA для данной задачи:

1) Генерация начальной популяции (осуществляется либо оператором Random, либо используют эвристики или «жадный алгоритм» в качестве исходных).

2) Функция стоимости evaluate равна длине тура.

3) Для полученных потомков используются генетические операторы:

ü унарные операторы (перебор всех вариантов);

ü операторы скрещивания (PMX, OX, CX).

Оператор OX (order expression) берет некоторую последовательность городов из одного тура и дополняет ее в относительном порядке городами из другого тура.

1 тур: 1 2 3 4 5 6 7 8 9 10 11 12

2 тур: 7 3 1 11 4 12 5 2 10 9 6 8

1 шаг. Выделяют «базу» - тур, который не меняется, например

x x x (4 5 6 7) x x x x x

2 шаг. Просматривают остальные города

1 11 12 (4 5 6 7) 2 10 9 8 3

3 шаг. Оценивается функция стоимости тура.

Оператор PMX (partially mapped expression).

1 тур: 1 2 3 |4 5 6 7| 8 9

2 тур: 4 5 2 |1 8 7 6| 9 3

1 шаг: Разбиение на части.

2 шаг: Выделение «базы».

О_1­=x x x | 4 5 6 7| x x

О_2­=x x x | 1 8 7 6| x x

«База» является картой перестановки городов (образует пары взаимозаменяемых городов).

3 шаг: О_1­=1 8 2 | 4 5 6 7| 9 3

О_2­=4 2 3 | 1 8 7 6| 5 9

Существуют и другие варианты операторов скрещивания. Например, представление тура в виде бинарной матрицы n x m, в которой единица соответствует условию, что i–й город идет раньше j-го.

		j
i

(…, i, …, j, …)

Например:

1 – 2 – 3 – 4 – 5 1 – 3 – 5 – 4 – 2

Дата добавления: 2014-01-07