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

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

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

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

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

t  : = 0инициализировать модель M (0) для представления равномерного распределения по допустимым решениямwhile (критерии завершения не выполнены) do  P  : = генерировать N> 0 возможных решений путем выборки M ( t ) F  : = оценивать все возможные решения в P M (t + 1): = adjust_model ( P , F , M ( t ) ) t  : = t + 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})}$${\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)).}$

Population-based incremental learning (PBIL)[edit]

The PBIL,^[6] represents the population implicitly by its model, from which it samples new solutions and updates the model. At each generation, ${\displaystyle \mu }$ individuals are sampled and ${\displaystyle \lambda \leq \mu }$ are selected. Such individuals are then used to update the model as follows

${\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,}$

where ${\displaystyle \gamma \in (0,1]}$ is a parameter defining the learning rate, a small value determines that the previous model ${\displaystyle p_{t}(X_{i})}$ should be only slightly modified by the new solutions sampled. PBIL can be described as

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

Compact genetic algorithm (cGA)[edit]

The CGA,^[7] also relies on the implicit populations defined by univariate distributions. At each generation ${\displaystyle t}$, two individuals ${\displaystyle x,y}$ are sampled, ${\displaystyle P(t)=\beta _{2}(D(t))}$. The population ${\displaystyle P(t)}$ is then sorted in decreasing order of fitness, ${\displaystyle S_{{\text{Sort}}(f)}(P(t))}$, with ${\displaystyle u}$ being the best and ${\displaystyle v}$ being the worst solution. The CGA estimates univariate probabilities as follows

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

where, ${\displaystyle \gamma \in (0,1]}$ is a constant defining the learning rate, usually set to ${\displaystyle \gamma =1/N}$. The CGA can be defined as

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

Bivariate factorizations[edit]

Although univariate models can be computed efficiently, in many cases they are not representative enough to provide better performance than GAs. In order to overcome such a drawback, the use of bivariate factorizations was proposed in the EDA community, in which dependencies between pairs of variables could be modeled. A bivariate factorization can be defined as follows, where ${\displaystyle \pi _{i}}$ contains a possible variable dependent to ${\displaystyle X_{i}}$, i.e. ${\displaystyle |\pi _{i}|=1}$.

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

Bivariate and multivariate distributions are usually represented as Probabilistic Graphical Models (graphs), in which edges denote statistical dependencies (or conditional probabilities) and vertices denote variables. To learn the structure of a PGM from data linkage-learning is employed.

Mutual information maximizing input clustering (MIMIC)[edit]

The MIMIC^[8] factorizes the joint probability distribution in a chain-like model representing successive dependencies between variables. It finds a permutation of the decision variables, ${\displaystyle r:i\mapsto j}$, such that ${\displaystyle x_{r(1)}x_{r(2)},\dots ,x_{r(N)}}$ minimizes the Kullback-Leibler divergence in relation to the true probability distribution, i.e. ${\displaystyle \pi _{r(i+1)}=\{X_{r(i)}\}}$. MIMIC models a distribution

${\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)}).}$

New solutions are sampled from the leftmost to the rightmost variable, the first is generated independently and the others according to conditional probabilities. Since the estimated distribution must be recomputed each generation, MIMIC uses concrete populations in the following way

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

Bivariate marginal distribution algorithm (BMDA)[edit]

The BMDA^[9] factorizes the joint probability distribution in bivariate distributions. First, a randomly chosen variable is added as a node in a graph, the most dependent variable to one of those in the graph is chosen among those not yet in the graph, this procedure is repeated until no remaining variable depends on any variable in the graph (verified according to a threshold value).

The resulting model is a forest with multiple trees rooted at nodes ${\displaystyle \Upsilon _{t}}$. Considering ${\displaystyle I_{t}}$ the non-root variables, BMDA estimates a factorized distribution in which the root variables can be sampled independently, whereas all the others must be conditioned to the parent variable ${\displaystyle \pi _{i}}$.

${\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}).}$

Each step of BMDA is defined as follows

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

Multivariate factorizations[edit]

The next stage of EDAs development was the use of multivariate factorizations. In this case, the joint probability distribution is usually factorized in a number of components of limited size ${\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})}$

The learning of PGMs encoding multivariate distributions is a computationally expensive task, therefore, it is usual for EDAs to estimate multivariate statistics from bivariate statistics. Such relaxation allows PGM to be built in polynomial time in ${\displaystyle N}$; however, it also limits the generality of such EDAs.

Extended compact genetic algorithm (eCGA)[edit]

The ECGA^[10] was one of the first EDA to employ multivariate factorizations, in which high-order dependencies among decision variables can be modeled. Its approach factorizes the joint probability distribution in the product of multivariate marginal distributions. Assume ${\displaystyle T_{\text{eCGA}}=\{\tau _{1},\dots ,\tau _{\Psi }\}}$ is a set of subsets, in which every ${\displaystyle \tau \in T_{\text{eCGA}}}$ is a linkage set, containing ${\displaystyle |\tau |\leq K}$ variables. The factorized joint probability distribution is represented as follows

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

The ECGA popularized the term "linkage-learning" as denoting procedures that identify linkage sets. Its linkage-learning procedure relies on two measures: (1) the Model Complexity (MC) and (2) the Compressed Population Complexity (CPC). The MC quantifies the model representation size in terms of number of bits required to store all the marginal probabilities

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

