Aprendizado da ligação entre genes em computação evolutiva : uma nova abordagem baseada em estatísticas de baixa ordem

Abstract

Resumo: Este trabalho propõe um novo algoritmo de computação evolutiva, baseado na aquisição de informação a partir das similaridades entre os indivíduos da população e no usodesta informação para guiar a busca. O teorema do esquema, que é uma fundamentaçãoteórica importante da 'área, já aponta que a existˆencia de similaridades entre os indivíduos está relacionada com a detecção de soluções parciais. Os indivíduos que possuem uma certa sub-estrutura comum podem ser considerados similares, e este grupode indivíduos é chamado de esquema.A inferência de modelos estatísticos para representar os melhores indivíduos encontrados é, atualmente, uma abordagem efetiva para computação evolutiva. Modelos cada vez mais complexos vem sendo usados pelos algoritmos de estimação dedistribuição (EDAs), o que frequentemente resulta em uma melhor eficácia. Os EDAsmais efetivos adotam redes Bayesianas, pois estes modelos capturam interações de altaordem entre as varáveis do problema. O aprendizado da estrutura destes modelos é,entretanto, uma tarefa computacionalmente cara. EDAs baseados em estatísticas deprimeira ordem, por sua vez, são computacionalmente mais simples mas não têm semostrado efetivos em muitos problemas benchmark. Isto é devido à incapacidade dosEDAs de baixa ordem em aprender sobre as ligações entre os genes, que são resultantesda estrutura de interações presentes nestes problemas.O algoritmo proposto é um EDA de baixa ordem que mantém a população agrupada por similaridade e procura explorar o espaço de busca combinando a informaçãoadquirida em grupos diferentes. Uma avaliação empírica é conduzida, a qual adotaum escopo abrangente de problemas que representam as principais difuculdades encontradas em EDAs. Os resultados mostram que a nova proposta é efetiva e eficienteem diversos problemas benchmark.

Abstract: This work proposes a new evolutionary computation algorithm, which is based on acquiring information from the similarities among the individuals of the population andusing this information to guide the search. The schemata theorem, which is an important theoretical foundation for evolutionary computation, already pointed out that thesimilarities among the individuals is related to the detection of partial solutions. Allindividuals possessing a certain substructure can be considered similar, and this groupof individuals is called schemata.Inferring statistical models from the best individuals found so far is currently aneffective approach for evolutionary computation. Increasingly more complex modelshave been used by estimation of distribution algorithms (EDAs), which often resultbetter effectiveness. The most effective EDAs adopt Bayesian networks, since thosemodels are able to capture interactions of high order among the variables of a problem.Learning the structure of those models is, however, a computationally expensive task.Simpler EDAs based on single order statistics, on the other hand, are computationallysimpler approaches, but have not been shown to be effective on many benchmark problems. This is due to inability of simpler EDAs to learn and respect the linkage amongthe genes, which is a result of the structure of interactions present in those problems.The algorithm proposed is a low-order EDA which keeps the population clusteredand attempts to explore the space by combining information from different clusters.Empirical evaluation is performed, which adopts a comprehensive range of benchmarkproblems, which illustrate most of the difficulties found by EDAs. Results show thatthe new approach is effective and efficient on several benchmark problems.