Estimativa do algoritmo de distribuição - Estimation of distribution algorithm

Estimativa do algoritmo de distribuição. Para cada iteração i , um sorteio aleatório é realizado para uma população P em uma distribuição PDu . Os parâmetros de distribuição PDe são então estimados usando os pontos PS selecionados . O exemplo ilustrado otimiza uma função objetivo contínua f (X) com um único O ótimo . A amostragem (seguindo uma distribuição normal N ) concentra-se em torno do ótimo conforme se avança no algoritmo de desenrolamento.

Algoritmos de estimativa de distribuição ( EDAs ), às vezes chamados de algoritmos genéticos de construção de modelos probabilísticos (PMBGAs), sãométodos de otimização estocásticos que orientam a busca pelo ótimo através da construção e amostragem de modelos probabilísticos explícitos de soluções candidatas promissoras. A otimização é vista como uma série de atualizações incrementais de um modelo probabilístico, começando com o modelo que codifica uma prévia não informativa sobre as soluções admissíveis e terminando com o modelo que gera apenas os ótimos globais.

Os EDAs pertencem à classe dos algoritmos evolutivos . A principal diferença entre os EDAs e a maioria dos algoritmos evolutivos convencionais é que os algoritmos evolutivos geram novas soluções candidatas usando uma distribuição implícita definida por um ou mais operadores de variação, enquanto os EDAs usam uma distribuição de probabilidade explícita codificada por uma rede Bayesiana , uma distribuição normal multivariada ou outra classe modelo. Da mesma forma que outros algoritmos evolutivos, os EDAs podem ser usados para resolver problemas de otimização definidos em uma série de representações de vetores para expressões LISP estilo S, e a qualidade das soluções candidatas é frequentemente avaliada usando uma ou mais funções objetivo.

O procedimento geral de um EDA é descrito a seguir:

t := 0
initialize model M(0) to represent uniform distribution over admissible solutions
while (termination criteria not met) do
    P := generate N>0 candidate solutions by sampling M(t)
    F := evaluate all candidate solutions in P
    M(t + 1) := adjust_model(P, F, M(t))
    t := t + 1

Usando modelos probabilísticos explícitas em EDAs otimização permitido para resolver viabilizar problemas de otimização que eram notoriamente difícil para a maioria dos algoritmos evolucionários convencionais e técnicas de otimização tradicionais, tais como problemas com altos níveis de epistasia . No entanto, a vantagem dos EDAs é também que esses algoritmos fornecem ao praticante de otimização uma série de modelos probabilísticos que revelam muitas informações sobre o problema que está sendo resolvido. Essa informação pode, por sua vez, ser usada para projetar operadores de vizinhança específicos para o problema para pesquisa local, para desviar execuções futuras de EDAs em um problema semelhante ou para criar um modelo computacional eficiente do problema.

Por exemplo, se a população é representada por sequências de bits de comprimento 4, o EDA pode representar a população de solução promissora usando um único vetor de quatro probabilidades (p1, p2, p3, p4) onde cada componente de p define a probabilidade de que posição sendo um 1. Usando este vetor de probabilidade, é possível criar um número arbitrário de soluções candidatas.

Estimativa de algoritmos de distribuição (EDAs)

Esta seção descreve os modelos construídos por alguns EDAs bem conhecidos de diferentes níveis de complexidade. É sempre assumido uma população na geração , um operador de seleção , um operador de construção de modelos e um operador de amostragem . ${\ displaystyle P (t)}$ ${\ displaystyle t}$ ${\ displaystyle S}$ ${\ displaystyle \ alpha}$ ${\ displaystyle \ beta}$

Fatoração univariada

Os EDAs mais simples assumem que as variáveis de decisão são independentes, ou seja . Portanto, EDAs univariados dependem apenas de estatísticas univariadas e distribuições multivariadas devem ser fatoradas como o produto de distribuições de probabilidade univariadas, ${\ 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}).}$

Essas fatorações são usadas em muitos EDAs diferentes; a seguir, descreveremos alguns deles.

Algoritmo de distribuição marginal univariada (UMDA)

O UMDA é um EDA simples que usa um operador para estimar as probabilidades marginais de uma população selecionada . Ao assumir que contém elementos, produz probabilidades: ${\ 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 \ em 1,2, \ pontos, N.}$

Cada etapa do UMDA pode ser descrita como segue

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

Aprendizagem incremental baseada na população (PBIL)

O PBIL representa a população implicitamente por meio de seu modelo, a partir do qual obtém amostras de novas soluções e atualiza o modelo. Em cada geração, os indivíduos são amostrados e selecionados. Esses indivíduos são então usados para atualizar o modelo da seguinte forma ${\ 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,}$

onde é um parâmetro que define a taxa de aprendizagem , um pequeno valor determina que o modelo anterior deve ser apenas ligeiramente modificado pelas novas soluções amostradas. PBIL pode ser descrito como ${\ displaystyle \ gamma \ in (0,1]}$ ${\ displaystyle p_ {t} (X_ {i})}$

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

Algoritmo genético compacto (cGA)

O CGA, também se baseia nas populações implícitas definidas por distribuições univariadas. Em cada geração , dois indivíduos são amostrados ,. A população é, então, classificados em ordem de aptidão decrescente, com sendo o melhor e ser o pior solução. O CGA estima as probabilidades univariadas da seguinte forma ${\ displaystyle t}$ ${\ displaystyle x, y}$ ${\ displaystyle P (t) = \ beta _ {2} (D (t))}$ ${\ displaystyle P (t)}$ ${\ displaystyle S _ {{\ text {Sort}} (f)} (P (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, \ pontos, N,}$

onde, é uma constante que define a taxa de aprendizagem , geralmente definida como . O CGA pode ser definido como ${\ displaystyle \ gamma \ in (0,1]}$ ${\ displaystyle \ gamma = 1 / N}$

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

Fatoração bivariada

Embora os modelos univariados possam ser calculados de forma eficiente, em muitos casos eles não são representativos o suficiente para fornecer melhor desempenho do que os AGs. Para contornar essa desvantagem, o uso de fatorações bivariadas foi proposto na comunidade EDA, em que dependências entre pares de variáveis poderiam ser modeladas. Uma fatoração bivariada pode ser definida como segue, onde contém uma possível variável dependente de , ie . ${\ 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 _{eu}).}$

Distribuições bivariadas e multivariadas são geralmente representadas como modelos gráficos probabilísticos (gráficos), nos quais as arestas denotam dependências estatísticas (ou probabilidades condicionais) e os vértices denotam variáveis. Para aprender a estrutura de um PGM a partir do data linkage-learning é empregado.

Informações mútuas maximizando o agrupamento de entrada (MIMIC)

O MIMIC fatoriza a distribuição de probabilidade conjunta em um modelo em cadeia que representa dependências sucessivas entre as variáveis. Ele encontra uma permutação das variáveis de decisão,, tal que minimiza a divergência de Kullback-Leibler em relação à distribuição de probabilidade verdadeira, ou seja . MIMIC modela uma distribuição ${\ displaystyle r: i \ mapsto j}$ ${\ displaystyle x_ {r (1)} x_ {r (2)}, \ dots, x_ {r (N)}}$ ${\ 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)}).}$

Novas soluções são amostradas da variável mais à esquerda para a mais à direita, a primeira é gerada de forma independente e as outras de acordo com probabilidades condicionais. Uma vez que a distribuição estimada deve ser recomputada a cada geração, o MIMIC usa populações concretas da seguinte maneira

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

Algoritmo de distribuição marginal bivariada (BMDA)

O BMDA fatoriza a distribuição de probabilidade conjunta em distribuições bivariadas. Primeiro, uma variável escolhida aleatoriamente é adicionada como um nó em um gráfico, a variável mais dependente de uma daquelas no gráfico é escolhida entre aquelas que ainda não estão no gráfico, este procedimento é repetido até que nenhuma variável remanescente dependa de qualquer variável no gráfico (verificado de acordo com um valor limite).

