Clever Algorithms: Nature-Inspired Programming Recipes

By Jason Brownlee PhD

Home | Read Online

This is the ad-supported version of the book. Buy it now if you like it.

Gene Expression Programming

Gene Expression Programming, GEP.


Gene Expression Programming is a Global Optimization algorithm and an Automatic Programming technique, and it is an instance of an Evolutionary Algorithm from the field of Evolutionary Computation. It is a sibling of other Evolutionary Algorithms such as a the Genetic Algorithm as well as other Evolutionary Automatic Programming techniques such as Genetic Programming and Grammatical Evolution.


Gene Expression Programming is inspired by the replication and expression of the DNA molecule, specifically at the gene level. The expression of a gene involves the transcription of its DNA to RNA which in turn forms amino acids that make up proteins in the phenotype of an organism. The DNA building blocks are subjected to mechanisms of variation (mutations such as coping errors) as well as recombination during sexual reproduction.


Gene Expression Programming uses a linear genome as the basis for genetic operators such as mutation, recombination, inversion, and transposition. The genome is comprised of chromosomes and each chromosome is comprised of genes that are translated into an expression tree to solve a given problem. The robust gene definition means that genetic operators can be applied to the sub-symbolic representation without concern for the structure of the resultant gene expression, providing separation of genotype and phenotype.


The objective of the Gene Expression Programming algorithm is to improve the adaptive fit of an expressed program in the context of a problem specific cost function. This is achieved through the use of an evolutionary process that operates on a sub-symbolic representation of candidate solutions using surrogates for the processes (descent with modification) and mechanisms (genetic recombination, mutation, inversion, transposition, and gene expression) of evolution.


A candidate solution is represented as a linear string of symbols called Karva notation or a K-expression, where each symbol maps to a function or terminal node. The linear representation is mapped to an expression tree in a breadth-first manner. A K-expression has fixed length and is comprised of one or more sub-expressions (genes), which are also defined with a fixed length. A gene is comprised of two sections, a head which may contain any function or terminal symbols, and a tail section that may only contain terminal symbols. Each gene will always translate to a syntactically correct expression tree, where the tail portion of the gene provides a genetic buffer which ensures closure of the expression.

Algorithm (below) provides a pseudocode listing of the Gene Expression Programming algorithm for minimizing a cost function.

Input: Grammar, $Population_{size}$, $Head_{length}$, $Tail_{length}$, $P_{crossover}$, $P_{mutation}$
Output: $S_{best}$
Population $\leftarrow$ InitializePopulation($Population_{size}$, Grammar, $Head_{length}$, $Tail_{length}$)
For ($S_{i}$ $\in$ Population)
    $Si_{program}$ $\leftarrow$ DecodeBreadthFirst($Si_{genome}$, Grammar)
    $Si_{cost}$ $\leftarrow$ Execute($Si_{program}$)
$S_{best}$ $\leftarrow$ GetBestSolution(Population)
While ($\neg$StopCondition())
    Parents $\leftarrow$ SelectParents(Population, $Population_{size}$)
    Children $\leftarrow \emptyset$
    For ($Parent_{1}$, $Parent_{2}$ $\in$ Parents)
        $Si_{genome}$ $\leftarrow$ Crossover($Parent_{1}$, $Parent_{2}$, $P_{crossover}$)
        $Si_{genome}$ $\leftarrow$ Mutate($Si_{genome}$, $P_{mutation}$)
        Children $\leftarrow$ $S_{i}$
    For ($S_{i}$ $\in$ Children)
        $Si_{program}$ $\leftarrow$ DecodeBreadthFirst($Si_{genome}$, Grammar)
        $Si_{cost}$ $\leftarrow$ Execute($Si_{program}$)
    Population $\leftarrow$ Replace(Population, Children)
    $S_{best}$ $\leftarrow$ GetBestSolution(Children)
