Оценка алгоритма распределения - Estimation of distribution algorithm

Оценка алгоритма распределения. Для каждой итерации я, случайный розыгрыш выполняется для популяции п в раздаче PDu. Параметры распределения PDe затем оцениваются с использованием выбранных точек PS. Иллюстрированный пример оптимизирует непрерывную целевую функцию f (X) с уникальным оптимумом О. Выборка (по нормальному распределению N) концентрируется вокруг оптимума по мере выполнения алгоритма раскрутки.

Оценка алгоритмов распределения (EDA), иногда называемый вероятностные генетические алгоритмы построения моделей (PMBGA),^[1] находятся стохастическая оптимизация методы, которые направляют поиск оптимума путем построения и выборки явных вероятностных моделей многообещающих возможных решений. Оптимизация рассматривается как серия последовательных обновлений вероятностной модели, начиная с модели, кодирующей неинформативные априорные решения по сравнению с допустимыми, и заканчивая моделью, которая генерирует только глобальные оптимумы.^[2][3][4]

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

Общая процедура EDA изложена ниже:

т : = 0 инициализировать модель M (0) для представления равномерного распределения по допустимым решениямпока (критерии прекращения не выполнены) делать    п : = генерировать N> 0 возможных решений путем выборки M (т)    F : = оценить все возможные решения в п    M (t + 1): = adjust_model (п, F, M (т))    т := т + 1

Использование явных вероятностных моделей в оптимизации позволило EDA реально решить задачи оптимизации, которые были заведомо сложными для большинства традиционных эволюционных алгоритмов и традиционных методов оптимизации, например, проблемы с высоким уровнем эпистаз^{[нужна цитата ]}. Тем не менее, преимущество EDA состоит также в том, что эти алгоритмы предоставляют специалисту по оптимизации ряд вероятностных моделей, которые раскрывают много информации о решаемой проблеме. Эта информация, в свою очередь, может использоваться для разработки операторов окружения для конкретных задач для локального поиска, для смещения будущих прогонов EDA по аналогичной проблеме или для создания эффективной вычислительной модели проблемы.

Например, если совокупность представлена ​​строками битов длиной 4, EDA может представлять совокупность многообещающих решений, используя один вектор из четырех вероятностей (p1, p2, p3, p4), где каждый компонент p определяет вероятность того, что позиция равна 1. Используя этот вектор вероятности, можно создать произвольное количество возможных решений.

Оценка алгоритмов распределения (EDA)

В этом разделе описаны модели, построенные некоторыми хорошо известными 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)

UMDA^[5] это простой EDA, в котором используется оператор ${ displaystyle alpha _ {UMDA}}$ для оценки предельных вероятностей от выбранной совокупности ${ Displaystyle S (P (t))}$. Предполагая ${ Displaystyle S (P (t))}$ содержать ${ displaystyle lambda}$ элементы ${ displaystyle alpha _ {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)

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 гамма в (0,1]}$ - параметр, определяющий скорость обучения, небольшое значение определяет, что предыдущая модель ${ displaystyle p_ {t} (X_ {i})}$ должны быть лишь немного изменены за счет отобранных новых решений. PBIL можно описать как

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

Компактный генетический алгоритм (cGA)

CGA,^[7] также полагается на неявные совокупности, определяемые одномерными распределениями. В каждом поколении ${ displaystyle t}$, два человека ${ displaystyle x, y}$ отбираются, ${ Displaystyle Р (т) = бета _ {2} (D (т))}$. Население ${ Displaystyle P (t)}$ затем сортируется в порядке убывания пригодности, ${ displaystyle S _ {{ text {Sort}} (f)} (P (t))}$, с ${ displaystyle u}$ быть лучшим и ${ displaystyle v}$ худшее решение. CGA оценивает одномерные вероятности следующим образом

${ displaystyle p_ {t + 1} (X_ {i}) = p_ {t} (X_ {i}) + gamma (u_ {i} -v_ {i}), quad forall i in 1, 2, точки, N,}$

куда, ${ Displaystyle гамма в (0,1]}$ константа, определяющая скорость обучения, обычно устанавливается на ${ displaystyle gamma = 1 / N}$. CGA можно определить как

${ Displaystyle D (t + 1) = alpha _ { text {CGA}} circ S _ {{ text {Sort}} (f)} circ beta _ {2} (D (t))}$

Двумерные факторизации

