Размещено на http://www.allbest.ru/

Министерство образования и науки

Томский государственный университет систем управления и Радиоэлектроники

Кафедра

Курсовая работа

на тему: «РЕШЕНИЕ ЗАДАЧИ МИНИМИЗАЦИИ ПРИ ПОМОЩИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА»

по дисциплине «Информатика»

2018 г



Содержание

Введение

1. Техническое задание

2. Описание и обоснование выбранного варианта решения

3. Описание способа мутации и скрещивания

4. Описание изменений

5. Результаты эксперимента

Заключение

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

Приложение

Введение

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

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



1. Техническое задание

Найти минимум функции в заданной области.

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

Целевая функция с областью поиска решения:

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

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

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

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

2. Описание и обоснование выбранного варианта решения

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

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

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

Стоит отдельно упомянуть о том, что MetaQuotes Software Corp. использует ГА в своих программных продуктах MetaTrader 4/5. Все мы знаем о тестере стратегий и о том, сколько времени и усилий позволяет сэкономить встроенный оптимизатор стратегий, в котором на ряду с прямым перебором имеется возможность оптимизации с применением ГА. Кроме того, тестер MetaTrader 5 позволяет использовать пользовательские критерии оптимизации. Возможно, читателю будет интересно прочитать статьи на тему ГА и о преимуществах, которые дают ЭА по сравнению с прямым перебором.

Описание ГА

В ГА заложены принципы, заимствованные у самой природы. Эти принципы - наследственность и изменчивость. Наследственность - способность организмов передавать свои признаки и особенности развития потомству. Благодаря этой способности все живые существа сохраняют в своих потомках характерные черты вида.

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

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

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

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

НАЧАЛО /* генетический алгоритм */

Создать начальную популяцию

Оценить приспособленность каждой особи

останов := FALSE

ПОКА НЕ останов ВЫПОЛНЯТЬ

НАЧАЛО /* создать популяцию нового поколения */

ПОВТОРИТЬ (размер_популяции/2) РАЗ

НАЧАЛО /* цикл воспроизводства */

Выбрать две особи с высокой приспособленностью из предыдущего поколения для скрещивания

Скрестить выбранные особи и получить двух потомков

Оценить приспособленности потомков

Поместить потомков в новое поколение

КОНЕЦ

ЕСЛИ популяция сошлась ТО останов := TRUE

КОНЕЦ

КОНЕЦ

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

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

3. Описание способа мутации и скрещивания

Одноточечное скрещивание

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

1. потомок, хромосома которого на позициях от 1 до lk состоит из генов первого родителя, а на позициях от lk до L - из генов второго родителя;

2. потомок, хромосома которого на позициях от 1 до lk состоит из генов второго родителя, а на позициях от lk до L - из генов первого родителя.

Рис. 1 Схема скрещивания

Инверсионная мутация.

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

Однако мутация происходит только с вероятностью 0.01 т.к. в природе мутации наступают не часто. Вероятность мутации в программе установлена согласно методическому пособию в 1%.

Рис. 2 Схема мутации

4. Описание изменений

За основу была взята программа, приведенная в методическом пособии.

Первым изменением было изменение пространства поиска с одной переменно на две, и соответственно изменение границ поиска.

Dim = 2; {пространство поиска}

xymax : phenotype = ( 2.048, 2.048); {максимальные границы}

xymin : phenotype = (-2.048,-2.048); {минимальные границы}

Также изменена целевая функция:

{ целевая функция }

Function ObjFunc(x : phenotype) : real;

Begin

ObjFunc := x[1] * x[1] + x[2] * x[2];

End;

Процедура одноточечного скрещивания - crossover:

Переменные, используемые в процедуре:

· parent1 , parent2 - две скрещиваемые особи - родители;

· child1 , child2 - результат скрещивания - потомки

· nmutation - счетчик количества мутаций;

· ncross - счетчик количества скрещиваний;

· flchrom - количество хромосом в потомках и родителях;

· j - переменная для итерации цикла

· jcross1 - точка скрещивания - lk по описанию

Процедура:

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

flchrom : integer;

var ncross , nmutation : integer);

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

var

j : integer;

jcross1 : integer;

begin

if flip(pcross) then begin {проверка, будет происходить скрещивание или нет}

jcross1 := rnd(1 , flchrom - 1); {выбираем точку скрещивания}

ncross := ncross + 1; {увеличиваем количество скрещиваний}

end else begin {скрещивание происходить не будет}

jcross1 := flchrom; {за точку скрещивания возьмем последнюю точку, тогда второй цикл будет иметь 0 итераций}

end;

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

for j := 1 to jcross1 do begin {все аллели то точки скрещивания}

child1[j] := parent1[j]; {из первого родителя переносятся в первого потомка}

