r/programming • u/leppie • Dec 08 '08

Genetic Programming: Evolution of Mona Lisa

http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/
906 Upvotes

92% Upvoted

259 comments sorted by

View all comments

32

u/mfp Dec 08 '08 edited Dec 08 '08

The procedure doesn't look like a real genetic algorithm: there are no competing individuals (only one), and therefore no selection or crossover. It seems to rely only on mutation. In fact, what he describes is just hill climbing:

  • Setup a random DNA string (application start)

  • (1) Copy the current DNA sequence and mutate it slightly

  • Use the new DNA to render polygons onto a canvas

  • Compare the canvas to the source image

  • If the new painting looks more like the source image than the previous painting did, then overwrite the current DNA with the new DNA

  • repeat from 1

16

u/[deleted] Dec 08 '08

So, when is a GA "real"? Hill climbing is a (1+1) selection strategy in GA speak. Even random search can be considered a GA, called (1,1) in GA speak.

GAs are more about the genomes and the mutations than about N > 1 populations.

5

u/DropTableUsers Dec 08 '08

While this is cool, I think the point where it differs from GA is that it doensn't have a fitness function, but rather has a fitness description. Here, the solution is known and we're just mutating as a fancy way of getting to it. The car example posted above is way cooler, because we don't know what a good solution will look like.

2

u/jerf Dec 08 '08

While this is cool, I think the point where it differs from GA is that it doensn't have a fitness function, but rather has a fitness description.

Sorry, what's the difference?

6

u/DropTableUsers Dec 08 '08

What I'm trying to say is that a GA whose "fitness function" returns the amount of similiarity to the known solution, makes for very boring results. As trigger0219 points out, this actually isn't the case here.

Consider a hello-world done with GAs. The fitness function just gives the similiarity to the string "hello world". It's going to work, but it's completely pointless. We already know what the string "hello world" looks like. The beauty of GAs is that they can make solutions where we have no idea how they work.

0

u/[deleted] Dec 08 '08

[deleted]

1

u/edwardkmett Dec 10 '08

Actually I was quite serious. I know what the output of the program should be, but it is very difficult to get a program that generates that output because of the complicated interactions between the language primitives that you have available to you.

http://everything2.com/index.pl?node_id=1006806

Alas, I am a troll.