b"\n_START_ARTICLE_\nAlgoritmos de estima\xc3\xa7\xc3\xa3o de distribui\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nAlgoritmos de estima\xc3\xa7\xc3\xa3o de distribui\xc3\xa7\xc3\xa3o (AED) s\xc3\xa3o m\xc3\xa9todos evolutivos que utilizam t\xc3\xa9cnicas de estima\xc3\xa7\xc3\xa3o de distribui\xc3\xa7\xc3\xa3o ao inv\xc3\xa9s de operadores gen\xc3\xa9ticos ._NEWLINE_AED's s\xc3\xa3o consequ\xc3\xaancia dos algoritmos gen\xc3\xa9ticos, sendo motivados pela defici\xc3\xaancia destes, principalmente pela sua incapacidade de representar e manipular as depend\xc3\xaancias entre as vari\xc3\xa1veis. Este problema \xc3\xa9 conhecido como linkage problem._NEWLINE_Em seu trabalho seminal sobre algoritmos gen\xc3\xa9ticos, Holland  j\xc3\xa1 havia reconhecido que, se a intera\xc3\xa7\xc3\xa3o das vari\xc3\xa1veis fosse utilizada, certamente traria benef\xc3\xadcios aos algoritmos gen\xc3\xa9ticos. Esta fonte de informa\xc3\xa7\xc3\xa3o, at\xc3\xa9 ent\xc3\xa3o inexplorada, foi chamada de informa\xc3\xa7\xc3\xa3o de liga\xc3\xa7\xc3\xa3o (linkage information)._NEWLINE_Assim, para contornar estes obst\xc3\xa1culos dos algoritmos gen\xc3\xa9ticos, os AEDs representam explicitamente as depend\xc3\xaancias entre as vari\xc3\xa1veis atrav\xc3\xa9s de modelos probabil\xc3\xadsticos, como desde simples representa\xc3\xa7\xc3\xa3o em vetores de probabilidades at\xc3\xa9 modelos mais complexos, como rede bayesiana, estruturas em \xc3\xa1rvore (grafo), cadeias de Markov, entre outras. Os AEDs utilizam estes modelos probabil\xc3\xadsticos como guias para desempenhar a busca em um determinado espa\xc3\xa7o de solu\xc3\xa7\xc3\xb5es._NEWLINE_Considere o seguinte exemplo de um AED. Seja uma popula\xc3\xa7\xc3\xa3o representada por vetores bin\xc3\xa1rios de comprimento 4. O AED pode empregar um \xc3\xbanico vetor composto por 4 probabilidades () onde cada  \xc3\xa9 a probabilidade da posi\xc3\xa7\xc3\xa3o  receber o valor 1. Usando este vetor de probabilidades \xc3\xa9 poss\xc3\xadvel criar qualquer quantidade de solu\xc3\xa7\xc3\xb5es candidatas. Ao fim de cada gera\xc3\xa7\xc3\xa3o, este vetor de probabilidades vai sendo atualizado segundo os melhores indiv\xc3\xadduos da gera\xc3\xa7\xc3\xa3o corrente.\n_START_SECTION_\nTipos de AEDs\n_START_PARAGRAPH_\nOs algoritmos presentes nesta classe diferenciam-se basicamente pela forma como a estima\xc3\xa7\xc3\xa3o \xc3\xa9 realizada, sendo classificados_NEWLINE_de acordo com a complexidade do modelo probabil\xc3\xadstico utilizado: vari\xc3\xa1veis sem depend\xc3\xaancia; depend\xc3\xaancia aos pares; depend\xc3\xaancia_NEWLINE_multivariada e modelos de mistura ._NEWLINE_A seguir, ser\xc3\xa3o apresentadas algumas abordagens de AEDs, tanto para problemas de otimiza\xc3\xa7\xc3\xa3o em espa\xc3\xa7os_NEWLINE_ discretos, quanto em espa\xc3\xa7os cont\xc3\xadnuos. Esta revis\xc3\xa3o ser\xc3\xa1 organizada considerando os quatro n\xc3\xadveis_NEWLINE_de complexidade do modelo probabil\xc3\xadstico, citados acima e utilizados para extrair as interdepend\xc3\xaancias_NEWLINE_das vari\xc3\xa1veis que formam o espa\xc3\xa7o de busca.\n_START_SECTION_\nModelos sem depend\xc3\xaancias\n_START_PARAGRAPH_\nA maneira mais simples de estimativa \xc3\xa9 supor que as vari\xc3\xa1veis do problema s\xc3\xa3o independentes, ou seja, n\xc3\xa3o h\xc3\xa1_NEWLINE_qualquer tipo de rela\xc3\xa7\xc3\xa3o entre elas (veja figura ao lado). Formalmente, a distribui\xc3\xa7\xc3\xa3o_NEWLINE_de probabilidade conjunta \xc3\xa9 fatorizada como o produto de n distribui\xc3\xa7\xc3\xb5es de probabilidades independentes e univariadas:_NEWLINE_onde x \xc3\xa9 o conjunto de solu\xc3\xa7\xc3\xb5es promissoras, em um espa\xc3\xa7o de busca n-dimensional,_NEWLINE_selecionadas para a estima\xc3\xa7\xc3\xa3o._NEWLINE_O modelo de estima\xc3\xa7\xc3\xa3o utilizado para gerar novos indiv\xc3\xadduos cont\xc3\xa9m o conjunto de frequ\xc3\xaancias de_NEWLINE_valores das vari\xc3\xa1veis que representam a solu\xc3\xa7\xc3\xa3o no conjunto selecionado. Assim, estas frequ\xc3\xaancias_NEWLINE_s\xc3\xa3o usadas para guiar a busca, gerando novos indiv\xc3\xadduos, vari\xc3\xa1vel por vari\xc3\xa1vel de acordo com_NEWLINE_os valores de frequ\xc3\xaancia. Dessa forma, os blocos construtivos de primeira ordem s\xc3\xa3o reproduzidos_NEWLINE_e mesclados eficientemente . Algoritmos baseados neste mecanismo s\xc3\xa3o indicados_NEWLINE_para problemas em que as vari\xc3\xa1veis n\xc3\xa3o possuem intera\xc3\xa7\xc3\xa3o m\xc3\xbatua  ._NEWLINE_Exemplos de algoritmos que fazem uso deste modelo probabil\xc3\xadstico, no espa\xc3\xa7o de vari\xc3\xa1veis discretas,_NEWLINE_s\xc3\xa3o: o UMDA ( Univariate Marginal Distribution Algorithm) , onde cada_NEWLINE_distribui\xc3\xa7\xc3\xa3o marginal univariada \xc3\xa9 estimada pelas respectivas frequ\xc3\xaancias marginais; o PBIL_NEWLINE_(Population Based Incremental Learning) , que utiliza a regra de aprendizado_NEWLINE_hebbiano para a atualiza\xc3\xa7\xc3\xa3o do vetor de probabilidades, a partir do conjunto de solu\xc3\xa7\xc3\xb5es selecionadas;_NEWLINE_e o CGA (Compact Genetic Algorithm) , que atualiza o vetor de probabilidades p(x) a partir de_NEWLINE_uma competi\xc3\xa7\xc3\xa3o entre dois indiv\xc3\xadduos amostrados com base em p(x), sendo p(x) deslocado em dire\xc3\xa7\xc3\xa3o ao indiv\xc3\xadduo vencedor._NEWLINE_Para o caso cont\xc3\xadnuo, sup\xc3\xb5e-se que a fun\xc3\xa7\xc3\xa3o densidade de probabilidade conjunta segue uma distribui\xc3\xa7\xc3\xa3o normal n-dimensional,_NEWLINE_que \xc3\xa9 fatorizada pelo produto de n densidades normais unidimensionais e independentes . O problema_NEWLINE_ent\xc3\xa3o consiste na estima\xc3\xa7\xc3\xa3o dos par\xc3\xa2metros da distribui\xc3\xa7\xc3\xa3o. Formalmente, para o caso de uma distribui\xc3\xa7\xc3\xa3o normal, a fun\xc3\xa7\xc3\xa3o densidade de probabilidades \xc3\xa9 descrita por:_NEWLINE_onde  denota a m\xc3\xa9dia da i-\xc3\xa9sima vari\xc3\xa1vel e  sua vari\xc3\xa2ncia._NEWLINE_O algoritmo UMDA foi estendido ao espa\xc3\xa7o de vari\xc3\xa1veis cont\xc3\xadnuas (UMDA) . Aqui, a cada itera\xc3\xa7\xc3\xa3o o algoritmo busca por uma fun\xc3\xa7\xc3\xa3o densidade que melhor se ajuste \xc3\xa0 vari\xc3\xa1vel,_NEWLINE_obtendo seus par\xc3\xa2metros pela estimativa da m\xc3\xa1xima verossimilhan\xc3\xa7a. J\xc3\xa1 o algoritmo SHCLVND_NEWLINE_(Stochastic Hill Climbing with Learning by Vectors of Normal Distributions) _NEWLINE_atualiza os par\xc3\xa2metros da distribui\xc3\xa7\xc3\xa3o normal, m\xc3\xa9dia e vari\xc3\xa2ncia, pela regra de Hebb para a m\xc3\xa9dia_NEWLINE_e uma pol\xc3\xadtica de redu\xc3\xa7\xc3\xa3o para a vari\xc3\xa2ncia.\n_START_SECTION_\nModelos com depend\xc3\xaancia aos pares\n_START_PARAGRAPH_\nEmbora a suposi\xc3\xa7\xc3\xa3o de independ\xc3\xaancia entre as vari\xc3\xa1veis seja satisfeita para alguns problemas, nem sempre esta hip\xc3\xb3tese_NEWLINE_\xc3\xa9 verificada, sendo ent\xc3\xa3o necess\xc3\xa1rio levar em considera\xc3\xa7\xc3\xa3o algumas depend\xc3\xaancias. Quando a depend\xc3\xaancia_NEWLINE_aos pares \xc3\xa9 considerada, estabelece-se um compromisso entre a precis\xc3\xa3o e o custo computacional._NEWLINE_A distribui\xc3\xa7\xc3\xa3o de probabilidades conjunta \xc3\xa9 fatorizada como:_NEWLINE_onde  \xc3\xa9 a vari\xc3\xa1vel da qual  \xc3\xa9 dependente._NEWLINE_Enquanto os algoritmos que consideram vari\xc3\xa1veis independentes estimam apenas os par\xc3\xa2metros_NEWLINE_do modelo, na depend\xc3\xaancia aos pares a aprendizagem param\xc3\xa9trica \xc3\xa9 estendida para a aprendizagem_NEWLINE_da estrutura do modelo de depend\xc3\xaancia (um grafo direcionado)._NEWLINE_No contexto discreto, o MIMIC (Mutual Information Maximizing Input Clustering)_NEWLINE_ usa uma cadeia simples de distribui\xc3\xa7\xc3\xa3o (veja figura a seguir)_NEWLINE_que maximiza a informa\xc3\xa7\xc3\xa3o m\xc3\xbatua das vari\xc3\xa1veis vizinhas (posi\xc3\xa7\xc3\xb5es na cadeia), atrav\xc3\xa9s de uma_NEWLINE_abordagem gulosa, que, embora eficiente, n\xc3\xa3o garante a otimalidade global. A utiliza\xc3\xa7\xc3\xa3o_NEWLINE_de \xc3\xa1rvores de depend\xc3\xaancia foi formalizada por  no COMIT (Combining Optimizers with Mutual Information Trees), que utiliza uma rede bayesiana_NEWLINE_com estrutura em \xc3\xa1rvore que \xc3\xa9 constru\xc3\xadda pelo algoritmo proposto por ._NEWLINE_O algoritmo BMDA (Bivariate Marginal Distribution Algorithm) _NEWLINE_implementa uma floresta (um conjunto de \xc3\xa1rvores de depend\xc3\xaancia mutuamente independentes)_NEWLINE_como modelo probabil\xc3\xadstico. Uma floresta pode ser interpretada como uma generaliza\xc3\xa7\xc3\xa3o do conceito_NEWLINE_de \xc3\xa1rvores de depend\xc3\xaancia. O algoritmo usa o teste Chi-quadrado de Pearson para determinar_NEWLINE_quais vari\xc3\xa1veis ser\xc3\xa3o conectadas._NEWLINE_No caso cont\xc3\xadnuo, o MIMIC foi estendido para problemas com vari\xc3\xa1veis cont\xc3\xadnuas, supondo que o_NEWLINE_modelo de probabilidades \xc3\xa9 uma distribui\xc3\xa7\xc3\xa3o normal bivariada que utiliza um resultado de_NEWLINE_ para calcular e usar a entropia como medida para determinar depend\xc3\xaancia_NEWLINE_entre duas vari\xc3\xa1veis._NEWLINE_Algoritmos desta fam\xc3\xadlia reproduzem e mesclam blocos construtivos de segunda ordem eficientemente,_NEWLINE_obtendo sucesso na aplica\xc3\xa7\xc3\xa3o junto a problemas lineares e quadr\xc3\xa1ticos .\n_START_SECTION_\nModelos com m\xc3\xbaltiplas depend\xc3\xaancias\n_START_PARAGRAPH_\nApesar de modelos que consideram depend\xc3\xaancia aos pares serem eficientes em certos cen\xc3\xa1rios,_NEWLINE_em problemas multivariados ou com alta sobreposi\xc3\xa7\xc3\xa3o de blocos construtivos, este tipo de modelo_NEWLINE_se mostra insuficiente para representar o espa\xc3\xa7o das boas solu\xc3\xa7\xc3\xb5es. Esta classe de problemas_NEWLINE_requer estimativas mais completas, mesmo \xc3\xa0 custa de uma maior demanda computacional._NEWLINE_No algoritmo ECGA (Extended Compact Genetic Algorithm) , no dom\xc3\xadnio discreto, as vari\xc3\xa1veis s\xc3\xa3o divididas em grupos, cujas vari\xc3\xa1veis de um mesmo grupo (bloco construtivo)_NEWLINE_s\xc3\xa3o independentes entre si, como mostra a figura abaixo. A divis\xc3\xa3o dos grupos \xc3\xa9 feita por um procedimento guloso que utiliza a m\xc3\xa9trica Minimum description length (MDL) . A distribui\xc3\xa7\xc3\xa3o de probabilidades conjunta foi codificada por uma rede bayesiana_NEWLINE_no algoritmo EBNA (Estimation of Bayesian Networks Algorithm) ._NEWLINE_Neste m\xc3\xa9todo, a estrutura da rede \xc3\xa9 constru\xc3\xadda por uma estrat\xc3\xa9gia gulosa de busca local utilizando_NEWLINE_alguma m\xc3\xa9trica para medir a qualidade da rede, como BIC (Bayesian Information Criterion),_NEWLINE_K2 com penalidades (K2+pen) ou teste de (in)depend\xc3\xaancia condicional._NEWLINE_A m\xc3\xa9trica de pontua\xc3\xa7\xc3\xa3o Bayesian-Dirichlet (BD) foi utilizada no algoritmo BOA_NEWLINE_(Bayesian Optimization Algorithm) , que, de forma incremental, vai adicionando novas arestas no grafo at\xc3\xa9 que n\xc3\xa3o haja melhorias na qualidade do modelo._NEWLINE_Com o objetivo de reduzir a cardinalidade do espa\xc3\xa7o de busca, os autores propuseram restringir,_NEWLINE_a um n\xc3\xbamero fixo, a quantidade de pais para cada n\xc3\xb3 da rede bayesiana._NEWLINE_No contexto de vari\xc3\xa1veis cont\xc3\xadnuas, o EMNA (Estimation Multivariate Normal Algorithm)_NEWLINE_ \xc3\xa9 baseado na estima\xc3\xa7\xc3\xa3o de uma fun\xc3\xa7\xc3\xa3o densidade normal multivariada em_NEWLINE_cada gera\xc3\xa7\xc3\xa3o. Apesar do grande n\xc3\xbamero de par\xc3\xa2metros a serem estimados, os c\xc3\xa1lculos envolvidos s\xc3\xa3o_NEWLINE_simples._NEWLINE_Os algoritmos desta classe se distinguem das outras abordagens pela capacidade de representar_NEWLINE_as intera\xc3\xa7\xc3\xb5es multivariadas presentes no problema. Apesar destes algoritmos demandarem alto custo_NEWLINE_computacional, devido ao aprendizado de modelos mais complexos, o n\xc3\xbamero de avalia\xc3\xa7\xc3\xb5es de fitness_NEWLINE_tende a ser reduzido significativamente . Por isso,_NEWLINE_a complexidade computacional total tende a ser reduzida para problemas mais complexos, em que_NEWLINE_o c\xc3\xa1lculo da fun\xc3\xa7\xc3\xa3o-objetivo \xc3\xa9 computacionalmente oneroso.\n_START_SECTION_\nModelos de mistura\n_START_PARAGRAPH_\nNo caso de problemas multimodais, outros modelos probabil\xc3\xadsticos mais flex\xc3\xadveis podem ser empregados._NEWLINE_Modelos de mistura fazem uso do procedimento de agrupamento das solu\xc3\xa7\xc3\xb5es promissoras e posicionam_NEWLINE_distribui\xc3\xa7\xc3\xb5es de probabilidade junto a cada agrupamento. O modelo pode ser descrito como segue:_NEWLINE_onde  representa o peso do i-\xc3\xa9simo componente da mistura e  \xc3\xa9 a_NEWLINE_distribui\xc3\xa7\xc3\xa3o de probabilidade do i-\xc3\xa9simo grupo criado pelo m\xc3\xa9todo de agrupamento de dados. O peso_NEWLINE_de cada componente juntamente com os par\xc3\xa2metros das distribui\xc3\xa7\xc3\xb5es de probabilidades s\xc3\xa3o obtidos_NEWLINE_por algum procedimento dedicado, como o algoritmo EM (Expectation-Maximization)_NEWLINE_._NEWLINE_A figura a seguir apresenta um modelo de mistura gaussiano arbitr\xc3\xa1rio composto de quatro componentes._NEWLINE_Um dos principais obst\xc3\xa1culos desses m\xc3\xa9todos \xc3\xa9 a necessidade de conhecer, de antem\xc3\xa3o, o n\xc3\xbamero de_NEWLINE_componentes, onde cada grupo busca representar um pico da fun\xc3\xa7\xc3\xa3o a ser otimizada. De fato,_NEWLINE_o n\xc3\xbamero de componentes do modelo depender\xc3\xa1 de qu\xc3\xa3o multimodal o problema \xc3\xa9. No entanto, existem_NEWLINE_formas de estimar este par\xc3\xa2metro, como por exemplo, atrav\xc3\xa9s dos crit\xc3\xa9rios de informa\xc3\xa7\xc3\xa3o:_NEWLINE_Bayesian Information Criterion, Akayke Information Criterion, entre outros._NEWLINE_No caso discreto, \xc3\xa9 poss\xc3\xadvel criar um modelo de mistura em que cada componente \xc3\xa9 uma rede bayesiana, como_NEWLINE_o EMDA (Estimation of Mixtures of Distributions Algorithm) descrito por , embora_NEWLINE_este tipo de estimador seja mais aplicado para o caso cont\xc3\xadnuo._NEWLINE_Para o espa\xc3\xa7o de vari\xc3\xa1veis cont\xc3\xadnuas,   propuseram o algoritmo AMix_NEWLINE_(Adaptative Gaussian Mixture'), que utiliza um modelo de mistura adaptativo._NEWLINE_O n\xc3\xbamero de componentes do modelo de mistura pode variar durante_NEWLINE_a execu\xc3\xa7\xc3\xa3o do algoritmo. O algoritmo EDA  _NEWLINE_emprega um modelo de mistura gaussiano que utiliza uma forma de treinamento ao longo do tempo, o que reduz significativamente_NEWLINE_o custo computacional do algoritmo. Al\xc3\xa9m disso, auto-ajusta a n\xc3\xbamero de componentes de mistura_NEWLINE_no decorrer do processo de busca.\n_START_SECTION_\nAplica\xc3\xa7\xc3\xb5es\n_START_PARAGRAPH_\nOs AEDs vem sendo aplicados em uma gama de problemas de diversas \xc3\xa1reas de conhecimento. Dentre as aplica\xc3\xa7\xc3\xb5es podemos destacar:_NEWLINE_sele\xc3\xa7\xc3\xa3o de atributos, evolu\xc3\xa7\xc3\xa3o de pesos de redes neurais MLP, gera\xc3\xa7\xc3\xa3o de regras SE-ENT\xc3\x83O para sistemas nebulosos, express\xc3\xa3o g\xc3\xaanica, an\xc3\xa1lise de  estrutura de prote\xc3\xadnas, em problemas de otimiza\xc3\xa7\xc3\xa3o multiobjetivo e de otimiza\xc3\xa7\xc3\xa3o din\xc3\xa2mica."