Genetic Programming: Evolution Of The Mona Lisa
Roger Asling wrote a program that draws pattens of polygons generated from a string of digital "DNA." He then mutated the DNA and selected the DNA that generated polygons that looked more like the source image (in this case, Mona Lisa) to live and have mutant babies. He repeated the process 904,314 times until he ended up with a 50 polygon image that looks just like the Mona Lisa.
Genetic Programming: Evolution Of The Mona Lisa (Via Presurfer)
the latest
latest episodes
That's not evolution, that's "Intelligent Design".
Seriously. In fact, this quite nicely illustrates the important difference between the two concepts:
While evolution supports any of a multitude of viable outcomes, ID works toward a predetermined specific goal (the "design").
Afraid I have to disagree with 1. This is just an example of a genetic algorithm, although not a very robust one, since the population is only 1 member. It would be intelligent design if he'd manually manipulated the bit strings, but according to the link the computer did everything randomly. And computers have no intelligence, so hence no intelligent design.
Yes, the strings were evolving towards a goal. But it was every bit as arbitrary having a gene that encodes polygons and grants survival to polygons that look like a painting, as it is to have genes which encode organs and grant survival based on their ability to properly process oxygen.
Its not really evolution or intelligent design. Evolution has a "fitness function" in a very loose sense too. In nature, if you meet some unknown criteria that determine your reproductive success, you are more likely to reproduce successfully. Your ability to reproduce successfully is an unknown function of all of the characteristics that make up you, plus a lot of chance.
Here they make the function explicit (similarity to the mona lisa) and keep the best example for later mutation. It is a bad evolutionary algorithm in a few other ways though. There don't seem to be multiple genetic lines, or genetic recombination. Its really more of a stochastic gradient ascent than evolution. If the offspring is better than the parent, kill the parent and replace them with the offspring.
The bicycle genetic algorithm from earlier in the day was much better. In that algorithm, the best offspring from any generation mixed their dna and then had it slightly mutated, forming the next generation. It was possible, and common, for the next generation to be worse than the previous, but the overall trend was for improved fitness.
Still, the arbitrary fitness function is a part of any genetic algorithm, and that is an important distinction between GA and actual evolution.
Maybe it's easier to think of this in terms of cryptic coloration and predators. The researcher played the role of a predator that ate every batch of polygons that couldn't hide on the Mona Lisa to some degree of success. The predator learned each time and the poor polygons had to try harder to fool him. Finally the wily survivor, descendant of hundreds of thousands of generations of the greatest butterfly ninjas of its people was captured by the researcher and pinned to a research paper. Such is life.
I would still argue that the ability to live is an arbitrary fitness function, just an incredibly complex one with, in general, more variables than are observed in the average GA.
Not to say that GAs are a particularly good mimic of evolution (though they're better mimics than many optimization algorithms), but I don't think the arbitrary fitness function is the biggest difference by a long shot.
Selecting reproductive winners on the basis of how closely they match The Mona Lisa is analogous to nature having selected reproductive winners on the basis of how closely they matched Homo Sapiens Sapiens.
That's not how evolution works. It is how "Intelligent Design" would have to work.
Whatever it may represent, evolution, ID, or door #3... we can still agree it's pretty cool, right?
prom77:
Sorry, yes, absolutely cool! I didn't mean to suggest otherwise.
This is an example of artificial selection. This is what we did with dogs and bananas (atheist's nightmare).
to #9
They have a non-slip grip and curve toward the mouth for easy insertion! They even have color coded packaging indicating freshness. Of course god exists!
The Unusual Suspect has it right: though interesting, this is not a good example of evolution, or even of genetic algorithms, because you already know what the end result is.
Selecting for "nearness to the end result" isn't evolution, it's just path-finding.
Create a 2D landscape. Start at one corner. "Mutate" a bunch of children near you. Pick the one closest to the opposite corner. Repeat. Voila, in enough generations you will reach the opposite corner.
That's actually exactly what this algorithm is doing, with the 2D landscape replaced by an n-dimensional set of attributes.
The bike example from earlier was much more interesting, because it was trying to find an unknown end.
(I actually wrote my master's thesis on genetic algorithms for problems for which you could show that there was no way you could find the end result just by picking examples that were "closer" to the end result, which was also quite interesting.)
Would a simulation where you artificially created an environment wherein an image that looked more like the Mona Lisa stood a greater chance of "success" in some goal be closer to "evolution" than the algorithm this is?
I'm having trouble thinking of something that would truly represent evolution (though not in an organic sense) but I'm interested in finding something that would represent principles of evolution. Does anybody have an idea how to pull this plan off?
... actually, I'm backing off my statement above just a little. The "end" sought here was not a reproduction of the Mona Lisa, but rather the best way to arrange 50 transparent shapes to create the Mona Lisa, which actually creates a more interesting fitness landscape than at first blush, as there are multiple solutions and presumably local maxima and the like.
Here the genotype =/= the phenotype, and thus the end result is not actually given from the start.
I that case my main argument is about the simplicity of the algorithm chosen (which is still exactly the same as my 2D corner-to-corner path-finding above), as a more interesting algorithm could probably have found a solution in rather faster time.
The Unusual Suspect @8
Didn't mean to suggest you did. :)
Of course it's artificial selection, it's running on a computer. Maybe it'd be natural selection if keyboard input was factored into the fitness function and he put a monkey in front of the keyboard.
@Samsam:
Deceptive problems, eh?
@Kattw:
Evolutionary computing operates on more than one individual. The idea is you create N random individuals, rate them according to their fitness, and then the ones that are more fit overall tend to mate, mutate, reproduce. When you have N new individuals, you have the next generation, and you keep going.
EC is essentially stochastic hill-climbing, and the more individuals you have, the more points in the fitness landscape you can explore. A single individual would perform, like, no search.
if there's already a target, isn't it: "intelligent design" ?
bwahahahahahahaaa!!!
but seriously, it would be evolution if the mona lisa arrived spontaneously without a target
The real problem is calling this a genetic algorithm when there is no cross-over mutation. Call it by its correct name instead: Simulated Annealing (http://en.wikipedia.org/wiki/Simulated_annealing).
Biologically-inspired genetic algorithms are mostly hype anyway... people doing serious optimization don't use them much.
This looks cool but isn't particularly difficult to do. I did something similar for a high school science fair competition in 1991, but instead of polygons my domain was fractal ferns. I made random mutations of the fractal parameters and I kept changes that resulted in larger surface area. I got 2nd at the county level, 1st place went to a project that emulated robots, and used a proper genetic algorithm to evolve their walking algorithm.
Sweet Zombie Jesus: It's only SA if he's changing the randomization function based on the temperature (generally the closeness to the solution). I don't see any suggestion that this is doing that.
This is just a hill-climber algorithm.
I'd like to see this implemented again, using cross-over, larger populations, and stochastic selection to keep the diversity high. I bet you'd find an increase in time to convergence. I'd also like to see this done on a harder problem -- maybe using fewer polygons. The fact that a hill-climbing algorithm found this first time means that it didn't get stuck in any local maximum, which means the fitness landscape was quite simple.
BTW, I like the notion presented in the thread on the page that this could be a compression and vectorization algorithm. Horribly, horribly inefficient to get there, but once there, probably quite compressed!
oops my bad, just read post #1. ah well, i concur.
#4 Procrastes
I enjoyed your explanation and imagery, immensely.
Imagine a species of butterfly that has Mona Lisa pattern on its wings. This butterfly also happens to be poisonous to birds. There also exists another species of butterfly with similar colored wings that isn't poisonous. The butterflies that don't look sufficiently like Mona Lisa butterflies get eaten. The ones that look a little more like the poisonous butterflies are less likely to get eaten. Natural selection would drive the evolution of the non-poisonous butterflies towards having Mona Lisas on their wings, like the poisonous butterflies.
APNG from the original GIF: http://img114.imageshack.us/img114/5268/monalisahh3.png
(1 MB, AFAIK works only with Firefox >=3 and Opera >= 9.5)
Now, if someone would only write a program to control a robot to make sculptures out of junkyard junk (maybe virtually), and if this program included arbitrary parameters that affect the sculptures' shapes and that could be randomly mutated and cumulatively passed on, and if the programs were then selected over many generations for making sculptures that are shaped like the structure and interior and engines of a Boeing 747... then maybe those ID people would get why their 747 analogy is not valid.
Nah, they probably wouldn't.
@12
Perhaps each of the successive mutations could be rated for beauty by humans on the web, using distributed social computing. Thus, the most beautiful painting/mutation would emerge.
It is evolution.
The designs die out if they are no good, they get reverted back to the "father" of that species. So cel 137 may have 700 kids, but only the best one survived (natural selection), which in this case is always the last one because it has to be "better" than the previous generation. The predetermined goal is not the Mona Lisa, it is just "better than the previous generation". It is however, asexual in it's reproduction. Not ID, Evolution.
This is INTELIGENT DESIGN
where the creator has an preset end-state for his creations - in this case the Mona Lisa. Or in God's case - humans.
This is quite the opposite of what most genetic algorithms are about.
A good genetic algorithm has no end-state.
I wish I noticed this earlier so I coulda posted sooner.
As a staunch believer in macro and micro evolution, there has been an often misused analysis in this discussion (both on this board and the source board).
Design.
The more you understand evolution, the more you understand that evolution IS about design.
It's about a "bottom-up" design process, opposed to the "top-down" design process of creationists.
It's absolutely evolution.
Ignore for the fact that the target is a known picture. Instead let's say the target is...
An underwater habitat, 30 degrees Celsius, very little sunlight, relatively high salinity, marked amounts of bacteria from a thermal vent.
That's our target.
We want a lifeform that fits that mold. That target.
It then follows the standard suit of evolution for one cell organisms to grow and fit that niche. Some will be better suited, they'll live to spread their genetic material to offspring who will be similar. The better they fit the target, they better their ability to pass their material onward.
So not only IS it design, it's a perfect illustration of evolution. Not the "creation requires a creator" fallacy. If it was, then the software would have generated it in 3 or 4 iterations the way that Davinci probably did.
Not the hundreds of thousands it took the software to evolve the image.
Unless you mean your creator created creation of the course of millions and millions of subtle changes.
I don't agree with your use of the word 'design', at all. Design requires intent and an agent.
You are just confusing the issue by calling it design, when really it is influenced, iterative interaction.
deâ‹…sign
   /dɪˈzaɪn/ Show Spelled Pronunciation [di-zahyn] Show IPA Pronunciation
–verb (used with object)
1. to prepare the preliminary sketch or the plans for (a work to be executed), esp. to plan the form and structure of: to design a new bridge.
2. to plan and fashion artistically or skillfully.
3. to intend for a definite purpose: a scholarship designed for foreign students.
4. to form or conceive in the mind; contrive; plan: The prisoner designed an intricate escape.
5. to assign in thought or intention; purpose: He designed to be a doctor.
6. Obsolete. to mark out, as by a sign; indicate.
–verb (used without object)
7. to make drawings, preliminary sketches, or plans.
8. to plan and fashion the form and structure of an object, work of art, decorative scheme, etc.
–noun
9. an outline, sketch, or plan, as of the form and structure of a work of art, an edifice, or a machine to be executed or constructed.
10. organization or structure of formal elements in a work of art; composition.
11. the combination of details or features of a picture, building, etc.; the pattern or motif of artistic work: the design on a bracelet.
12. the art of designing: a school of design.
13. a plan or project: a design for a new process.
14. a plot or intrigue, esp. an underhand, deceitful, or treacherous one: His political rivals formulated a design to unseat him.
15. designs, a hostile or aggressive project or scheme having evil or selfish motives: He had designs on his partner's stock.
16. intention; purpose; end.
17. adaptation of means to a preconceived end.
Origin:
1350–1400; ME designen
come to think of it, why "intelligent" design? Why didn't they just stick with "design"?
wait a minute, got it: they didn't want their god mixed up with the dumb ones.
Takuan @32
Good point. Does seem redundant.
#30 I'm not sure I agree with that, but I'll see what I can do.
The intent is to fit the target.
Whether it's the Giocondo or my made up underwater niche. The point of changing or evolving it to succeed in that framework. To be better fit for that environment.
The agent is the evolving itself.
This might not seem intuitive at first but 'agent' invokes purpose and desire. You'll be hard pressed to find a population who is not interested in surviving. The fact that the majority of known life shows signs of self preservation and are capable of enacting on behalf of themselves is enough to show they can act as your agent in this situation.
The mona lisa program wants to be closer to the target photo. It allows iterations that aren't properly suited to fall away. It wants to fit the niche.
It's hard to say 'snow rabbits want to be white'. It gives too much logic to the rabbits. But it's not that hard to say 'snow rabbits want to live'. Most life does. The fact that they probably don't know that being white furred increases that chance isn't evolutionarily necessary - the bright green rabbits wouldn't stand a chance and will be naturally selected against.
I still don't agree with your requirements to define 'design' but, there ya go. Agent and intent.
#28, and everyone who said something similar:
No it's not, as I noted in #13.
The creator didn't know what the final state would be. He knew what it would look like, but did not know how he could fit together 50 overlapping polygons to make it look like that.
If you had 50 colored overlapping polygons in a heap, do you think you could create the Mona Lisa? No. It would be very, very difficult without a lot of trial and error.
That's what the program was trying to create: the best way to fit together 50 overlapping polygons to create a defined shape. NOT to "draw the Mona Lisa." And it isn't a trivial difference.
It's like suggesting that using EAs to design circuits (e.g. [1], [2], [3]) isn't evolution, because the engineers already knew what the circuit was supposed to do.
Now, I think that he could have used more interesting Genetic Algorithm techniques, and maybe made the problem more difficult by allowing fewer polygons, but the fact remains that the end was not pre-defined: he had no idea how the polygons would eventually fit together, or even if it was possible.
#23, in fact many species and varieties of butterfly and moth have evolved wing patterns that warn away predators.
But without God or some other "designer", those patterns were never predetermined, as your thought experiment requires.
#29, there is a significant difference between the "target" you describe and the "target" of the original experiment.
The former may result in any of a near-infinite range of possible lifeforms that might thrive in an underwater habitat at 30 degrees Celsius with very little sunlight and relatively high salinity. Or not.
The latter will result in the single choice that most closely resembles the Mona Lisa. Every time without fail and without variation.
That would make for a fiendishly great lossy compression algorithm for images! 50 transparent polygons can be described in a few hundred bytes! It can probably be rendered by a flash program very quickly. Imagine multi-minute web video described in a couple of kilobytes.
Unusual @37 - insects being selected for resemblance to the plants they're standing on strikes me as a situation very similar to this Mona Lisa situation. I have to agree with the folks calling this evolution.
In reality, there is no "target". There is no "fit". There is only "alive", amongst an infinitude of stuff; predators, food and shelter (all of which may be one and the same thing, depending on your scope). All the things are getting on with living. Evolution is a consequence, a side-effect, nothing more.
Again, there is no "point". There is complex interactions that have results. No point. No intent.
Survival is not evolution. Obeying the built-in drives of your genes is not an awareness of evolution.
You see, that suggests that there is a discrete environment, separate from the things which live in it. And somehow, there is a need to place things in it, which will fit in or evolve to survive. That's just not it, although there are very limited circumstances that your example might hold true, like a sudden upheaval that markedly changes the environment at once, eg the Chixulub event.
All the things on our planet, have grown and changed and evolved together. Each thing has changed minutely over time, in a feedback loop containing itself and all the other information around it. There is no separatism, there is no goal or target, there is only change-or-stay-the-same, which is a result of other things changing-or-staying-the-same.
Frankly, that's the issue. You are not acknowledging that the use of the word 'design' is inconsistent with what you are describing. I understand the metaphorical similarity you are making between 'design' and constant-reiniterations-fed-by-the-interaction-of-infinite-free-agents. but it isn't the same thing. Besides a 'designer', design has a target and an endpoint at which it is 'finished'. Evolution has no endpoint, nor intent. It will never be finished
...insects being selected for resemblance to the plants they're standing on strikes me as a situation very similar to this Mona Lisa situation.
Actually, it's not. The insects you are referring to survive because of a reasonable resemblance to their surroundings, but it was not a foregone conclusion that this would happen.
It was just one of very, very many possible outcomes that allow those insects to survive up to this point. And, as luck would have it for the insects, it was NOT one of the even larger set of possible outcomes that would have seen them become extinct.
In the Mona Lisa case, it IS a foregone conclusion, on the part of the Designer, that one of the iterations would ultimately achieve what the Designer considers a match with the Mona Lisa.
The Mona Lisa case requires a Designer. Therefore it is really not evolution but rather something closer to "Intelligent Design".
To be a little clearer:
" I understand the metaphorical similarity you are making between 'design' and constant-reiniterations-fed-by-the-interaction-of-infinite-free-agents-leading-to-plants-and-animals-that-are-perfectly-tuned-to-their-current-environment, but it isn't the same thing."
#36 The Unusual Suspect:
That's not correct. Did you read my post above yours? There was not one single solution. There are thousands, if not millions of ways that polygons could be arranged to form the Mona Lisa, and an infinite number that do not.
There was no pre-determined final solution. The author did not know what the end result would be, and it would be very hard for any of us to recreate it without hours upon hours of trial and error. This iteration converged on one solution -- the next would converge on a different one, I guarantee you.
You are confusing what it looks like with that it is.
Likewise, it IS a foregone conclusion that any species will, if it survives, achieve a match with its environment. This is what evolution is. Naturally there are an infinite number of more variables in the real world that this simple play world, but you can still make the connection.Take any one variable, for instance, "in a volcanic environment, it is very hot."
Now, it is a foregone conclusion that any species that does not die out will ultimately be "matched" to live it a hot environment. Absolutely foregone. How they do it is besides the point -- it could be done in any number of ways, just like these polygons could have found any number ways to match to the Mona Lisa.
The heat is one aspect of the environment that the amoebae have to adapt to, and if the population survives it will adapt to it. The Mona Lisa is one aspect of the environment that the polygons have to adapt to, and if the population survives it will adapt to it. It just so happens that in the simple world this is the only aspect (and that this world is probably so simple that extinction is not an option), but this doesn't make it any less valuable.
#43 SamSam:
There was not one single solution. There are thousands, if not millions of ways that polygons could be arranged to form the Mona Lisa, and an infinite number that do not.
Unless I misread the article, at each iteration the author selected the arrangement of polygons that most closely resembled the Mona Lisa, and and used that arrangement to over-write the previous iteration. The equivalent to this in nature would be (for example) someone's god selecting Cro-Magnon Man over Neanderthals because they most closely resembled Modern Man, and exterminating the Neanderthals.
That requires a specific end goal and a number of direct interventions calculated to achieve it. It requires a Designer to set the goal, to work towards it and to end the process when the goal is achieved. That would be Intelligent Design, not evolution.
Likewise, it IS a foregone conclusion that any species will, if it survives, achieve a match with its environment.
I don't see, in evolutionary terms, a distinction between surviving and "matching with one's environment". You are essentially saying that any species which survives will survive. That's a rhetorical tautology, and quite possibly a logical one too.
The Unusual Suspect:
No. The Cro-Magnon example would be the equivalent if the author had already worked out what the solution was (50 semi-transparent polygons arranged in a certain way), and, at each iteration selected the one that was closest to his pre-defined solution.
You're still confusing the goal with the solution. The goal of the Mona Lisa example is to evolve something that looks like the Mona Lisa. The "goal" of the amoebae in the volcano example is to evolve something that survives in hot environments.
(Neither of them are strictly "goals," they are just a system of laws which will generally lead to an end, if the population doesn't go extinct).
In both cases there are an undefined number of solutions to that goal, none of which could have been predicted from the beginning.
You are confusing the fact that the final solution looks like the Mona Lisa with the idea that the final solution "is" the Mona Lisa (which is why you believe that the final solution has been pre-defined). However, this example is the same as evolving a circuit who's output was to control an arm that played the Ninth Symphony. The "solution," whether it's a set of polygons, a circuit or a hard cell wall, is distinct from the "goal," whether it's looking like the Mona Lisa, sounding like the Ninth Symphony, or surviving in a hot environment.
In the same way, the amoebae have the "specific end goal" of surviving in a hot environment. Both populations are evolving to fill a niche, both of which have at least one aspect that must be addressed.There are no "interventions" in either case. In both cases, there is a selective pressure that makes it more likely that the better-adapted individuals will reproduce more. In the Mona Lisa case, that probability is simplistically made to be 100%, but it could have just as easily been 1%.
Yes, that's what I was saying -- you saying that it's a foregone conclusion that the final polygons look like the Mona Lisa is as tautological as my saying that any amoebae living in a volcano are able to survive heat.In any event, neither is really a "foregone conclusion" -- the amoebae may all die out, and the polygons may never completely look like the Mona Lisa (what if the author had decided to use only 10 polygons?).
You're still confusing the goal with the solution. The goal of the Mona Lisa example is to evolve something that looks like the Mona Lisa.
The author stated that his challenge was to see if he could "paint a replica of the Mona Lisa using only 50 semi transparent polygons", by using his "small program that keeps a string of DNA for polygon rendering".
His success is measured by the degree to which the resulting image resembles the original Mona Lisa (or a handy photograph thereof) when his program ceases to produce new iterations.
The process itself was designed to reduce the chances that the resulting image would bear no resemblance to Mona Lisa whatsoever. And if it did, the author would doubtless have added polygons or fine-tuned the pixel-comparison "fitness function" and re-run the experiment.
The "goal" of the amoebae in the volcano example is to evolve something that survives in hot environments.
Evolution doesn't concern the amoeba. Its "goal" is to survive long enough to reproduce. The amoeba's success is measured by whether or not it managed to do so. There are many ways for the amoeba to succeed and many ways for it to fail in this. The sum of all the success/failures for that type of amoeba comprises its evolution.
If all amoebas of its type fail, there is no fine-tuning and re-running of the process to give it a better chance next time.
I wonder if a further reason why some religious types just can't get evolution is because not only do they reject deep time, they also think time is finite and imagine an imminent judgment day that "all goals must work towards".
Takuan, that plus many can't bear the thought that all of humanity is just happenstance.
Me, I take comfort in that fact and resolve to enjoy myself for the little freak of nature that I am!
what is wrong with happenstance? Appreciating happenstance makes you value life more. Think that the odds are against there ever being another chance if we screw this one up, no sky-daddy to clean up our mess.
http://ca.youtube.com/watch?v=JWVshkVF0SY
I'll be impressed when it can generate polyhedrons instead of polygons, and work with two (or more) source-images - photos of the same object taken from different positions and angles, thus forcing subsequent generations to become more like the source-object in order to survive.