Алгоритм оценки распределения

В этом разделе описаны вероятностные модели, используемые в различных известных EDA разной степени сложности. Во всех случаях предполагается популяция ${\displaystyle P(t)}$ на поколении ${\displaystyle t}$, оператор выбора ${\displaystyle S}$, оператор построения модели ${\displaystyle \alpha }$ и оператор генерации ${\displaystyle \beta }$.

Простейшие EDA предполагают независимость переменных, то есть ${\displaystyle p(X_{1},X_{2})=p(X_{1})\cdot p(X_{2})}$. Соответственно, одномерные EDA используют только одномерную статистику, а многомерное распределение представляется произведением ${\displaystyle N}$ одномерных вероятностных распределений:

${\displaystyle D_{\text{Univariate}}:=p(X_{1},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}).}$

Такие факторизации применяются во многих различных EDA, далее приведены отдельные из них.

UMDA^[5] — это простой EDA, где оператор ${\displaystyle \alpha _{\text{UMDA}}}$ оценивает маргинальные вероятности по выбранной популяции ${\displaystyle S(P(t))}$. Пусть ${\displaystyle S(P(t))}$ содержит ${\displaystyle \lambda }$ элементов, тогда ${\displaystyle \alpha _{\text{UMDA}}}$ вычисляет вероятности:

${\displaystyle p_{t+1}(X_{i})={\dfrac {1}{\lambda }}\sum _{x\in S(P(t))}x_{i},~\forall i\in 1,2,\dots ,N.}$

Каждый шаг UMDA можно описать так:

${\displaystyle D(t+1)=\alpha _{\text{UMDA}}\circ S\circ \beta _{\lambda }(D(t)).}$

PBIL^[6] представляет популяцию неявно через её модель, из которой выполняется выборка новых решений и обновление самой модели. На каждом поколении выбирается ${\displaystyle \mu }$ индивидов и из них отбирается ${\displaystyle \lambda \leq \mu }$. Эти индивиды используются для обновления модели по формуле:

${\displaystyle p_{t+1}(X_{i})=(1-\gamma )p_{t}(X_{i})+(\gamma /\lambda )\sum _{x\in S(P(t))}x_{i},~\forall i\in 1,2,\dots ,N,}$

где ${\displaystyle \gamma \in (0,1]}$ — параметр скорости обучения; маленькое значение означает минимальные изменения текущей модели ${\displaystyle p_{t}(X_{i})}$ при добавлении новых решений. PBIL можно записать так:

${\displaystyle D(t+1)=\alpha _{\text{PIBIL}}\circ S\circ \beta _{\mu }(D(t))}$

CGA^[7] также использует неявно определяемые популяции через одномерные распределения. На каждом поколении ${\displaystyle t}$ берутся две особи ${\displaystyle x,y}$, ${\displaystyle P(t)=\beta _{2}(D(t))}$, их сортируют по убыванию приспособленности, лучшая обозначается ${\displaystyle u}$, худшая — ${\displaystyle v}$. Оценка одномерных вероятностей производится так:

${\displaystyle p_{t+1}(X_{i})=p_{t}(X_{i})+\gamma (u_{i}-v_{i}),\quad \forall i\in 1,2,\dots ,N,}$

где ${\displaystyle \gamma \in (0,1]}$ — постоянная, обычно ${\displaystyle \gamma =1/N}$. CGA определяется так:

${\displaystyle D(t+1)=\alpha _{\text{CGA}}\circ S_{{\text{Sort}}(f)}\circ \beta _{2}(D(t))}$

Несмотря на эффективность одномерных моделей, зачастую они недостаточно хорошо отображают структуру задачи для достижения превосходства над стандартными ГА. Для устранения этого недостатка предлагается двумерная факторизация, учитывающая пары связанных переменных. Такую факторизацию можно записать так, где ${\displaystyle \pi _{i}}$ — связанная переменная для ${\displaystyle X_{i}}$, ${\displaystyle |\pi _{i}|=1}$:

${\displaystyle D_{\text{Bivariate}}:=p(X_{1},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}|\pi _{i}).}$

Двумерные и многомерные распредления, как правило, отображаются в виде вероятностных графических моделей, где рёбра соответствуют зависимостям (условным вероятностям), а вершины — переменным. Для обучения структуры графа из данных используется linkage-learning.

MIMIC^[8] факторизует совместное распределение вероятностей как цепочку зависимостей между переменными. Находится перестановка ${\displaystyle r:i\mapsto j}$ переменных, минимизирующая дивергенцию Кульбака — Лейблера, то есть ${\displaystyle \pi _{r(i+1)}=\{X_{r(i)}\}}$. Итоговое распределение:

${\displaystyle p_{t+1}(X_{1},\dots ,X_{N})=p_{t}(X_{r(N)})\prod _{i=1}^{N-1}p_{t}(X_{r(i)}|X_{r(i+1)}).}$

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

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{MIMIC}}\circ S(P(t)).}$

BMDA^[9] разбивает совместное распределение на несколько двумерных. Сначала случайно выбранная переменная включается как узел в граф, далее по мере обхода к имеющимся узлам добавляются наиболее зависимые переменные из ещё не включённых, пока не останется неродственных. Итоговая модель представляет собой лес из деревьев, где корневые переменные ${\displaystyle \Upsilon _{t}}$ формируют независимые компоненты, остальные — условные.

${\displaystyle p_{t+1}(X_{1},\dots ,X_{N})=\prod _{X_{i}\in \Upsilon _{t}}p_{t}(X_{i})\cdot \prod _{X_{i}\in I_{t}}p_{t}(X_{i}|\pi _{i}).}$

