Wednesday, June 17, 2015

Evolutionary algorithms are really adaptation algorithms

A recent article in Nature reminded me of the importance of definitions. The article discusses evolution and evolutionary algorithms in a special issue on machine learning (Eiben and Smith, 2015). I think we all know that "evolutionary" algorithms are based on natural selection and we all know that there's more to evolution than just adaptation. It's too late to change the name of these procedures in computer science but at the very least I expect computer scientists to be aware of the difference between their procedures and real evolution.

In this paper, there's a section on "how evolutionary computation compares with natural evolution." The authors consistently use "evolution" as a synonym for "selection" or "adaptation" and they seem to be unaware of any other mechanism of evolution.

In one sense, it's okay to conflate "evolution" and "adaptation" in computer science but if that error reflects and perpetuates a fundamental misunderstanding of the nature of real biological evolution then perhaps it's time to rename these algorithms "adpatation algorithms."


Eiben, A.E. and Smith, J. (2015) From evolutionary computation to the evolution of things. Nature 521: 476–482. [doi:10.1038/nature14544]

9 comments:

  1. EAs or GAs have no problem with neutral change. I suspect it is the dominant mode of change.

    The programmers may desire hill climbing, but a decent program will chug along in neutral.

    ReplyDelete
  2. I think it is an error to impute goals or targets to a GA. The programmer may have goals, but the program simply replicates entities with variation and differential success. There would be little or no adaptation if neutral evolution were not allowed.

    ReplyDelete
  3. If you think about Lensky, you have decades of mostly neutral change, but the environment is such that a rather narrow collection of changes confers a dramatic advantage. The population is quickly swamped with the adaptation.

    It would be a poor GA that didn't follow this model.

    ReplyDelete
  4. The authors published a table showing "Main differences between natural evolution and evolutionary algorithms " What part of that table recognizes the importance of neutral alleles and fixation by random genetic drift?

    ReplyDelete
    Replies
    1. I can't read the paper, so I can't respond to that. GAs -- to the best of my knowledge -- do not yet spawn new species. Perhaps someone familiar with Avida could respond.

      GAs are not sophisticated enough to model chemistry (except in narrowly confined areas) and cannot model the complexity of the biological environment. They also cannot model the astronomical number of replications and near-astronomical population sizes.

      But without neutral mutations, they would be ineffective. Whether neutral alleles fix in something like Avida, I don't know, but I would make a small bet they can.

      Delete
    2. There is a fundamental difference between GAs and things like Avida, though. The point of a GA is to optimize some criterion and is using a version of selection to do it. They really aren't meant to be any more evolutionarily informative than the competing method of artificial neural networks is neurologically informative.

      On the other hand, Avida, Tierra, etc. although very simple at this point, really *are* trying to tell us something about how evolution works.

      Delete
  5. Any method of optimization has to allow multiple alleles in the population. Nothing really models biology. A suffiently powerful GA environment would allow some simulation of speciation to prevent getting stuck in a local optimum. You really need multiple parallel paths.

    ReplyDelete
  6. I think we all know that "evolutionary" algorithms are based on natural selection

    A friend of mine developed "evolutionary" algorithms for the US Department of Defense "Star Wars" program. The degree of selection versus "neutral mutations" permitted can be adjusted. Therefore I wouldn't consider the quote in italics above to be completely accurate.

    ReplyDelete