Clever Algorithms: Nature-Inspired Programming Recipes

By Jason Brownlee PhD

Home | Read Online



This is the ad-supported version of the book. Buy it now if you like it.

Memetic Algorithm

Memetic Algorithm, MA.

Taxonomy

Memetic Algorithms have elements of Metaheuristics and Computational Intelligence. Although they have principles of Evolutionary Algorithms, they may not strictly be considered an Evolutionary Technique. Memetic Algorithms have functional similarities to Baldwinian Evolutionary Algorithms, Lamarckian Evolutionary Algorithms, Hybrid Evolutionary Algorithms, and Cultural Algorithms. Using ideas of memes and Memetic Algorithms in optimization may be referred to as Memetic Computing.

Inspiration

Memetic Algorithms are inspired by the interplay of genetic evolution and memetic evolution. Universal Darwinism is the generalization of genes beyond biological-based systems to any system where discrete units of information can be inherited and be subjected to evolutionary forces of selection and variation. The term 'meme' is used to refer to a piece of discrete cultural information, suggesting at the interplay of genetic and cultural evolution.

Metaphor

The genotype is evolved based on the interaction the phenotype has with the environment. This interaction is metered by cultural phenomena that influence the selection mechanisms, and even the pairing and recombination mechanisms. Cultural information is shared between individuals, spreading through the population as memes relative to their fitness or fitness the memes impart to the individuals. Collectively, the interplay of the geneotype and the memeotype strengthen the fitness of population in the environment.

Strategy

The objective of the information processing strategy is to exploit a population based global search technique to broadly locate good areas of the search space, combined with the repeated usage of a local search heuristic by individual solutions to locate local optimum. Ideally, memetic algorithms embrace the duality of genetic and cultural evolution, allowing the transmission, selection, inheritance, and variation of memes as well as genes.

Procedure

Algorithm (below) provides a pseudocode listing of the Memetic Algorithm for minimizing a cost function. The procedure describes a simple or first order Memetic Algorithm that shows the improvement of individual solutions separate from a global search, although does not show the independent evolution of memes.

Input: ProblemSize, $Pop_{size}$, $MemePop_{size}$
Output: $S_{best}$
Population $\leftarrow$ InitializePopulation(ProblemSize, $Pop_{size}$)
While ($\neg$StopCondition())
    For ($S_{i}$ $\in$ Population)
        $Si_{cost}$ $\leftarrow$ Cost($S_{i}$)
    End
    $S_{best}$ $\leftarrow$ GetBestSolution(Population)
    Population $\leftarrow$ StochasticGlobalSearch(Population)
    MemeticPopulation $\leftarrow$ SelectMemeticPopulation(Population, $MemePop_{size}$)
    For ($S_{i}$ $\in$ MemeticPopulation)
        $S_{i}$ $\leftarrow$ LocalSearch($S_{i}$)
    End
End
Return ($S_{best}$)
Pseudocode for the Memetic Algorithm.

Heuristics

  • The global search provides the broad exploration mechanism, whereas the individual solution improvement via local search provides an exploitation mechanism.
  • Balance is needed between the local and global mechanisms to ensure the system does not prematurely converge to a local optimum and does not consume unnecessary computational resources.
  • The local search should be problem and representation specific, where as the global search may be generic and non-specific (black-box).
  • Memetic Algorithms have been applied to a range of constraint, combinatorial, and continuous function optimization problem domains.

Code Listing

Listing (below) provides an example of the Memetic Algorithm implemented in the Ruby Programming Language. The demonstration problem is an instance of a continuous function optimization that seeks $\min f(x)$ where $f=\sum_{i=1}^n x_{i}^2$, $-5.0\leq x_i \leq 5.0$ and $n=3$. The optimal solution for this basin function is $(v_0,\ldots,v_{n-1})=0.0$. The Memetic Algorithm uses a canonical Genetic Algorithm as the global search technique that operates on binary strings, uses tournament selection, point mutations, uniform crossover and a binary coded decimal decoding of bits to real values. A bit climber local search is used that performs probabilistic bit flips (point mutations) and only accepts solutions with the same or improving fitness.

def objective_function(vector)
  return vector.inject(0.0) {|sum, x| sum +  (x ** 2.0)}
end

def random_bitstring(num_bits)
  return (0...num_bits).inject(""){|s,i| s<<((rand<0.5) ? "1" : "0")}
end

def decode(bitstring, search_space, bits_per_param)
  vector = []
  search_space.each_with_index do |bounds, i|
    off, sum = i*bits_per_param, 0.0
    param = bitstring[off...(off+bits_per_param)].reverse
    param.size.times do |j|
      sum += ((param[j].chr=='1') ? 1.0 : 0.0) * (2.0 ** j.to_f)
    end
    min, max = bounds
    vector << min + ((max-min)/((2.0**bits_per_param.to_f)-1.0)) * sum
  end
  return vector
end

def fitness(candidate, search_space, param_bits)
  candidate[:vector]=decode(candidate[:bitstring], search_space, param_bits)
  candidate[:fitness] = objective_function(candidate[:vector])
end

def binary_tournament(pop)
  i, j = rand(pop.size), rand(pop.size)
  j = rand(pop.size) while j==i
  return (pop[i][:fitness] < pop[j][:fitness]) ? pop[i] : pop[j]
end

def point_mutation(bitstring, rate=1.0/bitstring.size)
  child = ""
   bitstring.size.times do |i|
     bit = bitstring[i].chr
     child << ((rand()<rate) ? ((bit=='1') ? "0" : "1") : bit)
  end
  return child
end

def crossover(parent1, parent2, rate)
  return ""+parent1 if rand()>=rate
  child = ""
  parent1.size.times do |i|
    child << ((rand()<0.5) ? parent1[i].chr : parent2[i].chr)
  end
  return child
