An adaptive mutation scheme for a penalty-based graph-colouring GA.

Ross, Peter; Hart, Emma

Abstract

The folklore of evolutionary algorithms still seems to contain some gross over-generalistions, such as that direct encodings are inferior to indirect ones, that penalty-function methods are often poor, and that observed performance on a few instances can be extrapolated to a whole class. In the interests of exploring the status of such folklore we have continued to investigate in depth the use of a simple representation for graph-colouring problems. In this paper we demonstrate that good performance on a variety of medium-sized problems can be obtained with a simple adaptive mutation scheme. The scheme was originally motivated by considering an artificial counter-example to an earlier approach that had seemed very successful, because it had been used to solve some large real-world exam timetabling problems for certain universities. Those solutions were used in practice, and it would have been tempting to assert that the method was a practical success. This paper represents part of a continuing effort to map out the strengths and weaknesses of using a simple direct encoding and penalty functions for graph colouring.

Citation

Ross, P., & Hart, E. (1998). An adaptive mutation scheme for a penalty-based graph-colouring GA. In A. E. Eiben, T. Back, M. Schoenauer, & H. Schwefel (Eds.), Parallel Problem Solving from Nature V (795-802). https://doi.org/10.1007/BFb0056921

• Start Date: Sep 27, 1998
• End Date: Sep 30, 1998
• Publication Date: 1998
• Deposit Date: Sep 1, 2010
• Peer Reviewed: Peer Reviewed
• Volume: 1498
• Pages: 795-802
• Book Title: Parallel Problem Solving from Nature V
• ISBN: 978-3-540-65078-2
• DOI: https://doi.org/10.1007/BFb0056921
• Keywords: adaptive mutation; penalty functions; graph colouring
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/3179
• Publisher URL: http://dx.doi.org/10.1007/BFb0056921