What Are Genetic Algorithms ?

Genetic algorithms (GA) work by simulating the logic of Darwinian selection, where only the best are selected for replication.

Over many generations, natural populations evolve according to the principles of natural selection and stated by Charles Darwin in The Origin of Species. Only the most suited elements in a population are likely to survive and generate offspring, thus transmitting their biological heredity to new generations.

In computing terms, a genetic algorithm is a population of individuals represented by chromosomes, a  set of character strings that are analogous to the base chromosomes  that we see in our own DNA.
A genetic algorithm implement the model of computation by having arrays of bits or characters (binary string) to represent the  chromosomes. Each string represents a potential solution. /p>

The GA then manipulates the most promising chromosomes searching for improved solutions. A GA operates typically through a simple cycle of three stages:

1. Build and maintain a population of solutions to a problem,
2. Choose the better solutions for recombination with each other
3. Use their offspring to replace poorer solutions.

In each cycle a new generation of possible solutions for a given problem is produced. At the first stage, an initial population of potential solutions is created as a starting point for the search process, each element of the population is encoded into a string (the chromosome), to be manipulated by the genetic operators.

In the next stage, the performance (or fitness) of each individual of the population is evaluated with respect to the constraints imposed by the problem.

The selection is responsible for assuring survival of the best fitted individuals. The combined evaluation/selection process is called reproduction.

The basic Genetic algorithm is :

Initialize a random population of individuals
Compute fitness of each individual
WHILE NOT finished DO
BEGIN /* produce new generation */
FOR population_size DO
BEGIN /* reproductive cycle */
Select two individuals from old generation, recombine the
 two individuals to give two offspring
Make a mutation for selected individuals by altering a
 random bit in a string
Create a new generation (new populations)
END
IF population has converged THEN
finished := TRUE
END

GA Coding

Each individual of a population represents a possible solution to a given problem. Each individual is assigned a “fitness score" according to how good a solution to the problem it is.

A potential solution to a problem may be represented as a set of parameters. For example, if our problem is to maximize a function of three variables, F(x; y; z), we might represent each variable by a 10-bit binary number (suitably scaled). Our chromosome would therefore contain three genes, and consist of 30 binary digits.

Fitness function

A Fitness function must be specific for each problem to be solved. Given a particular chromosome, the fitness function returns a single numerical merit, which is supposed to be proportional to the utility of the individual which that chromosome represents. 

Reproduction

During the reproductive phase of the GA, individuals are selected from the population and recombined. Parents are selected randomly from the population using a scheme which favors the more important individuals (fitness value).

Having selected two parents, their chromosomes are recombined, typically using the mechanisms of crossover and mutation.

Crossover takes two individuals, and cuts their chromosome strings at some randomly chosen position, to produce two “head" segments, and two “tail" segments. The tail segments are then swapped over to produce two new full length chromosomes. The two individual each inherit some genes from each parent.

Mutation is applied to each child individually after crossover. It randomly alters each gene with a small probability (typically 0.001).

Convergence

A typical application of this technology would be to try to determine the best route for delivering product from point A to point B, when the conditions may periodically change. These conditions could be related to weather, road conditions, traffic flow, rush hour, etc. Many times the best route could be the fastest, shortest, most scenic, most cost effective, or a combination thereof. No one answer to the question will always be perfectly correct. It may get you from point A to B, but not necessarily to everyone's liking, or every time of the day or week. In fact, typically the more options you provide, the more accurate the answer will be.