ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

В ЗАДАЧАХ ОПТИМИЗАЦИИ

Цель работы – ознакомление с общими принципами работы генетических алгоритмов и применением их в задачах оптимизации.

Основные сведения

Генетические алгоритмы (ГА), оперируют с последовательностями двоичных цифр (единиц и нулей), получивших название хромосом [1]. Эти алгоритмы имитируют эволюционные процессы в поколениях таких хромосом. В них реализованы механизмы селекции и репродукции, аналогичные применяемым при естественной эволюции. Так же, как и в природе, ГА осуществляют поиск «хороших» хромосом без использования какой-либо информации о характере решаемой задачи. Требуется лишь некая оценка каждой хромосомы, отражающая ее приспособленность. Механизм селекции заключается в выборе хромосом с наивысшей оценкой, т. е. наиболее приспособленных, которые репродуцируют чаще, чем особи с более низкой оценкой (хуже приспособленные). Репродукция означает создание новых хромосом в результате рекомбинации генов родительских хромосом. Рекомбинация – это процесс, в результате которого возникают новые комбинации генов. Для этого используются две операции: скрещивание, позволяющее создать две совершенно новые хромосомы потомков путем комбинирования генетического материала пары родителей, а также мутация, которая может вызвать изменения в отдельных хромосомах.

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

Классический ГА состоит из следующих шагов: инициализация, или выбор исходной популяции хромосом; оценка приспособленности хромосом в популяции; проверка условия остановки алгоритма; селекция хромосом; применение генетических операторов; формирование новой популяции; выбор " наилучшей" хромосомы. Схема выполнения ГА приведена на рис. 6.1.

Рис. 6.1

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

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

Рис. 1. Схема выполнения генетического алгоритма

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

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

Селекция хромосом заключается в выборе (по рассчитанным на втором этапе значениям функции приспособленности) тех хромосом, которые будут участвовать в создании потомков для следующей популяции, т. е. для очередного поколения. Такой выбор производится согласно принципу естественного отбора, по которому наибольшие шансы на участие в создании новых особей имеют хромосомы с наибольшими значениями функции приспособленности. Существуют различные методы селекции. Наиболее популярным считается так называемый метод рулетки (roulette wheel selection). Каждой хромосоме может быть сопоставлен сектор колеса рулетки, величина которого устанавливается пропорциональной значению функции приспособленности данной хромосомы. Поэтому чем больше значение функции приспособленности, тем больше сектор на колесе рулетки. В результате селекции создается родительская популяция, также называемая родительским пулом (mating pool) с численностью N, равной численности текущей популяции.

Применение генетических операторовк хромосомам, отобранным с помощью селекции, приводит к формированию новой популяции потомков от созданной на предыдущем шаге родительской популяции. В классическом ГА применяются два основных генетических оператора: оператор скрещивания (crossover) и оператор мутации (mutation). Поскольку операция мутации играет второстепенную роль по сравнению с операцией скрещивания, оператор скрещивания в классическом ГА применяется практические всегда, а оператор мутации – достаточно редко.

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

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

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

Оператор мутации изменяет значение гена в хромосоме на противоположное (т. е. с 0 на 1 или обратно).

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

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

Пример. Для иллюстрации выполнения классического ГА рассмотрим сильно упрощенный пример, состоящий в нахождении хромосомы с максимальным количеством единиц. Пусть хромосомы состоят из 12 генов, а популяция насчитывает 8 хромосом. Понятно, что наилучшей будет хромосома, состоящая из 12 единиц. Посмотреть, как протекает процесс решения этой задачи с помощью ГА можно при помощи функции gen12(q) (задается преподавателем), запускаемой из рабочей области MATLAB. Функция имеет один необязательный параметр q – число эволюционных циклов (по умолчанию его значение равно 10). Этот параметр задает предел на количество поколений, которые сменяются до получения оптимального решения.

