к оглавлению к алгоритмизации СУБД ЯиМП 3GL 4GL 5GL технологии прогр.

Понятие об эволюционных алгоритмах

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

Масштаб пригодности
Селекция
Опции репродуцирования
Мутация и кроссовер
Установка числа мутаций
Установка кроссоверной доли
Установка без Мутаций
Мутации без кроссовера
Сравнение результатов с фракциями
измененных после операции кроссовера
Пример - сравнение глобального и локального минимумов
Пример решения данной задачи с помощью Генетического алгоритма
Установка максимального числа поколений
Векторизация функции пригодности
Минимизация при наличии ограничений с использованием функции ga
Параметризация функций, вызываемых с помощью ga
Параметризация функций при помощи анонимных функциq для ga
Параметризация функции при помощи вложенной функции для ga

Приводится разъяснение условий установки опций для генетического алгоритма.

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

Масштаб пригодности

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

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

Принимаемая по умолчанию функция масштабирования значений пригодности, Rank, масштабирует необработанные множества на основе определенного ранга для каждого индивидуализированного объекта вместо значений этого множества. Рангом индивидуализированного объекта является его позиция в отсортированном множестве: ранг наибольшей пригодности индивидуализированного объекта равен 1, ранг следующей наибольшей пригодности равен 2 и так далее. Функция масштабирования ранга приписывает отмасштабированные значения таким образом, что бы:

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

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

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

Поскольку в данном алгоритме минимизируется функция пригодности, то менее обработанные значения множеств имеют более высокие отмасштабированные значения. А так же, поскольку операция вычисления ранга придает значения, которые зависят только от ранга индивидуализированного объекта, то отмасштабированные значения, как это показано, есть те же самые как для любого семейства размера 20, так и для числа родителей равного 32.

Сопоставление ранга и Масштабирования высшего уровня.

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

Далее на рисунке приведено сравнение отмасштабированных значений семейства размером 20 числом родителей 32 при использовании ранга и Масштабирования высшего уровня.

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

Селекция

Операция селекции предназначена для выбора родителей следующего поколения на основе отмасштабированных величин полученных после использования функция масштабирования значений пригодности. Каждый индивидуализированный объект может быть избран в качестве родительского два и более раз, в этом случае он привносит свои гены в два и более дочерних параметра. Принимаемая по умолчанию функция Stochastic uniform составляет некую линию, на которой каждый родитель соответствует некому отрезку этой линии с длиной, пропорциональной его отмасштабированному значению. Таким образом, алгоритм продвигается вдоль этой линии с шагами одного и того же размера. При этом, на каждом шаге алгоритм назначает родителя в соответствии с отрезком его расположения.

Более детерминированной функцией отбора является функция Remainder, которая выполняется в два этапа:

На первом этапе данная функция отбирает родителей детерминированным способом согласно целой части отмасштабированного значения для каждого индивидуализированного объекта. Например, если отмасштабированное значения индивидуализированного объекта равно 2,3, то функция отбора принимает этот индивидуализированный объект в качестве родительского дважды.
На втором этапе данная функция отбора подбирает дополнительных родителей на основе использования уже дробной части отмасштабированных значений в виде стохастического однородного отбора. Данная функция выделяет линию на отрезках, чьи длины являются пропорциональными дробной части отмасштабированного значения индивидуализированного объекта, и для выбора родительских значений движется вдоль этой линии с единым размером шага.
Отметим, что если все дробные части отмасштабированных значений равны нулю, как это имеет место в методе Масштабирования высшего уровня, то данная операция отбора полностью детерминированной.

Опции репродуцирования

Опции репродуцирования определяют способ формирования последующего поколения в Генетическом алгоритме. Имеются следующие опции:

Elite count - элитный номер, это число индивидуализированных объектов с наилучшей функцией пригодности для текущего поколения, которые гарантировано останутся неизменными для следующего поколения. Эти индивидуализированные объекты называются элитными дочерними объектами. Принимаемое по умолчанию значение Elite count равно 2.
В случае, когда значение величины Elite count равно 1, то наилучшее значение функции пригодности может только уменьшаться при переходе от одного поколения к следующему. Это как раз наиболее желательный случай, поскольку в Генетическом алгоритме происходит минимизация функции пригодности. Установка опции Elite count в виде большого числа заставляет наиболее приспособленные индивидуализированные объекты доминировать в семействе, что может снижать эффективность операции поиска.
Crossover fraction - доля индивидуализированных объектов в следующем поколении, отличном от элитного дочернего, и которое формируется в операции Кроссовера (перекрещивания). В разделе Установка кроссоверной доли приводится описание как значение опции Crossover fraction оказывает влияние на эффективность работы Генетического алгоритма.

