C&A-SBA logo

Volume 13 number 2

Pages: 105-122


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

Ricardo Concilio, Fernando J. Von Zuben

    Departamento Fundamental, Escola de Engenharia Mauá,São Caetano do Sul, SP -- Brasil, 09580-900
    Faculdade de Engenharia Elétrica e de Computação (DCA/FEEC),Universidade Estadual de Campinas (Unicamp),C. P. 6101, 13083-970, Campinas, SP -- Brasil
    (ricardo.concilio@maua.br, vonzuben@dca.fee.unicamp.br)
Resumo: 
Este artigo apresenta contribuições junto àsolução de problemas de escalonamento, mais precisamente nageração de turnos completos em torneios. Trata-se de um problema degrande interesse prático, caracterizado por questões defactibilidade e uma explosão combinatória de candidatos àsolução. Sendo assim, a atuação direta de um especialista ea aplicação de ferramentas convencionais de busca geralmente nãoconduzem a resultados satisfatórios. A estratégia de soluçãoproposta está baseada na aplicação conjunta decomputaçã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 umarepresentaçã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 apartir 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. Aaplicação conjunta de computação evolutiva, busca local eté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.
Palavras Chave: Computação evolutiva, otimização com restrições, representação compacta, expansão decódigo, busca local.
  
Abstract:  An evolutionary approach to the automatic generation of a complete set of rounds in tournaments.
This paper presents contributions to the solution ofassignment problems, more precisely to the generation of a complete set ofrounds in tournaments. It represents a practical problem of high interest,being characterized by feasibility aspects and a combinatorial explosion of solution candidates. In this case, the direct actuation of an expert and theuse of conventional search tools generally guide to unsatisfactory results.The proposed solution strategy is based on the joint application of evolutionary computation, local search and restriction-based optimization. Although other evolutionary approaches have already been proposed in the literature, the one considered here innovates, since it suggests a compactgenetic codification in conjunction with an algorithm to expand the code. When compared with the solutions already implemented to deal with real-world assignment problems, the ones obtained from the solution strategy proposed in this work presented better performance and the required amount ofcomputational resource to produce the solution is reasonable. The joint application of evolutionary computation, local search and restriction-based optimization may be extended to deal with other assignment problems,assuming the existence of a compact genetic codification and the availability of an algorithm for restriction-based optimization.
Keywords: Evolutionary computation, constraint optimization,compact representation, code expansion, local search.

PDF copy (151202bytes)

Back to Volume 13 index.


Click here to obtain
get acrobat reader

Last modifications:  
 by jro