89130

Решение задачи оптимизации методом генетического алгоритма

Контрольная

Информатика, кибернетика и программирование

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

Русский

2015-05-09

248.02 KB

7 чел.

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

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ

УНИВЕРСИТЕТ

Кафедра «Прикладная математика и исследование операций в экономике»

КОНТРОЛЬНАЯ РАБОТА № 2 (13ИС2б)

по дисциплине «Дискретная математика. Методы оптимизации. Численные методы»

на тему «Решение задачи оптимизации методом генетического алгоритма»

Вариант № __

Автор работы:              ____________________________

Специальность:                                       _____________________________

Группа:       __________________________

Руководитель:      _____________________________

Работа защищена «__»_____20__г.  Оценка _______________

2014 г.

Содержание

Введение 3

1. ПОСТАНОВКА ЗАДАЧИ 3

2. Теоретические сведения 4

2.1 Понятие генетического алгоритма 4

2.2 Понятие минимизации функции многих переменных 5

3. Решение задания 7

3.1 Построение графика функции 7

3.2 Оптимизация заданной функции 7

3.3 Отражение хода решения задачи 8

3.4 Исследование зависимости решения от вида функции отбора родителей для кроссинговера и мутации потомков 9

Вывод 10

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

Приложение А – Текст программы 11


Введение

В процессе выполнения данной контрольной работе была написана программа Matlab, основной задачей которой является проведение условной минимизации заданной функции нескольких переменных на основе применения генетического алгоритма (ГА). Генетический алгоритм был реализован по уравнениям и данным, заданным согласно варианту. Также была реализована настройка ГА  встроенной  функцией gaoptimset. Результат был сравнен с результатом написанной программы. Также были проведены исследования работы ГА с необходимыми графическими иллюстрациями в соответствии с вариантом.

1. ПОСТАНОВКА ЗАДАЧИ

Цель работы.

Научиться реализовывать условную минимизацию заданной функции нескольких переменных на основе применения генетического алгоритма (ГА) в среде Matlab, научиться реализовывать алгоритм, не используя окно тулбокса, настраивать ГА встроенной функцией MATLAB gaoptimset и исследовать работу ГА, реализуя различные графики, диаграммы, таблицы.

Задание на контрольную работу.

  1.  Провести условную минимизацию заданной функции нескольких переменных на основе применения генетического алгоритма (ГА), программно реализованного в Matlab (использовать только стандартную функцию).
  2.  Составить программу решения задачи в Matlab в виде m-файла, не используя окно тулбокса.
  3.  Для настройки ГА использовать функцию gaoptimset. Все задаваемые опции прописать в разработанной программе явным образом.
  4.  Провести исследования работы ГА с необходимыми графическими иллюстрациями в соответствии с вариантом.

Индивидуальное задание.

Вариант № 24.

Дана следующая функция:

  1.  Построить график заданной функции при n = 2. Определить визуально, имеет ли данная функция глобальный минимум.
  2.  Провести оптимизацию заданной функции в Matlab (с помощью генетического алгоритма): найти глобальный минимум.
  3.  Для решения задачи составить программу в среде Matlab (m-файл).
  4.  Результат определить как среднее по 20 решениям.
  5.  В отчете отразить ход решения задачи:

- представить график средних и наилучших по поколениям значений целевой функции;

- провести исследование зависимости решения от вида функции отбора родителей для кроссинговера и мутации потомков.

2. Теоретические сведения

2.1 Понятие генетического алгоритма

Генетические алгоритмы — это адаптивные методы поиска, которые в последнее время используются для решения задач оптимизации. В них используются как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде и основные понятия линейной алгебры. Основной идеей генетических алгоритмов является организация «борьбы за существование» и «естественного отбора» среди этих пробных решений.

Рассмотрим принципы работы генетических алгоритмов на максимально простом примере. Пусть требуется найти глобальный минимум функции на отрезке [0; 7]. На этом отрезке функция принимает минимальное значение в точке x = 1. Очевидно, что в точке x = 6 функция попадает в локальный минимум. Если для нахождения глобального минимума использовать градиентные методы, то в зависимости от начального приближения можно попасть в данный локальный минимум.