Мутация и кроссовер

Индивидуализированные объекты используются в текущем поколении Генетического алгоритма в качестве дочерних объектов как основа для создания последующих поколений. Кроме элитных дочерних объектов, которые соответствуют индивидуализированным объектам текущего поколения с наилучшими значениями пригодности, данный алгоритм формирует:

Кроссоверные дочерние объекты путем отбора векторных элементов или генов из пары индивидуализированных объектов текущего поколения с их последующей комбинацией формированием дочерних объектов.
Мутационные дочерние объекты на основе использования стохастических операций для отдельно взятых индивидуальных объектах из текущего поколения и последующего формирования уже самих дочерних объектов.

Оба этих процесса представляют собой сущность Генетического алгоритма. Операция кроссовера позволяет данному алгоритму выделять наилучшие гены из индивидуумов различного типа и затем производить их рекомбинацию в дочерние объекты потенциально высшего качества. Мутация служит дополнением к диверсификации семейства и, таким образом, увеличивает вероятность, что в алгоритме сгенерируются индивидуальные объекты с наилучшими значениями пригодности. Без операции мутации в алгоритме могут воспроизводиться только индивидуализированные объекты с генами, являющимися простой комбинацией начального семейства.

Смотри раздел Создание следующего поколения как пример использования операций мутации и кроссовера в Генетическом алгоритме.

В алгоритме имеется возможность установить следующие опции для задания числа дочерних объектов каждого типа:

Значение Elite count в опции Reproduction устанавливает число элитных дочерних объектов.
Значение Crossover fraction в опции Reproduction устанавливает долю семейства, отличного от элитных дочерних объектов, которая является уже кроссоверными дочерними объектами.

Например, если значение величины Population size равно 20, значение величины Elite count равно 2 и значение величины Crossover fraction равно 0.8 то число дочерних объектов каждого типа будет следующим:

Число дочерних объектов 2.
Число объектов, отличных от дочерних будет 18 так, что алгоритм после операции округления 0.8*18 = 14.4 до 14 дает число кроссоверных детей.
Оставшиеся 4 индивидуализированных объекта, отличные от элитных дочерних объектов, составляют дочерние мутационные объекты.

Установка числа мутаций

Операция мутации осуществляется в Генетическом алгоритме на основе использования специальных установок поля Mutation function. Используемая по умолчанию функция Гауссовской мутации добавляет случайно выбранное с помощью распределения Гаусса число, mutation, к каждому элементу родительского вектора. Как правило, это число мутаций, которое пропорционально стандартному среднеквадратичному отклонению от распределения, уменьшается с каждой последующей итерацией. В алгоритме путем установки опций Scale и Shrink имеется возможность управлять усредненным числом мутаций для каждой итерации:

Опция Scale управляет стандартным среднеквадратичным отклонением на первой итерации, которое равно параметру Scale, умноженному на ранг исходного семейства, задаваемого с помощью опции Initial range.
Опция Shrink управляет скоростью уменьшения среднего числа мутаций. Стандартное среднеквадратичное отклонение линейно уменьшается до тех пор, пока его конечное значение будет равно 1 - Shrink от его начального значения для первого поколения. Например, если величина Shrink по умолчанию принимается равной 1, то тогда число мутаций уменьшается к конечному шагу до нуля.

Имеется возможность отследить влияние операции мутации с помощью установок для графических функций Distance и Range, с последующим выполнением Генетического алгоритма применительно к задаче, описанной в разделе Пример функции Растригана. Эта зависимость далее представлена на рисунке.

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

В качестве сравнения далее представлены графические зависимости для Distance и Range при установке параметра Shrink в 0.5.

При установке параметра Shrink в 0,5, среднее число мутаций уменьшается с коэффициентом ½ до достижения конечной итерации. Соответственно, среднее расстояние между индивидуализированными объектами уменьшается примерно с тем же коэффициентом.

