Coevolutionary Algorithms

Coevolutionary algorithms approach problems for which no function for evaluating potential solutions is present or known. Instead, algorithms rely on the aggregation of outcomes from interactions among evolving entities in order to make selection decisions. Given the lack of an explicit yardstick, understanding the dynamics of coevolutionary algorithms, judging whether a given algorithm is progressing, and designing effective new algorithms present unique challenges unlike those faced by optimization or evolutionary algorithms. The purpose of this chapter is to provide a foundational understanding of coevolutionary algorithms and to highlight critical theoretical and empirical work done over the last two decades. This chapter outlines the ends and means of coevolutionary algorithms: what they are meant to find, and how they should find it.

Handbook of Natural Computing
Volume 2
p. 987
Chapter 31
Coevolutionary Principles

The inspiration for coevolutionary algorithms (CoEAs) is the same as for traditional evolutionay algorithms (EAs): attempt to harness the Darwinian notions of heredity and survival of the fittest for simulation or problem-solving purposes. To put it simply, a representation is chosen to encode some aspects of potential solutions to a problem into individuals, those individuals are altered during search using genetic-like variation operators such as mutation and crossover, and search is directed by selecting better individuals as determined by a fitness evaluation. With any luck, the iteration of these steps will eventually lead to high-quality solutions to a problem, if problem solving is the aim, or to interesting or realistic system behavior.

Variation on a theme. Search. Problem solving. Solutions. Design. Directed Search.

Why are the authors of this chapter mistaken?

