Algoritmo de estimativa de distribuição

Os algoritmos de estimativa de distribuição ( Estimation of Distribution Algorithms , EDA , em inglês) são uma metaheurística familiar inspirada em algoritmos genéticos . Eles são usados ​​para resolver problemas de otimização, através da manipulação de uma função de amostragem que descreve a qualidade das soluções possíveis. Como todas as metaheurísticas que usam uma população de pontos, elas são iterativas .

Ao contrário dos algoritmos evolutivos “clássicos”, o coração do método consiste em estimar as relações entre as diferentes variáveis ​​de um problema de otimização, graças à estimação de uma distribuição de probabilidade, associada a cada ponto da amostra. Portanto, não utilizam operadores de crossover ou mutação, sendo a amostra construída diretamente a partir dos parâmetros de distribuição, estimados na iteração anterior.

Algoritmo

O vocabulário relacionado aos algoritmos de estimativa de distribuição é emprestado daquele dos algoritmos evolutivos, portanto, falaremos de "população de indivíduos" em vez de "amostra de pontos", ou "aptidão" em vez de "função objetivo", no entanto, todos esses termos têm o mesmo significado.

Algoritmo geral

O algoritmo básico procede da seguinte forma para cada iteração:

  1. seleção aleatória de um conjunto de pontos de acordo com uma determinada distribuição de probabilidade,
  2. seleção dos melhores pontos,
  3. extração dos parâmetros da distribuição de probabilidade descrevendo a distribuição desses pontos.

Mais especificamente, o algoritmo procede da seguinte forma:

Selecione aleatoriamente M indivíduos, para formar uma população D 0 .
i = 0
Enquanto um critério de parada não for verificado:

i = i + 1
Selecione N indivíduos (com N < M ) na população acima ( D i -1 ) para formar a população . Estime uma distribuição de probabilidade P i ( x ) , descrevendo a distribuição da população D
S
i -1.
Selecione aleatoriamente M indivíduos de P i ( x ) .

Fim do ciclo.

Exemplo para o problema "um máximo"

No problema “um máximo”, tentamos maximizar o número de 1 em um determinado número de dimensões. Para um problema tridimensional, uma solução x 1 = {1,1,0} terá, portanto, uma qualidade melhor do que uma solução x 2 = {0,1,0} , sendo o ótimo i * = {1,1, 1} . Portanto, procuramos maximizar uma função , onde x i pode assumir o valor 0 ou 1.

A primeira etapa consiste em desenhar indivíduos aleatoriamente, com para cada variável, uma chance em duas de tirar um 1 ou um 0. Em outras palavras, usamos uma distribuição de probabilidade , onde p 0 ( x i ) é a probabilidade de cada elemento é igual a 1. A distribuição é, portanto, fatorada como um produto de 3 distribuições marginais de Bernoulli univariadas , com parâmetro 0,5.

Exemplo de desenho da população D 0 , com uma população de 6 indivíduos, a última linha indica a probabilidade p ( x ) para cada variável:

eu x 1 x 2 x 3 f ( x )
1 0 1 0 1
2 0 1 0 1
3 1 0 1 2
4 1 0 1 2
5 0 1 1 2
6 1 0 0 1
p ( x ) 0,5 0,5 0,5

A próxima etapa é selecionar os melhores indivíduos, para formar DS
1. Em nosso exemplo, é simplesmente uma questão de manter apenas os 3 melhores indivíduos:

eu x 1 x 2 x 3 f ( x )
3 1 0 1 2
4 1 0 1 2
5 0 1 1 2
p ( x ) 0,7 0,3 1

Vemos que os três parâmetros ( p i ( x ) ) que caracterizam a distribuição de probabilidade ( DS
1) foram alterados após a seleção. Usando essa nova distribuição, podemos derivar uma nova população:

eu x 1 x 2 x 3 f ( x )
1 1 1 1 3
2 0 1 1 2
3 1 0 1 2
4 1 0 1 2
5 1 0 1 2
6 0 0 1 1
p ( x ) 0,7 0,3 1

E assim por diante até que um critério de parada seja verificado (por exemplo, quando todos os indivíduos estão no ótimo, como o indivíduo 1 na tabela acima).

Comportamento

