# Research Bibliographies, Page 2

This bibliography is like a glimpse into the past, an artefact of my time with BT’s Complex Systems Laboratory. Originally intended for internal use within a research group and later made available to the public, the bibliography has not been actively maintained since 2000.

## Evolutionary Algorithms

### Genetic & Evolutionary Algorithms (General)

Bäck, T., ed. (1997) *Proceedings of the Seventh International Conference on Genetic Algorithms*. San Mateo: Morgan Kaufmann.

Baker, J. E. (1987) ‘Reducing Bias and Inefficiency in the Selection Algorithm’, in Grefenstette (1987), pp. 14-21.

Introduces stochastic sampling with replacement (a.k.a. ‘roulette wheel’ selection).

Belew, R.K. and L.B. Booker, eds. (1991) *Proceedings of the Fourth International Conference on Genetic Algorithms*. San Mateo: Morgan Kaufmann.

Many high quality papers, including some listed in subsection on landscapes, schemata, etc.

Booker, L. (1987) ‘Improving Search in Genetic Algorithms’, in Davis (1987), pp. 61-73.

Introduces 2-point recombination operator which ensures that recombination focuses search attention on subspaces where two parents are not in agreement.

Davis, L., ed. (1987) *Genetic Algorithms and Simulated Annealing*. San Mateo: Morgan Kauffmann.

Goldberg, D.E. (1989a) *Genetic Algorithms in Search, Optimization & Machine Learning*. Reading, MA: Addison-Wesley.

This is the definitive text on genetic algorithms, and rightly so. Exceptionally well written and clear, the book begins with “A Gentle Introduction to Genetic Algorithms” and continues step by step through advanced operators, genetics-based machine learning, and applications. Includes appendices with sample code and a review of combinatorics and probability theory. Much easier to follow than Holland (1975).

Grefenstette, J.J., ed. (1987) *Proceedings of the Second International Conference on Genetic Algorithms and their Application*. Hillsdale, New Jersey: Lawrence Erlbaum Associates.

Holland, J.H. (1975/1992) *Adaptation in Natural and Artificial Systems*. 1975 edition Ann Arbor: University of Michigan Press. 1992 edition London: MIT Press.

For practical purposes, this is where the GA business all started. In fact, Holland had earlier publications about genetic algorithms, and this book is itself much broader than just GAs, but nonetheless this is what really set the foundations for the field of genetic algorithms research. Note that this is not for the fainthearted: heavy formalism (which is clear but somewhat eclectic) requires lots of effort. A more easily digested treatment of the GA-specific materials appears in Goldberg (1989a).

Ochoa, G.; I. Harvey, H. Buxton (1999) ‘Error Thresholds and Their Relation to Optimal Mutation Rates’, in Floreano et al. (1999), pp. 54-63.

Explores correlation between evolutionary algorithm notion of optimal mutation rate and the error threshold of molecular biology. Unsurprisingly, there is a correlation. Surprisingly, despite references to both Eigen and Schuster, authors do not discuss Eigen’s (1992) analysis of Schuster and Swetina’s 1982 computer simulation (J. Swetina and P. Schuster, ‘Self-replication with error — a model for polynucleotide replication, *Biophys. Chem.* 16, p. 329) and his explanation of why the error threshold provides the best conditions for evolution. See molecular biology vignette 10 of Eigen (1992). For a sophisticated discussion of the same topic, but in much greater depth, see chapter 11 — called ‘Adaptive Learning at the Error Threshold’ — of Adami’s (1998) book *Introduction to Artificial Life*.

Rechsteiner, A. and M.A. Bedau (1999) ‘A Generic Neutral Model for Quantitative Comparison of Genotypic Evolutionary Activity’, in Floreano et al. (1999), pp. 109-18.

