1 Общая структура генетического алгоритма.

Схема генетического алгоритма:

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

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

Воспроизводство. Хромосомы, имеющие большую выживамость (fitness), попадают к потомкам (которые затем могут мутировать) с большей вероятностью. Потомок, результат слияния 'отца' и 'матери', является комбинацей их ген. Этот процесс называется 'кроссиннговер' (crossing over).

Cледующее поколение. Если новое поколение содержит решение, достаточно близкое к ответу, то задача решена. В противоположном случае оно проходит через тот же процесс. Это продолжается до достижения решения.

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

Традиционным считается ГА, представленный на схеме.

begin {генетический алгоритм}

t := 0;

done := false;

init_population( P (0) );

{генерация начальной популяции P (0) (случайным образом или случайным в комбинации с некоторым набором начальных решений) и оценка пригодности каждой особи}

while not done do begin

P' := select_parents( P (t) );

{выбор родителей для скрещивания при помощи оператора селекции согласно пригодности и помещение их в промежуточную популяцию P'}

recombine P'(t);

{промежуточная популяция попарно подвергается оператору рекомбинации или скрещивания}

mutate P' (t);

{каждая особь в промежуточной популяции подвергается оператору мутации }

evaluate P' (t);

{расчет целевой функции для всех новых особей}

P(t+1) := P'(t);

{промежуточная популяция копируется в новое поколение P(t+1)}

Done := || P(t+1) - P(t+1)||<;

{проверка выполнения критерия сходимости}

t := t + 1;

end {while}

end

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

Рисунок 1 Репродуктивный план Холанда

2 Использование га в решении задач

Пусть S - некоторая система или процесс. Ее атрибутами есть  X - вектор входных и внутренних параметров, Y - вектор  выходных переменных. Пусть закон Y=f(X) идентифицирован и зависимость f   достаточно сложная. Известны также пределы возможных изменений составляющих вектора X. Необходимо найти такие значения вектора X, чтобы значение Y было оптимальным.

Как решается задача с использованием ГА? Функция f называется фитнесс-функцией. Возможные значения элемента вектора X есть его фенотипом. Двоичное представление фенотипа есть генотип (напр. 12,345->100011). Генотип имеет определенное количество элементов. Один или несколько генотипов (по количеству элементов X) представляют хромосому. Кроссовером называют деление двух хромосом и обмен частями (напр. 1100 и 1010 ->1110 и 1000). Кроссовер может быть как одноточечным так и двухточечным и многоточечным. Мутация - инвертирование одного из элементов хромосомы (напр. 0000->0100). Инверсия - изменение порядка следования частей хромосомы (напр. 1100->0011).

Вероятности выбора родительских пар тоже могут определяться по-разному. Известны следующие способы:

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

• селекция, когда значения функции приспособленности родителей выше среднего значения  по популяции;   

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

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

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

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

Рисунок 2 Триада генетических операторов