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

 

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

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

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

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

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

 

Рисунок - 1.1

 

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

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

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

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

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

 

Рисунок - 1.2

 

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

ВАРИАНТЫ ЗАДАНИЙ

 

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

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

 

1.

Рассмотреть одноточечное скрещивание и инверсионную мутацию.

Каждая переменная кодируется 20 битами.

Провести расчеты для 40 и 80 поколений.

Сравнить получающиеся решения при размерах популяции 8, 12, 20 особей.

 

2.

Рассмотреть одноточечное скрещивание и инверсионную мутацию.

Каждая переменная кодируется 30 битами.

Провести расчеты для 30 и 100 поколений.

Сравнить получающиеся решения при размерах популяции 10, 20, 30 особей.

 

3.

Рассмотреть одноточечное скрещивание и инверсионную мутацию.

Каждая переменная кодируется 30 битами.

Провести расчеты для 50 и 100 поколений.

Сравнить получающиеся решения при размерах популяции 10, 20, 30 особей.

 

4.

Рассмотреть двухточечное скрещивание и инверсионную мутацию.

Каждая переменная кодируется 30 битами.

Провести расчеты для 30 и 100 поколений.

Сравнить получающиеся решения при размерах популяции 10, 20, 30 особей.

 

5.

Рассмотреть двухточечное скрещивание и инверсионную мутацию.

Каждая переменная кодируется 20 битами.

Провести расчеты для 40 и 80 поколений.

Сравнить получающиеся решения при размерах популяции 8, 12, 20 особей.

 

6.

Рассмотреть двухточечное скрещивание и инверсионную мутацию.

Каждая переменная кодируется 30 битами.

Провести расчеты для 30 и 100 поколений.

Сравнить получающиеся решения при размерах популяции 10, 20, 30 особей.

 

7.

Рассмотреть равномерное скрещивание и инверсионную мутацию.

Каждая переменная кодируется 30 битами.

Провести расчеты для 50 и 100 поколений.

Сравнить получающиеся решения при размерах популяции 10, 20, 30 особей.

 

8.

Рассмотреть равномерное скрещивание и инверсионную мутацию.

Каждая переменная кодируется 30 битами.

Провести расчеты для 30 и 100 поколений.

Сравнить получающиеся решения при размерах популяции 10, 20, 30 особей.

 

9.

Рассмотреть равномерное скрещивание и инверсионную мутацию.

Каждая переменная кодируется 20 битами.

Провести расчеты для 40 и 80 поколений.

Сравнить получающиеся решения при размерах популяции 8, 12, 20 особей.

 

10.

Рассмотреть одноточечное скрещивание и двухточечную мутацию.

Каждая переменная кодируется 30 битами.

Провести расчеты для 30 и 100 поколений.

Сравнить получающиеся решения при размерах популяции 10, 20, 30 особей.

 

11.

Рассмотреть одноточечное скрещивание и двухточечную мутацию.

Каждая переменная кодируется 30 битами.

Провести расчеты для 50 и 100 поколений.

Сравнить получающиеся решения при размерах популяции 10, 20, 30 особей.

 

12.

Рассмотреть одноточечное скрещивание и двухточечную мутацию.

Каждая переменная кодируется 30 битами.

Провести расчеты для 30 и 100 поколений.

Сравнить получающиеся решения при размерах популяции 10, 20, 30 особей.

 

13.

Рассмотреть двухточечное скрещивание и двухточечную мутацию.

Каждая переменная кодируется 20 битами.

Провести расчеты для 40 и 80 поколений.

Сравнить получающиеся решения при размерах популяции 8, 12, 20 особей.

 

14.

Рассмотреть двухточечное скрещивание и двухточечную мутацию.

Каждая переменная кодируется 30 битами.

Провести расчеты для 50 и 100 поколений.

Сравнить получающиеся решения при размерах популяции 10, 20, 30 особей.

 

15.

Рассмотреть двухточечное скрещивание и двухточечную мутацию.

Каждая переменная кодируется 30 битами.

Провести расчеты для 30 и 100 поколений.

Сравнить получающиеся решения при размерах популяции 10, 20, 30 особей.

 

16.

Рассмотреть равномерное скрещивание и двухточечную мутацию.

Каждая переменная кодируется 30 битами.

Провести расчеты для 30 и 100 поколений.

Сравнить получающиеся решения при размерах популяции 10, 20, 30 особей.

 

17.

Рассмотреть равномерное скрещивание и двухточечную мутацию.

Каждая переменная кодируется 20 битами.

Провести расчеты для 40 и 80 поколений.

Сравнить получающиеся решения при размерах популяции 8, 12, 20 особей.

 

18.

Рассмотреть равномерное скрещивание и двухточечную мутацию.

Каждая переменная кодируется 30 битами.

Провести расчеты для 30 и 100 поколений.

Сравнить получающиеся решения при размерах популяции 10, 20, 30 особей.

 

