Too Constrained for Genetic Algorithms. Too Hard for Evolutionary Computing. The Traveling Tournament Problem.

Verduin, Kristian; Thomson, Sarah L.; van den Berg, Daan

Abstract

Unlike other NP-hard problems, the constraints on the traveling tournament problem are so pressing that it’s hardly possible to randomly generate a valid solution, for example, to use in a genetic algorithm’s initial population. In this study, we randomly generate solutions, assess the numbers of constraint violations, and extrapolate the results to predict the required number of samples for obtaining a single valid solution for any reasonable instance size. As it turns out, these numbers are astronomical, and we finish the study by discussing the feasibility of efficient sampling of valid solutions to various NP-hard problems.

Citation

Verduin, K., Thomson, S. L., & van den Berg, D. (2023, November). Too Constrained for Genetic Algorithms. Too Hard for Evolutionary Computing. The Traveling Tournament Problem. Presented at ECTA 2023 15th International Conference on Evolutionary Computation Theory and Applications, Rome, Italy

• Presentation Conference Type: Conference Paper (published)
• Conference Name: ECTA 2023 15th International Conference on Evolutionary Computation Theory and Applications
• Start Date: Nov 13, 2023
• End Date: Nov 15, 2023
• Acceptance Date: Sep 14, 2023
• Publication Date: 2023
• Deposit Date: Sep 28, 2023
• Publisher: Scitepress Digital Library
• Pages: 246-257
• Book Title: Proceedings of the 15th International Joint Conference on Computational Intelligence
• ISBN: 978-989-758-674-3
• DOI: https://doi.org/10.5220/0012192100003595
• Keywords: The Traveling Tournament Problem, Constraints, Genetic Algorithms, Evolutionary Computing, Constraint Hierarchy
• Public URL: http://researchrepository.napier.ac.uk/Output/3203193
• Related Public URLs: https://ecta.scitevents.org/