Genetic Algorithms (GA)
Simulated Annealing (SA) can be seen as a special case of Genetic Algorithms (GA):
•	Rather than start with a single random candidate solution, as SA does, GA starts with a whole population of random candidates.
•	GA, like SA, also minimizes a certain cost function over a series of successive cycles, or in GA terms, Generations. 
•	In each generation, every member of the population is evaluated for fitness against a set fitness metric/function.
•	The fittest members of the population in each generation are allowed to mate and cross-breed, producing new offspring  new candidate solutions which contain elements of their parents.
•	The weakest members of the population succumb to the ‘Survival Of The Fittest’ and are culled.
•	Eventually, successive mating of the best candidate solutions in each generation should cause the system to converge toward an excellent (optimal or near-optimal) final solution to the problem at hand.
•	GAs mimics nature’s model of ‘natural selection’

Genetic Representation
Some Terminology
•	In Genetic Algorithms, the population is viewed as a large collection of Chromosomes. Each chromosome corresponds to a different candidate solution to the search/minimization problem.
•	In programming terms, a Chromosome is a genetic Data Structure.
•	The Data Type to which a Chromosome belongs is called the Genotype (e.g., the chromosomes of People and Fish belong to different genotypes).
•	An actual instantiation of a particular Genotype (e.g., Bill Blogg’s chromosome) is called a Phenotype.
•	A Chromosome is composed of individual Genes. These correspond to the fields in a genetic data structure, and may each take on any of several values.
•	The different values that a Gene (chromosome field) may assume are called Alleles.

 	Chromosome	=	Data Structure
	Genotype	=	Data Type of Chromosome
	Phenotype	=	Instance of a Genotype
	Gene	=	Field in a Genotype
	Allele	=	Field filler (enum. type)
    Genetic Representation
A Very Simple Example

•	The Human Genotype (abridged):

   eye	hair	 skin	body	body	 brain
 colour	colour   colour	height	speed	  size

•	The Phenotype of O.J. Simpson (abridged):
    		 		 	 	  
    blue	black      dark	tall	fast	  small

•	The Phenotype of Sharon Stone (abridged):
    		 		 	 	  
  Green     Blonde    fair      medium	avg.	  avg.

•	Alleles of the Human Genotype:

    Green	Blonde	Fair	Tall	 Fast	  Large
    Blue	Brown	Dark	Short	 Slow	  Small
    Black	Grey	Black	Medium	  Avg.	  Tiny
        :	   :	   :	    :	    :	  Avg .
    Hazel	Black	Red			    :

 The Mating Game I: 
 Genetic Crossover

•	When two individuals mate to produce offspring, each individual contributes part of their chromosome to form the chromosome of each child.
•	The simplest way of combining the chromosomes of two parents to form the chromosome of a child is ‘Genetic Cross-Over’ : select a cross-over point in one parent chromosome, contribute all genes up to that point, and discard the rest. Then contribute all genes from that point on in the second parent.

A Simple Example:

   blue	black      dark	tall	fast	  small

  Green    Blonde      fair     medium	 avg.	avg.

    blue       black      dark    medium	 avg.	avg.

The Mating Game II: 
 Genetic Mutation

•	No physical copying mechanism in the universe is perfect: the possibility of errors arising in the genetic transcription of an offspring chromosome (either due to copying error, or external forces such as ‘radiation’) must be acknowledged.
•	While in nature, mutation is a predominantly negative force, it often introduces much-needed genetic variety into a phenotype. For this reason Mutation is a key player in Genetic Algorithms.

Our Example Revisited:

   blue	black      dark	tall	fast	  small

  Green    Blonde      fair     medium	 avg.	avg.

    blue       black      dark    medium	 avg.	large

