Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/40402
Type: Artigo de periódico
Title: Uma abordagem evolutiva para geração automática de turnos completos em torneios
Author: Concilio, Ricardo
Von Zuben, Fernando J.
Abstract: This paper presents contributions to the solution of assignment problems, more precisely to the generation of a complete set of rounds 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 the use 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 compact genetic 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 of computational 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.
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.
Subject: Computação evolutiva
otimização com restrições
representação compacta
expansão de código
busca local
Evolutionary computation
constraint optimization
compact representation
code expansion
local search
Editor: Sociedade Brasileira de Automática
Rights: aberto
Identifier DOI: 10.1590/S0103-17592002000200003
Address: http://dx.doi.org/10.1590/S0103-17592002000200003
http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-17592002000200003
Date Issue: 1-Aug-2002
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
S0103-17592002000200003.pdf210.37 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.