Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Пример работы и анализа генетического алгоритма




Читайте также:
  1. C2 Покажите на трех примерах наличие многопартийной политической системы в современной России.
  2. C2 Раскройте на трех примерах научный вывод о том, что социальные условия влияют на характер и форму удовлетворения первичных (биологических, витальных) потребностей.
  3. FDDI. Кадр. Процедуры управления доступом к кольцу и инициализации работы кольца.
  4. I. Задачи настоящей работы
  5. II. Организация выполнения курсовой работы
  6. II. Примеры проективных методик
  7. III. Защита курсовой работы
  8. III. КАКАЯ ИНФОРМАЦИЯ НУЖНА РУКОВОДСТВУ ДЛЯ РАБОТЫ
  9. III. Подготовка к защите, защита работы
  10. III. Примеры решения задач.

При использовании генетического алгоритма для решения задачи оптимизации необходимо:

1. Определить количество и тип оптимизируемых переменных задачи, которые необходимо закодировать в хромосоме.

2. Определить критерий оценки особей, задав функцию приспособленности (целевую функцию).

3. Выбрать способ кодирования и его параметры.

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

Отметим, что параметры ГА, определяемые в пункте 4 (а также, иногда, в пунктах 2 и 3), часто определяются методом проб и ошибок, на основе анализа получаемых результатов. Для анализа результатов работы ГА необходимо произвести несколько запусков алгоритма, для повышения достоверности выводов о качестве получаемых результатов, т.к. результат работы ГА носит вероятностный характер. Описанная общая схема решения задачи с использованием ГА показана на рис. 5.8.

Рассмотрим пример использования ГА для решения задачи минимизации следующей функции (сферическая функция):

(7.1)

Параметр n задает количество переменных функции z. Необходимо найти такие значения переменных xi , при которых функция z принимает наименьшее значение. Будем использовать общую схему решения (рис. 5.8):

1. Определение неизвестных переменных задачи.По условию поставленной задачи необходимо найти значения переменных xi, минимизирующие значение функции z, поэтому в хромосоме будем кодировать значения xi. Таким образом, каждый i-й ген хромосомы будет соответствовать i-й переменной функции z.

2. Задание функции приспособленности. Будем определять приспособленность особи в зависимости от значения, которое принимает функция z при подстановке в нее вектора параметров, соответствующих хромосоме этой особи. Поскольку рассматривается задача минимизации функции z, то будем также считать, что чем меньше значение z, тем приспособленнее особь. Приспособленность i-й особи fi будем определять по следующей формуле:

где zi – значение функции z в точке, соответствующей i-й особи.

 

 

Рис. 5.8. Общая схема решения задачи с использованием ГА

 

3. Выбор способа кодирования. В качестве способа представления генетической информации рассмотрим целочисленное кодирование с точностью кодирования параметров 0,01. Тогда в имеющемся по условию задачи диапазоне изменения значений параметров [–5,12; 5,11] можно закодировать (5,12 – (-5,11))/0,01 + 1 = 1024 различных значений переменной. Единица прибавляется, так как значение переменной равное 0 также учитывается.



Для того чтобы представить 1024 различных значений переменной, достаточно использовать log21024 = 10 бит на каждую переменную. Таким образом, будет использоваться целочисленное кодирование с 10-разрядными генами.

4. Определение параметров ГА. Для решения задачи рассмотрим популяцию из 20 особей. При отборе особей для скрещивания будем использовать турнирную селекцию с бинарным турниром. В качестве генетических операторов будем использовать 1-точечный кроссинговер и битовую мутацию. Вероятности применения операторов скрещивания и мутации установим равными 0,7 и 0,05, соответственно. Новое поколение будем формировать только из особей-потомков, т.е. величина разрыва поколений T равна 1.

Результат работы генетического алгоритма с выбранными параметрами представлен на рис. 7.9. Показаны зависимости изменения среднего <z> и наименьшего zmin в популяции значения функции z от номера поколения t. Данные усреднены по 100 независимым запускам.



 

Рис. 5.9. Изменение zmin(t) и <z>(t). Популяция из 20 особей, бинарный турнирный отбор, одноточечный кроссинговер (РС = 0,7), битовая мутация (РМ = 0,05)

 

По данным рис. 5.9 видно, что после 20-го поколения значение zmin колеблется в достаточно большом диапазоне. Из этого следует, что потери хороших особей в результате мутации велики, и следует уменьшить вероятность мутации. Установим значение этого параметра равным L-1 = 0,01, где L – длина хромосомы в битах, в данном случае L = 100. Результаты работы ГА с измененным значением вероятности мутации показаны на рис. 5.10.

 

Рис. 5.10. Изменение zmin(t) и <z>(t). Популяция из 20 особей, бинарный турнирный отбор, одноточечный кроссинговер (РС = 0,7), битовая мутация (РМ = 0,01)

 

Из сравнения графиков на рис 5.9 и 5.10 следует, что уменьшение вероятности мутации улучшило результат работы ГА. Также отметим, что теперь эволюционный процесс стабилизировался значительно позднее, примерно после 60-го поколения. Усредненное по всем запускам минимальное значение функции z, достигнутое за первые 100 поколений, равно ~1,016. Чтобы улучшить результат, увеличим давление селекции путем увеличения размера турнира до 4. Результат представлен на рис. 5.11.

Увеличение давления селекции привело к ускорению эволюционного поиска за счет удаления из популяции особей со средней и плохой приспособленностью. В результате стабилизация наступила после 40-го поколения, а усредненное по всем запускам минимальное полученное значение функции z равно ~0,013. Наименьшее значение функции z достигается в точке xi = 0, i = 1,2,…,10 и равно 0. В случае поиска минимума функции z с точностью 0,01, для ГА с параметрами, соответствующими графикам на рис. 5.11, решение было найдено в 69 запусках из 100. При этом в среднем было использовано 1698,68 вычислений целевой функции.



 

Рис. 5.11. Изменение zmin(t) и <z>(t). Популяция из 20 особей, турнирный отбор (t = 4), одноточечный кроссинговер (РС = 0,7), битовая мутация (РМ = 0,01)

 

Чтобы повысить стабильность результатов, увеличим размер популяции до 50 особей. Полученные кривые zmin(t) и <z>(t) изображены на рис. 5.12. Во всех 100 запусках найден минимум функции z с точностью не меньше 0,01. Среднее количество вычислений целевой функции, использованное для нахождения решения, равно 3145,34.

 

Рис. 5.12. Изменение zmin(t) и <z>(t). Популяция из 50 особей, турнирный отбор (t = 4), одноточечный кроссинговер (РС = 0,7), битовая мутация (РМ = 0,01)

 


Дата добавления: 2014-12-23; просмотров: 18; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.015 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты