RSS 2.0 Feed

» Welcome Guest Log In :: Register

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



Posts: 49
Joined: Sep. 2002

(Permalink) Posted: Feb. 27 2003,11:52   

This thread is to archive material relevant to the ID argument that evolutionary algorithms in general, and genetic algorithms in particular, either cannot generate "new information" or somehow show that an intelligent designer is necessary in order for an EA to generate new information.  It will include relevant postings from other boards as well as summaries and references to the appropriate literature.

I'll start it with a posting by Francis on ISCID's Brainstorms (a posting I was in the process of sporadically cobbling together until Francis anticipated me :))  In this posting Francis is responding to John Bracht's contention that (according to the TRIZ model of innovation), there are two sorts of inventions, routine and innovative, and that evolutionary processes can generate the former but not the latter.

Francis wrote as follows:

After having established that Genetic algorithms can indeed increase their hypervolume and thus cannot be in one grand swoop be excluded from being able to generate innovative/creative designs it may be interesting to explore if there may be some examples of such. Such a project however is complicated by the vague definitions of innovative/creative as used in TRIZ and thus on how to recognize creative/innovative solutions from routine design. In order to at least provide some foundation allowing us to define the various forms of design lets discuss the various forms of design.

Gero distinguished between routine and non-routine design. Routine design involves instances in which all necessary knowledge is available or more formally
Quote
...that designing activity which occurs when all the knowledge about the variables, objectives expressed in terms of those variables, constraints expressed in terms of those variables and the processes needed to find values for those variables, are all known a priori.

Source: MASS CUSTOMISATION OF CREATIVE DESIGNS John S. Gero

Gero points out that in addition routine design limits the available range of the variables.

Gero identifies two forms of non-routine designing:

Innovative designing and creative designing.
Quote
Innovative designing, in computational terms, can be defined as that designing activity that occurs when the constraints on the available ranges of the values for the variables are relaxed so that unexpected values become possible,

Innovative designing produces designs that belong to the same class as their routine 'brothers' but are also 'new'.

Creative designing:
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.

Lets look at the following paper

"Automatic Creation of Human-Competitive Programs and Controllers by Means of Genetic Programming" by Koza et al.

Abstract:
Quote
Genetic programming is an automatic method for creating a computer program or other complex structure to solve a problem. This paper first reviews various instances where genetic programming has previously produced human-competitive results. It then presents new human-competitive results involving the automatic synthesis of the design of both the parameter values i.e., tuning and the topology of controllers for two illustrative problems. Both genetically evolved controllers are better than controllers designed and published by experts in the field of control using the criteria established by the experts. One of these two controllers infringes on a previously issued patent. Other evolved controllers duplicate the functionality of other previously patented controllers. The results in this paper, in conjunction with previous results, reinforce the prediction that genetic programming is on the threshold of routinely producing human-competitive results and that genetic programming can potentially be used as an "invention machine" to produce patentable new inventions.

Koza provides us with two examples in which GA's were used to file innovative design patents
Quote
There are at least two instances where evolutionary computation yielded an invention that was granted a patent, namely a design for a wire antenna created by a genetic algorithm and a patent for the shape of an aircraft wing created by a genetic algorithm with variable-length strings.

Koza continues with a table of 24 examples of "results where genetic programming has produced results that are competitive with the products of human creativity and inventiveness."

15 of these 24 examples involve previously patented inventions, 6 infringe on patents and one improves on a patent. Nine duplicate the functionality of the patent in a novel manner.

The question remains, are these examples of routine or creative/non-routine design?

Koza specifies twoways of running GA's

There are two ways of determining the architecture for a program that is to be evolved using genetic programming.

1 The human user may prespecify the architecture of the overall program as part of the preparatory steps required for launching the run of genetic programming.

2 Architecture-altering operations may be used during the run to automatically create the architecture of the program.

Koza continues on to apply GA to a controller problem in the following manner
Quote
In this paper, programs trees in the initial random generation generation consist only of result-producing branches. Automatically defined functions are introduced sparingly on subsequent generations of the run by means of the architecture-altering operations.

The two lag plant:
Quote
As will be seen below, the result produced by genetic programming differs from a conventional PID controller in that the genetically evolved controller employs a second derivative processing block. As will be seen, the genetically evolved controller is 2.42 times better than the Dorf and Bishop 28 controller as measured by the criterion used by Dorf and Bishop namely, the integral of the time-weighted. absolute error . In addition, the genetically evolved controller has only 56% of the rise time in response to the reference input, has only 32% of the settling time, and is 8.97 times better in terms of suppressing the effects of a step disturbance at the plant input.

