Algoritmos evolutivos em problemas de grafos.

• Processo: 04/05732-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de novembro de 2004
• Data de Término da vigência: 31 de outubro de 2005
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação
• Pesquisador responsável: Alexandre Cláudio Botazzo Delbem
• Beneficiário: Vinicius Ferreira Negrisolo
• 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 Teoria dos grafos Algoritmos genéticos Computação evolutiva
• Palavra(s)-Chave do Pesquisador: Algoritmos Evolutivos | Algoritmos Geneticos | Computacao Evolutiva | Eficiencia Computacional | Grafos Dinamicos | Teoria De Grafos

Resumo

Alguns problemas do mundo real, que vão desde uma simples busca pela melhor roía de um veículo a um mais complexo como a distribuição de uma grande rede de energia elétrica, podem ser modelados por grafos. As soluções desses problemas são, em geral, computacionalmente muito complexas (NP-Hard). Devido à dificuldade de se encontrar soluções adequadas para tais problemas, técnicas alternativas que em geral produzem soluções aproximadas têm sido investigadas. Dentre essas técnicas, a Computação Evolutiva (CE) tem apresentado propostas capazes de produzir soluções adequadas, em tempo computacionalmente viável, para uma diversidade de problemas. Em vez de garantir que a melhor solução seja encontrada, a CE propõe algoritmos capazes de obter soluções adequadas, mesmo que não ótimas, demandando menos recursos computacionais. O número de trabalhos desenvolvendo novas abordagens evolutivas, bem como o número de problemas resolvidos por tais algoritmos tem aumentado significativamente. Este projeto busca estudar alguns problemas de grafos considerados complexos e, para esses, propõe-se à implementação de algoritmos da CE (como Algoritmos Genéticos, Programação Evolutiva e Estratégias Evolutivas). O projeto pretende contribuir com esta área de pesquisa publicando os resultados obtidos com os algoritmos implementados e também uma comparação desses com as soluções clássicas para os problemas de grafos considerados neste trabalho. (AU)