11 December 2008

Random notes 2008-12:

Genetic Algorithm

Evolution of Charles Darwin. I've implemented my own version of the Genetic Algorithm described by Roger Alsing in his blog ( http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa ). This algorithm finds the best set of colored triangles that could be used to re-create an original image.

On the left : the original image (via wikipdia), on the right the current image generated by the genetic algorithm at generation 240 (population:20 individuals of 50 triangles). My algorithm is currently running .
The source is available here: http://tinyurl.com/57xaeb
A short doc is available here: http://code.google.com/p/lindenb/wiki/GAMonaLisa
I've also uploaded an executable jar here: http://code.google.com/p/lindenb/downloads/list


I've uploaded a beta version of a spreadsheet-like program that I wrote for the people of my lab.
It was designed to help people with handling large tables in a rich graphical environment. It currently performs a few tasks that are common under unix. For example, it can finds the information about a column of SNP and I've implemented a grep/awk function filtering the rows with a simple javascript expression.The data are stored with the help of the Java berkeleyDB API to create an index of each row in a table.

This screenshot is a java JTable displaying the hapmap genotypes for chr1/build36/CEU. The size of the original file is 146Mo

The tool is available as a java webstart application. See http://code.google.com/p/cephlib/wiki/Workbench.


I've done a presentation on how to use a wiki in a lab. Used both OWW and wikipedia. I showed them how to edit/follow/track a page ( http://tinyurl.com/6ejw35), how to create/discuss a page with templates and categories ( http://tinyurl.com/5l5bw5 ), how files can be uploaded in a wiki and commented ( http://tinyurl.com/5ouc7y ). A demo of the wikipedia API ( http://tinyurl.com/2dp5r4 ).
People were then interested in storing+annotating (linkage) files in a wiki.


Thank you to all the crowd in FriendFeed. Really motivating.



gioby said...

why don't you share your presentation on slideshare?

Pierre Lindenbaum said...

because it was a *live* demo. No slide.

Anonymous said...

could you explain what is the relationship between random modifications of colored triangles and the formation of a human face
Is there any? If not, what does the algorithm truly proves, with respect to animal evolution?

Pierre Lindenbaum said...

random modification of the rectangles: only the best set of triangle 'wins' . The best set of triangle is the one where the colors match the best with the original picture. See another comments here: http://plindenbaum.blogspot.com/2008/12/genetic-algorithm-with-darwins-face.html

Anonymous said...

Ok, I understand the meaning of the word "genetic algorithm" in this instance, but the example has extremely little to do with actual evolution : first the terminal form (Darwin's portrait in this instance) is predetermined (which would be horrifying for Darwinian proponents); the fitness is matched against a predetermined shape which is not what nature does, second, the set of "base functions" chosen for the evolution has nothing to do with a true biological pattern formation system. Absolutely nothing, in my opinion.
A true challenge would be to implement a morphogenetic algorithm of head development, including the biomechanical field of deformation, hox genes etc. and then see how long it takes to match Darwin's face.
I understand that this example is more for fun, than really to prove anything about evolution, but the use of words such as "Darwin evolution" "genetic algorithm" etc. is somewhat dangerous and possibly ridicule. remember Alan Sokal.

Pierre Lindenbaum said...

Whatever, this kind of programming is a Genetic Algorithm . It is inspired by biological evolution the parents/solutions mate, generate children who are mutated. At the end, the best individuals will survive.
The aim here was not to mimic the evolution of a cell. It is too early for that but this is a goal of Systems Biology.

Anonymous said...

is there a possibility to upload a figure here?

Pierre Lindenbaum said...

Sorry, no time for this. You may have more information reading Roger Asling's blog or , if you're a programmer, the source code: http://code.google.com/p/lindenb/source/browse/trunk/proj/tinytools/src/org/lindenb/tinytools/GAMonaLisa.java

Anonymous said...

All right, it was just to show you that it is not too early, it can be done.