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

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

В эволюционных стратегиях целью является движение особей популяции по направлению к лучшей области ландшафта фитнесс-функции. ЭС изначально разработаны для решения многомерных оптимизационных задач, где пространство поиска – многомерное пространство вещественных чисел [1]. Иногда при решении задачи накладываются некоторые ограничения, например, вида $$g_i(x)>0$$.

Ранние эволюционные стратегии (ЭС) основывались на популяции, состоящей из одной особи, и в них использовался только один генетический оператор – мутация. Здесь для представления особи (потенциального решения) была использована идея, не представленная в классическом генетическом алгоритме, которая заключается в следующем.

Здесь особь представляется парой действительных векторов

$$v=(\bar x,\overline\sigma),$$

где $$\overline x$$- точка в пространстве решений и $$\overline\sigma$$- вектор стандартных отклонений (вариабельность) от решения. В общем случае особь популяции определяется вектором потенциального решения и вектором "стратегических параметров" эволюции. Обычно это вектор стандартных отклонений (дисперсия), хотя допускаются (и иногда используются) и другие статистики.

Единственным генетическим оператором в классической ЭС [1] является оператор мутации, который выполняется путем сложения координат вектора-родителя со случайными числами, подчиняющимися закону нормального распределения, следующим образом:

$$\overline x^{t+1}=\overline x^t+N(o,\overline\sigma),$$

где $$N(o,\overline\sigma)$$- вектор независимых случайных чисел, генерируемых согласно распределению Гаусса (например, табличным способом) с нулевым средним значением и стандартным отклонением $$\sigma$$. Как видно из приведенной формулы величина мутации управляется нетрадиционным способом. Иногда эволюционный процесс используется для изменения и самих стратегических параметров $$\sigma$$, в этом случае величина мутации эволюционирует вместе с искомым потенциальным решением. Это соответствует адаптивному ГА с изменяемым шагом мутации.

Интуитивно ясно, что увеличение отклонения подобно увеличению шага поиска на поверхности ландшафта. Высокая вариабельность способствует расширению пространства поиска и эффективна при нахождении потенциальных зон (суб)оптимальных решений и соответствует высоким значениям коэффициента мутации. В тоже время малые значения вариабельности позволяют сфокусироваться на поиске решения в перспективной области. В данном случае стратегические параметры стохастически определяют величину шага поиска: большая вариабельность ведет к большим шагам. Отметим, что поскольку отклонения генерируются стохастически (по нормальному закону), то большая вариабельность может давать маленький шаг и наоборот. Известно, что 68,26% случайных чисел при нормальном распределении попадают в интервал, определяемый стандартным отклонением $$\sigma$$; 95% чисел попадают в интервал 1,96 $$\sigma$$ и т.д.

9.1. Двукратная эволюционная (1+1)- стратегия

Здесь потомок принимается в качестве нового члена популяции (он заменяет своего родителя), если значение фитнесс функции (ЦФ) на нем лучше, чем у его родителя и выполняются все ограничения. Иначе, (если значение фитнесс-функции на нем хуже, чем у родителей), потомок уничтожается и популяция остается неизменной.

Рассмотрим выполнение оператора мутации на конкретном примере следующей функции [2]

$$f(x_1,x_2)=21,5+x_1\cdot\sin(4\pi x_1)+x_2\cdot\sin(20\pi x_2)\\-3.0\le x_1\le 12.1\quad\overline x=(x_1,x_2)\\4.1\le x_2\le 5.8\quad\overline\sigma=(\sigma_1,\sigma_2)$$

в предположении поиска максимума.

Для определенности предположим, что в $$t$$-поколении текущая особь имеет вид:

$$(\overline x^t,\sigma)=((5.3;4.9),(1.0;1.0)).$$

Тогда потомок определяется следующим образом:

$$\left\begin{aligned}x_1^{t+1}=x_1^t+N(0;1.0)=5.3+0.4=5.7\\x_2^{t+1}=x_2^t+N(0;1.0)=4.9-0.3=4.6\\\end{aligned}\right\}\mbox{потомок},$$

где числа 0.4 и 0.3 получены случайным образом в соответствии с распределением Гаусса.

Поскольку $$f(x^t)=f(5.3;4.9)=18.383705<24.849532=f(5.7;4.6)=f(x^{t+1})$$ (значение ЦФ потомка лучше, чем у родителя), то полученный потомок заменяет родителя.

В целом алгоритм процесса эволюции двукратной (1+1)- эволюционной стратегии можно сформулировать следующим образом.

