Изучение пакета Genetic Algorithm из системы Matlab 7.01 (Лабораторная работа № 7)

Лабораторная  работа  7

Изучение  пакета  Genetic Algorithm  из  системы  Matlab 7.01

Основные  сведения  по генетическим  алгоритмам

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

Терминология  в  генетических алгоритмах

          Фитнесс-функция  (ФФ)  -  это  функция,  которую  необходимо  оптимизировать.  Для  стандартных  алгоритмов  оптимизации  она  известна  как  целевая  функция.

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

          Популяция  -  это  набор  индивидуумов.  Например,  если  размер популяции  составляет  100  индивидуумов,  а  число  переменных  в ФФ  есть  3,  то  вся  популяция  представляется  в  виде  матрицы  100 х 3.  Отдельный  индивидуум  может  появиться  более  чем  один  раз  в  популяции.  Например,  строка  (2  3  1)  может  повториться  несколько  раз  в  матрице.

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

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

          Для создания  следующей  генерации  ГА  выбирает в  текущей  популяции определенные  индивидуумы,  называемые  родителями,  и  использует  их  для  создания  в   следующей  популяции  новых  индивидуумов,  называемых  потомками. 

1. Открытие  командного окна

Открыть  командное  окно  системы  Matlab  путем  выбора  Window – Command  Window.  Набрать  в  командном  окне  системы:    gatool  и  нажать  Enter.  Появится  панель  работы  генетического  алгоритма  (ГА),  как  показано  на  рис.1.

Рис.1. Панель  работы генетического  алгоритма

2. Начало  работы

Для  указания задачи,  которую  необходимо  решить,  используются    2  верхних  поля: 

Fitness function  (фитнесс-функция,  функция  пригодности)  -  та  функция,  которую  нужно  минимизировать.  В  это  поле  необходимо ввести  имя  М-файла,  который  вычисляет  функцию  пригодности  (ФП).

Number of variables  (число  переменных)  -  число  независимых  переменных  для  ФП.

Создание  М-файла

Для  работы  ГА  вначале  нужно  записать  М-файл,  который  вычисляет  оптимизируемую  функцию.  С  целью  большей ясности  изложения  рассмотрим    пример  такой  функции:

которую  необходимо  минимизировать.

          Для  записи  М-файла сделаем  следующие  шаги:

·  Создадим  М-файл  таким образом: в исходной  панели  MATLAB выбрать  File  -  New  -  M-File.  Эта  процедура  откроет  редактор  М-файла.

·  В  окне  редактора  ввести  следующие  2  строки:

 function z = my_fun(x)

z = x(1)^2 - 2*x(1)*x(2) + 6*x(1) + x(2)^2 - 6*x(2);

·  Сохранить  М-файл  как  my_fun.m.

Ввести  в  верхнее  поле  панели  (Fitness function)  имя  М-файла

следующим  образом:  @ my_fun,  а  в  поле   Number of variables  -  число  2,  поскольку  в  этой  функции  две  переменных.  В  итоге  два  верхних  поля  примут  вид,  показанный  на рис.2.   

Рис.2.  Заполненные  поля  панели  

          3. Запуск  ГА

Для  запуска  ГА  нажать  клавишу Start в  панели  Run solver   (Запуск  решателя). После  этого в поле  Current generation  field отобразится  номер  текущей  генерации. В  панели  Status and results  (Состояние  и   результаты)  появится  сообщение   "GA running" (ГА  запущен).

          При  завершении  алгоритма  в  панели  Status and results  появятся  сообщения

·  "GA terminated" (ГА  завершен);

·  значение  фитнесс-функции  лучшей  особи  в  последней  генерации;

·  основание  остановки  алгоритма;

·  координаты  последней  точки.

На  рис.3  показана  часть  итоговой  панели  работы ГА.

Рис.3. Итог  работы  ГА

          4. Пауза  и  остановка  алгоритма

          При  запущенном  ГА  имеются  следующие  возможности  наблюдения  за  его  выполнением:

·  нажать  клавишу  Pause  (Пауза)   для  временной  остановки  алгоритма.  Для  нового  запуска  алгоритма,  используя  текущую  популяцию,  необходимо  нажать  клавишу    Resume (Перезапуск).

·   Нажать  клавишу Stop  для  остановки  алгоритма.   Панель  Status and results  отобразит  значение  ФП  лучшей  точки  в  текущей   популяции  в  момент остановки.  

Примечание.  Если  после  нажатия  клавиши  Stop  вновь  запустить  алгоритм  клавишей   Start,  алгоритм  начнет  работу  с новой  случайной  популяции   или  с  популяции,  которая  определена  в  поле  Initial population   (Начальная  популяция).  В  случае  если  необходимо  запустить  алгоритм с того  места,  где  он  был  остановлен,  нужно  воспользоваться  клавишами   Pause  и  Resume.

Критерии  остановки  алгоритма

  Генетический  алгоритм  использует  5  критериев  остановки  в  том  случае,  если  алгоритм  не  остановлен  с  помощью  клавиши  Stop.  ГА  останавливается,  если  выполняется  одно  из  следующих  условий: