Practical Handbook of Genetic Algorithms

Complex Coding Systems, Volume III

Lance D. Chambers, Lance D. Chambers

• Publisher: CRC Press
• Year: 2019
• ISBN:
  9780429525575
• Edition: 1
• Topic: Computer Science
• Subtopic: Programming Algorithms
• Index: Computer Science

Practical Handbook of Genetic Algorithms, Volume 3: Complex Coding Systems contains computer-code examples for the development of genetic algorithm systems - compiling them from an array of practitioners in the field.
Each contribution of this singular resource includes:

• unique code segments
  
• documentation
  
• descripti

Chapter 1 A Lamarckian Evolution Strategy for Genetic Algorithms

Brian J. Ross

Brock University
Department of Computer Science
St Catharines, Ontario, Canada

email: [email protected]

1.1. Introduction

Prior to Charles Darwin’s theory of evolution by natural selection, Jean Baptiste Lamarck (1744-1829) proposed a multifaceted theory of evolution [Dawkins 1996, Gould 1980, Cochrane 1997]. One aspect of his theory is the notion that characteristics acquired by an organism during its lifetime are inheritable by its offspring. Lamarck proposed this as the means by which organisms passed on specialized traits for surviving in the environment, and this has since become known as Lamarckian evolution or Lamarckism. For example, if a horse developed especially adept leg muscles for negotiating mountainous terrain, Lamarckian evolution suggests that its offspring would inherit similarly muscular legs. Lamarckian inheritance of acquired characteristics maintains that the acquired development of strong legs, through years of exercise in a mountainous environment, will influence the actual genetic makeup of the horse. This altered genetic information is inheritable by the horse’s offspring. This contrasts with the Darwinian tenet that a horse that is genetically predisposed to having muscular legs will probably have offspring with a similar genetic tendency.

Lamarckism has been universally rejected as a viable theory of genetic evolution in nature. There are hundreds of millions of genetic variations in a typical DNA of an organism. Physical characteristics of a phenotype are the result of combined interactions between many separate components of the DNA. In addition, the acquired characteristics of a phenotype are manipulations of the organism’s tissues as permitted within their range of possible forms as dictated by the genotype. Darwinian evolution proposes that the complex structure of DNA results in sensible phenotypes due to the accumulation of millions of years of minute genetic mutations, and their subsequent success through natural selection. On the other hand, the mechanism required by Lamarckian evolution is that physical characteristics of the phenotype must in some way be communicated backwards to the DNA of the organism. The biological mechanism by which such communication would arise is unknown. Furthermore, the inversion of gross physical characteristics of the phenotype into the many genetic codes needed to reproduce them in subsequent generations seems to be an impossibly complex task. It is worth mentioning that Lamarckian effects have been conjectured in the context of some experiments with cellular life forms [Cochrane 1997]. These recent results are somewhat of a reprieve for the disrepute that Lamarck’s evolutionary theory has suffered over the centuries.

Although discredited in biology, Lamarckian evolution has proven to be a powerful concept within artificial evolution applications on the computer. Unlike life in the natural world, computer programs use very simple transformations between genotypes and phenotypes, and the inversion of phenotypes to their corresponding genotypes is often tractable. In the case that genotypes are their own phenotypes, there is no transformation whatsoever between them. The overall implication of this with respect to Lamarckian evolution is that it is possible to optimize a phenotype in the context of a particular problem environment, and have this optimization reflected in the corresponding genotype for subsequent inheritance by offspring. Therefore, the problems encountered by Lamarckism in nature is solved on the computer: inverted communication from the phenotype to the genotype is typically a simple computation.

Lamarckian evolution and genetic search have been combined together in genetic algorithms (GA) [Hart and Belew 1996, Ackley and Littman 1996, Li et al. 1996, Grefenstette 1991]. Lamarckism typically takes the localized-search form of a phenotype’s structure space within the context of the problem being solved. [Hart and Belew 1996] found that the traditional genetic algorithm is most proficient for searching and reconciling widely separated portions of the search space caused by scattered populations, while Lamarckian localized search is more adept at exploring localized areas of the population that would be missed by the wide global swath of the genetic algorithm. Lamarckism may be especially practical when the population has converged into pockets of local minima that would not be thoroughly explored by a standard genetic algorithm. The contribution of Lamarckism is a noticeable acceleration in overall performance of the genetic algorithm.