Выбрать множество $$P$$ параметров $$X$$, необходимых для представления решения данной проблемы, и определить диапазон допустимых изменений каждого параметра:$$\{x_{1\min},x_{1\max}\},\{x_{2min},x_{2\max}\},\dots,\{x_{P\min},x_{P\max}\},$$

установить номер поколения (итерации) $$t=0$$; задать стандартное отклонение $$\sigma_i$$ для каждого параметра, функцию $$f$$, для которой необходимо найти оптимум, и максимальное число поколений $$k$$.

Для каждого параметра случайным образом выбрать начальное значение из допустимого диапазона: множество этих значений составляет начальную популяцию (из одной особи) $$X^t=(x_1,x_2,\dots,x_P)$$.

Вычислить значение оптимизируемой функции $$f$$ для родительской особи $$F^p=f(X^t)$$.

Создать новую особь-потомка в соответствии с (9.2) $$\overline x^*=\overline x^t+N(0,\overline\sigma)$$

Вычислить значение $$f$$ для особи-потомка $$F^0=f(X^*)$$.

Сравнить значения функций $$f$$ для родителя и потомка; если значение потомка $$F^0$$ лучше, чем у родительской особи, то заменить родителя на потомка $$\overline x^t=\overline x^*$$, иначе оставить в популяции родителя.

Увеличить номер поколения $$t=t+1$$;

Если не достигнуто максимальное число поколений $$t<k$$, то переход на шаг 4, иначе выдать найденное решение $$X^t$$.

Несмотря на то, что фактически здесь популяция состоит из одной особи, рассмотренная стратегия называется двукратной ЭС. Причина в том, что здесь фактически происходит конкуренция потомка и родителя. Обычно вектор стандартных отклонений $$\sigma$$ остается неизменным в течении всего процесса эволюции. Если все его компоненты одинаковы и оптимизационная задача регулярна, то можно доказать следующую теорему сходимости [1,2].

Теорема. Для $$\sigma>0$$ и регулярной оптимизационной задачи с $$f_{opt}>-\infty$$ (минимизация), либо $$f_{opt}>+\infty$$(максимизация), имеет место равенство

$$P\{\lim_{t\to\infty}f(\overline x^t)=f_{opt}\}1$$

Эта теорема утверждает, что оптимальное решение регулярной оптимизационной задачи находится с вероятностью, равной единице при $$t\to\infty$$, но при этом совершенно ничего не говорится о том, как и каким образом двигаться к этому оптимальному решению. Поэтому, чтобы оптимизировать скорость сходимости этого процесса, И. Решенберг [1] (основоположник ЭС) предложил правило успеха "1/5".

Смысл его заключается в следующем - правило применяется после каждых $$k$$ поколений процесса (где $$k$$ – параметр этого метода):

$$\sigma^{t+1}=\begin{cases}c_d\cdot\sigma^t,\text{если $\phi(k)<1/5$}\\c_i\cdot\sigma^t,\text{если $\phi(k)>1/5$}\\\sigma^t,\text{если $\phi(k)=1/5$}\end{cases}$$

где $$\phi(k)$$- отношение числа успешных мутаций к общему числу произведенных мутаций $$k$$(число успехов, деленное на $$k$$), которое называется коэффициентом успеха для оператора мутации в течении $$k$$ последних поколений; величина $$c_i>1,c_d<1$$ – регулирует увеличение/уменьшение отклонения мутации.

Обычно на практике оптимальные значения полагают равными следующим величинам: $$c_d=0.82; c_i=1/0.82=1.22.$$. Смысл этого правила в следующем:

если коэффициент успеха $$\phi(k)>1/5$$, то отклонение $$\sigma^{t+1}$$ увеличивается (мы идем более крупными шагами);

если коэффициент успеха $$\phi(k)<1/5$$, то отклонение $$\sigma^{t+1}$$ уменьшается (шаг поиска уменьшается).

Идеи И.Решенберга получили дальнейшее развитие в концепции "эволюция окна" [3] при которой результат применения оператора мутации принимается только в том случае, если он лежит в пределах некоторой окрестности (окна) родительской особи в пространстве решений. Динамическое изменение шага мутации в сочетании с эволюцией величины окна ведет к метаэволюции [3].

Иногда рекомендуется устанавливать коэффициент мутации обратно пропорционально числу переменных в потенциальном решении (особи) и прямо пропорционально расстоянию от точки оптимального решения. Конечно, в реальных приложениях точное расположение оптимума неизвестно. Однако иногда может быть известна априорная информация об оптимуме (например, порядок величины). Даже ограниченная информация может быть полезна в процессе поиска в ЭС.

