Mimicking chromosomes
Reproduction loop
Strings of 0 and 1 simulate chromosomes in binary systems. An initial population of chromosomes is allowed to mutate (modification of certain bit in the strings), cross over with other strings during replication, or to remain the same.
Mutation: enables a step by step modification of chromosomes, allowing hill-climbing to improve fitness little by little
Cross over: enables the aggregation of the best characteristics from different chromosomes into a new one
The chromosomes “genotype”, encodes the phenotype of corresponding individuals (animals, peoples, programs…), which is represented by its fitness to the environment. The fitness provides a probability of survival to the next generation through a selection process.
Through the alteration (mutation, cross over, remain) of chromosomes and selection (fitness) before reproduction, chromosomes can evolve from one generation to the next.
This process of selection and reproduction is bound to get blocked in local maxima, but allows for a lot of intervention by the algorithm designer to circumvent such problems.
Defining the probability of survival
By fitness
Probability of survival = Fitness / Sum of fitness of all chromosomes
Rank Space
The probability of survival of the highest ranking individual is defined as a constant P[c]. If this highest ranking individual is not reaching the selection threshold, then the second highest ranking individual is checked, with a probability of (1-P[c]) P[c] and so on:
- P[1] = P[c]
- P[2] = (1-P[c]) P[c]
- P[3] = (1-P[c])^2 P[c]
- P[n-1] = (1-P[c])^(n-2) P[c]
- P[n] = (1-P[c])^(n-1)
By fitness and diversity
Both the most fit and most diverse individuals are retained for reproduction in the next generation. Diversity allows genetic algorithms to be much more effective and to not get blocked in local maxima.
Issues with genetic algorithm
The transition of genotype to phenotype is still not well understood.
The effectiveness of a genetic algorithm may lie in its creator’s ability to program it with the right parameters rather than the algorithm itself. It may also come from the richness of the environment, as other types of algorithm may do as well or better.
Applications
The combination of different good options from crossing over (beginning, end) can be useful in planning a series of steps. Combining different plans and different series of steps can result in a better plan.
Combining different rules from a rule-based expert system, such as horse-racing prediction.
Genetic algorithm may be used to encode “creatures“: their size, number of parts, articulations or method of operations…