My First Attempt At Genetic Programming

A couple of weeks ago I found this quite impressive post by Roger Johannson about approximating an image to Mona Lisa. At that time I was in search of ideas for a project to improve my coding skills and learn something new, and this was a perfect option. So I’ve decided to try and write something similar.

My implementation is written in C++ and OpenGL for rendering.
I haven’t found much on the topic of genetic image approximation, so I’m going to describe my program more precisely.

The idea behind it is as follows:
1. Create a population of chromosomes, consisting of genes, which represent 3 vertices and a colour of a triangle, at random.
2. Calculate fitness of each chromosome, comparing it to the original image.
3. For each chromosome, except for a few ‘elite’ ones, determine by chance if it is to be replaced by a result of mating two other chromosomes, or if it has to mutate.

Mating can be done in two ways:
1) Randomly select one point in a chromosome. A child chromosome will inherit all genes before this point from one parent, and all genes after it from another.
2) Each gene of a child will have a 50/50 chance of inheriting it from one of the parents.
Mutation methods are:
1) Based on a chance, each coordinate of each vertex and the colour of a gene will be changed by a small value.
2) Based on a chance, each coordinate of each vertex and the colour of a gene will be changed to a new random value.
Plus there is a chance, that two genes will swap their positions in a chromosome.

4.Calculate new fitness values for the chromosomes that have changed.
5.Repeat from 3.

This is the result.
Some values still need some tweaking, but it is not bad, in my opinion.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s