8 ms·

Grow Your Own Picture – Genetic Algorithms and Generative Art

123 points by altern8 12y ago

fogleman 12y ago
This guy did the same thing in 2008: http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/ http://rogeralsing.com/2008/12/07/genetic-programming-evolut...
- _almosnow 12y ago
  Yeah, I remember that guy and figured it would've been the same. It's not. Nice steal Chris, at least cite the main source in your site.
  - cec 12y ago
    Hello! Chris here. I wrote this after being inspired by a GA+JS implementation by Jacob Seidelin, (attributed). Unfortunately his blog is returning a 404, but I think he in turn attributed Roger Alsing. I am absolutely not claiming the idea of genetic algorithms and art to be my own, but the code is, so I think it's unfair of you to call me a thief.
    - _almosnow 12y ago
      You updated your page in order to credit Roger... ᕦ(ò_óˇ)ᕤ 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.
  - beejiu 12y ago
    And nobody credited da Vinci.
- Scaevolus 12y ago
  Here's another Javascript version http://alteredqualia.com/visualization/evolve/ http://alteredqualia.com/visualization/evolve/
- cec 12y ago
  https://github.com/ChrisCummins/chriscummins.github.io/commit/7d2a1910c0d15d268692b7e402b93a1bc221ed30 https://github.com/ChrisCummins/chriscummins.github.io/commi...
pavlov 12y ago
Why is the collection of properties for an individual mutated shard called DNA? It doesn't really have anything to do with the actual molecule, as far as I can tell... 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); } (Wow, the downvotes are aggressive these days. Relax - it's just a joke!)
- jal278 12y ago
  That kind of data structure is just an abstraction of hereditary material, so a good way to think about it is that it is "like" artificial DNA in some gross ways. I don't think the author is trying to claim he's recreated the complexity of living organisms in his model
- jacques_chester 12y ago
  > Why is the collection of properties for an individual mutated shard called DNA? By easy analogy to biological genomes, I suppose.
  - pavlov 12y ago
    Well, sure... But I wonder if such a specific name is more confusing than useful because the analogy is off in so many ways.
    - cec 12y ago
      You are right. The "DNA" label is inaccurate, but jal278 explained the reasoning perfectly. I'd be happy to hear suggestions for a better term though! ;)
gabemart 12y ago
Great project. Love that it's configurable and open source. The analytics are a nice touch. I'm a little confused by the fitness percentage though. 98% or even 99% fitness seems to have very little immediate resemblance to the target image.
- cec 12y ago
  The fitness value represents the difference between the pixels of the "goal" image and the pixels of the current individual [1]. It will not necessarily reflect the perceived similarity between two images, which will change from person to person. https://github.com/ChrisCummins/chriscummins.github.io/blob/master/js/genetics.js#L207 https://github.com/ChrisCummins/chriscummins.github.io/blob/...
gus_massa 12y ago
It's very difficult for the algorithm to optimize the hexagons. If you change the number of vertices from 6 to 3, it runs slightly faster but the results are much better.
based2 12y ago
https://news.ycombinator.com/item?id=8696255 https://news.ycombinator.com/item?id=8696255
netcraft 12y ago
A few years ago I wrote a genetic algorithm to solve a travelling salesman problem - it was a ton of fun - I need to port it to JS one day. 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.
- lucio 12y ago
  http://agentscript.org/models/tspga.html http://agentscript.org/models/tspga.html http://agentscript.org http://agentscript.org
  - netcraft 12y ago
    very cool! thanks for the link!
- jacques_chester 12y ago
  > Ive also thought about making an algorithm that would breed JS programs to solve basic tasks 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).
  - makeset 12y ago
    In a lot of GA applications the effects of mutation are negligible. Given a large and diverse population, crossover provides enough variation already. Mutation will only be necessary to escape if the entire population has converged to a poor local optimum, but that doesn't tend to happen often in practice, and even if it does, there's no guarantee that mutation will help; hence the lack of focus on mutation operators in general.
