Search This Blog

Sunday, December 8, 2013

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.

No comments: