Genetic Algorithms

 

Genetic algorithms mimic the process of natural selection to solve optimization and search problems appearing in a huge number of very different application fields, from bioinformatics to economics and engineering.

Suppose for example that you need to design a certain electronic equipment according to some specifications. This is an “optimization” problem in that the “optimal” solution will be one of the possibly many equipments meeting the specifications. Genetic algorithms serve indeed very often as optimizers for such kinds of “computer-automated” designs.

A genetic algorithm encodes candidate solutions (individuals) in strings of symbols (chromosomes), typically 0s and 1s (binary coded genetic algorithm) or real numbers (real coded genetic algorithms), and assigns them a fitness according to the problem to solve. The symbols of the chromosomes have the same semantics as in real life, namely, they are representative of the individual features while the fitness measures, for example in the computer-automated design case above, how much a certain equipment (candidate solution or individual) is “far” from satisfying the specifications.

Initially, a generation of individuals is produced at random, the fitness function is calculated for each individual, and individuals with highest fitness, thus farthest from meeting the specifications, are “killed”. The remaining ones have the genetic material most suited to reproduce and give rise, by a cross-over mechanism, to a new generation of individuals which are closer to meet the design requirements. Mutations (random changes in the chromosomes) are also necessary to add new genetic material to the offspring. The fitness function is then calculated for the new individuals and the whole process repeats again. The iterations terminate when either a maximum number of generations is reached or a satisfactory fitness is obtained.

A general pseudocode of the genetic algorithm is the following:

Initialize population
While (not exit criterion) do
Calculate Fitness for all population
Choose parents by the adopted selection method
Generate the offspring by the adopted crossover method
Apply mutation
End

Next, some central factors in the success of a genetic algorithm are shortly pointed out.

Encoding of candidate solutions

Binary encoding is the most popular both due to historical reasons and because it yields very simple operators (crossover, mutation,…). The chromosome is a sequence of 0s and 1s. For example

Population member

Chromosome

1

10110100101010

2

01010010110101

Generally, using a coding that has some underlying relevance to the problem at hand produces better results. Therefore, often variables are no longer represented by bits of zeros and ones, but instead by floating-point numbers over whatever range is deemed appropriate.

Selection

Survival of the “fittest” population members consists of discarding the chromosomes with the highest cost. Some chance that relatively unfit individuals are selected is usually preserved to ensure that genes carried by them are not “lost” prematurely. The simplest way to perform selection is population decimation. It consists of ranking the individuals from largest to smallest, according to their fitness values. An arbitrary minimum fitness is chosen as a cutoff point, and any individual with a lower fitness than the minimum is removed from the population. The remaining individuals are then used to yield the new generation through random pairing. The advantage of population decimation is its simplicity, but the disadvantage is that once an individual has been removed from the population, any unique characteristic of the population possessed by that individual is lost. More effective selection strategies are proportionate selection or tournament selection.

Mating

Mating consists of generating one or more offspring from the parents selected in the pairing process. The most simple way of mating involves two parents that produce two offspring. A crossover point is randomly selected between the first and last bits of the parents’ chromosomes. For example:

Parent

Chromosome

#1

101101 00101010

#2

010100 10110101

Offspring

Chromosome

#1

101101 10110101

#2

010100 00101010

The spacing indicates the crossover point, which is randomly selected as well.

Mutation

Mutation provides a means for exploring portions of the solution space not yet represented by the current population. An element of the chromosome is randomly selected and changed. In the case of binary coding, this amounts to selecting a bit from the chromosome string and inverting it (a “1” becomes a “0” and a “0” becomes a “1.”

If you want to know more, try it by yourself! We provide you a free Genetic Algorithms software.

Leave a Reply

Your email address will not be published. Required fields are marked *