An overview of genetic algorithms: Part 1, fundamentals
David W. C. Beasley, David Bull, Ralph Robert Martin · ORCA Online Research @Cardiff (Cardiff University) · 1993
Genetic Algorithms (GAs) are adaptive methods which may be used to solve search and optimisation problems. They are based on the genetic processes of biological organisms. Over many generations, natural populations evolve according to the principles of natural selection and \survival of the ttest, rst clearly stated by Charles Darwin in The Origin of Species. By mimicking this process, genetic algorithms are able to \evolve solutions to real world problems, if they have been suitably encoded. For example, GAs can be used to design bridge structures, for maximum strength/weight ratio, or to determine the least wasteful layout for cutting shapes from cloth. They can also be used for online process control, such as in a chemical plant, or load balancing on a multi-processor computer system. The basic principles of GAs were rst laid down rigourously by Holland [Hol75], and are well described in many texts (e.g. [Dav87, Dav91, Gre86, Gre90, Gol89a, Mic92]). GAs simulate those processes in natural populations which are essential to evolution. Exactly which biological processes are essential for evolution, and which processes have little or no role to play is still a matter for research; but the foundations are clear. In nature, individuals in a population compete with each other for resources such as food, water and shelter. Also, members of the same species often compete to attract a mate. Those individuals which are most successful in surviving and attracting mates will have relatively larger numbers of o spring. Poorly performing individuals will produce few of even no o spring at all. This means that the genes from the highly adapted, or individuals will spread to an increasing number of individuals in each successive generation. The combination of good characteristics from di erent ancestors can sometimes produce \super o spring, whose tness is greater than that of either parent. In this way, species evolve to become more and more well suited to their environment. GAs use a direct analogy of natural behaviour. They work with a population of \individuals, each representing a possible solution to a given problem. Each individual is assigned a tness according to how good a solution to the problem it is. For example, the tness score might be the strength/weight ratio for a given bridge design. (In nature this is equivalent to assessing how e ective an organism is at competing for resources.) The highly t individuals are given opportunities to \reproduce, by \cross breeding with other