Хотя одномерные модели можно вычислить эффективно, во многих случаях они недостаточно репрезентативны, чтобы обеспечить лучшую производительность, чем GA. Чтобы преодолеть такой недостаток, в сообществе EDA было предложено использование двумерной факторизации, в которой можно моделировать зависимости между парами переменных. Двумерная факторизация может быть определена следующим образом, где ${ displaystyle pi _ {я}}$ содержит возможную переменную, зависящую от ${ 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 _{я}).}$

Двумерные и многомерные распределения обычно представлены как вероятностные Графические модели (графы), в которых ребра обозначают статистические зависимости (или условные вероятности), а вершины обозначают переменные. Чтобы узнать структуру PGM на основе связывания данных, используется обучение.

Взаимная информация, максимизирующая кластеризацию ввода (MIMIC)

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

${ 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)

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

Результирующая модель представляет собой лес с несколькими деревьями, укорененными в узлах. ${ displaystyle Upsilon _ {t}}$. Учитывая ${ displaystyle I_ {t}}$ Для некорневых переменных BMDA оценивает факторизованное распределение, в котором корневые переменные могут быть выбраны независимо, тогда как все остальные должны быть обусловлены родительской переменной ${ displaystyle pi _ {я}}$.

${ 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, ~ forall i in 1,2, dots, N}$.

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

Изучение PGM, кодирующих многомерные распределения, является вычислительно затратной задачей, поэтому для EDA обычно оценивают многомерную статистику на основе двумерной статистики. Такая релаксация позволяет построить PGM за полиномиальное время за ${ displaystyle N}$; однако это также ограничивает универсальность таких EDA.

Расширенный компактный генетический алгоритм (eCGA)

ECGA^[10] был одним из первых EDA, который использовал многомерную факторизацию, в которой можно моделировать зависимости высокого порядка между переменными решения. Его подход факторизует совместное распределение вероятностей в произведении многомерных маржинальных распределений. Предполагать ${ displaystyle T _ { text {eCGA}} = { tau _ {1}, dots, tau _ { Psi} }}$ набор подмножеств, в котором каждое ${ displaystyle tau in T _ { text {eCGA}}}$ набор связей, содержащий ${ Displaystyle | тау | leq K}$ переменные. Факторизованное совместное распределение вероятностей представлено следующим образом

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

ECGA популяризировала термин «обучение связям» для обозначения процедур, которые идентифицируют наборы связей. Его процедура обучения связям основана на двух показателях: (1) сложности модели (MC) и (2) сложности сжатой совокупности (CPC). MC количественно определяет размер представления модели с точки зрения количества бит, необходимых для хранения всех предельных вероятностей.

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

CPC, с другой стороны, количественно оценивает сжатие данных в терминах энтропии предельного распределения по всем разделам, где ${ displaystyle lambda}$ - выбранная численность населения, ${ Displaystyle | тау |}$ количество переменных решения в наборе связей ${ Displaystyle тау}$ и ${ Displaystyle Н ( тау)}$ - совместная энтропия переменных в ${ Displaystyle тау}$

${ displaystyle CPC = lambda sum _ { tau in T _ { text {eCGA}}} H ( tau).}$

Обучение связыванию в ECGA работает следующим образом: (1) вставить каждую переменную в кластер, (2) вычислить CCC = MC + CPC для текущих наборов связей, (3) проверить увеличение CCC, обеспечиваемое объединением пар кластеров, (4) эффективно объединяет те кластеры с наибольшим улучшением CCC. Эта процедура повторяется до тех пор, пока улучшения CCC не станут невозможными, и не будет получена модель связи. ${ displaystyle T _ { text {eCGA}}}$. ECGA работает с конкретными популяциями, поэтому, используя факторизованное распределение, смоделированное с помощью ECGA, его можно описать как

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

Байесовский алгоритм оптимизации (BOA)

BOA^[11][12][13] использует байесовские сети для моделирования и выборки многообещающих решений. Байесовские сети представляют собой ориентированные ациклические графы, в которых узлы представляют переменные, а ребра представляют собой условные вероятности между парой переменных. Значение переменной ${ displaystyle x_ {i}}$ может быть обусловлено максимумом ${ displaystyle K}$ другие переменные, определенные в ${ displaystyle pi _ {я}}$. BOA строит PGM, кодирующий факторизованное совместное распределение, в котором параметры сети, то есть условные вероятности, оцениваются по выбранной совокупности с использованием оценки максимального правдоподобия.

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