Установка кроссоверной доли

Поле Crossover fraction опции Reproduction устанавливает долю объектов каждой семейства, в отличие от элитных дочерних объектов, которые составляют в итоге кроссоверные дочерние объекты. Кроссоверная доля равная 1 означает,что все дочерние объекты, в отличие от элитных индивидуумов, являются кроссоверными дочерними объектами, при этом кроссоверная доля равная 0 означает, что все дочерние объекты дочерними мутационными объектами. Приведенный далее пример показывает, что ни один из рассмотренных здесь экстремумов не представляет собой эффективную стратегию для оптимизации некой функции.

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

f(x₁,x₂,...,x_n)=|x₁|+|x₂|+...+|x_n|

Можно эту функцию задать и в виде анонимной функции, если в поле Fitness function внести следующую запись

@(x)sum(abs(x))

Для выполнения данного примера следует:

В поле Fitness function внести @(x)sum(abs(x)).
В поле Number of variables внести 10.
В поле Initial range внести [-1;1].
Выбрать параметры Best fitness и Distance на панели Plots.

В начале выполним пример с принимаемым по умолчанию значением 0,8 параметра Crossover fraction. После выполнения примера получим наилучшее значение функции пригодности примерно равное 0,2 и следующие типы графических зависимостей.

Установка без Мутаций

Для того, что проконтролировать работу Генетического алгоритма без включения операции мутации, следует установить параметр Crossover fraction в 1.0 и кликнуть мышкой на кнопку Start. В результате выполнения такой команды получим наилучшее значение функции пригодности примерно равное 1,3 и следующие типы графических зависимостей.

В данном случае в алгоритме производится отбор геномов из индивидуумов для начального семейства с последующей их рекомбинацией. Поскольку нет режима мутации, то алгоритм не может воспроизводить какие-либо новые геномы. В алгоритме генерируются наилучшие индивидуализированные объекты на основе возможного использования геномов с номером поколения, равным 8, когда график наилучшей пригодности достигает определенного уровня. После этого, формируются новые копии наилучших индивидуализированных объектов, которые далее выбираются для формирования новых поколений. К поколению с номером 17 уже все индивидуализированные объекты для данного семейства являются одними и теми же, а именно, наилучшими индивидуализированными объектами. В этом случае среднее расстояние между индивидуализированными объектами будет равно 0. Поскольку уже после поколения с номером 8 в данном алгоритме не может быть улучшено значение наилучшей пригодности, то алгоритм выходит на останов после 50 поколений, поскольку параметр Stall generations равен 50.

Мутации без кроссовера

Для того, что проконтролировать работу Генетического алгоритма без включения операции кроссовера, следует установить параметр Crossover fraction в 0 и кликнуть мышкой на кнопку Start. В результате выполнения такой команды получим наилучшее значение функции пригодности примерно равное 3,5 и следующие типы графических зависимостей.

В данном случае в результате стохастических операций в алгоритме не возникают какие-либо улучшения значений пригодности для наилучших индивидуализированных объектов первого поколения. Поскольку происходит улучшение геномов индивидуумов и для других индивидуализированных объектов, как это можно отследить из верхней графической зависимости по уменьшению среднего значения функции пригодности, то эти улучшенные геномы не участвуют в комбинациях с геномами наилучших индивидуализированных объектов вследствие отсутствия операции кроссовера. Как результат всего этого, график наилучшей пригодности выходит на некий уровень и алгоритм останавливается при числе генераций равном 50.

Сравнение результатов с фракциями измененных после операции кроссовера

С помощью включенной в данный тулбокс демонстрационной программы deterministicstudy.m имеется возможность провести сравнение результатов использования Генетического алгоритма для оптимизации функции Растригина с установками параметра Crossover fraction в 0, .2, .4, .6, .8 и 1. Демонстрационная программа выполняется для 10 поколений. Для каждого поколения в программе воспроизводится графическая зависимость средних и стандартных отклонений для значений наилучшей пригодности для всех предшествующих поколений и для каждого значения параметра Crossover fraction.

Для выполнения демонстрационной программы следует ввести команду

deterministicstudy

в командном окне MATLAB. По окончании демонстрационной программы отобразятся следующие графические зависимости.