This interesting but somewhat puzzling article introduces a generic approach to ‘neutral modelling’ which is intended to provide baseline information about the extent of a population’s neutral evolutionary activity, allowing it to be discounted in analyses of a population’s specifically *adaptive* activity. The authors use ‘activity’ in a unique way, defining it as the mean time for which a given genotype has been expressed in a population. It’s altogether possible that I’ve misunderstood significant parts of the article, but two immediate puzzles seemed to arise. The first and less significant is the question of why we should expect similar activity statistics through different neutral runs, given that population sizes are finite. At a glance, one would expect different neutral runs to differ significantly and with a notably larger standard deviation than that reported in the authors’ results. This in itself is not too worrisome, but a second puzzle seems on the face of it much more damning of the entire project. The authors suggest (p. 110) that their special definition of ‘activity’ reflects the intuitive notion of the degree of adaptive structure present within a system. Yet clearly at high rates of evolutionary innovation (which the authors equate with evolutionary ‘intensity’, a quantity which is not, contra the authors, statistically independent of ‘activity’), the ‘activity’ will suffer as less adaptive variants are weeded out of the population. In other words, a *moving* quasi-species, or mutant distribution, may well be adding ‘adaptive structure’ while destroying ‘activity’. If anything, ‘activity’ would appear to correspond to evolutionary stagnation. The problem might be ameliorated, and the whole effort brought into contact with standard population genetics, if attention were paid to the fixation of *alleles* rather than entire genotypes, but the authors make no mention of such a modification.

The problem compromises the conclusion the authors attempt to draw to the effect that their results “confirm the appropriateness of using activity statistics to measure the extent of adaptive structure in an evolving system, thereby confirming the appropriateness of using neutral model activity to measure the amount of activity that can be attributed to adaptation as opposed to other evolutionary forces” (p. 117): the conclusion is compromised precisely because ‘activity’ appears to be a sufficient but by no means necessary indicator of adaptive structure. This is perhaps masked somewhat in the current article specifically because of the use of genotypes with only 4 or 14 loci. (In the degenerate case of 1 locus, the method reduces to an allele-based analysis as suggested above, while with increasing number of loci, the method diverges from the suggestion above.)

Schaffer, J.D., ed. (1989) *Proceedings of the Third International Conference on Genetic Algorithms*. San Mateo: Morgan Kaufmann.

Taylor, T. (1999) ‘On Self-Reproduction and Evolvability’, in Floreano, et al. (1999), pp. 94-103.

Discussion of Tierra in the context of von Neumann’s architecture for self-reproducing machines. Interesting discussion but with limited conclusions.

Whitley, D. (1989) ‘The GENITOR Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best’, in Schaffer (1989), pp. 161-121.

One of the first papers advocating rank-based selection in GAs as a technique for specifically *reducing* the amount of information returned from the environment via the evaluation function. Nicely argued with respect to Holland’s schema theorem and includes positive, if mixed, empirical results for algorithm using ranking and one-at-a-time reproduction.

### Landscapes, Schemata, etc.

Forrest, S. and M. Mitchell (1993) ‘Relative Building-Block Fitness and the Building-Block Hypothesis’, in D. Whitley (ed.) *Foundations of Genetic Algorithms 2*, pp. 109-126.

Article introduces ‘Royal Road’ functions as a simple tool for exploring questions about schema processing by GAs and shows that ‘hitch-hiking’ effects, whereby less fit schemata may hitch-hike on genotypes of overall high fitness, can severely impact the effectiveness of GA search by causing a particular form of premature convergence. Such effects impact the ability of the GA to create intermediate-order schemata through the recombination of fit low-order schemata. The problem may occur whenever the GA population is searching simultaneously for two or more non-overlapping high fitness schemata. (Note also that the introduction of introns does not appear to help significantly.) Authors show, moreover, that a simple ‘random mutation hill climbing’ algorithm significantly outperforms the GA on simple examples of Royal Road functions.

Levenick, J.R. (1991) ‘Inserting Introns Improves Genetic Algorithm Success Rate: Taking a Cue from Biology’, in Belew and Booker (1991), pp. 123-27.

Presents evidence that insertion of introns between gene segments can improve GA success by around ten-fold, arguing that this is explained by the fact that non-functional introns increase the number of available non-disruptive crossover points (i.e., crossover points which do not break up genes). Unfortunately, the author makes no connections with the literature on neutrality or epistasis.

Lipsitch, M. (1991) ‘Adaptation on Rugged Landscapes Generated by Iterated Local Interactions of Neighboring Genes’, in Belew and Booker (1991), pp. 128-35.

