Эволюционное программирование

10.1. Основные аспекты эволюционного программирования

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

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

Инициализировать популяцию, номер поколения $$k=1$$.

Подвергнуть популяцию влиянию окружающей среды.

Вычислить значение фитнесс-функции для каждой особи.

Выполнить оператор мутации для каждой особи популяции.

Оценить каждую особь (родителя и потомка).

Выбрать особи популяции следующего поколения.

Если не выполнено условие останова ($$k<k_{\max}$$ и т.п.), то переход на шаг 2, иначе выдать полученное решение.

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

ЭП отличается от других эволюционных алгоритмов в следующих аспектах:

ЭП основано на поведенческих моделях и использует эволюцию на уровне фенотипа.

В ЭП не применяется оператор рекомбинации, поскольку здесь нет обмена генетическим материалом.

Для оценки характеристик особи ЭП использует значение фитнесс-функции относительно случайно выбранной группы особей

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

Потомки и родители на равных борются за выживание.

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

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

10.2. Конечный автомат в качестве генома

Итак, в классическом ЭП особь представляется в виде конечного автомата. В определенном смысле конечные автоматы являются подмножеством машин Тьюринга, которые являются базовой моделью в теории вычислительной сложности. На машине Тьюринга можно имитировать машину Поста, нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. Конечные автоматы, конечно, не обладают такой "вычислительной мощностью", но они также способны решать достаточно сложные задачи.

Напомним, что конечный автомат является совокупностью шести объектов $$A=(Y,X,Z,\delta,\lambda,y_0),$$, где $$Y, X, Z$$ - конечные множества состояний, входных и выходных сигналов соответственно; $$\delta:Y\times X\to Y$$- функция переходов, определяющая следующее состояние автомата; $$\lambda:Y\times X\to Z$$- функция выхода, определяющая выходной сигнал, $$y_0$$ – начальное состояние. Обычно автомат представляется таблицей или графом переходов-выходов.

Например, табл.10.1 представляет конечный автомат [1] с входным алфавитом из двух символов $$\{0,1\}$$, выходным алфавитом $$\{\alpha,\beta,\gamma\}$$ и тремя состояниями $$(A,B,C)$$. Здесь на пересечении строки (текущего состояния) и столбца (входного сигнала) приводятся следующее состояние и выходной сигнал автомата.

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

Y	X
	0	1
A	$$B,\beta$$	$$A,\beta$$
B	$$B,\gamma$$	$$C,\alpha$$
C	$$B,\beta$$	$$A,\gamma$$

(рис 10.1) Граф переходов-выходов

Очевидно, автомат на входную последовательность (в зависимости от текущего состояния) выдает некоторую выходную последовательность. Например, если автомат табл.10.1 находится в состоянии $$A$$, и на его вход поступает последовательность 0, 1, 1 , то он выдает выходную последовательность $$\beta,\alpha,\gamma$$. При этом входная последовательность моделирует воздействие окружающей среды, а выходная последовательность – реакцию на это воздействие. Таким образом, рассматриваются последовательности событий, которые отмечаются символами $$x_1,x_2,\dots,x_n$$, и алгоритм должен прогнозировать следующее событие $$x_{n+1}$$ на основе известных предыдущих $$n$$ символов (событий). Цель эволюции состоит в поиске особи, которая позволяет в каком-то смысле наилучшим образом решать данную проблему.

Таким образом, множество потенциальных решений составляет популяцию конечных автоматов. Как правило, автоматы имеют относительно небольшое число состояний. В процессе эволюции применяется оператор мутации (кроссинговер здесь не используется). Обычно используются пять возможных операторов мутации: изменение выходного сигнала (для данного перехода), изменение следующего состояния в переходе, изменение начального состояния, добавление одного состояния, удаление одного состояния. Вид операторов мутации выбирается случайным образом в соответствии с некоторым распределением вероятностей. При этом возможно применение не одного, а нескольких операторов мутации. Например, на рис.10.2 показан результат мутации автомата рис.10.1, где изменен выходной сигнал перехода из состояния $$C\stackrel{0/\beta}{\longrightarrow}B$$ на $$C\stackrel{0/\alpha}{\longrightarrow}B$$.

(рис 10.2) Автомат-мутант

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

Рассмотрим особенности выполнения основных этапов алгоритма эволюции в эволюционном программировании.

Инициализация. Начальная популяция состоит из m автоматов $$A_i=(Y_i,X_i,Z_i,\delta_i,\lambda_i,y_{0i}),i\in\{1,2,\dots,m\} ,$$ которые генерируются случайным образом. Число состояний в автоматах $$N_i=|Y_{i_i}|$$ выбирается также случайным образом с равной вероятностью из множества $$\{1, 2, \dots,N_{\max}\}$$.

Начальные состояния $$y_{0i}$$ и переходы в следующее состояние присваиваются случайным образом в зависимости от числа состояний данного (случайного) автомата, как и выходные символы $$z_i$$ из заданного конечного алфавита. При этом с каждым автоматом ассоциируется важный параметр $$\lambda_i$$, который представляет среднее число мутаций, применяемых к родительской особи при производстве потомков (мутантов). Обычно первоначально полагается $$\lambda_i=5$$, и счетчику поколений присваивается $$k=1$$.

Фитнесс-функция. Вид фитнесс-функции существенно зависит от рассматриваемой проблемы (ее целевой функции) и для некоторых задач (прогнозирования и управления) будет описан ниже.

Мутация. Каждый из родительских автоматов $$A_i$$ мутирует и производит потомка $$A'_i$$ путем применения (возможно нескольких) операторов мутации. В задачах прогнозирования их число $$M_i$$ обычно определяется заранее экспериментальным путем. В экспериментах по управлению $$M_i$$ получается в результате вероятностного эксперимента со случайной переменной, значения которой для потомка $$\lambda'_i$$ определяются из значения параметра родителя $$\lambda_i$$ согласно распределению Пуассона: $$\lambda'_i=\lambda_i+0.5N(0,1)$$, где $$N(0,1)$$ представляет распределение Гаусса с нулевым средним значением и единичной дисперсией. Если $$\lambda'_i$$ или $$M_i$$ превышает $$N_i$$ или меньше 1, то им присваивается другое значение. Аналогично, если родительская особь имеет только одно состояние, то уменьшение числа состояний или назначение нового состояния запрещено. Используются следующие операторы мутации.

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

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

Изменение начального состояния: в родительском автомате случайно выбирается другое начальное состояние.

Изменение перехода: случайным образом выбранный переход перебрасывается в случайным образом выбранное состояние.

изменение выходного сигнала: в случайным образом выбранном переходе случайным образом изменяется значение выходного сигнала на другое значение из заданного алфавита.

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

Оценка фитнесс-функции: для каждого "мутанта" (вновь порожденного потомка) выполняется оценка значения фитнесс-функции. Как отмечалось, вид фитнесс-функции существенно зависит от задачи и ниже приведены некоторые наиболее распространенные типы.

