Too Constrained for Genetic Algorithms too Hard for Evolutionary Computing the Traveling Tournament Problem

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

doi:10.5220/0012192100003595

Too Constrained for Genetic Algorithms too Hard for Evolutionary Computing the Traveling Tournament Problem

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

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	Proceedings of the 15th International Joint Conference on Computational Intelligence
Subtitle of host publication	Volume 1
Editors	Niki van Stein, Francesco Marcelloni, H. K. Lam, Marie Cottrell, Joaquim Filipe
Publisher	Science and Technology Publications, Lda
Pages	246-257
Number of pages	12
Volume	1
ISBN (Electronic)	9789897586743
DOIs	https://doi.org/10.5220/0012192100003595
Publication status	Published - 2023
Event	15th International Joint Conference on Computational Intelligence, IJCCI 2023 - Hybrid, Rome, Italy Duration: 13 Nov 2023 → 15 Nov 2023

Publication series

Name	International Joint Conference on Computational Intelligence
ISSN (Electronic)	2184-3236

Conference

Conference	15th International Joint Conference on Computational Intelligence, IJCCI 2023
Country/Territory	Italy
City	Hybrid, Rome
Period	13/11/23 → 15/11/23

Bibliographical note

Publisher Copyright:
© 2023 by SCITEPRESS – Science and Technology Publications, Lda.

Keywords

Constraint Hierarchy
Constraints
Evolutionary Computing
Genetic Algorithms
The Traveling Tournament Problem

Access to Document

10.5220/0012192100003595

Persistent URL (handle)

Copy link address

Cite this

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 N. van Stein, F. Marcelloni, H. K. Lam, M. Cottrell, & J. Filipe (Eds.), Proceedings of the 15th International Joint Conference on Computational Intelligence: Volume 1 (Vol. 1, pp. 246-257). (International Joint Conference on Computational Intelligence). Science and Technology Publications, Lda. https://doi.org/10.5220/0012192100003595

Verduin, Kristian ; Thomson, Sarah L. ; van den Berg, Daan. / Too Constrained for Genetic Algorithms too Hard for Evolutionary Computing the Traveling Tournament Problem. Proceedings of the 15th International Joint Conference on Computational Intelligence: Volume 1. editor / Niki van Stein ; Francesco Marcelloni ; H. K. Lam ; Marie Cottrell ; Joaquim Filipe. Vol. 1 Science and Technology Publications, Lda, 2023. pp. 246-257 (International Joint Conference on Computational Intelligence).

@inproceedings{0ac91a518b5d4b2bb8121b1319721da3,

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{\textquoteright}s hardly possible to randomly generate a valid solution, for example, to use in a genetic algorithm{\textquoteright}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.",

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

author = "Kristian Verduin and Thomson, {Sarah L.} and {van den Berg}, Daan",

note = "Publisher Copyright: {\textcopyright} 2023 by SCITEPRESS – Science and Technology Publications, Lda.; 15th International Joint Conference on Computational Intelligence, IJCCI 2023 ; Conference date: 13-11-2023 Through 15-11-2023",

year = "2023",

doi = "10.5220/0012192100003595",

language = "English",

volume = "1",

series = "International Joint Conference on Computational Intelligence",

publisher = "Science and Technology Publications, Lda",

pages = "246--257",

editor = "{van Stein}, Niki and Francesco Marcelloni and Lam, {H. K.} and Marie Cottrell and Joaquim Filipe",

booktitle = "Proceedings of the 15th International Joint Conference on Computational Intelligence",

}

Verduin, K, Thomson, SL & van den Berg, D 2023, Too Constrained for Genetic Algorithms too Hard for Evolutionary Computing the Traveling Tournament Problem. in N van Stein, F Marcelloni, HK Lam, M Cottrell & J Filipe (eds), Proceedings of the 15th International Joint Conference on Computational Intelligence: Volume 1. vol. 1, International Joint Conference on Computational Intelligence, Science and Technology Publications, Lda, pp. 246-257, 15th International Joint Conference on Computational Intelligence, IJCCI 2023, Hybrid, Rome, Italy, 13/11/23. https://doi.org/10.5220/0012192100003595

Too Constrained for Genetic Algorithms too Hard for Evolutionary Computing the Traveling Tournament Problem. / Verduin, Kristian; Thomson, Sarah L.; van den Berg, Daan.
Proceedings of the 15th International Joint Conference on Computational Intelligence: Volume 1. ed. / Niki van Stein; Francesco Marcelloni; H. K. Lam; Marie Cottrell; Joaquim Filipe. Vol. 1 Science and Technology Publications, Lda, 2023. p. 246-257 (International Joint Conference on Computational Intelligence).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Too Constrained for Genetic Algorithms too Hard for Evolutionary Computing the Traveling Tournament Problem

AU - Verduin, Kristian

AU - Thomson, Sarah L.

AU - van den Berg, Daan

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - Constraint Hierarchy

KW - Constraints

KW - Evolutionary Computing

KW - Genetic Algorithms

KW - The Traveling Tournament Problem

UR - http://www.scopus.com/inward/record.url?scp=85188250979&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85188250979&partnerID=8YFLogxK

UR - https://www.scitepress.org/ProceedingsDetails.aspx?ID=z5f/p31NVmI=&t=1

U2 - 10.5220/0012192100003595

DO - 10.5220/0012192100003595

M3 - Conference contribution

AN - SCOPUS:85188250979

VL - 1

T3 - International Joint Conference on Computational Intelligence

SP - 246

EP - 257

BT - Proceedings of the 15th International Joint Conference on Computational Intelligence

A2 - van Stein, Niki

A2 - Marcelloni, Francesco

A2 - Lam, H. K.

A2 - Cottrell, Marie

A2 - Filipe, Joaquim

PB - Science and Technology Publications, Lda

T2 - 15th International Joint Conference on Computational Intelligence, IJCCI 2023

Y2 - 13 November 2023 through 15 November 2023

ER -

Verduin K, Thomson SL, van den Berg D. Too Constrained for Genetic Algorithms too Hard for Evolutionary Computing the Traveling Tournament Problem. In van Stein N, Marcelloni F, Lam HK, Cottrell M, Filipe J, editors, Proceedings of the 15th International Joint Conference on Computational Intelligence: Volume 1. Vol. 1. Science and Technology Publications, Lda. 2023. p. 246-257. (International Joint Conference on Computational Intelligence). doi: 10.5220/0012192100003595

Too Constrained for Genetic Algorithms too Hard for Evolutionary Computing the Traveling Tournament Problem

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this