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

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

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)||<e;

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

t := t + 1;

end {while}

end

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

 

9.Описание простого генетического алгоритма

Генетические алгоритмы носят итерационный характер и имеют дело с обработкой популяций индивидуумов P(t)= для итерации t (поколение t). Каждый индивидуум представляет собой потенциальное решение задачи (испытание) и представлен в некоторой, возможно достаточно сложной, структуре данных S. В качестве S будем рассматривать бинарные строки.

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

Селекция. Целью селекции является осуществление выборки индивидуумов в текущей популяции (т.е. из некоторого набора) пропорционально их пригодности. Обычно используют четыре различных механизма селекции - “колесо рулетки”, остаточная стохастическая выборка, стохастическая равномерная выборка и турнирная селекция. Первые три алгоритма являются вариантами пропорциональной селекции, а последний - непропорциональной.

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

Скрещивание. Наиболее простым является одноточечное скрещивание - каждая выбранная таким образом пара строк скрещивается следующим образом: случайным образом выбирается положение точки сечения (целое число k в промежутке от 1 и l-1, где l - длина строки). Затем, путем обмена всеми элементами между позициями k+1 и l включительно, рождаются две новых строки.

Например, пусть первая особь - а вторая соответственно и пусть, случайно выбранная точка сечения будет после третьего гена (бита). Тогда в результате скрещивания получим две особи-потомки - и . После этого потомки замещают родительские особи в промежуточной популяции . Схематично этот вариант показан на рис.9.1.

Рис.9.1

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

После рекомбинации, применяется также оператор мутации. Каждый бит каждой особи в популяции мутирует (точнее, пытается мутировать) с некоторой низкой вероятностью pm. Обычно мутация применяется с вероятностью меньше чем 1 % и интерпретируется как “зеркальное отражение“ бита (инверсия его значения, т.е. изменение его с 1 на 0 или с 0 на 1).

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

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

Выполнение генетического алгоритма происходит в две стадии (рис. 9.2). Начинается он с текущей популяции, к которой применяется оператор выбора, чтобы создать промежуточную популяцию. При этом, например, особь s2 копируется в промежуточную популяцию дважды, а s3 – ни разу. После этого к промежуточной популяции применяются операторы рекомбинации и мутации для того, чтобы создать следующую популяцию. Процесс продвижения от текущей популяции до следующей популяции составляет одно поколение в выполнении генетического алгоритма.

Рис.9.2

 

 

 

 

 

 

 

 

 

Результаты работы программы

размер популяции	число поколений	лучшее значение минимума	среднее значение минимума
10	30	87.12345943	93.70422134
20	30	0.70952841	2.60640487
30	30	0.23712169	0.53752080
10	100	0.98207550	25.16792530
20	100	0.46923463	0.69057554
30	100	0.23369012	0.26288978

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Выводы

При выполнении курсового проекта учитывалось, что решение задачи является подверженным влиянию случайных величин. Поэтому, каждый запуск программы был повторен 30 раз, что прописано в теле основной программы. Затем, из набора полученных решений отбирались лучшие. Одновременно вычислено и среднее значение минимума за 30 запусков программы.

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

Увеличение количества поколений в 2 раза показало, что чаще при одних и тех же условиях, результат, полученный при количестве поколений равный 100, лучше. Это можно объяснить тем, что алгоритм, используя свои механизмы, находит лучшее решение с каждым последующим поколением, т.е. использует “накопленный опыт”.

Самые лучшие результаты были получены при числе поколений равным 100 и размере популяции геномов 30.

 

 

 

 

 

 

 

 

 

Список литературы

1. Тимченко С.В. Информатика. Часть 3: Учебное пособие. - Томск: Томский межвузовский центр дистанционного образования,  2003. - 124 с.

2. Тимченко С.В. Информатика. Часть 4. Указания к курсовому проекту.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 

Листинг программы

program sga;

uses crt;

const

maxpop=100;

maxstring=30;

dim=2;

type

allele=boolean;

chromosome = array[1..maxstring*dim] of allele;

fenotype=array[1..dim]of real;

individual=record

chrom:chromosome;

x:fenotype;

fitness:real;

end;

population = array [1..maxpop] of individual;

const

xmax:fenotype = (2.048,2.048);

xmin:fenotype = (-2.048,-2.048);

var

oldpop,newpop,intpop:population;

lchrom,gen,popsize:integer;

pcross,pmutation,sumfitness:real;

nmutation,ncross:integer;

avg,max,min:real;

function random_:real;

begin

random_:=random(65535)/(65535-1);

end;

function flip(probability:real):boolean;

begin

if probability = 1.0 then

flip:=true

else

flip:=(random_<=probability);

end;

function rnd(low,high:integer):integer;

var i:integer;

begin

if low>=high then

i:=low

else

begin

i:=trunc(random_*(high-low+1)+low);

if i>high then i:=high;

end;

rnd:=i;

end;

function objfunc(x:fenotype):real;

begin

objfunc:=100*sqr(sqr(x[1])-(x[2]))+sqr(1-x[1]);

end;

procedure decode (chrom:chromosome;lbits:integer;var x:fenotype);

var

i,j:integer;

f,accum,powerof2:real;

begin

for i:=1 to dim do

begin

accum:=0.0;

powerof2:=1;

f:=1;

for j:=1+lbits*(i-1) to lbits+lbits*(i-1) do

begin

if chrom[j] then accum:=accum+powerof2;

powerof2:=powerof2*2;

f:=f*2;

end;

x[i]:=xmin[i]+(xmax[i]-xmin[i])*accum/(f-1);

end;

end;