Отбор родителей: для популяции с числом особей меньше десяти особи сортируются согласно их значениям фитнесс-функции и лучшая половина особей используется для генерации следующего поколения. Для больших популяций обычно используется турнирный отбор родителей. Часто применяется попарное сравнение между множеством родителей $$\{P_i\}\forall i\in\{1,\dots,m\}$$ и потомков $$\{P'_i\}\forall i\in\{1,\dots,m\}$$. Последующий выбор особей производится с равной вероятностью из множества родителей и потомков. Потомок признается победителем, если он имеет ошибку прогнозирования не больше, чем у конкурирующей особи. При этом в качестве родителей для генерации следующего поколения отбирается m особей-победителей

Процедура заканчивается при выполнении критерия останова, в противном случае наращивается номер поколения $$k=k+1$$ и осуществляется переход на шаг 3 алгоритма эволюции. Для прогнозирования часто число поколений ограничивается сверху $$(k=5)$$.

10.3.Применение классического эволюционного программирования в прогнозировании

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

Задача заключается в определении следующего символа входной последовательности. Допустим приведенный автомат рис.10.3 находится в начальном состоянии $$С$$, и на его вход подается последовательность $$X=011101$$. В этом случае согласно графу переходов-выходов автомат выдает выходную последовательность $$Y=110111$$. Автомат правильно выполняет предсказание, если его выходной сигнал $$z_i$$ равен следующему входному сигналу $$x_{i+1}$$. В случае равенства $$z_i=x_{i+1}$$ значение фитнесс-функции увеличивается на 1. Для нашего примера автомат правильно предсказывает 3 из 5 символов входной последовательности. .Иногда в фитнесс-функцию вводится штраф за превышение заданного числа состояний автомата.

(рис 10.3) Пример автомата для задачи прогнозирования

В качестве примера рассмотрим предсказание следующего символа периодической последовательности, один период которой представляется (101110011101)* [2]. Здесь входной и выходной алфавит конечных автоматов равен {0,1}. В качестве обучающего множества используется множество подпоследовательностей, содержащих первые 20 символов указанной циклической последовательности. Популяция случайным образом синтезированных конечных автоматов проходит пять поколений эволюции. В качестве фитнесс-функции в данном случае используется средняя абсолютная ошибка (число неправильно предсказанных символов). После короткого периода эволюции в популяции определялась лучшая особь (с минимальной ошибкой), которая далее использовалась для предсказания следующего символа входной последовательности. Такая процедура повторялась 300 раз, и процесс эволюции в итоге состоял из 1500 поколений. Процедура ЭП оценивалась при каждом прогнозе с использованием совокупной доли корректных прогнозов.

Эксперименты по прогнозированию выполнялись с популяциями, содержащими $$m=\{3,5,10,0,100\}$$ особей. Число мутаций выбиралось случайным образом из $$M_i=\{1,2,3\}$$. Было выполнено 30 попыток для каждой комбинации $$m$$ и $$M_i$$. Число состояний автоматов варьировалось от 1 до 10. Во всех экспериментах максимальное число состояний ограничивалось сверху 10.

Согласно [2] получены следующие результаты экспериментов для задачи прогнозирования, которые представлены на рис.10.4. Здесь показано, как изменяется доля правильных прогнозов для лучшего автомата в популяции, усредненная по 30 попыткам для популяций с числом особей 3,5,10,50 и 100 и выполнением от 1 до 3 операторов мутации. Из графика видно, что при первом прогнозе число правильных прогнозов примерно равно 80% (после 30 попыток первого эксперимента). Далее следует небольшой спад, и затем постепенное повышение доли правильных прогнозов примерно до 90%.

(рис 10.4) Изменение доли правильных прогнозов для различных мощностей популяций

10.4. Применение эволюционного программирования в задачах управления

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

В дальнейших экспериментах, для определенности, автомат должен выдать выходной сигнал, равный 5. Здесь особи популяции представляют модели целевого устройства управления, которые видоизменяются для того, чтобы получить необходимое выходное управляющее воздействие. Пусть для простоты алфавит автоматов состоит из целых чисел {0,1,2,…,9}. В первой серии экспериментов [4] в качестве целевого устройства использовался циклический автомат с тремя состояниями, представленный на рис.10.5. Во второй серии экспериментов применялись случайные автоматы с $$N$$ состояниями.

(рис 10.5) Циклический автомат с 3 состояниями

Как видно из рис.10.5, в качестве начального используется первое состояние автомата. Данный автомат, находясь в состоянии 1 при подаче входного сигнала $$i=\{1,\dots,8\}$$ на выходе генерирует значение $$i+1$$(по модулю 10). При подаче на вход 9 автомат выдает на выход 0 и переходит в следующее состояние $$n+1$$. Аналогично в состоянии 2 входные символы 0,1,2,…,8 генерируют выходы 2,3,…,9,0 соответственно. И наконец, в последнем состоянии 3 входы 0,1,2,…,8 производят выходы 3,4,….0,1. Аналогично может быть построен подобный циклический автомат для произвольного числа состояний. Отметим, что этот автомат полностью контролируем – то есть для каждого состояния существует входной сигнал, который выдает необходимое управляющее воздействие 5. С другой стороны, случайный автомат с $$N$$ состояниями может быть либо частично контролируемым (для некоторых состояний существует входной сигнал, выдающий управляющее воздействие), либо неконтролируемым (ни для одного состояния не существует входного сигнала, которые генерирует управляющее воздействие).

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

10.5. Современные направления эволюционного программирования

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

В современных работах в качестве особи в ЭП все чаще используется вектор вещественных чисел $$x$$. Рассмотрим этот подход на примере минимизации непрерывной неограниченной функции $$f:R^{n_z}\to R$$. Обозначим через $$x_i(t)$$ потенциальное $$i$$-е решение в поколении $$t$$, у которого каждая компонента $$x_{ij}(t)\in R,\ j=1,\dots,n_x$$. Потомок генерируется из родителя с помощью оператора мутации следующим образом:

$$x'_{ij}(t)=x_{ij}(t)+\Delta x_{ij}(t)$$

где $$x'_{ij}$$– компонента вектора потомка и $$\Delta x_{ij}(t)$$- шаг мутации. Размер шага определяется стохастически в соответствии с некоторым вероятностным распределением, где девиация (отклонение) шума задается параметром $$\sigma_{ij}$$. В общем виде размер шага вычисляется в соответствии с выражением $$\Delta x_{ij}(t)=\phi(\sigma_{ij}(t))\eta_{ij}(t)$$, где $$\phi:R\to R:$$- функция, которая масштабирует вклад шума $$\eta_{ij}(t)$$.

На базе характеристик масштабирующей функции $$\Phi$$ можно разбить алгоритмы ЭП на три группы:

Неадаптивное ЭП, в котором $$\Phi(\sigma)=\sigma$$, где отклонения размера шага остаются постоянными.

Динамическое ЭП, где отклонение размера шага изменяется с течением времени в соответствии с некоторой детерминированной функцией (как правило, фитнесс-функцией особи).

Самоадаптивное ЭП, в котором отклонение размера шага изменяется динамически. При этом лучшие значения $$\sigma_{ij}$$ отслеживаются параллельно с значениями переменных $$x_{ij}$$.

Поскольку девиация $$\sigma_{ij}$$ в значительной степени определяет поведение особи в случае динамического или самоадаптивного ЭП, они относятся к важнейшим параметрам ЭП. При этом каждая особь имеет свою стратегию параметров, в которой каждая особь представляется кортежем $$\lambda_i(t)=(x_i(t),\sigma_i(t))$$. Кроме девиации, которая является наиболее популярным параметром в ЭП, в некоторых работах [6,7] ЭП используются коэффициенты корреляции между компонентами особи, что фактически заимствовано из ЭС.

Как и любой эволюционный алгоритм, ЭП основано на стохастическом поиске. Здесь стохастичность вводится в вычисление размера шага, как функции шума $$\eta_{ij}$$, соответствующей некоторому вероятностному распределению. Следующие основные вероятностные распределения используются для указанных целей:

Однородное. Здесь шум формируется согласно однородному распределению $$\eta_{ij}(t)\sim U(x_{\min},x_{\max},j)$$, где $$x_{\min}$$ и $$x_{\max}$$ определяют нижнюю и верхнюю границы изменения диапазона значений $$\eta_{ij}$$. Отметим, что $$E[\eta_{ij}]=0$$ предотвращает любое смещение индуцированного шума, где $$E[\cdot]$$ означает оператор математического ожидания.

В [8] предложен оператор однородной мутации, который выполняется в соответствии с выражением $$\Delta x_{ij}(t)=U(0,1)(\hat{y}_j(t)-x_{ij}(t))$$, где $$\hat{y}_j$$ представляет лучшую особь текущей популяции $$C(t)$$. Этот оператор мутации заставляет все особи сделать случайное движение в сторону лучшей особи (подобно социальной компоненте в роевых алгоритмах). При этом лучшая особь не изменяется.

Гауссово. Для Гауссова оператора мутации шум формируется в соответствии с нормальным распределением с нулевым средним значением $$[6,9]:\eta_{ij}(t)\sim N(0,\sigma_{ij}(t))$$, где плотность функции Гаусса задается как $$f_c(x)=\frac{1}{\sigma\sqrt{2\pi}}e^{-x^2/(2\sigma^2)}$$ с отклонением $$\sigma$$.

Коши. При выполнении оператора мутации Коши $$\eta_{ij}(t)\sim C(0,v)$$, где $$v$$- масштабируюший коэффициент и функция плотности центрирована и определяется следующим образом:

$$f_c(x)=\frac{1}{\pi}\frac{v}{v+x^2}\mbox{ для }v>0.$$

Тогда соответствующая функция распределения определяется как $$F_c(x)=\frac{1}{2}+\frac{1}{\pi}\arctan(\frac{x}{v})$$. Отметим, что распределение Коши имеет более широкий "хвост" и поэтому данный оператор дает большие значения, чем Гауссов.

Леви. В этом распределении $$\eta_{ij}(t)\sim L(v)$$, где центрированная функция вероятностей Леви определяется как $$F_{L,v,\tau}(x)=\frac{1}{\pi}\int_0^{\infty}e^{-\tau q^v}\cos(qx)dq$$,где $$\gamma>0$$- масштабирующий множитель и значения $$0<\gamma<2$$ контролируют форму распределения. Отметим, что в случае $$\gamma=1$$ получается распределение Коши, а при $$\gamma=2$$- распределение Гаусса. При $$|x|\gg 1$$ плотность распределения Леви можно аппроксимировать как $$f_L(x)\infty x^{-(v+1)}$$. Алгоритм генерации случайных чисел Леви дан в работе [10].

Экспоненциальное. В этом случае $$\eta_{ij}(t)\sim E(0,\xi)$$ и функция плотности двойного экспоненциального вероятностного распределения определяется так:

$$f_{E,\xi}(x)=\frac{\xi}{2}e^{-\xi|x|}$$, где параметр $$\xi>0$$ управляет вариацией (которая равна $$\frac{2}{\xi^2}$$). При этом случайные числа генерируются в соответствии со следующими правилами: $$x=\begin{cases}\frac{1}{\xi}\ln(2y) if\ y\le 0.5\\-\frac{1}{\xi}\ln(2(1-y)) if\ y> 0.5\end{cases}$$, где $$y\sim U(0,1)$$. Следует отметить, что $$E(0,\xi)=\frac{1}{\xi}E(0,1)$$.

Хаос. Распределение хаоса также может быть использовано для шумовой составляющей $$\eta_{ij}(t)\sim R(0,1)$$, где $$R(0,1)$$ представляет хаотическую последовательность в диапазоне (-1,1). Эту последовательность можно генерировать в соответствии с выражением $$x_{t+1}=\sin(2/x_t)x_t,t=0,1\dots$$.

Комбинированные (сложные) распределения. В некоторых работах предложено использовать комбинированные распределения, например в[11] введен оператор средней мутации (mean mutation operator - MMO), где применяется линейная комбинация распределений Гаусса и Коши. В этом случае $$\eta_{ij}(t)=\eta N_{ij}+\eta C_{ij}(t)$$, где $$\eta N_{ij}(0,1)N(0,1),\eta C_{ij} C(0,1)$$. Результирующее распределение порождает большие мутации, чем Гауссово распределение, но меньшие, чем распределение Коши.

Таким образом, в настоящее время имеется богатый выбор различных видов операторов мутации. Вопрос в том, как различные распределения влияют в процессе поиска решения на расширение или эксплуатацию в пространстве решений. Для достижения хороших характеристик необходимо соблюдать баланс между малыми и большими величинами мутации. Распределение Коши вследствие более широкого "хвоста" порождает большие значения мутации, чем распределение Гаусса. Поэтому распределение Коши больше, чем распределение Гаусса способствует расширению пространства поиска. Поэтому распределение Коши хорошо использовать на начальном этапе поиска решения. Но с другой стороны, мутации на базе распределения Коши работают хуже, чем распределение Гаусса при тонкой коррекции решений на заключительном этапе поиска решений. Распределение Леви дает значения между величинами, порождаемыми распределениями Гаусса и Коши. Поэтому это распределение имеет лучший баланс в расширении и эксплуатации в процессе поиска решения и поэтому предпочтительней.

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

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

Обозначим через $$\mu$$ число родительских особей и через $$\lambda$$- число потомков. На первом этапе отбора для каждого родителя $$x_i(t)$$ или потомка $$x'_i(t)$$ необходимо вычислить значение относительной фитнесс-функции. Определим пул конкуренции $$P(t)=C(t)\cup C'(t)$$ и особь $$u_i(t)\in P(t),i=1,\dots,\mu+\lambda$$, принадлежащую этому пулу. Для каждой особи пула $$u_i(t)\in P(t)$$ случайным образом генерируется $$n_p$$ конкурентов из оставшихся особей пула $$P(t)\backslash u_i(t)$$. Тогда значение фитнесс-функции для каждой особи $$ u_i(t)$$ вычисляется следующим образом:

$$s_i(t)=\sum_{l=1}^{n*p} S_{il}(t),$$

где (в случае минимизации) $$s_{ij}(t)=\begin{cases}1,\mbox{если $f(u_l(t))<f(u_i(t))$}\\0,\mbox{в противном случаи}\end{cases}.$$.

В работе [12] предложен более "мягкий" подход, где число успешных исходов вычисляется согласно следующей формуле $$s_{ij}(t)=\begin{cases}1,\mbox{если $r_1<\frac{f(u_i(t))}{f(u_l(t))+f(u_i(t))}$}\\0,\mbox{в противном случаи}\end{cases}.$$, где $$n_p$$ оппонентов выбирается согласно выражению $$l=\lfloor 2\mu r_2+1\rfloor$$ и $$r_1r_2\sim U(0,1)$$. При этом в случае значительного превосходства $$f(u_i(t))\ll f(u_l(t))$$ с высокой вероятностью значение фитнесс-функции увеличивается на 1.

Основываясь на полученных значениях фитнесс-функции для каждой особи, далее выполняется отбор особей одним из методов, рассмотренных в разделе 3 (элитизма, турнира, рулетки, ранжирования и т.п.).

Кроме этого, различные методы можно использовать для отбора особи (родителя или потомка) в популяцию следующего поколения. Часто используется следующий подход, где выбирается по абсолютным значениям фитнесс-функции лучший потомок данного родителя и принимается решение о том, кто из них перейдет в следующее поколение согласно методу моделирования отжига. То есть потомок $$x'_i(t)$$ выживает в следующем поколении если:

$$f(x_i(t))< f(x_l(t))$$, или

$$e^{(-(f(x'_i(t))-f(x_l(t)))/\tau(t))}>U(0,1)$$,

где $$\tau$$- температурный коэффициент с $$\tau(t)=\gamma\tau(t-1),0<\gamma<1$$, иначе в следующем поколении выживает родительская особь. В этом случае, согласно методу моделирования отжига имеет шанс выжить особь с худшим значением фитнесс-функции.

10.6. Параметры ЭП

К основным параметрам ЭП относится, прежде всего, размер шага мутации. В простейшем случае значения отклонения фиксируются и функция параметра линейна, т.е. $$\Phi(\sigma_{ij}(t))=\sigma_{ij}(t)=\sigma_{ij}$$, где $$\sigma_{ij}$$ малая величина. Тогда потомок вычисляется в предположении Гауссова распределения $$x'_{ij}(t)=x_{ij}(t)+N_{ij}(0,\sigma_{ij})$$ с $$\Delta x_{ij}(t)=N_{ij}(0,\sigma_{ij})$$. Нотация $$N_{ij}(\cdot,\cdot)$$ означает, что новое случайное значение генерируется для каждой компоненты каждой особи. Очевидным недостатком такого подхода является то, что слишком малые значения $$\sigma_{ij}$$ ограничивают пространство поиска и дают низкую скорость сходимости. С другой стороны, слишком большие значения $$\sigma_{ij}$$ сдерживают "эксплуатацию" пространства поиска и способность точной доводки решения. Поэтому разработаны различные динамические стратегии изменения значений параметров.

В одном из первых методов динамической настройки параметров его значение зависит от значения фитнесс-функции [6,13]:

$$\sigma_{ij}(t)=\sigma_i(t)=\gamma f(x_i(t))$$, где $$\gamma \in(0,1]$$ и потомок $$x'_i(t)$$ генерируется следующим образом $$\begin{align*}x'_{ij}(t)=x_{ij}(t)+N(0,\sigma_i(t))\\=x_{ij}(t)+\sigma_i(t)N(0,1)\end{align*}$$.

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

$$\sigma_{ij}(t)=\sigma_i(t)=|f(\hat{y}-f(x_i)|$$

где $$\hat y$$- лучшая особь.

Расстояние от лучшей текущей особи в пространстве решений также можно использовать для этих целей:

$$\sigma_{ij}(t)=\sigma_i(t)=\varepsilon(\hat y,x_i)$$

где $$\varepsilon(\cdot,\cdot)$$ означает Евклидово расстояние между векторами. Преимущество этого подхода в том, что здесь чем хуже особь, тем больше шансов у нее мутировать. При этом потомок удаляется от худшей родительской особи. С другой стороны, чем лучше особь, тем потомок меньше удаляется от родительской особи, что позволяет "доводить" хорошее текущее решение. Но данный подход имеет следующие недостатки:

для очень больших значений фитнесс-функции размер шага может также быть слишком большим, что чревато пропуском оптимума;

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

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

Фогель [9] предложил аддитивный подход, где $$x'_{ij}(t)=x_{ij}(t)+\sqrt{\beta_{ij}(t)f(x_i)+\gamma_{ij}+N_{ij}(0,1)}$$,а $$\beta_{ij}$$ и $$\alpha_{ij}$$ - коэффициенты пропорциональности и сдвига.

Для функции $$f(x_1,x_2)=x_1^2+x_2^2$$ в [14] предложено $$\sigma_{ij}(t)=\sigma_i(t)=\frac{1.224\sqrt{f(x_i(t))}}{n_x}$$,где $$n_x$$- размерность пространства поиска $$(n_x=2)$$.

Для обучения рекуррентных нейронных сетей в [15] используется $$x'_{ij}(t)=x_{ij}(t)+\beta\sigma_{ij}(t)N_{ij}(0,1)$$, где $$\beta$$- коэффициент пропорциональности и $$sigma_{ij}(t)=U(0,1)\left[1-\frac{f(x_i(t))}{f_{\max}(t)}\right]$$ с максимальным значением $$f_{\max}(t)$$ текущей популяции (здесь рассматривается случай максимизации и $$f(x_i(t))$$ возвращает положительные значения).

В работе [17] (для задач минимизации) используется отклонение, пропорциональное нормализованному значению фитнесс-функции $$x'_{ij}(t)=x_{ij}(t)+\beta\sigma_i(t)N_{ij}(0,1)$$, где $$\beta_{ij}$$- коэффициент пропорциональности, $$\sigma_i(t)=\frac{f(x_i(t))}{\sum_{i=1}^{n_x}f(x_i(t))}$$ и $$n_s$$ - мощность популяции.

В работе [17] (для задач максимизации) используется выражение $$\sigma_{ij}(t)=(x_{\max,j}-x_{\min,j})(\frac{f_{\max}(t)-f(x_i(t))}{f_{\max}(t)}+\gamma)$$, которое позволяет комбинировать граничные условия и фитнесс-функцию. Здесь $$x_{\min}$$ и $$x_{\max}$$ определяют границы диапазона изменения в пространстве поиска и параметр $$\gamma>0$$ является малым числом.

В [18] используется отклонение, пропорциональное расстоянию от лучшей особи $$\beta_{ij}=\beta\frac{\sqrt{\varepsilon(x_{\min},x_{\max})}}{\pi}$$,где параметр $$\gamma>0$$ и коэффициент пропорциональности $$\beta_{ij}$$ определяется следующим образом: $$\beta_{ij}=\beta\frac{\sqrt{\varepsilon(x_{\min},x_{\max})}}{\pi}$$, где $$\beta\in[0,2]$$ и $$E(x_{\min},x_{\max})$$ определяет ширину пространства поиска как Евклидово расстояние между векторами $$x_{\min}$$ и $$x_{\max}$$. При этом большие значения параметра $$\gamma$$ способствуют расширению пространства поиска, а малые значения – его эксплуатации. Иногда этот параметр изменяется со временем от больших начальных значений до малых конечных. При этом потомок генерируется так: $$x_{ij}(t)=x_{ij}(t)-dit(x_{ij})\sigma_{ij}(t)N_{ij}(0,1)$$, где направление определяется выражением $$dir(x_{ij})=sign(\hat y_i-x_{ij})$$

В работе [19] предложено использовать следующее выражение: $$\sigma_{ij}(t)=\left[\frac{1}{\sqrt{\beta_jf(x(t))+\lambda_j}}\right]\left[\frac{\lambda}{f_{\max}(t)-f_{\min}(t)}\right]$$, где $$\gamma=2.5$$ и $$f_{\min}$$, $$f_{\max}$$ представляют минимальное и максимальное значения фитнесс-функции текущей популяции.

10.7. Самоадаптация

мы видели ранее, самоадаптация используется не только в ЭП, но и ЭС и ГА. Первые методы самоадаптации в ЭП предложены Фогелем в [20], получившие развитие в последующих работах, которые можно разбить на три основные группы.

Аддитивные методы. Первый аддитивный метод предложен Фогелем [21], где $$x'_{ij}=x_{ij}(t)+\sqrt{\beta_{ij}(t)f(x_i)+\lambda_{ij}+N_{ij}(0,1)}$$ и $$\eta$$- коэффициент обучения. В первых приложениях использовались значения $$\eta=1/6$$. Если $$\sigma_{ij}\le0$$, то $$\sigma_{ij}=\gamma$$, где $$\gamma$$- малая положительная константа.

Второй аддитивный метод [9] также предложен Фогелем, где $$\sigma_{ij}(t+1)=\sigma_{ij}(t)+\sqrt{f_{\sigma}(\sigma_{ij}(t))}N_{ij}(0,1)$$, где $$f_{\sigma}(a)=\left\{\begin{array}{rcl}a\mbox{если}a>0\\\gamma \mbox{если}a\le 0\end{array}\right\}$$. $$\sigma_{ij}\le0$$

Мультипликативные методы, где $$\sigma_{ij}(t+1)=\sigma(0)(\lambda_1e^{-\lambda_2\frac{t}{n_t}}+\lambda_3$$ и $$\lambda_1,\lambda_2,\lambda_3$$- управляющие параметры и $$n_t$$- максимальное количество итераций

Методы на основе логарифмически нормального распределения [21],где $$\sigma_{ij}(t+1)=\sigma_{ij}(t+1)e^{(\tau N_i(0,1)+\tau'N_{ij}(0,1))},$$ $$\tau'=\frac{1}{\sqrt{2\sqrt{n_x}}},\tau=\frac{1}{\sqrt{2n_x}}.$$

При этом потомок производится следующим образом:

$$x'_{ij}(t)=x_{ij}(t)+\sigma_{ij}(t)N_{ij}(0,1).$$

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

Робастное ЭП предложено в [22], здесь представление каждой особи расширяется до вектора из $$n_{\sigma}$$ параметров $$(x_o(t),\sigma_{i0},\dots,\sigma_{ik},\dots,\sigma_{in_{\sigma}})$$, где $$\sigma_{i0}$$ вектор параметров, получаемых в результате применения трех операторов мутации следующим образом:

Дупликация, где

$$\sigma'_{i0j}(t)=\sigma_{i0j}(t)\\\sigma'_{ilj}(t)=\sigma_{i(l-1)j}(t)$$

для $$i\in \{1,2,\dots,n_{\sigma}\}$$. Затем выполняется самоадаптация путем применения формулы (10.1) для $$\sigma_{ikj}(t)$$ для $$k=0,1,\dots.n_{\sigma}$$.

Устранение, где

$$\sigma'_{i(l-1)j}(t)=\sigma_{ilj}(t)\\\sigma_{in_{\sigma}j}(t)=\min\left\{\sigma_{\max}(t),\sum_{k=0}^{n_{\sigma}-1}\sigma_{ikj}(t)\right\}$$

для $$i\in \{1,2,\dots,n_{\sigma}\}$$. Далее производится самоадаптация путем применения формулы (10.1) для $$\sigma_{ikj}(t)$$ для $$k=0,1,\dots.n_{\sigma}$$.

Инвертирование, где

$$\sigma'_{i0j}(t)=\sigma_{ilj}(t)\\\sigma'_{ilj}(t)=\sigma_{i0j}(t)$$

для $$i\in \{1,2,\dots,n_{\sigma}\}$$. Затем также применяется формула (10.1) к $$\sigma_{i0j}(t)$$ и $$\sigma_{ilj}(t)$$ соответственно.

После выполнения приведенных операторов мутации порождается потомок путем использования выражения $$x'_{ij}(t)=x_{ij}(t)+\sigma_{i0j}(t)C(0,1)$$.

Аналогичным образом, Фогель [23] предложил векторную самоадаптацию, где на каждой итерации перед генерацией потомка вектор параметров с вероятностью $$p_{\sigma}$$ изменяется на один из оставшихся $$n_{\sigma}-1$$ векторов. Здесь важно определить лучшие значения для $$n_{\sigma}$$ и $$p_{\sigma}$$, которые являются проблемно- зависимыми.

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

10.8. Реализация ЭП

Разработаны различные способы реализации ЭП, к которым относятся следующие основные виды.

Классическое ЭП в современной нотации [5] подразумевает использование мутации Гаусса. Кроме этого возможно применение самоадаптации основе логарифмически нормального распределения. На этапе отбора обычно применяется стратегия элитизма.

Быстрое эволюционное программирование реализуется с использованием мутации Коши с $$\eta_{ij}(t)\sim C(0,v)$$ и $$v=1$$. Потомок генерируется согласно следующей формуле:

$$x'_{ij}(t)=x_{ij}(t)+\sigma_{ij}(t)C_{ij}(0,1),$$

где используется логарифмически нормальное распределение. На этапе отбора также применяется стратегия элитизма.

Экспоненциальное эволюционное программирование использует для формирования шума мутации двойное экспоненциальное распределение вероятностей с $$f_{E,\varepsilon}(x)=\frac{\xi}{2}e^{-\xi|x|}$$. Потомок генерируется следующим образом:

$$x'_{ij}(t)=x_{ij}(t)+\sigma_{ij}(t)\frac{1}{\xi}E_{ij}(0,1),$$

где для $$\sigma_{ij}$$ выполняется самоадаптация и изменение распределения контролируется параметром $$\xi$$. При этом, чем меньше значение $$\xi$$, тем имеет место большее изменение. Обычно используются малые начальные значения $$\xi$$, которые увеличиваются со временем.

Ускоренное эволюционное программирование использует два оператора вариации:

Оператор направления для определения направления поиска на основе значений фитнесс-функции;

мутация Гаусса $$\eta_{ij}(t)\sim N(0,\sigma_{ij}(t))$$.

Здесь особи представляются в виде $$X_i(t)=(x_i(t),p_i(t),a_i(t))$$, где $$p_i\in\{-1,1\},j=1,\dots,n_x$$ дает направление поиска для каждой компоненты $$i$$-ой особи и $$a_i$$–возраст этой особи. При этом возраст используется для форсирования расширения пространства поиска в том случае, если потомок хуже родителей. Потомок генерируется в два этапа. На первом шаге изменяются значения параметра возраста для каждой особи и определяется направление поиска (в предположении минимизации) следующим образом:

$$a_{i}(t)=\begin{cases}1,\mbox{если $f(x_i(t))<f(x_i(t-1))$}\\a_i(t-1)+1,\mbox{в противном случае}\end{cases}\mbox{ и}\\p_{ij}(t)=\begin{cases}sign(x_{ij}(t)-x_{ij}(t-1)),\mbox{если $f(x_i(t))<f(x_i(t-1))$}\\p_{ij}(t-1),\mbox{в противном случае}\end{cases}.$$

Если значение фитнесс-функции особи улучшается, поиск продолжается в прежнем направлении. В противном случае увеличивается значение параметра возраста по следующему правилу:

Если $$a_{i=1}$$, то

$$\sigma_i(t)=\gamma_1f(x_i(t))\\x'_{ij}(t)=x_{ij}(t)+p_{ij}(t)|N(0,\sigma_i(t))|$$

иначе

$$\sigma_i(t)=\gamma_2f(x_i(t))a_i(t)\\x'_{ij}(t)=x_{ij}(t)+N(0,\sigma_i(t)),$$

где $$\gamma_1,\gamma_2$$ -положительные компоненты.

Кроме приведеннных видов реализации разработаны многие другие модификации ЭП, некоторые из которых представлены в [5].

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

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

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

Чем отличается эволюция на уровне фенотипа от эволюции на уровне генотипа?

Какие виды мутации применяются в ЭП?

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

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

Какие различия между ГА и ЭП?

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

Как можно использовать ЭП в прогнозировании?

Какую фитнесс-функцию можно использовать при прогнозировании?

Как можно использовать ЭП при решении задач управления?

Какие формы генома используются в современных разделах ЭП?

Какие генетические операторы используются в современных разделах ЭП?

Какое представление решения используется в современных направлениях ЭП?

Какие вероятностные распределения и операторы мутации используются в современном ЭП?

Какие методы отбора родительских особей применяются в современном ЭП?

Что относится к основным параметрам ЭП?

Приведите способы управления шагом.

Какие методы самоадаптации применяются в ЭП?

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

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

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

описано представление потенциального решения в виде конечного автомата;

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

описаны различные виды фитнесс-функций, применяемые в ЭП;

представлено современное направление ЭП на основе вещественных векторов;

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