danielweber 12y ago
For fun: start with one picture, then it run for a while, and then change the source picture
antirez 12y ago
It looks like it no longer does much progresses after some time. Many years ago I wrote one of those stuff, just a few days after the famous 2008 blog post doing the same (http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/ http://rogeralsing.com/2008/12/07/genetic-programming-evolut...). However after some time I switched the code to use simulated annealing, and it performed better. I'm running it for a few minutes against the Monalisa image to see what happens. Btw I had a plan to release the code after some cleanup, maybe tonight is the right moment after 6 years of this code hanging on my HD. EDIT: after 6 minutes (64 shapes) -> http://imgur.com/gyZCjBD http://imgur.com/gyZCjBD EDIT2: after ~15 minutes -> http://imgur.com/5XMU8vH 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 http://imgur.com/x9E9TmK EDIT4: 10 minutes more and she got a nose: http://imgur.com/bX8UTIQ http://imgur.com/bX8UTIQ EDIT5: Code released! https://news.ycombinator.com/item?id=8710418 https://news.ycombinator.com/item?id=8710418
- Dn_Ab 12y ago
  Excellent observation! In this video, Dr Christos Papadimitriou lays out a compelling argument for why genetic algorithms are poor at optimizing individual fitness when compared to simulated annealing. The video is about asexual vs sexual evolution and how it connects to multiplicative update/weighted majorty type algorithms. https://www.youtube.com/watch?v=cWv-s6KuDlM https://www.youtube.com/watch?v=cWv-s6KuDlM
- jacques_chester 12y ago
  I took a course on this stuff in uni, it was so fantastically fun to play with. 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 https://github.com/jchester/ruby-ackley-genetic-algorithm
imaginenore 12y ago
This looks more like hill climbing rather than genetic. http://en.wikipedia.org/wiki/Hill_climbing http://en.wikipedia.org/wiki/Hill_climbing
andmarios 12y ago
Every now and then comes an interesting algorithm implementation in javascript alas always single threaded. :/
- keville 12y ago
  I haven't looked at the specific source, but I can't imagine there's anything preventing this from being modified to run as a Web Worker on multiple threads.
kendallpark 12y ago
I love genetic algorithms. I wrote one for the 0-1 knapsack problem back in school, then used a genetic-ish algorithm (didn't have enough time for a true GA) to win a rock paper scissors tourney at work. 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. ;)
- jacques_chester 12y ago
  > 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. This has been tried in the literature -- usually by adding those parameters to the genome. Basically it's a wash.
  - kendallpark 12y ago
    Good to know! Thanks.
RogerAlsing 12y ago
Nice to see another spinoff :) Great to see this post now since it is exactly 6 years since my EvoLisa post was released today :)
- minimax 12y ago
  EvoLisa was a great post. I spent a few nights trying to reproduce it and I'm sure I wasn't the only one. I eventually got to the point where I was using SSE instructions (I think it was PSADBW) to speed up the fitness function. It was loads of fun. OpenGL is probably the solution to really upping the generation frequency, but I stopped messing with it before I got there.
userbinator 12y ago
It'd be nondeterministic and quite time-consuming, but this suggests an image compression algorithm that could conceivably come up with very compact representations of its input.
- dmurray 12y ago
  I tried this as a college project inspired by the Roger Alsing post. Unfortunately I didn't create anything usable. If I was doing it again I'd use a SA approach or pure hillclimbing like Alsing - as antirez points out in a sibling post, crossover between diverse individuals rarely gives viable offspring with this problem.
thisisdave 12y ago
I'm having fun with this, thanks for posting it. 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_of_natural_selection https://en.wikipedia.org/wiki/Fisher%27s_fundamental_theorem...
ada1981 12y ago
would be cool to be able to upload your own photos / pull in from instagram, etc. 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!
darkFunction 12y ago
I wrote something similar- first I did a hill climbing implementation and then a genetic one. The genetic algorithm worked way better: https://github.com/darkFunction/PolygonPainter https://github.com/darkFunction/PolygonPainter