9.2. Многократная эволюционная стратегия

По сравнению с двукратной многократная эволюция отличается не только размером популяции $$(N > 2)$$, но и имеет некоторые дополнительные отличия:

все особи в поколении имеют одинаковую вероятность выбора для мутации;

имеется возможность введения оператора рекомбинации (например, однородного ОК в ГА, рассмотренного в разделе 4), где два случайно выбранных родителя производят потомка по следующей схеме:$$(\overline x^1,\overline\sigma^1)=((x_1^1,\dots,x_n^1),(\sigma_1^1,\dots,\sigma_n^1))\\\underbrace{(\overline x^2,\overline\sigma^2)=((x_1^2,\dots,x_n^2),(\sigma_1^2,\dots,\sigma_n^2))}_{\mbox{$\overline x,\overline\sigma)=((x_1^{q_1},\dots,x_n^{q_n}),(\sigma_1^{q_1},\dots,\sigma_n^{q_n}))$}}$$ где $$q_i=1$$ или $$q_i=2$$, $$i=1,\dots,n$$ (т.е. каждая компонента потомка копируется из первого или второго родителя).

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

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

$$(1+1)$$-ЭС - двукратная стратегия (1 родитель производит 1 потомка);

$$(\mu+1)$$-ЭС - многократная стратегия ($$\mu$$ родителей производят 1 потомка);

$$(\mu+\lambda)$$-ЭС, где $$\mu$$-родителей производят $$\lambda$$-потомков и отбор $$\mu$$ лучших представителей производится среди объединенного множества ($$(\mu+\lambda)$$ особей) родителей и потомков;

$$(\mu,\lambda)$$-ЭС, где $$\mu$$ особей родителей порождает $$\lambda$$ потомков, причем $$\lambda>\mu$$ и процесс выбора лучших производится только на множестве потомков.

Следует подчеркнуть, что в обоих последних видах ЭС обычно число потомков существенно больше числа родителей $$\lambda>\mu$$(иногда полагают $$\lambda/\mu=7$$).

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

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

9.3. Основные параметры и самоадаптация

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

В первых реализациях ЭС применялся только один вид параметра – отклонение в распределении Гаусса, которое используется в операторе мутации. В этом случае, как показано в разделе 9.1, $$i$$–я особь определяется как $$v=(\overline x_i,\overline\sigma_i)$$, где $$\overline x_i\in R^{n_x}$$ представляет генотип и $$\overline\sigma_i$$- вектор-параметр отклонений (обычно $$\overline\sigma_i\in R^{n_x}$$ и все компоненты отклонения одинаковы $$\sigma_{ij}=\sigma_i$$ для $$j=1,2,\dots,n_x$$). Применение большего числа параметров дает больше степеней свободы особям и лучшие возможности для регулирования распределения мутации.

Если в качестве параметров используются только отклонения, то лучшие направления поиска определяются вдоль осей системы координат пространства поиска. Но не всегда лучшее направление поиска совпадает с осями. В таких случаях необходима дополнительная информация для ускорения процесса сходимости. Такую информацию можно получить из матрицы $$H$$– гессиана фитнесс-функции. Если гессиан используется в качестве параметра, то мутация определяется следующим образом:

$$x_i(t)=x_i(t)+N(0,H^{-1}).$$

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

В [4] предложено использовать матрицу ковариации $$C^{-1}$$, которая определяется отклонениями параметров особи и может использоваться в качестве дополнительной информации, позволяющей определить оптимальный размер шага и направление поиска. В этом случае $$x_i(t)=x_i(t)+N(0,C)$$, где $$N(0,C)$$ обозначает нормальное распределение вектора $$к$$ с нулевым математическим ожиданием и плотностью вероятностей $$f_G(r)=\frac{det\ C}{(2\pi)_x^n}e^{-\frac{1}{2}r^rCr}$$.

Здесь диагональные элементы $$C^{-1}$$ - вариации $$\sigma_j^2$$, а не- диагональные элементы – ковариации величин шагов мутации. При этом ковариации определяются углами вращения, которые необходимо произвести, чтобы преобразовать некоррелированный вектор мутации в коррелированный вектор. Если $$\omega_i(t)$$ означает угол вращения вектора для $$i$$-ой особи, то особь представляется триплетом $$x_i(t)=(x_i(t),\sigma_i(t),\omega_i(t))$$, где

$$x_i(t)\in R^{n_x},\sigma_i(t)\in R_+^{n_x},\omega_i(t)\in R^{n_x(n_x-1)/2},\mbox{и}\\\omega_{ik}(t)\in(0,2\pi],k=1,\dots,n_x(n_x-1/2)$$

