Some thoughts on evolutionary algorithms and design
by machtIn this post I would like to explore some of the implications of evolutionary algorithms (EA's) and what they can (and can't) tell us about design. While I think what I say is relevant to all EA's, I am going to focus specifically on the Avida software program. I'm doing this for a number of reasons - the software and documentation are available online, Avida is often used in debates about design and evolution, and Robert Pennock made some claims about Avida during the Dover trial that I want to explore.
Before I get to EA's, though, I want to clear up one misunderstanding that many people have about design. The term "design" can refer to multiple ideas and this ambiguity is often the cause of a lot of confusion. Michael Behe, I think, is guilty of confusing two different uses of the term design. On p. 193 of his book Darwin's Black Box, Behe defines design as "the purposeful arrangement of parts." I think this definition gets at what many people think of when they think of design. If an engineer designs a circuit, he puts a resistor here and a capacitor there and a transistor there. But a little earlier on the page, Behe, I think, conflates this sense of design with another sense of the word. Behe claims,
"[Biochemical systems] were designed not by the laws of nature, not by chance and necessity; rather, they were planned. The designer knew what the systems would look like when they were completed, then took steps to bring the systems about."
Now, I want to suggest that "knew what the systems would look like when they were completed" can mean one of two things. These two things both often go under the term "design" even though they are separate ideas. The first is related to the definition Behe gave above "purposeful arrangement of parts." If "design" is thought of as something like this, it suggests a physical layout - what a circuit actually looks like, where the rooms/walls/lights/etc. are physically located in a house.
But "design" can refer to something different than this, too. This use of the term is closer to what one means when one talks about the "purpose," but very often it is related quite closely to the requirements. If I needed to design a circuit that needs to keep the voltage at 10V +/- 0.5V, the physical circuit may take many different forms. The the purpose/requirements would be the same - to regulate the voltage. Another name for this might be the "function."
I think most of Behe's book focuses on the "physical arrangement" part of his definition and not on the "purpose" part of his definition. He doesn't, in fact, seem to acknowledge the difference between these two uses of the term "design." This is understandable, I think, because ultimately all purposes, if they are to come to fruition, must have some physical arrangement. The problem comes in when we start to think that these two senses of "design" are tied to each other. This is the problem for Behe, I believe, in that giving an explanation of how the "arrangement of parts" came to be does not mean that we then have an explanation for the "purpose," if indeed there is one. This is because multiple arrangements of parts could serve the same purpose.
With this in mind, let's look at evolutionary algorithms. I'm using the phrase "evolutionary algorithm" as a general term for genetic algorithms, evolutionary programming, etc. - basically any algorithm that is based on the evolutionary biology. Here is a very general piece of pseudocode for how an evolutionary algorithm works:
1) Choose an initial population
2) Determine the fitness of the each member of the population
3) Select members of the population, kill the rest
4) Breed a new generation
5) Repeat steps 2-4 until threshold is met
Again, this is very general. Step 4, for example, can include replication, mutations, insertions, deletions, crossover and more. A program like Avida may also change the rate at which new generations breed. ("Breed" shouldn't be taken too literally. If there is no crossover, this would be similar to asexual reproduction.) The "threshold" may be a when a certain fitness is met or when a certain percentage of the population attains a certain fitness or any number of other things. Step 3 may be just a straight selection of the most fit members of the population or it may assign each member a probability of survival based on its fitness (therefore occasionally allowing less fit members of the population to survive).
Generally randomness is found in Step 4, but as I mention above, there may be some randomness in Step 3, too.
EA's can produce very complex solutions to problems. For example, look at the antenna designs near the bottom of this page. They were made using a genetic algorithm and they look nothing like an antenna that a human engineer would design. A claim that I've often heard is that the GA designed these antennas, not the humans. But this claim rests on the misunderstanding I wrote about at the beginning of this post. The antennas function in the way the engineers want them to - they fulfill the purpose, the requirements. In this sense, they are designed and they were designed by the engineers. However, the engineers didn't produce the "arrangement of parts." This came about because of the GA - a gradual process involving a combination of randomness and selection for fitness. It is clear, then, that just because something came about through a process of randomness and selection, doesn't mean that it isn't designed.
Well, this post is getting longer than I expected so I'm going to split it into two. The next post will look at Avida specifically, some of the claims made about it by both ID critics and ID supporters, and some more of the implications that EA's have for design in general.
January 10th, 2007 at 12:00 am
Thanks, Macht, for a good post. I wish I had time to write a whole essay on this point, but will have to confine myself to a couple of bullet point thoughts tonight:
1. It seems that the "evolvable systems group" is carrying out design work with a computerized tool that facilitates the rapid review and decision making that would be inherent in a trial and error process. Very interesting use of technology and one that will no doubt become more commonplace. Does using such a design tool mean that the system was "evolved" or is that a stretch of terminology? Is it the sheer number of trials that the computer allows that makes it an "evolved" system, as opposed the relatively few number of trials that I could accomplish through conventional means?
2. The engineers had a clearly defined goal in place at the beginning of the process, with each of the types of design they were focused on, whether the Yagi-Uda, the Mars Odyssey or the ST5 antenna. Can such a goal-oriented process fit within the evolutionary paradigm?
3. What relationship do such "evolvable systems" have to biological systems? Specifically, if the traditional evolutionary paradigm is geared toward survivability fitness (speaking stochastically, of course), does such a paradigm really mesh with all functional results? In other words, it is a nontrivial question whether generating new complex feature really leads to greater survivability. For example, are porpoises more "fit" than bacteria in terms of longevity and survival of the fittest? If not, then why would evolution go to all the trouble of the engineering work needed to construct the porpoise, unless there was some "goal" or "programming" to drive the process to that goal? This is not trite "“ it is a basic threshold question evolution must grapple with.
4. When attempts are made to apply evolutionary algorithms to biology, what risks do we run that we are incorporating as premises in our algorithm the very issues in question? Namely: ease of generating new biological system, likelihood of the new system being useful to the organism (again, it must be useful in the survivability sense), likelihood of the new system being incorporated into the next generation, likelihood of the new system being a direct way station on the path to the next useful system, absence of interfering reactions, likelihood of the new system being of the type that can be incorporated into the population as a whole, etc.
Comment by Eric Anderson — January 10, 2007 @ 12:00 am
January 10th, 2007 at 12:19 am
4. When attempts are made to apply evolutionary algorithms to biology, what risks do we run that we are incorporating as premises in our algorithm the very issues in question? Namely: ease of generating new biological system, likelihood of the new system being useful to the organism (again, it must be useful in the survivability sense), likelihood of the new system being incorporated into the next generation, likelihood of the new system being a direct way station on the path to the next useful system, absence of interfering reactions, likelihood of the new system being of the type that can be incorporated into the population as a whole, etc.
You've nailed the problem. There is too much wiggle room for subjective input. We are also captive to the times we live in. Who would designate an identical set of assumptions today as might have existed 20, 15, 10 or even 5 years ago? EAs are linked to both available knowledge and interpretation of it.
Comment by Bradford — January 10, 2007 @ 12:19 am
January 10th, 2007 at 4:12 am
macht wrote:
Hi macht,
Defining the word 'design' as broadly as you suggest leads to some patent absurdities.
For example, watch me 'design' a jetliner:
Requirements:
1. Must carry 700+ passengers.
2. Must use commercially-available turbofan engines.
3. Must travel transcontinental distances without refueling.
4. Must travel at an average speed of several hundred miles per hour.
5. Must meet prevailing safety and fuel economy standards.
6. Must interoperate with existing airport gates and fit on existing taxiways and runways.
Voila! I just 'designed' a successor to the 747, according to your definition of 'design', because I supplied the requirements that it must meet.
I don't think Boeing will be offering me a job on the strength of that 'design', do you?
And even if we were to grant your contention that the word design should encompass both a) purpose/requirements and b) the arrangement of parts, it wouldn't change the fact that these are distinct concepts. Producing (b), when the engineers have input only (a), is the real achievement of evolutionary algorithms.
Comment by keiths — January 10, 2007 @ 4:12 am
January 10th, 2007 at 5:15 am
Eric Anderson asks:
No. An evolutionary algorithm is an evolutionary algorithm, regardless of the speed at which it executes. I would say the essence of an evolutionary algorithm is that the generation of "mutations" is blind — that is, not informed by the selection criteria. Human design and evolutionary algorithms share the characteristic of employing multiple iterations, as you point out, but in the case of human design, the "mutations" that are generated are not blind at all, but are the ones that the designer thinks will get him closer to his design goals (i.e. the selection criteria).
Yes. In both cases, the ultimate "goal" of the replicators is to survive and replicate successfully. In the case of a variant antenna design inside an EA, survival and replication depend on bandwidth, gain, radiation pattern, and impedance. In the case of a biological replicator such as an animal, survival and replication will depend on other factors, such as speed, camouflage, and sensory acuity. In both cases the mutations are blind with respect to their consequences for survival and replication. Both fit into the evolutionary paradigm.
No, porpoises are no more "fit" than bacteria in an evolutionary sense.
Evolution, being a mindless process, has no concept of "trouble", "programming", "purpose", or "goal". It was never striving toward porpoises or away from them. Changes simply happened over time; the ones that tended to facilitate survival and reproduction were retained; and we now find ourselves in a world containing bacteria and porpoises, both of whom remain (for now) successful at survival and reproduction.
Regarding your final question, I would say that programs like Avida are not attempts at modeling biological evolution per se. Rather, they are models of abstract Darwinian processes, and as such can yield useful information, when applied with care, about real Darwinian processes like biological evolution.
Comment by keiths — January 10, 2007 @ 5:15 am
January 10th, 2007 at 7:39 am
No.
Comment by macht — January 10, 2007 @ 7:39 am
January 10th, 2007 at 8:23 am
keiths:
What Machts means by "design" in this case is really a "functional specification" in my world.
Comment by kornbelt888 — January 10, 2007 @ 8:23 am
January 10th, 2007 at 10:48 am
I think that the two senses are actually pretty closely related. If, say, I were to play a game of 52 Card Pickup, nobody would call the physical arrangement of cards on the floor the "design" of the cards, precisely because the physical arrangement wasn't intended by me, and doesn't serve any purpose of mine. So "design" is only applied to physical arrangements that appear, at least in part, to be the result of intent or purpose.
It's not the only word that we use as both an adjective and a verb in this way. For instance, we often refer to the "cut" of a diamond (an adjective describing its physical characteristics), but this refers to the fact that the diamond was cut that way (a verb describing the action of the jeweler), and it's improper to refer to the "cut" of a diamond that wasn't actually cut.
Comment by Deuce — January 10, 2007 @ 10:48 am
January 10th, 2007 at 11:58 am
Macht says:
What you say here reminds me of an interview where Sean Booth from the electronic group Autechre discuss the creative methods behind one of their recent albums. Notice his reaction to the interviewer towards the middle… http://www.sas.upenn.edu/~reyn...
Comment by Mertens — January 10, 2007 @ 11:58 am
January 10th, 2007 at 1:32 pm
"With this in mind, let's look at evolutionary algorithms. I'm using the phrase "evolutionary algorithm" as a general term for genetic algorithms, evolutionary programming, etc. - basically any algorithm that is based on the evolutionary biology.""”macht
To me this is the most interesting implication: based on evolutionary biology.
A designer's knowledge of natural processes determines (but not completely) the effectiveness of his control over those process for his own purposes.
Scientists and engineers (by most people's estimation, I presume) are "intelligent designers," and they warrant the designation by controlling natural processes for their own purposes"”including the process of biological evolution.
I would think that the statement of the obvious would have some negative implications for people who habitually refer to evolution as "blind" and "mindless," as if I knew it, or we all accepted it, as a matter of fact.
My experience over the years, Macht, has been that the discussions generally bog down in distinctions between "design" and "evolution."
For six years I've been begging (literally!) people to tell me what the difference is between "design" and "evolution" and I'm still w/o a clue!
In all this time I've certainly learned something about peoples "metaphysical" or "philosophical" stances wrt evolution ("blind," "mindless"), but virtually nothing about design (that I didn't already know LOL).
Comment by Rock — January 10, 2007 @ 1:32 pm
January 10th, 2007 at 3:24 pm
Rock wrote:
Rock,
See my reply to Eric Anderson above for an explanation of what I think is the major difference.
Comment by keiths — January 10, 2007 @ 3:24 pm
January 10th, 2007 at 6:34 pm
keiths wrote:
"It was never striving toward porpoises or away from them. Changes simply happened over time; the ones that tended to facilitate survival and reproduction were retained; and we now find ourselves in a world containing bacteria and porpoises, both of whom remain (for now) successful at survival and reproduction."
Assumption based on the theory: changes that tended to facilitate survival were retained and now we have porpoises.
Tautology slipped in the back door (actually right in front of our noses): porpoises were "retained" because of characteristics that helped them survive. How do we know that? Well, because here they are — they survived!
Bonus observation: bacteria reproduce more quickly, with less resources, occupy a greater variety of niches, and get to pass on their precious genes, by all accounts, a lot more efficiently. Again, it is worth asking: Is there any reason to believe, beyond the fact that Darwinism demands it, that every one of the functional complexities we see around us confer a survivability advantage?
Comment by Eric Anderson — January 10, 2007 @ 6:34 pm
January 10th, 2007 at 6:54 pm
Again, it is worth asking: Is there any reason to believe, beyond the fact that Darwinism demands it, that every one of the functional complexities we see around us confer a survivability advantage?
Since complex functions are multi-component, each and every incremental addition in its pathway would have to confer a reproductive advantage.
Comment by Bradford — January 10, 2007 @ 6:54 pm
January 10th, 2007 at 10:56 pm
Bradford wrote:
Absolutely right. And that is precisely the point where Behe focused his attention in 1996. In addition to that damning fact, I want to consider a moment another fundamental question, namely, whether there is anything to suggest that every complete functional system confers a survivability advantage (speaking here of the building of function, rather than its degradation). Perhaps each such system performs a function, but is it really a function that provides a survivability advantage?
A contemplative review of nature will suggest examples that appear to have a logical or useful function, but that do not necessarily translate into survivability advantage. The traditional response is inevitably the same: in some long forgotten age the system must have conferred a survivability advantage. Such a declaration is, however, not a statement of fact nor is it an explanation of how the system came about. Rather, it is simply a restatement of the theory. The declaration will often be tenuously propped up with a just-so story, but it will rarely, if ever, be supported by any actual evidence. Thus, we are left with the wonderfully circular "explanation" that the biological system came on the scene because it conferred a survivability advantage. And how do we know that it conferred a survivability advantage? Well, here is it, so it must have conferred a survivability advantage!
Comment by Eric Anderson — January 10, 2007 @ 10:56 pm
January 10th, 2007 at 11:27 pm
I would think that evidence for a function conferring no reproductive advantage would also be prima facie evidence for ID. However, the ability to conceive of a selective utility would be an obstacle to the acceptance of the "no advantage" argument. I distinguish between a conceptual utility and a demonstrable one but not everyone does.
I received an e-mail from a friend of mine who is currently employed in the UK as a professor of mathematics. He noted a number of life experiences and some physical features associated with things like appreciating music and beauty and emotional responses; none of which could be unequivocably associated with the conferrence of enhanced reproductive fitness but all of which lend themselves to explanations of resourceful and imaginative minds. This is the kind of speculation observed when empirical support falls short of supporting theorized mechanisms.
Comment by Bradford — January 10, 2007 @ 11:27 pm
January 11th, 2007 at 11:55 am
See my reply to Eric Anderson above for an explanation of what I think is the major difference."”kieths
I saw it: "Human design and evolutionary algorithms share the characteristic of employing multiple iterations, as you point out, but in the case of human design, the "mutations" that are generated are not blind at all, but are the ones that the designer thinks will get him closer to his design goals (i.e. the selection criteria)."
Human design and evolutionary algorithms? Ya lost me right away here. Evolutionary algorithms are human designs. I am sure I don't understand rightly what you were trying to say. And of course, a designer will attempt to skew a search positively in the direction of his objectives. And one of the advantages of evolutionary algorithms (if properly devised), and an advantage that makes them a quite attractive (and sometimes the only effective) alternative to the designer is that they do this automatically. (Which itself suggests that contrary to a common argument that evolution is a ridicuoulsy asteful way to design anything, there are in fact distinct economies involved from the designers'perspective. But no more about that.)
However, kieths, what does the designer do when there is a definite uncertainty wrt to his "design goals (i.e., selection criteria)"? (I think people who have some real-world experience will probably this situation as more typical.) I can tell you what I would do"”I would seek to systematically eliminate in so far as possible any artifactual biases I have unintentionally introduced into the evolutionary design processes, such as in the selection of the code, and in the algorithmic procedures used to generate random numbers, how and when the operators introducing variation into the population of candidates is introduced, etc. Indeed, if I really knew how to bias a search for a solution then more direct methods would naturally suggest themselves to me. So I don't think you've truly identified a difference between design and evolution. But I implied one myself: The evolutionary process proceeds automatically, mechanically, whereas my interventions in the process may not be so automatic or mechanical. (IDers? Any thoughts about that?)
Which reminds me of another design advantage to evolutionary computation: Evolutionary algorithms are "anytime" algorithms, meaning that upon arbitrary termination they can be expected to have found the best solution at that time. Many people have the impression (this is a common argument amongst Neo-Darwinists) that evolution is ridiculously wasteful way to go about designing anything, but there is a definite economy involved from the designers perspective. It saves him the wasted effort of pursuing the incorrect solution to the problem or having no solution in hand or even in sight when an arbitrary deadline is imposed.
This relates to Bradford's question: "Since complex functions are multi-component, each and every incremental addition in its pathway would have to confer a reproductive advantage." But since these are designed processes (and not de jure theoretical doctrines like Darwinism or Neo-Darwinism) this is not really an objection to evolutionary computation. Nothing prevents me from designing the evolutionary process to admit "less fit" instances and there are in fact advantages to doing so. (This is very much like what is done in "tabu" search and optimization methods, e.g.) I think if you will familiarize yourself more with the primary literature you'll find that designers have little interest in conforming their designs to the pet theories of biologists. In the natural sciences things can "work in theiry." In design science nothing "works in theory." It either works or doesn't. In that repect design science is far more demanding than natural science.
Macht asked the question: "In this post I would like to explore some of the implications of evolutionary algorithms (EA's) and what they can (and can't) tell us about design." And it occurred to me if they tell us anything about design we should ask why a designer chooses to use such methods. And to answer that question we should ask another question: What characterizes the problems (and solutions) to which these techniques are effectively applied? Needless to say these are complex problems, definitively problems that are analytically intractable (by "direct methods") for a variety of reasons, such as they are cursed with dimensionality, there are significant unknowns or uncertainties, problems that in short, that do not have any known material implementation that solves.
I realize the bloggers are principally interested in religious matters, but I can't give it a "theological spin." I can't think of a reason why God would bother to perform an experiment. And biological evolution is just an exercise in automated experimental design. And I suppose that's the only reason why biologists think that such designed evolutionary processes can tell us anything about biological evolution.
But that kind of thinking generally befuddles me though. OTOH I do know if there were some really interesting "religious" dimensions to such seeming mundanities it would be missed by persons who a priori make a "hard" (but otherwise inexplicable) distinction between design and evolution. Obviously they are not such different things because biologists generally think life forms evolved, but admit they sure look like they were designed. As if! How would they know?! They are used to asking questions similar to those asked here: What can such evolutionary design techniques tell us, if anything, about biological evolution? Designers don't often ask that question, and likewise biologists never ask what evolutionary design can tell us about design (or designers). But now I'm getting all "designer-centric" and I know that's frowned upon so I'll keep my questions to myself.
And its not topical anyway as macht didn't ask that question. Nonetheless he asked a very interesting question: In this post I would like to explore some of the implications of evolutionary algorithms (EA's) and what they can (and can't) tell us about design.
I think evolutionary design techniques, when consciously embraced and reflected upon (since we all use such techniques but don't always consider that we are doing so) reveals a little appreciated paradigm-shift in the way design decisions can be made (and automated), which I think is interesting, but I don't think its going to be of much interest to the bloggers to explore.
Comment by Rock — January 11, 2007 @ 11:55 am
January 11th, 2007 at 12:09 pm
This relates to Bradford's question: "Since complex functions are multi-component, each and every incremental addition in its pathway would have to confer a reproductive advantage."
I won't dispute this but would add that selection demands some advantage, however slight, so if the less fit still confers some advantage it would be consistent with neo-Darwinian theory. If the capacity for and direction of change is front loaded one would still use selection criteria by which to assess the credibility of the theory, right?
Comment by Bradford — January 11, 2007 @ 12:09 pm
January 11th, 2007 at 3:03 pm
Notions of selection for fitness and how they differ in biological theory from design is an interesting subject, Bradford. Consider a simple example: a grounded electrical cord. The guy who invented it (whoever that was) no doubt thought that his design was "fitter" than the old ungrounded cords. But imagine him taking his invention to the marketing department. LOL Their gonna tell him this is a truly stupid idea. Unfit. (And maybe they did!) No one's gonna buy it, ya dimwit, "˜cuz it won't fit anyone's outlets! Even if the consumer sees the advantage of it, has a criteria for positively selecting it over any alternative, he has a disincentive"”the consumer will be required to rewire all his electrical outlets.
Two or three points here. Sometimes there are no selection criteria because there is no choice. Sometimes such criteria are drastically restricted (as in the example of three-prongs) by the very fact that design (like biological evolution) is a strongly path dependent process. And sometimes even when presented with what seem to be viable alternatives from which one could select one as advantageous over the other, there is no effective way to determine what that advantage is"”what truly distinguishes the alternative"”in which case the selection from amongst them would be said to be arbitrary. We could flip a coin, default lexicographically, or choose first in temporal order, so even when there appears to be no real basis for the selection in terms of "advantage,' we can still make selections in some sense.
I would hazard to speculate that the theory of natural selection, and therefore the concept of fitness, is one of, if not the most, complicated theories ever devised by scientists. There is a reason for that and it hardly needs to be voiced: The fit between the life form (the design) and the pattern to which it must be fitted is exceedingly complex and the process (variation and selection) whereby this fitting is effected is too.
This is just another way that human design is like biological evolution. It never ceases to amaze me that designers are capable of true innovation, when one considers that whatever they invent has to fit into an existing technological infrastructure whose complexity defies both knowledge and imagination.
It's nothing short of a miracle, I'd say! LOL
"If the capacity for and direction of change is front loaded one would still use selection criteria by which to assess the credibility of the theory, right?""”Bradford
In one very interesting way the "capacity for and direction of change is front-loaded." All life on Earth is based on the genetic code. A code defines an intrinsic bias in any changes it admits. Typically codes are defined or described in terms of three basic parameters, and these altogether define the complete design space. I want you to think of these parameters as biases. As defining a capacity for and direction of change. Mike Gene's "theory" vindicated! I've suggested that people think about codes they way do"”as algorithms (because that's what they are). The genetic code, I don't believe, is properly understood in terms of arbitrary representational device, but as a set of effective procedures. Effective wrt what?! Adaptation.
Adaptation = Design?
(Sorry, macht I don't want to ruin your topic by rambling on endlessly and stupidly along any number of remotely tangential topics that interest me, so I'll just shut for a while. Yeh, right, Rock. Like its even possible for you to keep your mouth shut for a minute.)
Comment by Rock — January 11, 2007 @ 3:03 pm