123 points by altern8 12y ago

This guy did the same thing in 2008: http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/ http://rogeralsing.com/2008/12/07/genetic-programming-evolut...

_almosnow 12y ago
Yeah, I remember that guy and figured it would've been the same. It's not. Nice steal Chris, at least cite the main source in your site.
- cec 12y ago
  Hello! Chris here. I wrote this after being inspired by a GA+JS implementation by Jacob Seidelin, (attributed). Unfortunately his blog is returning a 404, but I think he in turn attributed Roger Alsing. I am absolutely not claiming the idea of genetic algorithms and art to be my own, but the code is, so I think it's unfair of you to call me a thief.
  - _almosnow 12y ago
    You updated your page in order to credit Roger... ᕦ(ò_óˇ)ᕤ 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.
- beejiu 12y ago
  And nobody credited da Vinci.
Scaevolus 12y ago
Here's another Javascript version http://alteredqualia.com/visualization/evolve/ http://alteredqualia.com/visualization/evolve/
cec 12y ago
https://github.com/ChrisCummins/chriscummins.github.io/commit/7d2a1910c0d15d268692b7e402b93a1bc221ed30 https://github.com/ChrisCummins/chriscummins.github.io/commi...

pavlov 12y ago

Why is the collection of properties for an individual mutated shard called DNA? It doesn't really have anything to do with the actual molecule, as far as I can tell... 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); } (Wow, the downvotes are aggressive these days. Relax - it's just a joke!)

jal278 12y ago
That kind of data structure is just an abstraction of hereditary material, so a good way to think about it is that it is "like" artificial DNA in some gross ways. I don't think the author is trying to claim he's recreated the complexity of living organisms in his model
jacques_chester 12y ago
> Why is the collection of properties for an individual mutated shard called DNA? By easy analogy to biological genomes, I suppose.
- pavlov 12y ago
  Well, sure... But I wonder if such a specific name is more confusing than useful because the analogy is off in so many ways.
  - cec 12y ago
    You are right. The "DNA" label is inaccurate, but jal278 explained the reasoning perfectly. I'd be happy to hear suggestions for a better term though! ;)

gabemart 12y ago

Great project. Love that it's configurable and open source. The analytics are a nice touch. I'm a little confused by the fitness percentage though. 98% or even 99% fitness seems to have very little immediate resemblance to the target image.

cec 12y ago
The fitness value represents the difference between the pixels of the "goal" image and the pixels of the current individual [1]. It will not necessarily reflect the perceived similarity between two images, which will change from person to person. https://github.com/ChrisCummins/chriscummins.github.io/blob/master/js/genetics.js#L207 https://github.com/ChrisCummins/chriscummins.github.io/blob/...

gus_massa 12y ago

It's very difficult for the algorithm to optimize the hexagons. If you change the number of vertices from 6 to 3, it runs slightly faster but the results are much better.

based2 12y ago

https://news.ycombinator.com/item?id=8696255 https://news.ycombinator.com/item?id=8696255

netcraft 12y ago

A few years ago I wrote a genetic algorithm to solve a travelling salesman problem - it was a ton of fun - I need to port it to JS one day. 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.

lucio 12y ago
http://agentscript.org/models/tspga.html http://agentscript.org/models/tspga.html http://agentscript.org http://agentscript.org
- netcraft 12y ago
  very cool! thanks for the link!
jacques_chester 12y ago
> Ive also thought about making an algorithm that would breed JS programs to solve basic tasks 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).
- makeset 12y ago
  In a lot of GA applications the effects of mutation are negligible. Given a large and diverse population, crossover provides enough variation already. Mutation will only be necessary to escape if the entire population has converged to a poor local optimum, but that doesn't tend to happen often in practice, and even if it does, there's no guarantee that mutation will help; hence the lack of focus on mutation operators in general.

danielweber 12y ago

