Procura e Otimização com Seleção Adaptativa de Algoritmos de Estimação da Distribuição

Nome do projeto: Procura e Otimização com Seleção Adaptativa de Algoritmos de Estimação da Distribuição

Investigador responsável: Fernando Lobo

Data início: 01 de julho de 2013

Área Científica: Engenharia Eletrotécnica e Engenharia Informática

Breve sumário do projeto:
Algoritmos de Estimação de Distribuição (EDAs) são uma classe de Algoritmos Evolutivos (EAs) que combina ideias utilizadas em Computação Evolutiva e Aprendizagem Máquina. Os EDAs têm sido desenvolvidos ao longo dos últimos 15 anos, e estão a ter sucesso na resolução de muitos problemas para os quais não é possível obter bons resultados com EAs tradicionais. Aquilo que distingue os EDAs dos outros EAs é o facto de não utilizarem operadores de variação explícita tais como crossover e mutação. Em vez disso, os EDAs aprendem um modelo probabilístico a partir de um conjunto de potenciais soluções, e usam esse modelo para gerar novas soluções. Esta abordagem é poderosa pois permite que o algoritmo de pesquisa se adapte ao problema a ser resolvido. Uma vez que a maioria dos problemas do mundo real possuem algum tipo de estrutura interna (em oposição a serem de natureza completamente aleatória), é legítimo esperar que os EDAs possam aprender tais estruturas, ou pelo menos parte delas, e possam utilizar esse conhecimento de forma efetiva na procura de soluções ótimas.
Os EDAs existentes variam desde os muito simples até aos muito complexos, dependendo do tipo de modelo probabilístico utilizado. Os EDAs mais simples são baseados em modelos univariados e não incluem a aprendizagem da estrutura. Os EDAs mais complexos realizam essa aprendizagem, pesquisando para tal potenciais dependências em cadeia, em árvore ou outras factorizações mais gerais, dadas pelas redes de Bayes e de Markov.
Naturalmente, existe um maior custo associado à utilização dos modelos mais complexos. A aprendizagem da estrutura do problema é uma operação que consome tempo e recursos e que é necessária realizar em cada geração do algoritmo. Para muitos problemas, este custo adicional pode ser compensado por uma pesquisa mais eficaz. Porém, para muitos outros problemas (mais simples), esta operação é desnecessária. Dado um problema de otimização, a escolha do EDA (ou, em geral, a escolha do algoritmo de otimização) mais adequado para resolver esse problema é uma questão que continua a desafiar os investigadores.
Do ponto de vista do utilizador, o principal problema é precisamente estimar de forma objetiva a dificuldade de um dado problema. Tipicamente, um utilizador não possui uma ideia clara, ainda que meramente qualitativa, do grau de complexidade de um problema e, portanto, não sabe antecipadamente qual o tipo de EDA mais adequado. A solução para este problema é usualmente obtida por tentativa e erro. Para tornar este processo ainda mais complicado, para cada EDA utilizado é necessário proceder a afinações de parâmetros, tais como o tamanho da população, determinantes para a eficiência do algoritmo.
O objetivo deste projeto é o desenvolvimento de métodos que automatizem este processo de tentativa e erro para a seleção de EDAs na resolução de problemas de otimização. A ideia principal do projeto é a conceção de um meta-algoritmo que decida qual o EDA que aparenta ser mais adequado para resolver um dado problema, de acordo com certos critérios objetivos. Este objetivo pode ser alcançado utilizando técnicas semelhantes àquelas usadas na adaptação de parâmetros em EAs. O projeto também aborda a integração de algoritmos mais simples, que não são EDAs, na framework de otimização. Além disso, é proposto o desenvolvimento de um método de aprendizagem rápida dos parâmetros dos modelos para os EDAs multivariados.

Palavras-chave: Algoritmos de Estimação da Distribuição, Computação Evolutiva, Aprendizagem Máquina, Otimização