Обзор меметических и мульти-меметических методов глобальной оптимизации

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

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

Общая схема алгоритма:

Меметический алгоритм.

Шаг 1. Генерация начальной популяции P o , t = 0.

Шаг 2. Пока не выполнен критерий остановки, выполнять шаги 2.1–2.4

• 2.1.    При помощи операторов селекции, кроссинговера, мутации построить популяцию потомков Q_t .

• 2.2.    Выполнить локальное улучшение популяции Q_t .

• 2.3.    Из популяций Q_t и P_t создать популяцию P_t+1 следующего поколения, t = t + 1.

• 2.4.    При условии выполнения критерия перезапуска выполнить перезапуск с новой начальной популяцией P₀, t = 0.

Начальную популяцию можно построить, сгенерировав особей случайно или с помощью конструктивных эвристик и/или эвристик локального поиска.

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

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

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

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

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

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

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

Основная часть

Существует большое количество модификаций классических алгоритмов. В статье [1] авторы предложили свою модификацию метода дифференциальной эволюции. Метод относится к эволюционным алгоритмам. И используется для решения задач оптимизации большой размерности (однокритериальных или многокритериальных). Основных параметров алгоритма дифференциальной эволюции всего три: фактор масштабирования мутации, размер популяции и crossover rate. Этот алгоритм создает популяцию из векторов X i, _G, i = 1,2, ...,N, где N — размер популяции, которые изначально находятся в случайных местах. Особи нового поколения создаются путем комбинации элементов с предыдущего поколения. На каждом поколении G создается мутантный вектор V i, _G, который создается для каждого целевого вектора X [, _G,i = 1,2, .„,N в текущем поколении. Так наиболее часто используемые операторы мутации представлены ниже:

Модификация случайного вектора:

• ^Vi,G = ^Xr o ,G + ^^.g ^— Х_{Г 2}, _С)

Модификация текущего вектора с помощью лучшего:

• ^Vi,G = ^Xi,G + ^F(xbest,G ^{— X} i,G ) + ^F ( ^Xr₀,G ^{— Х}г 1 ^)

Модификация лучшего вектора 1:

V iG = ^Xbest,G + ^F(x r o ,G ^{— X} r 1 ,G )

Модификация лучшего вектора 2:

^Vi,G = ^Xbest,G + ^F ( ^Xr₀,G - ^ ri,G ) + ^F ( ^Xr₂,G - ^X^ ,G )

где F Е К — фактор мутации, генерируемый в интервале [0,1], X b _est , _G — лучший вектор-индивид в популяции на текущем шаге, г₀,.,т₃ — случайно выбранные не повторяющиеся индексы и отличные от ⁱ, ^Xbest,G •

Оператор кроссовера создает новый пробный вектор U i_iG = ( ^иИ£ , ^ui2,G , - , ^ui,D,G ) на с помощью смешивания элементов из векторов Vig и ^ i,G • Операцию выбора элемента можно записать следующим образом:

ui,j,G

ГVij.G, если Rj(0,1) ^ СГ или j = Jrand (      Хц£,если Rj(0,1)> Cr ,

где j = 1,2, ...,D, j_ran d — случайное целое число из интервала [1,D]. R j (0,1) — случайное число, генерируемое с равномерным распределением для каждого индекса j, в промежутке от 0 до 1, C_r Е [0,1] - оценочный параметр смешивания.

После создания нового пробного вектора реализуется процесс выбора, направленный на выбор лучшего вектора X i, _G или U iG . Для задачи минимизации выбор вектора для следующего поколения X i, _G+1 показан в выражении:

Xi,G+i

={

utjG,ecnu f(ul>G)

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

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

velocity = F(xr0,G—Xr1,G),

где X_ro,_G - вектор лучшего решения, X_ri,G - второй лучший вектор соответственно. Если же следующая итерация направленного локального поиска не дает результатов, то он прекращается.

Вторая модификация стандартного метода Shuffled frog leaping algorithm (алгоритм перемешанных лягушек), который является эвристикой, имитирующей поведение лягушек. По принципу работы алгоритм похож на алгоритм роя частиц. В ал- горитме различные особи популяции (лягушки) распределяются на группы, которые формируются из отсортированного в порядке убывания качества решения, то есть в каждой последующей группе все решения хуже, чем худшее решение из предыдущей группы. В каждой группе лягушки разделены в соответствии со значением пригодности от лучшей к худшей. Оператор перемешивания, который разде- ляет особи на группы, выражен следую- щим образом:

Р = {Qk|Qk = Qi+mG-ipi = 1,2,-,m,j = 1,2, .„,n,k = 1,2, .„,popsize}, где m — количество субпопуляций, n — количество лягушек в каждой субпопуляции, popsize = mxn — количество лягушек в популяции.

Q' = Qw + rand

где Q_w и Qbest — представляют позиции локально худшей и лучшей лягушек соответственно, rand — случайное число с равномерным распределением в интервале от 0 до 1. В случае же невозможности обновления худшей особи лучшим значением, значение лучшей локальной особи Qbe_st может быть заменено глобально лучшей особью Q_g. В случае же если на значение не может быть обновлено генерируется новое решение, случайно выбранное из всего пространства, где оптимизируемая функция определена.

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

Для адаптации SFLA к глобальному поиску минимума и решения задач оптимизации авторы [2] модифицировали алго-

После процесса перемешивания худшая лягушка может быть обновлена с помощью информации от лучшей лягушки (оператор прыжка лягушки), что описывается выражением:

• * (Qbest ^Qw),

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

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

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

п

Qc=nLQj- j=1

Для определения позиции гравитационного центра сначала вычисляется сила притяжения между элементами:

р..

rij

= G0

MiMj Rij + е

Rij = ||Xi    ^j'H2,

где Mi и Mj — представляют массу частиц i и j, Xi и Xj представляют положения частиц в пространстве высокой размерности, Rij — евклидова норма между Xi и Xj, е — небольшая константа. Качество решения частицы используется для измерения гравитационной массы частицы:

Mt =

mt ^"Ч

mt =

fiti — worstfit

bestfit — worstfit’

где fiti - представляет качество решения i-ой частицы, worstfit и bestfit — представляют качество решения худшей и лучшей частиц в популяции из п частиц. Отношение величин силы гравитации между двумя частицами:

Gfij =

Mj

Rij + =

Mj

(j * i)’

yn

^{1 j} = 1R2j+_£

откуда вытекает формула для определения гравитационного центра

n

Qg = £ GfyQ,.

j=i’j*i где Qj — позиция у-ой лягушки, п — количество лягушек в субпопуляции, Qg — гравитационный центр. Процесс выбора точки притяжения для худшей лягушки можно записать следующим образом:

(Qg’ecnu rand. < 0.5 {     QC’ иначе

Тогда новое положение худшей частицы будет определяться с помощью выражения:

Q w Qw + rand(Qbest  Qw) + rand(Qm Qw)’ где Qw — худшая лягушка, Qbest — лучшая лягушка. Таким образом, худшая лягушка может избежать попадания в локальный оптимум, но так как это не гарантированно, то применяется полет Леви, который действует, как оператор мутации для двух центров притяжения: гравитационного и геометрического и определяется выражением:

LevyFlight = rand(0’1) • normal(Q’l) • Levy’

где rand(0’1) — число, полученное с помощью равномерного распределения, normal(0’1) — число, полученное с помощью нормального распределения, Levy — число, полученное с помощью распреде- ления Леви в пространстве высокой размерности. Определение нового положения худшей лягушки с применением полета Леви выглядит следующим образом:

Q'w = Qw + rand(Qbest — Qw) + rand(LevyFlight 0 Qm—Qw)’

где 0 — поэлементное умножение.

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

Для этого авторы решили использовать аппроксимацию дискретного равномерного распределения для выбора особей и измерения.

Ui = randperm(D), popA = randperm(popSize), popB = randperm(popSize),

где Ui - вектор строка с различными случайными целыми числами в диапазоне [1, D]. popA и popB - векторы строки со случайными целыми числами в диапазоне [1, popSize] соответственно.

Выбор измерения, основанный на аппроксимации равномерного дискретного распределения, можно записать как:

Ut = Uj(1: ceil(rand * D))

где rand * D - равномерное случайное распределение в диапазоне [0, D], ceil -оператор округления в сторону большего целого. В итоге операцию обновления осо би можно записать в виде:

Qu = {

^Qij + ^rand(QpopA(u),j   ^QpopB(v)J),^{j G U}i

Qua e Ui              '

где QpopA(u) и QpopB(v) - осуществляют выбор случайной особи на основе аппроксимации равномерного дискретного распределения, j - целое число в диапазоне [1, D], U,v,i - целые числа в диапазоне [1, popSize] соответственно.

В источнике [3] авторы описывают их меметический алгоритм для решения задач крупномасштабной глобальной оптимизации. Основные идеи – добавление методов многородительской эволюции и пошагового адаптивного локального поиска. Мутантный вектор генерируется по формуле:

Vi,G = ^Xi,G + ^r1^(xbest,G

—

Xi,G)+r2(Xp-best,G-X,G),

где Xbest,G — лучший вектор в текущем поколении, p — best — индекс случайно выбранного вектора из 10% лучших векторов G-го поколения. Затем в зависимости от значений параметров в операции крос- совера выбирается один из векторов: мутантный вектор, этот же вектор с предыдущего шага, либо один из двух лучших векторов популяции. Операцию кроссовера можно записать в виде:

Г                VjiG, если rrand(ji) < СР1,

= I       Xja(i),G, если СР1 < rrand(ji) < СР1 + СР2,

Xji,G+1   | Xjb(i),G, если СР1 + СР2 < rrand(ji) < СР1 + СР2 + СР3,

I                       Xji G, иначе,

где         ; G {1,2, _,D], a(i) и b(i) G

{1,2, ,„,^Р) — индексы векторов случайно выбранных из лучшей половины векторов G -го поколения. Размер популяции уменьшается в процессе оптимизации, пока не уменьшится до одной особи.

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

Выбор измерений, в которых ведется поиск, производится в соответствии с выражением:

fji,G

={

0.5

1, если rand(1) < — +

0,

. 0.1 D ) или j = jrand(i) iteration/                 v 7,

иначе,

где fji E {0,1} — показывает будет ли j-е измерение i-го вектора изменяться, rand(1) — функция, генерирующая случайное число с равномерным распределением в интервале (0,1), iteration — номер итерации, jrand(i) E {1,2, ^,D} — случайно выбранный индекс, чтобы убедится, что хотя бы одно измерение в векторе Xi будет участвовать в поиске. Генерируется новое решение, в соответствии с формулой:

Xi,G+i = Xi,G + Si,G * rand(D, 1) * fi,G,

где Si,G — вектор, представляющий стандартный размер шага i-го индивида в G-ом поколении. Если новое решение лучше исходного, размер шага этих выбранных измерений умножается на 2. В противном случае решение восстанавливается, и каждый размер шага умножается на

• -0,5. Таким образом шаг обновляется в соответствие с выражением:

( sji,G х (—0.5), если Xi,G лучше чем xWi и fji,G = 1, Sji,G+i = {Sji,G х 2,     если Xi,G не лучше чем Xi,G+1 и fji,G = 1,

(                         Sji,G, иначе.

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

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

x = p±s|x—P|ln(ran5).

где д — параметр поиска, р — потенциальная яма.

Также используется алгоритм гравитационного поиска, основанный на законе тяготения Ньютона. Формула для определения силы притяжения между элементами:

Fij = G,

,  MiMj

0 Rij + ^

Rij = ||%i    %jh2,

где Mi и Mj — представляют массу частиц i и j, Xi и Xj представляют положения частиц в пространстве высокой размерности, Rij — евклидова норма между Х| и Xj,

£ — небольшая константа. Качество решения частицы используется для измерения гравитационной массы частицы:

mi

М- =---1—

1  Z^m- fit — worstfit mi      1      , г - ,                , г - , ’

bestfit — worstfit

где fiti — представляет качество решения i-ой частицы, worstfit и bestfit — представляют качество решения худшей и лучшей частиц в популяции из n частиц.

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

Zj е Kbest,j*i Go

vf = rand • vf

+

MiMj

R2j + £

(xf

^—X^f)

Mi xf = xf + vf,

где Kbest — набор K лучших частиц, d — измерение, v^f — ускорение.

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

Механизм квантовой эволюции реализован в каждой отдельной группе. Для повышения разнообразия населения используются разные центры потенциала:

Р = (1 — w) • xWOTSt + w • xbest,    w = rand,

^sgⁿ⁽) =^{

1, если rand < 0.5 —1, иначе

xworst

9 = 1.5

—

FES

0.5 X MAX FES’

= Р ± 9 • s9n() • |xWorst — Р'1 •

In (rand)’

где xWOTSt — представляет позицию худшей частицы, Xbest — позиция лучшей частицы, Р — центр потенциала, который находится в прямоугольной области, где xWOrst и Xbest вершины диагонали в этой области. В итоге худшая частица должна сходиться к одному из центров Р или Р' Р Ф Р':

XWorst(t) = Р(t),t^ ^, XWorst(f) = Р'(t),t^ го.

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

Рс =

п

1у nZ—।

Xj,

где n — количество частиц в подгруппе. Отношение величин силы гравитации между двумя частицами:

Gftj =

Mj

Rj + ^

z

п   ^Mj

j=1Rj+E

(j * i)

P = ^  GfiJ • Xj, j=1,j*t где Pj — позиция j-ой частицы, п — количество частиц в подгруппе, Рд — гравитационный центр. Затем один из центров - геометрический или гравитационный выбираются в качестве альтернативного центра квантового потенциала:

Р'

(Рд,если rand < 0.5 {     Рс, иначе

Итоговую формулу для вычисления нового положения худшей частицы можно записать в виде:

Xworst = xWOrst + rand(xbest — xworst) + parameter • Direction • Length., где parameter = g • ^^^, Length = \P' — xworst|, Direction = sgnQ.

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

Заключение

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