Research Bibliographies, Page 2

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

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

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

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).

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).

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.

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.)

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

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.

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.

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.

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).

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).

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

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

(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).

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.

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.

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.

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.

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

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.

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

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.

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.

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.

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.

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.