|
Conference Proceedings,
24th IEEE Conference on Signals, Systems, and Computers Asilomar, CA, November 5-7, 1990. R. Chen, editor. Pages 1030-1035 IEEE/Maple Press, San Jose, CA
Wirt Atmar
© 1990 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Abstract
Natural evolution is an iterative optimization process such that a population of trials is subject to repetitive selection, a process which operates to minimize functional (behavioral) error. The physics employed in common numeric search techniques is structurally different than that characteristic of natural evolutionary processes. Sufficient experience has now been garnered to suggest that all strongly-determined numerical optimization methods tend to work acceptably well on some adaptive surfaces, but exhibit a pronounced tendency to stall in indefinite oscillation, fail to converge, or become entrapped in local optima on others. These stalls are caused by the highly-determined correlation between parent and child trial vectors. But this is not the manner in which evolutionary optimization proceeds. The mutagenesis guaranteed by replicative error generates a continuum of fine- and large-grained mutations. The correlation between parent and child trial vectors is often strong, but it is never absolute. Under random mutation, no combination is impossible, thus global solutions in a finite state space are guaranteed in infinite time. Naturally-occurring processes which accelerate this search are discussed using two simple models, one combinatorial, the other time-sequential.
Introduction An increasingly common engineering design problem is the rapid and accurate determination of optimal (or near-optimal) solutions in complex systems which are extensively combinatorial. The functional form to be optimized is generally composed of a large number of independent variables, the measure of which is taken by the "appropriateness" or "fitness" of one or more trial vectors moving across the system-defined topography. Exploration by exhaustive enumeration is generally impossible. Time and complexity are the enemy in immensely large combinatorial state spaces. Nevertheless, simple evolutionary mechanisms exist which have optimized genetical systems of unimaginable complexity. The most rapid physical reactions known operate on the order of femtoseconds. The amount of information in the mammalian genome is such that a random rearrangement of the base pairs offers 103 billion possibilities. Should a million million experiments be run every femtosecond for the presumed life of the galaxy, only 1045 possibilities could have been tried and evaluated. That is, only 10-2,999,999,955 of the experiential state space could have been enumeratively explored, an unimaginably small number. This simple calculation must forcibly lead an observer to either one of two conclusions: (i) that the evolution of life, especially higher-ordered life, by means of simple natural phenomena and process is so beyond possibility as to be completely discountable, or obversely, (ii) that the evolution of highly ordered structures is guaranteed once self-replication is in place. No middle ground is arithmetically tenable. The mechanism which allows for the accumulation of such immense improbability is that the evolutionary process is not enumerative; it does not explore all possibilities. The track an evolving phyletic line wends through the experiential state space is irreversibly in the direction of increasingly appropriate behavioral response. Complexity is not built for complexity's sake but rather because it is the most appropriate contingent reaction thermodynamically. The subject to be explored here are those mechanisms which accelerate the evolution of complexly appropriate behavior. Two simple models will be used to demonstrate several of the most salient aspects of Darwinian evolution. One of the models will be combinatorial, the other time-sequential. Darwinian/Wallacian Physics On July 1, 1858, Darwin & Wallace presented joint papers describing the processes and consequences of natural selection, a theory each derived independently. The physics of the evolutionary process described by Darwin & Wallace operates solely through culling the least appropriate variants of the excess population that must inevitably arise in a finite arena. This simple mechanism has commonly been misrepresented or misunderstood. Selection operates only against expressed behaviors, never directly on the coding structure itself. Nor does the process select for isolated attributes separate from the behavioral appropriateness of the whole. The minimization of total functional behavioral error — integrated over all probable threat, ordered by the probability of that threat and the severity of its penalty — is the quality optimized; not the encoding genetics per se. The code evolves only by consequence. The acuity of selection imposed on a population is a direct function of the intensity of competition. In those rare periods when competition disappears, the selective filtering of phenotypes is concomitantly abated. In nature, absolute fitness values are indeterminable. Rather, context-dependent, relative behavioral error within the current population of phenotypic trials is the quality sieved by selection. Although selection often has a pronounced stochastic component, selection becomes inexorable over time within large populations under even the mildest competition for resources and space. In 1859, and later in 1871, Darwin defined a second form of selection, sexual selection. This second form is evolved within the group rather than being externally imposed, as is natural selection. Under sexual selection, (generally) males compete for the right to inseminate females. This second form of selection will be shown to be one of several mechanisms which greatly accelerate evolutionary optimization. The metric of natural selection is goodness-of-fit (minimal behavioral error) to external environmental demands. The agent of selection is competition for limited resources in a finite arena. Of that portion of selection which is internal to the group (sexual selection), Darwin argued demonstratable vigor to be the primary metric, but he seemed unsure whether the culling exclusion of the least vigorous males through male-male contest was a sufficiently comprehensive agent. Males in many species engage in elaborate courtship displays which appear to "fascinate" the female. Darwin added female choice as a second agent of selection and male attractiveness as a second metric. Female choice has proven to be less generalizable than male-male intrasexual combat; although the phenomenon surely exists, it is not informationally necessary. In mammals, the female's "choice" of males is most normally made in her absence. To insure the rapid exclusion of measurable defects from the germline, the species need only evolve symmetric behavior in the female such that she is reasonably sexually faithful to the subpopulation of victorious males.
 Fig. 1. Schematic representation of a single generation. Four mappings are defined: f1:I X G®P, epigenesis (environmentally influenced genetic expression); f2:P®P, phenotypic selection; f3:P®G, genomic survivorship; and f4:G®G, mutation (replication error). (After [7] p.14). Two state spaces are defined in Darwinian evolutionary theory: P, the phenotypic (behaviorial) state space, and G, the genotypic (informational) state space (Fig. 1). Selection (natural and sexual) operates only in P. The genetics which encode expressed behavior exist only in G. Darwinian evolutionary theory is the philosophical progenitor of statistical mechanics and information theory. The unifying concept in each is selection acting upon a population. Boltzmann wrote: "If someone asked me what name we should give this century, I would answer without hesitation that this is the century of Darwin". Boltzmann was deeply attracted by the idea of evolution of system states. He approached the question of thermodynamics not as individual trajectories but as that of populations ([1] pp. 240-241), thus the evident similarity between the simulated annealing [2] and simulated evolution [3],[4] algorithms is not coincidental. Shannon reinterpreted Boltzmann's populational entropy and made it an information measure, where noise is defined as a statistical population in a finite channel. Shannon's information measure, I, is defined more as a metric of surprise than disorder. In that, a philosophical circle is completed. Darwinian/Wallacian evolutionary optimization is an information-transforming process such that the agent of selection operates to minimize the costs of inappropriate behavior. Model 1: Combinatorial Optimization An adaptive topography is formed by a series of n linear equations. Bremmerman [5] wondered if evolutionary procedures could not be used to solve simultaneous equations. Such simple topographies are useful for experimentation because (1) they are known to possess a single global optimum, if they are not over- or underspecified, and (2) the global optimum can be easily deduced by standard methods. Consider a series of linear equations of n dimensions, where n is large:
n To place these equations in biological context, presume the xj Î X to be n independent gene products, the ri Î R to be m phenotypic behavioral responses, and the coefficients aij Î A to be the respective contribution of each xj component to the ri response. Such a system of equations is said to be non-pleiotropic iff aij = 0 " i ¹ j. (Pleiotropy is the condition in which a single gene (xi) exhibits manifold phenotypic effects on various character expressions. All physical systems, biological or mechanical, if randomly built, are extensively pleiotropic. Wright [6] has argued the universal pleiotropy of gene effects.) Let us also define m externally imposed, ideal behavioral responses, yi Î R . The criterion of acceptability (fitness) is the quality of system responses ri to the yi environmental demands. An error score E will occur which will measure the appropriateness of the behavioral state vector R to the required response vector Y, where
ei = | yi - ri | and where
E = S ei. Absolute fitness (zero prediction error) will occur when E = 0, if a solution exists. Bremmerman established an evolutionary scheme where the current parent vector generated 3n trial vectors by altering each xi ± 0, Dx through all possible combinations. Should one of these vectors provide a lower error score than the parent, it became the basis behavioral vector for the next generation. Bremmerman was disappointed and surprised to find how easily this simple gradient-search technique often stalled. Using ever smaller values of Dx did not help. Although Bremmerman's failure to reliably obtain solutions appears to more methodological than pathological, his "disappointment" is not uncharacteristic of such techniques. Iterative optimization techniques, especially those which are designed to accelerate convergence (e.g., over-relaxation, back-propagation, etc.), tend to become stalled in an oscillatory pattern, often some distance from the known optimum. But this is not the manner in which evolution operates. In genetical systems which are both complexly polygenic and highly pleiotropic, a virtually continuous range of phenotypic expression exists. Replicative error is random. If each of the xi's Î X are mutated by N(xi, si2), where si2 is a normally-distributed variance centered about the current mean xi, a qualitatively different result occurs. Gradient-search techniques often quickly become trapped in local minimum error wells from which no escape is possible. With the application of a gaussian noise function, a continuum of fine- and large-grained mutations appears. No combination is impossible; the combination necessary to jump a barrier only becomes a more remote possibility as the dimensionality of the state space is increased and the demanded distance from the present vector is increased. However, evolutionary experimentation is inherently a parallel process. The larger the effective population, Ne, at each generation, the more comprehensive the exploration (the greater the "sense") of the state space surrounding the current epiphenotype (the statistically expected phenotype) at each generation. This greater exploration of the adaptive topography feeds back into the population of trial vectors, and thus shallow local optima which might otherwise entrap a lineage of single trials for a time are traversed unnoticed. While this modified scheme remains basically as simple as Bremmerman's, a solution is guaranteed in any continuous, finite topography and tends to appear rapidly. Complex topographies are not necessary to generate conditions which cannot be solved enumeratively. Resolving the global optimum to 1 ppm in a rank 5 matrix generates an experimental state space of 1030 possibilities. An exhaustive search using a fast computer (106 evaluations per second) could explore only 3x1023 possibilities in 1010 yr, the life of the galaxy. Although solutions occur within a few minutes (105-106 trials), the speed of solution can be much increased if the variance is made a direct function of the error score, s2(E). As the error score approaches zero, reducing the variance causes the search to fine-tune itself. This effect is not unnatural. Genetic stablization by means of error repair and defect expurgation exhibits approximately this effect. Accelerating Mechanisms Three naturally occuring processes appear to accelerate normally-distributed evolutionary searches of complex adaptive topographies. They are: (i) increased rates of mutagenesis, (ii) the evolution of mechanisms of genetic stabilization, and (iii) noisy adaptive topographies. Increased Mutagenesis Increasing the rate of mutagenesis in a large population of trial vectors concomitantly increases the search rate, but only to a point. Beyond a certain threshold, further increases in mutagenesis (i.e., multiple mutations per locus (xi) per trial) garners no benefit and indeed will prove to be disruptive. Completely random trials assume the worst characteristics of enumeration, but with the additional penalty of trial repetition. To escape simple enumeration, evolutionary searches must exhibit pronounced correlation between parent and child vectors, but the relationship cannot be absolutely correlated, nor can it be completely methodical. Although no mutational possibility is disallowed in a true evolutionary search, the greatest rates of evolution will be achieved when the majority of trial vectors explore the state space immediately adjacent to the present epiphenotypic vector. The evolutionary invention of sex achieves both these qualities. Sexuality greatly increases the effective rate of mutagenesis over naturally-occuring background mutational rates by accelerating allelic and chromosomal recombination, but the process proceeds only in limited context. Existing fine-grained variation is drawn and evaluated from within a highly constrained subset of "working" variants. Genetic Stabilization The initial advantages of sex to an evolving lineage cannot however be ascribed to be either a necessary or consequential feature of inter-organismal chromosomal recombination; primitive eukaryotic species are not obligately outbred. Rather autogamy and automixis are common in lower-order eukaryotes, remaining common in phyla as complex as Bryozoa and some flowering plants. More likely, the principal attribute of sex in its most primitive form is the sexual alternation of diploid (redundant) and haploid (non-redundant) genetic states. Evolutionary optimization generally occurs quite quickly, the speed of which is proportional to the steepness of the adaptive surface's wells. As optimality is approached, the surface flattens and phenotypic (trial vector) wastage becomes an increasingly pressing issue. Natural populations are observed to suffer mutation rates of m = 10-5 to 10-6 errors per locus (xi) per generation. The expected number of novel errors to be introduced into the population per generation is pnNem, where p is the ploidy number, Ne the effective population size, and n the active length of the state genetic vector. Although the process may initially seem counter-intutitive, the stabilization of genetic information accelerates evolutionary optimization. Collapsing the variance of a normally-distributed mutagenesis function proportionally to the error (fitness) score increases the density of trial vectors by a factor of (st' / st)n, where st is the characteristic variance of the state vector at time t and n the rank of the trial vector. Because n is very large, small changes in s produce large volumetric changes in the state space which is to be probablistically explored. Sexual recombination is the union of two trial vectors into a single zygote. There are only two simple methods available to minimize the search-decelerating effects of unconstrained macromutations injected into a population: (i) post-union repair, and (ii) pre-union filtering. Some error can be detected and corrected without translating the encoded message itself. Repair mechanisms are known to be active during biological gene replication, transcription, translation and subsequent protein manufacture [8], [9], [10]. However, no finite set of information recovery algorithms can detect, repair and recover all forms of error. The second option, pre-filtering, is the mechanism of sexual selection as defined by Darwin. Genetic error is sieved through a (generally) male filter. The filtering mechanism is most exaggerated under haplodiploidy, a genetical condition in which females are diploid (redundantly encoded) and males are haploid (non-redundant). Under diploidy, two copies of the genome (the trial vector) are maintained in an individual. The presence of significant error at a locus (xi) is often overcome through the presence of an alternate, fit second coding routine (allele). If so, the defect is said to be fully recessive. But in a haploid male, any defect, no matter how minor, is open to direct exposure to selection. In both diploid and haploid males, prolonged demonstrations of relative physiological vigor by contesting males prior to mating operate to exclude the less vigorous, defect-impaired individuals from the recombining population, thereby collapsing species-typical variance. More importantly, the effect is multiplicatively regenerative, generation after generation, eliminating significant error from the population while honing species-specific variance to levels at or near environmental noise. Undulating and Noisy Adaptive Topographies Environmental noise may be defined as fluctuations in the adaptive topography which occur at rates faster than the generational rate of vector trials. Undulations may be similarly defined as fluctuations which occur at rates much slower than the generational rate. Although both forms of fluctuations in the adaptive topography are extrinsic to the evolutionary algorithm, both contribute to the acceleration of the evolutionary search. The presence of noise generates characteristics roughly equivalent to an underspecified set of simultaneous equations. An infinity of solutions exists in a noisy environment, but only within a constrained, fuzzy set. A noisy adaptive topography is no longer infinitely thin but assumes the attributes of possessing some "depth". Fitness values are randomly specified for any trial vector, within the bounds of the environmental variance. The effective result of such environmental noise is that shallow wells become less apparent to the evolving phyletic lineage of trial vectors. As the intensity of environmental noise increases, the effect a shallow well exhibits on an evolving population is lessened and loiter time near the well is reduced. Slow undulations exhibit a slightly different effect. Successful iterative optimization is a matter of steady reduction in functional error, regardless of the algorithm employed. Long-period undulations with large population sizes of high-n state vectors increases the probability that all relictual variance cannot be purged in the period between environmental shifts. Some evolutionary "baggage" persists at or above the level of short-term environmental variance. This relictual variance encourages the formation of simultaneous, polyphyletic lineages of trial vectors rather than beginning anew with a single, homogeneous solution. The exploration of the state space is often accelerated by these polyphyletic lineages. Model 2: Time-Sequential Optimization The environment presents itself as an mth order Markov chain, where the previous m symbols influence the probability of occurrence of the next symbol. Should the probability of certain symbol strings be high, then it is expected that the evolving phyletic lineage will come to predict these highly correlated strings. Uncorrelated symbols (noise) will be tend to be ignored in favor of more certain predictors of future events. If the environment were completely uncorrelated in its symbols strings, such that
Pr(x(t) | x(t-1), x(t-2), ..., x(t-m)) = Pr(x(t)) then optimal prediction would degenerate to predicting the most likely symbol. But the environment does not present uncorrelated strings of symbols. The language-like nature of environmental symbols is obvious. Ethograms are drawn to indicate the probability of transition from behavioral state to behavioral state in natural biota. The probabilities of transition are commonly indicated by varying thicknesses of arrowed paths between states. An ethogram is a stochastic Markov process described by the 2-tuple, < Q, d >, where Q is the set of behavioral states and d is a transition function such that
d : Q ® Q. The information lacking in an ethogram is stimulus-response identification. This missing information may be more completely represented by a finite-state machine (FSM) process. A Mealy machine is described by the 5-tuple, < Q, I, Z, d, w >, where Q is the set of behavioral states, I the set of input symbols, Z the set of response symbols, d the next-state transition mapping, and w the output mapping function. The 5-tuple which describes a Mealy machine naturally partitions itself into the two previously defined state spaces. The 2-tuple, < I, Z >, is an attribute only of the phenotypic state space, P. The remaining 3-tuple, < Q, d, w >, is the genome of a species, g, such that g Î G. The two state spaces are related by the mapping function w, where w(i,q) maps the present input and present state into the response symbol set
w: I X Q ® Z, and where d(i,q) similarly maps the present state and present stimulus into the next state
d : I X Q ® Q. If, at every state, the transition functions are specified for all input symbols, the machine is said to be completely specified, a condition akin to stochasticity. Only completely specified machines are considered in the following. For the purposes of simulation, a prediction error score, E, was established (following [3]) such that error in predicting the next symbol occurrence in a string of symbols of length k becomes the singular measure of fitness,
k and
n for the n strings of the environmental set. Zero error represents perfectly adapted structures.
Because a specific organism g is defined by its genomic 3-tuple, < Q, d, w >, and because all mutational events occur in the information state space G, a set of mutations,
m1 altered the output mapping, w (mild). Other mutational possiblities are easily imagined, but were unused. The application of only these three mutational forms is insufficient to reach anywhere in G in one step, thus there occur the possiblity of local optima from which there is no escape under these rules. The cure for this condition is simple: allow either multiple mutations per trial or impose more disruptive mutational functions on the evolving FSMs. For the purposes of the simulation at hand, m3 was found to be sufficiently disruptive that other functional forms appeared unneccessary. The number of possible rearrangements, N, for each mutational form are
m1: N = abn where n is the number of states, a the number of input symbols in I, and b the number of output symbols in Z. Because of the selection criterion imposed in these demonstrations, I = Z, thus a = b. Natural environments are complex in both space and time. A 20 x 20 square map consisting of potentially 400 distinct environmental strings was established. Each location could be occupied by only one organismal type per epoch. Competition per epoch was such that each organismal type competed with the four adjacent populations and its own progeny. The organismal species which best predicted the local string(s) occupied the space under contention. Ties were resolved in favor of the original occupant. The simulation was always begun with a single-state FSM placed at the center of an empty map. Two hundred runs were conducted. Several common themes predmoninate in the results. Accelerating Conditions The accurate prediction of complex environmental patterns cannot be accomplished by simple genomes. The task-at-hand thus becomes the identification of those conditions which promote the accelerated evolution of appropriate complexity in the genomic state structures. The evolutionary process in this time-sequential example is fundamentally the same as the combinatorial example, and the conclusions noted earlier are equally apropos to these simulations. However, due to the increased detail of these simulations, additional environmental factors can be identified which accelerate iterative optimization. Factor 1: Ambiguity. In a subset of experiments, 10 related environmental strings were presented at each point on the map. The FSMs were reset to initial state conditions for the prediction of each string in the set such that perfect prediction of all strings was impossible. This ambiguous condition provides for the possiblity of nearly equally fit but differently organized behavioral structures, analogous to genetic differentiation. In spatially patchy environments, environmental ambiguity promoted significant increases in diversity and complexity. Those sections of the strings which were ambiguous, when compared string-to-string, promoted hotspots (points of rapid evolutionary change) in the evolved state transition diagrams. Those string sections which were very similar or identical in all strings in the set promoted stablity in the evolved state structures, once reliable prediction was evolved. The adaptation to sets of similar strings emphasized the evolution of attributes of the class (signal) while suppressing environmental artifact (noise).
 Fig. 2. Experimental species diversity as a function of environmental heterogeneity and time. Species diversity is calculated using the Shannon index, H'. Factor 2: Environmental Heterogeneity. Heterogeneity promoted both diversity and evolved complexity. The results of a set of experiments appears in Fig. 2. In various experiments, differing environmental strings sets were placed: (i) randomly, (ii) as clinal gradations, or (iii) as isolating barriers, among other patterns. A recurrent pattern is presented in Fig. 2. Fig. 2 is unusual only in that in most monotypic environments, species diversity generally collapsed to one evolved species. Heterogeneity markedly accelerated the evolution of complexity, especially in the early epochs when no environmental string was well predicted. The mutating progeny of a locally adapted species often better predicted neighboring patterns than resident species or their progeny. Factor 3: Area. Area proved to be a strong determinant of evolved complexity and diversity. Because the map was square, the edge was first reached in Epoch 10 and the map completely filled in by Epoch 15. Prior to these critical epochs, diversity flourished on the expanding periphery. Competition, and thus stringent selection, is low or nil on the expanding periphery, thus a diverse array of types were permitted. Although short-lived, this diversity of types often proved valuable in accelerating the evolution of appropriate complexity. The negative inflection point in the diversity curves of Fig. 2 is the direct result of the initial onset of intense competition concomitant with the filling of the resource space. These rise-and-fall diversity patterns are commonly seen in the paleontological record (e.g., North American mammals, [11]; marine invertebrates, [12]) and in defaunation-refaunation experiments [13], and probably should be interpreted in the same manner. Factor 4: Stability. In a subset of runs, four similar but distinct environmental sets were cyclically presented as the environment. One set of strings was presented each epoch. The process was indefinitely repeated with a periodicity of four epochs. The anticipated result was that the evolving FSMs would develop four separate, perhaps interwoven pathways, one for each environmental type, not unlike the "phenotypic plasticity" that is occasionally found in plants in highly variable but predictable environments. This never happened. Rather than promote complexity and diversity, cyclicity markedly suppressed the evolution of complexity. The result was the evolution of FSMs which were generalists. No species predicted any seasonal environmental string set well, but rather "plowed" through them all with minimally acceptable behavior. Although initially unplanned, the identification of these three factors: environmental heterogeneity, area, and stability was particularly welcome. These three factors have come to be recognized as three principal factors promoting diversity in natural biotas. That these factors could be so clearly delineated with such simple rules of simulation suggests that these factors should be considered to be fundamental properties of the evolutionary process. Neutral Mutations Neutral mutations (mutations in unexpressed sections of the state transition diagram) were allowed and frequently occured. They did not however promote the acceleration of diversity or complexity. Neutrally-mutated "sibling species" on a homogeneous map are subject to selection neither for nor against them. Their survival is a Markov process with a close absorbing barrier, extinction ("gambler's ruin"). Because of intense competition for resource space and their small numbers, sibling species were quickly swamped. Their average time-on-map (1 or 2 epochs) proved to be too short to be of any value. Summary In all iterative optimization, the adaptive topography is the ultimate determinant of the result. The point of optimality resides somewhere on the surface; it simply waits to be discovered. Randomly-mutated populations are demonstrably efficient ways to explore state spaces of enormous complexity. Pielou ([14] p. 9) is quite wrong when she says that, "It cannot be too strongly emphasized that fancied links between the information-theoretic concept of 'information' and the diversity of an ecological community are merely fancies and nothing more". Evolved species diversity is inevitably strongly linked to the informational entropy of the environment. It is the nature of the Darwinian evolutionary process to minimize the environmental prediction error of the evolving species. While the form of the ultimately evolved state structures cannot be foretold, their behavior is greatly predetermined by the shape and informational entropy of the adaptive response surface. The shape of the response surface is unknown — and unknowable — to the iterative optimizer, other than by trial and error exploration. Nonetheless, given sufficiently disruptive mutation and a static topography, the eventual discovery of the optimal solution is guaranteed. Simulated evolution, in its most basic form (Model 1), is an ensemble of simulated annealings. The stochastic search of the adaptive topography is conducted in a very similar manner in both simulated evolution and simulated annealing. But there are differences. In simulated annealing, the entire population of trials is condensed every generation to a single ensemble average, T. In the Kirkpatrick et al. [2] algorithm, temperature becomes an search schedule, a mechanism of variance reduction as optimality is approached. However reporting only a single statistic (average velocity) denies much of the information about the adaptive topographcy that is intrinsically held in the distribution of the population of trials. But the more important difference is that simulated annealing emphasizes the stochastic optimization of passive particles, while simulated evolution emphasizes the same fundamental process with evolutionarily active particles of far greater behavioral complexity (Model 2). Simulated annealing has often been criticized as being slow, especially in its initial stages of search. However any algorithm that avoids entrapment in local optima possesses an infinity-to-one speed advantage over a search algorithm which becomes easily entrapped. Unconstrained mutability is the mechanism by which such traps are escaped and is fundamental to the general search technique. The initial slowness of simulated annealing results from the monophyletic (single lineage) search inherent to the annealing algorithm. In contrast, polyphyletic, simultaneous searches composed of a large population of lineages rapidly seek out the most promising descent path(s) quite quickly. Moreover, it is clear that there are processes which accelerate the random search. Some of the mechanisms are extrinsic to the evolving solutions and must be expected to be present in both optimization methods, such as noisy adaptive topographies. More similar yet, reductions in annealing temperature (cooling) have an effect directly analogous to the repair and expurgation of defects from a breeding population (sexual selection) in limiting the search-decelerating effects of macromutations. The effect of each is to decrease the variance of a normally-distributed mutagenesis function, a process which greatly accelerates end-point optimization, which would otherwise be the slowest portion of the search. Kirkpatrick et al. [2] were aware of the artificial intelligence possibilities inherent in the uninstructed nature of a stochastic search. But the process is not "artificial". The physics of the thermodynamically-inevitable stochastic search is fundamental to the evolution of life and intelligence. Part and parcel to the Darwinian stochastic search is the evolution of increasingly complex, increasingly appropriate behavior. Thus "intelligence" is not an end-point of such a search. Rather intelligence is inspeparable from the trial-and-error process itself. Acknowledgements
I wish to thank V.J. Atmar of AICS Research, Inc., University Park, NM, B.D. Patterson of the Field Museum of Natural History, Chicago, and D.B. Fogel of Orincon Corp., San Diego for their careful and thoughtful reviews of this paper. Literature Cited
[1] I. Prigogine and I. Stengers. Order out of Chaos.
Bantam Books, N.Y., 1984.
[2] S. Kirkpatrick et al. "Optimization by simulated
annealing," Science, vol 220, no. 4598, pp. 671-680.
[3] L.J. Fogel et al. Artificial Intelligence Through
Simulated Evolution. John Wiley & Sons, N.Y., 1966.
[4] J.W. Atmar. Speculation on the Evolution of
Intelligence and Its Possible Realization in Machine
Form. D.Sc. Dissertation, New Mexico State
University, 1976.
[5] H.J. Bremmerman. "Optimization through evolution
and recombination," in M.C. Yovits et al. (eds.),
Self-organizing Systems. Spartan Books,
Washington, D.C., 1962.
[6] S. Wright. "The roles of mutation, inbreeding,
crossbreeding, and selection in evolution," Proc.
6th Int. Cong. Genetics, Ithaca, vol. 1,
pp. 356-366, 1932.
[7] R.C. Lewontin. The Genetic Basis of Evolutionary
Change. Columbia University Press, N.Y, 1974.
[8] P.C. Hanawalt et al. "DNA repair in bacteria and
mammalian cells," A. Rev. Biochem., vol. 48,
pp. 783-836, 1979.
[9] B. Lewin. Genes III. John Wiley & Sons, N.Y., 1987.
[10] E.C. Friedberg and Hanawalt, P.C. (eds.) Mechanisms
and Consequences of DNA Damage Processing.
Alan R. Liss, N.Y., 1989.
[11] G.G. Simpson. The Geography of Evolution. Chilton, Philadelphia, 1965.
[12] D.M. Raup. "Taxonomic diversity during the Phanerozoic," Science, vol 177, pp. 1065-1071, 1972.
[13] E.O. Wilson and D.S. Simberloff. "Experimental zoogeography of islands. Defaunation and monitoring techniques," Ecology, vol. 50, pp. 267-277, 1969.
[14] E.C. Pielou. Ecological Diversity. Wiley-Interscience, N.Y., 1975.
|