Hey guys back again with a whole new project for myself. In my earlier posts I was getting use to programming to do certain jobs was rather easy to get use to but now I want to see what can be done in programming something more creative.
So I will be asking a series of questions related to algorithms. Have not a Scooby what they truly are or how to write one. But one that interests me is GA(Genetic Algorithms).
I’ve broke down what I will try and achieve but I need a start point and some programming (console c#) to get me on my way and thinking programmatically. Hope you enjoy the read and can help me on my way.
All living organisms consist of cells. In each cell there is the same set of chromosomes. Chromosomes are strings of DNA and serves as a model for the whole organism. A chromosome consist of genes, blocks of DNA. Each gene encodes a particular protein. Basically can be said, that each gene encodes a trait, for example color of eyes. Possible settings for a trait (e.g. blue, brown) are called alleles. Each gene has its own position in the chromosome. This position is called locus.
Complete set of genetic material (all chromosomes) is called genome. Particular set of genes in genome is called genotype. The genotype is with later development after birth base for the organism's phenotype, its physical and mental characteristics, such as eye color, intelligence etc.
Outline of the Basic Genetic Algorithm
Encoding of a Chromosome
The chromosome should in some way contain information about solution which it represents. The most used way of encoding is a binary string. The chromosome then could look like this:
Chromosome 1 1101100100110110
Chromosome 2 1101111000011110
Each chromosome has one binary string. Each bit in this string can represent some characteristic of the solution. Or the whole string can represent a number - this has been used in the basic GA applet.
Of course, there are many other ways of encoding. This depends mainly on the solved problem. For example, one can encode directly integer or real numbers, sometimes it is useful to encode some permutations and so on.
Crossover
After we have decided what encoding we will use, we can make a step to crossover. Crossover selects genes from parent chromosomes and creates a new offspring. The simplest way how to do this is to choose randomly some crossover point and everything before this point point copy from a first parent and then everything after a crossover point copy from the second parent.
Crossover can then look like this ( | is the crossover point):
Chromosome 1 11011 | 00100110110
Chromosome 2 11011 | 11000011110
Offspring 1 11011 | 11000011110
Offspring 2 11011 | 00100110110
There are other ways how to make crossover, for example we can choose more crossover points. Crossover can be rather complicated and very depends on encoding of the encoding of chromosome. Specific crossover made for a specific problem can improve performance of the genetic algorithm.
Mutation
After a crossover is performed, mutation takes place. This is to prevent falling all solutions in population into a local optimum of solved problem. Mutation changes randomly the new offspring. For binary encoding we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1. Mutation can then be following:
Original offspring 1 1101111000011110
Original offspring 2 1101100100110110
Mutated offspring 1 1100111000011110
Mutated offspring 2 1101101100110110
The mutation depends on the encoding as well as the crossover. For example when we are encoding permutations, mutation could be exchanging two genes.
Take a look at your explanation.
Outline of the Basic Genetic Algorithm
- [Start] Generate random population of n chromosomes (suitable solutions for the problem)
- [Fitness] Evaluate the fitness f(x) of each chromosome x in the population
- [New population] Create a new population by repeating following steps until the new population is complete
- [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
- [Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents.
- [Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome).
- [Accepting] Place new offspring in a new population
- [Replace] Use new generated population for a further run of algorithm
- [Test] If the end condition is satisfied, stop, and return the best solution in current population
- [Loop] Go to step 2
That already looks an awful lot like a program. If you take that, and convert it to code, you should be about 95% of the way. What you'll be missing is your "fitness function", which is basically the running of the solution + the criteria for success. That varies per question, so we can't help much there. But what it'd do is more than likely use the bits of the chromosome as flags or opcodes, depending on the complexity of the problem, and see whether and how fast the chromosome (ie: the current combination of bits/bytes/flags/opcodes/whatever) solved the problem.