Research Output
Too Constrained for Genetic Algorithms. Too Hard for Evolutionary Computing. The Traveling Tournament Problem.
  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.

  • Date:

    30 November 2023

  • Publication Status:

    Published

  • Publisher

    SCITEPRESS

  • DOI:

    10.5220/0012192100003595

  • Funders:

    Edinburgh Napier Funded

Citation

Verduin, K., Thomson, S. L., & van den Berg, D. (2023). Too Constrained for Genetic Algorithms. Too Hard for Evolutionary Computing. The Traveling Tournament Problem. In Proceedings of the 15th International Joint Conference on Computational Intelligence (246-257). https://doi.org/10.5220/0012192100003595

Authors

Keywords

The Traveling Tournament Problem, Constraints, Genetic Algorithms, Evolutionary Computing, Constraint Hierarchy

Monthly Views:

Available Documents