Bit-Coded Genes: 
A More Robust Approach
•	A Problem: Symbolic Alleles (like Red, Large, etc.) are a klunky way to represent chromosomal properties. Symbolic chromosomes are not continuous (too high-level) to mutate in a semantics-free fashion. Cross-breeding of symbolic chromosomes gives rise to compositional mixtures of existing alleles, whereas we often prefer new alleles to arise out of the mating.
•	A Solution: We can avoid these problems by representing chromosomes below the symbolic level, using bit-coding. Each allele is now a single bit, which may be grouped with others for a high-level semantic interpretation.

		0 0 1	1 0 0	0 1 0	0 1 1	 1 1 1	1 0 0

   Green	Brown	White	 Tall	 Fast	  Large
    Blue	Blonde	Black	 Short	 Slow	  Small
    Black	Grey	Dark	 Tiny	  Avg .	  Tiny
    Grey	Silver	Olive	Medium	Immobile	  Avg .
    Hazel	Black	Red	 Huge		  Huge
   Brown    Red	Brown
  Blu/Gre    Ash	  Yellow
	 Gre/Bro    Ginger	  Fair

Cross-Over (Again): 
Bit-Coded Approach

•	In bit-coded mating, we randomly choose the cross-over point at any bit allele in the parent chromosomes, regardless of whether the cross-over occurs at a logical/semantic boundary or not.

		 Blue	 Black	Dark 	 Med.	Avg.	Large
		0 0 1	1 0 0	0 1 0	0 1 1	 1 1 1	1 0 0

		Green	Blonde	Fair 	 Med.	Avg.	Large
		0 0 0	1 0 1	1 1 1	0 1 1	 1 1 0	0 0 0

		Green	Blonde	Olive 	 Med.	Avg.	Large
		0 0 1	1 0 0	0 1 1	0 1 1	 1 1 0	0 0 0

•	So, bit-coding of chromosomes allows the offspring of the mating to possess a high-level allele (olive) that neither parent possesses, yet which both parents contribute to.
•	Mutation is also made simpler -- a single bit allele is chosen at random and flipped (negated).

Solving Optimization/Search Problems
Using Genetic Algorithms

•	Consider the Travelling Salesman Problem (TSP). The first point to note is that, as generally poor as symbolic chromosomes are for GAs overall, they are particularly unsuited to the TSP! Why?
Consider the following symbolic chromosomes for TSP, each representing different potential routes/solutions:

Dub	Par	Hel	NY	Sai	Bom	Chi	 Cai	Bei	 Los	 Tok

But nasty things happen when we mate these solutions:

Los	 Bom	Bei	NY	Sai	Chi	Par	Dub	Hel	 Cai	 Tok

Our offspring solution doesn’t seem very well-formed ...

Dub	 Par	Hel	NY	Sai	Chi	Par	Dub	Hel	 Cai	 Tok

Note how we end up duplicating Dublin, Paris, Helsinki on the route, and lose Los Angeles, Bombay and Beijing altogether! 	
Bit-Wise Encoding Saves the Day

•	Let each Gene specify for a given city
Cost: 33
Bom	Bei	Dub	Hel	NY	 Par	Cai	 Chi	 Sai	  Los	Tok
 
00101 01101110101100010010 10101 01010 101110111011101 00001 

   5 	13	26	24	18	  21	 10	 23	 14	  29	    1
 10th 	8th	2nd	3rd	6th	  5th	 9th	 4th	 7th	  1st	   11th

 Cost: 26
 
01101 01001100111001010001 11100 01011 101010111010001 01111 

   13 	  9	 19	18	17	  28	 11	 21	 14	  17	    15
  9th 	11th	3rd	4th   6th	  1st	10th	 2nd	 8th	  5th	   7th
Cost: 19
 
00101 01101110101100010011 11100 01011 101010111010001 01111

   5 	13	26	24	19	  28	 11	 21	 14	  17	    15
  11th 	9th	2nd	3rd   5th	  1st	10th	 4th	 8th	  6th	   7th

That is, [Los, Dub, Hel, Chi, Par, NY, Sai, Bei, Cai, Bom, Tok] mated with [Par, Chi, Dub, Hel, Los, NY, Tok, Sai, Bom, Cai, Bei] gives [Par, Dub, Hel, Chi, NY, Los, Tok, Sai, Bei, Cai, Bom].

