RSS 2.0 Feed

» Welcome Guest Log In :: Register

    
  Topic: Evolutionary Algorithms and GAs, Postings and Other Reference Material< Next Oldest | Next Newest >  
ExYECer



Posts: 36
Joined: May 2002

(Permalink) Posted: Mar. 04 2003,00:46   

A recent posting by Frances:

Dear John,

I am glad that you have returned despite your undoubtably busy schedule. You still seem to not agree with the plethora of evidence presented to you that genetic algorithms can and in fact do increase the hypervolume of possibilities. I apologize if my comments or arguments may be hard to understand, I will do my best to explain it as straightforward terms as possible. Others have shown other problems in your arguments so I will not focus on the issue of gene duplication and new function, something which seems quite prevalent in nature, nor will I follow the route of those who have challenged you to show that multicellulatity etc are truely examples of innovation. What I will be focusing on is the foundation of your argument namely that GA's cannot increase their hypervolume. While you have not formally defined the term hypervolume, I believe that from your claims one can make certain observations which if correct would contradict your claims. It may very well be that your definition of hypervolume differs from both how the term is used (although in limited form) or that your definition of hypervolume has evolved.

Basically the argument you are making is simple, a GA is limited by the number of parameters which are allowed to vary, these parameters determine the hypervolume in which the GA can search for solutions. If this is correct then it is trivial to show examples in which the number of parameters actually evolves with the GA. While such applications are relatively recent it may explain why your description of GA's seems to be somewhat outdated. It is perfectly common and acceptable than knew knowledge or previously unfamiliar facts can affect a hypotheses requiring it to be adapted or in worst case rejected. Since I believe that the basic foundation of your argument is that GA's cannot vary the hypervolume of their parameter space and since variations in the hypervolume are argued by you to be essential for creative inventions, one cannot reject GA's in one big swoop unlike the case in which one could argue that GA's cannot increase their hypervolume. So while your argument is correct for a limited class of GA's and thus your conclusions may very well be valid for such classes, I am not addressing whether or not the rest of your arguments are supportable, it also is clear that for a significant class of GA's the restrictions as formulated by you do not hold. This is not dissimilar from the findings that while the NFL theorems hold for a subclass of cases, they do not seem to hold for the classes which are most relevant. Now that I have laid out my conclusions based on what I believe to be your argument based on your own writings as well as based on the available research on GA's which addresses parameter space and hypervolume variations. Not only do I assert that GA's can increase their hypervolume but I have provided for several examples in which not only such GA's are shown in action but they arguable are shown to generate inventive and creative solutions.

So here we go:

I base most of my argument on your paper mentioned in my original posting referenced your paper which makes among others the following claims:

Quote

For each program, there is an n-dimensional hypervolume of possibilities in which that program operates, with n equal to the number of variable parameters. In the language of William Dembski's design inferential machinery, this n-dimensional hypervolume is equivalent to the reference class of possible outcomes, Omega 10.
Quote

This observation suggests that we may consider any genetic algorithm to be operating within a certain n-dimensional hypervolume, and certain fixed parameters completely determine that hypervolume ahead of time. Furthermore, any particular n-dimensional hypervolume is completely isolated and separate from any other m-dimensional hypervolume (m .ne. n).
and the most relevant one

Quote

The essential insight is that trial and error may only operate within a given hypervolume—but it may never jump to a new, higher-order hypervolume. The unbridgeable gaps between hypervolumes correspond to the technical contradictions in TRIZ theory.
Quote

This hypervolume is fixed by certain non-varying parameters (In Dawkin’s Biomorph example, the number of genes and the rules regarding how the integer values of each gene are interpreted) that an intelligent agent must set and which are not allowed to vary.
You then give some examples including the traveling salesman problem.

Quote

