BIOLOGICAL INSPIRATION FOR COMPUTING 267
•A mechanism (or mechanisms) by which changes to the candidate solutions can be introduced—
portions of different candidate solutions are exchanged, for example, or modified in some small random way.^57
With these components in place, an evolutionary process takes place. The set of new solutions is
evaluated for fitness—those with lower fitness scores are thrown out and those with higher scores are
retained. This mutation process is iterated many times, and the result at the end is (supposed to be) a
solution that is much better than anything in the starting set.
Initially demonstrated on the solving of what might be called “toy” problems, evolutionary tech-
niques have been used in a variety of business applications, including scheduling and production
optimization, image processing, engine design, and drug design. Evolutionary computation has also
achieved results that are in some sense competitive with human-developed solutions to quite substan-
tive problems. Competitiveness has a number of possible measures, among them results that are com-
parable to those produced by a succession of human researchers working on a well-defined problem
over a period of years, a result that is equivalent to a previously patented or patentable invention, a
result that is publishable in its own right (i.e., independent of its origins), or a result that wins or ranks
highly in a judged competition involving human contestants.^58
Evolutionary computation has demonstrated successes according to all of these measures. For
example, there are at least 21 instances in which evolutionary techniques have led to artifacts related to
previously patented inventions.^59 Eleven of these infringe on previously issued patents, and ten dupli-
cate the functionality of previously patented inventions in a non-infringing way. Also, while some of
the relevant patents were issued many years ago (as early as 1917), others were issued as recently as
- Some of the inventions created by evolutionary processes include the ladder filter, the crossover
filter, a second-derivative controller, a NAND circuit, a PID (proportional, integrative, and derivative)
controller, a mixed analog-digital variable capacitor circuit, a voltage-current conversion circuit, and a
cubic function generator. They have also created a soccer-playing program that won its first two games
in the Robo Cup 1997 competition and another that ranked in the middle of the field of 34 human-
written programs in the Robo Cup 1998 competition, four different algorithms for the transmembrane
segment identification problem for proteins, and a variety of quantum computing algorithms, and have
rediscovered the Campbell ladder topology for low-pass and high-pass filters.
Evolutionary computation also poses intellectual challenges, as described in the next several
sections.
8.3.1.2 Suitability of Problems for Evolutionary Computation,
Whether or not an evolutionary approach will be successful in solving a given problem is not yet
fully understood. Although many components of a full theory of evolutionary algorithms have been
worked out, there are critical gaps that remain open questions.
It is known that the relationship between the representation of a problem, genetic operators, and the
objective function is the primary determinant of the performance of an evolutionary algorithm. For any
optimization problem, there is always a representation or a genetic operator that makes the optima easy
to find with an evolutionary algorithm.^61 In addition, evolutionary algorithms are no better or worse
(^57) In biology, “crossover” refers to the process in which chromosomal material is exchanged between chromosomes during cell
duplication. The exchanged chromosomal material is analogous to portions of the different candidate solutions. “Mutations” are
genetic changes induced as the result of random environmental events.
(^58) See http://www.genetic-programming.org.
(^59) See http://www.genetic-programming.com/humancompetitive.html. More information on these accomplishments can be
found in J.R. Koza, M.A. Keane, M.J. Streeter, W. Mydlowec, J. Yu, and G. Lanza, Genetic Programming IV: Routine Human-
Competitive Machine Intelligence, Series in Genetic Programming, Volume 5, Springer, New York, 2005.
(^60) Lee Altenberg of the University of Hawaii was a major contributor to Section 8.3.1.2.
(^61) G.E. Liepins and M.D. Vose, “Representational Issues in Genetic Optimization,” Journal of Experimental and Theoretical Artifi-
cial Intelligence 2(2):101-115, 1990.