ЛИТЕРАТУРА

1. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. - М.:ФИЗМАТЛИТ, 2003. - 432 с.

2. Батищев Д.А. Генетические алгоритмы решения экстремальных задач. - Воронеж: Изд.-во ВГТУ, 1995.

 

ПРИЛОЖЕНИЕ

 

program sga;

uses crt;

 

const

maxpop = 100;

maxstring = 30;

dim = 1; {размерность пространства поиска}

 

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=(5.12);

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

xmin:fenotype=(-5.12);

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

 

var

oldpop, newpop, intpop:population;

{Три непересекающихся популяции - старая, новая и промежуточная}

popsize, lchrom, gen, maxgen: 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;

{подбрасывание монетки - true если орел}

begin

if probability = 1.0 then

flip:= true

else

flip:= (random_ <= probability);

end;

 

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

{Случайный выбор между low и high}

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;

 

{интерфейсные процедуры: decode and objfunc}

 

function objfunc(x:fenotype):real;

begin

objfunc:= sqr(x[1]);

end;

 

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

{Декодирование строки в массив вещественных координат точки в пространстве поиска - true=1, false=0}

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;

 

{Расчет статистических величин: statistics }

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;

{Цикл для max, min, sumfitness }

for j:= 2 to popsize do with pop[j] do begin

sumfitness:= sumfitness + fitness;

{Накопление суммы значений функции пригодности}

if fitness>max then max:= fitness;

{Новое значение max}

if fitness<min then min:= fitness;

{Новое значение min}

end;

{Расчет среднего}

avg:= sumfitness/popsize;

end;

 

{Процедура инициализации initpop}

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.5);

{Бросок монетки}

decode(chrom,lchrom,x);

{Декодирование строки}

fitness:= objfunc(x);

{Вычисление начальных значений функции пригодности}

end;

end;

 

{3 генетических оператора: отбора (select), скрещивания (crossover) и

мутации (mutation)}

 

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;

 

function mutation (alleleval:allele; pmutation:real;

var nmutation:integer):allele;

{мутация одного бита в строке (аллеля) с вероятностью pmutation, count number of mutations}

var

mutate:boolean;

begin

mutate:= flip(pmutation);

{Flip the biased coin}

if mutate then begin

nmutation:= nmutation + 1;

mutation:= not alleleval;

{Change bit value}

end else

mutation:= alleleval;

{No change}

end;

 

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

flchrom:integer; var ncross, nmutation, jcross:integer;

var pcross, pmutation:real);

{Скрещивание 2 родительских строк, результат помещается в 2 строках-потомках}

var

j:integer;

begin

if flip(pcross) then begin

{Выполняется скрещивание с вероятностью pcross}

jcross:= rnd(1,flchrom-1);

{Определение точки сечения в диапазоне между 1 и l-1}

ncross:= ncross + 1;

{Инкрементирование счетчика скрещиваний}

end else

jcross:= flchrom;

{певая часть обмена, 1 to 1 and 2 to 2}

for j:= 1 to jcross do begin

child1[j]:= mutation(parent1[j], pmutation, nmutation);

child2[j]:= mutation(parent2[j], pmutation, nmutation);

end;

{вторая часть обмена, 1 to 2 and 2 to 1]

if jcross<>flchrom then

{пропуск, если точка скрещивания равна flchrom--скрещивание не происходит}

for j:= jcross+1 to flchrom do begin

child1[j]:= mutation(parent2[j], pmutation, nmutation);

child2[j]:= mutation(parent1[j], pmutation, nmutation);

end;

end;

 

{Процедура создания нового поколения: generation}

 

procedure generation;

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

{Прим: предполагается, что популяция имеет четный размер}

var

j, mate1, mate2, jcross:integer;

begin

select;

j:= 1;

repeat

{выполняются отбор, скрещивание и мутация, пока полностью не сформируется новая популяция - newpop}

mate 1:= j;

{выбор родительской пары}

mate 2:= j+1;

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

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

newpop[j ].chrom, newpop[j + 1].chrom,

lchrom*dim, ncross, nmutation, jcross, pcross, pmutation);

{Декодирование строки и вычисление пригодности}

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;

 

begin { Главная программа }

popsize:=20;

{размер популяции}

lchrom:=20;

{число битов на один кодируемый параметр}

maxgen:=100;

{максимальное число поколений}

pmutation:=0.01;

{вероятность скрещивания}

pcross:=0.9;

{вероятность мутации}

{Инициализация генератора случайных чисел}

randomize;

{Инициализация счетчиков}

nmutation:= 0;

ncross:= 0;

initpop;

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

gen:= 0; {Установка счетчика поколений в 0}

repeat {Главный итерационный цикл}

gen:= gen + 1;

generation;

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

oldpop:= newpop;

{переход на новое поколение }

writeln('min= ',min);

until (gen >= maxgen)

end. {End главной программы}