Рассмотрим на примере данной задачи принцип работы генетических алгоритмов. Для простоты положим, что x принимает лишь целые значения, т.е. x {0, 1, 2, 3, 4, 5, 6, 7}. Это предположение существенно упростит изложение, сохранив все основные особенности работы генетического алгоритма. Выберем случайным образом несколько чисел на отрезке [0; 7]: {2, 3, 5, 4}.  Запишем пробные решения в двоичной форме: {010, 011, 101, 100}. Поскольку генетические алгоритмы используют биологические аналогии, то и применяющаяся терминология напоминает биологическую. Так, одно пробное решение, записанное в двоичной форме, мы будем называть особью или хромосомой, а набор всех пробных решений – популяцией. Как известно, принцип естественного отбора заключается в том, что в конкурентной борьбе выживает наиболее приспособленный. В нашем случае приспособленность особи определяется целевой функцией: чем меньше значение целевой функции, тем более приспособленной является особь, т.е. пробное решение, использовавшееся в качестве аргумента целевой функции.

Теперь приступим к процессу размножения: попробуем на основе исходной популяции создать новую, так чтобы пробные решения в новой популяции были бы ближе к искомому глобальному минимуму целевой функции. Для этого сформируем из исходной популяции брачные пары для скрещивания. Поставим в соответствие каждой особи исходной популяции случайное целое число из диапазона от 1 до 4. Будем рассматривать эти числа как номера членов популяции. При таком выборе какие-то из членов популяции не будут участвовать в процессе размножения, так как образуют пару сами с собой. Какие-то члены популяции примут участие в процессе размножения неоднократно с различными особями популяции. Процесс размножения (рекомбинация) заключается в обмене участками хромосом между родителями. Например, пусть скрещиваются две хромосомы 111111 и 000000. Определяем случайным образом точку разрыва хромосомы, пусть, это будет 3: 111|111 000|000. Теперь хромосомы обмениваются частями, стоящими после точки разрыва, и образуют двух новых потомков: 111000 и 000111.

Следующим шагом в работе генетического алгоритма являются мутации, т.е. случайные изменения полученных в результате скрещивания хромосом. Пусть вероятность мутации равна 0,3. Для каждого потомка возьмем случайное число на отрезке [0; 1], и если это число меньше 0,3, то инвертируем случайно выбранный ген (заменим 0 на 1 или наоборот).

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

Теперь из четырех особей-родителей и четырех полученных особей потомков необходимо сформировать новую популяцию. В новую популяцию отберем четыре наиболее приспособленных особей из числа «старых» особей и особей-потомков.

В результате получим новое поколение. Получившуюся популяцию можно будет вновь подвергнуть кроссинговеру, мутации и отбору особей в новое поколение. Таким образом, через несколько поколений мы получим популяцию из похожих и наиболее приспособленных особей. Значение приспособленности наиболее «хорошей» особи (или средняя приспособленность по популяции) и будет являться решением нашей задачи. Следуя этому, в данном случае, взяв наиболее приспособленную особь 001 во втором поколении, можно сказать, что минимумом целевой функции является значение −5,42, соответствующее аргументу x = 1. Тем самым попадания в локальный минимум удалось избежать! На данном примере разобран вариант простого генетического алгоритма. При дальнейшем использования ГА к разным задачам возможно моделирование основных операторов алгоритма.

2.2 Понятие минимизации функции многих переменных

Градиентом дифференцируемой функции f(x) в точке х[0] называется n-мерный вектор f(x[0]), компоненты которого являются частными производными функции f(х), вычисленными в точке х[0], т. е. f'(x[0]) = (дf(х[0])/дх1, …, дf(х[0])/дхn)T.