Углы вращения используются при представлении ковариаций для $$n_x$$ генетических переменных генетического вектора $$x_i$$. Поскольку ковариационная матрица симметрична, можно использовать вектор для представления углов вместо матрицы. Углы вращения можно использовать для вычисления ортогональной матрицы вращения $$T(\omega_i)$$ следующим образом:

$$T(\omega_i)=\prod_{i=1}^{n_x-1}\prod_{j=i+1}^{n_x}R_{ij}(\omega_i),$$

которая является произведением $$n_x(n_x-1)/2$$ матриц вращения. Каждая матрица вращения $$R_{ij}(\omega_i)$$ является единичной матрицей с $$r_u=\cos(\omega_{ik})$$ и $$r_{lj}=-r_{jl}=-\sin(\omega_{ik})$$, с $$k=1\Leftrightarrow(l=1,j=2),k=2\Leftrightarrow(l=1,j=3),\dots$$.

Построенная матрица вращения используется в операторе мутации.

Итак, в ЭС используются два вида параметров: 1) стандартные отклонения величины шага мутации; 2) углы вращения, которые представляются ковариациями размера шага мутации. Пусть $$n_{\sigma}$$ обозначает число используемых параметров отклонений и $$n_{\omega}$$- число углов вращения. На практике имеют место, в основном, следующие типовые ситуации:

$$n_{\sigma}=1,n_{\omega}=0$$, т.е. используется только один параметр отклонения $$((\sigma_j=\sigma\in R_+,j=1,j=2),k=2\Leftrightarrow(l=1,j=3),\dots.)$$, одинаковый для всех компонент генотипа нулевые углы вращения. При этом распределение вероятностей имеет круглую форму, что показано на рис.9.1а. Середина окружности определяет позицию родительской особи $$x_i$$, в то время как $$\sigma$$ указывает на отклонение величины шага.

Отметим, что это распределение фактически показывает вероятность позиции потомка $$x'_i$$, имеющей наиболее высокую вероятность в центре. Тогда параметр регулируется следующим образом - $$\sigma_i^t=\sigma_i(t)e^{\tau N(0,1)}$$, где $$\tau=\frac{1}{\sqrt{n_z}}$$. При этом регулирование одного параметра выполняется быстро, но подход является не гибким в том случае, когда координаты имеют различные градиенты.

(рис 9.1) Иллюстрация распределений вероятностей мутации.

