Codificacao de algoritmos evolutivos para problemas de modificacao de grafos.

• Processo: 04/01209-1
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de maio de 2004
• Data de Término da vigência: 31 de dezembro de 2004
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Sistemas de Computação
• Pesquisador responsável: Alexandre Cláudio Botazzo Delbem
• Beneficiário: Giampaolo Luiz Libralon
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Assunto(s): Algoritmos evolutivos
• Palavra(s)-Chave do Pesquisador: Algoritmos Evolutivos | Grafos Dinamicos | Operadores De Recombinacao | Representacao No Profundidade

Resumo

Este projeto busca explorar a potencialidade de Algoritmos Evolutivos (AEs) na solução de problemas de modificação de grafos (PMG). As soluções desses problemas são computacionalmente complexas (em geral, NP-Hard). Por outro lado, metodologias capazes de obter soluções satisfatórias para tais problemas possuem uma larga gama de aplicações. As áreas de aplicações podem variar de Determinação de Árvores Filogenéticas em Bioinformática a Reconfiguração de Circuitos Eletrônicos de FPGAs. A representação (ou codificação) afeta drasticamente a eficiência computacional dos AEs para problemas envolvendo grafos. Essa questão se torna mais grave quando as soluções são florestas de grafos e/ou a escala do sistema considerado (tamanho do grafo) é muito grande. Um outro agravante para a solução deste problema é a falta de pesquisas nessa área. Neste contexto, este projeto propõe o estudo de técnicas de representação de grafos para AEs aplicados a PMG. Busca-se investigar codificações mais eficientes para tais problemas. Para melhoria do desempenho dos AEs, será inicialmente estudada e implementada a representação Nó-Profundidade, uma nova forma de representar grafos que confere aos AEs um melhor desempenho. Em uma segunda fase, serão investigadas alterações na representação Nó-Profundidade, estudando possíveis operadores de recombinação (OR) baseados nesta representarão que aumentem a eficiência dos AEs para PMG. (AU)