Этот вектор перпендикулярен к плоскости, проведенной через точку х[0] , и касательной к поверхности уровня функции f(x), проходящей через точку х[0] .В каждой точке такой поверхности функция f(x)принимает одинаковое значение. Приравнивая функцию различным постоянным величинам С0, С1, ... , получим серию поверхностей, характеризующих ее топологию.

Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке. Вектор, противоположный градиенту (-f’(х[0])), называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы первого порядка, называемые также градиентным и методами минимизации. Использование этих методов в общем случае позволяет определить точку локального минимума функции.

Очевидно, что если нет дополнительной информации, то из начальной точки х[0] разумно перейти в точку х, лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска р[k] антиградиент -f’(х[k]) в точке х[k], получаем итерационный процесс вида х[k+1] = x[k]-akf'(x[k]), аk > 0; k=0, 1, ...

В координатной форме этот процесс записывается следующим образом:

xi[k+1]=хi[k] - akf(x[k])/xi; i = 1, ..., n; k= 0, 1, 2,...

В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента || x[k+l] - x[k] || <= e, либо выполнение условия малости градиента|| f’(x[k+l]) || <= g. Здесь e и g - заданные малые величины.

Возможен и комбинированный критерий, состоящий в одновременном выполнении указанных условий. Градиентные методы отличаются друг от друга способами выбора величины шага аk. При методе с постоянным шагом для всех итераций выбирается некоторая постоянная величина шага. Достаточно малый шаг аk обеспечит убывание функции, т. е. выполнение неравенства f(х[k+1]) = f(x[k] – akf’(x[k])) < f(x[k]).

Однако это может привести к необходимости проводить неприемлемо большое количество итераций для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать неожиданный рост функции либо привести к колебаниям около точки минимума (зацикливанию). Из-за сложности получения необходимой информации для выбора величины шага методы с постоянным шагом применяются на практике редко. Более экономичны в смысле количества итераций и надежности градиентные методы с переменным шагом, когда в зависимости от результатов вычислений величина шага некоторым образом меняется.


3. Решение задания

3.1 Построение графика функции

График заданной функции представлен на рисунке 3.1.

Рис. 3.1 – График заданной функции

3.2 Оптимизация заданной функции

В процессе оптимизации целевой функции в командном окне Matlab отображается информация о следующих параметрах (рис. 3.2):

- номере поколения и количестве вычислений значений целевой функции;

- наилучших значениях целевой функции;

- среднем значении целевой функции;

- количестве вычислений в рамках одного поколения;

- причины завершения расчета.

Рисунок 3.2 – Текущая информация о параметрах

 3.3 Отражение хода решения задачи

В результате решения задачи оптимизации заданной функции искомые xi стремятся к значениям, показанным на рис. 3.2.

Результаты решения (значения целевой функции) представлены в таблице 3.1.

n=2

-27

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

Рис. 3.3 - График средних и наилучших по поколениям значений целевой функции

3.4 Исследование зависимости решения от вида функции отбора родителей для кроссинговера и мутации потомков

 Для проведения исследования задавались различным видом функции отбора родителей для кроссинговера и мутации потомков:

  1.  @selectionremainder;
  2.  @selectionuniform;
  3.  @selectionstochunif;
  4.  @selectionroulette;
  5.  @selectiontournament.

Результаты расчетов представлены на рисунке 3.4.

Рис. 3.4 - График зависимости решения от вида функции отбора родителей для кроссинговера и мутации потомков

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


Вывод

В процессе выполнения данной контрольной работы была реализована программа Matlab, основной задачей которой является проведение условной минимизации заданной функции нескольких переменных на основе применения генетического алгоритма (ГА). Генетический алгоритм был реализован по уравнениям и данным, заданным согласно варианту. Также была реализована настройка ГА встроенной  функцией gaoptimset. Результат был сравнен с результатом написанной программы. Также были проведены исследования работы ГА с необходимыми графическими иллюстрациями в соответствии с вариантом.

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

  1.  Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Изд. «Высшая школа», 1986.
  2.  Гершкович Ю.Б. Методы оптимизации и их применение для управления процессами в нефтяной промышленности. – М.: МИНГ им. И.М. Губкина, 1988.
  3.  Моисеев Н.Н., Иванилов Ю.П. Методы оптимизации. – М.: Наука, 1978.
  4.  Новгородцев А. Расчет электрических цепей в “MATLAB”. – Спб.: Питер, 2004.