Bit-Wise Encoding solves N-Queens

•	Let each Gene specify for a given Chess File (Column):
Conflicts:   8
 	F1	 F2	 F3	F4	 F5	F6	 F7	 F8	
 
         01101 11010 1100010010 10101 01010 10111  01110   

     	13	26	24	18	  21	 10	  23	   14	   	     
   	R6	R1	R2	R5	 R4	 R8	 R3	   R7	   	    

•	This chromosome corresponds to the following chess board:

8

7

6

5

4

3

2

1
	1	2	3	4	5	6	7	8

Create an initial population of 2xP random solutions

Evaluate each individual solution for fitness

Order population of solutions by fitness

Cull all but the fittest P solutions

Select fittest M members of population for mating

Mate fittest M amongst themselves and with lower members of population

Generate N new offspring to add to population

Select fittest member of population F

Is Fn appreciably fitter than
fittest member of previous generations {F0 ... Fn-1}?

Stop evolution, select F as best solution
 
•	A Mating Algorithm:

Select fittest M phenotypes from population

For every individual phenotype I in M

Pick a mate I’ for I from within M
with probability Pm

Pick a mate I’ for I from outside M (i.e., in P - M)
with probability 1 - Pm

Randomly generate a cross-over point C

Combine all of I up to C with all of I’ from C onwards
to create new offspring O

Introduce a mutation into O with probability R

All of M mated ?
Other Applications: Fantasy Football

•	The object of the game is to select a soccer team from players in the premier division (say), such that their sum cost (in real terms) does not exceed £30m.
	
•	Each player in the (real) league is evaluated weekly for his contribution to a game, and awarded points accordingly.
	
•	The value of a fantasy team is the sum of points awarded to each fantasy player in that team.
	
•	In GA terms, each potential fantasy team is represented by a different chromosome.
	
•	The following fitness function can be employed in a GA to evolve the fittest fantasy team from a population of random candidates:

fitness(TeamT)  =   merit(PlayerT)  - |cost(PlayerT) - 30|
	 	 cost(PlayerT)

•	The left term ensures that we get maximum value for each player. The right term punishes a team that either overspends (which is not allowed) or underspends (in FF, it’s not your money after all, so spend it all!)

 Bit-Coded Chromosomes for
 Fantasy Football

•	Let’s allocate a gene in the chromosome for each player in the team (1 goalie, 4 defenders, 4 midfielders, 2 strikers, assuming a 4-4-2 formation).
•	Let each gene be represented by a 5-bit field that specifies a particular player allele. For instance, in a striker gene, 11010 might indicate Alan Shearer.

Fantasy Team #121: ‘Mutant Wanderers’
Goal	D1	D2	D3	D4	 M1	M2	 M3	 M4	   S1	   S2
 
00101 01101110101100010010 10101 01010 1011101110 00001 00001 

00000	Cole
00001	Shearer
	   :
01010	Rush
01011	Hughes
	   :

Finally: Gray-Coded Representations
•	Thusfar, all our bit-coded chromosomes have employed the traditional binary number scale. E.g., 0 = 000, 1 = 001, 2 = 010, 3 = 011, 4 = 100 etc.
•	This number scale can actually cause problems however. Consider that, like SA, Genetic Algorithms are expected to converge toward a good/near optimal solution by initially taking large random jumps (by mating random chromosomes) and gradually taking smaller and smaller steps toward the solution (by mating more evolved chromosomes).
•	For this convergence to occur smoothly, we need a relatively continuous representation, such that a small change in a chromosome (such as a single bit flip) will cause a small change in fitness.
•	However, in traditional binary representations, a single bit change can cause large differences in decimal value. For instance, flipping the MSB in 000001 causes 64 times as much change in value as flipping the LSB.
 
The solution is a coding system called Gray Codes (after their inventor). In a Gray code, any two successive numbers are only a single bit flip apart.