Very original paper by Hinton and Nowlan

• G. E. Hinton and S. J. Nowlan (1987) "How Learning Can Guide Evolution." Complex Systems Vol. 1, pp. 495--502 (5 pages)
  
  
  • "We demonstrate that this effect allows learning organisms to evolve much faster than their nonlearning equivalents, even though the characteristics acquired by the phenotype are not communicated to the genotype."
  • "It seems very wasteful not to make use of the exploration performed by the phenotype to facilitate the evolutionary search for good genotypes. The obvious way to achieve this is to transfer information about the acquired characteristics back to the genotype."
  • "This type of interaction between learning and evolution was first proposed by Baldwin (1896) and Lloyd Morgan (1896) and is sometimes called the Baldwin effect." "Baldwinism is best understood by considering an extreme (and unrealistic) case in which the combinatorics are very clear."
    - While later this is challanged for very sophisticated case.
  • "It is like searching for a needle in a haystack when someone tells you when you are getting close."
  • "The central point of the argument is that the person who tells you that you are getting close does not need to tell you anything more."
  • "We assume, for simplicity, a learning mechanism that simply tries a random combination of switch settings on every trial. If the combination of the switch settings and the genetically specified decisions ever produce the one good net we assume that the switch settings are frozen. Otherwise they keep changing.[2]"
  • "what happens to the relative frequencies of the correct, incorrect, and ? alleles during a typical evolutionary search in which each organism runs many learning trials during its lifetime."
  • "The crux of the problem is that only the one good genotype is distinguished, and fitness is the only criterion for mate selection."

• [B] "An Introduction to Quantum Computing for Non-Physicists" (45 pages)
  
  • The author of "Finding Solutions to NP Problems: Philosophical Differences Between Quantum and Evolutionary Search Algorithms" claims the best tutorial among othres which were writtne by physisits.
  "Accessing the results is equivalent to making a measurement, which disturbs the quantum state."

Other Related Works

• R. Mills, and R. A. Watson (2005) "Genetic assimilation and canalisation in the Baldwin effect." In Proceedings of the European Conference on Artificial Intelligence, pp. 353-362, Springer-Verlag. (10 pages)
  
  
  • "Here we present a simplified model that is used to reveal the essential mechanisms and highlight several conceptual issues that have not been clearly defined in prior literature."
  • "The Baldwin Effect indicates that individually learned behaviours acquired during an organism's lifetime can influence the evolutionary path taken by a population, without any direct Lamarckian transfer of traits from phenotype to genotype."
  • "Several computational studies modelling this effect have included complications that restrict its applicability."
  • "Our knowledge of modern genetics suggests that an organism's lifetime adaptations cannot influence the course of evolution because learned characteristics do not change ones own genes."
  • "The hypothesis appears very similar to Lamarck's disproved beliefs that an acquired trait is directly inherited by offspring."
  • "In 1987 Hinton and Nowlan published the first computational model [6] to demonstrate the Baldwin Effect which provides excellent insight into how the effect works."
  • "In typical runs of the simulation after very few generations, the all 1fs phenotype is found by lifetime learning, and the average number of 1's in the genotype increases rapidly. In subsequent generations the average number of 1's in the genotype increases slowly towards the fittest genotype."
  • "Canalisation, or reduction in lifetime plasticity, is facilitated by means of reduction in numbers of ?'s -- the allele representing that plasticity."
  • "the canalisation effect in the experiment; that is pressures for the reduction in plasticity following a learned behaviour becoming genetic."
  • "H&N's model is analysed in [7-9], which all focus on the canalisation effect in the experiment; that is pressures for the reduction in plasticity following a learned behaviour becoming genetic." [7] Belew, R.K.: When both individuals and populations search, In Schaffer, J.D. (ed.) Pro-ceedings of the Third International Conference on Genetic Algorithms, San Mateo, Cali-fornia: Morgan Kaufmann (1989) [8] Harvey I.: The puzzle of the persistent question marks: A case study of genetic drift. In S. Forrest (editor) Proceedings of the Fifth International Conference on Genetic Algorithms, ICGA-93, California: Morgan Kaufmann (1993) [9] Wiles, J., Schultz, R., Hallinan, J., Bolland, S., Tonkes, B.: Probing the persistent question marks, In L. Spector, E. Goodman, A. Wu, W. B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon & E. Burke (Eds), Proceedings of the Genetic and Evo-lutionary Computation Conference (GECCO-2001). San Francisco, CA: Morgan Kaufmann Publishers (2001) 710--717
  • "To remove the assumption of learning phenotypes, we evaluate fitness as the mean fitness of the lifetime phenotypes, rather than the number of trials remaining after the phenotypic solution is first found. This means that the organisms do not have to recognise their own success (as is implicit in H&Nfs model)."
  • "In our constant plasticity model there is no designation of particular traits that are phenotypically plastic, i.e. we do not use ? alleles. Instead lifetime plasticity varies any trait with equal probability, using non-heritable mutation-like variations applied to the genotypic trait specifications in each lifetime trial. This models a constant plasticity level which separates the effects of lifetime plasticity from canalisation."
  • "Specifically, this new model does not use canalisation, individuals do not have to recognise their own success (i.e. cognitive learning is not required, only some form of phenotypic plasticity),"
  
  
  

