@misc { ,
title = { Too Constrained for Genetic Algorithms. Too Hard for Evolutionary Computing. The Traveling Tournament Problem.},
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.},
conference = {ECTA 2023 15th International Conference on Evolutionary Computation Theory and Applications},
doi = {10.5220/0012192100003595},
isbn = {978-989-758-674-3},
pages = {246-257},
publicationstatus = {Published},
publisher = {Scitepress Digital Library},
url = {http://researchrepository.napier.ac.uk/Output/3203193},
keyword = { The Traveling Tournament Problem, Constraints, Genetic Algorithms, Evolutionary Computing, Constraint Hierarchy},
year = {2024},
author = {Verduin, Kristian and Thomson, Sarah L. and van den Berg, Daan}
}