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

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

Реферат

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

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

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

группа РК6-91

Москва 2013

Аннотация

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

Содержание

• 1. Постановка задачи
• 2. Эволюционная стратегия
• 3. Базовый метод эволюционной стратегии
• 4. Самоадаптивный метод эволюционной стратегии
• 5. Метод C-центроидов с использованием эволюционной стратегии
• Список использованных источников


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

3) DE/rand-to-best/1:

4) DE/best/2:

5) DE/rand/2:

Здесь

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

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

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

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

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

j = 1, …, N. (3)

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

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

(4)

· DE/rand/2/bin:

· DE/current-to-rand/1:

.

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

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

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

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

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

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

5) После 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-центроидов с использованием эволюционной стратегии

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

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.

3. 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.

4. 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.