Evolutionary Algorithms

One of the bedrock claims of creationism is that mutation can never create new information, that random changes can only make complex systems worse and never improve them. Although there are many examples of information-increasing mutations in the natural world that prove this claim false, there’s an even more potent and understandable counterexample, one that I think defenders of evolution too often overlook. That counterexample comes in the form of evolutionary algorithms.

Altshuler and Linden used EAs to design this crooked-wire antenna. Despite its strange, asymmetric shape, it has a nearly perfect hemispherical radiation pattern. (source)

Evolutionary algorithms are a type of computer simulation that uses evolution as a design tool. In an EA, the problem to be solved is represented as a fitness function, a quantitative metric that measures how well a proposed solution meets the parameters of the problem. An EA begins with a population of candidate solutions, usually generated at random, and uses the fitness function to evaluate each of them. The best candidates are copied with random mutations, creating “offspring” that go on to the next generation, and the process repeats. Some EAs even simulate sex by allowing candidate solutions to swap parts of their code.

As simple as this sounds, evolutionary algorithms have proven their worth as a problem-solving strategy of dramatic creativity and power, often producing solutions that surpass the best efforts of human engineers. EAs are widely used in academia and industry to get a handle on problems that seem intractable by any other method.

EAs have two major advantages over human design techniques. One is their open-mindedness. Because EAs operate through randomness, mutating their candidate solutions without trying to predict in advance whether the changes will be beneficial, they are not limited by human preconceptions about how a problem should be approached. The only thing that “matters” to an EA is results, and as a consequence, they often come up with solutions that a human designer would never have thought of.

Computer simulations suggest this EA-designed expandable truss for an aircraft or satellite would damp out damaging vibrations much better than an ordinary design. (source)

The other advantage, more subtle, is called the Schema Theorem. Many important problems in industry and science exhibit combinatorial explosion – that is, they have so many different possible solutions that it would be impossible to individually test each one, even on a computer. This vast number of candidates can be grouped into what are called search spaces, collections of individuals that are similar in important ways. The idea behind an evolutionary algorithm is that, by evaluating an individual from a given search space, it’s learning something about all the individuals in that search space. As it repeats this process, it will gradually build up more and more accurate information about the average fitness values of these spaces, until it can home in on the one that’s most likely to contain the answer being sought. This sounds complicated, but fundamentally it’s the same thing that a scientific poll does. Pollsters ask questions of a certain member of an ethnic, religious or social group because they expect to learn something about the opinions of all members of that group, and therefore gain the ability to predict national opinion after sampling only a small fraction of the population.

But far more important than these theoretical concerns is the empirical evidence demonstrating the power of evolutionary algorithms, and the facts do not disappoint. EAs have been used throughout academia, industry and government to solve problems that seemed insoluble or to come up with answers that outclass their best human-designed competitors. They have been taught to play expert checkers, to design wings for supersonic aircraft, to predict stock market swings and currency exchange rate fluctuations, to schedule assembly lines and air traffic, to control automobile anti-lock braking systems, to optimize engines and turbines, and many more. Here are some other examples of evolutionary algorithms in the news over the past few months:

The next time an ignorant creationist insists that evolution can never produce anything complex, functional and useful, point him to the evidence of evolutionary algorithms. These algorithms permit us to view evolution at work in real time, and in human technology, as in organic life, it proves to be a problem-solving strategy of surpassing flexibility and power.

About Adam Lee

