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

摘要

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.