RBH
Posts: 49
Joined: Sep. 2002
|
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.
|
