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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Селекция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

@(x)sum(abs(x))

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

В начале выполним пример с принимаемым по умолчанию значением 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.

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

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

  1. Скопировать и записать следующие коды в новый М-файл редактора MATLAB

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

Генетический алгоритм возвратит точку очень близкую к локальному минимуму в точке 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 и введем следующие установки:

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

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

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

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

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

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