Author studied fitness landscapes generated by a CA-based developmental process, wherein an elementary (1-dimensional, with update rules expressed in terms of states of current cell and two adjacent cells) CA generated a phenotype string from the genotype seed and the phenotype fitness was based on its Hamming proximity to a target sequence. Author used a 30-bit genome and studied all 256 possible CA rules, using the CA rule classifications provided by Li and Packard (‘Technical Report CCSR-89-8, Center for Complex Systems Research, University of Illinois at Urbana-Champaign, 1989), which categorise CA rules in terms of their dynamics — fixed point, nonhomogeneous fixed point, periodic attractor, ‘locally chaotic’ (areas of fixed or periodic behaviour separated by ‘chaos’), and ‘chaotic’ (cycle length diverges exponentially with increased lattice length). (Note that this is a very bad use of the word ‘chaos’, since *all* finite CA dynamics must either go to a limit cycle or a fixed point; the use of ‘chaos’ here just links the length of limit cycles to the growth in the number of available lattice states.) Using two measures of landscape correlation (correlation length and correlation coefficient) to categorise landscapes, author discovered that chaotic rules generate tough landscapes (short mean walk length to local optima, low values for both correlation functions), yet locally chaotic rules had by far the longest mean walk length to local optima of any rule class, with correlation measures in line with those for rules with nonhomogeneous fixed points or periodic attractors. The upshot is that locally chaotic landscapes produced the highest performance for adapting populations and the lowest standard deviation in performance of any of the four CA rule classes of interest. Author concluded that the type of bounded exploration afforded by a locally chaotic development process is very efficient. Separately, author uncovered cases in which performance differed depending on target string, despite the fact that the landscapes in question shared the same correlation lengths, the same nature of epistasis, and a similar adaptive ‘task’; on this basis, author concluded that these measures (correlation, etc.) alone are insufficient predictors of GA performance. This is a very impressive paper — all the more so because it resulted from work undertaken during an undergraduate internship at SFI. Interesting to read in conjunction with Manderick, et al (1991).

Manderick, B.; M. de Weger, and P. Spiessens (1991) ‘The Genetic Algorithm and the Structure of the Fitness Landscape’, in Belew and Booker (1991), pp. 143-50.

Applies three statistical tools to the analysis of fitness landscapes: autocorrelation function (correlation of fitnesses of points as a function of their Hamming separation), correlation length (maximum Hamming distance from a point which still preserves information about the fitness of that point), and fitness correlation coefficients of the genetic operators (correlation at the distance created between parent and offspring via the application of a given operator; i.e., the correlation of the landscape as it ‘appears’ to the operator). Authors analyse NK-landscapes and the Travelling Salesman Problem, showing that the correlation coefficients provide a way to assess and tune the GA. Article shows that beyond the correlation length of the fitness landscape, GA exploration reduces to random search. (Note the method for actually calculating the coefficients depends on the assumption of an isotropic landscape, where any random walk displays the same statistics.) This is a very interesting paper, and useful to read in conjunction with Lipsitch (1991).

Stephens, C. and H. Waelbroeck (1997) ‘Effective Degrees of Freedom in Genetic Algorithms and the Block Hypothesis’, in Bäck (1997), pp. 34-41.

Introduces notions of effective degrees of freedom and effective fitness discussed more fully in Stephens and Waelbroeck (1999).

Stephens, C. and H. Waelbroeck (1998) ‘Analysis of the Effective Degrees of Freedom in Genetic Algorithms’, *Physical Review* D57: 3251-64.

More on effective degrees of freedom and effective fitness, discussed more fully in Stephens and Waelbroeck (1999).

Stephens, C. and H. Waelbroeck (1999) ‘Schemata Evolution and Building Blocks’, *Evolutionary Computation* 7(2): 109-24.

(Warning: I don’t think I fully understand this paper yet…!) Appealing to notions of *effective fitness *(Stephens and Waelbroeck 1997, 1998) and *effective degrees of freedom* (EDOF), derives a new schema theorem according to which schemata of higher than average effective fitness receive exponentially increasing number of trials over time. (For the original theorem, see Holland 1975 or Goldberg 1989a.) EDOF reflects the structure of the GA search space (quantifying the notion that GA search is not merely a random exhaustive search but a constrained one), while effective fitness reflects the notion that, given the particular genetic operators at work, otherwise fitness-equivalent schemata may have different probabilities of producing fit descendants. As they put it, “…genetic operators can radically change the effective landscape in which the population evolves. The actual bare landscape associated purely with selection offers little intuition as to the true population evolution. Real populations can flow rapidly along flat directions and strings may be present even if they have zero fitness. To take this into account we propose using an *effective* fitness function” (p. 116, emphasis original). It is unclear, however, whether this extension of the notion of fitness simply revisits a long-running debate within biology as to how fitness itself should be defined, with the authors siding with the view that fitness must reflect long-term, ‘trans-generational’ reproductive success. Significantly, authors show that in the general case, *there is no preference* for short ‘building blocks’. Indeed, the reconstructive effects of crossover dominate the destructive effects specifically when the probability of selecting parts of a given schema exceeds that of selecting the whole schema. In this case, *longer* rather than shorter schema are favoured (p. 120): “…crossover plays an important role in allowing both parts of a successful schema to appear in the same individual. The effect of crossover is to…make it easier to find the whole schema” (p. 120).

