Cultural Algorithm

Cultural Algorithm, CA.

Taxonomy

The Cultural Algorithm is an extension to the field of Evolutionary Computation and may be considered a Meta-Evolutionary Algorithm. It more broadly belongs to the field of Computational Intelligence and Metaheuristics. It is related to other high-order extensions of Evolutionary Computation such as the Memetic Algorithm.

Inspiration

The Cultural Algorithm is inspired by the principle of cultural evolution. Culture includes the habits, knowledge, beliefs, customs, and morals of a member of society. Culture does not exist independent of the environment, and can interact with the environment via positive or negative feedback cycles. The study of the interaction of culture in the environment is referred to as Cultural Ecology.

Metaphor

The Cultural Algorithm may be explained in the context of the inspiring system. As the evolutionary process unfolds, individuals accumulate information about the world which is communicated to other individuals in the population. Collectively this corpus of information is a knowledge base that members of the population may tap-into and exploit. Positive feedback mechanisms can occur where cultural knowledge indicates useful areas of the environment, information which is passed down between generations, exploited, refined, and adapted as situations change. Additionally, areas of potential hazard may also be communicated through the cultural knowledge base.

Strategy

The information processing objective of the algorithm is to improve the learning or convergence of an embedded search technique (typically an evolutionary algorithm) using a higher-order cultural evolution. The algorithm operates at two levels: a population level and a cultural level. The population level is like an evolutionary search, where individuals represent candidate solutions, are mostly distinct and their characteristics are translated into an objective or cost function in the problem domain. The second level is the knowledge or believe space where information acquired by generations is stored, and which is accessible to the current generation. A communication protocol is used to allow the two spaces to interact and the types of information that can be exchanged.

Procedure

The focus of the algorithm is the KnowledgeBase data structure that records different knowledge types based on the nature of the problem. For example, the structure may be used to record the best candidate solution found as well as generalized information about areas of the search space that are expected to payoff (result in good candidate solutions). This cultural knowledge is discovered by the population-based evolutionary search, and is in turn used to influence subsequent generations. The acceptance function constrain the communication of knowledge from the population to the knowledge base.

Algorithm (below) provides a pseudocode listing of the Cultural Algorithm. The algorithm is abstract, providing flexibility in the interpretation of the processes such as the acceptance of information, the structure of the knowledge base, and the specific embedded evolutionary algorithm.

Heuristics

• The Cultural Algorithm was initially used as a simulation tool to investigate Cultural Ecology. It has been adapted for use as an optimization algorithm for a wide variety of domains not-limited to constraint optimization, combinatorial optimization, and continuous function optimization.
• The knowledge base structure provides a mechanism for incorporating problem-specific information into the execution of an evolutionary search.
• The acceptance functions that control the flow of information into the knowledge base are typically greedy, only including the best information from the current generation, and not replacing existing knowledge unless it is an improvement.
• Acceptance functions are traditionally deterministic, although probabilistic and fuzzy acceptance functions have been investigated.

Code Listing

Listing (below) provides an example of the Cultural 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=2$. The optimal solution for this basin function is $(v_0,\ldots,v_{n-1})=0.0$.

The Cultural Algorithm was implemented based on the description of the Cultural Algorithm Evolutionary Program (CAEP) presented by Reynolds [Reynolds1999]. A real-valued Genetic Algorithm was used as the embedded evolutionary algorithm. The overall best solution is taken as the 'situational' cultural knowledge, whereas the bounds of the top 20% of the best solutions each generation are taken as the 'normative' cultural knowledge. The situational knowledge is returned as the result of the search, whereas the normative knowledge is used to influence the evolutionary process. Specifically, vector bounds in the normative knowledge are used to define a subspace from which new candidate solutions are uniformly sampled during the reproduction step of the evolutionary algorithm's variation mechanism. A real-valued representation and a binary tournament selection strategy are used by the evolutionary algorithm.

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

def rand_in_bounds(min, max)
  return min + ((max-min) * rand())
end

