Skip to main content

Research Repository

Advanced Search

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

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

Authors

Kristian Verduin

Daan van den Berg



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.

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/