На нижнем графике приведены средние величины и стандартные среднеквадратичные отклонения значений функции пригодности для 10 поколений применительно для каждого из значений кроссоверной функции. На верхнем графике представлена цветовая кодировка для значений наилучшей пригодности в каждом поколении.

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

Пример - сравнение глобального и локального минимумов

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

В качестве примера рассмотрим следующую функцию:

Далее на рисунке представлен график данной функции

Функция имеет два локальных минимум, один в точке x = 0, где значение функции равно - 1, и другой в точке = 21, где значение функции равно 1 - 1/e. Поскольку последнее значение является более меньшим, то глобальный минимум находится в точке = 21.

Пример решения данной задачи с помощью Генетического алгоритма

Для выполнения данного примера с помощью Генетического алгоритма следует выполнить следующие действия:

Скопировать и записать следующие коды в новый М-файл редактора MATLAB
```
function y = two_min(x)
if x<20
    y = -exp(-(x/20).^2);
else
    y = -exp(-1)+(x-20)*(x-22);
end
```
Записать файл под именем two_min.m in в рабочую директорию пространства MATLAB.
В инструментарии генетического алгоритма выполнить следующие действия.

Установить Fitness function в @two_min.
Установить Number of variables в 1
Кликнуть кнопку Start.

Генетический алгоритм возвратит точку очень близкую к локальному минимуму в точке x = 0.

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

Отметим, что все индивидуализированные объекты находятся в пределе от -2до 2.5. Поскольку этот диапазон больше принимаемого по умолчанию параметра Initial range [0;1], то вследствие принятого типа функции мутационных процессов, он не является достаточно большим, что бы обрабатывать точки вблизи глобального минимума в точке x = 21.

Один из способов заставить Генетический алгоритм обрабатывать точки из более широкого диапазона, т.е. расширить диверсификацию семейств, заключается в увеличении параметра Initial range. По свой сути параметр Initial range не должен включать в себя точку x = 21, но он должен быть достаточно большим, так что бы данный алгоритм генерировал индивидуализированные объекты вблизи 21. Установим параметр Initial range в [0;15], как это представлено на рисунке далее.

Затем кликнем мышкой кнопку Start. Генетический алгоритм возвратит точку очень близкую к 21.

К данному моменту времени на специализированном графике можно видеть много больший диапазон индивидуализированных объектов. Уже для второго поколения индивидуализированные объекты уже охватывает точку со значением 21 и к 12 поколению алгоритм определяет наилучший индивидуализированный объект, который примерно равен 21.

Использование гибридной функции

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

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

В качестве примера выбран поиск минимума функции Розенброка, определяемой как

Далее на рисунке представлен график функции Розенброка.

Для расчета данной функции в тулбоксе имеется М-файл dejong2fcn.m. С целью демонстрации примера выполним команду

hybriddemo

в окне команд пакета MATLAB.

С начала, для запуска данного примера откроем инструментарий Генетического алгоритма с помощью команды gatool и введем следующие установки:

установим в поле Fitness function @dejong2fcn.
установим в поле t Number of variables 2.
установим в поле Population size 10.

Перед введением гибридной функции постараемся выполнить Генетический алгоритм сам по себе при помощи кнопки Start. После выполнения Генетического алгоритма на панели Status and results можно будет увидеть следующие результаты.

Конечная точка расчетов близка к точке истинного минимума (1, 1). Имеется возможность улучшить результаты расчета путем установки в опции Hybrid function требуемой гибридной функции fminunc.

По окончании выполнения Генетического алгоритма функция fminunc воспринимает конечную точку Генетического алгоритма в качестве исходной и возвращает более точный результат, как это представлено далее на панели Status and results.

Установка максимального числа поколений

Опция Generations в разделе Stopping criteria определяет максимальное число итераций при выполнении функции Генетического алгоритма, более подробно смотри раздел Условия останова алгоритма. Увеличение параметра Generations, как правило, приводит к улучшению конечного результата.

В качестве примера изменим установки инструментария Генетического алгоритма следующим образом:

установим в поле Fitness function @rastriginsfcn.
установим в поле Number of variables 10.
выберемt Best fitness на панели Plots.
установим в поле Generations Inf.
установим в поле Stall generations Inf.
установим в поле Stall time Inf.

