Evolving first lady of the internet

At last I ported selfish gene algorithm into Python. This algorithm pseudo-code is: 1. Encode some solution into set of genes. 2. Set default probability for each gene. 3. Generate 2 random solutions, according to genes probability. 4. Compare these 2 solutions: for better solution- increase it`s genes probability by some value for worse solution- decrease it`s genes probability by some value 5. Repeat everything from 3, until needed. Now, interesting part. What can we do with selfish gene algorithm ? After seeing this post about genetic programming and evolutionary art, I`ve decided to try something similar. But only by using selfish gene algorithm. I`ve tried 2 experiments - tried to evolve picture of first lady of the internet composed of polygons. And second experiment - lenna picture is evolved as some number of lines. So experiment idea is to generate 2 random images, composed of random polygons (or lines in other experiment) and to compare these 2 images. For image which is more similar to original lenna picture - we increase polygons probability, for other picture - decrease polygons probability. In the long run - "good polygons" tends to group together. Below are the results of these experiments. Evolved pictures of lenna are compiled as frames of animated GIF image. N - is the iteration number (starting from zero): Lena evolved as set of polygons

Original Lena	Lena evolution: 39614 iterations 100 polygons 3.5 hours experiment code

Lena evolved as set of lines

Original Lena	Lena evolution: 69471 iterations 200 lines 2.5 hours experiment code

Conclusions: Selfish gene algorithm (sort of evolution strategy algorithm) is suitable for solving search and optimization problems, including generation of evolutionary art :-) Below are final iteration pictures better quality than gif: Have fun with selfish gene algorithm, genetic algorithms and evolution art !

Selfish Gene Algorithm

This time I will present a branch of evolutionary algorithms - Selfish gene algorithm.

Scope of article
Question arises - Why we need yet another genetic algorithm (GA) ? Well, its always good to have different point of view. It`s because selfish gene algorithm (further- SGA) is a different beast than 'standard' GA. For that reasons I will present SGA and it's uses in 2 sample problems. For the article being short I will assume reader`s basic knowledge of GA.

Biological background

Several concepts will be used here. Organism genetic makeup is called - genotype. All living organisms has DNA molecules. DNA molecule is composed of genes. Gene location in DNA is called locus. Usually for the same locus there can be different versions of gene. These different versions of gene is called alleles. There can be calculated allele frequency (or probability) in population. In general evolution means, that organisms which succeeds- increases its alleles frequency in population at the expense of children. And vise-versa,- organism which fails- decreases its alleles frequency in population.

Main features of SGA

• There are no explicit population in algorithm. Individuals are created and destroyed
  only temporary for comparision of their genomes. This means that there are no recombination operator at all. Instead new solutions is generated according to their genes frequency in population.
• Mutation operator is encoded as random gene selection (not accordingly to frequencies)
• We need not to assign absolute value of fitness to generated solution, but instead we
  need to compare 2 generated solutions between each other. And we need to return back to the algorithm which solution was better.

Pseudo-code of SGA

1. Generate 2 solutions, according to solution genes frequency/probability in population.
   1a. If mutation happens - take random solution gene, not according to its freqency.
2. Compare these 2 solutions, and decide which is better.
   2a. Reward better solution - increase its alleles frequency in population.
   2b. Penalyze worse solution - decrease its alleles frequency in population.
3. Update best solution found if any.
4. Repeat steps 1-3 until required solution found or other needed criteria is met-
   for example maximum evolve cycles elapsed or solutions genes frequency is above some threshold or whatever you need.

SGA class diagram



So main SGA classes is 4:

SGAgenotype - main class for executing GA algorithm. This class is container for SGAlocus class. SGAlocus - class is container for class SGAallele, also holds info about temporary generated solution genes.
SGAlocusGroup is just for possibility of grouping SGAlocus classes, because (you will later see it) it is sometimes usefull to do it. That is acctually SGAgenotype holds SGAlocusGroup class, which in turn groups SGAlocus.
SGAallele is class for describing allele, mainly - allele value and its frequency/probability in population.
Thats it, its all you need for SGA to run on your PC.
Practical examples of SGA usage
There was 2 cases of usage of SGA.
First - box grouping problem.
Given amount of boxes of some random sizes try to arrange boxes in some area while trying to minimize total boxes intersection area and maximize free unfragmented space left in room.
Below is video of how evolves box positions in some number of iterations:

In this type of problem SGAlocusGroup groups 2 loci - one locus for box X position and second locus for box Y position. Total SGAlocusGroup count equals to box count. Alleles encodes all possible values of box positions.
Second - sudoku puzzle generation problem
Given grid size, 9x9 or 16x16, try to generate (if possible) sudoku puzzle or at least something that is close to sudoku puzzle enough :-) . Similarity is measured by duplicating cell colors, that is by error count in grid. Different numbers is represented as different colors.
Below is video how grid evolves in some iterations:

In this problem SGAlocusGroup has only one locus, which holds info about cell color.
SGAlocusGroup count equals to grid cell count. Alleles encodes all possible colors of cell.
In the 9x9 grid case often is that there are left 2-4 color duplicates. In 16x16 case there are much more. But we can adjust evolve cycles to bigger number to overcome these errors.
C# project source files
It is for .NET 2 (VS 2005) but should run in .NET 3.5 also. You can download it here and use as you wish (GNU license):
http://coding-experiments.googlecode.com/files/SelfishGeneAlgorithm.zip
Last- useful references
1. http://www.cad.polito.it/pap/db/sac98.pdf
F. Corno, M. Sonza Reorda, G. Squillero, "The Selfish Gene Algorithm: a New Evolutionary Optimization Strategy," SAC98: 13th Annual ACM Symposium on Applied Computing, Atlanta, Georgia (USA), February 1998, pp. 349-355
2. Book "The Selfish Gene", Richard Dawkins, 1976.
Additional helper links-
http://en.wikipedia.org/wiki/Genotype
http://en.wikipedia.org/wiki/Locus_(genetics)
http://en.wikipedia.org/wiki/Allele
Thats all, have fun !!!