Genetic Algorithms terminology

Decision Making (Multi Objective optimization)

Fig.1.a Trade-off solutions  for a car-buying decision making problem

History of Genetic Algorithms

•Charles Darwin stated the theory of natural evolution in the origin of species. Over several generations, biological organisms evolve based on the principle of natural selection “survival of the fittest”

• In 1975, John Holland described how to apply the principles of natural evolution to optimization problems and built the first Genetic Algorithm.

• Genetic algorithms are based on the principle of genetics and evolution

What is Genetic Algorithm?

• Holland proposed GA as a heuristic method based on “Survival of the fittest”. GA was discovered as a useful tool for search and  optimization problems.

Search Space

•The space of all feasible solutions (the set of solutions among which the desired solution resides) is called search space (also state space).

•The difficulties in this are the local minima and the starting point of the search (see Fig.1.b).

                           Fig.1.b An example of search space

Individuals

An individual is a single solution. Individual groups together two forms of solutions as given below:

1. The chromosome, which is the raw ‘genetic’ information (genotype) that the GA deals.

2. The phenotype, which is the expressive of the chromosome in the terms of the model.

A chromosome is subdivided into genes. A gene is the GA’s representation of a single factor for a control factor. Each factor in the solution set corresponds to gene in the chromosome.

            Fig.2 Representation of Geno type and Pheno type

•A chromosome should in some way contain information about solution that it represents. Chromosomes are encoded by bit strings are given in Fig. 3

Fig.3 Representation of a chromosome

Genes

•Genes are the basic “instructions” for building a Generic Algorithms.

•A chromosome is a sequence of genes. Genes may describe a possible solution to a problem, without actually being the solution. 

In a chromosome, the genes are represented as in fig.4

Fig.4 Representation of a Gene

Fitness

•The fitness of an individual in a genetic algorithm is the value of an objective function for its phenotype.

•In general, fitness function F(x) is first derived from the objective function and used in successive genetic operations.

• Consider the following transformations:

•   F(x) = f(x) for maximization problem

            =1/f(x) for minimization problem if f(x)≠0

            = 1/(1+f(x)) if f(x)=0

Population

•A population is a collection of individuals.

•A population consists of a number of individuals being tested, the phenotype parameters defining the individuals and some information about search space.

•The two important aspects of population used in Genetic Algorithms are:

i) Initial population generation

ii) Population size

Population being combination of various chromosomes is represented as in Fig. 5

                                      Fig.5 Population

Encoding

•Encoding is a process of representing individual genes.

•The process can be performed using bits, numbers, trees, arrays, lists or any other objects.

•The encoding depends mainly on solving the problem. For example, one can encode directly real or integer numbers.