Затем выполним Генетический алгоритм примерно на 300 итераций и кликнем на кнопку Stop. Далее на рисунке представлена зависимость для итогового значения параметра Best fitness после 300 итераций.

Отметим, что алгоритм практически прекращается примерно после выполнения примерно 170 поколений - то есть, нет заметного улучшения в функции пригодности после 170 поколений. Если восстановить параметр Stall generations в его принимаемое по умолчанию значение равное 50, то алгоритм остановится на числе поколений примерно равном 230. Если происходит постоянный останов Генетического алгоритма с текущим значением параметра Generations, то имеется возможность улучшить итоговые результаты путем увеличения обоих параметров Generations и Stall generations. Хотя, конечно, не исключена возможность более эффективного улучшения работы алгоритма с помощью изменения других опций.

Примечание. Если параметр Mutation function установить как Gaussian, то увеличение значения параметра Generations действительно может привести к ухудшению конечного результата. Это обстоятельство можно объяснить тем, что Гауссова функция мутации снижает среднее количество мутаций для каждого поколения на некий коэффициент, величина которого зависит от параметра Generations. Следовательно, установка параметра Generations оказывает влияние на эффективность работы алгоритма.

Векторизация функции пригодности

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

Записать М-файл расчета искомой функции таким образом, что бы он был представлен в виде матрицы с произвольным числом строк, которые соответствовали бы индивидуализированным объектам данного поколения. Например, для векторизации функции

Запишем М-файл в виде следующих кодов:

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

Колонка первого элемента переменной х указывает на строчные элементы от х, так что x(:, 1) есть вектор. Операторы .^ и .* указывают на поэлементные операции с данными векторами

Установить опцию Vectorize как On.

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

С помощью следующего сравнения, выполненного из командной строки, можно увидеть эффект увеличения скорости выполнения, достигаемого с помощью установки опции Vectorize.

tic;ga(@rastriginsfcn,20);toc

elapsed_time =

    4.3660

options=gaoptimset('Vectorize','on');

tic;ga(@rastriginsfcn,20,options);toc

elapsed_time =

    0.5810

Установка максимального числа поколений

Опция Generationsв разделе Stopping criteria определяет максимальное число итераций при выполнении функции Генетического алгоритма, более подробно смотри раздел Условия останова алгоритма. Увеличение параметра Generations, как правило, приводит к улучшению конечного результата.

В качестве примера изменим установки инструментария Генетического алгоритма следующим образом:

установим в поле Fitness function @rastriginsfcn.
установим в поле Number of variables 10.
выберем Best fitness на панели Plots.
установим в поле Generations Inf.
установим в поле Stall generations Inf.
установим в поле Stall time Inf

Примечание. Если параметр Mutation function установить как Gaussian, то увеличение значения параметра Generations действительно может привести к ухудшению конечного результата. Это обстоятельство можно объяснить тем, что Гауссова функция мутации снижает среднее количество мутаций для каждого поколения на некий коэффициент, величина которого зависит от параметра Generations. Следовательно, установка параметра Generations оказывает влияние на эффективность работы алгоритма.

Векторизация функции пригодности

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

Запишем М-файл в виде следующих кодов:

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

Колонка первого элемента переменной х указывает на строчные элементы от х, так что x (:, 1) есть вектор. Операторы .^ и .* указывают на поэлементные операции с данными векторами.

Установить опцию Vectorize как On.

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

tic;ga(@rastriginsfcn,20);toc

elapsed_time =

    4.3660

options=gaoptimset('Vectorize','on');

tic;ga(@rastriginsfcn,20,options);toc

elapsed_time =

    0.5810

Минимизация при наличии ограничений с использованием функции ga

Пусть необходимо найти минимум простой функции пригодности с двумя переменными x1 and x2

При условии выполнения следующих нелинейных неравенств и ограничений

Начнем с создания функций пригодности и ограничений. В первую очередь, создадим следующий М-файл под именем simple_fitness.m

function y = simple_fitness(x)
y = 100 * (x(1)^2 - x(2)) ^2 + (1 - x(1))^2;

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

Далее создадим следующий М-файл под именем simple_fitness.m, который включал бы в себя вводимые в задачу ограничения