O modelo resultante é uma floresta com várias árvores enraizadas em nós . Considerando as variáveis não raiz, o BMDA estima uma distribuição fatorada na qual as variáveis raiz podem ser amostradas independentemente, enquanto todas as outras devem ser condicionadas à variável pai . ${\ displaystyle \ Upsilon _ {t}}$ ${\ displaystyle I_ {t}}$ ${\ 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}).}$

Cada etapa do BMDA é definida como segue

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

Fatoração multivariada

O próximo estágio de desenvolvimento de EDAs foi o uso de fatorações multivariadas. Nesse caso, a distribuição de probabilidade conjunta é geralmente fatorada em uma série de componentes de tamanho limitado . ${\ 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})}$

O aprendizado de PGMs que codificam distribuições multivariadas é uma tarefa computacionalmente cara, portanto, é comum para EDAs estimar estatísticas multivariadas a partir de estatísticas bivariadas. Tal relaxamento permite que PGM seja construído em tempo polinomial em ; no entanto, também limita a generalidade de tais EDAs. ${\ displaystyle N}$

Algoritmo genético compacto estendido (eCGA)

O ECGA foi um dos primeiros EDA a empregar fatorações multivariadas, nas quais dependências de alta ordem entre as variáveis de decisão podem ser modeladas. Sua abordagem fatoriza a distribuição de probabilidade conjunta no produto de distribuições marginais multivariadas. Assume é um conjunto de subconjuntos, em que cada é um conjunto de ligações, contendo variáveis. A distribuição de probabilidade conjunta fatorada é representada da seguinte forma ${\ displaystyle T _ {\ text {eCGA}} = \ {\ tau _ {1}, \ dots, \ tau _ {\ Psi} \}}$ ${\ displaystyle \ tau \ in T _ {\ text {eCGA}}}$ ${\ displaystyle | \ tau | \ leq K}$

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

O ECGA popularizou o termo "aprendizagem de ligação" como denotando procedimentos que identificam conjuntos de ligação. Seu procedimento de linkage-learning baseia-se em duas medidas: (1) a Complexidade do Modelo (MC) e (2) a Complexidade da População Comprimida (CPC). O MC quantifica o tamanho da representação do modelo em termos de número de bits necessários para armazenar todas as probabilidades marginais

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

O CPC, por outro lado, quantifica a compressão de dados em termos de entropia da distribuição marginal sobre todas as partições, onde é o tamanho da população selecionada, é o número de variáveis de decisão no conjunto de ligação e é a entropia conjunta das variáveis em ${\ displaystyle \ lambda}$ ${\ displaystyle | \ tau |}$ ${\ displaystyle \ tau}$ ${\ displaystyle H (\ tau)}$ ${\ displaystyle \ tau}$

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

O linkage-learning em ECGA funciona da seguinte forma: (1) Insira cada variável em um cluster, (2) calcule CCC = MC + CPC dos conjuntos de ligação atuais, (3) verifique o aumento no CCC fornecido pela união de pares de clusters, (4) efetivamente junta-se aos clusters com maior melhoria de CCC. Este procedimento é repetido até que nenhuma melhoria no CCC seja possível e produza um modelo de ligação . O ECGA trabalha com populações concretas, portanto, utilizando a distribuição fatorada modelada pelo ECGA, pode ser descrito como ${\ displaystyle T _ {\ text {eCGA}}}$

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

Algoritmo de otimização bayesiana (BOA)

