Research Bibliographies
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 public, the bibliography has not been actively maintained since 2000. Nonetheless, I have kept it here for what value it may have for those involved in research in these areas.
Also available: bibliography from Mind Out of Matter.
Artificial Life (General)
Funny to have such a short section here, considering my work is supposed to be primarily artificial life! Please see the other sections for finer characterisations of parts of the field. This category is reserved just for collections, introductions & that sort of thing.
Adami, C. (1998) Introduction to Artificial Life. New York: Springer-Verlag.
This is an outstanding book, particularly for those with an interest in information theoretic or thermodynamic approaches to problems in evolutionary systems. Despite its unsurprising focus on avida, the book remains an excellent introduction to broader issues in artificial life. And despite being called an 'introduction', much of the material here is very recent and will be of interest to most professional researchers in the field.
Floreano, D.; J-D. Nicoud, F. Mondada, eds. (1999) Advances in Artificial Life: Lecture Notes in Artificial Intelligence 1674. New York: Springer-Verlag.
This is the proceedings volume for the European Conference on Artificial Life 1999, held at EPFL.
Cognitive Science & Psychology
Like several other sections, it seems bizarre to include a tiny little section on cognitive science when my previous work was so wrapped up with the field! But nonetheless, here it is...
Karmiloff-Smith, A. (1992) Beyond Modularity: A Developmental Perspective on Cognitive Science. Cambridge, Massachusetts: MIT Press.
This book, which introduced the ideas of representational redescription, is still on my list! Notes to follow...
Snyder, A.W. and D.J. Mitchell (1999) 'Is integer arithmetic fundamental to mental processing?: The mind's secret arithmetic', Proceedings of the Royal Society of London B 266: 587-92.
Argues that the remarkable abilities of autistic savants are due to an abnormal ability to access low level levels of neural processing which are present in 'normal' individuals but not normally available to introspection. I.e., the neural circuitry responsible for lightning fast mental arithmetic, perfect pitch, artistic ability, and other special savant capabilities may well be present in all normal brains but simply inaccessible. Authors leave open the question of why the brain should be so adept at integer arithmetic, equipartitioning, and similar feats.
Psychobiology & Psychopharmacology
From the standpoint of computational substrates, it's interesting to consider the relationship between underlying neural functioning and psychopathologies such as depression.
Owens, M.J. and C.B. Nemeroff (1994) 'Role of Serotonin in the Pathophysiology of Depression: Focus on the Serotonin Transporter', Clinical Chemistry 40(2): 288-95.
Review of evidence on the role of inhibitory neurotransmitter 5-hydroxytryptamine -- 5-HT, or serotonin -- and its relevance to depression. Notable results include experimental evidence that a special diet deficient in tryptophan (the central metabolic precursor of 5-HT) and high in neutral amino acids which compete with existing tryptophan for carrier-mediated brain uptake, precipitated a rapid relapse in depressed patients within hours of ingestion. (Who volunteers for these things??) Also discusses, from the transport point of view, the effect of selective reuptake inhibitors in increasing serotonergic neurotransmission and the effect of some amphetamine derivatives, including 3,4-methylene-dioxymethamphetamine (MDMA, or 'ecstasy'), in creating a large wash of synaptic 5-HT. Also notes that 5-HT transporter mRNA has been observed in areas altogether devoid of serotonergic perikarya as well as the finding that this mRNA expression can apparently be controlled by both nonselective and selective reuptake inhibitors. Interestingly, much of the work on 5-HT transporters is actually performed on platelets, which apparently have identical 5-HT transporter sequences.
Nemeroff, C.B. (1996) 'The corticotropin-releasing factor (CRF) hypothesis of depression: new findings and new directions', Molecular Psychiatry 1: 336-42.
Excellent review article on CRF and hyperactivity of the HPA axis. Particularly notable results include notion that elevated CRF levels not only stimulate the HPA axis but also act on extra-pituitary brain sites. Also, evidence suggests that undue stress early in an organism's life may sensitise CRF neurons, and paraventricular nucleus (PVN) hypothalamic tissue in particular, leading to CRF hypersecretion in response to stresses later in life. This appears linked to an increase in CRF mRNA expression. Selective serotonin reuptake inhibitors appear remarkably effective in normalising ACTH and corticosterone responses to stress, as well as normalising mRNA expression in the PVN and other areas.
Nemeroff, C.B. (1998) 'The Neurobiology of Depression', Scientific American 278(6): 28-35.
Excellent review article describing the chemical pathways implicated in depression, ranging from norepinephrine and other monoamines, to serotonin (produced in neurons projecting from the raphe nuclei to many areas, including those which affect the release of norepinephrine), to hormonal disturbances in the HPA (hypothalamic-pituitary-adrenal) axis and the stress-diathesis model, which predicts that early childhood stress can permanently increase CRF gene expression. For more details, see Owens and Nemeroff (1994) and Nemeroff (1996).
Cryptography and Cryptanalysis
Bennett, C.H.; G. Brassard and A.K. Ekert (1992) 'Quantum Cryptography', Scientific American 267(4): 26-33.
Very straightforward survey of quantum key distribution techniques based on the pioneering work of Bennett and Brassard, recently (1989) demonstrated in a working device at IBM's Thomas J. Watson Research Center. Additional comments on Ekert's work and also on the use of similar methods for discreet public decision making based on securely held private data.
Shamir, A. (1999) 'Factoring Large Numbers with the TWINKLE Device', extended abstract, Dept. of Applied Mathematics, The Weizmann Institute of Science. (email author)
Describes a fascinating and ingenious GaAs-based ultra-fast optical implementation of the sieving process used in the QS (Quadratic Sieve) and NFS (Number Field Sieve) algorithms for attacking product of primes style public-key cryptography systems such as RSA. The author suggests the relatively inexpensive device could improve the efficiency of the NFS algorithm by two to three orders of magnitude, increasing the size of factorable numbers by 100 to 200 bits. "The main practical significance of such an improvement is that it can make 512 bit numbers...[used in many e-commerce applications]...easy to crack" (p. 2).
Dynamics and Self-Organisation
Also see the section on neural networks and that on Benford's Law under Information Theory.
Bak, P.; C. Tang and K. Wiesenfeld (1988) 'Self-Organized Criticality', Physical Review A 38(1): 364-74.
This and a short 1987 account by the same authors (Physical Review Letters 59: 381) are the original sources for the phrase 'self-organised criticality'. Despite a great deal of hype which later accreted around the phrase, this original article is rigorous and free of hyperbole, offering an account intended to link nonlinear dynamics, the appearance of scale-invariant spatial self-similarity (i.e., fractal structure), and 1/f noise, or 'flicker noise' in a robust way. The essential dynamical property of the systems considered is the presence of many metastable states.
Garfinkel, A. (1987) 'The Slime Mold Dictyostelium as a Model of Self-Organization in Social Systems', in Yates (1987), pp. 181-212.
Fascinating account of aggregation in slime mold Dictyostelium, which self-organises from single-celled amoebae into multicellular colony, which then undergoes cellular differentiation and moves as a whole over macroscopic distances. (For the full story on slime molds, see Loomis 1975.) The paper describes and critiques various attempts to model the self-organising behaviour of Dictyostelium using field models and individual cell models, neither of which have been particularly successful. Includes interesting comments on the crucial role of entrainment in self-organisation (both in terms of frequency and in terms of phase -- the latter also being known as 'phase locking', or 'synchronisation), including some architectural preconditions for entrainment to occur (p. 195, for instance). (See Winfree 1980 for discussion of biological phase entrainment examples and Glass and Mackey 1979 for a simplified model of phase locking entrainment under the action of a sinusoidal stimulus.) This is an incredibly interesting account of self-organisation; latter parts of the paper, extrapolating to the emergence of social structures, are somewhat less rigorous.
Glass, L. and M.C. Mackey (1979) 'A simple model for phase-locking of biological oscillators', Journal of Mathematical Biology 7: 339-52.
Simple model of biological phase entrainment due to sinusoidal stimulus.
Loomis, W. (1975) Dictyostelium discoideum: A Developmental System. New York: Academic Press.
Background on slime mold with amazing life cycle summarised & analysed in Garfinkel (1987).
Winfree, A. (1980) The Geometry of Biological Time. Berlin: Springer-Verlag.
Discussion of phase entrainment in cricket chirping, firefly flashing, glycolitic oscillation in yeast cells, and eclosion cycle coherence in insect populations mentioned in Garfinkel (1987).
Yates, F.E., ed. (1987) Self-Organising Systems: The Emergence of Order. London: Plenum Press.
This collective volume brings together several early perspectives on self-organisation from physicists, biologists, chemists, and others.
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. (email supervisor, Alden H. Wright)
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 Systems 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.
Evolutionary Theory
Epistasis
Baatz, M. (1998) 'Pleiotropy and the Evolution of Adaptability', in Van de Vijver, et al. (1998), pp. 101-12.
Very interesting model of an evolvable epigenetic modifier system modulating pleiotropic and polygenic effects. This one merits a closer look than I've given it so far.
Cheverud, J. and E. Routman (1995) 'Epistasis and its contribution to genetic variance components', Genetics 130: 1455-61.
Principle point of interest for me is distinction between physiological and statistical views of dominance and epistasis. Physiological dominance is deviation of heterozygote phenotype value from average of the two homozygote phenotype values at one locus, while statistical dominance is taken as deviation from the linear model (deviation of single locus values from linear regression of composing alleles to genotypic values) and is dependent on genotype frequencies in the population.
Wagner, G.P.; M.D. Laubichler, and H. Bagheri-Chaichian (1998) 'Genetic measurement theory of epistatic effects', Genetica 102/103: 569-80. (available online)
Offers new approach to scaling of epistasis which is argued to be superior to normal treatment in population genetics, where epistasis "is often represented as a mere noise term in an additive model of gene effects" (p. 569). Includes a useful section on dominance, which begins with the distinction between the physiological and the statistical interpretation of dominance (noted, along with the analogous distinction between physiological and statistical interpretations of epistasis, by Cheverud and Routman1995).
General
Eigen, M. (1992) Steps Towards Life: A Perspective on Evolution. Oxford: Oxford University Press.
This is an excellent but regrettably brief book from one of the best authorities in the field. It's organised into a series of 'vignettes' on theoretical issues and the details of areas of molecular biology.
Fisher, R.A. (1958) The Genetical Theory of Natural Selection, revised 2nd edn. New York: Dover Publications. (First edition published in 1929.)
One of the classics of modern evolutionary theory, this book covers areas from variation, sexual selection, and the evolution of dominance (this is the place to go for Fisher's original position on the evolution of modifiers) to human society and social selection. There's far too much here to cover in the time this popular book is available on interlibrary loan, so a better look will have to wait for a purchased copy.
Morowitz, H.J. (1968) Energy Flow in Biology: Biological Organization as a Problem in Thermal Physics. London: Academic Press.
Broad early account applying, as the title suggests, principles of thermal physics to problems in biology. Introduces and justifies several important ideas, such as that energy flow alone can give rise to order in a system and that such order can only be maintained, once it arises, by continued energy flow. Includes an interesting but somewhat dated chapter on order, information and entropy.
Steele, E.J.; R.A. Lindley, R.V. Blanden, P. Davies (1998) Lamarck's Signature: How Retrogenes are Changing Darwin's Natural Selection Paradigm. Reading, Massachusetts: Perseus Books.
Evidence from the field of somatic hypermutation now strongly suggests that the so-called Weismann Barrier may be selectively permeable: information may flow from somatic to germline cells. More notes on this one to follow...
Stentiford, S. (to appear) 'Evolution: The Best Possible Search Algorithm?', to appear in Millenium Edition of the BT Technical Journal.
The question posed in the title does not find an answer in the article, although the author's general predilection is definitely toward the affirmative. The article is principally a review of selected elements of Darwinism and basic molecular genetics, with some comments toward the end about evolution-inspired computer methods.
Life Histories
Stearns, S.C. (1992) The Evolution of Life Histories. Oxford: Oxford University Press.
This is an introductory text for life histories theory, with one half covering the basic elements of explanations of life history variation -- demography, quantitative genetics, trade-offs, and lineage-specific effects -- and the other covering the application of these to major life history traits -- age and size at maturity, number and size of offspring, and reproductive lifespan and ageing. While certain areas are deliberately not covered (sex allocation theory, complex life histories, modular organisms, frequency-dependent life histories, etc.), the book nonetheless provides a very broad look at the field for anyone trying to understand the evolution of life history traits.
Multiploidy
Also see sections on epistasis, on sex, and on speed of evolution, as well as section on multiploidy in GAs.
Kacser, H. and J.A. Burns (1981) 'The molecular basis of dominance', Genetics 97: 639-66.
Important theoretical account of dominance in terms of the kinetics of enzyme systems. Notes on this one to follow.
Kettlewell, H.B.D. (1955) 'Selection experiments on industrial melanism in Lepidoptera', Heredity 9: 323-42.
As far as I'm aware, this is the earliest original sources for the celebrated example of the peppered moth Biston betularia, whose rapid colour change in response to nineteenth century British industrial pollution occurred as a result of a dominance change in a single gene controlling wing colouration. The change from white wings with small black spots to black wings was not the result of a fortuitous mutation for black wings, but of the re-emergence of a previously evolved solution 'stored' as a recessive allele. Also see Kettlewell (1961).
Kettlewell, H.B.D. (1961) 'The Phenomenon of Industrial Melanism in the Lepidoptera', Annual Review of Entomology 6: 245-62.
Lewis, J. and L. Wolpert (1979) 'Diploidy, Evolution and Sex', Journal of Theoretical Biology 78: 425-38.
Excellent article contrasting the two paths by which haploid and diploid species may create a new gene for a new purpose through the mutation of an existing gene. Assuming that the new gene will be created on a duplicate of the old gene (since mutations which turn an existing functional gene into a new dual-purpose functional gene are rare), an important difference arises between the two cases: haploids must duplicate the original gene first and then mutate it, while the diploid can mutate an existing copy of the gene and duplicate it later during recombination. Thus, "an additional gene for a new purpose can become fixed in a haploid population only after a happy coincidence of two rare chances [duplication then mutation]; whereas in a diploid species the gene can become fixed by a two-step process, in which the two rare chances have merely to occur in sequence [mutation, then later duplication]" (p. 426). The authors observe further that "mutations which are forbidden as lethals in the haploid may be tolerated as recessive lethals in the diploid" (p. 426). The upshot is that diploids can enlarge their genomes much more easily than haploids. Later, "mutations preserved in balanced polymorphism act as a driving force for enlargement of the genome; through recombination, they lend their heterotic selective advantage to any duplication that may arise, and tend to carry it to fixation" (pp. 431-32).
Near the end of the article (pp. 432-33), the authors offer a fascinating line of reasoning about the different evolutionary pathways available to haploids and diploids with respect to gene control networks--such as may play an important rôle in the development of multicellular organisation. Consider a particular example where a need arises to control a gene H via an adjacent control locus L via the binding of a protein P (i.e., where the presence of such control would confer a selective advantage). They observe that there are two basic strategies: 1) evolve the original locus L0 adjacent to H so it will bind P or 2) mutate an original P0 so as to bind to locus L. The haploid will be best suited for option 1. For the diploid, however, option 2 will be available: there is already a copy of the gene responsible for P0 which can be mutated to create P without disrupting the existing function of P0. A heterozygote carrying a new variant P will be at an advantage, with the effect of the mutant P binding to control locus L ensuring dominance. Consideration of this process suggests that "haploids and diploids will gend to evolve differently in response to selection favouring the development of this sort of control over transcription" (p. 433).
Mayo, O. and R. Bürger (1997) 'The Evolution of Dominance: A Theory Whose Time Has Passed?', Biological Reviews 72: 97-110.
This comprehensive, if somewhat compressed, review article traces the idea of the evolution of dominance from R.A. Fisher in 1928 through to the present day. One upshot is that, contra Fisher, it cannot be correct "that dominance has always arisen through the accrual by natural selection of modifiers of heterozygotes" (p. 105, emphasis original). Yet at the same time, the theory of Kacser and Burns (1981), which suggests that there is no need at all to explain the phenomenon of dominance by inferring that it has evolved, also does not fully accommodate all the evidence. In the end, the authors conclude about the range of apparently conflicting available theories that they "provide explanations at different levels of the phenotype, and as such all may be of some use" (p. 105). This is an excellent entry point for the literature, with plenty of references to other important work in the history of ideas about the evolution of dominance.
Paquin, C. and J. Adams (1983) 'Frequency of fixation of adaptive mutations is higher in evolving diploid than haploid yeast populations', Nature 302: 495-500.
Contrasts two positions on adaptive significance of diploidy: 1) greater variability and 2) capacity to mask deleterious recessive mutations. Suggests instead that adaptive significance is the capacity for faster adaptation to new environments. Despite poorly justified assumption that >50% of adaptive mutations are expressed in the heterozygous state (on the grounds that advantageous mutations should be dominant -- likely and probably true but in need of better justification than the authors provide), empirical data show a significantly higher fixation of adaptive mutations for diploids than haploids of the single-celled eukaryote Saccharomyces cerevisiae -- which has both stable haploid and diploid phases. Includes interesting background on the tracking of selectively favoured genes through the observation of the frequency of an unrelated neutral mutation, thus making it possible to track adaptive mutations without knowing their phenotypic expressions.
Soltis, D.E. and P.S. Soltis (1999) 'Polyploidy: Recurrent Formation and Genome Evolution', Trends in Ecology & Evolution 14(9): 348-52.
Review of recent work on polyploidy suggesting that most polyploid species have formed multiple times from different populations of their diploid progenitors. Subsequent hybridization between populations of different origins can be a great source of variation. Authors suggest polyploidization may be viewed as transilience, "a period during which the genome is more amenable to or tolerant of change, such as recombination" (p. 351), noting that divergent genomes within a common polyploid nucleus may be a source of stress genomic stress which may facilitate rapid evolution. Article also discusses this process of rapid and radical genomic restructing after polyploidization and the role of transposons in the evolution of gene silencing mechanisms.
Philosophical Emphasis
Dennett, D.C. (1995) Darwin's Dangerous Idea: Evolution and the Meanings of Life. London: Simon & Schuster.
Uncharacteristically wordy treatment of evolution by natural selection with a pan-adaptationist flavour. A few technical pitfalls mar what is an otherwise useful text, even if it does unwittingly rehash Schilcher and Tennant (1984) somewhat. See the 1997 Philosophical Books 38(2): 81-89 for my review of the book, with Dennett's reply pp. 89-92.
Gray, R.D. (to appear) 'Selfish genes or developmental systems? Evolution without replicators and vehicles', to appear in Singh, et al. (email author)
Extended philosophical critique of genic selectionism from the viewpoint of developmental systems theory. Apart from some comments in the last few pages partly directed at Philip Kitcher, it is unclear how seriously Gray expects practicing scientists to take the debate; it is tempting to think the arguments will attract the interest mainly of philosophers, although Gray does offer a few thoughts as to why research scientists might care as well.
Gray, R.; P. Griffiths, and S. Oyama (2000) Cycles of Contingency. Cambridge: MIT Press.
von Schilcher, F. and N. Tennant (1984) Philosophy, Evolution and Human Nature. London: Routledge & Kegan Paul.
Now looking a little dated, this book was well ahead of its time and anticipated many of the ideas later explored to good effect in Dennett (1995). Written by a biologist and a philosopher, the book is by no means of interest just to philosophers. More than one third of the book is devoted to introducing and explicating the modern theory of evolution by natural selection, and for this reason it makes a very useful introduction to the field and its theoretical terrain. The remaining three chapters after the introduction to evolution cover sociobiology, evolutionary epistemology, and the evolution of language.
Singh, R.; K. Krimbas, D. Paul and J. Beatty, eds. (to appear) Thinking about Evolution: Historical, Philosophical and Political Perspectives: Festschrift for Richard Lewontin. Cambridge: Cambridge University Press.
Sterelny, K. (2000) 'Niche Construction, Developmental Systems and the Extended Replicator', to appear in Gray, et al. (2000).
This is an outstanding example of how clear philosophical/theoretical analysis can bear usefully on scientific thinking about evolution. Sterelny outlines a set of properties characterising evolvable inheritance systems and then analyses both genetic mechanisms and environmental engineering within the context of those properties, with extra attention to the extent to which such mechanisms may be interpreted as information carriers. This is an excellent critical introduction to ideas from developmental systems theory and to ideas related to the view of genetic inheritance as information flow.
Van de Vijver, G.; S.N. Salthe and M. Delpos, eds. (1998) Evolutionary Systems. Dordrecht: Kluwer Academic.
This collection has many very promising titles, but many of the articles themselves turn out to be too short on quantitative conclusions to excite too much interest from those approaching evolutionary systems from a scientific perspective.
Population Genetics
Hartl, D.L. and A.G. Clark (1989) Principles of Population Genetics, 2nd edition. Sunderland, Massachusetts: Sinauer Associates.
Source for viability selection model which allows exploration of selection-based behaviour while avoiding complexities introduced by fitness. Appealed to in Bidwell's (1996) treatment of diploidy in GAs.
RNA Folding & Neutrality
For references on neutrality specifically in an artificial, as opposed to natural setting, please see entries under Evolutionary Algorithms.
Schuster, P. (1997) 'Landscapes and molecular evolution', Physica D 107: 351-65.
Very straightforward & easy to understand article reporting on modelling & analysis of the space of 2D RNA secondary structure (i.e., mathematically simpler pseudo-structure of folded RNA sequences) and how it relates to sequence space. Sequences folding into the same secondary structure are nearly randomly distributed in sequence space. This, combined with the fact that some 93% of the sequence space analysed folded into a set of 'common' structures -- where 'common' denotes a structure formed by more sequences than the average structure -- means that within a comparatively small Hamming radius of a given sequence, there exists on average at least one sequence for every common structure. This radius grows linearly with chain length, with a coefficient of about 1/4. Thus while the number of sequences within the radius grows exponentially with sequence length, it also shrinks exponentially as a fraction of the total sequence space. Persuasive observations on the crucial role of neutral evolution.
Wolynes, P.G. and W.A. Eaton (1999) 'The Physics of Protein Folding', Physics World 12(9): 39-44.
Discusses experimental and theoretical approaches to understanding how a single amino acid sequence can fold into myriad different 3D conformations. Particularly interesting is the description of energy landscapes, frustration, and single dominant energy funnels (for proteins which easily acquire a particular conformation) vs. complex funnels with many local minima.
Sex
Also see section on multiploidy.
Brooks, R. and M.D. Jennions (1999) 'The Dark Side of Sexual Selection', Trends in Ecology & Evolution 14(9): 336-37.
This 'News & Comment' section from TREE reviews recent work on the hidden costs of sexual selection in terms of intersexual conflict.
Crow, J.F. and M. Kimura (1965) 'Evolution in Sexual and Asexual Populations', American Naturalist 99: 439-50.
This very cleanly written article compares evolution in sexual and asexual populations vis-a-vis the rate at which favourable gene combinations can be fixed, considering the effects of gene interaction, mutation rate, population size, and magnitude of a mutation's effect. Observes that "the advantage of a reproductive system that permits free recombination is greatest for the incorporation of mutant genes with individually small effects, occurring at relatively high rates, and in large population" (p. 443). Also, "sexual reproduction can be a disadvantage if evolution progresses mainly by putting together groups of individually deleterious, but collectively beneficial mutations. ...if this type of gene action were the limiting factor in evolution at the time sexual reproduction first evolved, sexual recombination might never have been 'invented'" (p. 445). And "The type of gene that is most efficiently selected in a sexual population is one that is beneficial in combination with a large number of genes" (p. 446). On haploidy vs. diploidy, "when the population has reached equilibrium as a haploid, a change to diploidy offers an immediate advantage (Muller 1932). ...when the population reaches a new diploid equilibrium the advantage is lost. ...Thus, it is easy to see how diploidy might evolve from haploidy, even if the population did not gain any permanent benefit therefrom" (p. 448, emphasis my own). Also mentions possibility that diploidy functions to protect against effects of somatic mutation, protection which would be more important for organisms which are large and complicated.
Muller, H.J. (1932) 'Some Genetic Aspects of Sex', American Naturalist 8: 118-38.
Mentioned by Crow and Kimura (1965) as an earlier source for the idea that a change to diploidy offers an immediate advantage for a population which has reached equilibrium as a haploid.
Speed of Evolution
Also see section on multiploidy in evolution as well as section on information, complexity and entropy.
Reznick, D.N.; F.H. Shaw, F.H. Rodd, R.G. Shaw (1997) 'Evaluation of the Rate of Evolution in Natural Populations of Guppies (Poecilia reticulata)', Science 275: 1934-36.
Report on extended studies of guppy populations in Trinidad reveals a capacity for much higher rates of evolutionary adaptation than that normally inferred from the fossil record. As they put it, "sustained directional selection can support far more rapid directional change than seen in the fossil record" (p. 1936). Authors suggest that results are entirely compatible with the low rate evidenced by the fossil record because such records are effectively averages over periods which might include periods of stasis, periods of rapid change, and even periods of reversal of change. Note that differences in rate of evolution explored here are principally attributable to differences in heritabilities of the traits under selection; fastest evolution was a result of their being more genetic variation on which natural could act.
Wagner, G.P. (1981) 'Feedback selection and the evolution of modifiers', Acta Biotheoretica 30: 79-102.
Author notes that modifier theory may be viewed as "a population genetic prerequisite for an explanation of so-called major evolutionary steps" (p. 100), citing work by Frazzetta, by Rechenberg, and by Reidl in support of the view that "the evolution of complex morphological characters is only possible if the structure of the genome is currently optimized in order to allow a maximum speed of adaptation" (p. 100). Wagner suggests that 'feedback selection', a positive feedback loop between the evolution of a phenotypic character and the speed of evolution of that character, fills this rôle. Paper considers view that modifier evolution may be interpreted as a result of selection for adaptation speed in populations far from equilibrium. This 'feedback selection' occurs when the "modifying influence of the secondary allele...enhance[s] the selection of its primary allele. This advantage feeds back on the selection of the modifier gene, forming a positive feedback loop" (p. 81). The general model of feedback selection depends on the notion of 'dispositive genes' which influence the disposition of a population in response to a particular variety of selection pressure. Wagner defines the dispositive gene as a genetic unit which "i) is able to enhance the speed of certain genetic adaptation processes and ii) has virtually no influence on the mean fitness of the population after the adaptation process is completed" (p. 81).
Worden, R.P. (1995) 'A Speed Limit for Evolution', Journal of Theoretical Biology 176: 137-52.
Derives very restrictive upper bound on the rate of a population's accumulation of information about the environment as displayed in spread of phenotypic characteristics ("genetic information in the phenotype", or GIP). The treatment rests on a partitioning of phenotypic characteristics which would be challenging to apply in empirical settings, and the notion of GIP does not appear to distinguish between full allele fixation on a sub-optimal local fitness peak and fixation on a global optimum. More complete critical review of this work is included in a paper currently under development.
Information, Complexity and Entropy
And Evolution
Also see section on speed of evolution, as well as Adami's (1998) book Introduction to Artificial Life.
Bookstein, F. (1983) 'Comment on a "Nonequilibrium" Approach to Evolution', Systematic Zoology 32: 291-300.
Mostly on-target critique of Wiley and Brooks (1982), but not without its own problems; see Wicken (1983).
Brooks, D.R. and E.O. Wiley (1986) Evolution as Entropy: Toward a Unified Theory of Biology. Chicago: University of Chicago Press.
Having read this book very quickly in hopes of finding new perspectives on how to quantify the accumulation of information by a population over time -- not the authors' principle aim, I must emphasise -- I was disappointed. Amidst a profusion of notions of entropy deriving from statistical mechanics, thermodynamics, and communication theory (embellished with apparently random switches between them) are embedded some fundamental positions which I believe to be patently false. For instance, the authors believe (as does Wiley 1988 in a shorter and more accessible article) that, due to the second law of thermodynamics, entropy always increases in evolutionary systems -- yet this clearly need not be the case for such open systems. Yes, the overall entropy of the entire system of which an evolutionary system is a part must certainly increase, but I can find no argument as to why the subset of physical entities which make up the evolutionary system itself should display increasing entropy. Similarly, the authors insist (p. 137, in what was actually for me the single most interesting chapter) that phylogenetic change can never be negentropic -- yet, the authors' own account would appear to suggest that exactly that may occur when, for instance, an organism's genome is significantly shortened (as is known to occur with some bacterial strains). Nonetheless, alert and critical readers will find interesting insights on the relationship between various notions of entropy and biological evolution and the pseudo-paradox that evolutionary systems appear to accumulate information even while the overall system of the universe is perpetually destroying it due to the second law.
Collier, J. (1986) 'Entropy in Evolution', Biology and Philosophy 1: 5-24.
This is an interesting attempt to sort out some of the myriad terminological confusions of Brooks and Wiley (1986), which I have read only quickly. While Collier does seem to have gone some way toward de-obfuscating Brooks and Wiley, I haven't yet become sufficiently convinced that Brooks and Wiley's approach is useful that I am motivated to study Collier in detail.
Collier, J. (1998) 'Information Increase in Biological Systems: How Does Adaptation Fit?', in Van de Vijver et al. (1998), pp. 129-40.
The author introduces 'information of adaptation', which turns out half-way through the paper to be simply the classical mutual information relation, in this case between traits and the environment. This is interesting but uninspiring.
Griffiths, P.E. (1999) 'Genetic Information: A Metaphor in Search of a Theory', draft of 7.9.99 -- NOT FOR CITATION. (Included here for research reference and not for citation.)
Offers a critical look at 'information talk' in molecular and developmental biology. It would be unfair to critique the article, as it is clearly a working draft. I would note, however, a general impression that theoretical and philosophical discussion of the role of 'information talk' with respect to genes and such would seem to be more useful in a context informed by quantitative information theoretic analysis.
Layzer, D. (1988) 'Growth of Order in the Universe', in Weber et al. (1988), pp. 23-39.
This is a very interesting article which particularly emphasises a distinction between potential entropy or potential information on the one hand and actual entropy on the other, with the author arguing that information should be understood as the difference between potential and actual entropy, rather than simply equating it with negentropy. According to this view, systems may increase in information and in entropy at the same time, provided the generation of potential entropy exceeds the realisation of actual entropy. This view permits, for instance, the universe to have begun to expand from a state of zero entropy and zero information, and it allows a view of increasing entropy during the process of evolution which is grounded in the expansion of the dimensionality of the genetic state space. As Layzer suggests, genetic variation may thus generate both entropy and potential entropy/information. Later in the article, unfortunately, Layzer refrains from pinning down precisely quantitative expressions for the relevant quantities which undergo change during the course of evolution. Also, it should be noted that Layzer suffers from a common misconception about Maxwell's Daemon, noted in the comments on Morowitz (1968a).
Løvtrup, S. (1983) 'Victims of Ambition: Comments on the Wiley and Brooks Approach to Evolution', Systematic Zoology 32: 90-96.
Mostly on-target critique of Wiley and Brooks (1982); see Wicken (1983).
Morowitz, H.J. (1968a) 'Order Information and Entropy', chapter 6 of Morowitz (1968), pp. 123-147.
This is an interesting, if somewhat meandering treatment of biological topics from the standpoint of thermodynamic entropy theory and information theory. (Note that these two topics are often conflated to poor effect, but in this case little harm seems to have been done.) While useful ideas can be gleaned from this chapter, doing so is very challenging on account of a common error running through the whole of the treatment: namely, Szilard's 1929 idea that the acquisition of information entails the expenditure of sufficient energy to save the second law of thermodynamics. This view was later shown to be in error, and a correct account was given by Bennett in 1987. (See Bennett 1987b in the bibliography for Mind Out of Matter). (Of course, Morowitz is not to be blamed for this appeal to Szilard and Brillouin after him, since he predated Bennett by nearly two decades.) There is also a somewhat confusing discussion of a system's entropy from its own 'point of view' which appears (pp. 133-134) to entail treating nonequilibrium biological systems as conservative. Unless I have missed something very badly (which is altogether possible!), citing the Liouville theorem and the conservation of phase space volumes over time requires treating the systems as conservative.
Ray, T. S. (1994) 'Evolution, complexity, entropy, and artificial reality', Physica D 75:239-63. (available online)
Statistical analysis of four variations of the original Tierra, with interesting notes on changes in population entropy over time. Nothing too Earth-shattering.
Standish, R.K. (1999) 'Some Techniques for the Measurement of Complexity in Tierra', in Floreano et al. (1999), pp. 104-8.
Offers a start on empirically estimating the classical information content of Tierran organisms, with a view to analysing the accumulation (or otherwise) of information over time. Unfortunately, after an interesting start, the paper finishes with an apology about the lack of results: "Due to the time constraints of finishing this paper, the analysis...has not been completed" (p. 107). Rats!
Saunders, P.T. and M.W. Ho (1976) 'On the Increase in Complexity in Evolution', Journal of Theoretical Biology 63: 375-84.
While this article gets off to a promising start with an abstract including comments like "complexity...gives a direction to evolution" and the "increase in complexity is...a consequence of the process by which a self-organizing system optimizes its organization" (p. 375), it shies from drawing any substantive conclusions whatsoever or appealing to any quantitative definitions of information or redundancy, noting that "such definitions ignore too many aspects of our intuitive understanding of the word to be suitable for our purposes" (p. 377). Later, in a discussion which appears to ignore utterly the difficulty and subtlety of the intellectual terrain (p. 377), the authors suggest that complexity admits of easy definition and empirical quantification in the form of DNA content. Very disappointing.
Teal, T.; D. Albro, E. Stabler, C.E. Taylor (1999) 'Compression and Adaptation', in Floreano et al. (1999), pp. 709-19.
Explores idea that adaptive systems, and particularly evolutionary ones, compress information about their environments. While initially promising, the paper's examination of MDL (minimum description length) for formal grammars is marred by the ommission of references to early work in the area of compression and predictability. For example, the authors' first conjecture that compression aids in generalisation is a weaker form of a result actually proved -- rather than conjectured -- in the late 1970s. Grounding in Kolmogorov complexity, Solomonoff's results on prediction, and general PAC (probably approximately correct) stuff would really have helped. All these things would have been impossible to miss with a reference to Li & Vitanyi (1997), yet only a short IEE presentation by Li & Vitanyi is actually cited.
Weber, B.H.; D.J. Depew, J.D. Smith, eds. (1988) Entropy, Information, and Evolution: New Perspectives on Physical and Biological Evolution. Cambridge, Massachusetts: MIT Press.
Having recently re-read this interesting collection of contributions from top authors on an eclectic mix of thermodynamics, information theory, and evolution, my impression of the book's single most glaringly plain characteristic has been reinforced: it is the astonishing extent to which the authors disagree blatantly over even the very basics. Only slightly less remarkable is the convincingness and authority with which each writes about their own particular position and those of others. Readers looking for a clear and uncontroversial picture of the relationship between evolution, information theory and thermodynamics will not find it here. Those looking to find confusion mixed with insight will be rewarded, but it's hard work separating the two.
Wicken, J.S. (1979) 'The Generation of Complexity in Evolution: A Thermodynamic and Information-Theoretical Discussion', Journal of Theoretical Biology 77: 349-65.
Author attempts to show how the tendency of evolutionary processes to give rise to increasingly complex life forms is a consequence of the Second Law of Thermodynamics. While this paper is one of Wicken's better written pieces, I nonetheless find Wicken (1987) more useful. This paper also provides the clearest indication yet that Wicken's repeated allusions to Chaitin and algorithmic information theory are based on fundamental confusions about the field.
Wicken, J.S. (1980) 'A Thermodynamic Theory of Evolution', Journal of Theoretical Biology 87: 9-23.
Similar in flavour to Wicken (1979), builds on idea that biosphere evolves toward maximum structuring and minimum dissipation. Again, Wicken (1987) is probably more useful.
Wicken, J.S. (1983) 'Entropy, Information, and Nonequilibrium Evolution', Systematic Zoology 32(4): 438-43.
Primarily a comment on Wiley and Brooks (1982), which successfully clarifies some of the semantic confusion surrounding both Wiley and Brooks and their commentators (including Bookstein 1983 and Løvtrup 1983), while unfortunately introducing one or two of his own confusions.
Wicken, J.S. (1987) Evolution, Thermodynamics, and Information. Oxford: Oxford University Press.
This attempt to forge greater connections between neo-Darwinism and thermodynamics is interesting and generally well conceived, but it suffers from a very qualitative as opposed to quantitative feel throughout. It's difficult to extract concrete quantitative conclusions, which will be a disappointment to those who, like me, read the book in hopes of finding insights into the job of using thermodynamics or information theory to quantify measurable aspects of evolution. Of particular note is a useful first chapter (pp. 17-28) on 'Entropy and Information' which persuasively explodes the ever so common conflation of Shannon and thermodynamic concepts of entropy based on the symbolic isomorphism between the respective equations. This is a good salve to those like Brooks and Wiley (1986), who run rough shod over the distinction.
Wiley, E.O. (1988) 'Entropy and Evolution', in Weber et al. (1988), pp. 173-88.
Concise discussion of the Brooks & Wiley approach to entropy and evolution, as discussed more fully in Brooks & Wiley (1986). The basic aim of the approach is to explain evolution by natural selection as a consequence of the second law of thermodynamics. In the space of two short pages, however (pp. 176-177), I become deeply confused attempting to follow the thinking. With a nod to authors such as Morowitz (1968) and Schrödinger (1945 book called What is Life?), who took the apparently decreasing entropy of evolutionary systems as a merely local effect paid for by global increases in entropy (makes perfect sense to me...), Wiley goes on to suggest that biological organisms really shouldn't be viewed as dissipative structures at all and should be analysed via nonequilibrium thermodynamics. From there, he suggests that information resides within biological systems and has a physical basis and that the entropy of biological information must therefore increase in irreversible processes due to the second law of thermodynamics. My confusion: for a start, biological systems obviously are dissipative structures at the chemical level, and I don't quite understand why a nonequilibrium thermodynamical approach to biological systems should require that this fact be superseded by some higher level notion according to which they are not dissipative. I completely agree (following Layzer 1988, for instance) that a genetic phase space of increasing dimensionality is a very important factor in understanding how entropy and information might simultaneously increase in an evolutionary process, but I have difficulty following Wiley's reasoning which appears to go along with this.
Wiley, E.O. and D.R. Brooks (1982) 'Victims of History -- A Nonequilibrium Approach to Evolution', Systematic Zoology 31: 1-24.
Pre-cursor to Brooks and Wiley (1986).
Wiley, E.O. and D.R. Brooks (1983) 'Nonequilibrium Thermodynamics and Evolution: A Response to Løvtrup', Systematic Zoology 32: 209-19.
As the title suggests...
Benford's Law
I'm not sure whether everyone will agree that this is most properly classified as information theory, but that's the context in which I tend to think about it, so here it is! NOTE: Benford's law describes the appearance of significant digits in a wide range of data with a logarithmic distribution: probability (first significant digit = d) = log10(1 + 1/d), where d = 1, 2, ... 9. Successive digits are much more uniform but still follow logarithmic distributions.
Benford, F. (1938) 'The law of anomalous numbers', Proceedings of the American Philosophical Society 78:551-72.
This was Benford's re-discovery of Newcomb's results and included evidence in the form of 20,229 observations from data sets ranging from areas of rivers, baseball statistics, atomic weights, and the street addresses of the first 342 men listed in American Men of Science. The results follow the logarithmic distribution remarkably well -- some commentators believe too well, suggesting Benford may have massaged the numbers for a better match.
Feldstein, A. and P. Turner (1986) 'Overflow, Underflow, and Severe Loss of Significance in Floating-Point Addition and Subtraction', IMA Journal of Numerical Analysis 6:241-51.
This paper shows that a Benford distribution of data implies that floating point additions and subtractions can result in overflow or underflow with surprisingly high frequency. Authors discuss this result in light of computer design and suggest a 128-bit long word format for reducing the risks of serious errors in scientific computations to more acceptable levels.
Hamming, R.W. (1970) 'On the Distribution of Numbers', Bell System Technical Journal 49(8): 1609-25.
Describes the distribution of mantissas of floating point numbers in terms of what Hamming calls the 'reciprocal distribution'. (Benford is not mentioned in the article, but of course the form of the distribution is the same.) Argues that sequences of multiplications and divisions effectively 'drive' numbers toward the familiar distribution (in essence, because the presence of just one member of the distribution in a sequence of operations ensures the outcome will also be, due to the invariance of the distribution under scaling operations), with similar but more limited results for the case of addition & subtraction. Discusses important applications to computer hardware and software design, the generation of random numbers, etc.
Hill, T. (1995a) 'Base invariance implies Benford's Law', Proceedings of the American Mathematical Society 123: 887-95.
This and Hill (1995c) are the more mathematically detailed of Hill's articles on Benford's law, this one demonstrating that scale invariance implies base invariance, and that base invariance in turn implies Benford's law. If we assume that any intuitively 'universal' law governing the distribution of digits must be scale invariant -- i.e., that changing measurement units does not change the distribution of digits -- then it turns out that Benford's law is the only law which can govern the distribution of digits.
Hill, T. (1995b) 'The significant-digit phenomenon', The American Mathematical Monthly 102: 322-27.
This is a brief but somewhat detailed explanation of the fact that scale invariance implies base invariance, which in turn implies Benford's law.
Hill, T. (1995c) 'A statistical derivation of the significant-digit law', Statistical Science 10(4): 354-63.
This and Hill (1995a) are the more mathematically detailed of Hill's articles on Benford's law, this one demonstrating that if distributions are selected at random, and in turn random samples are taken from these distributions, the significant digits of the combined samples converge to the Benford distribution. Moreover, distributions of successive digits also conform to a logarithm law, and successive digits are not independent. I.e., the probability of a given digit appearing in a given place depends on the presence of other digits in other places. (NOTE: This article is repeatedly referred to, even by Hill, as having a 1996 publication date, yet the first page of the actual article definitely says 1995. I have seen only a photocopy and not the original journal itself, so I cannot verify other dates printed on the journal, but I would guess it unlikely that Statistical Science printed its date incorrectly on the first page of the article...)
Hill, T. (1996) 'The first-digit phenomenon', American Scientist 86: 358-63.
This is a very accessible account of Benford's law, it's history and applications, including several examples and a description of the character of the 'random samples from random distributions' theorem. An interesting example illustrates the dependent nature of the probability of particular digits occuring in particular places: while the unconditional probability that the second digit of a base 10 number is a 2 is approximately 0.109, the conditional probability that the second digit is 2 given that the first digit is 1 is 0.115. And the probability that the first three significant digits are 3, 1, 4 is roughly 0.0014, fourty percent higher than one would expect if digits were distributed uniformly!
Matthews, R. (1999) 'The power of one', New Scientist 10 July 1999, pp. 26-30.
This 'popular science' article covers Benford's Law, which describes the frequency of appearance of digits in all manner of humanly used data, ranging from listings of drainage areas of rivers to numbers appearing in magazine articles, from census data to stock market prices. The law is the basis of the new field of 'digital analysis', which applies statistical tests to uncover deviations from Benford's law and thus the more likely appearance of fraud in data sets.
Newcomb, S. (1881) 'Note on the frequency of use of the different digits in natural numbers', American Journal of Mathematics 4:39-40.
This was the first publication of the logarithmic distribution which would be re-discovered by Benford more than half a century later. Includes observation about un-even wear in books of logarithm tables but no statistical evidence or proof.
Schatte, P. (1988) 'On Mantissa Distributions in Computing and Benford's Law', Journal of Information Processing and Cybernetics EIK 24(9):443-55.
Suggests but doesn't prove that after a sufficiently long computation in floating point arithmetic, mantissa distributions follow Benford's Law; treats Benford's Law itself as a corollary of this more general logarithmic mantissa distribution in 'extensive computing'. Reiterates conclusion that base 8 is optimal for information storage, first floated in 1973 article in German by same author (given as 'Zur Verteilung der Mantisse in der Gleitkommadarstellung einer Zufallsgrösse', Z. Angew. Math. Mech. 53:553-65). Although the author does a much better job than Hill of situating work within a broader context of other people's results, I found the article almost impossible to follow.
General
Also see section on information and evolution, which has some entries which are quite broad.
Chaitin, G.J. (1987) Information Randomness & Incompleteness. Singapore: World Scientific.
This is the broadest collection available of Greg Chaitin's foundational work on algorithmic information theory, sometimes also known as Kolmogorov complexity theory. Includes early papers from before the self-delimiting version of algorithmic information theory, as well as more recent work. Also see Li and Vitani (1997) and introductory material available on this site.
Collier, J. (1990) 'Intrinsic Information', in Hanson (1990), pp. 390-409.
Here the author attempts to offer an account of an object's intrinsic physical information, in terms of 'intropy' (what is often called 'negentropy', the difference between maximum possible entropy and displayed entropy) and 'enformation'; the latter term I never could find an explicit definition for. By the end, I have to admit a degree of befuddlement as to why something like the algorithmic complexity conditional on the laws of physics couldn't do the same job. (Algorithmic complexity does make an appearance, but in a significantly under-explained way.)
Hanson, P.P., ed. (1990) Information, Language and Cognition: Vancouver Studies in Cognitive Science, vol. 1. Oxford: Oxford University Press.
Lachmann, M.; M.E.J. Newman and C. Moore (submitted) 'The Physical Limits of Communication, or Why Any Sufficiently Advanced Technology is Indistinguishable from Noise', submitted to Nature. (available online)
Shows that optimally coded communications are indistinguishable from black body radiation, for anyone who does not know the encoding scheme. Perhaps I missed some subtleties in the physics, but the basic argument of the paper seems singularly unremarkable from the standpoint of algorithmic information theory or even classical information theory: it is, after all, well known (as the authors acknowledge) that an optimally coded message is incompressible and appears completely random.
Li, M. and P. Vitanyi (1997) An Introduction to Kolmogorov Complexity and its Applications. 2nd edition. New York: Springer-Verlag.
This is probably the single most comprehensive textbook of Kolmogorov complexity, or algorithmic information theory, presently available. Highly technical and much broader than, say, Chaitin's collective volume on the same topic. (Chaitin 1987)
Shannon, C.E. and W. Weaver (1949) The Mathematical Theory of Communication. Urbana: University of Illinois Press.
This is what started it all in modern information theory -- it's still one of the best treatments available. The only significant criticism is Weaver's over-emphasis of the connections with thermodynamics; while many authors succumb to the attraction of the analogy between thermodynamic entropy and Shannon's entropy of a distribution, readers should be careful of inferring from the superficial symbolic similarity between the two definitions some genuine isomorphism, particularly when it comes to applications to the second law. Shannon himself mentions Boltzmann only briefly and makes no such strong claims.
Stentiford, F.W.M. and D.W. Lewin (1973) 'An evolutionary approach to the concept of randomness', British Computer Journal 16(1): pages? February. (email primary author)
Briefly reviews von Mises and Kolmogorov/Chaitin approaches to randomness and introduces an 'evolutionary' approach based on a variety of probabilistic finite automata. Relative complexity comparisons may be made (and are made, via a short collection of empirical results) by comparing the extent to which individual sequences may be predicted by the probabilistic automata. There are one or two minor distractions in the paper, such as a slight superfluity in the definition of conditional complexity (which allows for the possibility that no program will exist which can compute one string given another string, yet one always exists which simply computes the required string directly, ignoring the given string) and a statement which seems to suggest that effective definitions of randomness for arbitrarily long strings are impossible. (The latter is a standard part of modern algorithmic information theory.) The later statement that "it would not be possible to design a computable sequence which would be guaranteed to baffle an estimate of complexity based on an evolutionary procedure" is parasitic on the randomness incorporated into the evolutionary procedure; consider "it would not be possible...based on a procedure of randomly guessing bits". (Clearly it is never possible to construct a sequence, computable or otherwise, which we can guarantee cannot be produced by randomly choosing bits.)
Management & Finance
Christensen, C.M. (1997) The Innovator's Dilemma: When New Technologies Cause Great Firms to Fail. Boston: Harvard Business School Press.
This is an excellent book, which I seem to be the last in the whole business community to have read. Based on real research and data rather than the metaphor which abounds in so many management books, this book describes the process whereby a new disruptive technology, inferior by the standards of existing value networks, takes root in a new value network and then proceeds to improve its performance at a sufficiently high rate that it shifts the entire value framework and ultimately drives the previous technology into an 'upmarket retreat' in the direction of higher margins but shrinking volumes. The phenomenon has occurred repeatedly in industries as diverse as disk drives, steel mills, excavators, motorbikes, and many others. This is a 'must read' which, like many classic books, will make the reader feel clever by clearly and explicitly articulating that which otherwise might have been appreciated mainly intuitively and incompletely. It should certainly be read by managers of research departments who need to grasp the importance of pursuing work with no identifiable markets and with no clear potential for generating significant revenues within the existing value network. It should also be read by researchers, because it will let them say to themselves, "I told you so".
Davis, S. and Meyer, C. (1998) Blur: The Speed of Change in the Connected Economy. Oxford: Capstone.
While occasionally heavy on consultant-style metaphorical fluff, this book is an otherwise excellent treatment of the dynamics of the modern, communication-enabled economy and gives short shrift to many of the clear-cut 19th-century concepts and distinctions which are still de rigeur in many business and economics curricula (think products and services, buyers and sellers, the importance of tangible capital, etc.) The book is primarily an exercise in challenging the way people think about market dynamics. The final chapter's list of practical suggestions for 'blurring' the reader's own business and approach might seem at first like flaky "business self-help", but in fact they have some substance to them and are worth considering!
Evans, P. and T.S. Wurster (2000) Blown to Bits: How the New Economics of Information Transforms Strategy. Boston: Harvard Business School Press.
(I'm not sure how this book came to have a copyright year of 2000 when I read a retail copy in December of 1999, but that's what it says...) Written by two vice presidents of the Boston Consulting Group, this book offers some very strong central tenets and metaphors wrapped up in many layers of seemingly unnecessary explanation and exposition, resulting in a remarkably high ratio of words to substance. The main message is that the exploding growth of connectivity between participants in the economy is fundamentally changing the traditional trade-off between a product or service's richness and its reach (i.e., the number of participants to whom it can be delivered).
Neural Networks
It seems strange to include this tiny little section here, since my previous work involved a great deal more attention to neural networks. Nonetheless, in keeping with the aim of recording notes on resources for ease of reference later, I'll maintain this section like the others. There is also at least one relevant entry in the section on Chemical Computing (Other). For other items on neural networks, the bibliography for Mind Out of Matter is probably a better place to visit.
Bartfai, G. (19??) 'An Adaptive Resonance Theory-based Neural Network Capable of Learning via Representational Redescription', unknown. {A colleague gave me a paper copy of this article, and I haven't yet tracked down the actual reference.} (email author)
This short paper reviews Grossberg's adaptive resonance theory and the representational redescription framework of Karmiloff-Smith (1992) before introducing a modification to the ARTMAP architecture which permits it to learn relational input-output dependencies which cannot easily be extracted solely from the statistics of input and output data. The mechanism can be understood as effecting a process by which knowledge embedded in a network can be redescribed and made available to it for further learning. Unfortunately, the means whereby the critical 'feature recombinators' at the heart of the architecture can be discovered are not addressed. On the last page, the author acknowledges that the problem is, in general, intractable -- but wonders if genetic algorithms might be applied to the search. So while the paper is genuinely interesting, it does smack of magic.
Maass, W. and C.M. Bishop, eds. (1999) Pulsed Neural Networks. London: MIT Press.
This is a super book spanning the range of current research in pulsed neural networks which, unlike the common computational model of networks shuffling continuous variables from one node to the next, rely on the timing of neuronal spikes to encode information and perform computations. The first half of the book contains several longer tutorial articles from the perspectives of neurobiology, hardware, and theory, while the second half comprises shorter articles on the latest research work. The book's twenty-eight contributors cover everything from population dynamics, phase locking, synchronisation and temporal binding to subthreshold analogue VLSI and the role of noise.
Smith, L.S. and A. Hamilton, eds. (1998) Neuromorphic Systems: Engineering Silicon from Neurobiology. Singapore: World Scientific.
Neuromorphic Systems
Deiss, S.R.; R.J. Douglas and A.M. Whatley (1999) 'A Pulse-Coded Communications Infrastructure for Neuromorphic Systems', in Maass & Bishop (1999), pp. 157-178. (available online)
Because CMOS VLSI technology limits the internal connectivity of neuromorphic chips (as well as their connectivity to the outside world), larger scale neuromorphic systems will likely have to be constructed from many chips working together. This article presents a communications protocol developed as part of the Silicon Cortex project which uses an asynchronous digital multiplexing technique dubbed 'address event representation' to allow several mixed analogue/digital neuromorphic chips to be incorporated into one system.
Indiveri, G.; J. Kramer and C. Koch (1996) 'Neuromorphic Vision Chips: Intelligent Sensors for Industrial Applications', in Advanced Microsystems for Automotive Applications 1996, pp. ??. (available online)
This article briefly surveys several neuromorphic circuits used for vision and motion detection and describes an automotive application developed at CalTech which employs such circuits for the computation of heading direction.
Indiveri, G. and P. Verschure (1997) 'Autonomous vehicle guidance using analog VLSI neuromorphic sensors', in Proceedings of the International Conference on Artificial Neural Networks 1997, pp. ??. (available online)
This Koala mobile robot from EPFL Lausanne uses a one-dimensional silicon retina to achieve reliable autonomous performance in an edge tracking task.
Mahowald, M. and R. Douglas (1991) 'A silicon neuron', Nature 354: 515-18.
This early rendition of a CMOS analogue VLSI 'neuron', simulating the electrophysiological characteristics of one variety of cortical neuron, is a classic in the field of neuromorphic design. While Misha Mahowald tragically passed away early in her prolific career after moving to EPFL from CalTech, co-author Rodney Douglas continues with similar work in this area.
Rasche, R.; R.J. Douglas and M. Mahowald (1998) 'Characterization of a Silicon Pyramidal Neuron', in Smith and Hamilton (1998), pp. ??. (available online)
Extending the extraordinary silicon neuron of Mahowald and Douglas (1991), the authors demonstrate a CMOS aVLSI silicon pyramidal cell which approximates the Hodgkin-Huxley model for active neuronal membrane conductances. Dynamical characteristics of the cell, such as spike frequency adaptation and interspike interval distributions, closely mimic those of real pyramidal cells.
Novel Computation & Computation Theory
Also see the section on neuromorphic systems under neural networks.
Chemical Computing (Other)
Adamatzky, A.; O. Holland, N. Rambidi, A. Winfield. (1999) 'Wet Artificial Brains: Towards the Chemical Control of Robot Motion by Reaction-Diffusion and Excitable Media', in Floreano, et al. (1999), pp. 304-13.
Reviews theoretical analysis and simulations of chemical controllers for object following, optimal path finding, and universal control; controllers exploit wave processes in reaction-diffusion systems (such as the BZ system) and 2D excitable lattices. Fascinating possibilities, especially the portion on universal computation in excitable media (rememeber the gates of Fredkin & Toffoli? no mention of Landauer...). Unresolved questions about the practical feasibility for real computing devices, though; authors' principle interest appears to be in the direction of motor control for robots.
Hjemfelt, A.; E.D. Wienberger and J. Ross (1991) 'Chemical implementation of neural networks and Turing machines', Proceedings of the National Academy of Sciences USA 88: 10983-87.
Describes chemical implementation of a McCulloch-Pitts style neural network using reversible chemical reaction mechanisms. Interesting, but the architecture does not involve learning, the actual chemistry of connecting large numbers of cells is not addressed, and the reactions require 4 + 4N + M reactants, where N is the number of neurons and M the number of connections. Also, the networks are primarily 'configure & compute' style, where the initial conditions are set and the system then settles to an answer (although the authors do address the possibility of altering neuron states over time via an externally supplied modulatory signal).
Computation Theory (General)
Budach, L., ed. (1979) Fundamentals of Computation Theory: Proceedings of the Conference on Algebraic, Arithmetic, and Categorial Methods in Computation Theory. Berlin: Akademie-Verlag.
Havel, I.M. and V. Koubek, eds. (1992) Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 629. New York: Springer-Verlag.
Hemmerling, A. (1979a) 'Systeme von Turing-Automaten und Zellularräume auf rahmbaren Pseudomustermengen', Journal of Information Processing and Cybernetics EIK 15(1/2): 47-72.
Original reference introducing Hemmerling's Systems of Turing Automata; discussed in English in Hemmerling (1979b).
Hemmerling, A. (1979b) 'Concentration of Multidimensional Tape-Bounded Systems of Turing Automata and Cellular Spaces', in Budach (1979), pp. 167-174.
First English treatment of Hemmerling's 'Systems of Turing Automata', proving several properties of the machines.
Wiedermann, J. (1992) 'Weak Parallel Machines: A New Class of Physically Feasible Parallel Machine Models', in Havel & Koubek (1992), pp. 95-111.
Generalised the STA model of Hemmerling (1979b) to the case of parallel Turing Machines.
Worsch, T. (to appear-a) 'On parallel Turing machines with multi-head control units', to appear in Parallel Computing. (available online)
Treatment of the generalisation of cellular automata called PTMs (Parallel Turing Machines), with particular attention to the definition of space complexity and resulting conclusions about PTM complexity.
Worsch, T. (to appear-b) 'Parallel Turing Machines With One-Head Control Units and Cellular Automata', to appear in Theoretical Computer Science. (available online)
Very technical treatment of complexity classes for parallel Turing machines and, thus, for cellular automata. (As the author notes in concluding comments on p. 31, in the extremes parallel Turing machines degenerate either to ordinary sequential Turing machines with one head -- no parallelism -- or to cellular automata -- full parallelism.)
Configurable Hardware & Defect Tolerance
Heath, J.R.; P.J. Kuekes, G.S. Snider, R.S. Williams (1998) 'A Defect-Tolerant Computer Architecture: Opportunities for Nanotechnology', Science 280: 1716-21.
This excellent article describes a massively parallel computer designed at HP Labs and constructed from largely faulty FPGAs. Meriting particular attention in the article is the possible application of the same techniques used to route around defects in the architecture to the problem of routing around faulty components in a molecular-level computer. If we can perfect techniques for efficiently using a hardware substrate made of faulty FPGAs, the authors suggest, we may be able to apply those same techniques to make efficient use of a hardware substrate comprising faulty molecular level components. Permitting flaws in molecular computers might in turn allow them to be produced at much higher yields and lower cost than ordinary silicon semiconductors, which are required to be virtually perfect.
Ortega, C. and A. Tyrrell (1998) 'Design of a Basic Cell to Construct Embryonic Arrays', IEE Proceedings on Computers and Digital Techniques 145(3): 242-8. (May)
Introduces authors' 'embryonics' approach to fault-tolerant FPGA configuration; need to follow this up.
Ortega, C. and A. Tyrrell (1999) 'Self-Repairing Multicellular Hardware: A Reliability Analysis', in Floreano, et al. (1999), pp. 442-6.
Building on the 'embryo | 