• R. Mills, and R. A. Watson (2006) "On Crossing fitness Valleys with the Baldwin Effect." Proceedings of Artificial Life X, pp. 493--499 (2006). (7 pages)
  
  The target task of this paper is "the jester's cap" which "is a hierarchical task that has two major fitness peaks and multiple sub-peaks." The target didn't interest me so much but found a couples of good descriptions of Hinton and Nowlan's problem.
  
  
  • 
    ----- see ref -----
    "Although many studies of the Baldwin effect have involved more general fitness landscapes, some of which will certainly involve multiple fitness peaks, studies which specifically address this seem lacking. One exception (Wiles et al. 2001) provides a simulation study of the Baldwin effect on an explicitly multi-peaked landscape -- however, the findings of this paper are concerned with the interaction between the Baldwin effect and the operation of genetic crossover on the underlying modular structure that produced these peaks."
    ----- see ref -----
    
  • "In this paper we address the influence of the Baldwin effect on crossing fitness valleys using a simple two-peaked example (building on Hinton and Nowlan's approach), and we provide quantitative analysis of its abilities and limitations in this process."
  • 
    ----- see ref -----
    "One way to understand the effect of lifetime plasticity on the selective pressures acting on a population is as a 'smoothing' of the fitness landscape (Watson et al. 2000)."
    ----- see ref -----
    
  • "However, ours does not assume that an individual knows it has found the global optimum; thus exploration continues throughout its lifetime."
  • "We show that, whereas in the Hinton and Nowlan model the Baldwin effect merely converts a flat area of the landscape to an inclined area, the Baldwin effect can go further and convert a negative selective gradient into a positive selective gradient for the learning population."
  • "Moreover we see that the particular way in which Hinton and Nowlan represent canalisation in their model is questionable as well as unnecessary."
  • "To remove the assumption of learning phenotypes, we evaluate fitness as the mean fitness of the lifetime phenotypes, rather than the number of trials remaining after the phenotypic solution is first found. This means that the organisms do not have to recognise their own success (as is implicit in H&Nfs model)."
  • "In our constant plasticity model there is no designation of particular traits that are phenotypically plastic, i.e. we do not use e?f alleles."
  • "We find the extent of modifications to this landscape provided by plasticity, by calculating the expected fitness of individuals as a function of their location with respect to the two peaks."
  • "In this model each of the phenotypic trials is independent and the fitness of an individual is calculated by the mean of the fitness of all of its phenotypes."
    ----- see ref -----
    
  • "This calls for a different approach in calculating the total expected fitness, and for this we extend the method used by Harvey (1993) to analyse Hinton and Nowlan's model."
    ----- see ref -----
    
  • "Thus from an engineering perspective, the Baldwin effect is not an efficient means for crossing valleys in terms of the number of fitness evaluations."
  • "the crossing time without the Baldwin effect will be very long (exponential in N).
  • "Our evolving population is modelled using a constant population size of 200 N-bit genotypes, initialised on the low-fitness peak. Each new generation is formed by fitness-proportional reproduction."
  • "In (Mills and Watson 2005) we stress that many works have conflated these two concepts and that this confusion is in large part because they are difficult to disentangle in the particular model that Hinton and Nowlan provided."
  • "1 To consider performance from an engineering perspective, we find the learning population takes approx. 13.3*200*1024 = 2,723,840 evaluations, which is significantly more than for the non-plastic case (approx. 2382*200 = 476,400 evaluations). However, this model is not intended to show any engineering advantage; from a biological viewpoint, generation time is approximately fixed. Thus the important comparison to make is upon the number of generations required."
  • "it is not clear to us that this mechanism of canalisation makes sense in general."
    ----- 2nd -----
    
  • "Another study presents a cultural model with learned and inherited behaviours, using a physical world similar to [10], but with shared behaviours between phenotypes [13]. Results are similar to [11-12]; when behaviours are shared in abundance, assimilation advantage (i.e. selection for independence) reduces. Turney identifies confusion surrounding Baldwinian and Lamarckian evolution, and highlights that although the benefits of learning are demonstrated, often the costs of learning pass without acknowledgement."