Return ($S_{best}$)
Pseudocode for GEP.


  • The length of a chromosome is defined by the number of genes, where a gene length is defined by $h + t$. The $h$ is a user defined parameter (such as 10), and $t$ is defined as $t = h (n-1) + 1$, where the $n$ represents the maximum arity of functional nodes in the expression (such as 2 if the arithmetic functions $\times, \div, -, +$ are used).
  • The mutation operator substitutes expressions along the genome, although must respect the gene rules such that function and terminal nodes are mutated in the head of genes, whereas only terminal nodes are substituted in the tail of genes.
  • Crossover occurs between two selected parents from the population and can occur based on a one-point cross, two point cross, or a gene-based approach where genes are selected from the parents with uniform probability.
  • An inversion operator may be used with a low probability that reverses a small sequence of symbols (1-3) within a section of a gene (tail or head).
  • A transposition operator may be used that has a number of different modes, including: duplicate a small sequences (1-3) from somewhere on a gene to the head, small sequences on a gene to the root of the gene, and moving of entire genes in the chromosome. In the case of intra-gene transpositions, the sequence in the head of the gene is moved down to accommodate the copied sequence and the length of the head is truncated to maintain consistent gene sizes.
  • A '?' may be included in the terminal set that represents a numeric constant from an array that is evolved on the end of the genome. The constants are read from the end of the genome and are substituted for '?' as the expression tree is created (in breadth first order). Finally the numeric constants are used as array indices in yet another chromosome of numerical values which are substituted into the expression tree.
  • Mutation is low (such as $\frac{1}{L}$), selection can be any of the classical approaches (such as roulette wheel or tournament), and crossover rates are typically high (0.7 of offspring)
  • Use multiple sub-expressions linked together on hard problems when one gene is not sufficient to address the problem. The sub-expressions are linked using link expressions which are function nodes that are either statically defined (such as a conjunction) or evolved on the genome with the genes.

Code Listing

Listing (below) provides an example of the Gene Expression Programming algorithm implemented in the Ruby Programming Language based on the seminal version proposed by Ferreira [Ferreira2001]. 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: Functions: $F=\{+,-,\div,\times,\}$ and Terminals: $T=\{x\}$.

The algorithm uses binary tournament selection, uniform crossover and point mutations. The K-expression is decoded to an expression tree in a breadth-first manner, which is then parsed depth first as a Ruby expression string for display and direct evaluation. 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.

def binary_tournament(pop)
  i, j = rand(pop.size), rand(pop.size)
  return (pop[i][:fitness] < pop[j][:fitness]) ? pop[i] : pop[j]

def point_mutation(grammar, genome, head_length, rate=1.0/genome.size.to_f)
  child =""
  genome.size.times do |i|
    bit = genome[i].chr
    if rand() < rate
      if i < head_length
        selection = (rand() < 0.5) ? grammar["FUNC"]: grammar["TERM"]
        bit = selection[rand(selection.size)]
        bit = grammar["TERM"][rand(grammar["TERM"].size)]
    child << bit
  return child

def crossover(parent1, parent2, rate)
  return ""+parent1 if rand()>=rate
  child = ""
  parent1.size.times do |i|
    child << ((rand()<0.5) ? parent1[i] : parent2[i])
  return child

def reproduce(grammar, selected, pop_size, p_crossover, head_length)
  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[:genome] = crossover(p1[:genome], p2[:genome], p_crossover)
    child[:genome] = point_mutation(grammar, child[:genome], head_length)
    children << child
  return children

def random_genome(grammar, head_length, tail_length)
  s = ""
  head_length.times do
    selection = (rand() < 0.5) ? grammar["FUNC"]: grammar["TERM"]
    s << selection[rand(selection.size)]
  tail_length.times { s << grammar["TERM"][rand(grammar["TERM"].size)]}
  return s

def target_function(x)
  return x**4.0 + x**3.0 + x**2.0 + x

def sample_from_bounds(bounds)
  return bounds[0] + ((bounds[1] - bounds[0]) * rand())

def cost(program, bounds, num_trials=30)
  errors = 0.0
  num_trials.times do
    x = sample_from_bounds(bounds)
    expression, score = program.gsub("x", x.to_s), 0.0
    begin score = eval(expression) rescue score = 0.0/0.0 end
    return 9999999 if score.nan? or score.infinite?
    errors += (score - target_function(x)).abs
  return errors / num_trials.to_f