function [c, ceq] = simple_constraint(x)
c = [1.5 + x(1)*x(2) + x(1) - x(2);
-x(1)*x(2) + 10];
ceq = [];

Предполагается, что функция ga имеет функцию ограничений с одним входом x, где x имеет столько же элементов, что и число переменных решаемой задачи. В функции ограничений вычисляются значения всех ограничений типа равенств и неравенств и возвращаются два вектора, ceq и c, соответственно.

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

ObjectiveFunction = @simple_fitness;
nvars = 2;    % Number of variables
LB = [0 0];   % Lower bound
UB = [1 13];  % Upper bound
ConstraintFunction = @simple_constraint;
[x,fval] = ga(ObjectiveFunction,nvars,[],[],[],[],LB,UB,ConstraintFunction)
Warning: 'mutationgaussian' mutation function is for unconstrained minimization only; 
using @mutationadaptfeasible mutation function.
Set @mutationadaptfeasible as MutationFcn options using GAOPTIMSET.

Optimization terminated: current tolerance on f(x) 1e-007 is less than options.TolFun
 and constraint violation is less than options.TolCon.

x =

    0.8122   12.3122

fval =

  1.3578e+004

Примечание для задачи минимизации при наличии ограничений функция ga изменила мутационную функцию на новую @mutationadaptfeasible. Принимаемая по умолчанию функция мутации @mutationgaussian подходит только для задач минимизации без наличия ограничений

Решатель Генетического алгоритма обращается с линейными ограничениями и границами несколько отличным образом по сравнению со случаем с нелинейными ограничениями. Все линейные ограничения и границы выполняются по всему ходу оптимизации. Однако функция ga применительно к части поколений может и не соблюдать все необходимые нелинейные ограничения. Как только ga будет сходиться к некоему решению, то и нелинейные ограничения будут выполняться в этом случае.

Функция ga использует функции мутации и кроссовера в каждом поколении для новых индивидуализированных объектов. Функция ga выполняет все линейные и связанные ограничения при помощи функций мутации и кроссовера, которые генерируют только допустимые точки. Например, в предыдущем обращении к команде ga, принимаемая по умолчанию функция мутации mutationguassian не соблюдает линейные ограничения и, таким образом, вместо нее используется функция мутации mutationadaptfeasible. Если принимать произвольную функцию мутации, то эта произвольная функция мутации должна генерировать только такие точки, которые являются допустимыми относительно линейных ограничений и пределов. Все кроссоверные функции данного инструментария генерируют такие точки, которые удовлетворяют линейным ограничениям и пределам за исключением случая с выбором функции crossoverheuristic.

С помощью функции gaoptimset зададим mutationadaptfeasible в качестве функции мутации для выбранной задачи минимизации

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

Далее запустим решатель ga.

[x,fval] = ga(ObjectiveFunction,nvars,[],[],[],[],LB,UB,ConstraintFunction,options)

Optimization terminated: current tolerance on f(x) 1e-007 is less than options.TolFun
 and constraint violation is less than options.TolCon.

x =

    0.8122   12.3122

fval =

  1.3578e+004

Теперь с помощью функции gaoptimset построим структуру опций, которая будет отбирать функции для двух графических зависимостей. Первой функцией графической зависимости будет gaplotbestf, которая отображает наилучшую и среднюю оценку семества для каждого поколения. Второй функцией графической зависимости будет gaplotmaxconstr, которая отображает максимальное нарушение заданного ограничения в виде нелинейных ограничений для каждого поколения. Так же имеется возможность с помощью опции 'Display' получить визуализацию прогресса алгоритма путем отображения информации в окне команд.

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

Перезапустим решатель ga, что даст:

[x,fval] = ga(ObjectiveFunction,nvars,[],[],[],[],LB,UB,ConstraintFunction,options)
                           Best       max        Stall
Generation  f-count        f(x)     constraint  Generations
    1         849       14915.8            0      0
    2        1567       13578.3            0      0
    3        2334       13578.3            0      1
    4        3043       13578.3            0      2
    5        3752       13578.3            0      3
Optimization terminated: current tolerance on f(x) 1e-009 is less than options.TolFun
 and constraint violation is less than options.TolCon.

x =

    0.8122   12.3123


fval =

  1.3578e+004