$$n_{\sigma}=n_x,n_{\omega}=0$$, где каждая компонента имеет свой собственный параметр отклонения. В этом случае распределение мутации имеет эллиптическую форму, как показано на рис.9.1b, где $$\sigma_1<\sigma_2$$. Тогда увеличение числа параметров вызывает линейное увеличение вычислительной сложности, но дополнительные степени свободы обеспечивают большую гибкость. При этом могут учитываться различные значения градиентов по разным осям. Значения параметров корректируются в соответствии со следующими формулами:$$\sigma_1{ij}(t)=\sigma_{ij}(t)e^{\tau'N(0,1)+\tau N_j(0,1)},\mbox{где }\tau^t=\frac{1}{\sqrt{2n_x}}\ and\ \tau=\frac{1}{\sqrt{2\sqrt{n_x}}}$$

$$n_{\sigma}=n_x,n_{\omega}=n_x(n_x-1)/2$$, где в качестве параметров кроме отклонений (девиаций) используются также углы вращения. В этом случае эллиптическое распределение мутации вращается относительно осей координат как показано на рис.9.1с. Эти вращения позволяют найти лучшую аппроксимацию контуров в пространстве поиска. Тогда параметры отклонений корректируются в соответствии с предыдущей формулой (9.11), а значения углов по нижеприведенной формуле $$\omega_{ik}^t(t)=\omega_{ik}(t)+\gamma N_j(0,1)\mod 2\pi,\mbox{где }\gamma\approx 0.0873$$. Расширение параметров путем ввода углов вращения повышает гибкость, но вычислительная сложность при этом растет квадратично.

$$1<n_{\sigma}<n_x$$, где допускается еще больше степеней свободы. Для всех $$j>n_{\sigma}$$ используется отклонение $$\sigma_{n_{\sigma}}$$.

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

В работе [5] предложен метод адаптации параметров на основе "обучения с подкреплением", в котором параметры корректируются следующим образом:

$$\sigma_{ij}^t(t)=\sigma_{ij}(t)e^{\theta_i(t)|\tau^tN(0,1)+\tau N_j(0,1)}$$

где $$\theta_i(t)$$- сумма временных поощрений за последние $$n_{\theta}$$ поколений для $$i$$-ой особи, то есть

$$\theta_i(t)=\frac{1}{n_{\theta}}\sum_{t'=0}^{n_{\theta}}\theta_i(t-t').$$

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

$$\theta_i(t)=\left\{\begin{array}\ 0.5\mbox{ если }\Delta f(x_i(t))>0\\0\mbox{ если }\Delta f(x_i(t))=0\\-1\mbox{ если }\Delta f(x_i(t))<0\end{array}\right\},$$

где ухудшение значений фитнесс-функции сурово штрафуется. Здесь $$\Delta f(x_i(t))=f(x_i(t))-f(x_i(t-1))$$.

В работе [6] использовались поощрения +1, 0 или -1 в зависимости от полученных характеристик. Кроме этого, в этой же работе предложено применять:

$$\theta_{ij}(t)=f(x_i(t))-f(x_i(t-\Delta t)),\mbox{с }0<\Delta t<t$$ Этот подход определения поощрения основан на учете изменений на уровне фенотипа, поскольку определяется фитнесс-функцией. При этом чем больше особь улучшает значение фитнесс-функции, тем она получает большее поощрение. С другой стороны, худшее значение фитнесс-функции особи ведет к увеличению штрафа для этой особи

$$\theta_{ij}(t)=sign(f(x_i(t))-f(x_i(t-\Delta t)))$$. Эта схема дает значения поощрений +1, 0 или -1.

$$\theta_{ij}(t)=\|x_i(t)-x_i(t-\Delta t)\|sign(f(x_i(t))-f(x_i(t-\Delta t)))$$.

Здесь поощрение пропорционально размеру шага в пространстве решений.

В [7] рассматривается схема самоадаптации, где $$n_{\sigma}=1$$ и применяется ковариационная матрица. В этой схеме отклонение потомка определяется как функция отклонений производящих его родителей. Здесь для каждого потомка $$x'_1(t),l=1,\dots,\lambda$$

$$\sigma'_l(t)=\sqrt[p]{\prod_{i\in\Omega_i(t)}\sigma_i(t)e^{\xi}},$$

где $$\Omega_i(t)$$- индекс множества $$\rho$$ родителей потомка $$x'_1(t)$$ и распределение $$\xi$$ такое, что $$prob(\xi=0.4)=prob(\xi=-0.4)=0.5$$. В разделе 9.4 (оператор мутации) показано, как эта схема самоадаптации может быть использована в операторе мутации.

В работе [8] применяется схема самоадаптации, где $$1<n_{\sigma}<n_x$$ и каждая особь использует различное количество параметров отклонений $$n_{\sigma i}(t)$$. На каждой итерации $$t$$ число параметров отклонений может быть увеличено или уменьшено с вероятностью 0.05. Если число параметров отклонений увеличивается, то новый параметр отклонения инициализируется следующим образом:

$$\sigma_{i n_{\sigma,i}(t)}(t)=\frac{1}{n_{\sigma,i}(t-1)}\sum_{k=1}^{n_{\sigma,i}(t-1)}\sigma_{ik}(t).$$

9.4. Генетические операторы ЭС

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

9.4.1 Операторы отбора

В ЭС отбор особей используется для: 1) выбора родителей, которые принимают участие в рекомбинации; 2) для формирования популяции следующего поколения. Для отбора $$\rho$$ родителей оператора кроссинговера может быть использован любой из методов, рассмотренных в разделе 3.3. Часто родительские особи выбираются случайно.

В каждом поколении $$\lambda$$ потомков генерируются из $$\mu$$ родителей и подвергаются мутации. После кроссинговера и мутации отбираются особи в следующее поколение. При этом применяются две основные стратегии:

$$(\mu+\lambda)$$-ЭС, где из $$\mu$$ родителей генерируется $$\lambda$$ потомков $$(1\le\mu\le\lambda<\infty)$$ и отбор $$\mu$$ лучших особей в следующее поколение (обычно с применением элитизма) производится среди объединенного множества ( $$(\mu+\lambda)$$ особей) родителей и потомков;

$$(\mu,\lambda)$$-ЭС, где $$\mu$$ -особей родителей порождает $$\lambda$$-потомков, причем $$\mu>\lambda$$ и процесс выбора лучших производится только на множестве потомков.