def mapping(genome, grammar)
  off, queue = 0, []
  root = {}
  root[:node] = genome[off].chr; off+=1
  while !queue.empty? do
    current = queue.shift
    if grammar["FUNC"].include?(current[:node])
      current[:left] = {}
      current[:left][:node] = genome[off].chr; off+=1
      current[:right] = {}
      current[:right][:node] = genome[off].chr; off+=1
  return root

def tree_to_string(exp)
  return exp[:node] if (exp[:left].nil? or exp[:right].nil?)
  left = tree_to_string(exp[:left])
  right = tree_to_string(exp[:right])
  return "(#{left} #{exp[:node]} #{right})"

def evaluate(candidate, grammar, bounds)
  candidate[:expression] = mapping(candidate[:genome], grammar)
  candidate[:program] = tree_to_string(candidate[:expression])
  candidate[:fitness] = cost(candidate[:program], bounds)

def search(grammar, bounds, h_length, t_length, max_gens, pop_size, p_cross)
  pop = do
    {:genome=>random_genome(grammar, h_length, t_length)}
  pop.each{|c| evaluate(c, grammar, bounds)}
  best = pop.sort{|x,y| x[:fitness] <=> y[:fitness]}.first
  max_gens.times do |gen|
    selected ={|i| binary_tournament(pop)}
    children = reproduce(grammar, selected, pop_size, p_cross, h_length)
    children.each{|c| evaluate(c, grammar, bounds)}
    children.sort!{|x,y| x[:fitness] <=> y[:fitness]}
    best = children.first if children.first[:fitness] <= best[:fitness]
    pop = (children+pop).first(pop_size)
    puts " > gen=#{gen}, f=#{best[:fitness]}, g=#{best[:genome]}"
  return best

if __FILE__ == $0
  # problem configuration
  grammar = {"FUNC"=>["+","-","*","/"], "TERM"=>["x"]}
  bounds = [1.0, 10.0]
  # algorithm configuration
  h_length = 20
  t_length = h_length * (2-1) + 1
  max_gens = 150
  pop_size = 80
  p_cross = 0.85
  # execute the algorithm
  best = search(grammar, bounds, h_length, t_length, max_gens, pop_size, p_cross)
  puts "done! Solution: f=#{best[:fitness]}, program=#{best[:program]}"
Gene Expression Programming in Ruby


Primary Sources

The Gene Expression Programming algorithm was proposed by Ferreira in a paper that detailed the approach, provided a careful walkthrough of the process and operators, and demonstrated the the algorithm on a number of benchmark problem instances including symbolic regression [Ferreira2001].

Learn More

Ferreira provided an early and detailed introduction and overview of the approach as book chapter, providing a step-by-step walkthrough of the procedure and sample applications [Ferreira2002]. A more contemporary and detailed introduction is provided in a later book chapter [Ferreira2005]. Ferreira published a book on the approach in 2002 covering background, the algorithm, and demonstration applications which is now in its second edition [Ferreira2006].


[Ferreira2001] C. Ferreira, "Gene Expression Programming: A New Adaptive Algorithm for Solving Problems", Complex Systems, 2001.
[Ferreira2002] C. Ferreira, "Gene Expression Programming in Problem Solving", in Soft Computing and Industry: Recent Applications, pages 635–654, Springer-Verlag, 2002.
[Ferreira2005] C. Ferreira, "Gene Expression Programming and the Evolution of computer programs", in Recent Developments in Biologically Inspired Computing, pages 82–103, Idea Group Publishing, 2005.
[Ferreira2006] C. Ferreira, "Gene expression programming: Mathematical modeling by an artificial intelligence", Springer-Verlag, 2006.
Clever Algorithms: Nature-Inspired Programming Recipes

Free Course

Get one algorithm per week...
  • ...delivered to your inbox
  • ...described in detail
  • read at your own pace
Sign-up Now

Own A Copy

This 438-page ebook has...
  • ...45 algorithm descriptions
  • practice usage
  • ...pseudo code
  • ...Ruby code
  • ...primary sources
Buy Now

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

Clever Algorithms: Nature-Inspired Programming Recipes

Do you like Clever Algorithms?
Buy the book now.

© Copyright 2015. All Rights Reserved. | About | Contact | Privacy