Lamarckism in Genetic Algorithms

by Amit


Charles Darwin’s theory of natural selection proposed in his seminal On The Origin of Species [1] is  widely believed to be the key to understand how evolution has happened in Nature. However, it is not the only one. Almost sixty years before Darwin, in 1809 a Frenchman by the name Jean-Bapteste Lamarck had proposed another theory of Evolution in his work Philosophie zoologique, ou exposition des considérations relatives à l’histoire naturelle des animaux(English Translation) .

The year 2009 marks the 200th anniversary of  Jean-Bapteste Lamarck’s magnum opus Philosophie Zoologique [2].

Lamarck’s theory  (Lamarckism ) has become somewhat irrelevant as biologists have not been able to correlate the proposed theory to the actuality. However, what doesn’t take place in Natural life can always  be experimented with in Artificial Life. Evolutionary Computing researchers have successfully experimented with lamarckism in their field. This is my focus here. To narrow it down further, I shall (to start with) talk about applying key ideas of  Lamarckian Evolution in Genetic Algorithms

Genetic Algorithms with its Selection, Crossover, Mutation and reproduction mechanisms is the implementation of Darwinian model of evolution in Artificial Life. [3] has a short and concise overview of Genetic Algorithms, which should suffice for the current context.

These are some published works where the authors have applied the ideas of Lamarck in Genetic Algorithms:

  • Wellock, Ross.  An Examination of Lamarckian Genetic Algorithms
  • Whitley, Gordon, Mathias. Lamarckian Evolution, The Baldwin Effect and Function Optimization
  • Orvosh, Davis. Using a Genetic Algorithm to optimize problems with Feasibility Constraints

I shall now present some of the core ideas presented in the above works.

  1. In Lamarck’s theory plants and animals adapted to their environment and these adaptations passed on to their offspring. Darwin’s idea of natural  selection did not have any role in evolution in this theory. Thus, evolution takes place strictly by means of individual adaptation [3]
  2. In the context of Genetic Algorithms, adapting a individual directly translates to making the individual fitter in its environment. That is the key necessity of adaptation. An optimization technique is applied on the individual before its evaluation so as to make it more eligible for selection for the next generation. [3]. Various optimization techniques such as Local Search based methods and Artificial Neural Network   [3, 4] based models have been experimented with as optimization techniques. The key idea is to adapt the individual so that it is the fittest in its immediate environment. That is a Lamarckian strategy. [4]

Adaptation of a Individual in  a Genetic Algorithm: I mentioned the idea of adaptation in my last point. I shall try to give a better idea what I am trying to say here. Consider a individual coded as a string of bits, like in a Binary Coded GA without any loss of generality. Genetic Algorithms work with a search space. For any given binary coded individual, flipping any of its bits gives us another individual, which may be better or worse (in terms of fitness) compared to the given individual. Likewise, for any L-bit sized individual we have a total of other L individuals  (allowing a flipping of only 1-bit at a time) which may be better or worse to the given individual. The idea of applying a Lamarckian strategy in a Genetic Algorithm is to replace an incoming individual by a fitter  (or the fittest) individual in its environment or neighborhood. This is what we are calling as adaptation of a individual.

Drawing a parallel with Mutation: We can draw a parallel of the idea of adaptation with the concept of mutation in a Genetic Algorithm. Adaptation is a form of mutation! So you can actually use a Lamarckian strategy in a Genetic Algorithm as a mutation operator. See [5] for an use of such a strategy.

Repair and Replacement: Lamarckian strategy has also been used as a repair operator in highly constrained problems where feasible solutions are hard to find. See [5] for the details.

Performance: Usage of a Lamarckian strategy in Genetic Algorithms can result in faster convergence and at the same time in premature convergence. See [3], [4] and [5] for some performance statistics on various optimization problems

Besides the above works, I also came across some other published works where Lamarckian strategy has been applied in Genetic Algorithms. I hope to update this post in the near future when I am done reading them.

This is a final draft :). I hope to improve upon this with your comments and suggestions! Please report errors of any kind!!

References

  1. On The Origin of Species
  2. Is evolution Darwinian or/and Lamarckian?
  3. Wellock, Ross.  An Examination of Lamarckian Genetic Algorithms
  4. Whitley, Gordon, Mathias. Lamarckian Evolution, The Baldwin Effect and Function Optimization
  5. Orvosh, Davis. Using a Genetic Algorithm to optimize problems with Feasibility Constraints
Advertisements