Учитывая приведенные нотации, иногда используется $$(\mu^+,\lambda)$$-ЭС обозначение. В некоторых случаях нотация $$(\mu+\lambda)$$-ЭС расширяется до $$(\mu,k,\lambda)$$, где $$k$$ обозначает максимальную продолжительность жизни особи. Если число поколений превышает этот предел, то особь не может отбираться в следующее поколение. Заметим, что $$(\mu,\lambda)$$-ЭС эквивалентна $$(\mu,1,\lambda)$$-ЭС. Выбор лучшей стратегии зависит от решаемой задачи.

9.4.2. Операторы кроссинговера

В классической (1+1)-ЭС используется только оператор мутации. В последующих модификациях, начиная с ($$\mu$$+1)-ЭС допускается применение операторов кроссинговера. При этом оператор может применяться как на уровне генотипа (векторов вещественных чисел), так и параметров и реализуется способом, отличным от других парадигм ЭВ. Реализация отличается по возможному числу родителей, участвующих в рекомбинации и по способу комбинации генетического материала и значений параметров. В общем случае нотация $$(\mu/\rho,^+,\lambda)$$ используется для указания того, что $$\rho$$ родителей используется при реализации оператора кроссинговера. На основе значений этих родительских особей потомки генерируются путем применения:

локального кроссинговера $$\rho=2$$, где один потомок производится из двух случайно взятых родителей;

глобального кроссинговера $$2<\rho\le\mu$$, где более чем два родителя используются для генерации потомка. Чем больше значение $$\rho$$, тем больше возможное разнообразие у получаемых потомков.

Поэтому глобальный кроссинговер улучшает эксплутационные свойства ЭС.

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

Дискретная рекомбинация, значения родительских особей используются для получения значений генов потомков, как описано в разделе 3.3. Для каждой компоненты потомка берется компонента одного из родителей (как описано в разделе 3.3). Нотация $$(\mu/\rho_D,^+\lambda)$$ используется для обозначения дискретной рекомбинации.

Промежуточная рекомбинация, где значение особи-потомка получается путем взвешенной арифметической суммы родительских особей (как описано в разделе 3.3). Нотация $$(\mu/\rho_I,^+\lambda)$$ используется для обозначения промежуточной рекомбинации.

На основе приведенных выше типов рекомбинации в ЭС разработаны и применяются следующие основные пять видов рекомбинации:

Нет рекомбинации: Если $$X_i(t)$$- родительская особь, то она переходит в следующее поколение в качестве потомка $$\tilde X_i=X_i(t)$$.

Локальная дискретная рекомбинация, где $$\overline x_{lj}(t)=\left\{\begin{array}{}x_{i_1j}(t)\mbox{ если $U_j(0,1)\le 0.5$}\\x_{i_2j}(t)\mbox{ иначе}\end{array}\right\}$$ и $$U_j(0,1)$$- случайное число в диапазоне (0,1).Здесь потомок $$\overline x_{l}(t)=(\overline x_{l}(t),\overline\sigma_l(t),\overline\omega_l(t))$$ наследует свойства обоих родителей $$x_{i_1}(t)=(x_{i_1}(t),\sigma_{i_1}(t),\omega_{i_2}(t))$$ и $$x_{i_2}(t)=(x_{i_2}(t),\sigma_{i_2}(t),\omega_{i_2}(t))$$

Локальная промежуточная рекомбинация, где $$\overline x_{lj}(t)=rx_{ij}(t)+(1-r)x_{ij}(t),\forall j=1,\dots,n_z$$ и $$\overline\sigma_{lj}(t)=r\sigma_{ij}(t)+(1-r)\sigma_{ij}(t),\forall j=1,\dots,n_z$$ с $$r\sim U(0,1)$$.Если используются углы вращения, то $$\omega_{lj}=[rx_{i_1k}(t)+(1-r)\sigma_{i_2k}(t)]\mod 2\pi,\forall k=1,\dots,n_x(n_x-1)$$.

Глобальная дискретная рекомбинация, где $$\overline x_{lj}(t)=\left\{\begin{array}{}x_{i_1j}(t)\mbox{ если $U_j(0,1)\le 0.5$}\\x_{r_jj}(t)\mbox{ иначе}\end{array}\right\}$$ с $$r_j\sim\Omega_l$$, где $$\Omega_l$$ множество индексов $$\rho$$ родителей, отобранных для выполнения кроссинговера.

