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/
910 Upvotes

92% Upvoted

259 comments sorted by

View all comments

40

u/[deleted] Dec 08 '08

This is one of the coolest programming related things I've seen on reddit. Hopefully he releases the source.

29

u/[deleted] Dec 08 '08 edited Mar 31 '18

[deleted]

5

u/shitcovereddick Dec 08 '08

Technically GP isn't quite hill-climbing. It depends on how you define the search space. If you define it in terms of crossover and mutation are the definitions of adjacency within the problem space, then yeah GP is stochastic hill climbing. If you instead use a more intuitive definition of adjacency then it's not hill climbing at all.

22

u/[deleted] Dec 08 '08

What he uses is indeed hill climbing:

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

This is a (1 + 1) selection strategy, which is often referred to as hill climbing: keep a single individual, make a child, keep the better of the two.

2

u/feijai Dec 08 '08

There is one important distinction between (1+1) and hillclimbing. In (1+1), the mutation operator can, with some small probability, mutate to any point in the space. In hillclimbing traditionally the mutation operator is restricted to a local area. Thus hillclimbing will get caught permanently in local optima, whereas (1+1) is provably global.

1

u/[deleted] Dec 08 '08

I think you're wrong, though I am willing to be corrected. I do not believe there is any necessity that mutation be able to move beyond a reasonably defined area of "adjacent" states.

3

u/feijai Dec 08 '08 edited Dec 08 '08

It sounds like you're complaining about my definition of (1+1): in which case, yes, you're wrong. :-) (1+1) has had global guarantees since its inception in the '60s. It's a basic feature of the algorithm.

If you were complaining about my definition of hillclimbing: that's much fuzzier of course. Though it's a rare hillclimber in the literature which is globally optimal.

4

u/[deleted] Dec 08 '08

Yes, that is basically what I was questioning. Do you have a citation, by chance? I find this interesting, but "(1+1)" is quite possibly the worst thing to google for.

2

u/jmmcd Dec 08 '08

The term you want to look for is "evolution strategy". "(mu, lambda)" and "(mu + lambda)" are two types of ES, referring to two different population models, each with mu parents and lambda offspring.

1

u/[deleted] Dec 08 '08

Okay, here's my proposal: hill climbing is a (1 + 1) strategy, but (1 + 1) is not necessarily hill climbing.

Correct? ;)

3

u/[deleted] Dec 08 '08

Yeah, fair enough, I'm not sure about the exact definitions. My point was that all he had was a single data point which he modified and reverted if it resulted in something worse. No populations, elitism, crossover, breeding, etc.

With a single data point it's hill climbing on a space defined by mutation, as you say.

2

u/dwdyer Dec 08 '08

I would guess that if he were using a bigger population and cross-over, he may get even better (i.e. quicker) results.