25-01-2012, 12:41 PM
An Overview of Genetic Algorithms Part 1 , Fundamentals
[attachment=16571]
Introduction
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 strengthweight 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
Basic Principles
The standard GA can be represented as shown in Figure
Before a GA can be run a suitable coding or representation for the problem must be devised We also
require a tness function which assigns a gure of merit to each coded solution During the run parents must
be selected for reproduction and recombined to generate ospring These aspects are described below
Fitness function
A tness function must be devised for each problem to be solved Given a particular chromosome the tness
function returns a single numerical tness or gure of merit which is supposed to be proportional to the
utility or ability of the individual which that chromosome represents For many problems particularly
function optimisation it is obvious what the tness function should measureit should just be the value of the
function But this is not always the case for example with combinatorial optimisation
Reproduction
During the reproductive phase of the GA individuals are selected from the population and recombined pro
ducing ospring which will comprise the next generation Parents are selected randomly from the population
using a scheme which favours the more t individuals Good individuals will probably be selected several times
in a generation poor ones may not be at all