Примеры оптимизации функции с помощью программы FlexTool

Применение генетического алгоритма для оптимизации раз­личных функций будем иллюстрировать примерами, реализованны­ми на IBM PC совместимом компьютере с использованием програм­мы FlexTool [48].

Программа FlexTool позволяет выбирать различные варианты генетического алгоритма - такие, как классический (regular), с частич­ной заменой популяции (steady-state) или микроалгоритм (micro). По­мимо того, предоставляется возможность выбрать метод селекции (рулетка, турнирный или ранговый), а также количество точек скрещи­вания и способ кодирования (двоичное или логарифмическое). В дан­ном случае под двоичным кодированием понимается способ, приме­нявшийся в примерах 4.1, 4.5 и 4.6, а логарифмическое кодирование было представлено в п. 4.8.4. Программа FlexTool также позволяет одновременно оптимизировать несколько функций и содержит алго-

ритм создания ниш для нахождения более чем одного оптимума (по­мимо единственного глобального решения). FlexTool взаимодейству­ет с программой MATLAB и запускается в ее окне. Для определения оптимизируемых функций используются файлы с расширением.т (так называемые гл-файлы), служащие для записи математических функций в программе MATLAB. В рабочем окне MATLAB'a также можно считывать значения различных переменных, используемых программой FlexTool, что дает, в частности, возможность просмотра популяций хромосом.

Программа FlexTool требует от пользователя ввести размер­ность популяций, вероятности скрещивания и мутации, интервалы из­менения параметров задачи (пространства поиска), а также условия останова алгоритма. Предоставляется возможность прервать выпол­нение алгоритма в произвольный момент времени с последующим возобновлением его работы с точки прерывания (так называемый warm-start) либо с начальной точки (cold-start)

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

Пример 4.12 демонстрирует способ решения задачи, рассмот­ренной в примере 4.5, но при использовании генетического алгорит­ма, реализованного в программе FlexTool Для такой простой задачи лучше всего подходит генетический микроалгоритм, представленный в п. 4.8.8. В отличие от примера 4.5, в примере 4.12 ищется минимум функции, заданной формулой (4.1).

Пример 4.12

С помощью генетического микроалгоритма программы FlexTool найти минимум функции, заданной формулой (4.1), т.е.

f(x) = 2х² + 1 для целых значений х в интервале от 0 до 31.

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

Длина хромосом равна пяти, что очевидно следует из возмож­ности кодирования 32 целых чисел (для указанного интервала изме­нения переменной х) пятью битами двоичной последовательности. В программе FlexTool применяется двоичное кодирование, аналогич­ное представленному в примерах 4.1 и 4.5, однако для удобства про­граммной реализации используется обратный код, т.е. на первой по-

Глава 4. Генетические алгоритмы

и функции с помощью программы FlexTool

зиции находится наименее значащий бит, а на последней - наиболее значащий. Такой способ записи прямо противоположен повсеместно распространенной форме записи двоичных чисел.

Существенным элементом выполнения генетического микроал­горитма считается процедура «рестарта», т.е. запуска его с начальной точки при обнаружении сходимости (п. 4.8.8). В программе FlexTool рестарт производится периодически после выполнения установлен­ного количества итераций. По умолчанию оно равно 7, примеры вы­полнялись именно при этом значении.

Исходная популяция - на первой итерации генетического мик­роалгоритма - состоит из следующих хромосом:

[01100] [11000] [01111] [10101] [11001] со значениями фенотипов

6 3 30 21 19,

которые являются действительными целыми числами из интервала от 0 до 31.

Наименьшее значение функции приспособленности в этой по­пуляции имеет стоящая на втором месте хромосома с фенотипом, равным трем. Оно равно 19. Наибольшее значение функции приспо­собленности у стоящей на третьем месте хромосомы с фенотипом, равным 30, составляет 1801. Легко подсчитать, что среднее значение функции приспособленности будет равно 699,8.

Популяция, полученная в результате селекции и скрещивания, становится текущей для следующей (второй) итерации. Она характе­ризуется средним значением функции приспособленности, равным 173,8. Заметно, что это значение меньше, чем рассчитанное для пер­вого поколения. Наибольшее значение функции приспособленности, равное 723, имеет хромосома с фенотипом 19. Это наихудшая особь данной популяции. «Наилучшая к текущему моменту» хромосома с фенотипом, равным двум, имеет минимальное значение функции приспособленности, которое равно девяти.