Имеется возможность с помощью опции InitialPopulation задать стартовую точку минимизации для функции ga. Таким образом, функция ga будет использовать индивидуализированный объект из опции InitialPopulation в качестве стартовой точки минимизации при наличии ограничений.

X0 = [0.5 0.5]; % Start point (row vector)
options = gaoptimset(options,'InitialPopulation',X0);
Далее перезапустим решатель ga. 
[x,fval] = ga(ObjectiveFunction,nvars,[],[],[],[],LB,UB,ConstraintFunction,options)
                           Best       max        Stall
Generation  f-count        f(x)     constraint  Generations
    1         965       13579.6            0      0
    2        1728       13578.2   1.776e-015      0
    3        2422       13578.2            0      0
Optimization terminated: current tolerance on f(x) 1e-007 is less than options.TolFun
 and constraint violation is less than options.TolCon.
x =

    0.8122   12.3122

fval =

  1.3578e+004

Параметризация функций, вызываемых с помощью ga

Иногда может быть необходимым записывать вызываемые с помощью команды ga функции с учетом дополнительных параметров к независимой переменной. Например, предположим, что необходимо минимизировать следующую функцию:

Для различных значений a, b, и c. Поскольку команда ga воспринимает функцию пригодности только как зависимую от х функцию, то необходимо до обращения к команде ga определить параметры a, b и c. Далее приводится детальное описание двух подходов к решению этой проблемы:

Параметризация функций при помощи анонимных функциq для ga
Параметризация функции при помощи вложенной функции для ga

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

Параметризация функций при помощи анонимных функциq для ga

Для параметризации функции сначала запишем М-файл со следующими кодами:

function y = parameterfun(x,a,b,c)
y = (a - b*x(1)^2 + x(1)^4/3)*x(1)^2 + x(1)*x(2) + ...
         (-c + c*x(2)^2)*x(2)^2;

Сохраним М-файл в рабочей директории MATLAB под именем parameterfun.m

Пусть необходимо минимизировать данную функцию со следующими значениями параметров a = 4, b =2.1, и c = 4. Для этих целей определим посредством ввода в окне команд MATLAB так называемый функциональный указатель для анонимной функции.

a = 4; b = 2.1; c = 4;    % Define parameter values
fitfun = @(x) parameterfun(x,a,b,c);
NVARS = 3;

При использовании инструментария Генетического алгоритма,

Установить параметр Fitness function в fitfun.

Установить параметр Number of variables в NVARS.

a = 3.6; b = 2.4; c = 5;    % Define parameter values
fitfun = @(x) parameterfun(x,a,b,c);

Параметризация функции при помощи вложенной функции для ga

В качестве альтернативы методу параметризации при помощи анонимной функции можно использовать и обычный М-файл, составленный следующим образом:

Принять a, b, c и NVARS в качестве входных параметров.
Составить функцию пригодности в виде вложенной функции.
Запустить команду ga.

Составим следующий М-файл.

function [x fval] =  runga(a,b,c,NVARS)
[x, fval] = ga(@nestedfun,NVARS);
% Вложенная функция для расчета функции пригодности
   function y = nestedfun(x)
        y = (a - b*x(1)^2 + x(1)^4/3)*x(1)^2 + x(1)*x(2) + ...
         (-c + c*x(2)^2)*x(2)^2;
    end
end

Отметим, что функция пригодности рассчитывается во вложенной функции nestedfun, которая уже имеет обращение к переменным a, b и c. Для выполнения задачи оптимизации следует выполнить команду

 [x fval] = runga(a,b,c,NVARS)

После выполнения команды получим

Optimization terminated: average change in the fitness value less than options.TolFun.

x =

   -0.1302    0.7170    0.2272

fval =

   -1.0254

к оглавлению к алгоритмизации СУБД ЯиМП 3GL 4GL 5GL технологии прогр.

Знаете ли Вы, что спецификация - это документ, описывающий соглашение между разработчиками и пользователями. Разработчик берется написать модуль, а пользователь соглашается не полагаться на знания о том, как именно этот модуль реализован, т.е. не предполагать ничего такого, что не было бы указано в спецификации. Такое соглашение позволяет разделить анализ реализации от собственно использования программы. Спецификации дают возможность создавать логические основы, позволяющие успешно "разделять и властвовать".

НОВОСТИ ФОРУМА

Рыцари теории эфира