The three lag plant:
Quote
As will be seen below, the controller produced by genetic programming is better than 7.2 times as effective as the textbook controller as measured by the integral of the time-weighted absolute error, has only 50% of the rise time in response to the reference input, has only 35% of the settling time, and is 92.7 dB better in terms of suppressing the effects of a step disturbance at the plant input.

In both instances the controller included P, I and D, or proportional constants, integrators and differentiators and the genetic algorithm was allowed to vary its hyperspace by including one or more of each. Not surprisingly the program re-discovers the PID and PI topology as invented by Callender et al.

They conclude
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.

Thus not only did the GA control the parameter values but also the topology allowing the GA to vary the hyperspace.

But not only did the GA find solution but the solutions were better than the best solution provided by experts in the field of control technology.

A propos, Kroo, one of the inventors who patented design in which GA's were used comments that "This configuration was independently "discovered" by a genetic algorithm that was asked to find a wing of fixed lift, span, and height with minimum drag. The system was allowed to build wings of many individual elements with arbitrary dihedral and optimal twist distributions. The figure below depicts front views of the population of candidate designs as the system evolves. On the right, the best individual from a given generation is shown. "

Adrian Thompson describes in "Notes on Design Through Artificial Evolution: Opportunities and Algorithms" an experiment of the design of an electronic circuit in which it was attempted "to allow evolution to explore the design space as a type © system, with the minimum or simplifying constraints or prejudice."

A type © system refers to a system in which neither the forward nor inverse model is tractable.
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. Desirable or not, it is obvious that evolution is exploring new design space.

Finally a paper which I believe I have already mentioned but which captures much of my argument

JOHN GERO AND VLADIMIR KAZAKOV, "ADAPTING EVOLUTIONARY COMPUTING FOR EXPLORATION"
Quote
Abstract. This paper introduces a modification to genetic algorithms which provides computational support to creative designing by adaptively exploring design structure spaces. This modification is based on the re-interpretation of the GA's crossover as a random sampling of interpolations and its replacement with the random sampling of direct phenotype-phenotype interpolation and phenotype-phenotype extrapolation. Examples of the process are presented.

And here the relevant part
Quote
Non-routine designing maps onto creative designing. In routine designing all the variables which specify designs are given in advance. This means that the space of possible designs is known a priori, each point in this space can be constructed and evaluated directly. What needs to be done is to search this space in order to locate an appropriate or most appropriate design. The result here is the "best" design from this space. In nonroutine designing the result is the "best" space of possible designs as well as the "best" design from this space. Processes which modify the design space of the search problem are called exploratory processes.

Gero comments
Quote
One of the well-established notions related to creative designing processes is that an important means of characterising them is to determine whether they have the capacity to expand the state space of possible designs - exploration (Gero, 1994).
And finally
Quote
As can be seen from the example the resulting designs are unpredictable in the sense that they are unexpected given only knowledge of the original designs and of the interpolation/extrapolation functions. In this sense the process matches well the meaning of exploration both in the technical sense used in this paper and in the natural language sense. The designs produced by the system demonstrate both the novelty and unexpectedness of what can be generated.

It seems that John was correct in pointing out that creative design requires one to leave the hyperspace of the original and explore different design spaces. As I have shown however, GA's are very capable of doing exactly this, exploring hyperspace by varying the dimensions of the search space. As such I would argue that not only do GA's have the potential for innovative/creative solutions but have actually been shown to exactly produce such designs.

--------------
"There are only two ways we know of to make extremely complicated things, one is by engineering, and the other is evolution. And of the two, evolution will make the more complex." - Danny Hillis.

  
RBH



Posts: 49
Joined: Sep. 2002

(Permalink) Posted: Feb. 27 2003,11:58   

AS an addendum to Francis's Brainstorms posting archived above, this is the syllabus for Gero's course in Computational Models of Creative Design: Theory and Applications, which contains a number of appropriate references.  I accessed it on February 27, 2003.  If it disappears from the Web I have it on disk and will supply it at need.

RBH

--------------
"There are only two ways we know of to make extremely complicated things, one is by engineering, and the other is evolution. And of the two, evolution will make the more complex." - Danny Hillis.

  
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]