Foi demonstrado (geralmente usando modelos de Markov ou sistemas dinâmicos ) que a maioria das versões para otimização combinatória são convergentes (ou seja, eles podem encontrar o ótimo em um tempo acabado). Para as variantes que tratam de otimização em variáveis ​​reais, a convergência é ainda mais fácil de demonstrar, desde que os modelos de distribuições utilizados permitam ergodicidade (ou seja, é então possível chegar a qualquer solução a cada movimento), mas frequentemente ficamos satisfeitos com uma quase ergodicidade (se as metaheurísticas podem chegar a qualquer solução em um número finito de movimentos).

Modelos de distribuição

O comportamento dos algoritmos de estimativa de distribuição depende muito da escolha do modelo de distribuição usado para descrever o estado da população. Pedro Larrañaga e seus colegas propõem classificar esses modelos de acordo com o grau em que levam em consideração as dependências entre as variáveis:

No caso de modelos sem dependências, a distribuição de probabilidade é construída a partir de um conjunto de distribuições definidas em uma única variável. Em outras palavras, a distribuição é fatorada a partir de distribuições univariadas e independentes em cada variável.

O exemplo dado acima para o problema “um máximo” cai nesta categoria: a probabilidade de ter 1 na variável x 2 não influencia a probabilidade de ter 1 na variável x 3 , se n não houver correlação entre o duas variáveis.

Os modelos sem dependências são fáceis de manusear, mas têm a desvantagem de não serem muito representativos de problemas de otimização difíceis, em que as dependências costumam ser numerosas. É possível lidar com dependências fora do modelo de distribuição, mas o algoritmo pode se tornar mais difícil de manipular.

Nos tipos de modelos com dependências de duas variantes, é possível usar distribuições de duas variantes como base. Larrañaga et al. em seguida, proponha classificar a aprendizagem na noção de estrutura .

Em modelos de dependência multivariante, todas as dependências são consideradas no modelo.

O mundo da estimativa de distribuição

Histórico

Variantes

As variantes mais conhecidas da distribuição são a população de aprendizagem incremental estimada ("  Population Based Incremental Learning  " PBIL), o algoritmo de distribuição marginal univariada ("  Univariate Marginal Distribution Algorithm  " UMDA) ou o algoritmo genético compacto ("  Compact Genetic Algorithm  ", CGA) .

Existem também variantes que usam mecanismos de particionamento de dados para otimização multimodal, adaptações para computação paralela, etc.

Devido ao lugar central no lado probabilístico, a estimativa de distribuição compartilha muitos pontos em comum com as estratégias de evolução , uma das primeiras metaheurísticas propostas e algoritmos de colônia de formigas . Mas também podemos apontar as semelhanças com o recozimento simulado (que usa a função objetivo como uma distribuição de probabilidade para construir uma amostra) e algoritmos genéticos , a partir dos quais os algoritmos de estimativa de distribuição são derivados, e dos quais sempre usam os operadores de seleção.

Da mesma forma, encontramos muitos pontos em comum entre essas metaheurísticas de otimização e ferramentas de aprendizado de máquina , como métodos que usam árvores de decisão ou modelos de mistura gaussiana . A diferença às vezes é difícil de identificar; pode-se de fato encontrar metaheurísticas realizando tarefas de aprendizagem, métodos de aprendizagem resolvendo problemas de otimização considerados difíceis (no sentido da teoria da complexidade ) ou ferramentas de aprendizagem usadas dentro da metaheurística.

Referências

Origens

  1. Rechenberg, I., Caminho da solução cibernética de um problema experimental , Royal Aircraft Establishment Library Translation, 1965
  2. Holland, John H., Adaptation in Natural and Artificial Systems , University of Michigan Press, Ann Arbor, 1975
  3. M. Dorigo, Otimização, Aprendizagem e Algoritmos Naturais , Tese de Doutorado, Politécnico de Milão, Itália, 1992.
  4. S. Baluja. Aprendizagem incremental baseada na população: um método para integrar a otimização da função baseada em pesquisa genética e a aprendizagem competitiva . Relatório Técnico CMU-CS-94-163, Carnegie Mellon University, 1994
  5. Mühlenbein, H., Paaß, G., From recombination of genes to the estimation of distribution I. Parâmetros binários , Lectures Notes in Computer Science 1141: Parallel Problem Solving from Nature, tomo PPSN IV, páginas 178--187, 1996

Veja também