def random_vector(minmax)
  return Array.new(minmax.size) do |i|
    rand_in_bounds(minmax[i][0], minmax[i][1])
  end
end

def mutate_with_inf(candidate, beliefs, minmax)
  v = Array.new(candidate[:vector].size)
  candidate[:vector].each_with_index do |c,i|
    v[i]=rand_in_bounds(beliefs[:normative][i][0],beliefs[:normative][i][1])
    v[i] = minmax[i][0] if v[i] < minmax[i][0]
    v[i] = minmax[i][1] if v[i] > minmax[i][1]
  end
  return {:vector=>v}
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 initialize_beliefspace(search_space)
  belief_space = {}
  belief_space[:situational] = nil
  belief_space[:normative] = Array.new(search_space.size) do |i|
    Array.new(search_space[i])
  end
  return belief_space
end

def update_beliefspace_situational!(belief_space, best)
  curr_best = belief_space[:situational]
  if curr_best.nil? or best[:fitness] < curr_best[:fitness]
    belief_space[:situational] = best
  end
end

def update_beliefspace_normative!(belief_space, acc)
  belief_space[:normative].each_with_index do |bounds,i|
    bounds[0] = acc.min{|x,y| x[:vector][i]<=>y[:vector][i]}[:vector][i]
    bounds[1] = acc.max{|x,y| x[:vector][i]<=>y[:vector][i]}[:vector][i]
  end
end

def search(max_gens, search_space, pop_size, num_accepted)
  # initialize
  pop = Array.new(pop_size) { {:vector=>random_vector(search_space)} }
  belief_space = initialize_beliefspace(search_space)
  # evaluate
  pop.each{|c| c[:fitness] = objective_function(c[:vector])}
  best = pop.sort{|x,y| x[:fitness] <=> y[:fitness]}.first
  # update situational knowledge
  update_beliefspace_situational!(belief_space, best)
  max_gens.times do |gen|
    # create next generation
    children = Array.new(pop_size) do |i|
      mutate_with_inf(pop[i], belief_space, search_space)
    end
    # evaluate
    children.each{|c| c[:fitness] = objective_function(c[:vector])}
    best = children.sort{|x,y| x[:fitness] <=> y[:fitness]}.first
    # update situational knowledge
    update_beliefspace_situational!(belief_space, best)
    # select next generation
    pop = Array.new(pop_size) { binary_tournament(children + pop) }
    # update normative knowledge
    pop.sort!{|x,y| x[:fitness] <=> y[:fitness]}
    acccepted = pop[0...num_accepted]
    update_beliefspace_normative!(belief_space, acccepted)
    # user feedback
    puts " > generation=#{gen}, f=#{belief_space[:situational][:fitness]}"
  end
  return belief_space[:situational]
end

if __FILE__ == $0
  # problem configuration
  problem_size = 2
  search_space = Array.new(problem_size) {|i| [-5, +5]}
  # algorithm configuration
  max_gens = 200
  pop_size = 100
  num_accepted = (pop_size*0.20).round
  # execute the algorithm
  best = search(max_gens, search_space, pop_size, num_accepted)
  puts "done! Solution: f=#{best[:fitness]}, s=#{best[:vector].inspect}"
end

References

Primary Sources

The Cultural Algorithm was proposed by Reynolds in 1994 that combined the method with the Version Space Algorithm (a binary string based Genetic Algorithm), where generalizations of individual solutions were communicated as cultural knowledge in the form of schema patterns (strings of 1's, 0's and #'s, where '#' represents a wildcard) [Reynolds1994].

Learn More

Chung and Reynolds provide a study of the Cultural Algorithm on a testbed of constraint satisfaction problems [Chung1996]. Reynolds provides a detailed overview of the history of the technique as a book chapter that presents the state of the art and summaries of application areas including concept learning and continuous function optimization [Reynolds1999]. Coello Coello and Becerra proposed a variation of the Cultural Algorithm that uses Evolutionary Programming as the embedded weak search method, for use with Multi-Objective Optimization problems [CoelloCoello2003].

Bibliography

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