take-home lesson is that selection and mutation processes can operate within pre-set hypervolumes to find solutions that we know exist but which may be intractable given our current knowledge. However, they cannot find the hypervolume or the fitness function apart from intelligence—we still have to do the design work (getting the program into the right hypervolume where a solution may be found, and then finding the right fitness function over that hypervolume) before the algorithm can take over and sift through the vast possibilities to find a workable solution.
The examples shown by you indeed are good examples of a hypervolume or parameter space which is fixed but such GA's are a subclass of a much larger class of GA's which not only vary the values of their parameters but also the parameter space itself.

Now lets look at very similar words by Gero

Quote

in computational terms, can be defined as the designing activity that occurs when one or more new variables is introduced into the design. Processes that carry out this introduction are called “creative designing processes”. Such processes do not guarantee that the artifact is judged to be creative, rather these processes have the potential to aid in the design of creative artifacts. Thus, creative designing, by introducing new variables, has the capacity to produce novel designs and as a result extends or moves the state space of potential designs.
I provided a reference to a paper in which GA's are shown to generate better solutions to control problems than experts in these fields. They achieve this by not only searching parameter space but also higher dimensions of parameter space.

And once again the authors conclude that

Quote

This paper has demonstrated that genetic programming can be used to automatically create both the parameter values tuning and the topology for controllers for illustrative problems involving a two-lag plant and a three-lag plant.
So not only did the parameter values evolve but also the topology (hypervolume) itself. Other examples show how GA's can explore higher hypervolumes

Quote

It is expected that the performance of a circuit will fall with rising temperature, but Figure 5 reveals that the evolved circuit's behaviour also degrades as the temperature is decreased from 340mK. This kind of behaviour had never been seen in such proposed `single electron' circuits before, and indicates that the circuit actually exploits or relies upon the thermal noise of the electrons at 340mK. This is not necessarily desirable, and perhaps by evaluating across a range of temperatures during evolution a thermally robust solution could be found [7], but we see immediately that evolution is exploring a previously inaccessible part of design space/
Note that I am not arguing any specific examples in biology, others have done this and shown how the genetic toolbox seems to include variations in the parameter space.

Lets give another example out of many which shows how GA's can manipulate their parameter space

Quote

In designing a state space of possible designs is implied by the representation used and the
computational processes that operate on that representation. GAs are a means of effectively
searching that state space which is defined by the length of the genotype’s bit string. Of
particular interest in design computing are processes that enlarge that state space to change
the set of possible designs. This paper presents one such process based on the generalization
of the genetic crossover operation.
Adaptive Enlargement of State Spaces in Evolutionary Designing by JOHN S. GERO AND VLADIMIR KAZAKOV

A side comment about Davidson and genetic networks. I too have listened to a presentation by Davidson on the sea urchin and  the starfish. You state that "For instance, a starfish wiring diagram has some fundamental, deep-rooted differences from a sea urchin (which it is supposed to have evolved from), in terms of how genes are plugged into the network.". First of all it should be emphasized that starfish and sea urchins shared common ancestors. It's like saying that we evolved from apes rather than the more correct "apes and humans share common ancestry".

Some quotes from hist talk on 2/12/03 where Davidson presented some of the latest findings.

When looking at a genetic network slide for the sea urchin Davidson comments

endomesoderm formation in the sea urchin and I want to consider a piece of the network as it exists in another animal the starfish which diverged 500 million years ago.
two thing to discuss: part of the regulatory network that is responsible for skeletogenesis, how did the change happen?Endoderm gut formation, sea urchins and starfish have very similar processes here.

Three gene positive regulatory loop, system cannot revert. Multi gene loops are found in many gene loop networks 'drosophila', 'hox network" common loops. New invention the micromere. Making micromeres and skeleton is new, not having it is old. So skeletons happened since the divergence of the sea urchins and the starfish. Fate maps of both embryos, missing a skeleton but spatial relationships are pretty much similar with some minor differences.
Similar networks in gut formation for sea urchin and star fish, Foxa, Brachyary are examples of very similar genes. Now perturbation analysis on other genes was applied. Tbrain is involved in skeletogenesis, one of the regulatory genes that run the downstream skeleton. Chance to acutally look at the process of evolutionary change. In sea urchin it is used in endoderm, in starfish it is used in skeleton. Tbrain under the same regulatory controls as the other genes. So what did they find out? What remained the same in enormous detail. The same Krox gene activates the same Otx gene and has the same feedback relation with GataE and feedback to OTX. Forward drive feature, which has not changed in 500 million years. What is different? All of the connection to Tbrain are entirely changed, confined to two cis-regulatory elements, tbrain was totally rewired got a new cis-regulary control and got destroyed in the endoderm. Comparative investigation of cis-regulatory genes can help us understand how this all happened.