70 thoughts on “Coevolutionary Algorithms

  1. How could one possibly build an effective algorithm when anytime one believes A is better than B it is possible that later one will believe B is better than A?

    Not a problem! Natural selection to the rescue.

  2. Mung: Evolution is search.

    What an amazing display of confirmation bias! Gusz Eiben and Jim Smith have told you that the coevolutionary process isn’t necessarily used to solve a problem. It’s right there in the passage you’ve quoted. I’m literally shaking my head, Mung.

    In “Evo-Info Sidebar: Conservation of Performance in Search,” I explained that some search algorithms use simulated evolutionary processes to sample the space of possible solutions to a problem. The sample is used by another component of the search, logically distinct from the evolutionary sampling process, to generate a solution to the problem. In “Evolution Is Not Search,” I used pictures to show that, even when a simulator is tuned to maximize its utility as a component of a search algorithm, the resulting evolutionary process does not search, but instead settles into statistical equilibrium.

    I have in fact been writing with you in mind as my primary reader. What you’re doing here is very discouraging. It’s as though nothing I’ve tried to convey has registered with you.

  3. Tom English,

    You make it seem as if its difficult to grasp that a computer just does what you tell it to do. If you tell it to choose the reddest, it chooses the reddest. If you tell it to chose the shape which has the least wind resistance, then that is what it chooses.

    This is all evolutionary algorithms do, but you then want to speak in such convoluted, and irrelevant language, that its as if you want to obscure this simple fundamental reality. That is why it is so easy for Mung or I to counter every time Joe claims some program has no search function. Because without a search function it does nothing interesting or of consequence.

  4. Mung: Not a problem! Natural selection to the rescue.

    You’re deflecting by spouting “clever” stuff that reveals your ignorance of the subject matter. It is in fact not natural selection to the rescue. As Wolpert and Macready pointed out, the coevolutionary free lunch that they identified corresponds to nothing in biological evolution.

    Why did you not tell us that you were quoting Popovici et al. (2012), “Coevolutionary Principles“?

  5. phoodoo: You make it seem as if its difficult to grasp that a computer just does what you tell it to do.

    What a splendid ass you are at this particular moment, having seen computer-generated forecasts of Hurricane Irma for the past week, and having seen the storm hit the Keys and Southern Florida this morning, pretty much as predicted.

  6. Tom English: You’re deflecting by spouting “clever” stuff that reveals your ignorance of the subject matter. It is in fact not natural selection to the rescue. As Wolpert and Macready pointed out, the coevolutionary free lunch that they identified corresponds to nothing in biological evolution.

    Why did you not tell us that you were quoting Popovici et al. (2012), “Coevolutionary Principles“?

    Does it explain random genetic drift?

  7. Tom English: What a splendid ass you are at this particular moment, having seen computer-generated forecasts of Hurricane Irma for the past week, and having seen the storm hit the Keys and Southern Florida this morning, pretty much as predicted.

    It was 100% accurate…especially initially…

  8. Tom English,

    What a splendid ass you are, you actually believe that a program developer didn’t tell the computer what parameters to select. You must believe there is a program that was written to say, “Computer, tell us what the weather will be!”

  9. phoodoo:
    Tom English,

    What a splendid ass you are, you actually believe that a program developer didn’t tell the computer what parameters to select.You must believe there is a program that was written to say, “Computer, tell us what the weather will be!”

    I think you’re absolutely correct. Each person who ran a model, had obviously decided in advance where the storm would go, and adjusted the parameters to make it so. Clearly, these so-called “computer models” are just eyewash, obfuscating the fact that all these various possible tracks are simply a priori guesses made by programmers. Some of whom guessed better than others. This his how ALL computer models work.

  10. Flint,

    Phoodoo’s computer illiteracy is embarrassing. Sometimes I wonder if he would benefit from taking a programming class.

    Then I think “Nah, probably not.”

  11. keiths:
    Flint,

    Phoodoo’s computer illiteracy is embarrassing.Sometimes I wonder if he would benefit from taking a programming class.

    Then I think “Nah, probably not.”

    I agree, but probably not for the same reasons as yours. Computer models (which generally describe systems too complex for straightforward calculation) tend to be also fiendishly complex, and very large (that is, lots and lots and lots of code, written by many people). These models are most useful when there’s a large number of independent variables, few if any of which are particularly specific. They tend to be rather hazy, have wide latitudes, and interact with one another in unpredictable ways.

    Conversely, most programming classes introduce the student to simple logical sequences (beyond PRINT “HELLO WORLD”). You have to be fairly advanced to reach the point where the outputs of the system you were on the team developing, aren’t clearly correct or incorrect. Where an unexpected result MIGHT indicate the system being modeled itself has surprises, or it MIGHT be the result of some obscure bug in the code. Such bugs are unavoidable, and give rise to the aphorism that computers are dumber than people, but smarter than programmers!

  12. Flint,

    For crying out loud, you are telling me I need to understand computer programming, and then you are saying that I claim the programmers are the ones doing the guessing? That’s completely inaccurate. The programmers tell the computer what to search for, and the program does the searching and makes the outcome.

    Are you another one of these Lucky Accidenters who can’t separate the goal of the search from the result of the search? I understand keiths wouldn’t get it…

  13. Mung: Not a problem! Natural selection to the rescue.

    Yes. Finally you’re catching on. Natural selection is why evolution is much better than blindly rolling dice.

  14. Tom, to Mung:

    I have in fact been writing with you in mind as my primary reader. What you’re doing here is very discouraging. It’s as though nothing I’ve tried to convey has registered with you.

    Tom,

    You’ve been overestimating Mung for a very long time, in terms both of character and of intellect.

    The rest of us didn’t reach our low opinions of him on a whim. We’ve already seen what you are only now discovering.

  15. phoodoo, to Flint:

    For crying out loud, you are telling me I need to understand computer programming, and then you are saying that I claim the programmers are the ones doing the guessing? That’s completely inaccurate. The programmers tell the computer what to search for, and the program does the searching and makes the outcome.

    phoodoo,

    You literally do not know what you are talking about. Tom and Flint’s comments were about weather models, not searches:

    Tom, to phoodoo:

    What a splendid ass you are at this particular moment, having seen computer-generated forecasts of Hurricane Irma for the past week, and having seen the storm hit the Keys and Southern Florida this morning, pretty much as predicted.

    Flint, to phoodoo:

    I think you’re absolutely correct. Each person who ran a model, had obviously decided in advance where the storm would go, and adjusted the parameters to make it so. Clearly, these so-called “computer models” are just eyewash, obfuscating the fact that all these various possible tracks are simply a priori guesses made by programmers. Some of whom guessed better than others. This his how ALL computer models work.

    You have no idea how weather models are implemented, do you, phoodoo?

    So yes, you need to understand computer programming — that is, if you don’t want to make a fool of yourself when talking about computer programming.

    On the other hand, if you’re happy to look stupid, then proceed as usual.

  16. Tom English: I have in fact been writing with you in mind as my primary reader. What you’re doing here is very discouraging. It’s as though nothing I’ve tried to convey has registered with you.

    Perhaps you’re aware of all the crap that I’ve taken for pointing out what people actually involved in evolutionary computing say about it. If you’re not one of those people who have been giving me crap about it you’ve nothing to worry about.

    People who claim that genetic algorithms aren’t random search algorithms. People who claim that they have no targets and aren’t directed search. These people are ignorant. I’m educating them.

    And I have more coming, because I can hardly pick up a single book on evolutionary algorithms that doesn’t make these same points.

  17. keiths: Tom and Flint’s comments were about weather models, not searches

    Oh really? Gee I thought they were about evolutionary algorithms

    phoodoo: This is all evolutionary algorithms do,

    .

    Doofus.

  18. Allan Miller: The plaintive cry of evolutionary search …

    William Dembski, “Conservation of Information Made Simple“:

    Search is a very general phenomenon. The reason we don’t typically think of search in broad terms applicable to nature generally is that we tend to think of it narrowly in terms of finding a particular predefined object. Thus our stock example of search is losing one’s keys, with search then being the attempt to recover them. But we can also search for things that are not pre-given in this way. Sixteenth-century explorers were looking for new, uncharted lands. They knew when they found them that their search had been successful, but they didn’t know exactly what they were looking for. U2 has a song titled “I Still Haven’t Found What I’m Looking For.” How will Bono know once he’s found what he’s looking for? Often we know that we’ve found it even though it’s nothing like what we expected, and sometimes even violates our expectations.

    By the way, I have shown (by animation and other means) that if “what I’m looking for” is defined after the fact, as Dembski suggests, then the so-called information is not conserved. See “The Law of Conservation of Information Is Defunct.”

  19. Tom English: They knew when they found them that their search had been successful, but they didn’t know exactly what they were looking for.

    *chuckles* Reminds me of Blaise Pascal (as reported by M. Belloiseau in Pagnol’s Manon des Sources)

    Tu ne me chercherais pas, si tu ne m’avais pas déjà trouvé !

  20. Evolution (the thing that happens in the wild) is too open-ended to be usefully termed a ‘search’. It’s more a rummage. Or a pursuit. An examination, perhaps. Or rather, an exploration – a hunt, if you will. An inquiry, inspection, investigation, quest, research, chase, going-over, inquest, pursual, wild goose chase. But not a search.

  21. I’m sticking with rummage. Or probe. I expect the fields of evolutionary computing and evolutionary biology to follow me on this, once I’ve made my mind up.

  22. Tom English: Why did you not tell us that you were quoting Popovici et al. (2012), “Coevolutionary Principles“?

    Because I’m quoting from a book, exactly as indicated in the OP. Want me to post a picture?

  23. No discussion of alien abductions would be complete without quoting this gem from WJM:

    I haven’t been personally abducted as far as I know/remember. I have physically encountered one of those “greys” in my house. My wife had multiple experiences with all the characteristics of abduction, as did her son. At one point she was in the early stages of pregnancy when the fetus disappeared overnight from her womb after she had a nightmare about little creatures with clown faces coming out of a closet and taking her away. There’s also considerable more personal evidence, but that’s the main stuff.

    So yeah, I’m pretty sure abductions occur, even though I’ve never actually seen or experienced it firsthand that I’m aware of.

  24. Mung: Because I’m quoting from a book, exactly as indicated in the OP. Want me to post a picture?

    I misread the title at first, and thought you were quoting again from from Eiben and Smith, Introduction to Evolutionary Computing.

    You should have cited the chapter, and not just the book. Furthermore, if informed discussion is what you really want, then you should link to the material online, when possible.

  25. GlenDavidson: But were aliens designed to abduct humans?

    Please stick to the topic. Are alien abductors and human abductees adapted to their roles by coevolution, or are they codesigned to serve a purpose grander than any of them can conceive?

  26. Tom English: You should have cited the chapter, and not just the book. Furthermore, if informed discussion is what you really want, then you should link to the material online, when possible.

    I cited the volume (it’s a 4-volume work), chapter, and page. And I wasn’t aware it was available online. 🙂

    It’s all right there in the OP:

    Handbook of Natural Computing
    Volume 2
    p. 987
    Chapter 31
    Coevolutionary Principles

  27. I’m wondering…what would panspermia believers (panspermia is often used as a backup plan by many atherists when faced with the fact of no evidence for the origins of life) look like in comparison to human abductees?

  28. J-Mac:
    I’m wondering…what would panspermia believers (panspermia is often used as a backup plan by many atherists when faced with the fact of no evidence for the origins of life) look like in comparison to human abductees?

    I’m trying to make sense of that — but without success.

Leave a Reply