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

Ross, Peter and Hart, Emma (1998) An adaptive mutation scheme for a penalty-based graph-colouring GA. In: Parallel Problem Solving from Nature V. Lecture Notes in Computer Science, 1498 . Springer-Verlag, pp. 795-802. ISBN 978-3-540-65078-2

Full text not available from this repository. (Request a copy)


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.

Item Type: Book Section
ISBN: 978-3-540-65078-2
Electronic ISBN: 978-3-540-49672-4
Additional Information: 5th International Conference Amsterdam, The Netherlands September 27-30, 1998
Uncontrolled Keywords: adaptive mutation; penalty functions; graph colouring;
University Divisions/Research Centres: Faculty of Engineering, Computing and Creative Industries > School of Computing
Dewey Decimal Subjects: 000 Computer science, information & general works > 000 Computer science, knowledge & systems > 004 Data processing & computer science
Library of Congress Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Item ID: 3179
Depositing User: Computing Research
Date Deposited: 01 Sep 2010 15:51
Last Modified: 08 Jan 2016 09:42

Actions (login required)

View Item View Item

Edinburgh Napier University is a registered Scottish charity. Registration number SC018373