Further Study of R. Mills, and R. A. Watson (2006) --- the papers refered.

• J. Wiles, B. Tonkes, and J. R. Watson (2001) "How learning can guide evolution in hierarchical modular tasks" In Moore, J. D. and Stenning, K, (Eds.), Proceedings of the 23rd Annual Conference of the Cognitive Science Society, pp 1130-1135. (6 pages)
  
  The target task of this paper is "the jester's cap" which "is a hierarchical task that has two major fitness peaks and multiple sub-peaks." The target didn't interest me so much but found a couples of good descriptions of Hinton and Nowlan's problem.
  
  
  • "Under Darwinian inheritance, the things that an animal learns during its life cannot be passed directly to its offspring via the genotype."
  • "Behaviors that were initially interpreted as general learning abilities would, over time, become innate. No information about the content of learning is passed from parent to offspring, but in the general variation across the population, some individuals would by chance have starting points closer to the fitness maximum and smaller search radii (i.e., slightly stronger biases). These individuals would have more offspring than those with weaker biases, and in environments with fixed fitness functions, innate behaviors would gradually replace learned ones."
  • "Agents that can search their local environment will be able to explore whole regions of search space in their lifetimes, rather than the single point of their own genotype. In this way, learning can enable an evolutionary algorithm to solve problems that are too costly for genetic search alone."
  • "The ones and zeroes were fixed values that did not change during an individual's lifetime. The question marks were learnable genes, which could change during a lifetime."
  • "Hinton and Nowlan showed that the zero alleles quickly dropped out of the population and the number of question marks reduced over time."
  • "A useful reference is the edited volume of papers relating to learning and evolution by Mitchell and Belew (1996), which includes reprints of the original papers by Baldwin (1896),Morgan (1896), and Hinton and Nowlan (1987) as well as many other related studies."
  • "H-IFF is a simple function that is hierarchical, modular, is not searchable by mutation, but is amenable to search by crossover."
  • "H-IFF has two optimal bit-strings and, for bit-strings of length k = 2^n, there are 2^(k/2) local optima."
  • "The highest scoring guess (0011) is taken as the 'learned' setting. However, this 'learned' setting is not passed on during reproduction, it is the initial genome, 0??1 that is used in reproduction."
  • "We consider the jesterfs cap task with three variations of the amount of learning time available to the agents: no learning (replicating the H-IFF task), a small amount of learning (N = 10) and a moderate amount of learning (N = 100)."
  • "These simulations were repeated 100 times for each condition, varying the initial random seed. During the course of a simulation, the mean fitness of the population is monitored. Simulations were run for a maximum of 2000 generations, or until the population converged."
  • "Local search provides the wrong operator for preserving and improving fitness because it spends too much time in the troughs of fitness space."
  • "Our study shows how the Baldwin effect can operate without canalisation and this aids significantly in simplifying understanding of how the Baldwin effect works by smoothing out of the fitness landscape."
  
  
  