Исходная популяция насчитывает 8 хромосом, функция приспособленности определяет количество единиц в хромосоме. Селекция хромосом осуществляется методом рулетки. Вероятность мутации во всех эволюционных циклах равна 0, а вероятность скрещивания равна 1. Это означает, что ни одна из отобранных при селекции хромосом не подвергается мутации, и все они составляют популяцию хромосом, предназначенных для скрещивания.

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

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

Применение алгоритма для оптимизации функций f(x) = x².

Сначала необходимо создать m-файл для описания рассматриваемой функции в виде: function y = fun_name(x); y = x^².

Закодированная таким образом функция затем будет передаваться в виде ссылки на созданный m-файл: @fun_name.

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

В поле Fitness function вводим ссылку на функцию, а в поле Number of variables – количество независимых переменных для данной функции. Заполнение этих полей обязательно, остальные поля можно оставить без изменений. Запуск генетического алгоритма осуществляется кнопкой Start.

При завершении работы алгоритма в соответствующих окнах выводится значение найденного минимума (значение функции – Fitness function value) в точке с координатами (поле Final point), а также номер цикла, на котором данное решение было получено. Затем можно продолжить вычисление, предварительно изменив настройки ГА: Population type – тип данных; Population size – количество особей в каждой популяции; Selection – тип селекции; Mutation – вид и вероятность мутации; Crossover – вид селекции.

Порядок выполнения работы

1. Ознакомление с принципом работы классического ГА с помощью программы gen12.m. Количество эволюционных циклов: q = 2; 3; 4.

2. Определение минимума функции f(x) = x² (согласно описанию).

3. Определение минимума функции . Функция имеет минимум равный 0 в нескольких точках.

Содержание отчета

1. Описание работы ГА на примере одного из циклов программы gen12.m.

2. Результаты оптимизации (графики функций, настройки ГА, полученные экстремальные значения).

6.4. Контрольные вопросы

1. Краткое изложение механизма ГА.

2. Достижим ли глобальный экстремум помощью ГА?

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

1. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы /Пер. с польск. И. Д. Рудинского. - М.: Горячая линия - Телеком, 2004.

2. Алиев Р. А., Церковный А. Э., Мамедова Г. А. Управление производством при нечеткой исходной информации. - М.: Энергоатомиздат, 1991.

3. Поляхов Н. Д., Приходько И. А. Нечеткие системы управления: Учеб. пособие. СПб.: Изд-во СПбГЭТУ " ЛЭТИ", 2003.

4. Дьяконов В., Круглов В. Математические пакеты расширения MATLAB: Спец. справ. - СПб.: Питер, 2001.

5. Джонс М. Т. Программирование искусственного интеллекта в приложениях /Пер. с англ. А. И. Осипова - М.: ДМК Пресс, 2004.

Содержание

Лабораторная работа № 1. Построение и исследование нечеткого

регулятора на основе алгоритма Заде-Мамдани…………………………………………..…3

Лабораторная работа № 2. Построение и исследование нечеткого

регулятора на основе алгоритма Такаги-Сугено……………………………………………..8

Лабораторная работа № 3. Решение задач аппроксимации на основе

нейронечеткого подхода……………………………………….…………………………..….11

Лабораторная работа № 4. Реализация логических функций " и", " или", " не" с помощью искусственного нейрона……………………...………………………….…………..14

Лабораторная работа № 5. Решение задач аппроксимации средствами

нейросетевых технологий……………………………………………………………………..17

Лабораторная работа № 6. Применение генетических алгоритмов

в задачах оптимизации……………………………………………………………...………….22

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

Редактор И. Г. Скачек

__________________________________________________________________

Подписано в печать.. Формат 60 ´ 84 1/16.

Бумага офсетная. Печать офсетная. °Печ. л. 1, 75.

Гарнитура " Times". Тираж 100 экз. Заказ.

__________________________________________________________________

Издательство СПбГЭТУ " ЛЭТИ"

197376, С.-Петербург, ул. Проф. Попова, 5

⇐ Предыдущая 1 2 34