Нахождение минимума функции z(x,y) в заданной области методом генетического алгоритма

 

                                                                                                                                                                              

Министерство образования Российской Федерации

 

 

 

 ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ 

СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

 

 

 

 

 

 

 

 

Нахождение минимума функции z(x,y) в заданной области МЕТОДОМ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

Пояснительная записка по курсовому проекту по дисциплине «Информатика»

 

 

 

 

 

 

 

Выполнил:

студент ТМЦДО

специальности 210405

Группы

 

2010 г.

 

 

 

 

 

 

 

 

 

 

Министерство образования Российской Федерации

 

 

ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

 

 

ЗАДАНИЕ

на курсовую работу

“Нахождение минимума функции z(x,y) в заданной области МЕТОДОМ ГЕНЕТИЧЕСКОГО АЛГОРИТМА”

студенту  группа   кафедра _ _

 

Вариант №13

 

1 Исходные данные:

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

2 Задание

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

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

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

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

3 Перечень прилагаемого  материала:

- файл исходной программы KURS.PAS.

 

          Руководитель _________________________(_)

                                                   Подпись                                        Ф.И.О.

           Задание  принял к исполнению

            _____________________________________________________

                                                       дата и подпись студента

 

Содержание

 

Введение

Генетические Алгоритмы (ГА)– адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течение нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы. Например, ГА могут использоваться, чтобы проектировать структуры моста, для поиска максимального отношения прочности/веса, или определять наименее расточительное размещение для нарезки форм из ткани. Они могут также использоваться для интерактивного управления процессом, например на химическом заводе, или балансировании загрузки на многопроцессорном компьютере.

Основные принципы ГА были сформулированы Холландом (Holland, 1975), и хорошо описаны во многих работах. В отличие от эволюции, происходящей в природе, ГА только моделируют те процессы в популяциях, которые являются существенными для развития. Точный ответ на вопрос: какие биологические процессы существенны для развития, и какие нет? – все еще открыт для исследователей.

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

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

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

 

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

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

Генерация случайного начального состояния.

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

Вычисление коэффициента выживаемости (fitness).

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

Воспроизводство.

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

Следующее поколение.

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

 

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

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

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

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

 

Рисунок 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 Триада генетических операторов

 

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

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

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

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

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

Схематично этот вариант показан на рисунке 3.

---

Рисунок 3 Принцип работы двухточечного скрещивания.

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

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

 

4 Результаты работы

В курсовом проекте предполагалось найти минимум функции в заданной области. Листинг программы реализующей поиск минимума функции ,    приведен в приложении А, основная программа KURS.PAS прилагается отдельным файлом.

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

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

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

Результат работы программы сведен в таблицу 1.

Таблица 1 Результаты вычислений

Размер популяции	8 особей		12 особей		20 особей
	Лучший минимум	Среднее значение минимума	Лучший минимум	Среднее значение минимума	Лучший минимум	Среднее значение минимума
Полученное значение при 40 поколениях	0,00000005	0,01924912	0,00000000	0,00161956	0,00000018	0,00002828
Полученное значение при 80 поколениях	0,00000000	0,00000482	0,00000000	0,00000174	0,00000000	0,00000003

 

5 Заключение

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

Очевидно, что минимальное значение данной функции z(x,y) при заданных диапазонах значений переменных будет стремиться к 0. Подвергнув анализу полученные данные, можно сделать вывод, доказывающий, что особенностью генетических алгоритмов является то, что они обеспечивают сходимость к глобальному оптимуму, а не являются случайным поиском решения функции.

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

Увеличение размера популяции, при неизменном количестве поколений, также улучшает значения минимума на 1-2 порядка (среднее значение на 4), т.е. появляется возможность более детального выбора для скрещивания наиболее приспособленных особей, что обеспечивает оптимальный исход решения задачи.

Самые лучшие результаты, как в среднем, так и в минимальном  значении функции, получены при числе поколений 80 и размере популяции 20. Полученный результат максимально стремиться к истинному решению задачи, т.е. к 0.

 

 

Список использованных источников

1. Тимченко С.В., Информатика часть 3, учебное пособие, Томск – 2003г.
2. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. - М.:ФИЗМАТЛИТ, 2003. - 432 с.
3. Батищев Д.А. Генетические алгоритмы решения экстремальных задач. - Воронеж: Изд.-во ВГТУ, 1995.

 

Приложение А

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

program sga;

uses crt;

 

const

     maxpop=80;

     maxstring=20;

     dim=2;

     n=30;

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,5.12);

    xmin:fenotype=(-5.12,-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;

 

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:=sqr(x[1])+sqr(x[2]);

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

          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;

 

function mutation(var child:chromosome; alleleval:allele; pmutation:real;

                  var nmutation:integer; flchrom:integer):allele;

var

   p,mutate:boolean;j1,j2:integer;

begin

     mutate:=flip(pmutation);

     if mutate then begin

        repeat begin

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

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

         end;

         until j1<>j2;

         mutation:=not alleleval;

         p:=child[j1];

         child[j1]:=child[j2];

         child[j2]:=p;

         nmutation:=nmutation+1;

        end else

        mutation:=alleleval

      end;

 

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

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

var pcross, pmutation:real);

 

var

   j:integer;

begin

     if flip(pcross) then begin

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

     ncross:=ncross+1;

     end else jcross:=flchrom;

     for j:=1 to jcross do begin

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

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

     end;

    if jcross<>flchrom then

         for j:=jcross+1 to flchrom do begin

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

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

         end;

     end;

procedure generation;

 

var

   j,mate1,mate2,jcross: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,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;

 

var

   i,j:integer;

   smin,mmin,sr:real;

 

Begin

      clrscr;

      writeln('Введи размер популяции');

      readln (popsize);

      writeln('Введи число поколений');

      readln (maxgen);

      lchrom:=20;

      pmutation:=0.01;

      pcross:=0.9;

 

      randomize;

      nmutation:=0;

      ncross:=0;

      smin:=0;

      for i:=1 to n do

       begin

      initpop;

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

      gen:=0;

      if i=1 then mmin:=min;

      repeat

            gen:=gen+1;

            generation;

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

            oldpop:=newpop;

 

     until(gen>=maxgen);

          if mmin>min then mmin:=min;

             writeln(' минимум =',min:3:8);

 

              smin:=smin+min;

 

    end;

            sr:=smin/n;

 

    writeln('Лучший минимум=',mmin:3:8);

    writeln(Среднее значение минимума =',sr:3:8);

   readln

  end.

 

 

Оценка --- 5. Сама программа  KURS.PAS