Memetic AlgorithmMemetic Algorithm, MA. TaxonomyMemetic 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. InspirationMemetic Algorithms are inspired by the interplay of genetic evolution and memetic evolution. Universal Darwinism is the generalization of genes beyond biologicalbased 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. MetaphorThe 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. StrategyThe 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. ProcedureAlgorithm (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}$)Heuristics
Code ListingListing (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_{n1})=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 + ((maxmin)/((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[i1] p2 = selected[0] if i == selected.size1 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 Download: memetic_algorithm.rb.
ReferencesPrimary SourcesThe 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 MoreMoscato 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 'selfgenerating' Memetic Algorithms that use the memetic principle to coevolve 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

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. 