Grow Your Own Picture – Genetic Algorithms and Generative Art
chriscummins.cc
chriscummins.cc
EDIT: after 6 minutes (64 shapes) -> http://imgur.com/gyZCjBD
EDIT2: after ~15 minutes -> http://imgur.com/5XMU8vH
Now trying using just triangles, again with 64 shapes, I remember it was much better than when using circles for most images.
EDIT3: Oh, much better now, after 6 minutes (64 triangles) -> http://imgur.com/x9E9TmK
EDIT4: 10 minutes more and she got a nose: http://imgur.com/bX8UTIQ
EDIT5: Code released! https://news.ycombinator.com/item?id=8710418
Simulated annealing has less cachet than GAs (and other evolution-inspired approaches) but tends to perform well enough on lots of problems that you might as well skip GAs.
I haven't dug much on the linked GA, but it looks like it converges too quickly. That's a classic problem (exploration vs exploitation, aka coverage vs convergence) in optimisation problems. The problem I practiced on was Ackley's Function[1]. Even in 2 dimensions it's really good at tripping up algorithms that converge too eagerly.
Some GA methods actually make the parameters of the system part of the genome, but as I recall it doesn't make a huge difference overall. Fun to think about though.
Mind you, the No Free Lunch Theorem means that there's a place for everyone in the heuristic computing tent. And simple random sampling (monte carlo method) and/or graphing can be very helpful for looking for the contours of a solution space. There's still room for humans too.
[1] https://github.com/jchester/ruby-ackley-genetic-algorithm
So actually I think this demonstrates a kind speciation in a very sharply divided landscape. It'd probably work better on simple images with smooth gradients and the like.
The nicest approach to exploration/exploitation I've seen for simulated annealing is to run two searches side-by-side. Their relative "temperatures" (ie. probability of accepting a worse solution) depends on their relative fitness: if both are the same fitness, both have the same temperature; if one has higher fitness than the other, its temperature lowers (so it can "focus" on that high-fitness region) whilst the other's temperature raises (so it can "spread out" to find higher-fitness regions).
Also, regarding the No Free Lunch Theorems, I don't give them much thought since they don't take the computational complexity of the problem into account. They say that every search algorithm, when averaged over all problems, achieves total performance that's the same as random search. The real world doesn't contain all problems; in particular, we care more about (computationally) simple problems than unrealisitically-complex ones. Worrying about NFL for search is like worrying about adversaries with infinite computing power in crypto; yes your algorithm will be weak against such an attacker, but it's unrealistic to care about.
1. Stop trying to prove that your solution is the "best overall"
2. Hooray, we can pick and choose our tools.
We were told early in public school that we share 98% (or some such very high number percent) of our DNA with our simian relatives. I always was amazed at how just small a section of the genome was responsible for such amazing diversity among primates, or even mammals in general.
Seeing the wild differences that result in these images when you're given 3% of leeway between generations really helps me appreciate the vast number of individuals in our species!
http://rogeralsing.com/2008/12/07/genetic-programming-evolut...
Anyway, don't take it personal, its just that it appeared to me that it was very obvious when you even used the same seed image.
I'd love to see reports of basic genetic genetic properties of the population. What's the variance in fitness within each generation? This turns out to be the key factor in the rate of evolution [1], assuming that one defines fitness the way that geneticists do.
Also, estimates of the relative strengths of mutation, selection, and drift would be nice, as would options for distinguishing between hard and soft selection. These sorts of diagnostics and options could really improve the method's effectiveness.
[1] https://en.wikipedia.org/wiki/Fisher%27s_fundamental_theorem...
By the same logic, this is a C2H6O simulator:
var s = "I'm going to get drunk";
for (var i = 0; i < 10000; i++) {
var idx = Math.floor(Math.random()*s.length);
var c = s.substr(idx, 1);
s = s.substr(0, idx) + s.substr(idx-1, s.length-1-idx);
idx = Math.floor(Math.random()*s.length);
s = s.substr(0, idx) + c + s.substr(idx, s.length-idx);
}
By easy analogy to biological genomes, I suppose.
Ive also thought about making an algorithm that would breed JS programs to solve basic tasks - sort an array of input or find the longest consecutive group of numbers. Maybe one day I'll find the time.
When you do, a useful tip: in the literature, Genetic Algorithms are distinct from Genetic Programming.
GAs evolve collections of parameters into a function or group of functions.
GPs evolve actual executable programs. Mostly as interpreter trees, though some experiments have been done with evolving strings of machine code for real and virtual machines.
So in your case, the place to start is Genetic Programming.
ps. it's freakishly slow and the GP literature is really fixated on favouring one evolution step almost to the exclusion of others (I can't remember if it's the crossover step or mutation step).
I've heard good things about Essentials of Metaheuristics[3] and Clever Algorithms[4] too, I would like to read them some day.
[1] http://www.gp-field-guide.org.uk/
[2] http://www.cs.vu.nl/~gusz/ecbook/ecbook.html
It seems to me that one needs another genetic algorithm to manage all the variables (such as mutation rate, population size, crossover, etc) because they have such an impact on the effectiveness of the algorithm.
Gives me way more respect for mother nature. ;)
This has been tried in the literature -- usually by adding those parameters to the genome. Basically it's a wash.
https://github.com/ChrisCummins/chriscummins.github.io/blob/...
you might make a little coin by piping the finished images to a t-shirt or skin printer.
we'd be happy to give a free CreditCover, credit card skin to any one who wants one using your imagery. We have a standing $10 gift code for hacker news users (hackernews) but we could make something specific for you if you like.
CreditCovers.com/DIY
cool!