Grammatical Evolution

Grammatical Evolution, GE.

Taxonomy

Grammatical 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.

Inspiration

The 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.

Metaphor

The phenotype is a computer program that is created from a binary string-based genome. The genome is decoded into a sequence of integers that are in turn mapped onto pre-defined rules that makeup the program. The mapping from genotype to the phenotype is a one-to-many 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 structure-agnostic genetic operators used during the evolutionary process on the sub-symbolic representation and the transcription of well-formed executable programs from the representation.

Strategy

The 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 sub-symbolic form as variable length binary strings and mapped to a symbolic and well-structured form as a context free grammar for execution.

Procedure

A 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 non-terminals. A variable-length 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.

Heuristics

• Grammatical Evolution was designed to optimize programs (such as mathematical equations) to specific cost functions.
• Classical genetic operators used by the Genetic Algorithm may be used in the Grammatical Evolution algorithm, such as point mutations and one-point crossover.
• Codons (groups of bits mapped to an integer) are commonly fixed at 8 bits, proving a range of integers $\in [0,2^{8}-1]$ that is scaled to the range of rules using a modulo function.
• Additional genetic operators may be used with variable-length representations such as codon segments, duplication (add to the end), number of codons selected at random, and deletion.

Code Listing

Listing (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:

• Non-terminals: $N={expr,op,pre_op}$
• Terminals: $T={+, -, \div, \times, x, 1.0}$
• Expression (program): $S=$<expr>

The production rules for the grammar in BNF are:

• <expr> $::=$ <expr><op><expr> , (<expr><op><expr>), <pre_op>(<expr>), <var>
• <op> $::=$ $+, -, \div, \times$
• <var> $::=$ x, 1.0

The algorithm uses point mutation and a codon-respecting one-point 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[i-1]
    p2 = selected[0] if i == selected.size-1
    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_depth-1) ? grammar["VAR"] : grammar[k]
        integer = integers[offset].modulo(set.size)
        offset = (offset==integers.size-1) ? 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

References

Primary Sources

Grammatical 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 More

O'Neill and Ryan provide a high-level 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

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