РК6-93.АОРС.ПугачёвАВ
.docxМосковский государственный технический университет имени Н.Э. Баумана
РЕФЕРАТ
по курсу
«Методы оптимизации»
на тему:
«Алгоритм оптимизации роем светлячков»
Выполнил: Пугачёв А.В.
группа РК6-93
Проверил: Карпенко А.П.
Москва, 2014
Оглавление
Введение ................................................................................................................... 3
-
Краткие сведения ............................................................................................... 4
-
Постановка задачи ............................................................................................. 5
-
Алгоритм динамического симплекса ................................................................ 6
-
Описание алгоритма ..................................................................................... 6
-
Выбор параметров в динамическом симплекс-методе ............................... 8
-
Примеры ........................................................................................................ 8
-
Двухмерная задача динамической непрерывной оптимизации ........... 8
-
Трехмерная задача динамической непрерывной оптимизации.......... 10
-
-
Вывод о модификации................................................................................ 11
-
Заключение ............................................................................................................. 12
Список литературы ................................................................................................ 13
Введение
Для решения динамических задач оптимизации на сегодняшний день разработано множество алгоритмов.
В реферате осуществлен обзор статьи, посвященной динамическим задачам непрерывной оптимизации. В разделе 1 дано описание используемых в статье терминов [1], в разделе 2 приведена постановка задачи [1], в разделе 3 изложено описание алгоритма (модификация симплекс-метода Нелдера-Мида)
[1] и примеры его применения.
-
Краткие сведения
Алгоритм оптимизации роем светлячков (GSO -GLOWWORM SWARM OPTIMIZATION ALGORITHM) предложили в 2005 г. Кришнананд (K.N. Krishnanand) и Гхоус ( D. Ghose).
Динамические задачи оптимизации (DOPs – Dynamic Optimization Problems) — задачи, где технические характеристики (часто известные в оптимизации как фитнес-функции) изменяются с течением времени в процессе оптимизации, что приводит к непрерывному движению оптимума.
Целевая функция — математическое выражение некоторого критерия качества одного объекта (решения, процесса и т.д.) в сравнении с другим. Требуется найти такие оценки, в которых целевая функция достигнет минимума.
Задачи непрерывной оптимизации — задачи, в которых целевая функция и ограничения непрерывно зависят от переменных.
-
Постановка задачи
Общая нелинейная изменяющаяся во времени система и ее целевая функция имеет вид
, (1) (2) где f и g являются нелинейными функциями, х – входные процессы, - изменяющийся во времени вектор параметров, у – выходные процессы, - шум, J является целевой функцией, которая должна быть сведена к минимумуf[1].
В режиме моделирования новое значение у рассчитывается путем оценки функции f. В режиме реального времени у получают в виде измерения. Значение функции и измерение взаимозаменяемы в статье [1]. Каждое измерение y занимает некоторый конечный промежуток времени. Таким образом, проблема, с которой мы сталкиваемся, состоит в том, чтобы оптимизировать функцию y, используя как можно меньше оценок (измерений) функции.
-
Алгоритм динамического симплекса
Алгоритм динамического симплекса (Dynamic simplex), разработанный авторами статьи [1], основан на симплекс-методе Нелдера-Мида. Данный алгоритм позволяет отслеживать движущийся оптимум.
3.1 Описание алгоритма
Состояние светлячка , i ϵ [1: |S|], определяют следующие переменные:
Xi – его текущие положение в пространстве поиска
li – уровень светимости (luciferin level)
ri – радиус окрестности (neighborhood range)
Основным содержанием каждой итерации является обновление значений указанных переменных.
Уровень светимости светлячка si обновляем по формуле:
liʹ=(1-ρ) li +γφ (Xi), i ϵ [1: |S|],
где ρ, γ –положительные свободные параметры алгоритма, моделирующие распад флуоресцирующего вещества и привлекательность светлячка. Отличные от нуля значения параметра ρ обеспечивают алгоритм памятью. Параметр γ определяет относительные веса текущей светимости агента и значения его фитнесс-функции.
Светлячок sj считается соседом светлячка :
i, j ϵ [1: |S|], i ≠ j
при выполнении двух следующих условий:
-
евклидово расстояние между этими светлячками не превышает текущий радиус окрестности ri
-
текущий уровень светимости светлячка sj превышает этот уровень светлячка , т.е. lj > li.
Если светлячок имеет несколько соседей, то случайным образом выбирает одного из них с вероятностью, пропорциональной уровням их светимости (правило рулетки).
Положим, что по рассмотренной схеме светлячком выбран . Тогда новое положение светлячка определяет формула:
где - постоянное значение шага(свободный параметр алгоритма).
Новый радиус окрестности светлячка si определяем в соответствии с выражением:
где – текущее множество соседей светлячка , -минимально допустимый радиус окрестности, -желательное число соседей, - положительная константа. Последние три величины являются свободными параметрами алгоритма.
Модификации.
Рассмотрим некоторые модификации представленного канонического алгоритма GSO.
Для диверсификации поиска в случае, когда число соседей светлячка , в окрестности менее желательного числа n, радиус окрестности может быть по тому или иному правилу расширен (в простейшем случае, положим, на 5%).
В той же ситуации возможно иное решение – случайное перемещение светлячка в переделах куба с центром в точке и длиной ребра, равное шагу :
Если значение фитнесс функции в новой точке лучше ее значения в точке , то оставляем светлячка в точке .
Новый радиус окрестности светлячка может вычисляться не по формуле
а по формуле вида
где - максимальное значение этой величины, – заданная константа, – средняя текущая плотность агентов в окрестности :
Величины , представляют собой свободные параметры алгоритма.
Наиболее сложной является модификация алгоритма GSO, использующая специальный механизм организации агентов в группы. В каждой из групп в этом случае выделяют одного из агентов в качестве ее владельца (master), который определяет миграцию всех подчиненных (slave) агентов. В исходном состоянии подчиненные агенты равномерно распределены случайным образом в гиперсфере радиуса с центром, совпадающим с начальным положением владельца группы. В процессе поиска величина может варьироваться в диапазоне, где - свободный параметр.