Cultural AlgorithmCultural Algorithm, CA. TaxonomyThe Cultural Algorithm is an extension to the field of Evolutionary Computation and may be considered a MetaEvolutionary Algorithm. It more broadly belongs to the field of Computational Intelligence and Metaheuristics. It is related to other highorder extensions of Evolutionary Computation such as the Memetic Algorithm. InspirationThe 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. MetaphorThe 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 tapinto 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. StrategyThe information processing objective of the algorithm is to improve the learning or convergence of an embedded search technique (typically an evolutionary algorithm) using a higherorder 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 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. Input :
$Problem_{size}$, $Population_{num}$
Output :
KnowledgeBase
Population $\leftarrow$ InitializePopulation ($Problem_{size}$, $Population_{num}$)KnowledgeBase $\leftarrow$ InitializeKnowledgebase ($Problem_{size}$, $Population_{num}$)While ($\neg$StopCondition ())Evaluate (Population )$SituationalKnowledge_{candidate}$ $\leftarrow$ AcceptSituationalKnowledge (Population )UpdateSituationalKnowledge (KnowledgeBase , $SituationalKnowledge_{candidate}$)Children $\leftarrow$ ReproduceWithInfluence (Population , KnowledgeBase )Population $\leftarrow$ Select (Children , Population )$NormativeKnowledge_{candidate}$ $\leftarrow$ AcceptNormativeKnowledge (Population )UpdateNormativeKnowledge (KnowledgeBase , $NormativeKnowledge_{candidate}$)End Return (KnowledgeBase )Heuristics
Code ListingListing (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_{n1})=0.0$. The Cultural Algorithm was implemented based on the description of the Cultural Algorithm Evolutionary Program (CAEP) presented by Reynolds [Reynolds1999]. A realvalued 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 realvalued 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 + ((maxmin) * 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 Download: cultural_algorithm.rb.
ReferencesPrimary SourcesThe 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 MoreChung 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 MultiObjective Optimization problems [CoelloCoello2003]. Bibliography

Free CourseGet one algorithm per week...
Own A CopyThis 438page ebook has...


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

Do you like Clever Algorithms? Buy the book now. 