For fun: start with one picture, then it run for a while, and then change the source picture

antirez 12y ago

It looks like it no longer does much progresses after some time. Many years ago I wrote one of those stuff, just a few days after the famous 2008 blog post doing the same (http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/ http://rogeralsing.com/2008/12/07/genetic-programming-evolut...). However after some time I switched the code to use simulated annealing, and it performed better. I'm running it for a few minutes against the Monalisa image to see what happens. Btw I had a plan to release the code after some cleanup, maybe tonight is the right moment after 6 years of this code hanging on my HD. EDIT: after 6 minutes (64 shapes) -> http://imgur.com/gyZCjBD http://imgur.com/gyZCjBD EDIT2: after ~15 minutes -> http://imgur.com/5XMU8vH 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 http://imgur.com/x9E9TmK EDIT4: 10 minutes more and she got a nose: http://imgur.com/bX8UTIQ http://imgur.com/bX8UTIQ EDIT5: Code released! https://news.ycombinator.com/item?id=8710418 https://news.ycombinator.com/item?id=8710418

Dn_Ab 12y ago
Excellent observation! In this video, Dr Christos Papadimitriou lays out a compelling argument for why genetic algorithms are poor at optimizing individual fitness when compared to simulated annealing. The video is about asexual vs sexual evolution and how it connects to multiplicative update/weighted majorty type algorithms. https://www.youtube.com/watch?v=cWv-s6KuDlM https://www.youtube.com/watch?v=cWv-s6KuDlM
jacques_chester 12y ago
I took a course on this stuff in uni, it was so fantastically fun to play with. 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 https://github.com/jchester/ruby-ackley-genetic-algorithm

imaginenore 12y ago

This looks more like hill climbing rather than genetic. http://en.wikipedia.org/wiki/Hill_climbing http://en.wikipedia.org/wiki/Hill_climbing

andmarios 12y ago

Every now and then comes an interesting algorithm implementation in javascript alas always single threaded. :/

keville 12y ago
I haven't looked at the specific source, but I can't imagine there's anything preventing this from being modified to run as a Web Worker on multiple threads.

kendallpark 12y ago

I love genetic algorithms. I wrote one for the 0-1 knapsack problem back in school, then used a genetic-ish algorithm (didn't have enough time for a true GA) to win a rock paper scissors tourney at work. 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. ;)

jacques_chester 12y ago
> 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. This has been tried in the literature -- usually by adding those parameters to the genome. Basically it's a wash.
- kendallpark 12y ago
  Good to know! Thanks.

RogerAlsing 12y ago

Nice to see another spinoff :) Great to see this post now since it is exactly 6 years since my EvoLisa post was released today :)

minimax 12y ago
EvoLisa was a great post. I spent a few nights trying to reproduce it and I'm sure I wasn't the only one. I eventually got to the point where I was using SSE instructions (I think it was PSADBW) to speed up the fitness function. It was loads of fun. OpenGL is probably the solution to really upping the generation frequency, but I stopped messing with it before I got there.

userbinator 12y ago

It'd be nondeterministic and quite time-consuming, but this suggests an image compression algorithm that could conceivably come up with very compact representations of its input.

dmurray 12y ago
I tried this as a college project inspired by the Roger Alsing post. Unfortunately I didn't create anything usable. If I was doing it again I'd use a SA approach or pure hillclimbing like Alsing - as antirez points out in a sibling post, crossover between diverse individuals rarely gives viable offspring with this problem.

thisisdave 12y ago

I'm having fun with this, thanks for posting it. 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_of_natural_selection https://en.wikipedia.org/wiki/Fisher%27s_fundamental_theorem...

ada1981 12y ago

would be cool to be able to upload your own photos / pull in from instagram, etc. 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!

darkFunction 12y ago

I wrote something similar- first I did a hill climbing implementation and then a genetic one. The genetic algorithm worked way better: https://github.com/darkFunction/PolygonPainter https://github.com/darkFunction/PolygonPainter