Эволюционная стратегия

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

Московский государственный технический университет имени Н.Э. Баумана (МГТУ им. Н.Э. Баумана)

Факультет «Робототехника и комплексная автоматизация» (РК)

Кафедра Системы автоматизированного проектирования (РК-6)

Реферат

по дисциплине: Методы оптимизации

Эволюционная стратегия

Выполнил: Гавин М.В.

группа РК6-91

Москва 2013

Аннотация

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

Содержание

1. Постановка задачи

. Эволюционная стратегия

. Базовый метод эволюционной стратегии

. Самоадаптивный метод эволюционной стратегии

. Метод C-центроидов с использованием эволюционной стратегии

Список использованных источников

1. Постановка задачи

Решается задача глобальной оптимизации

,

,

где - минимизируемая (целевая) функция,

- N-мерное пространство,

- N-мерный вектор,

ограничение снизу,

ограничение сверху,

- оптимальное значение вектора,

- множество допустимых значений вектора.

2. Эволюционная стратегия

Эволюционная стратегия - эвристический метод оптимизации в разделе эволюционных алгоритмов, основанный на адаптации и эволюции. Метод разработан в 1964 году немецким ученым Инго Рехенбергом и развит в дальнейшем Хансом Полом Швефелом и другими.

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

3. Базовый метод эволюционной стратегии

Алгоритм направлен на улучшение популяции NP параметрических векторов , где. Каждый вектор - кандидат в решение. Здесь NP - численность популяции (рекомендуется выбирать между 5N и 10N), G - номер поколения.

При выборе начальной популяции нужно учитывать ограничения на размер векторов . Например, начальное значение j-ого параметра i-ого вектора в начальном поколении (G=0) получается по формуле

j = 1,…, N. (1)

Здесь - число, полученное из нормального случайного распределения в промежутке [0, 1].

Операция мутации. После инициализации используем операцию получения вектора мутации.

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

1)DE/rand/1:

. (2)

2)DE/best/1:

)DE/rand-to-best/1:

)DE/best/2:

)DE/rand/2:

Здесь

- лучший вектор текущего поколения (оптимальное решение текущего поколения),

-i-ый вектор мутации текущего поколения,

- вектор, номер которого определяется случайным целым числом в интервале [1:NP] без повторений, где l ,

F - масштабирующий фактор (положительное число, масштабирующее разность векторов, оптимальный промежуток.

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

j = 1, …, N. (3)

Здесь - коэффициент скрещивания (постоянная, заданная пользователем в диапазоне [0, 1); чем больше , тем быстрее сходимость), - случайно выбранное целое число в диапазоне [1: N].

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

(4)

4. Самоадаптивный метод эволюционной стратегии

эволюционный стратегия вектор центроид

Базовый метод находит решение путем проб и ошибок. Это требует больших вычислительных затрат. Рассмотрим самоадаптивный метод эволюционной стратегии, в котором значения параметров управления NP, CR, F пробного вектора будут самостоятельно адаптироваться на основании предыдущих вычислений.

Пробный вектор адаптации [2]. Вместо использования поиска путем проб и ошибок предварительно введем набор стратегий, в состав которого войдут несколько пробных векторов с разными параметрами управления.

·DE/rand/1/bin:

·DE/rand-to-best/2/bin:

·DE/rand/2/bin:

·DE/current-to-rand/1:

.

Здесь случайные j-ые компоненты i-ого вектора без повторений (l , K - число стратегий в наборе.

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

1)Формируем набор из K стратегий.

2)Согласно вероятности 1/K выбираем одну из стратегий и применяем ее по отношению к каждому вектору (кандидату в решение).

)Каждое успешное применение занесем в память , неудачное - в память . Условие успешного применения: .

)Повторяем пункты 2, 3 в течение LP поколений. Здесь LP - число поколений обучения.

)После LP поколений, то есть когда GLP, вероятность пересчитывается по формуле

Здесь k = 1, 2, …, K,

LP - число обучающих поколений, в течение которых накапливается информация об успешных стратегиях,

- вероятность выбора k-ой стратегии поколения G,

небольшое постоянное значения (используется во избежание нулевой вероятности, можно принять равной 0,01).

Адаптация параметров. В методе эволюционной стратегии выбор численных значений для трех параметров управления F, CR, NP зависит от рассматриваемой задачи. В самоадаптивном методе пользователю предлагается самостоятельно выбрать параметр NP. Выбор параметра CR зависит от наличия унимодальности функции, от параметра F зависит скорость сходимости. Обычно F задается нормальным распределением N(0,5; 0,3), где 0,5 среднее значение, 0,3 стандартное отклонение. Таким образом, набор значений F выбирается случайно из этого нормального распределения. Но успешные значения параметров управления попадают в небольшой диапазон. Поэтому мы решили регулировать на каждом шаге значения этих параметров, и на основании опыта предыдущих шагов получать успешные значения для текущего поколения.

Будем считать, что CR задано следующим нормальным распределением N(0,5; 0,1). Здесь 0,5 - среднее значение параметра CR (CRm), 0,1 - стандартное отклонение (Std). Нормальное распределение N(0,5; 0,1) гарантирует, что большинство значений параметров управления будет находиться в промежутке [0, 1].

Исходя из случайного нормального распределения N(0,5; 0,1), получаем новое значение CRm. Наиболее успешный параметр CRm заносим в CRm-память. В CRm-памяти храним среднее арифметическое всех успешных значений параметра CRm.

5. Метод C-центроидов с использованием эволюционной стратегии

Метод C-центроидов - популярный метод кластеризации. Кластеризация - разбиение N-мерного пространства на кластеры (зоны). Каждому кластеру соответствует свой центроид. Число кластеров равно числу центроидов C, которое мы задаем сами.

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

.

Здесь - центроид, с = 1,.., С.

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

) Из множества NP векторов выбираем C центроидов. Выборка центроидов может быть как случайной, так и производиться по определенному алгоритму.

) Входим в цикл, который продолжается до тех пор, пока центроиды не перестанут изменять свои компоненты.

.1) Перебираем каждый вектор и определяем, к какому из центроидов он является близлежащим.

.2) После определения своего близлежащего центроида, вектор попадает в кластер этого центроида.

.3) После того как перебрали все векторы, изменяем компоненты всех центроидов последовательно по формулам (1) - (4).

.4) Теперь проверяем компоненты новых центроидов. Если они совпадают с компонентами уже установленных центроидов - выходим из цикла, если нет, то возвращаемся к пункту 2.1.

Список использованных источников

1.Qin A.K., Huang V.L. Suganthan P.N. Differential Evolution Algorithm With Strategy Adaptation for Global Numerical Optimization\\ IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, ? VOL. 13, ? NO. 2, APRIL 2009, ? pp. 399-401.

2.Qin A.K., Huang V.L. Suganthan P.N. Differential Evolution Algorithm With Strategy Adaptation for Global Numerical Optimization\\ IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, ? VOL. 13, ? NO. 2, APRIL 2009, ? pp. 401-403.

.Tae Seong Kim, Joong Chae Na and Kyung Joong Kim. Optimization of an Autonomous Car Controller using a Self-Adaptive Evolutionary Strategy\\ 14 Int J Adv Robotic Sy, ? 2012, ? Vol. 9, 73: 2012, ? pp.7-8.

.Merzougui M., Nasri M., Bouali B. Entropic Approach and Evolution Strategies for Optimizing the Image Segmentation by Pixel Classification: Application to Quality Control\\ International Journal of Computer Applications (0975 - 8887) Volume 61- No.13, January 2013, ? pp. 22-23.