• R. A. Watson, T. Reil, and J. B. Pollack "Mutualism, Parasitism, and Evolutionary Adaptation" (9 pages)

Yet other related papers

• P. Turney (1996) "Myths and Legends of the Baldwin Effect" Proceedings of the 13th International Conference on Machine Learning, pp. 135--142. (8 pages)
  
  
  • "This position paper argues that the Baldwin effect is widely misunderstood by the evolutionary computation community."
  • "Since Hinton and Nowlanfs (1987) classic paper, several researchers have observed a synergetic effect in evolutionary computation when there is an evolving population of learning individuals (Ackley and Littman, 1991; Belew, 1989; Belew et al., 1991; French and Messinger, 1994; Hart, 1994; Hart and Belew, 1996; Hightower et al., 1996; Whitley and Gruau, 1993; Whitley et al., 1994)."
  • "Most of the work in the artificial life and genetic algorithm communities has focused on the benefits of phenotypic plasticity and the plasticity of learning (observations 1 and 4) (Ackley and Littman, 1991; Belew, 1989; Belew et al., 1991; French and Messinger, 1994; Hart, 1994; Hart and Belew, 1996; Hightower et al., 1996; Whitley and Gruau, 1993; Whitley et al., 1994; Balakrishnan and Honavar, 1995; Belew and Mitchell, 1996). Together, these observations imply that learning can facilitate evolution."
  • "Some recent work in ALife and GA has combined analysis of the benefits of phenotypic plasticity, phenotypic rigidity, and the plasticity of learning (observations 1, 2, and 4) (Anderson, 1995a, 1995b; Cecconi, 1995; Hinton and Nowlan, 1987; Behera and Nanjundiah, 1995). These observations imply that learning can facilitate evolution, but learned behaviors may eventually be replaced by instinctive behaviors."
  • "Lamarckism requires an inverse mapping from phenotype and environment to genotype. This inverse mapping is biologically implausible. However, the Baldwin effect is purely Darwinian; not Lamarckian. The Baldwin effect does not involve any inverse mapping."
  • "Suppose a short-necked animal learns to stretch its neck to reach nutritious leaves on a tall tree. Lamarck believed that the animalfs offspring would inherit slightly longer necks than they would otherwise have had. This would require a mechanism for modifying the DNA of the parent, to alter its genes for neck length, based on its habit of stretching its neck."
  • "The Baldwin effect has consequences that are similar to Lamarckian evolution. Over many generations, animals that stretch their necks may evolve longer necks. However, the mechanism is purely Darwinian. Parents who stretch their necks will pass on to their children not their longer necks, but rather their ability to stretch their necks."
  • "Evolution will select for the ability to stretch. Over many generations, the population will evolve to consist largely of animals that are very good at stretching their necks."
  • "However, there can be advantages to being born with a longer neck. Given sufficient time, the population may eventually evolve longer necks. Their ability to stretch their necks is what grants them the time required to evolve longer necks. The point of this story is that the Baldwin effect is somewhat Lamarckian in its results, but it is not Lamarckian in its mechanisms."
  • "Perhaps Lamarckian evolution is superior to the Baldwin effect, when we are attempting to solve problems by evolutionary computation (Belew, 1990; Hightower et al., 1996; Whitley et al., 1994; Moscato, 1989, 1993; Moscato and Fontanari, 1990; Norman and Moscato, 1989; Moscato and Norman, 1992; Radcliffe and Surry, 1994; Paechter et al., 1995; Burke et al., 1995)."
  • "The mapping from genotype (bias) and environment (data) to phenotype (decision tree) was easily computed, but there is no known algorithm for the inverse mapping from phenotype (decision tree) and environment (data) to genotype (bias)."
  • "Lamarckian evolution distorts the population so that the Schema Theorem no longer applies (Whitley et al., 1994). The Baldwin effect alters the fitness landscape, but it does not modify the basic evolutionary mechanism (i.e., it is purely Darwinian). Therefore the Schema Theorem still applies to the Baldwin effect."
  • "It seems possible that memes in our brains may evolve as much in a few minutes or days as birds evolve in ten-thousand years."
  • "A second argument for Lamarckian memes is based on creativity. Creative thought often seems to consist of combining ideas to make new ideas. This might appear to support a Lamarckian view. However, perhaps creative thought is a mating of memes, rather than a merging of ideas. Unlike biological organisms, memes do not seem to respect species boundaries; any two memes might mate with each other and produce fertile offspring. The evidence appears to be compatible with both Lamarck and Darwin. ----- maybe double but ---
  • {\it ``The genotype is ... In a living organism, this is typically the organism's DNA. In evolutionary computation, it is typically a string of bits. The phenotype is the set of observable characteristics of an organism, as determined by the organism's genotype and environment.''
  • {\it ``The distinction between genotype and phenotype is clear in biological evolution, but the distinction does not exist in many of the simpler examples of evolutionary computation.''}
  • {\it ``Learning has benefits but it also has costs. The Baldwin effect is concerned with the costs and benefits of lifetime learning in an evolving population.''}
  • ``Learning can accelerate evolution under certain circumstances, but it can also slow evolution under other circumstances.''
  • {\it ``This makes it easier for evolution to climb to peaks in the landscape.''} (Turney 1998).
  • ``Lamarckism requires an inverse mapping from phenotype and environment to genotype. This inverse mapping is biologically implausible.'' (Turney)
  • %% the Baldwin effect is somewhat Lamarckian in its results, but it is not %% Lamarckian in its mechanisms.
  • %% In biological evolution, no organism can have maximize expected inclusive fitness as a goal,
  • %% Perhaps Lamarckian evolution is superior to the %% Baldwin effect, when we are attempting to solve problems %% by evolutionary computation
  • %% Perhaps Lamarckian evolution is superior to the %% Baldwin effect, when we are attempting to solve problems %% by evolutionary computation
  • %% In some recent work with Lamarckian evolution, there is no distinction between the phenotype %% and the genotype (Whitley et al., 1994; Paechter et al., 1995; Burke et al., %% 1995). This produces the misleading impression that the %% inverse mapping is trivial. It may well be trivial for many %% interesting and worthwhile problems, but we believe that it is generally intractable. %% With progress in evolutionary computing, we will eventually encounter the limits of the %% Lamarckian approach.
  • %% There are reasons to believe that the Baldwin effect has more applications in evolutionary %% computation than Lamarckian evolution. Lamarckian evolution %% requires an inverse mapping from phenotype and %% environment to genotype. We believe that computing this %% mapping is intractable in general.
  
  
  

• R. A. Watson, and J. B. Pollack "How Symbiosis Can Guide Evolution" (10 pages)
  
  ----- After Section 3 -----
  
  • "Hinton and Nowlan choose the population size, number of lifetime trials, and number of variables in the problem carefully so as to make it most unlikely that genetic variation alone will find the solution but very likely that lifetime variation will."
  • "Since we are interested in the ability of symbiotic scaffolding to encapsulate the abilities of symbionts of different species, we will not use genetic recombination (crossover) in our main experiments. ... Instead we will use mutation as our only source of genetic variation."
  • "From the evolutionary computation point of view, the influence of symbiosis in guiding genetic variation is interesting only if it provides inspiration for more effective algorithms (here abstractions, rather than specific biological details, are more informative)."
  
  
  

• J. Wiles, J. Watson, B. Tonkes, T. Deacon (2002) "Strange loops in learnign and evolution"" (12 pages)
  • "We ised a fra,ewprl based pm Jomtpm amd Mpw;am s 1987 simulation of the Baldwin effec. Additional gene complexes and an environmental parameter were added to their basic model. and the fitness function extended."
  • "As is well-known in the modelling community, the Baldwin effect only occurs in simulations when the population of agents is "poised on the brink" of dixcovering the genetically specified solution. " (done before 1.2)

Complexity of Random Search