Generic chromosome representation and evaluation for genetic algorithms

Abstract

The past thirty years have seen a rapid growth in the popularity and use of Genetic Algorithms for searching for optimal or near-optimal solutions to optimisation problems. One of the reasons for their immense success is the fact that the principles governing the algorithm are simple enough to be appreciated and understood. The major differences between one Genetic Algorithm and another lie within the schemes used to represent chromosomes, the semantics of the genetic operators, and the measures used to evaluate their fitness. Yet, these very differences make Genetic Algorithms so complex to design and implement when opposed with most real-world optimisation problems. The truth is that the people faced with these types of optimisation problems are not necessarily computer sci- entists or machine learning experts. Indeed, these types of problems constantly appear in various non-computing disciplines ranging from biology to manufacturing and economics. In this report, we present a simple, yet powerful, high-level technique that can be used to describe the structure of chromosomes and how their fitness can be evaluated. The method is abstract enough to insulate the practitioner from all the implementation, design, and coding details usually associated with a Genetic Algorithm. Nonetheless, a wide array of optimisation problems ranging from the classical travelling salesman problem and the n-Queens problem to time-table scheduling and dynamic programs can be described.