Creating my first Algorithm
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**

   1. **[Start]** Generate random population of n chromosomes (suitable solutions for the problem)
   2. **[Fitness]** Evaluate the fitness f(x) of each chromosome x in the population
   3. **[New population]** Create a new population by repeating following steps until the new population is complete
         1. **[Selection]** Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
         2. **[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.
         3. **[Mutation]** With a mutation probability mutate new offspring at each locus (position in chromosome).
         4. [Accepting] Place new offspring in a new population 
   4. **[Replace]** Use new generated population for a further run of algorithm
   5. **[Test]** If the end condition is satisfied, stop, and return the best solution in current population
   6. **[Loop]** Go to step 2

**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.

Creating my first Algorithm
===

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**

   1. **[Start]** Generate random population of n chromosomes (suitable solutions for the problem)
   2. **[Fitness]** Evaluate the fitness f(x) of each chromosome x in the population
   3. **[New population]** Create a new population by repeating following steps until the new population is complete
         1. **[Selection]** Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
         2. **[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.
         3. **[Mutation]** With a mutation probability mutate new offspring at each locus (position in chromosome).
         4. [Accepting] Place new offspring in a new population 
   4. **[Replace]** Use new generated population for a further run of algorithm
   5. **[Test]** If the end condition is satisfied, stop, and return the best solution in current population
   6. **[Loop]** Go to step 2

**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.