Каждый шаг BMDA:

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{BMDA}}\circ S(P(t)).}$

Дальнейшее развитие EDA опирается на многомерные факторизации. Совместное распределение разлагается на компоненты ограниченного размера ${\displaystyle |\pi _{i}|\leq K}$:

${\displaystyle p(X_{1},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}|\pi _{i})}$

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

ECGA^[10] — один из первых EDA с явной многомерной факторизацией, учитывающий высокоуровневые зависимости между переменными. Здесь совместное распределение представлено произведением многомерных маргинальных, для кластера (linkage set) ${\displaystyle \tau }$, ${\displaystyle |\tau |\leq K}$:

${\displaystyle p(X_{1},\dots ,X_{N})=\prod _{\tau \in T_{\text{eCGA}}}p(\tau ).}$

ECGA популяризировал термин linkage-learning — процедуры определения зависимостей. Обучение связываний опирается исключительно на две меры: сложность модели (MC) и степень компрессии популяции (CPC):

${\displaystyle MC=\log _{2}(\lambda +1)\sum _{\tau \in T_{\text{eCGA}}}(2^{|\tau |-1}),}$ ${\displaystyle CPC=\lambda \sum _{\tau \in T_{\text{eCGA}}}H(\tau ),}$

где ${\displaystyle H(\tau )}$ — совместная энтропия группы переменных ${\displaystyle \tau }$. Модель связываний ${\displaystyle T_{\text{eCGA}}}$ строится путём последовательного объединения кластеров, максимизирующих прирост метрики ${\displaystyle CCC=MC+CPC}$, до тех пор пока дальнейшие улучшения невозможны. Ход ECGA:

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{eCGA}}\circ S(P(t))}$

BOA^[11][12][13] использует байесовские сети для построения и выборки перспективных решений. Байесовские сети — ориентированные ациклические графы, где узлы — переменные, а рёбра — условные вероятности. Максимальная размерность условного множества — ${\displaystyle K}$ переменных. BOA строит графическую модель вероятностной факторизации, параметры которой (условные вероятности) оцениваются по выбранной популяции методом максимального правдоподобия:

${\displaystyle p(X_{1},X_{2},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}|\pi _{i}).}$

Структура самой сети настраивается итеративно, на каждом шаге добавляя рёбра, максимизирующие некую меру качества (например, BIC либо метрика Бая–Дирихле)^[14]. После построения сети BOA генерирует решения в упорядочении по предшественникам: каждая переменная выбирается условно по "родителям". Формально:

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{BOA}}\circ S(P(t))}$

LTGA^[15] отличается тем, что не строит явное вероятностное распределение, а лишь модель связей — семейство подмножеств (FOS):

${\displaystyle T_{\text{LT}}=\{\{x_{1}\},\{x_{2}\},\{x_{3}\},\{x_{4}\},\{x_{1},x_{2}\},\{x_{3},x_{4}\}\}.}$

Обучение дерева связей — определение иерархической кластеризации: на каждом шаге объединяются два "ближайших" кластера, в поддеревья, которые и сохраняются как подмножества ${\displaystyle \tau \in T_{\text{LT}}}$.

LTGA использует ${\displaystyle T_{\text{LT}}}$ для процедуры "оптимального смешивания" (революционный модифицированный оператор рекомбинации), обозначаемой ${\displaystyle R_{\text{LTGA}}}$: перенос блоков генетического материала только если улучшение качества. Формально:

   Вход: семейство подмножеств ${\displaystyle T_{\text{LT}}}$ и популяция ${\displaystyle P(t)}$
   Выход: популяция ${\displaystyle P(t+1)}$.
   для каждого ${\displaystyle x_{i}}$ в ${\displaystyle P(t)}$ делать
       для каждого ${\displaystyle \tau }$ в ${\displaystyle T_{\text{LT}}}$ делать
           выбрать случайный ${\displaystyle x_{j}\in P(t):x_{i}\neq x_{j}}$
           ${\displaystyle f_{x_{i}}}$ := ${\displaystyle f(x_{i})}$
           ${\displaystyle x_{i}[\tau ]}$:= ${\displaystyle x_{j}[\tau ]}$
           если ${\displaystyle f(x_{i})\leq f_{x_{i}}}$ то
               ${\displaystyle x_{i}[\tau ]:=x_{j}[\tau ]}$
   вернуть ${\displaystyle P(t)}$

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

${\displaystyle P(t+1)=R_{\text{LTGA}}(P(t))\circ \alpha _{\text{LTGA}}(P(t))}$

• Probability collectives (PC)^[16][17]
• Hill climbing with learning (HCwL)^[18]
• Estimation of multivariate normal algorithm (EMNA)
• Estimation of Bayesian networks algorithm (EBNA)
• Стохастический подъём на холм с обучением по векторам нормальных распределений (SHCLVND)^[19]
• Real-coded PBIL
• Selfish Gene Algorithm (SG)^[20]
• Compact Differential Evolution (cDE)^[21] и её варианты^{[22][23][24][25][26]}
• Компактный рой частиц (cPSO)^[27]
• Компактная бактериальная поисковая оптимизация (cBFO)^[28]
• Вероятностная инкрементальная эволюция программ (PIPE)^[29]
• Estimation of Gaussian networks algorithm (EGNA)
• Estimation multivariate normal algorithm with thresheld convergence^[30]
• Genetic Algorithm with Matrix of Dependences (DSMGA)^[31][32]