1.2. Implementation

1.2.1 Basic Implementation

The appendix contains Prolog code that introduces Lamarckian evolution to a genetic algorithm and this code is discussed in detail in the remainder of this section. The language is Quintus Prolog 3.2 and the code was implemented in the Silicon Graphics Irix 5.3 environment.

The code presumes the following is done by the main genetic algorithm. First, the individual genotypes are saved as separate Prolog clauses in the following form: individual(ID, Fitness, Expression).

ID is an identification label such as an integer that uniquely identifies each individual in the population. Fitness is the evaluated fitness score for the individual, where the lower scores denote higher fitness. Expression is the individual’s chromosome as used by the genetic algorithm for the particular problem at hand.

Second, two clauses are used to communicate control and population information from the genetic algorithm and user to the Lamarckian module. A clause population_size(PopSize) should contain the current population size as its single numeric argument. A clause lamarckian(Percent, K) is used to control the Lamarckian evolution itself. Percent is a fractional value between 0.0 and 1.0 denoting the percentage of the population upon which Lamarckian evolution should be applied. K is the number of iterations used by the search strategy, which is discussed below.

Finally, the user should have the following three predicates defined somewhere in the main genetic algorithm (change as appropriate): (i) select(ID). This returns a single ID from the population to the calling code. This predicate should use a selection technique of choice, such as tournament selection or fitness-proportional selection, (ii) mutation(Expr, Mutant). This applies an appropriate mutation on an Expression, resulting in its Mutant. (iii) eval_fitness(Individual, Fitness). This applies the problem-specific fitness evaluation function on an Individual, resulting in its Fitness value, such that lower values of Fitness denote fitter individuals.

The top-level predicate of the module is Iamarckian_evolution/0. This predicate should be called within the main generational loop of the genetic algorithm, at a point after the main genetic reproduction has occurred for a generation. For example,

loop :- … {perform reproduction and mutation for entire population}

…

%(a new generation has now been formed…)

lamarckian_evolution, loop.

% iterate to next generation

Although the code is written to be used in a generational style of genetic algorithm, as opposed to a steady-state genetic algorithm [Mitchell 1996], it is easily adapted to a steady-state approach if desired (see Section 1.2.2).

The first clause of lamarckian_evolution takes care of the case when the user wants to perform Lamarckian evolution on the entire population (Percent is 1.0). The clause collects the entire set of individual identifiers from the population, and calls the Lamarckian algorithm on them. Otherwise, if a fraction of the population greater than 0.0 is to be processed, the second clause is used. Here, the rough number of individuals to process is computed from the percentage parameter and the population size, and an appropriately sized list of unique IDs is obtained and processed.

The second clause of lamarckian_evolution calls the predicate get_unique__IDs/3 to select a set of unique identifiers of a desired size between 1 and the size of the population as a whole. To do this, get_unique_IDs loops repeatedly until a list of the desired size has been obtained. The selection routine from the main genetic algorithm is used to select individuals. Note that if a high percentage of the population is to be selected for Lamarckian processing, this routine can become slow, since the selection of individuals unique to an already large list of selections can take time. It is recommended that the entire population be processed in such cases, as the first clause of lamarckian_evolution will efficiently process such selections. Finally, if the user does not wish to use Lamarckism, the final clause will activate.

The predicate lamarck_loop/2 controls the Lamarckian evolution of a list of selected individuals. For each individual as referenced by an ID in the list, its current expression and fitness are obtained from the database. Then, a localized search is performed on it, for the number of iterations specified by the parameter K. The result of the localized search is possibly a new individual NewExpr, with fitness NewFit. If the new fitness is better than that of the original, then the original individual’s clause ...