Adam Lee is an atheist writer and speaker living in New York City. His new novel, Broken Ring, is available in paperback and e-book. Read his full bio, or follow him on Twitter.

  • http://discussionator.com LeeJH

    I created 2 collections of difficult Sokoban puzzles by writing a computer program which starts with random candidates and mutates them, keeping the ones with longer solutions (which are assumed to be more difficult to solve). Gradually, the fitness of the puzzles increases, and you end up with puzzles which can take a human a few hours to solve.

    The puzzles are very different from the ones humans design themselves – the evolved ones are compact and convoluted, with no obvious structure and no sign of planning. The computer is blind, and lacks the constraints we face when following rules we make up to help us construct something.

    You an even download the program I used and watch your own complex puzzles pop into existence from nothing…

  • http://bridgingschisms.org Eshu

    Yes EA’s definitely work. I once wrote one to solve the sorting networks problem using co-evolution. As the networks evolve, so do the patterns they have to sort, so the two populations end up in a predator/prey “arms race”, which keeps things moving along and not stagnating. On large problems it did far better than I could do manually.

    It’s certainly an impressive demonstration of evolution, but I don’t expect creationists to be convinced by it – for a start it’s not a trivial thing to understand even if you’re making an effort.

  • mike

    Another plus for EAs is that they generally find solutions that are robust to small changes. Evolution will not favor solutions whose fitness is greatly harmed by most small mutations — these individuals are unlikely to produce very fit children. Just like in nature, it is very common for a population of computer programs to evolve lots of inaccessible parts of the code (“junk DNA”). In this way, the junk portions are more likely to absorb the inevitable mutations in a benign way.

  • Alex, FCD

    In fact, we even use evolutionary algorithms to study evolution. Phylogenetic trees* are usually constructed by producing a tree at random, assessing its ‘fitness’, and then making random changes to the tree (‘mutations’). The ‘fitness of the mutated is then compared to that of the parent tree. If it is greater, the mutated tree is used as the starting point for another round. Tree ‘fitness’ is calculated differently by different biologists, but as far as I know, all phylogenetic programs use this basic method.

    *Diagrams that show the evolutionary relationships between groups of organisms. This one shows how all the primates are related to one another.

  • Wayne Essel

    Computers do not do random. They do logic. Computers are programmed. They can have the appearance of randomness, but if you seed a random number generator with the same value on two different computers, you will get the same sequence of numbers/events. Computers also have to make a decision about what trait or characteristic to “randomly” change. Somehow, that has to be seeded and perhaps bound as well.

    So, while I would acknowledge the usefulness of these systems based upon empirical evidence, I would want to know more about just how “random” these systems are.

  • http://primesequence.blogspot.com/ PrimeNumber

    Computers can be fed a list of truly random numbers. Your could use ERNIE if you want or whatever, it doesn’t matter. Evolutionary Algorithms still work.

    Computer random number seeds are usually based from how long the computer has been running. That means each time you run the algorithm, a different seed will be chosen, at random.

  • MIchael

    http://random.org/

    True random number generator, based on atmospheric noise.

    Anyway, surely that doesn’t make a difference? As long as the random number generator had nothing to do with the GA, surely it is effectively random to the algorithms?

  • http://piepalace.ca/blog Erigami

    If I had to debate a creationist about evolution, I’d actually use genetic algorithms (the term my university used for EAs) as a counterexample against any kind of intelligent design.

    In a nutshell, an evolutionary algorithm is constrained by the designer. The designer picks the scope in which the algorithm is allowed to mutate, decides how traits are encoded, decides how mutation works, and decides how reproduction combines the genome. It’s really, really hard to do that well. Any wrong choice, and the EA is stuck in a tiny corner of the probability space, and is unable to improve itself.

    Of course, any ID proponent would just say that goes to prove how awesome the designer is.

  • Joffan

    It’s an interesting argument that could even be regarded as a meeting ground. After all, evolutionary algorthms in computers need a designer, as Erigami says. So evolution can be admitted as real without immediately precluding a designer. Only those hung up on categorically-disproved myths (YEC) need lose any sleep about evolution.

    Hey, I just like everyone to get along, all right?

  • Tom

    I’ve done some work myself with these; they really are quite powerful tools. They’re not, it should be stressed, as good as a truly analytical approach, when that’s actually possible; compared to other iterative numerical techniques, however, they’re excellent – relatively quick to converge, more resistant to local optima and better at dealing with very large search spaces, and also have the habit of occasionally coming up with something phenomenally good that a human imagination wouldn’t stand a chance of conceiving.

    Oh, you can also use them to show that, if machine parts actually could breed, you really could evolve a damn pocketwatch. Link

  • http://www.bellatorus.com Petrucio

    I’m currently writing an EA to compute an NP-Hard problem at work. Very cool stuff.

  • nfpendleton

    This post reminds me of this fascinating video I saw at the Internet Archive (archive.org) called “Evolved Virtual Creatures.” They ran simulations in a 3D space with “creatures” made of cubes, and gave them various problems to solve – locomotion, defense, etc. It’s truly amazing seeing how they problem solved and adapted their physical traits (as well as taking on more complexity) to meet their goals. I highly recommend watching this video and passing it along.

    I’m not sure how to post a hyperlink, so here’s the address: http://www.archive.org/details/sims_evolved_virtual_creatures_1994

  • 5acos(phi/2)

    When I first learned about the concept of EAs and their applications, I was dumbfounded. As an algorithm novice, I was working hard to come up with neat heuristics to solve various computational problems. The realization that some seemingly random, convoluted algorithm can beat human design really hurt my human pride.

    Ah, how mistaken I was… :)

  • prase

    “Evolved Virtual Creatures” – shouldn’t they call them “evolutures” instead? Evolved creature sounds like an oxymoron.

  • Brad

    @Essel: As long as computer RNGs spew out numbers that pass certain noise tests related to the function(s) they’re being used for, it doesn’t matter how truly, philosophically ‘random’ they are. As far as the holistic function is concerned, the numbers would be effectively random.

    @Petrucio: Hmm, I wonder what the math involving EAs and NP-hard problems is like. Perhaps EAs could serve as a basis for defining a new class of computational complexity?

  • exrelayman

    Ebon,

    Thanks for bringing this totally unknown material into my awareness. I am ever delighted with the scope of things you think about.

    So we have evolved to a place where we use evolution as a tool, while there are yet those who deny evolution. How quaint (yet tragic)!

  • Samuel Skinner

    “It’s an interesting argument that could even be regarded as a meeting ground. After all, evolutionary algorthms in computers need a designer, as Erigami says. So evolution can be admitted as real without immediately precluding a designer. Only those hung up on categorically-disproved myths (YEC) need lose any sleep about evolution.

    Hey, I just like everyone to get along, all right?”

    Don’t make me post the code of the sith!

    On topic, is there anyway to purge the junk dna that accumulates in the solutions?

  • Paul

    Brad,

    I don’t think what you’re pondering regarding EAs and NP-hard problems would be a meaningful distinction. I didn’t get a PhD in Computational Complexity or anything, but NP-hard does not mean you cannot come up with a relatively efficient algorithm to approximate an answer. And that is really all you could get with an EA. You can find what seems to be very good local maxima, but that is not the same as “solving” the problem — and being able to do so would still not necessarily tell you anything meaningful about Computational Complexity of the issue at hand.

  • Paul

    @Samuel Skinner

    Not sure what you mean by “junk DNA”. If you are referring to mike’s post where the Genetic Algorithm is developing a standalone computer program, it would seem possible to excise “junk DNA” (e.g. inaccessible/unexecuted code) by enforcing a selective pressure based on a minimum functionality you desire to be maintained as well as one on the overall code length. If your population size is large enough it’s possible that such selective pressures will tend to weed out excess code without killing off the entire population. It’s really just a matter of what selection pressures are exerted.

  • http://thewarfareismental.typepad.com cl

    The next time an ignorant creationist insists that evolution can never produce anything complex, functional and useful, point him to the evidence of evolutionary algorithms.

    By no means am I defending the “bedrock claims” of creationism you rebut, but in all fairness, what do you suggest we do the next time an ignorant atheist implies the conflation that EA’s are analogous to biological evolution and can successfully account for the geno / pheno- type distinction?

    Erigami’s comments were also relevant.

  • Paul

    cl,

    Perhaps you can explain how the geno/pheno-type distinction represents selection pressures that cannot be properly emulated by an Evolutionary Algorithm? Or how the fitness function used by an Evolutionary Algorithm fundamentally differs from that which would have driven biological evolution (aside from the fact that the algorithm designers generally have a specific goal in mind, whereas unthinking nature would not)?

  • http://www.whyihatejesus.blogspot.com/ OMGF

    From the “non-creationist” clown at another website:

    Using Avida to support biological evolution is about as scrupulous as using Haeckel’s embryos or those damned horse diagrams.

  • jack

    I’m another user of evolutionary algorithms, and I’m delighted to see them discussed in this context. I have just a few thoughts to add:

    It’s misleading to point to the results of EAs and say to our creationist friends, “See, randomness can produce complex and interesting things!” It’s not the randomness that does it. To suggest this is to buy into their flawed logic, rather like trying to answer the question, “Have you stopped beating your wife?”

    Evolution, natural or in computer simulation, is better described as stochastic, rather than random. It has randomness in it, and that randomness is essential, but it also has a highly nonrandom component: selection. Whenever a creationist asks me, “Do you really believe X could have arisen purely by chance?”, where X is some example of beauty, complexity, order and function in biology, I just answer, “No, of course not. That could never have arisen by chance. But that is not what Darwin’s theory of evolution says.” I then go on to explain the highly nonrandom effects of natural selection. Of course I seldom succeed in changing their minds, but that’s a separate issue.

    Getting back to our computer simulations of evolution, some comments alluded to the role of the programmer as designer, in choosing how to represent the problem, deciding what attributes should be mutable, deciding how large a perturbation should be made with each mutation, etc. This is all true. These are thorny problems for anyone who sets out to solve a really hard, complex problem using EAs. But this in no way casts doubt on the reality of biological evolution, nor does it imply that, for biological evolution to work as well as it does, it must have been set up by an intelligent designer. Some of these thorny problems can be solved by evolution itself. A good example is the adjustment of the size of the perturbation used in mutation by indirect selection pressure, what practitioners call self-adaptive mutation rates. The correlation of mutations across multiple dimensions can also be handled in this way. The details are a bit too arcane for this comment, but can be found in books like this one.

    Biological evolution works as well as it does in part because the details of the representation — for example the mapping of the triplet codons onto amino acids in such a way that small errors in the genetic code tend to lead to small changes in the chemical nature of the amino acids — are themselves the result of a long process of evolution that preceded the emergence of one dominant solution, the one that was the progenitor of all extant life. Similarly, mutation rates differ greatly in different organisms, being higher in simpler organisms with small genomes, HIV being near one extreme. In more complex organisms, these mutation rates are controlled by DNA repair enzymes, and the error rates are almost certainly fine-tuned by indirect selection pressure.

  • http://thewarfareismental.typepad.com cl

    jack,

    It’s misleading to point to the results of EAs and say to our creationist friends, “See, randomness can produce complex and interesting things!” It’s not the randomness that does it. To suggest this is to buy into their flawed logic…

    Exactly, jack, exactly. I think you hit the nail on the head here. Interestingly, since he mentioned me, when I tried to even begin to suggest this to our friend OMGF, it all went over his head, and instead of discuss it intelligently, he just preferred to accuse me of “believing the lies of the creationists” even though I pre-stated I was not an evolution denier, then disingenuously chop a single sentence out a substantial discussion to accompany an immature ad hominem remark. Here’s a little more context surrounding the sentence of mine that he farmed out of the other thread, which suggests a different story:

    You seem to have misunderstood the relevance of Haeckel’s embryos, as whether or not they were faked doesn’t affect my point at all. Further, Claim CC216.2 directly supports my point, so I’m left to wonder why you’d reference that, and to wonder if maybe you’re making knee-jerk responses here. These are even further supported by the fact that even after I explicitly told you I am not an evolution denier, you merely handwaved my claims and proceeded to gas on about how I’ve accepted the lies of the anti-evolution movement. I believe in LUCA for cryin’ out loud, don’t you read?!?!? And why on Earth would you assume I’ve never spent any time scouring the TalkOrigins archive and attempt to handwave me to an authority I’m quite familiar with? Your strategy here lends well to the idea that you can’t formulate your own intelligent responses to my points, and that you’d wave me to a reference that supports one of them lends well to the idea that you haven’t even understood them. (cl to OMGF)

    This is sad, because we see how an irrational reaction obscures knowledge, meaning that instead of thinking and considering whether my points had validity, OMGF simply flanks me. Maybe he’ll accept your well-reasoned criticisms? To accept my statements in the thread OMGF conveniently failed to cite or jack’s statements here does not in any way entail that one is questioning or denying evolution, or attempting to make some lame, backhanded argument for creationism. As you said,

    ..this in no way casts doubt on the reality of biological evolution, nor does it imply that, for biological evolution to work as well as it does, it must have been set up by an intelligent designer.

    The only reason I made my remark at all was to provide a more well-rounded treatment of the subject than was presented in the original posts. Sure, Ebon covered many of the positives of EA’s just fine, but leaves important anomalous evidence out, or interpretations that challenge his point-of-view. People might like to know a little more about the subject.

    Paul,

    If you still have any questions jack didn’t answer, let me know.

  • Paul

    Sorry for the delay in answering, I had a family issue and have been away from the internet for a few days.

    In my opinion, jack did not sufficiently explain why evolutionary algorithms cannot be said to be analogous to biological evolution (which was the claim I was speaking to in my response to you). But on reading his post it does not seem that that was his point, anyway. His argument is suitable against the creationist strawman of “can x/y/z be created by random processes”, when they are trying to cast doubt on biological evolution. But that does not speak to my response to you.

    Both biological evolution and evolutionary algorithms in general both operate in an analogous fashion. Both incorporate random mutation and decidedly non-random selection. It would be silly to say that evolutionary algorithms prove biological evolution, but I do not think it is any less silly to say they are not analogues. And I have not seen any convincing arguments otherwise in this thread. And I say that wholly agreeing with jack’s points. At most, his post states that biological evolution is a much more intricate model — but that was not what I was protesting.