С другой стороны, байесовская сетевая структура должна строиться итеративно (связывание-обучение). Он начинается с сети без ребер и на каждом шаге добавляет ребро, которое лучше улучшает некоторую метрику оценки (например, байесовский информационный критерий (BIC) или метрику Байеса-Дирихле с эквивалентностью правдоподобия (BDe)).^[14] Показатель скоринга оценивает структуру сети в соответствии с ее точностью моделирования выбранной популяции. На основе построенной сети BOA отбирает новые многообещающие решения следующим образом: (1) он вычисляет родовой порядок для каждой переменной, причем каждому узлу предшествуют его родители; (2) каждая переменная условно отбирается для своих родителей. При таком сценарии каждый шаг BOA можно определить как

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

Генетический алгоритм дерева сцепления (LTGA)

LTGA^[15] отличается от большинства EDA в том смысле, что в нем явно не моделируется распределение вероятностей, а только модель связей, называемая деревом связей. Связь ${ displaystyle T}$ представляет собой набор наборов связей без ассоциированного распределения вероятностей, поэтому нет возможности брать образцы новых решений непосредственно из ${ displaystyle T}$. Модель связей - это дерево связей, созданное в виде Семейство наборов (FOS).

${ displaystyle T _ { text {LT}} = { {x_ {1} }, {x_ {2} }, {x_ {3} }, {x_ {4} }, {x_ {1}, x_ {2} }, {x_ {3}, x_ {4} } }.}$

Процедура изучения дерева связей - это иерархическая кластеризация алгоритм, который работает следующим образом. На каждом шагу двое ближайший кластеры ${ displaystyle i}$ и ${ displaystyle j}$ объединяются, эта процедура повторяется до тех пор, пока не останется только один кластер, каждое поддерево сохраняется как подмножество ${ displaystyle tau in T _ { text {LT}}}$.

LTGA использует ${ displaystyle T _ { text {LT}}}$ для управления процедурой «оптимального перемешивания», которая напоминает оператор рекомбинации, но допускает только улучшающие ходы. Обозначим его как ${ displaystyle R _ { text {LTGA}}}$, где обозначение ${ Displaystyle х [ тау] получает у [ тау]}$ указывает на передачу генетического материала, индексированного ${ Displaystyle тау}$ из ${ displaystyle y}$ к ${ displaystyle x}$.

Алгоритм Оптимальное смешение генофонда Вход: семейство подмножеств ${ displaystyle T _ { text {LT}}}$ и население ${ Displaystyle P (t)}$   Продукт: Население. ${ Displaystyle P (t + 1)}$.   для каждого ${ displaystyle x_ {i}}$ в ${ Displaystyle P (t)}$ делать       для каждого ${ Displaystyle  тау}$ в ${ displaystyle T _ { text {LT}}}$ делать           выбрать случайный ${ Displaystyle x_ {j}  in P (t): x_ {i}  neq x_ {j}}$           ${ displaystyle f_ {x_ {i}}}$ := ${ displaystyle f (x_ {i})}$           ${ Displaystyle х_ {я} [ тау]}$:= ${ Displaystyle х_ {j} [ тау]}$           если ${ displaystyle f (x_ {i})  leq f_ {x_ {i}}}$ тогда               ${ Displaystyle х_ {я} [ тау]: = х_ {j} [ тау]}$    возвращаться ${ Displaystyle P (t)}$

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

${ Displaystyle P (t + 1) = R _ { text {LTGA}} (P (t)) circ alpha _ { text {LTGA}} (P (t))}$

Другой

• Вероятностные коллективы (ПК)^[16][17]
• Восхождение на холмы с обучением (HCwL)^[18]
• Оценка многомерного нормального алгоритма (EMNA)^{[нужна цитата ]}
• Алгоритм оценки байесовских сетей (EBNA)^{[нужна цитата ]}
• Стохастическое восхождение на гору с обучением по векторам нормальных распределений (SHCLVND)^[19]
• PBIL с реальным кодированием^{[нужна цитата ]}
• Эгоистичный генный алгоритм (SG)^[20]
• Компактная дифференциальная эволюция (cDE)^[21] и его варианты^{[22][23][24][25][26][27]}
• Оптимизация роя компактных частиц (cPSO)^[28]
• Компактная оптимизация сбора бактерий (cBFO)^[29]
• Вероятностная инкрементальная эволюция программы (PIPE)^[30]
• Алгоритм оценки гауссовских сетей (EGNA)^{[нужна цитата ]}
• Многомерный нормальный алгоритм оценки с пороговой сходимостью^[31]
• Генетический алгоритм матрицы структуры зависимостей (DSMGA)^[32][33]

Связанный

• CMA-ES
• Кросс-энтропийный метод

Рекомендации