child2[j] := parent2[j]; {из второго родителя переносятся во второго потомка}

end;

{вторая часть обмена, 1 во 2 и 2 в 1 }

for j := jcross1 + 1 to flchrom do begin {для всех остальных аллелей}

child1[j] := parent2[j]; {в первого потомка переносятся аллели из второго родителя}

child2[j] := parent1[j]; {во второго потомка переносятся аллели из первого родителя}

end;

if jcross1 <> flchrom then begin {таким образом, проверяем, было ли скрещивание}

mutation(child1 , nmutation , flchrom); {сначала первый потомок мутирует}

mutation(child2 , nmutation , flchrom); {потом и второй}

end;

end;

Процедура инверсионной мутации:

Используемые переменные:

· chrome - мутирующая хромосома

· nmutation - счетчик количества мутаций

· flchrom - количество хромосом

· j - номер мутирующей аллели

Процедура:

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

Procedure mutation (var chrome : chromosome;

var nmutation , flchrom : integer);

Var j : integer;

Begin

if flip(pMutation) then begin {проверка, будет происходить мутация или нет}

j := rnd(1 , flchrom); {если да, выбираем номер мутирующей еллели}

if chrome[j] then {если там было true}

chrome[j] := false {нужно изменить его на false}

else {если же там false}

chrome[j] := true; {нужно поставить там true}

end;

End;

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

begin

clrscr; {очищаем экран}

lchrom := 20; {количество бит на одну хромосому}

{Вероятности скрещивания и мутации}

for i1 := 1 to 3 do {цикл по количеству индивидов в популяции}

for i2 := 1 to 2 do begin {цикл по количеству поколений в исследовании}

{флаг для определения необходимости присвоить первый раз минимум}

b := false;

gavgmin := 0;

{количество индивидов в популяции}

if i1 = 1 then

popsize := 8

else if i2 = 1 then

popsize := 12

else

popsize := 20;

{Количество поколений в исследовании}

if i2 = 1 then

maxgen := 40

else

maxgen := 80;

randomize; {инициализируем счетчик случайных чисел}

for i := 1 to 30 do begin {т.к. результаты случайны, проведем 30 прогонов программы}

initpop; {инициализируем начальную популяцию}

Stat(popsize , max , avg , min , sumfitness , oldpop); {подсчитываем статистические переменные}

gen := 0; {инициализируем количество поколений}

nmutation := 0; {инициализируем количество скрещиваний и мутаций}

ncross := 0;

{Проходим поколения 0 ... MaxGen}

repeat

inc(gen); {увеличиваем количество поколений}

generation; {генерируем следующее поколение}

stat(popsize, max, avg, min, sumfitness, newpop); {считаем статистики}

oldpop := newpop;

until (gen >= maxgen); {и повторяем, пока не сделаем необходимое количество}

{необходимо установить минимум}

if not b then begin

b := true;

gmin := min;

gmax := max;

end;

gavgmin := gavgmin + min; {считаем средний арифметический минимум}

if (gmin > min) then gmin := min; {пересчитываем минимум}

if (gmax < max) then gmax := max; {пересчитываем максимум}

end;

gavgmin := gavgmin / 30; {среднее}

writeln('Объем популяции : ' , popsize); {выводим ответы}

writeln('Поколений : ' , maxgen);

writeln('Минимум ц.ф. : ' , gmin : 3 : 15);

writeln('Средний минимум ц.ф. : ' , gavgmin : 3 : 15);

end;

WriteLn;

readln;

end.

5. Результаты эксперимента

Размер популяции	Число поколений	Лучшее значение минимума	Среднее значение минимума
8	40	0,5*10-2	1,3880
8	80	0,2*10-2	1,1952
12	40	0,1*10-2	0,3327
12	80	0,9*10-5	0,1278
20	40	0,6*10-3	0,6223
20	80	0,5*10-5	0,1922

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

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



Заключение

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

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



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

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



Приложение

Uses Crt;

CONST maxpop = 100; {максимальное количество индивидов в популяции}

maxstring = 20; {максимальное количество бит в индивиде}

Dim = 2; {размерность области поиска}

pCross = 0.9; {Вероятность скрещивание}

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

type

allele = boolean;{позиция в битовой строке}

chromosome = array [1..maxstring * Dim] of allele; {битовая строка - генотип}

phenotype = array [1..Dim] of real; {фенотип - характеризует приспособленность генотипа}

{структура описывающая индивида}

individual = record

chrom : chromosome; {генотип}

x : phenotype; {фенотип}

fitness : real; {значение целевой функции}

end;

{наша популяция}

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

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

CONST

xymax : phenotype = ( 5.12, 5.12);

xymin : phenotype = (-5.12,-5.12);

var

{старое, новое, промежуточное популяции}

OldPop , NewPop , IntPop : population;

