Uma abordagem evolutiva para geração automática de turnos completos em torneios

Abstract

Este artigo apresenta contribuições junto à solução de problemas de escalonamento, mais precisamente na geração de turnos completos em torneios. Trata-se de um problema de grande interesse prático, caracterizado por questões de factibilidade e uma explosão combinatória de candidatos à solução. Sendo assim, a atuação direta de um especialista e a aplicação de ferramentas convencionais de busca geralmente não conduzem a resultados satisfatórios. A estratégia de solução proposta está baseada na aplicação conjunta de computação evolutiva, busca local e otimização baseada em restrições. Embora outras abordagens evolutivas já tenham sido propostas na literatura, a empregada aqui inova ao sugerir uma representação genética compacta aliada a um algoritmo de expansão de código. Comparadas às soluções já implementadas para problemas reais de escalonamento, aquelas obtidas a partir da estratégia de solução proposta neste trabalho apresentaram melhor desempenho e a quantidade de recursos computacionais requeridos para produzir a solução é aceitável. A aplicação conjunta de computação evolutiva, busca local e técnicas de otimização baseada em restrições pode ser estendida ao tratamento de outros problemas de escalonamento, supondo a existência de uma codificação genética compacta e a disponibilidade de um algoritmo de otimização baseado em restrições.