Saturday, February 21, 2009

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 LenaLena evolution:
39614 iterations
100 polygons
3.5 hours
experiment code


Lena evolved as set of lines
Original LenaLena 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 !

No comments:

Post a Comment

Comment will be posted after comment moderation.
Thank you for your appreciation.