Глобальная промежуточная рекомбинация походит на локальную промежуточную рекомбинацию за исключением того, что индекс $$i_2$$ заменяется на $$r_j\sim\Omega_l$$. Есть альтернативный вариант этого оператора, когда потомок вычисляется на основе средних значений родителей $$\overline x_l(t)=(\frac{1}{p}\sum_{i=1}^p x_i(t),\frac{1}{p}\sum_{i=1}^p\sigma_i(t),\frac{1}{p}\sum_{i=1}^p\omega_i(t))$$.

В [9] предложена арифметическая рекомбинация между лучшей и средней по всем родителям особью: $$\overline x_l(t)=r\hat{y}(t)+(1-r)\frac{1}{p}\sum_{i\in\Omega_i}^p x_i(t)$$, где $$\hat{y}(t)$$- лучшая особь текущей популяции. Этот подход применим и к построению значений параметров ЭС. Данная стратегия ведет к тому, что потомок располагается в окрестности лучшей особи.

9.4.3. Операторы мутации

После выполнения оператора кроссинговера полученные потомки с вероятностью $$p_m=1$$ подвергаются мутации. Оператор мутации выполняется в два шага для каждого потомка следующим образом:

На первом шаге производится самоадаптация параметров одним из методов, изложенных ранее.

На втором шаге выполняется собственно мутация $$x'_l(t)=\overline x_l(t)+\Delta x_l(t)$$.

При этом $$\lambda$$ мутируемых потомков $$x'_{l}(t)=(x'_{l}(t),\overline\sigma_l(t),\overline\omega_l(t))$$ принимают участие в процессе отбора (наравне со своими родителями) в зависимости от того, какая стратегия - $$(\mu+\lambda)$$-ЭС или $$(\mu,\lambda)$$-ЭС используется. В данном разделе рассматривается только мутация значений генотипа, поскольку мутация и самоадаптация параметров изложены ранее.

Если в качестве параметров используются только отклонения, генотип $$\tilde x_l(t)$$ каждого потомка мутирует в соответствии с правилами:

Если $$n_{\sigma}=1,\Delta x_{lj}(t)=\sigma_l(t)N_j(0,1),\forall j=1,\dots,n_x$$

Если $$n_{\sigma}=n_x,\Delta x_{lj}(t)=\sigma_{lj}(t)N_j(0,1),\forall j=1,\dots,n_x$$

Если $$1<n_{\sigma}<n_x,\Delta x_{lj}(t)=\sigma_{lj}(t)N_j(0,1),\forall j=1,\dots,n_{\sigma}\ and\ \Delta x_{lj}(t)=\sigma_{ln_{\sigma}}(t)N_j(0,1),\forall j=n_{\sigma}+1,\dots,n_x$$

Если, кроме этого, используются и углы вращения, то в предположении $$n_{\sigma}=,n_x$$ приращение вычисляется согласно выражению

$$\Delta x_l(t)=T(\overline\omega_l(t))S(\overline\sigma_l(t))N(0,1),$$

где $$T(\tilde\omega(t))$$- ортогональная матрица вращения

$$T(\overline\omega_l(t))=\prod_{a=1}^{n_z-1}\prod_{b=a+1}^{n_z}R_{ab}(\overline\omega_l(t)),$$

которая является произведением $$n_x(n_x-1)/2$$ матриц вращения. Каждая матрица вращения $$R_{ab}(\overline\omega_l(t))$$- единичная матрица, где элементы определяются следующим образом: $$r=\cos(\tilde\omega_{lk}),r_{ab}=-r_{ab}=-sin(\tilde\omega_{lk})$$ для $$k=1,\dots,n_x(n_x-1)/2$$ и $$k=1\Leftrightarrow(a=1,b=2),\ k=2\Leftrightarrow(a=1,b=3),\dots S(\tilde\sigma_l(t))-diagn(\tilde\sigma_{l1}(t),\tilde\sigma_{l}(t),\dots,\tilde\sigma_{ln_x}(t))$$ - диагональная матрица, представляющая отклонения.

В работе [10] предложена направленная мутация, где предпочтение отдается некоторому направлению в пространстве поиска. Как показано нарис.9.2, она основана на асимметричном вероятностном распределении мутации. Здесь размер шага по оси $$x_2$$ больше, чем по оси $$x_1$$ и отдается предпочтение положительным направлениям.

(рис 9.2) Направленная мутация в ЭС.

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