Vose, M.D. and G.E. Liepins (1991) ‘Schema Disruption’, in Belew and Booker (1991), pp. 237-42.

This fascinating article generalises the notion of a schema to that of an arbitrary set of strings called a predicate and offers a generalisation of the usual building block hypothesis in terms of predicates. Authors convincingly demonstrate that it is the relationship between predicates and the crossover operator which determines what the building blocks are. In the case of ordinary crossover, Holland schema are at work, but in the cases of other possible varieties of crossover, the building blocks might actually be different from the usual notion. Authors also note that for an injective fitness function over a finite domain, there always exists some representation of the space which makes GA optimization essentially the problem of counting the 1’s in the genome.

### Multiploidy in GAs

Also see sections on multiploidy and on speed of evolution under evolutionary theory.

Bidwell, G.L. (1996) *Applying Diploidy and Dominance to Artificial Genetic Search*. Master of Science thesis in computer science, University of Montana.

Although the code supporting some of the empirical results of the thesis has reportedly been found to contain bugs which may compromise those results, the thesis contains an excellent overview of the topic and an extensive multiallelic viability selection model, based on the population genetics of Hartl and Clark (1989), which I am unfortunately not qualified to evaluate.

Calabretta, R.; R. Galbiati, S. Nolfi and D. Parisi (1996) ‘Two is better than one: A dyploid genotype for neural networks’, *Neural Processing Letters* 4: 149-155. (available online)

Although simulations do not use crossover, an interesting fixed dominance mask allowing for incomplete dominance showed slightly better *peak* performance than a haploid algorithm, particularly on non-stationary problems. Main conclusion is that diploidy enhances variability and ‘buffers’ environmental change. Data also show that *average *fitness is lower in diploids than haploids, perhaps because mutations affect diploids more severely when modifier genes (lacking in haploids) are hit. Generally speaking, distribution of fitness values tends to be bimodal in diploids and unimodal in haploids.

Collingwood, E.; D. Corne and P. Ross (1996) ‘Useful Diversity via Multiploidy’, in* Proceedings of the IEEE International Conference on Evolutionary Computing 1996*, pp. ??. (available online)

Suggests multiploidy “appears useful in cases where attractive suboptima are profoundly Hamming distant from the true optimum” (p. 1) and “*Multiploidy appears useful in precisely those cases where useful genetic material may othewise be irretrievably lost*” (p. 5, emphasis original). Argues convincingly that multiploidy is sometimes valuable but sometimes detrimental, depending on circumstances. Empirical results employ fixed dominance mask (i.e., dominance is not determined by alleles themselves, but by mask applied to chromosomes) and stationary problems.

Corne, D.; E. Collingwood and P. Ross (1996) ‘Investigating Multiploidy’s Niche’, in *Proceedings of AISB Workshop on Evolutionary Computing 1996*, pp. ??. (available online)

Results with fixed dominance mask and multiple knapsack problem reinforce suggestion of Collingwood, et al (1996).

Goldberg, D.E. (1989b) ‘Advanced Operators and Techniques in Genetic Search’, Chapter 5 of Goldberg (1989a), pp. 147-215.

First section of chapter provides a thorough discussion of GA-aspects of diploidy and dominance, including an analysis of the effect of dominance mechanisms in light of the schema theorem.

Goldberg, D.E. and M. Rudnick (1991) ‘Genetic Algorithms and the Variance of Fitness’, *Complex System*s 5: 265-78.

Goldberg, D.E. and R.E. Smith (1987) ‘Nonstationary Function Optimization Using Genetic Algorithms with Dominance and Diploidy’, *Proceedings of the Second International Conference on Genetic Algorithms*, pp. 59-68.

See Smith and Goldberg (1992) for a newer and broader treatment of these results.

Lewis, J. (1997) A Comparative Study of Diploid and Haploid Binary Genetic Algorithms. Master’s thesis in Artificial Intelligence, University of Edinburgh.

