New order-based crossovers for the graph coloring problem

Mumford, Christine Lesley ORCID: https://orcid.org/0000-0002-4514-0272 2006. New order-based crossovers for the graph coloring problem. Presented at: 9th International Conference on Parallel Problem Solving from Nature, Reykjavik, Iceland, 9-13 September 2006. Parallel Problem-Solving From Nature - PPSN IX. Lecture Notes in Computer Science - Parallel Problem Solving from Nature - PPSN IX. Lecture Notes in Computer Science (4193) Berlin: Springer Verlag, pp. 880-889. 10.1007/11844297_89

Full text not available from this repository.

Abstract

Huge color class redundancy makes the graph coloring problem (GCP) very challenging for genetic algorithms (GAs), and designing effective crossover operators is notoriously difficult. Thus, despite the predominance of population based methods, crossover plays a minor role in many state-of-the-art approaches to solving the GCP. Two main encoding methods have been adopted for heuristic and GA methods: direct encoding, and order based encoding. Although more success has been achieved with direct approaches, algorithms using an order based representation have one powerful advantage: every chromosome decodes as a feasible solution. This paper introduces some new order based crossover variations and demonstrates that they are much more effective on the GCP than other order based crossovers taken from the literature.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics > QA76 Computer software
Publisher:	Springer Verlag
ISBN:	9783540389903
ISSN:	0302-9743
Last Modified:	20 Oct 2022 09:25
URI:	https://orca.cardiff.ac.uk/id/eprint/31893

Citation Data

Cited 27 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item