$$f_D(x)=\left\{\begin{array}{cl}\frac{2}{\sqrt{\pi\sigma}(1+\sqrt{1+c}}(e^{-\frac{z^2}{\sigma}})\mbox{если $x<0$}\\\frac{2}{\sqrt{\pi\sigma}(1+\sqrt{1+c}}(e^{-\frac{z^2}{\sigma(1+c)}})\mbox{если $x\ge 0$}\\\end{array}\right\}$$

где $$c>0$$ положительно определенная величина.

Метод направленной мутации использует только параметры отклонений, но ассоциирует с каждым отклонением $$\sigma_j$$ значение $$c_j$$, определяющее направление. Для обеих величин $$\sigma$$ и $$c$$ возможна само-адаптация, что дает $$2n_x$$ параметров. С вычислительной точки зрения это более эффективно, чем использование вектора вращения размерности $$n_x(n_x-1)/2$$ и дает больше информации о предпочтительном направлении и размере шага.

Если $$D(c,\sigma)$$ означает асимметричное распределение, то $$\Delta x_{ij}(t)=D_j(c_{ij}(t),\sigma_{ij}(t))$$

В работе [7] предложен инвариантный в системе координат оператор мутации с самоадаптацией, где генотип мутирует, используя значения отклонений и корреляций следующим образом:

$$x'_l(t)=\frac{1}{p}\sum_{i\in\Omega_l(t)} x_i(t)+\overline\sigma_l N(0,C_l(t)).$$

9.5. Сравнение эволюционной стратегии и генетических алгоритмов

Эволюционные стратегии применяются, в основном, в численной оптимизации, так как они были (по крайней мере, первоначально) посвящены функциональным задачам оптимизации в вещественной области. ЭС позволяет эффективно решать многие задачи стандартной и сложной нелинейной оптимизации с ограничениями (и без них) [11,12].

Они являются примерами эволюционных программ, которые используют соответствующие структуры данных (вещественные векторы, расширенные параметрами стратегии управления) и "генетические" операторы, ориентированные на решение определенных задач.

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

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

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

Первое различие между ЭС и ГА - это форма представления решений. ЭС использует вектор вещественных чисел, ГА – двоичный.

Второе различие между ГА и ЭС скрыто в процедуре выбора. В ЭС $$\mu$$-особей родителей порождают промежуточную популяцию, которая состоит из $$\lambda$$-потомков, путем оператора мутации и репродукции. На промежуточной популяции выполняется процедура отбора, которая сокращает эту популяцию обычно до исходной. В простейшем случае оставляются $$\mu$$ лучших особей – решение (причем все они разные).

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

Третье различие заключается в относительном порядке выполнения процедур отбора и рекомбинации. В ЭС процедура отбора выполняется после выполнения оператора репродукции. В ГА наоборот, ОР работает перед ОК и ОМ.

Следующее различие в том, что в классическом ГА параметры операторов рекомбинации обычно остаются постоянными (вероятность ОМ, ОК), а в ЭС параметры $$\overline\sigma$$ изменяются.

ЭС и ГА по разному учитывают ограничения: в ЭС есть множество неравенств $$g_1(\overline x)\ge 0,\dots,g_q(\overline x)\ge 0$$, которое рассматривается как часть оптимизационной задачи. В ГА ограничения обычно учитываются в виде штрафных функций, т.е. в неявном виде.

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

Контрольные вопросы

Как представляется потенциальное решение в ЭС?

Какой генетический оператор применяется в ЭС?

Как выполняется мутация в ЭС?

Опишите двукратную ЭС.

Сформулируйте правило успеха в ЭС.

Что такое двукратная ЭС?

Что такое многократная ЭС?

Приведите основные параметры ЭС.

Что такое самоадаптация в ЭС?

Какие параметры, кроме отклонений, можно использовать в ЭС?

Как можно использовать углы вращения в ЭС?

Приведите основные стратегии самоадаптации.

Приведите основные типы операторов отбора в ЭС.

Что такое локальный и глобальный оператор кроссинговера?

Какие операторы рекомбинации могут быть использованы в ЭС?

Сформулируйте общий алгоритм решения задачи с использованием ЭС.

Как выполняется оператор мутации в ЭС?

Что такое направленная мутация?

Что общего между ГА и ЭС?

Каковы различия между ГА и ЭС?

Зачем и как вводится третья компонента для представления решения в ЭС?

Краткие итоги:

изложены основы эволюционной стратегии, которая использует эволюцию на уровне фенотипа;

описано представление потенциальных решений в виде векторов действительных чисел;

изложены различные генетические операторы мутации и рекомбинации и отбора, которые применяются в ЭС;

представлена двукратная и многократные ЭС в зависимости от числа особей в популяции;

описаны параметры метода, значение которых определяет эффективность ЭС;

введены элементы самоадаптации ЭС, где значения параметров подстраиваются в процессе эволюции;

рассмотрены различия и сходства ЭС и ГА.