Recombinação por decomposição em computação evolutiva

Resumo

A recombinação de soluções assume papel importante em diversos algoritmos da computação evolutiva. Recombinação é também interessante em outros paradigmas usados em otimização, quer para recombinar soluções encontradas em diferentes execuções de um algoritmo, quer para recombinar soluções produzidas por diferentes algoritmos. O objetivo principal deste projeto é o desenvolvimento de novos operadores de recombinação por decomposição para problemas em que a função de avaliação pode ser escrita como uma soma de termos. Operadores de recombinação por decomposição particionam as variáveis de decisão do problema de modo a permitir a decomposição da função de avaliação. Assim, encontra-se, com custo computacional proporcional ao custo de se avaliar uma solução do problema, a melhor solução de um conjunto de soluções descendentes que cresce exponencialmente com o número de partições encontradas. Neste projeto, serão pesquisados operadores de recombinação por decomposição para problemas de otimização pseudo-Booleana k-restritos e problemas de otimização combinatória envolvendo grafos. (AU)