An optimizationalgorithm is an algorithm for finding a value x such that f(x) is as small (or as large) as possible, for a given function f, possibly with some constraints on x. Here, x can be a scalar or vector of continuous or discrete values. An algorithm terminates in a finite number of steps with a solution.
An algorithm is a special case of an iterative method, which generally need not converge in a finite number of steps. Instead, an iterative method produces a sequence of iterates from which some subsequence converges to a solution.
Many authors use "algorithm" more broadly for both finitely terminating algorithms and for iterative methods.
2. Conceptual Algorithm:
3. Introduction:
Inspired by natural evolution
Population of individuals
Individual is feasible solution to problem
Each individual is characterized by a Fitness function
Higher fitness is better solution
Based on their fitness, parents are selected to reproduce offspring for a new generation
Fitter individuals have more chance to reproduce
New generation has same size as old generation; old generation dies
Offspring has combination of properties of two parents
If well designed, population will converge to optimal solution
Pseudocode:
Example Of Convergence:
Reproduction mechanisms have no knowledge of the problem to be solved
Link between genetic algorithm and problem:
Coding
Fitness function
4. Basic Principles:
Coding or Representation
String with all parameters
Fitness function
Parent selection
Reproduction
Crossover
Mutation
Convergence
When to stop
An individual is characterized by a set of parameters: Genes
The genes are joined into a string: Chromosome
The chromosome forms the genotype
The genotype contains all information to construct an organism: the phenotype
Reproduction is a "dumb” process on the chromosome of the genotype
Fitness is measured in the real world (‘struggle for life’) of the phenotype
5. Coding
Parameters of the solution (genes) are concatenated to form a string (chromosome)
All kind of alphabets can be used for a chromosome (numbers, characters), but generally a binary alphabet is used
Order of genes on chromosome can be important
Generally many different codings for the parameters of a solution are possible
Good coding is probably the most important factor for the performance of a GA
In many cases many possible chromosomes do not code for feasible solutions
