Genetic Programming: Evolution of Mona Lisa
rogeralsing.com
rogeralsing.com
Sadly I don't think there is too much commercial value in extraordinarily CPU-intensive lossy image compression but it sure beats the heck out of 99.5% of what I saw in undergraduate AI/algorithms-type courses as a demo.
Incidentally, I think from a marketing perspective that is a great test case to use for it. If you had picked, I don't know, some portrait by an unknown artist it would have been no less technically impressive but it wouldn't spread NEARLY as far. (This is one reason why I managed to work the KJV Bible and the US Constitution into my test corpora for almost every natural language processing project I've ever done.)
For example, NASA used evolutionary computation to design a little antenna thing, and it went into space, and it was human-competitive (as good or better than anything a human could design in a reasonable amount of time). http://ti.arc.nasa.gov/projects/esg/research/antenna.htm
Most of the applications, in other words, have little to do with the kind of highly data-driven web applications with rapidly changing requirements that seems to occupy a lot of the time of the users on this site. :( Still, excellent candidate for spare-time/weekend hacking.
Finally, one basic thing to observe about most of these heuristics is that they are embarrassingly parallel, which means they really could make good use of a 16-core machine.
First, as commenters on that post pointed out, this is horribly inefficient. It's not even a GA, it's a blind hill climber! Hint: you need crossover; calling something "DNA" is not sufficient.
Second, even if it's a large image, and takes say 10 minutes on a laptop-class computer, that's 1 cent on EC2. Computing power has gotten ridiculously cheap.
Third, here is at least one killer app: mobile. B/W still sucks, and rendering speed could use some help as well. I can certainly imagine large websites benefitting from this. This is basically a raster to vector converter. You could start using this right now in SVG enabled environments.
Finally, I just thought of something truly sick. Note that you can draw arbitrary polygons using javascript. http://www.uselesspickles.com/triangles/demo.html Put these two together, and... dear God, I don't even want to think about it.
It makes me wonder whether there is some demoscener who has already done something like this to fit the Mona Lisa (or probably something geekier, like a picture of Clive Sinclair) into their 4k demo.
Take pictures of a 3D object from say 100 different angles, remembering which angles they were. Now, use this mona lisa algorithm to put 3D polygons inside a box of sufficient size, keep those that most look like the original object when looked at from all those angles.
Will you get a compressed 3D representation of an object this way?
A typical application is when they measure brain signals at the surface of the brain and then try to reconstruct what happens inside. Have people thought of using genetic algorithms and other stochastic methods ? Probably yes.
"At each step, the SA heuristic considers some neighbour s' of the current state s, and probabilistically decides between moving the system to state s' or staying in state s. The probabilities are chosen so that the system ultimately tends to move to states of lower energy. Typically this step is repeated until the system reaches a state that is good enough for the application, or until a given computation budget has been exhausted."
Want evidence? Look at the iteration counts. With SA, you'd see the differences between the successive pictures be roughly constant or even decrease (I can't prove it, but I've implemented it, and you usually end up choosing a cooling heuristic that roughly matches the human intuition for "closeness").
As it is, the algorithm that's implemented finds it exponentially harder to get close to optimum. You start off with a gap of 100 iterations between optima, and you end up at 300,000.
Which is exactly why I think this is even more amazing -- it's just about the dumbest algorithm you can think of, and it still manages to vectorize an arbitrary raster image. If an actual GA or SA version were built, it could have some real potential. (See my comment below.)
from __future__ import division
import matplotlib.mlab as M
import matplotlib.pyplot as plt
import random as R
def crossover(a, b):
new = []
for x,y in zip(a,b):
if R.random() > 0.5:
new.append(x)
else:
new.append(y)
return new
def mutate(xs):
xs[int(R.uniform(0, len(xs)))] = int(R.uniform(1, 10))
return xs
def fitness(xs, goal):
summa = 0
for x,y in zip(xs, goal):
summa += abs(x-y)
return summa, xs, True if summa == 0 else False
def nFittest(xs, goal, n=2):
fittest = sorted(fitness(x, goal) for x in xs)[:n]
if fittest[0][2] :
return fittest[0]
elif fittest[1][2]:
return fittest[1]
else:
return fittest
def init(fields, n):
return [[int(R.uniform(1,10)) for x in xrange(fields)] for y in xrange(n)]
def newGen(a,b,n):
next = [crossover(a,b) for x in xrange(n)]
mutated = []
for x in next:
if R.random() > 0.9: mutated.append(mutate(x))
else: mutated.append(x)
return mutated
def run(printing=True):
n = 0
first = init(15, 10)
while n < 1000000:
n += 1
next = nFittest(first, [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], 2)
if type(next) == tuple: break
first = newGen(next[0][1],next[1][1], 10)
if printing:
print "Nbr of generations: ", n
print next
return n, next
def plot():
trials = [run(False)[0] for x in range(100)]
print "Done trials"
averages = [sum(trials[:x]) / len(trials[:x])\
for x in xrange(1,len(trials)+1)]
print "Done averages"
plt.plot([x for x in xrange(len(averages))], averages, 'ro')
plt.axis([1, 100, 0, 1000])
plt.show()
def test():
goal = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
c=0
while 1:
c += 1
x = [int(R.uniform(1,10)) for y in range(15)]
if sum(x) == 15: break
if c % 10000 == 0: print c
print xYeah, I guess this is GA alright. Your crossover is not right -- it should "cross over" at one point, not flip flop at each location :-)
[Edit] And there's a lot of in-breeding going on! You want to keep 10-20 sequences from each generation, not just 2.
That being said, his approach is also a viable GA operator. It is called a uniform crossover. But really, to qualify as a GA, his solution only needs some kind of variation, mutation, and selection.
Here's Koza's material from his Stanford class: http://www.genetic-programming.com/coursemainpage.html
BTW your comment was eponysterical :)
Although part of the reason I picked that username is that a lot of my work involves statistics/probability, so it's not entirely a coincidence that I should be posting about this.