Grammatical EvolutionGrammatical Evolution, GE. TaxonomyGrammatical Evolution is a Global Optimization technique and an instance of an Evolutionary Algorithm from the field of Evolutionary Computation. It may also be considered an algorithm for Automatic Programming. Grammatical Evolution is related to other Evolutionary Algorithms for evolving programs such as Genetic Programming and Gene Expression Programming, as well as the classical Genetic Algorithm that uses binary strings. InspirationThe Grammatical Evolution algorithm is inspired by the biological process used for generating a protein from genetic material as well as the broader genetic evolutionary process. The genome is comprised of DNA as a string of building blocks that are transcribed to RNA. RNA codons are in turn translated into sequences of amino acids and used in the protein. The resulting protein in its environment is the phenotype. MetaphorThe phenotype is a computer program that is created from a binary stringbased genome. The genome is decoded into a sequence of integers that are in turn mapped onto predefined rules that makeup the program. The mapping from genotype to the phenotype is a onetomany process that uses a wrapping feature. This is like the biological process observed in many bacteria, viruses, and mitochondria, where the same genetic material is used in the expression of different genes. The mapping adds robustness to the process both in the ability to adopt structureagnostic genetic operators used during the evolutionary process on the subsymbolic representation and the transcription of wellformed executable programs from the representation. StrategyThe objective of Grammatical Evolution is to adapt an executable program to a problem specific objective function. This is achieved through an iterative process with surrogates of evolutionary mechanisms such as descent with variation, genetic mutation and recombination, and genetic transcription and gene expression. A population of programs are evolved in a subsymbolic form as variable length binary strings and mapped to a symbolic and wellstructured form as a context free grammar for execution. ProcedureA grammar is defined in Backus Normal Form (BNF), which is a context free grammar expressed as a series of production rules comprised of terminals and nonterminals. A variablelength binary string representation is used for the optimization process. Bits are read from the a candidate solutions genome in blocks of 8 called a codon, and decoded to an integer (in the range between 0 and $2^{8}1$). If the end of the binary string is reached when reading integers, the reading process loops back to the start of the string, effectively creating a circular genome. The integers are mapped to expressions from the BNF until a complete syntactically correct expression is formed. This may not use a solutions entire genome, or use the decoded genome more than once given it's circular nature. Algorithm (below) provides a pseudocode listing of the Grammatical Evolution algorithm for minimizing a cost function. Input :
Grammar , $Codon_{numbits}$, $Population_{size}$, $P_{crossover}$, $P_{mutation}$, $P_{delete}$, $P_{duplicate}$
Output :
$S_{best}$
Population $\leftarrow$ InitializePopulation ($Population_{size}$, $Codon_{numbits}$)For ($S_{i}$ $\in$ Population )$Si_{integers}$ $\leftarrow$ Decode ($Si_{bitstring}$, $Codon_{numbits}$)$Si_{program}$ $\leftarrow$ Map ($Si_{integers}$, Grammar )$Si_{cost}$ $\leftarrow$ Execute ($Si_{program}$)End $S_{best}$ $\leftarrow$ GetBestSolution (Population )While ($\neg$StopCondition ())Parents $\leftarrow$ SelectParents (Population , $Population_{size}$)Children $\leftarrow \emptyset$For ($Parent_{i}$, $Parent_{j}$ $\in$ Parents )$S_{i}$ $\leftarrow$ Crossover ($Parent_{i}$, $Parent_{j}$, $P_{crossover}$)$Si_{bitstring}$ $\leftarrow$ CodonDeletion ($Si_{bitstring}$, $P_{delete}$)$Si_{bitstring}$ $\leftarrow$ CodonDuplication ($Si_{bitstring}$, $P_{duplicate}$)$Si_{bitstring}$ $\leftarrow$ Mutate ($Si_{bitstring}$, $P_{mutation}$)Children $\leftarrow$ $S_{i}$End For ($S_{i}$ $\in$ Children )$Si_{integers}$ $\leftarrow$ Decode ($Si_{bitstring}$, $Codon_{numbits}$)$Si_{program}$ $\leftarrow$ Map ($Si_{integers}$, Grammar )$Si_{cost}$ $\leftarrow$ Execute ($Si_{program}$)End $S_{best}$ $\leftarrow$ GetBestSolution (Children )Population $\leftarrow$ Replace (Population , Children )End Return ($S_{best}$)Heuristics
Code ListingListing (below) provides an example of the Grammatical Evolution algorithm implemented in the Ruby Programming Language based on the version described by O'Neill and Ryan [ONeill2001]. The demonstration problem is an instance of symbolic regression $f(x)=x^4+x^3+x^2+x$, where $x\in[1,10]$. The grammar used in this problem is:
The production rules for the grammar in BNF are:
The algorithm uses point mutation and a codonrespecting onepoint crossover operator. Binary tournament selection is used to determine the parent population's contribution to the subsequent generation. Binary strings are decoded to integers using an unsigned binary. Candidate solutions are then mapped directly into executable Ruby code and executed. A given candidate solution is evaluated by comparing its output against the target function and taking the sum of the absolute errors over a number of trials. The probabilities of point mutation, codon deletion, and codon duplication are hard coded as relative probabilities to each solution, although should be parameters of the algorithm. In this case they are heuristically defined as $\frac{1.0}{L}$, $\frac{0.5}{NC}$ and $\frac{1.0}{NC}$ respectively, where $L$ is the total number of bits, and $NC$ is the number of codons in a given candidate solution. Solutions are evaluated by generating a number of random samples from the domain and calculating the mean error of the program to the expected outcome. Programs that contain a single term or those that return an invalid (NaN) or infinite result are penalized with an enormous error value. The implementation uses a maximum depth in the expression tree, whereas traditionally such deep expression trees are marked as invalid. Programs that resolve to a single expression that returns the output are penalized. 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.to_f) child = "" bitstring.size.times do i bit = bitstring[i].chr child << ((rand()<rate) ? ((bit=='1') ? "0" : "1") : bit) end return child end def one_point_crossover(parent1, parent2, codon_bits, p_cross=0.30) return ""+parent1[:bitstring] if rand()>=p_cross cut = rand([parent1[:bitstring].size, parent2[:bitstring].size].min/codon_bits) cut *= codon_bits p2size = parent2[:bitstring].size return parent1[:bitstring][0...cut]+parent2[:bitstring][cut...p2size] end def codon_duplication(bitstring, codon_bits, rate=1.0/codon_bits.to_f) return bitstring if rand() >= rate codons = bitstring.size/codon_bits return bitstring + bitstring[rand(codons)*codon_bits, codon_bits] end def codon_deletion(bitstring, codon_bits, rate=0.5/codon_bits.to_f) return bitstring if rand() >= rate codons = bitstring.size/codon_bits off = rand(codons)*codon_bits return bitstring[0...off] + bitstring[off+codon_bits...bitstring.size] end def reproduce(selected, pop_size, p_cross, codon_bits) 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] = one_point_crossover(p1, p2, codon_bits, p_cross) child[:bitstring] = codon_deletion(child[:bitstring], codon_bits) child[:bitstring] = codon_duplication(child[:bitstring], codon_bits) child[:bitstring] = point_mutation(child[:bitstring]) children << child break if children.size == pop_size end return children end def random_bitstring(num_bits) return (0...num_bits).inject(""){s,i s<<((rand<0.5) ? "1" : "0")} end def decode_integers(bitstring, codon_bits) ints = [] (bitstring.size/codon_bits).times do off codon = bitstring[off*codon_bits, codon_bits] sum = 0 codon.size.times do i sum += ((codon[i].chr=='1') ? 1 : 0) * (2 ** i); end ints << sum end return ints end def map(grammar, integers, max_depth) done, offset, depth = false, 0, 0 symbolic_string = grammar["S"] begin done = true grammar.keys.each do key symbolic_string = symbolic_string.gsub(key) do k done = false set = (k=="EXP" && depth>=max_depth1) ? grammar["VAR"] : grammar[k] integer = integers[offset].modulo(set.size) offset = (offset==integers.size1) ? 0 : offset+1 set[integer] end end depth += 1 end until done return symbolic_string end def target_function(x) return x**4.0 + x**3.0 + x**2.0 + x end def sample_from_bounds(bounds) return bounds[0] + ((bounds[1]  bounds[0]) * rand()) end def cost(program, bounds, num_trials=30) return 9999999 if program.strip == "INPUT" sum_error = 0.0 num_trials.times do x = sample_from_bounds(bounds) expression = program.gsub("INPUT", x.to_s) begin score = eval(expression) rescue score = 0.0/0.0 end return 9999999 if score.nan? or score.infinite? sum_error += (score  target_function(x)).abs end return sum_error / num_trials.to_f end def evaluate(candidate, codon_bits, grammar, max_depth, bounds) candidate[:integers] = decode_integers(candidate[:bitstring], codon_bits) candidate[:program] = map(grammar, candidate[:integers], max_depth) candidate[:fitness] = cost(candidate[:program], bounds) end def search(max_gens, pop_size, codon_bits, num_bits, p_cross, grammar, max_depth, bounds) pop = Array.new(pop_size) {i {:bitstring=>random_bitstring(num_bits)}} pop.each{c evaluate(c,codon_bits, grammar, max_depth, bounds)} best = 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,codon_bits) children.each{c evaluate(c, codon_bits, grammar, max_depth, bounds)} children.sort!{x,y x[:fitness] <=> y[:fitness]} best = children.first if children.first[:fitness] <= best[:fitness] pop=(children+pop).sort{x,y x[:fitness]<=>y[:fitness]}.first(pop_size) puts " > gen=#{gen}, f=#{best[:fitness]}, s=#{best[:bitstring]}" break if best[:fitness] == 0.0 end return best end if __FILE__ == $0 # problem configuration grammar = {"S"=>"EXP", "EXP"=>[" EXP BINARY EXP ", " (EXP BINARY EXP) ", " VAR "], "BINARY"=>["+", "", "/", "*" ], "VAR"=>["INPUT", "1.0"]} bounds = [1, 10] # algorithm configuration max_depth = 7 max_gens = 50 pop_size = 100 codon_bits = 4 num_bits = 10*codon_bits p_cross = 0.30 # execute the algorithm best = search(max_gens, pop_size, codon_bits, num_bits, p_cross, grammar, max_depth, bounds) puts "done! Solution: f=#{best[:fitness]}, s=#{best[:program]}" end Download: grammatical_evolution.rb.
ReferencesPrimary SourcesGrammatical Evolution was proposed by Ryan, Collins and O'Neill in a seminal conference paper that applied the approach to a symbolic regression problem [Ryan1998a]. The approach was born out of the desire for syntax preservation while evolving programs using the Genetic Programming algorithm. This seminal work was followed by application papers for a symbolic integration problem [ONeill1998] [ONeill1998a] and solving trigonometric identities [Ryan1998]. Learn MoreO'Neill and Ryan provide a highlevel introduction to Grammatical Evolution and early demonstration applications [ONeill1999]. The same authors provide a thorough introduction to the technique and overview of the state of the field [ONeill2001]. O'Neill and Ryan present a seminal reference for Grammatical Evolution in their book [ONeill2003]. A second more recent book considers extensions to the approach improving its capability on dynamic problems [Dempsey2009]. 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. 