popsize : byte; {размер популяции}

lchrom : byte; {кол-во битов в индивиде}

gen : byte; {текущее количество поколений}

maxgen : byte; {максимальное количество поколений}

{глобальные вещественные переменные}

nmutation , ncross : integer;

{Статистические переменные}

avg , max , min , sumfitness : real;

{глобальная статистика по всем поколениям}

gavgmin, gmin, gmax : real;

i : integer;

b : boolean;

{

Случайное число [0..1]

}

Function Random_:real;

Begin

random_ := random(65535) / (65534);

End;

{

Подбрасывание монетки true если орел

}

Function Flip(probability : real) : boolean;

Begin

if probability = 1.0 then

flip := true

else

flip := (random_ <= probability);

End;

{

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

}

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 : phenotype) : real;

Begin

ObjFunc := x[1] * x[1] + x[2] * x[2];

End;

{

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

Проще говоря по генотипу получаем фенотип индивида

}

Procedure Decode(chrom : chromosome; lbits : integer; var x : phenotype);

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;

{

вычисление фенотипа те сопоставление двоичному числу по генотипу

числа из диапазона xymax xymin

f = 2^N accum = I

}

x[i] := xymin[i] + (xymax[i] - xymin[i]) * accum / (f - 1)

end

End;

{ Инициализация начальной популяции случайным образом }

Procedure InitPop;

Var i, j: integer;

Begin

for i := 1 to popsize do

with oldpop[i] do begin

{Составляем произвольные генотипы}

for j := 1 to lchrom * dim do

chrom[j] := flip(0.5);

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

decode(chrom,lchrom,x);

{Вычисление приспособленности генотипов}

fitness := objfunc(x);

end;

End;

{

Расчет статистик популяции

}

Procedure Stat(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

{Cумма функции пригодности}

sumfitness := sumfitness + fitness;

if fitness > max then

max := fitness;

if fitness < min then

min := fitness;

end;

{Среднее}

avg := sumfitness / popsize;

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

{

если ipick больше количиства индивидов впопуляции, то

необходимо перемешать ее

}

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 chrome : chromosome;

var nmutation , flchrom : integer);

Var j : integer;

Begin

if flip(pMutation) then begin

j := rnd(1 , flchrom);

if chrome[j] then

chrome[j] := false

else

chrome[j] := true;

end;

End;

{

одноточечное скрещивание

}

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

flchrom : integer;

var ncross , nmutation : integer);

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

var

j : integer;

jcross1 : integer;

begin

if flip(pcross) then begin

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

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

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

ncross := ncross + 1;

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

end else begin

jcross1 := flchrom;

end;

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

for j := 1 to jcross1 do begin

child1[j] := parent1[j];

child2[j] := parent2[j];

end;

{вторая часть обмена, 1 во 2 и 2 в 1 }

for j := jcross1 + 1 to flchrom do begin

child1[j] := parent2[j];

child2[j] := parent1[j];

end;

if jcross1 <> flchrom then begin

mutation(child1 , nmutation , flchrom);

mutation(child2 , nmutation , flchrom);

end;

end;

{

Генерация нового поколения в популяции с четным размером

}

Procedure generation;

Var j: integer;

Begin

select;

j := 1;

repeat

crossover(oldpop[j].chrom, oldpop[j+1].chrom,

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

lchrom*dim, ncross, 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 i1 , i2 : byte;

begin

clrscr;

lchrom := 20;

{Вероятности скрещивания и мутации}

for i1 := 1 to 3 do

for i2 := 1 to 2 do begin

{флаг для определения необходимости присвоить первый раз минимум}

b := false;

gavgmin := 0;

{количество индивидов в популяции}

if i1 = 1 then

popsize := 8

else if i2 = 1 then

popsize := 12

else

popsize := 20;

{Количество поколений в исследовании}

if i2 = 1 then

maxgen := 40

else

maxgen := 80;

randomize;

for i := 1 to 30 do begin

initpop;

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

gen := 0;

nmutation := 0;

ncross := 0;

{Проходим поколения 0 ... MaxGen}

repeat

inc(gen);

generation;

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

oldpop := newpop;

until (gen >= maxgen);

{необходимо установить минимум}

if not b then begin

b := true;

gmin := min;

gmax := max;

end;

gavgmin := gavgmin + min;

if (gmin > min) then gmin := min;

if (gmax < max) then gmax := max;

end;

gavgmin := gavgmin / 30; {среднее}

writeln('Объем популяции : ' , popsize);

writeln('Поколений : ' , maxgen);

writeln('Минимум ц.ф. : ' , gmin : 3 : 15);

writeln('Средний минимум ц.ф. : ' , gavgmin : 3 : 15);

end;

WriteLn;

readln;

end.

Результат выполнения программы



Размещено на Allbest.ru