Discussion:

Lots of sculpting can be done by moving repression around. Tbrain was used in the gut first and now is in charge of the skeleton. Gene battery for skeleton came under tbrain control. I can make a scenario with a few changes of how this could have happened. Davidson provided a scenario mainly based on repression which may explain these morphological changes. It's a testable hypothesis. It's a hard problem: how do the kinds of multiple cis regulatory elements that are strongly interrelated appear in evolution. The traditional argument has been that GC/AT basepair changes can make surpressors but this is insufficient for more than single sites. Next argument: cis regulatory genes migrate by transposition: happens but where do they come from originally? It's hard to make a convincing case. So what other mechanisms could be responsible for constructing cis-regulating elements? Characteristics of these networks is their plasticity to rewiring.

Some relevant articles
"A regulatory gene network that directs micromere specification in the sea urchin embryo." Oliveri P, Carrick DM, Davidson EH.

Quote

To generate the echinoid system would then require only that the pmar1 gene (itself a member of a gene family; our unpublished data) be brought under the control of maternal factors localized at the pole of the egg, and that a single key regulatory link between it and the gene encoding the global repressor be installed. This evolutionary hypothesis suggests that despite its great elegance, the whole micromere specification system that we see in Fig. 7 is basically a jury-rigged add-on, which except for the role of pmar1, is all made of preexistent parts. Whatever its connection with evolutionary reality, the argument suggests that comparative network analysis will someday provide the means to test directly the pathways of regulatory evolution, so that we can understand not only how developmental systems work, but how they got that way.
Carl: When asked how ID would solve the problem you seem to not provide for any testable or quantifiable scenarios

Quote
There may be other proposals to account for many simultaneous mutations, but I have not been able to find one. That would leave ID as an excellent candidate, as it fits all the evidence.
So far I have yet to see any ID scenario so whether or not it fits 'all the evidence' would surely seem to be begging the question. Perhaps if you could spend some time on elaborating why you believe ID is an excellent candidate rather than assert it then we can actually determine for ourselves if there is some foundation to your claims.

When asked about the reason why humans should be the goal Carl suggests that this is because of his religious beliefs. But all life is created in the image of God, including us. Evidence of a designer would be helpful in supporting a belief, not necessarily a Christian one though but so far the evidence of such a designer seems to be what seems to be lacking. Attempts have been made to infer its existence through negative evidence but they seem to all have failed so far. As a Christian I do believe that God created us and all life in His image and we just happened to be that part of His Creation which evolved to become able to appreciate in fuller detail His Creation. But we are getting into religious speculations here.

Yersinia, thanks for your extensive links which approach the whole discussion from a very different side namely by showing that evolution and gene duplication appear to be able to be quite inventive and creative. Changes in timing seem to be one way of development of evolutionary novelties.

ASCSCommanding, your approach is quite interesting in that you show that the difference between us and other organisms is contained in the dimensionality and ordering of the billions (?) of basepairs, something which is not by itself beyond at least the theoretical range of GA's. Indeed, without knowing the predecessors, it may be hard to identify what is truely inventive. A similar problem seems to apply to CSI, which seems to require historical knowledge. An interesting parallel.

  
  2 replies since Feb. 27 2003,11:52 < Next Oldest | Next Newest >  

    


Track this topic Email this topic Print this topic

[ Read the Board Rules ] | [Useful Links] | [Evolving Designs]