Приложение А – Текст программы

Файл a2.m

N = 20;

nvars = 2; % число переменных x

 

Xmin(1) = -30;

Xmax(1) = 30;

Xmin(2) = -10;

Xmax(2) = 10;

% построение графика функции 2-х переменных

if nvars == 2

   dx1 = (Xmax(1)-Xmin(1))/49;

   dx2 = (Xmax(2)-Xmin(2))/49;

   x1 = Xmin(1):dx1:Xmax(1);

   x2 = Xmin(2):dx2:Xmax(2);

   n1 = length(x1);

   n2 = length(x2);

 for i=1:1:n1

    for j=1:1:n2

Y(i,j) = 2*x1(i)^2-4*x1(i)^4+1/2*x1(i)^6+x1(i)^2*x2(j)^2;

    end

 end

   surfc(x1,x2,Y), grid on;

   xlabel('x1');

   ylabel('x2');

   zlabel('f(x)');

end

 

for i1=1:1:5

   switch i1

   case 1,

        SF = @selectionremainder;

   case 2,

        SF = @selectionuniform;

   case 3,

        SF = @selectionstochunif;

   case 4,

        SF = @selectionroulette;

   case 5,

        SF = @selectiontournament;

end

PIR   = [Xmin;Xmax];

options = gaoptimset;

options = gaoptimset(options,'PopInitRange', PIR);

options = gaoptimset(options,'PopInitRange', []);

options = gaoptimset(options,'PopulationSize', 100);

options = gaoptimset(options,'EliteCount', 5);

options = gaoptimset(options,'CrossoverFraction', 0.8);

options = gaoptimset(options,'ParetoFraction', 0.05);

options = gaoptimset(options,'MigrationDirection', 'both');

options = gaoptimset(options,'MigrationInterval', 1);

options = gaoptimset(options,'MigrationFraction', 1);

options = gaoptimset(options,'Generations', 100);

options = gaoptimset(options,'TimeLimit', 400);

options = gaoptimset(options,'FitnessLimit', -Inf);

options = gaoptimset(options,'StallGenLimit', 50);

options = gaoptimset(options,'StallTimeLimit', 600);

options = gaoptimset(options,'TolFun', 1e-6);

options = gaoptimset(options,'TolCon', 1e-6);

options = gaoptimset(options,'InitialPopulation', []);

options = gaoptimset(options,'InitialScores', []);

options = gaoptimset(options,'InitialPenalty', []);

options = gaoptimset(options,'PenaltyFactor', []);

options = gaoptimset(options,'CreationFcn', @gacreationuniform);

options = gaoptimset(options,'FitnessScalingFcn', @fitscalingrank);

options = gaoptimset(options,'SelectionFcn', SF);

options = gaoptimset(options,'CrossoverFcn', {@crossoverheuristic, 1.2});

options = gaoptimset(options,'MutationFcn', @mutationadaptfeasible);

options = gaoptimset(options,'DistanceMeasureFcn', []);

options = gaoptimset(options,'HybridFcn', []);

options = gaoptimset(options,'Display', 'iter');

options = gaoptimset(options,'PlotFcns', { @gaplotbestf });

options = gaoptimset(options,'PlotInterval', 1);

     

for k=1:1:N

[X(k,:),FVal(k)]=ga(@ex95,nvars,[],[],[],[],Xmin,Xmax,[],options);

end

F(i1) = mean(FVal),

   for j=1:1:nvars

       X_(i1,j) = mean(X(:,j));  

   end

   X_(i1,:),

End

figure(3);

plot(1:1:i1,F), grid on;

