Algoritmos de estimação de distribuição (AED) são métodos evolutivos que utilizam técnicas de estimação de distribuição ao invés de operadores genéticos A.R. Gonçalves. Otimização em ambientes dinâmicos com variáveis contínuas empregando algoritmos de estimação de distribuição. Dissertação de mestrado. Faculdade de Engenharia Elétrica e de Computação. Universidade Estadual de Campinas (Unicamp). 2011. .
thumb|Fluxograma de um algoritmo de estimação de distribuição.
AED's são consequência dos algoritmos genéticos, sendo motivados pela deficiência destes, principalmente pela sua incapacidade de representar e manipular as dependências entre as variáveis. Este problema é conhecido como linkage problem.
Em seu trabalho seminal sobre algoritmos genéticos, Holland J.H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Harbor,1975. já havia reconhecido que, se a interação das variáveis fosse utilizada, certamente traria benefícios aos algoritmos genéticos. Esta fonte de informação, até então inexplorada, foi chamada de informação de ligação (linkage information).
Assim, para contornar estes obstáculos dos algoritmos genéticos, os AEDs representam explicitamente as dependências entre as variáveis através de modelos probabilísticos, como desde simples representação em vetores de probabilidades até modelos mais complexos, como rede bayesiana, estruturas em árvore (grafo), cadeias de Markov, entre outras. Os AEDs utilizam estes modelos probabilísticos como guias para desempenhar a busca em um determinado espaço de soluções.
Considere o seguinte exemplo de um AED. Seja uma população representada por vetores binários de comprimento 4. O AED pode empregar um único vetor composto por 4 probabilidades () onde cada é a probabilidade da posição receber o valor 1. Usando este vetor de probabilidades é possível criar qualquer quantidade de soluções candidatas. Ao fim de cada geração, este vetor de probabilidades vai sendo atualizado segundo os melhores indivíduos da geração corrente.
Definição Diferentemente dos algoritmos genéticos comuns, que utilizam operadores de recombinação e mutação para gerar novos indivíduos da população, os algoritmos de estimação de distribuição fazem uso de informações extraídas do conjunto de soluções promissoras presentes na população daquela geração. Uma maneira de utilizar a informação global sobre um conjunto de soluções promissoras é estimar sua distribuição e usar esta estimativa para gerar novos indivíduos. Os algoritmos que fazem uso deste princípio são chamados de Algoritmos de Estimação de Distribuição - AED (do inglês Estimation of distribution algorithm) H. Mühlenbein & G. Paaß. From recombination of genes to the estimation of distributions I. Binary parameters. Parallel Problem Solving from Nature-PPSN IV, pages 178–187, 1996.. Essas distribuições contemplam diretamente as interações das variáveis que compõem o espaço de busca.
Formalmente, pode-se definir um AED como uma quádrupla da forma :
onde, : método para codificação dos indivíduos; : população de n indivíduos codificados; : operador estocástico (ou determinístico) para seleção; : Estimador da distribuição das melhores soluções (na iteração corrente).
Nota-se a eliminação dos componentes de recombinação, de mutação e suas probabilidades, em relação ao algoritmo genético (AG). No entanto, a tarefa de estimação deverá ser feita levando em conta a complexidade do modelo utilizado, como será visto nas seções seguintes. Dependendo do modelo de estimação utilizado, alguns parâmetros adicionais deverão ser informados.
Diferentemente do AG, em que as inter-relações (blocos construtivos) das variáveis representando os indivíduos são mantidas implicitamente, nos AEDs essas relações são expressadas explicitamente através da distribuição de probabilidade conjunta associada aos indivíduos selecionados em cada iteração.
A sequência estrutural do AED é bastante similar ao AG, diferindo na maneira como são gerados novos indivíduos. A seleção das soluções promissoras pode ser realizada de forma determinística ou estocástica, privilegiando indivíduos com melhores valores de fitness. A população pode ser amostrada integralmente a partir da distribuição de probabilidade; ou, visando maior exploração do ambiente, estipular uma porcentagem para adição de novos indivíduos gerados aleatoriamente; ou ainda substituindo alguns indivíduos da população anterior pelos novos indivíduos amostrados pela distribuição.
Gera população inicial aleatoriamente enquanto condição de parada não for satisfeita faça Avalição: Seleção: Estimação da distribuição de probabilidades, , do conjunto selecionado Amostre a nova população a partir de
retorne o melhor indivíduo encontrado.
Exemplos de critérios de parada são: um número fixo de iterações, um número fixo de diferentes avaliações de fitness dos indivíduos e ausência de melhorias do melhor indivíduo em um certo número de iterações subsequentes.
O passo fundamental nesta classe de algoritmos é como estimar a distribuição das soluções promissoras. Na realidade, a estimação da distribuição de probabilidade conjunta associada às variáveis, a partir de soluções promissoras selecionadas, constitui o gargalo destes algoritmos. Será necessário então um balanço entre a precisão desta estimação e seu custo computacional.
Tipos de AEDs Os algoritmos presentes nesta classe diferenciam-se basicamente pela forma como a estimação é realizada, sendo classificados de acordo com a complexidade do modelo probabilístico utilizado: variáveis sem dependência; dependência aos pares; dependência multivariada e modelos de mistura P. Larrañaga, J.A. Lozano & E. Bengoetxea. Estimation of distribution algorithms based on multivariate normal and Gaussian networks. Technical Report KZZA-IK-1-01, Department of Computer Science and Artificial Intelligence, University of the Basque Country, 2001..
A seguir, serão apresentadas algumas abordagens de AEDs, tanto para problemas de otimização em espaços discretos, quanto em espaços contínuos. Esta revisão será organizada considerando os quatro níveis de complexidade do modelo probabilístico, citados acima e utilizados para extrair as interdependências das variáveis que formam o espaço de busca.
Modelos sem dependências A maneira mais simples de estimativa é supor que as variáveis do problema são independentes, ou seja, não há qualquer tipo de relação entre elas (veja figura ao lado). Formalmente, a distribuição de probabilidade conjunta é fatorizada como o produto de n distribuições de probabilidades independentes e univariadas:
onde x é o conjunto de soluções promissoras, em um espaço de busca n-dimensional, selecionadas para a estimação.
O modelo de estimação utilizado para gerar novos indivíduos contém o conjunto de frequências de valores das variáveis que representam a solução no conjunto selecionado. Assim, estas frequências são usadas para guiar a busca, gerando novos indivíduos, variável por variável de acordo com os valores de frequência. Dessa forma, os blocos construtivos de primeira ordem são reproduzidos e mesclados eficientemente M. Pelikan, D.E. Goldberg & F.G. Lobo. A survey of optimization by building and using probabilistic models. Computational optimization and applications, 21(1):5–20, 2002.. Algoritmos baseados neste mecanismo são indicados para problemas em que as variáveis não possuem interação mútua G. Harik, E. Cantú-Paz, D.E. Goldberg & B.L. Miller. The Gambler’s Ruin Problem, Genetic Algorithms, and the Sizing of Populations. In Proceedings of the IEEE Conference on Evolutionary Computation, pages 7–12, 1997. .
thumb|AED sem dependência. Os nós representam as variáveis do problema e a ausência de arestas entre os nós indica que não há dependência entre as variáveis.
Exemplos de algoritmos que fazem uso deste modelo probabilístico, no espaço de variáveis discretas, são: o UMDA ( Univariate Marginal Distribution Algorithm) , onde cada distribuição marginal univariada é estimada pelas respectivas frequências marginais; o PBIL (Population Based Incremental Learning) S. Baluja. Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning. Technical Report CMU-CS-94-163, Carnegie Mellon University, Pittsburgh, PA, 1994., que utiliza a regra de aprendizado hebbiano para a atualização do vetor de probabilidades, a partir do conjunto de soluções selecionadas; e o CGA (Compact Genetic Algorithm) G.R. Harik, F.G. Lobo & D.E. Goldberg. The compact genetic algorithm. In Proceedings of the IEEE Conference of Evolutionary Computation, pages 523–528, 1998., que atualiza o vetor de probabilidades p(x) a partir de uma competição entre dois indivíduos amostrados com base em p(x), sendo p(x) deslocado em direção ao indivíduo vencedor.
Para o caso contínuo, supõe-se que a função densidade de probabilidade conjunta segue uma distribuição normal n-dimensional, que é fatorizada pelo produto de n densidades normais unidimensionais e independentes . O problema então consiste na estimação dos parâmetros da distribuição. Formalmente, para o caso de uma distribuição normal, a função densidade de probabilidades é descrita por:
onde denota a média da i-ésima variável e sua variância. O algoritmo UMDA foi estendido ao espaço de variáveis contínuas (UMDA) P. Larrañaga, R. Etxeberria, J.A. Lozano & J.M. Pena. Optimization by learning and simulation of Bayesian and Gaussian networks. Technical Report EHU-KZAAIK-4, University of the Basque Country, 1999.. Aqui, a cada iteração o algoritmo busca por uma função densidade que melhor se ajuste à variável, obtendo seus parâmetros pela estimativa da máxima verossimilhança. Já o algoritmo SHCLVND (Stochastic Hill Climbing with Learning by Vectors of Normal Distributions) S. Rudlof & M. Köppen. Stochastic hill climbing with learning by vectors of normal distributions. In Proceedings of the American Association for Artificial Intelligence, Nagoya, Japan, 1996. atualiza os parâmetros da distribuição normal, média e variância, pela regra de Hebb para a média e uma política de redução para a variância.
Modelos com dependência aos pares Embora a suposição de independência entre as variáveis seja satisfeita para alguns problemas, nem sempre esta hipótese é verificada, sendo então necessário levar em consideração algumas dependências. Quando a dependência aos pares é considerada, estabelece-se um compromisso entre a precisão e o custo computacional. A distribuição de probabilidades conjunta é fatorizada como:
onde é a variável da qual é dependente.
Enquanto os algoritmos que consideram variáveis independentes estimam apenas os parâmetros do modelo, na dependência aos pares a aprendizagem paramétrica é estendida para a aprendizagem da estrutura do modelo de dependência (um grafo direcionado).
No contexto discreto, o MIMIC (Mutual Information Maximizing Input Clustering) J.S. De Bonet, C.L. Isbell & P. Viola. MIMIC: Finding optima by estimating probability densities. In Advances in Neural Information Processing Systems, volume 4, pages 424–430. The MIT Press, 1997. usa uma cadeia simples de distribuição (veja figura a seguir) que maximiza a informação mútua das variáveis vizinhas (posições na cadeia), através de uma abordagem gulosa, que, embora eficiente, não garante a otimalidade global. A utilização de árvores de dependência foi formalizada por S. Baluja & S. Davies. Using optimal dependency-trees for combinatorial optimization: Learning the structure of the search space. In Proceedings of 14th International Conference on Machine Learning, pages 30–38. Morgan Kaufmann, 1997.S. Baluja & S. Davies. Fast Probabilistic Modeling for Combinatorial Optimization. In Proceedings of the American Association for Artificial Intelligence, pages 469–476, 1998. no COMIT (Combining Optimizers with Mutual Information Trees), que utiliza uma rede bayesiana