procedure statistics (popsize:integer;var max,avg,min,sumfitness:real; var pop:population);

var

j:integer;

begin

sumfitness:=pop[1].fitness;

min:= pop[1].fitness;

max:=pop[1].fitness;

for j:=2 to popsize do

with pop[j] do

begin

sumfitness:=sumfitness+fitness;

if fitness>max then max:=fitness;

if fitness<min then min:=fitness;

end;

avg:=sumfitness/popsize;

end;

procedure initpop;

var

j,j1:integer;

begin

for j:=1 to popsize do

with oldpop[j] do

begin

for j1:=1 to lchrom*dim do chrom[j1]:=flip(0.1);

decode(chrom,lchrom,x);

fitness:=objfunc(x);

end;

end;

procedure select;

var

ipick:integer;

procedure shuffle(var pop:population);

var

i,j:integer;

ind0:individual;

begin

for i:=popsize downto 2 do

begin

j:=random(i-1)+1;

ind0:=pop[i];

pop[i]:=pop[j];

pop[j]:=ind0;

end;

end;

function select_1:integer;

var

j1,j2,m:integer;

begin

if(ipick>popsize)then

begin

shuffle(oldpop);

ipick:=1;

end;

j1:=ipick;

j2:=ipick+1;

if (oldpop[j2].fitness<oldpop[j1].fitness) then

m:=j2

else m:=j1;

ipick:=ipick+2;

select_1:=m;

end;

var

j:integer;

begin

ipick:=1;

for j:=1 to popsize do

begin

intpop[j]:=oldpop[select_1];

end;

oldpop:=intpop;

end;

procedure mutation(var chromos:chromosome;flchrom:integer;pmutation:real;var nmutation:integer);

var

mutate:boolean;

gen0:allele;

jmut1,jmut2:integer;

begin

mutate:=flip(pmutation);

if mutate then

begin

nmutation:=nmutation+1;

jmut1:=rnd(1,flchrom);

jmut2:=rnd(1,flchrom);

gen0:=chromos[jmut1];

chromos[jmut1]:=chromos[jmut2];

chromos[jmut2]:=gen0;

end;

end;

procedure crossover(var parent1,parent2,child1,child2:chromosome;

flchrom:integer;var ncross:integer;var pcross:real);

var

j,jcross1,jcross2:integer;

chgen:integer ;

begin

if flip(pcross) then

begin

jcross1:=rnd(2,flchrom-1);

jcross2:=rnd( 2,flchrom-1);

if (jcross1>jcross2) then

begin

chgen:=jcross1;

jcross1:=jcross2;

jcross2:=chgen;

end;

ncross:=ncross+1;

end

else begin

jcross1:=1;

jcross2:=flchrom;

end;

for j:=1 to jcross1-1 do

begin

child1[j]:=parent1[j];

child2[j]:=parent2[j];

end;

for j:=jcross1 to jcross2 do

begin

child1[j]:=parent2[j];

child2[j]:=parent1[j];

end;

for j:=jcross2+1 to flchrom do

begin

child1[j]:=parent1[j];

child2[j]:=parent2[j];

end;

end;

procedure generation;

var

j,mate1,mate2:integer;

begin

select;

j:=1;

repeat

mate1:=j;

mate2:=j+1;

crossover(oldpop[mate1].chrom, oldpop[mate2].chrom,newpop[j].chrom,

newpop[j+1].chrom,lchrom*dim,ncross,pcross);

mutation(newpop[j].chrom,lchrom*dim,pmutation,nmutation);

mutation(newpop[j+1].chrom,lchrom*dim,pmutation,nmutation);

with newpop[j] do

begin

decode(chrom,lchrom,x);

fitness:=objfunc(x);

end;

with newpop[j+1] do

begin

decode(chrom,lchrom,x);

fitness:=objfunc(x);

end;

j:=j+2;

until j>popsize;

end;

var

avgpr,minpr:real;

textfile,file2:Text;

const

popular:array[1..3] of integer = (10,20,30);

maxgen:array[1..2] of integer = (30,100);

prog = 30;

var

k,p,m:integer;

begin

assign(textfile,'Rezultat.txt');

rewrite(textfile);

writeln(textfile,'Sozonov A.V., Variant 8.');

writeln('Sozonov A.V., Variant 8.');

writeln(textfile,'Provesti rascheti dla 30 i 100 pokolenii.');

writeln(textfile,'Pri razmerah populacii 10,20,30 osobei');

writeln(textfile,'Rezultat isledovaniy:');

lchrom:=30;

pmutation:=0.1;

pcross:=0.9;

for p:=1 to 3 do begin

for m:=1 to 2 do begin

popsize:=popular[p];

avgpr:=0;

minpr:=objfunc(xmin);

for k:=1 to prog do begin

randomize;

nmutation:=0;

ncross:=0;

initpop;

statistics (popsize,max,avg,min,sumfitness,oldpop);

gen:=0;

repeat

gen:=gen+1;

generation;

statistics (popsize,max,avg,min,sumfitness,newpop);

oldpop:=newpop;

until(gen>=maxgen[m]);

if min<minpr then minpr:=min;

avgpr:=avgpr+minpr;

end;

avgpr:=avgpr/prog;

writeln(textfile,'Razmer populacii ',popsize:2,

' Colithestvo pocoleniy ',maxgen[m],' min = ',minpr:10:8,' srednee = ',avgpr:10:8);

writeln('Razmer populacii ',popsize:2,

' Colithestvo pocoleniy ',maxgen[m],' min= ',minpr:10:8,' sr= ',avgpr:10:8);

end;

end;

close(textfile);

readln;

end.