Файл ex95.m

function y = ex95(x)

x(1)^2-12*x(1)+11+10*cos(pi/2*x(1))+8*sin(5*pi*x(1))-1/sqrt(5)*exp(-1*((x(1)-0.5)^2)/2);

end


 

А также другие работы, которые могут Вас заинтересовать

34426. Россия на рубеже XVI – XVII вв. Смутное время и его последствия 43.5 KB
  Начало XVII века в России произошли события вошедшие в историю под названием Смутного времени. Они были заинтересованы в отторжении западных территорий России. Появление шведов на территории России дало Сигизмунду III враждовавшему со Швецией повод для открытой интервенции. Шведы в это время оккупировали север России.
34427. Становление самодержавия Романовых в XVII в 33 KB
  После возвращения из плена отца царя Михаила Федоровича Филарета созыв соборов прекратился. Ее функции стала выполнять так называемая Ближняя государева дума составленная из доверенных лиц царя. Теперь назначение на должности стало исключительно волей царя. Человек обнаживший в присутствии царя оружие наказывался отсечением руки.
34428. Преобразования Петра I в первой четверти XVIII в.: содержание, итоги, последствия 15.24 KB
  Изменения в сословиях: По указу о единонаследии запрещалось делить имения при передаче их по наследству. Изменения в государственном управлении: В 1721 г. Изменения в области культуры: Развивалось просвещение. Произошли изменения во внешнем облике дворян.
34429. Дворцовые перевороты в России в середине XVIII века 30.5 KB
  Причины дворцовых переворотов: Указ Петра I о престолонаследии 1722 г. императором стал внук Петра I Петр II. Императрицей стала племянница Петра I Анна Иоанновна вдова герцога Курляндского. в результате дворцового переворота с помощью гвардии императрицей стала дочь Петра I Елизавета Петровна.
34430. Россия в эпоху Екатерины II. Просвещенный абсолютизм 27.5 KB
  Внутренняя политика. Политика Екатерины II известна как политика просвещенного абсолютизма. Просвещенный абсолютизм – политика сформировавшаяся под влиянием идей философов – просветителей и направленная на организацию общества на основе разумных законов при сохранении абсолютной власти монарха. В результате политика Екатерины II еще больше укрепила крепостнические порядки.
34431. Противоречивость внутренней политики Александра I 32 KB
  После Отечественной войны 1812 года в настроении Александра I произошли большие перемены.Аракчеев поэтому этот период правления Александра I получил название аракчеевщина.
34432. Отечественная война 1812 г. и заграничный поход русской армии (1813 – 1814 гг.) 32 KB
  Причины войны: Россия нарушала условия невыгодного для нее Тильзитского мира и была препятствием на пути Наполеона к мировому господству. На границе с Россией Наполеон сосредоточил 600тысячную армию. – Бородинское сражение в котором Наполеон стремился разгромить русскую армию. Наполеон не достиг своей цели.
34433. Россия в годы правления Николая I 37.5 KB
  в России начинается промышленный переворот – переход от ручного труда к машинному от мануфактуры к фабрике. Турция стремилась вернуть территории утраченные в войнах с Россией Англия и Франция стремились не допустить усиление влияния России на Балканах и Ближнем Востоке. Основные военные действия развернулись в Крыму где противники России высадили десант и осадили Севастополь. Причины поражения России: Военнотехническая отсталость России Дипломатические просчеты: Россия оказалась в изоляции Итоги: Поражение России в Крымской войне...
34434. Реформы 1860 -1870-х гг. и их значение 35.5 KB
  Реформа расчистила дорогу для развития капиталистических отношений но была половинчатой и не решила аграрного вопроса. Другие реформы: год реформа Содержание 1864 Земская реформа В уездах и губерниях создавались выборные органы самоуправления которые решали местные хозяйственные вопросы. 1864 Судебная реформа Создавался бессословный гласный суд с адвокатом и присяжными заседателями. 1864 Реформа образования Образование становилось бессословным.