|
Author
|
Topic: I.G.D. Strachan: An Evaluation of "Ev"
|
RBH
Member
Member # 380
|
posted 06. July 2003 02:13
An afterthought on the "fixed target" claim: In the Avida simulation, the external fitness function was fixed, in the sense that the mix of intermediates that produced reproductive advantage did not change during the course of an evolutionary run. However, the mix of lineages in the population, and hence the competitive context, changes over time during a run. Since lineages compete with each other for living space on the Avida world matrix, a lineage that has an advantage early in a run because it performs one appropriate input-output mapping would likely be at a disadvantage late in a run when it is up against lineages that perform multiple mappings.
An interesting set of research questions falls out of that observation: What would be the effect of imposing a dynamic fitness function over the course of a long evolutionary run, where the reproductive advantages conferred by the various less complex functions are (randomly?) varied on some appropriate time grain? Under those circumstances, where the external fitness function changes over time, would lineages adapt? Could a lineage evolve to perform the more complex (4-nand and 5-nand) mappings when the particular less complex mappings that are rewarded change?
Clearly that will depend in part on the time grain of the external environment's variation. I can see two potential patterns in the evolutionary runs. In the first, with relatively slow variation in the exernal fitness function my bet is that lineages will emerge to adapt to the changing circumstances, and that lineages that perform the more complex mappings will emerge.
If the variations in the external fitness function are rapid relative to the evolutionary rates possible in the simulation, then I suspect the whole population will evolve an array of 'species' that roughly mirrors the statistical properties of the variations in the external fitness function. (For those not familiar with Avida, with a decently large (e.g. 3,200 cell) 'world,' typically a significant number of lineages (ranging into the dozens or more) are simultaneously present, and at least in evolutionary runs without an external fitness function less well-adapted lineages can hang on in the population at low numbers for some time.) The distribution of the lineages present in the population after some considerable period of evolution would, I suspect, roughly mirror the distribution of variations in the external fitness function. I also suspect that lineages capable of performing the more complex mappings would also evolve in this kind of environment as well, though I'm less certain of that. I have to think about that a while to develop a firmer expectation.
RBH
IP: Logged
|
|
Erik
Member
Member # 160
|
posted 06. July 2003 18:43
Paul Nelson, the sitelocations array in Schneider's computer program seems like a reasonable model of reality to me. Since binding sites exist at specific locations in real (biological) genomes it seems reasonable to place them at specific locations in the computer simulation as well. The fact that the sitelocations array does not change corresponds to an assumption that the evolution of new binding sites is a slow process compared to the evolution of the binding site recognizers and characteristic nucleotide frequencies at binding sites (or, more generally, it corresponds to an assumption that allowing the number and locations of binding sites to evolve as well would not significantly change the outcome of the process). Perhaps the biggest idealization is the approximation that the portion of the genome outside of the binding sites is characterized by the statistical distribution of single nucleotides (as opposed the statistical distribution of pairs, or n-tuples, of nucleotides). This is definitely a good approximation for the simulation, but I don't know if it is a good approximation for real (biological) genomes*. On the other hand, Schneider's conclusions were more qualitive conclusions about Darwinian evolution and binding site recognition in general, than they were quantitative conclusions about the particular processes of Darwinian evolution we observe in biology.
Erik
* Question for molecular biologists: How large portion of a genome is saturated with point mutations (or has the same statistical properties as a portion that is saturated with point mutations)? Does the answer differ a lot between bacteria and mammals?
IP: Logged
|
|
Pim van Meurs
Member
Member # 541
|
posted 12. July 2003 16:41
I have confirmed by initial suspicions about Ev with Tom Schneider. Indeed, the recognizer and binding sites co-evolve thus the similarity between the simulation on ISCID (Vignere (sic)) and Ev is wanting since Vigenere finds a fixed target ("The answer is 43") while Ev does not find a fixed target.
Thus my conclusion is that Iain's attempt to link Ev to be related to Dawkins' Weasel seems to be erroneous.
Tom updated some of his graphics see Here for more details
Hope this clarifies some of the issues.
IP: Logged
|
|
Micah Sparacio
Member
Member # 6
|
posted 13. July 2003 09:16
quote:
I have confirmed by initial suspicions about Ev with Tom Schneider. Indeed, the recognizer and binding sites co-evolve thus the similarity between the simulation on ISCID (Vignere (sic)) and Ev is wanting since Vigenere finds a fixed target ("The answer is 43") while Ev does not find a fixed target.
Pim I'm not sure that I understand your point, especially after viewing Tom Schneider's reply to your question:
quote:
Pim van Meurs asked:
... even with the same initial conditions for the genome, the final evolved binding sites/recognizers will vary?
Yes, the sites and their recognizer are different.
Perhaps I'm reading this all wrong, but with the vignere program, you've also got a co-evolving genome and cipher which are different each time you run the simulation.
IP: Logged
|
|
Pim van Meurs
Member
Member # 541
|
posted 13. July 2003 15:26
Micah,
Correct me if I am wrong but the cipher and the 'genome' in the vignere (sic) program, always result in the same answer "the answer is 42".
not so for Ev.
Seems that Vignere (sic) and Ev share only a superficial similarity here.
Not surprisingly since the cipher and the message are related by a functional/linear relationship.
Btw I assume Vignere refers to Blaise de Vig_e_nere who used Caesar like ciphers?
Vignere has a fixed target, Ev hasn't. From Vete2.php " basis of similarity to the target text"
Thus while Vig(e)nere may be related to Dawkins' Weasel, Ev clearly isn't.
Iain's comments thus apply to a more general Weasel approach but their relevance to Ev seems minimal in this aspect.
[ 13. July 2003, 15:39: Message edited by: Pim van Meurs ]
IP: Logged
|
|
Erik
Member
Member # 160
|
posted 13. July 2003 19:58
Actually, Strachan's fitness function is, in a sense, intermediate between the fitness functions used by Dawkins and Schneider, respectively.
Dawkins's fitness function is a decreasing function of the distance to an optimal genotype. This means that the fitness landscape looks like a (many-dimensional) cone, with the tip of the cone corresponding to the best possible genotype.
Strachan's fitness function is a decreasing function of the distance between one half of the genome to the other half. This means that the fitness landscape will look like a (many-dimensional) vulcano crater. That is, the best possible genomes are located on a many-dimensional "circle", with fitness decreasing the farther away from the circle you get.
Schneider's fitness function is too complicated to allow me to visualize it with confidence, but I'd imagine that it looks like a deformed and rugged version of Strachan's fitness function. Some of the deformations may be large, but we would still see an obvious qualitive similarity to Strachan's fitness function (or so I think).
Just as Dawkins's fitness function is among simplest conceivable models for the (non-neutral) evolution of a single genotype, Strachan's fitness function is among simplest conceivable models for the coevolution of two genotypes. I think Strachan's fitness function is a reasonable abstract idealization of coevolution. It is a reasonable starting-point for studying coevolution. Schneider's fitness function is more specific in that it is intended to be an idealized model of the coevolution of binding site patterns and recognizers. If we must (why?) single out one of the fitness functions and say that it is the most deviant one in our triple of fitness functions, then it would have to be Dawkins's fitness function. In other words, Strachan's fitness function has more in common with Schneider's fitness function than with Dawkins's.
Erik
[ 14. July 2003, 05:51: Message edited by: Erik ]
IP: Logged
|
|
Pim van Meurs
Member
Member # 541
|
posted 13. July 2003 20:24
Erik,
And yet Iain's solution is always deterined, as is the case with Dawkins by the global goal set while Ev's 'solution' evolves truely in a coevolutionary manner namely both the fitness function and the genome are time variant and not pre-specified.
In fact all that Iain has done is to add another functional mapping between the goal "the answer is forty two" but to state that the solutions co-evolve seem to be in need of some additional explanation. As I understand it there is a simple mapping between the cypher and the solution.
IP: Logged
|
|
Micah Sparacio
Member
Member # 6
|
posted 13. July 2003 21:50
Pim,
In what sense do you mean determined? It wouldn't change things if Strachan had chosen a random target and string length at the beginning of each run. The cool thing is that we end up with a different organism in each run.
Also, when you say that there is a predefined target, keep two things in mind. First, Strachan's target is pre-determined in the same way that EQU is pre-determined in the Lenski simulation. Yet, what interests us is that a different genome/organism results in each run. Second, there is plenty that is pre-determined in Schneider's system (IIRC, e.g. number of binding sites). I think that Strachan identifies some of these things in his paper and pulls out the implications (its been a while since I read the paper, so I'll have to take a another look).
[ 13. July 2003, 21:52: Message edited by: Micah Sparacio ]
IP: Logged
|
|
Erik
Member
Member # 160
|
posted 14. July 2003 05:53
Pim van Meurs wrote: And yet Iain's solution is always deterined, as is the case with Dawkins by the global goal set while Ev's 'solution' evolves truely in a coevolutionary manner namely both the fitness function and the genome are time variant and not pre-specified.
I don't know what you mean by "always determined" and "global goal", but here's how the regions of maximum fitness are determined:
Dawkins's GA: A location is chosen arbitrarily (Dawkins picked the sequence "METHINKS...", but that has no significance). This is assigned the maximum fitness by the fitness function and its all downhill from there. The fitness function is fixed through the entire simulation.
Strachan's GA: By arbitrarily choosing a sequence to encode & decode, you fix the location of the circle* of maximum fitness. Any genome on this circle will be assigned maximum fitness by the fitness function and it's all downhill from this circle. The fitness function is fixed through the entire simulation.
Schneider's GA (Ev): By randomly and arbitrarily fixing the binding site position at the beginning of the simulation, you fix the location of the region of maximum fitness. It's all a rugged downhill slope from there. The fitness function is fixed through the entire simulation (exactly the same rule is used to determine the number of recognition mistakes at the beginning at and the end of the simulation).
Adami's GA (Avida): The fitness function is determined implicitly by how the programs interact with their environment and with other programs. This fitness function depends not only on the genome of the individual whose fitness is to be evaluated, but also on the composition of the rest of the population (this is particularly obvious in the case of parasites, which of course are most fit in the presence of their hosts). By deciding which logical functions that increase fitness and how much (I don't write "arbitrarily" because this is significant for the dynamics), you add a static contribution to Avida's fitness function as a result of the environmental interactions.
Pim van Meurs wrote: In fact all that Iain has done is to add another functional mapping between the goal "the answer is forty two" but to state that the solutions co-evolve seem to be in need of some additional explanation. As I understand it there is a simple mapping between the cypher and the solution.
In the region of maximum fitness there is indeed a simple mapping between the two parts of the genome that coevolve in Strachan's GA. In Schneider's GA there is, in the region of maximum fitness, a less simple mapping between the parts of the genome that coevolve. The two parts coevolve because the modifications of them are highly correlated. One difference between Strachan's and Schneider's fitness function is that in the former the region of high fitness can be reached by just modifying one of the parts. In the latter both parts must be modified.
Erik
* The genome space is finite with periodic boundary conditions. This means that the genome space looks like a (many-dimensional) torus. The region of maximum fitness resulting from Strachan's fitness function is a line (or many-dimensional hyperplane), but if you follow that line long enough you can back to where you started (periodic boundary conditions). That's why I called the region a "circle", but it occurs to me now that visualizing it as a line is a little better.
[ 14. July 2003, 07:31: Message edited by: Erik ]
IP: Logged
|
|
Pim van Meurs
Member
Member # 541
|
posted 14. July 2003 12:51
Micah: In what sense do you mean determined? It wouldn't change things if Strachan had chosen a random target and string length at the beginning of each run. The cool thing is that we end up with a different organism in each run.
The main difference is that Strachan specifies the solution while Lenksi and Schneider do not constrain the solution in this manner. The question is if information arose because of some front loading, and certainly one may argue that Strachan and Dawkins pre-specify the solution. But in case of Lenski and Schneider the solutions are not predetermined by the initial conditions and thus it seems that information was "created" rather than pre-specified.
Of course Strachan could make the goal to be randomly specified but the solution is always what has been specified as the global goal. Not so with Schneider and Lenski's simulations.
quote:
Also, when you say that there is a predefined target, keep two things in mind. First, Strachan's target is pre-determined in the same way that EQU is pre-determined in the Lenski simulation.
If that is the case EQU would invariable be a result but it isn't. Strachan has to explicitly predefine his target. Not surprisingly in each run Strachan finds the same solution. To suggest that there is a similarly predetermined target seems untenable.
Micah: Yet, what interests us is that a different genome/organism results in each run. Second, there is plenty that is pre-determined in Schneider's system (IIRC, e.g. number of binding sites).
Sure, there are predetermined parameters in Schneider but lets not forget that we are trying to establish if the outcome is predetermined. The question is, is the predetermination of the number of binding sites important to the increase in information? Strachan predetermined the outcome, Schneider did not. This contingency in the outcome is what is a major and determining difference. That is the suggestion by Strachan was that the researcher predefines a goal "the answer is forty two". In Strachan's case, it is clear that he sets a global goal to be the specific string and one may thus argue if information was front loaded. But in the cases of Lenski and Schneiders no such front loading which invariably leads to EQU or a particular binding patterns exists.
IP: Logged
|
|
RBH
Member
Member # 380
|
posted 14. July 2003 16:33
There's another substantial difference among the set of simulations under discussion, and that is the metric used in the evaluation of fitness. As I (no doubt imperfectly) understand them, Dawkins', Strachan's, and Schneider's simulations (as well as the VETE simulation on the Web) all use an explicit measurement of the difference (analogous to Hamming distance) between the output of the genotype under evaluation and some global reference peak (or line or lip-of-a-volcano) to determine fitness and thus reproductive advantage.
The Avida simulation does not. It evaluates just the current behavior of a genotype against the local topography of the fitness landscape. For example, in the Lenski, et al., study, evaluation of the fitness of a given digital critter had no explicit reference to how 'far' it was from performing the input-output mapping corresponding to EQU; it had reference only to its mapping's correspondence with one or another of the various logic functions that earned reproductive advantage. But for the last incremental step to performing EQU, the simulation would have performed in exactly the same way if EQU had never been rewarded with reproductive advantage. That is, EQU can be removed from the fitness landscape and evolution will proceed in much the same manner as when EQU is present and rewarded. (Pending getting Version 1.6 running on the Beowulf cluster, I've edited the Avida Version 1.3 control files to test this on Windows machines. It is the case.) EQU existed on the fitness landscape in the Lenski, et al., study, but its existence was not relevant to a digital critter's fitness unless and until a digital critter performed it. If a digital critter did not perform the mapping corresponding to EQU, the fact that EQU would have been rewarded is invisible to the simulation. To be sure, the fitness landscape had a non-uniform topography, with various logic functions differing in their reproductive advantage as a function of the minimum number of nands required to perform them, but there was no explicit fitness metric that depended on measurement of the difference between a critter and some distant peak. Any cumulative reproductive advantage that was acquired by a lineage was implicit in the non-uniform local topography of the landscape, not in an explicit measurement of long distances on it.
The WEASEL simulation and Strachan's VETE simulation, and possibly the Scheider simulation, embody an explicit notion of 'progress toward goal' in evaluating the relative fitness of members of a population; the Avida simulation does not. In Avida a lineage can decrease in fitness and still survive (the lineage survives, not specific individuals) for some time while members of the lineage continue to mutate and "explore" the neighborhood's topography. That is not the case in a pure WEASEL-type simulation. Is it true of those of Strachan and Schneider? Do less successful lineages hang on for significant periods, casting mutational tests out into the neighborhood, potentially finding alternative pathways on the topography of the landscape, in those simulations? I ask for information, not tendentiously. I don't know.
RBH
Added in edit: As soon as I can free up enough computer cycles and machines, I'm going to do some Avida runs replicating the Lenski, et al. study but randomly assigning fitness rewards (SIPs) to the various 'intermediate' logic functions. The goal is to look at whether any particular topography of fitness landscape is necessary, or if merely the existence of intermediates of some sort is sufficient to enable evolution to create a lineage that performs the mapping corresponding to EQU. The Lenski, et al. control conditions suggest that the latter is the case. That would invite an analysis of fitness landscapes in accessibility pre-topology terms like those that Stadler, et al. describe rather than in terms of some sort of Euclidean vector space.
[ 14. July 2003, 16:57: Message edited by: RBH ]
IP: Logged
|
|
Erik
Member
Member # 160
|
posted 15. July 2003 14:00
quote:
RBH: There's another substantial difference among the set of simulations under discussion, and that is the metric used in the evaluation of fitness. As I (no doubt imperfectly) understand them, Dawkins', Strachan's, and Schneider's simulations (as well as the VETE simulation on the Web) all use an explicit measurement of the difference (analogous to Hamming distance) between the output of the genotype under evaluation and some global reference peak (or line or lip-of-a-volcano) to determine fitness and thus reproductive advantage.
The Avida simulation does not. It evaluates just the current behavior of a genotype against the local topography of the fitness landscape.
I disagree. Remember your high school math classes. There you were taught that the functions
f(x) = (x + 1)(x - 1),
g(x) = x^2 - 1
are the same function. The fact that different expressions are used to define f(x) and g(x) is 100% irrelevant. A function should be thought of as a (possibly humongous) look-up table. The look-up tables for f(x) and g(x) are the same and therefore the two functions are the same.
A fitness function should not be identified with the expression used to define it or the algorithm used to compute it. A fitness function should be identified with its (possibly humongous) look-up table. Some look-up tables are easier to compress into neat expressions or algorithms than others, but that is (for the purposes of this discussion) a fact of only practical significance. The fitness functions used by Dawkins (WEASEL) and Strachan (VETE) can be compressed into neat little mathematical expressions. Some of these neat little expressions will be in the form of explictly expressed distances. Schneider's fitness function cannot be fully compressed into such a neat expression involving distances; the simplest way to compute it seems to be by running a little simulation specified by a few lines of code. But why do you find this to be theoretically significant?
In the light of all this, I wonder what you mean by a genotype being evaluated "against the local topography of the fitness landscape". I find it difficult to imagine how the process of looking up the fitness value in the (possibly compressed) look-up table could ever be non-local.
quote:
RBH: The WEASEL simulation and Strachan's VETE simulation, and possibly the Scheider simulation, embody an explicit notion of 'progress toward goal' in evaluating the relative fitness of members of a population; the Avida simulation does not. In Avida a lineage can decrease in fitness and still survive (the lineage survives, not specific individuals) for some time while members of the lineage continue to mutate and "explore" the neighborhood's topography. That is not the case in a pure WEASEL-type simulation.
Again I disagree. It is possible for an individual to have offspring with lower fitness in all of the GAs discussed here. And it is possible for this offspring to succeed in getting offspring of its own, despite having lower fitness than its parent. How long lineages of decreasing fitness one is likely to see depends on the size of the fitness differences and the mutation rate (try out Dawkins's fitness function in combination with an extremely high mutation rate! will a population that starts on the peak stay there?).
Erik
IP: Logged
|
|
RBH
Member
Member # 380
|
posted 15. July 2003 15:14
Erik,
That two functions are mathematically equivalent (are the 'same' function) doesn't imply that they model the phenomena of the world equally well. In order to model phenomena with mathematical expressions, one establishes (theory-guided) correspondences between the terms and operators of the math on the one hand and the objects, relationships, and processes of the phenomena on the other. If there is no relationship in the phenomena that corresponds to the squaring operator, for example, then a math expression containing the squaring operator is not a veridical representation of the phenomena. In that sense,
f(x) = (x+1)(x-1) is not the same model as g(x) = x^2-1.
Though f and g are mathematically equivalent functions, they are different models. The theoretical significance then arises when one manipulates a math model to calculate some state that is interpreted to describe the world, and takes that to mean that the world also arrives at that state by means of physical processes that correspond (map directly) to the particular mathematical transformations employed by the model.
Given that one can arrive at the same state with two mathematically equivalent expressions (models) that contain different terms and/or operators, the scientific question is which of the two models veridically maps the way the world does it. Which way of writing the function is the better representation of phenomena?
RBH
[ 15. July 2003, 15:19: Message edited by: RBH ]
IP: Logged
|
|
Erik
Member
Member # 160
|
posted 15. July 2003 16:14
quote:
A mathematician was asked by his religious colleague: "Do you
believe in one God?". He answered: "Yes, up to isomorphism!" (joke copied from the internet)
RBH,
1. Do you believe in one model?
2. What is the most veridical expression for the gravitational force between two bodies of mass m and M, respectively, separated by the distance r? Is it
F = GMm / r^2
or
F = GMm / (1 + (r + 1)(r - 1))
or something else? Same question for the electrostatic force between charges of size q and Q, respectively, separated by the distance r.
3. In a world where the differential and integral forms of Maxwells equations, the Heisenberg and Schrödinger formulations of QM, the Hamiltonian and Lagrangian formulations of classical mechanics, etc. coexist without competing you will find it extremely difficult to find anyone who agrees with you about different (but mathematically equivalent) representations being, in any significant sense, different models.
Erik
IP: Logged
|
|
RBH
Member
Member # 380
|
posted 15. July 2003 22:14
Erik,
We're using "model" in different senses, I think. In the case of the simulations at issue, I am interpreting a "model" to be a representation of the components of the innards of the real-world system, perhaps not isomorphic to all aspects of the phenomena but closer to that than merely a black box function. A mathematical model maps the input/output relationships, and it doesn't matter (perhaps aside from computational convenience) which of several equivalent functions one uses. However, if one wants to interpret the terms and operators of the equation as corresponding to parts of the system, then there are choices to be made.
In the present case, the question is whether the process of evaluating fitness in the innards of the simulation must include reference to the difference between the current state and some distant state, regardless of whether the difference is explicitly calculated on the fly or is pre-calculated in a lookup table. My understanding is that at least in the WEASEL and VETE simulations that difference must be calculated in order to assign a fitness value to a genotype. In the Avida simulation that difference is neither calculated on the fly nor is it pre-calculated and encoded in a lookup table. It is surely the case that there is a kind of lookup table in the Avida simulations, in the sense that if a digital critter performs a particular input/output mapping corresponding to an operation in the table, then it is assigned appropriate additional reproductive resources. But (with the 'number of nands' exception I noted above) neither the evaluation of the mapping nor the structure of the lookup table embodies an explicit or implicit calculation of the difference between current state and some distant state. That's the difference between goal-directed search and local evolution.
You asked quote:
1. Do you believe in one model?
I believe there are better and worse simulation models, in the sense described in my previous posting.
And quote:
2. What is the most veridical expression for the gravitational force between two bodies of mass m and M, respectively, separated by the distance r?
If the math operators are interpreted to refer to (represent) physical processes, then that's a question for research in physics, not math. For example, if the "^" in r^2 is interpreted to represent some actual physical process, then it's a question for research to see if in fact that physical process occurs. If the value calculated from an equation is interpreted to be produced by physical processes corresponding to the order and nature of the mathematical operations performed in the calculation, as it would be in a simulation model, then that's a topic for research: Do the implied intermediate states exist in nature? Not being a physicist, I'll pass on choosing among your examples. quote:
3. In a world where the differential and integral forms of Maxwells equations, the Heisenberg and Schrödinger formulations of QM, the Hamiltonian and Lagrangian formulations of classical mechanics, etc. coexist without competing you will find it extremely difficult to find anyone who agrees with you about different (but mathematically equivalent) representations being, in any significant sense, different models.
Once again, to the extent that the terms and operators of equations are interpreted to represent physical processes in the context of a simulation model of phenomena (as distinguished from a formal representation of the input/output mappings of a black box), then there are non-trivial choices to be made among mathematically equivalent representations. I'm not particularly concerned with whether lots of people do or do not agree with me. As my father (a WWII veteran) used to say, "Forty million Frenchmen not only can be wrong; they probably are!"
RBH
IP: Logged
|
|
|
Printer-friendly view of this topic