Lewis, J.; E. Hart and G. Ritchie (1998) ‘A Comparison of Dominance Mechanisms and Simple Mutation on Non-Stationary Problems’, in *Proceedings of Parallel Problem Solving from Nature: PPSN IV*, pp. ??. Springer-Verlag. (available online)

Suggests that diploid representation is not enough, by itself, to allow flexible population response to change; also need some mechanism for dominance change. Authors use variations on Ng and Wong (1995) and Ryan (1996) dominance mechanisms with non-stationary problems and also show that a haploid algorithm which applies a very high mutation rate to any individuals with a sudden drop in fitness also performs well. These very artificial mechanisms are essentially techniques for boosting variability in response to environmental changes which select against existing genes represented in the population.

Ng, K.P. and K.C. Wong (1995) ‘A New Diploid Scheme and Dominance Change Mechanism for Nonstationary Function Optimization’, in *Proceedings of the Sixth International Conference on Genetic Algorithms*, pp. 159-167.

Dominance change mechanism for diploid representation, seemingly removed from biological reality, which inverts dominance values of all allele pairs for a particular population member when the fitness of that individual drops by a particular percentage between successive evaluation cycles. This dominance change mechanism *does* manage to realise some of the benefits which diploidy has been speculated to offer. Article shows that many previous attempts at diploidy, including triallelic scheme which Goldberg and Smith (1987) borrowed from Hollstein’s 1971 work (also see Smith and Goldberg 1992), do not work well in the general case for improving adaptation to changing environments. (Shows that Goldberg and Smith’s success is a strictly isolated example.) Population genetics arguments, as well as simulations, back up their arguments very convincingly.

Ryan, C. (1996) ‘The Degree of Oneness’, in *Proceedings of the ECAI Workshop on Genetic Algorithms 1996*, pp. ??. Springer-Verlag.

Unfortunately, although I have definitely found it cited, I can neither find this paper nor verify the details of the citation — nor can the British Library! The author’s web pages include only a broken link, and the author has not replied to email requests for the paper. (I would imagine the author has probably changed institutions, and I have not yet caught up with his current whereabouts.) Apparently this paper introduced ‘additive dominance’ for diploid representations, where dominance is calculated via a pseudo ‘addition’ operator over allele values. Extended by Lewis et al. (1998) to accomodate dominance change.

Smith, R.E. and D.E. Goldberg (1992) ‘Diploidy and Dominance in Artificial Genetic Search’, *Complex Systems* 6: 251-85.

Analytical and empirical treatment of the application of diploidy and dominance relationships in GAs, with emphasis on nonstationary search. Considers recessivity as a mechanism for maintaining a probabilistic memory of phylogenetically earlier environmental conditions. Analytical and qualitative results retain their usefulness, but unfortunately the generality of much of the experimental work (largely based on Goldberg and Smith 1987) has been convincingly questioned by Ng and Wong (1995). Includes curious comments near end (pp. 281-282) on interpreting schema fitness samples as subject to nonstationary ‘collateral noise’ (Goldberg and Rudnick 1991) which *appears* to be thoroughly unremarkable, *unless* one begins with a misinterpretation of the schema theorem. Authors suggest that GA selection of building blocks is “clearly noisy since schema average fitness values vary from sample to sample, and thus from population to population” (p. 281). Yet it is *not* the schema average fitness values which vary, but the *samples* of schema fitness values. It is *entirely* to be expected that the fitness of a given point on a hyperplane may vary from the average fitness of all points across that hyperplane; thus it would be incorrect to interpret the schema theorem as suggesting that a *specific* GA gives exponentially growing representation to schemata with higher average fitnesses. *It need not*. It gives exponentially growing representation to schemata with higher *sampled* fitnesses. On this interpretation of the schema theorem, ‘collateral noise’ seems unremarkable.

Yoshida, Y. and N. Adachi (1994) ‘A Diploid Genetic Algorithm for Preserving Population Diversity — pseudo-Meiosis GA’, in *Parallel Problem Solving from Nature: PPSN III*, pp. 36-45. Springer-Verlag.

Definitely *not* a remotely biologically-plausible rendition of meiosis, but very interesting for its seeming ability to control the character of local searches performed around the ‘assistant chromosome’. Cluster analysis shows that populations group into clusters in chromosome space, with clusters grouped around better individuals.

## Sections Available

This article was originally published by Dr Greg Mulhauser on .

on and was last reviewed or updated by