Homogeneous genetic algorithms

Abstract

A new type of genetic algorithm (GA) is developed to mitigate one or both of the following two major difficulties that traditional GAs may suffer: (1) when the number of ‘active genes’ needs to be held constant or kept within some prescribed range, and (2) when the set of genes is much larger than the set of active genes of feasible solutions under consideration. These homogeneous GAs use (unordered) sets to represent ‘active genes’ in chromosomes rather than strings, and a correspondingly natural crossover operator is introduced. ‘Homogeneous’ refers to the fact that, in contrast to traditional GAs where pairs of genes that are ‘close’ have better chances of being preserved under crossover, there is no notion of proximity between pairs of genes. Examples are provided that will demonstrate superior performance of these new GAs for some typical problems in which these difficulties arise.

Keywords:

• evolutionary computation
• genetic algorithms
• homogeneous genetic algorithms
• covariance matrix adaptation-evolutionary strategies
• the p-centre problem

2000 AMS Subject Classification :

• 68W20
• 68T20
• 90C15
• 90C59
• 90C27

CCS Category :

• G.3

Acknowledgements

The author would like to thank the two anonymous referees for their careful readings that have led to their helpful comments and suggestions, as well as some interesting references. He would also like to thank Thomas Bartz-Beielstein for introducing him to the CMA-ES method of stochastic optimization, and its inventor, Nikolaus Hansen for some helpful communications he had with the author when the latter was employing this method to assist in finding decent values for the parameters for the GAs used in this paper.