end

def reproduce(selected, pop_size, p_cross, p_mut)
  children = []
  selected.each_with_index do |p1, i|
    p2 = (i.modulo(2)==0) ? selected[i+1] : selected[i-1]
    p2 = selected[0] if i == selected.size-1
    child = {}
    child[:bitstring] = crossover(p1[:bitstring], p2[:bitstring], p_cross)
    child[:bitstring] = point_mutation(child[:bitstring], p_mut)
    children << child
    break if children.size >= pop_size
  end
  return children
end

def bitclimber(child, search_space, p_mut, max_local_gens, bits_per_param)
  current = child
  max_local_gens.times do
    candidate = {}
    candidate[:bitstring] = point_mutation(current[:bitstring], p_mut)
    fitness(candidate, search_space, bits_per_param)
    current = candidate if candidate[:fitness] <= current[:fitness]
  end
  return current
end

def search(max_gens, search_space, pop_size, p_cross, p_mut, max_local_gens,
    p_local, bits_per_param=16)
  pop = Array.new(pop_size) do |i|
    {:bitstring=>random_bitstring(search_space.size*bits_per_param)}
  end
  pop.each{|candidate| fitness(candidate, search_space, bits_per_param) }
  gen, best = 0, pop.sort{|x,y| x[:fitness] <=> y[:fitness]}.first
  max_gens.times do |gen|
    selected = Array.new(pop_size){|i| binary_tournament(pop)}
    children = reproduce(selected, pop_size, p_cross, p_mut)
    children.each{|cand| fitness(cand, search_space, bits_per_param)}
    pop = []
    children.each do |child|
      if rand() < p_local
        child = bitclimber(child, search_space, p_mut, max_local_gens,
          bits_per_param)
      end
      pop << child
    end
    pop.sort!{|x,y| x[:fitness] <=> y[:fitness]}
    best = pop.first if pop.first[:fitness] <= best[:fitness]
    puts ">gen=#{gen}, f=#{best[:fitness]}, b=#{best[:bitstring]}"
  end
  return best
end

if __FILE__ == $0
  # problem configuration
  problem_size = 3
  search_space = Array.new(problem_size) {|i| [-5, +5]}
  # algorithm configuration
  max_gens = 100
  pop_size = 100
  p_cross = 0.98
  p_mut = 1.0/(problem_size*16).to_f
  max_local_gens = 20
  p_local = 0.5
  # execute the algorithm
  best = search(max_gens, search_space, pop_size, p_cross, p_mut, max_local_gens, p_local)
  puts "done! Solution: f=#{best[:fitness]}, b=#{best[:bitstring]}, v=#{best[:vector].inspect}"
end
Memetic Algorithm in Ruby

References

Primary Sources

The concept of a Memetic Algorithm is credited to Moscato [Moscato1989], who was inspired by the description of meme's in Dawkins' "The Selfish Gene" [Dawkins1976]. Moscato proposed Memetic Algorithms as the marriage between population based global search and heuristic local search made by each individual without the constraints of a genetic representation and investigated variations on the Traveling Salesman Problem.

Learn More

Moscato and Cotta provide a gentle introduction to the field of Memetic Algorithms as a book chapter that covers formal descriptions of the approach, a summary of the fields of application, and the state of the art [Moscato2003]. An overview and classification of the types of Memetic Algorithms is presented by Ong et al. who describe a class of adaptive Memetic Algorithms [Ong2006]. Krasnogor and Smith also provide a taxonomy of Memetic Algorithms, focusing on the properties needed to design 'competent' implementations of the approach with examples on a number of combinatorial optimization problems [Krasnogor2005]. Work by Krasnogor and Gustafson investigate what they refer to as 'self-generating' Memetic Algorithms that use the memetic principle to co-evolve the local search applied by individual solutions [Krasnogor2004]. For a broader overview of the field, see the 2005 book "Recent Advances in Memetic Algorithms" that provides an overview and a number of studies [Hart2005].

Bibliography

[Dawkins1976] R. Dawkins, "The selfish gene", Oxford University Press, 1976.
[Hart2005] W. E. Hart and N. Krasnogor and J. E. Smith, "Recent Advances in Memetic Algorithms", Springer, 2005.
[Krasnogor2004] N. Krasnogor and S. Gustafson, "A study on the use of "self-generation" in memetic algorithms", Natural Computing, 2004.
[Krasnogor2005] N. Krasnogor and J. Smith, "A Tutorial for Competent Memetic Algorithms: Model, Taxonomy and Design Issues", IEEE Transactions on Evolutionary Computation, 2005.
[Moscato1989] P. Moscato, "On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms", California Institute of Technology, 1989.
[Moscato2003] P. Moscato and C. Cotta, "A gentle introduction to memetic algorithms", in Handbook of Metaheuristics, pages 105–144, Kluwer Academic Publishers, 2003.
[Ong2006] Y–S. Ong and M–H. Lim and N. Zhu and K–W. Wong, "Classification of Adaptive Memetic Algorithms: A Comparative Study", IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, 2006.
Clever Algorithms: Nature-Inspired Programming Recipes

Free Course

Get one algorithm per week...
  • ...delivered to your inbox
  • ...described in detail
  • ...to read at your own pace
Sign-up Now












Own A Copy

This 438-page ebook has...
  • ...45 algorithm descriptions
  • ...best practice usage
  • ...pseudo code
  • ...Ruby code
  • ...primary sources
Buy Now




Please Note: This content was automatically generated from the book content and may contain minor differences.

Clever Algorithms: Nature-Inspired Programming Recipes



Do you like Clever Algorithms?
Buy the book now.


© Copyright 2015. All Rights Reserved. | About | Contact | Privacy