The CPC, on the other hand, quantifies the data compression in terms of entropy of the marginal distribution over all partitions, where ${\displaystyle \lambda }$ is the selected population size, ${\displaystyle |\tau |}$ is the number of decision variables in the linkage set ${\displaystyle \tau }$ and ${\displaystyle H(\tau )}$ is the joint entropy of the variables in ${\displaystyle \tau }$

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

The linkage-learning in ECGA works as follows: (1) Insert each variable in a cluster, (2) compute CCC = MC + CPC of the current linkage sets, (3) verify the increase on CCC provided by joining pairs of clusters, (4) effectively joins those clusters with highest CCC improvement. This procedure is repeated until no CCC improvements are possible and produces a linkage model ${\displaystyle T_{\text{eCGA}}}$. The ECGA works with concrete populations, therefore, using the factorized distribution modeled by ECGA, it can be described as

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

Bayesian optimization algorithm (BOA)[edit]

The BOA^[11][12][13] uses Bayesian networks to model and sample promising solutions. Bayesian networks are directed acyclic graphs, with nodes representing variables and edges representing conditional probabilities between pair of variables. The value of a variable ${\displaystyle x_{i}}$ can be conditioned on a maximum of ${\displaystyle K}$ other variables, defined in ${\displaystyle \pi _{i}}$. BOA builds a PGM encoding a factorized joint distribution, in which the parameters of the network, i.e. the conditional probabilities, are estimated from the selected population using the maximum likelihood estimator.

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

The Bayesian network structure, on the other hand, must be built iteratively (linkage-learning). It starts with a network without edges and, at each step, adds the edge which better improves some scoring metric (e.g. Bayesian information criterion (BIC) or Bayesian-Dirichlet metric with likelihood equivalence (BDe)).^[14] The scoring metric evaluates the network structure according to its accuracy in modeling the selected population. From the built network, BOA samples new promising solutions as follows: (1) it computes the ancestral ordering for each variable, each node being preceded by its parents; (2) each variable is sampled conditionally to its parents. Given such scenario, every BOA step can be defined as

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

Linkage-tree Genetic Algorithm (LTGA)[edit]

The LTGA^[15] differs from most EDA in the sense it does not explicitly model a probability distribution but only a linkage model, called linkage-tree. A linkage ${\displaystyle T}$ is a set of linkage sets with no probability distribution associated, therefore, there is no way to sample new solutions directly from ${\displaystyle T}$. The linkage model is a linkage-tree produced stored as a Family of sets (FOS).

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

The linkage-tree learning procedure is a hierarchical clustering algorithm, which work as follows. At each step the two closest clusters ${\displaystyle i}$ and ${\displaystyle j}$ are merged, this procedure repeats until only one cluster remains, each subtree is stored as a subset ${\displaystyle \tau \in T_{\text{LT}}}$.

The LTGA uses ${\displaystyle T_{\text{LT}}}$ to guide an "optimal mixing" procedure which resembles a recombination operator but only accepts improving moves. We denote it as ${\displaystyle R_{\text{LTGA}}}$, where the notation ${\displaystyle x[\tau ]\gets y[\tau ]}$ indicates the transfer of the genetic material indexed by ${\displaystyle \tau }$ from ${\displaystyle y}$ to ${\displaystyle x}$.

Algorithm Gene-pool optimal mixing Input: A family of subsets ${\displaystyle T_{\text{LT}}}$ and a population ${\displaystyle P(t)}$ Output: A population ${\displaystyle P(t+1)}$. for each ${\displaystyle x_{i}}$ in ${\displaystyle P(t)}$ do for each ${\displaystyle \tau }$ in ${\displaystyle T_{\text{LT}}}$ do choose a random ${\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 ]}$ if ${\displaystyle f(x_{i})\leq f_{x_{i}}}$ then ${\displaystyle x_{i}[\tau ]:=x_{j}[\tau ]}$ return ${\displaystyle P(t)}$

The LTGA does not implement typical selection operators, instead, selection is performed during recombination. Similar ideas have been usually applied into local-search heuristics and, in this sense, the LTGA can be seen as an hybrid method. In summary, one step of the LTGA is defined as

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

Other[edit]

• Probability collectives (PC)^[16][17]
• Hill climbing with learning (HCwL)^[18]
• Estimation of multivariate normal algorithm (EMNA)^{[citation needed]}
• Estimation of Bayesian networks algorithm (EBNA)^{[citation needed]}
• Stochastic hill climbing with learning by vectors of normal distributions (SHCLVND)^[19]
• Real-coded PBIL^{[citation needed]}
• Selfish Gene Algorithm (SG)^[20]
• Compact Differential Evolution (cDE)^[21] and its variants^{[22][23][24][25][26][27]}
• Compact Particle Swarm Optimization (cPSO)^[28]
• Compact Bacterial Foraging Optimization (cBFO)^[29]
• Probabilistic incremental program evolution (PIPE)^[30]
• Estimation of Gaussian networks algorithm (EGNA)^{[citation needed]}
• Estimation multivariate normal algorithm with thresheld convergence^[31]
• Dependency Structure Matrix Genetic Algorithm (DSMGA)^[32][33]

Related[edit]

• CMA-ES
• Cross-entropy method

References[edit]