O BOA usa redes bayesianas para modelar e amostrar soluções promissoras. Redes bayesianas são grafos acíclicos direcionados, com nós representando variáveis e arestas representando probabilidades condicionais entre pares de variáveis. O valor de uma variável pode ser condicionado a um máximo de outras variáveis, definidas em . O BOA constrói um PGM que codifica uma distribuição conjunta fatorada, na qual os parâmetros da rede, ou seja, as probabilidades condicionais, são estimados a partir da população selecionada usando o estimador de máxima verossimilhança. ${\ displaystyle x_ {i}}$ ${\ displaystyle K}$ ${\ displaystyle \ pi _ {i}}$

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

A estrutura da rede bayesiana, por outro lado, deve ser construída iterativamente (linkage-learning). Ele começa com uma rede sem arestas e, a cada etapa, adiciona a aresta que melhor melhora alguma métrica de pontuação (por exemplo, critério de informação Bayesiano (BIC) ou métrica Bayesiana-Dirichlet com equivalência de verossimilhança (BDe)). A métrica de pontuação avalia a estrutura da rede de acordo com sua precisão na modelagem da população selecionada. A partir da rede construída, o BOA mostra novas soluções promissoras como segue: (1) ele calcula a ordem ancestral para cada variável, cada nó sendo precedido por seus pais; (2) cada variável é amostrada condicionalmente a seus pais. Diante desse cenário, cada etapa do BOA pode ser definida como

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

Algoritmo Genético de Árvore de Ligação (LTGA)

O LTGA difere da maioria dos EDA no sentido de que não modela explicitamente uma distribuição de probabilidade, mas apenas um modelo de ligação, denominado árvore de ligação. Uma ligação é um conjunto de conjuntos de ligações sem distribuição de probabilidade associada, portanto, não há como obter amostras de novas soluções diretamente . O modelo de ligação é uma árvore de ligação produzida e armazenada como uma família de conjuntos (FOS). ${\ displaystyle T}$ ${\ displaystyle T}$

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

O procedimento de aprendizagem da árvore de ligação é um algoritmo de agrupamento hierárquico , que funciona da seguinte maneira. Em cada passo, os dois mais próximos aglomerados e são fundidas, este procedimento se repete até sobrar apenas um agrupamento, cada sub-árvore é armazenado como um subconjunto . ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle \ tau \ in T _ {\ text {LT}}}$

O LTGA usa para guiar um procedimento de "mistura ideal" que se assemelha a um operador de recombinação, mas só aceita movimentos de melhoria. Nós o denotamos como , onde a notação indica a transferência do material genético indexado por de para . ${\ displaystyle T _ {\ text {LT}}}$ ${\ displaystyle R _ {\ text {LTGA}}}$ ${\ displaystyle x [\ tau] \ obtém y [\ tau]}$ ${\ displaystyle \ tau}$ ${\ displaystyle y}$ ${\ displaystyle x}$

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

"←" denota atribuição . Por exemplo, " maior ← item " significa que o valor do maior muda para o valor do item .
" return " termina o algoritmo e produz o seguinte valor.

O LTGA não implementa operadores de seleção típicos; em vez disso, a seleção é realizada durante a recombinação. Idéias semelhantes têm sido geralmente aplicadas em heurísticas de busca local e, nesse sentido, o LTGA pode ser visto como um método híbrido. Em resumo, uma etapa do LTGA é definida como

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

De outros

Coletivos de probabilidade (PC)
Alpinismo com aprendizagem (HCwL)
Estimativa de algoritmo normal multivariado (EMNA)
Estimativa do algoritmo de redes bayesianas (EBNA)
Escalada estocástica com aprendizagem por vetores de distribuições normais (SHCLVND)
PBIL codificado real
Algoritmo do gene egoísta (SG)
Evolução diferencial compacta (cDE) e suas variantes
Otimização de enxame de partículas compactas (cPSO)
Otimização de forrageamento bacteriano compacto (cBFO)
Evolução do programa incremental probabilístico (PIPE)
Estimativa do algoritmo de redes gaussianas (EGNA)
Algoritmo normal multivariado de estimativa com convergência de limiar
Algoritmo Genético de Matriz de Estrutura de Dependência (DSMGA)

Languages

In other projects