В третьем поколении среднее значение функции приспособ­ленности уменьшается до 13. Наибольшее значение для хромосомы с фенотипом, равным трем, составляет 19, а наименьшее значение функции приспособленности для этой популяции, также, как и для предыдущей, равно девяти. «Наилучшей к текущему моменту» про­должает оставаться хромосома с фенотипом, равным двум

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

До этого момента алгоритм выполнялся аналогично классичес­кому генетическому алгоритму, причем селекция проводилась детер­минированным турнирным методом с сохранением наилучшей хро­мосомы из популяции (элитарная стратегия).

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

После селекции и скрещивания в очередном (девятом) поколе­нии получаем популяцию со средним значением функции приспособ­ленности, равным 481,4. Наибольшее значение функции приспособ­ленности, равное 1579, имеет хромосома с фенотипом 28, а наимень­шее значение, равное девяти, - с фенотипом, равным двум.

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

С пятнадцатого поколения начинается очередной (третий) цикл выполнения генетического микроалгоритма. Он также открывается случайным выбором четырех новых хромосом и формированием по­пуляции с сохранением «наилучшей к текущему моменту» особи с фенотипом, равным двум.

На девятнадцатой итерации генетического микроалгоритма, т.е. в пятом поколении третьего цикла (состоящего из семи итераций) возникает сходимость к оптимальному решению, которым оказывает­ся хромосома с фенотипом, равным 0. Среднее, наибольшее и наи­меньшее значения функции приспособленности по всей популяции с 19 по 21 поколение остается равным 1.

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

Конечно, задачу из примера 4.12 можно решить с применением генетического алгоритма с произвольной размерностью популяций, при задании пользователем значений вероятностей скрещивания и мутации, а также при выборе им одного из методов селекции (рулет­ки, турнирного или рангового). Таким образом, вместо микроалгорит­ма можно применить реализованный в программе FlexTool обычный генетический алгоритм (regular). Однако необходимо отметить, что при его использовании на популяциях малой размерности с вероятно­стями скрещивания и мутации, соответственно равными 1 и 0, а так­же при выполнении селекции методом рулетки (так, как в примере 4.5) весьма часто встает проблема преждевременной сходимости этого алгоритма. Результат значительно улучшается, если вероятность му­тации отличается от нуля (например, если она принимается равной 0,1). Несмотря на то, что мутация играет определенно второстепен­ную роль по отношению к скрещиванию, она оказывается необходи­мой, поскольку обеспечивает разнообразие хромосом в популяции.

		Глава 4. Генетиче	скив алгоритмы
Функция приспособленн (наилучшая) t	эсга
1,04
1.031.02 1.01 1.00
	\
	1 2 3	4 5 6 7 8 9 Ю	Поколения
Рис. 4.18.Наименьшее зна<-последовательных итерациях г	ение функции приспособленности энетического алгоритма для примера	в популяции на 4.13.

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

Следующий пример относится к задаче, похожей на задачу примера 4.12. Минимизируется та же функция, однако переменная х принимает действительные значения из интервала [-5, 5]. По этой причине пространство поиска оказывается большим, чем в примере 4.12. Для решения данной задачи применим обычный генетический алгоритм программы FlexTool и селекцию методом рулетки. Заметим, что этот метод, который пригоден и для селекции в случае максими­зации функции, в программе FlexTool может использоваться только для задач минимизации. Это обусловлено адаптацией программы к требованиям пользователей, которые чаще решают задачи миними­зации (например, погрешностей, затрат и т.п.), чем задачи максимиза­ции.

Пример 4.13

С помощью генетического алгоритма программы FlexTool най­ти минимум функции, заданной формулой (4.1) для х е [-5, 5] с точ­ностью до 0,1.

Поставленная задача решается путем использования обычного генетического алгоритма (regular) с селекцией методом рулетки. За­метим, что поиск проводится в пространстве, состоящем из 100 воз­можных решений. Длина хромосом (в соответствии с формулой 4.4)) должна быть равной семи. Пусть размерность популяции составляет 11 особей. Будем применять одноточечное скрещивание с вероятнос­тью 0,9, а вероятность мутации установим равной 0,1.

|

4.9. Примеры оптимизации функции с помощью программы FlexTool 175

Исходная популяция состоит из 11 хромосом длиной семь би­тов, соответствующих следующим фенотипам:

3,4 2,4 2,0 5,0 1.4 0.1 3,0 -2,3 2,3 5,0 -4,8

Наилучшее решение, т.е. хромосома с фенотипом, равным 0, для которой значение функции приспособленности составляет 1, по­лучено на седьмой итерации алгоритма. На первой итерации наи­большее значение функции приспособленности по всей популяции равно 51, среднее - 22,0745, а наименьшее - 1,02. Однако в седьмом поколении наибольшее значение функции приспособленности равно 45,18, среднее по популяции составляет 5,9909, а наименьшее значе­ние соответствует лучшей хромосоме и равно 1. График на рис. 4.18 показывает наименьшее значение функции приспособленности в по­пуляции на последовательных итерациях генетического алгоритма.

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

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

В программе FlexTool по умолчанию приняты следующие (наи­лучшие для большинства решаемых задач) значения параметров ге­нетического алгоритма:

- размерность популяции = 77,

- вероятность скрещивания = 0,77,

- вероятность мутации = 0,0077.

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

Пример 4.14

С помощью генетического алгоритма программы FlexTool най­ти минимум функции, заданной формулой

-6

Пх) =

(х - 0.3)² + 0,01""" (х - 0,9)² + 0,04

для х е [-1, 2] с точностью до 0,01.

График оптимизируемой функции представлен на рис. 4.19. Об­ратим внимание на то, что функция имеет не только глобальный мак­симум, но и локальные оптимумы. Для нахождения глобального мак­симума применяется генетический алгоритм с турнирной селекцией в подгруппах по две особи. Размерность популяции равна 21; вероят­ности скрещивания и мутации составляют, соответственно 0,77 и 0,0077; используется одна точка скрещивания.

Глава 4. Ге

алгоритмы

Хромосомы состоят из девяти генов со значениями 0 или 1. На рисунке 4.20 более светлой линией показана динамика изменения «наилучшего», в рассматриваемом случае - максимального значения функции приспособленности в популяции при увеличении количества поколений. Более темная линия на втором графике иллюстрирует из­менение «наихудшего» значения функции приспособленности в попу­ляции при последовательной смене поколений. На оси ординат обоих графиков указаны значения функции приспособленности (fitness value). На оси абсцисс второго графика указаны номера поколений, которые соответствуют числам на оси абсцисс первого графика, ум­ноженным на размерность популяции, т.е. на 21.

Из графиков видно, что «наилучшая» хромосома в первом и втором поколениях характеризуется значением функции приспособ­ленности, близким к 20. В то же время значение функции приспособ­ленности «наихудшей» хромосомы примерно равно -5. В четвертом поколении это значение приблизилось к -4, а значение функции при­способленности «наилучшей» хромосомы возросло до 70. В нижней правой части рис. 4.20 показаны значения параметра задачи, т.е. пе­ременной х со значениями в интервале от -1 до 2; другими словами, это фенотипы, соответствующие отдельным хромосомам рассматри­ваемой популяции. Заметно, что популяция характеризуется значи­тельным разнообразием. На рис. 4.21 популяция более однородна, а на рис. 4.22 зафиксировано только одно значение параметра, рав­ное 0,3; это означает, что все хромосомы в популяции равны между собой. В рассматриваемом примере мы имеем дело только с одним параметром задачи Р1, который совпадает с Р2, поэтому все точки располагаются вдоль прямой так, как это показано на рис. 4.20 и 4.21

Графики на рис. 4.21 демонстрируют увеличение «наилучше­го» значения функции приспособленности от около 47 в третьем по­колении до примерно 70 в четвертом и примерно 93 - в пятом поко­лении, а в седьмом поколении достигается значение, равное 96,5. Это максимальная величина, которая остается неизменной в следую­щих поколениях, что видно на рис. 4.22. Таким образом, на седьмой итерации алгоритма найдено «наилучшее» решение - хромосома со значением фенотипа, равным 0,3, для которого значение функции приспособленности составляет 96,5. Нижние графики на рис. 4.21 и 4.22 также показывают, как изменяется «наихудшее» значение функции приспособленности от 3 до 16 поколения. В шестнадцатом поколении это значение равно 92,81. Среднее значение функции при­способленности в популяциях очередных поколений изменяется от 2,24 на первой итерации алгоритма до 96,32 на шестнадцатой итера­ции, что показывает таблица 4.4.

Дата добавления: 2015-06-04