Top Level Namespace

Defined Under Namespace

Modules: Charlie, EdgeRecombinationCrossover, Enumerable, GABenchmark, GPTreeHelper, GladiatorialSelection, InsertionMutator, InversionMutator, MatrixUniformCrossover, NullCrossover, NullMutator, PartiallyMappedCrossover, PermutationCrossover, RandomSelection, RotationMutator, RouletteSelection, SinglePointCrossover, TranspositionMutator, TreeChopMutator, TreeCrossover, TreeInsertNodeMutator, TreeRemoveNodeMutator, TreeTerminalMutator, UniformCrossover Classes: Array, Genotype, Module, Numeric, Population, String, Symbol, Table

Constant Summary collapse

TruncationSelection = 
TruncationSelection()
BestOnlySelection =

This selection algorithm is basically randomized hill climbing.

TruncationSelection(1)
ScaledRouletteSelection = 
ScaledRouletteSelection()
RankSelection = 
ScaledRouletteSelection()
TournamentSelection = 
TournamentSelection()
CoTournamentSelection = 
CoTournamentSelection()
TreeReplaceMutator = 
TreeReplaceMutator()
TreePruneMutator = 
TreeReplaceMutator(0)
TreeNumTerminalMutator = 
TreeNumTerminalMutator()
TreeEvalMutator = 
TreeEvalMutator()
MatrixMutationStrategies =

The mutation strategies for MatrixMutator

{
  :probability => MMSPRB = Proc.new{|genes,pointmut,p| 
    p ||= 0.05
    genes.map!{|r| r.map!{|e| rand < p ? pointmut.call(e) : e } }
  },
  :expected_n => Proc.new{|genes,pointmut,n|             n ||= 3
    MMSPRB.call(genes,pointmut,n.to_f / (genes.size * genes[0].size))
  },
  :expected_n_per_row => Proc.new{|genes,pointmut,n|     n ||= 3
    MMSPRB.call(genes,pointmut,n.to_f / genes[0].size)
  },
  :expected_n_per_column => Proc.new{|genes,pointmut,n|  n ||= 3
    MMSPRB.call(genes,pointmut,n.to_f / genes.size)
  },
  :n_point => Proc.new{|genes,pointmut,n|
    n ||= 3
    s, r = genes.size, genes.rows;
    n.times{ i,j = rand(s).divmod(r); genes[i][j] = pointmut.call(genes[i][j]) }
  }
}
NN_TANH =

The tanh function is the default

proc{|x| Math.tanh x }
NN_SIGN =

The sign function is also commonly used

proc{|x| x>=0?1:-1 }
MutationStrategies =

The mutation strategies for ListMutator

  • :single_point : Mutates a single element

  • :n_point : Mutates a single element, n times. Example: :n_point, :n_point

  • :probability[ p=0.05 ] : Mutates each element with probability p

  • :expected_n : Mutates each element with probability n/genes.size, i.e. such that the expected # of mutations is n

{  # TODO: change to default parameters in 1.9
  :probability => Proc.new{|genes,pointmut,p| 
    p ||= 0.05
    genes.map!{|e| rand < p ? pointmut.call(e) : e }
  },
  :expected_n => Proc.new{|genes,pointmut,n|
    n ||= 3
    p   = n.to_f / genes.size
    genes.map!{|e| rand < p ? pointmut.call(e) : e }
  },
  :single_point => Proc.new{|genes,pointmut|
    i = genes.rand_index
    genes[i] = pointmut.call(genes[i])
  },
  :n_point => Proc.new{|genes,pointmut,n|
    n ||= 3
    n.times{ i = genes.rand_index; genes[i] = pointmut.call(genes[i]) }
  }
}
PointMutators =

The point mutators for ListMutator

  • :flip : flips bit (x->1-x), use in BitStringGenotype

  • :replace[ c1,c2,…,cn ] : replaces the element with one of the arguments. use in StringGenotype. Example: :replace[ *‘a’..‘z’ ]

  • :uniform[ max_size=0.25 ]: adds a random number in the range [-max_size,+max_size], uniformly distributed.

  • :gaussian[ sigma=0.2 ] : adds a random number, gaussian distributed with standard deviation sigma

{
  :replace => proc{|x,*pos| pos.at_rand },
  :flip    => proc{|x| 1-x },
  :uniform => Proc.new{|x,max_size| max_size ||= 0.25;  x - max_size + max_size * 2 * rand },
  :gaussian=> Proc.new{|x,sigma|
     sigma ||= 0.2;
     delta = Math.sqrt(-2 * Math.log(rand)) * Math.cos(2 * Math::PI * rand)  # Box-Muller transformation
     x + delta * sigma
   }
}
TwoPointCrossover = 
NPointCrossover(2)
ThreePointCrossover = 
NPointCrossover(3)
BlendingCrossover = 
BlendingCrossover()

Instance Method Summary collapse

Instance Method Details

#BitMatrixGenotype(rows, columns = rows) ⇒ Object

Genotype for a 2D array of bits, for example: connection matrices for graphs



34
35
36
37
38
39
40
41
42
43
44
 
# File 'lib/charlie/list/matrix.rb', line 34

def BitMatrixGenotype(rows,columns=rows)
 Class.new(MatrixGenotype(rows,columns)) {
  def initialize
    self.genes = Array.new(rows){ Array.new(columns){  rand(2) } }
  end
  def to_s
    @genes.map{|r| r.map(&:to_s).join }.join("\n")
  end
  use MatrixMutator(:expected_n,:flip)
 }
end

#BitStringGenotype(n) ⇒ Object

Genotype of n bits. Individuals are initialized as an array of n random bits.



26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/charlie/list/list_genotype.rb', line 26

def BitStringGenotype(n)
 Class.new(Genotype) {
  [self,metaclass].each{|c| c.class_eval{ # include both in class and metaclass
   define_method(:size){ n }
  }}
  def initialize
    @genes = Array.new(size){ rand(2) }
  end
  def to_s
    @genes.map(&:to_s).join
  end
  use ListMutator(:expected_n,:flip), SinglePointCrossover.dup
 }
end

#BlendingCrossover(exploration_alpha = 0.1, type = :cube) ⇒ Object

Blending crossover, common in evolutionary strategies.

  • Given two parents x1(i), x2(i)

  • Returns two children with as i’th elements y(i)x1(i)+(1-y(i))x2(i) and y(i)x2(i)+(1-y(i))x1(i)

  • type=:cube takes y(i) independent, so children roughly within the hypercube spanned by the parents.

  • type=:line takes y(i)=y(1), so children roughly on the line between the parents.

  • exploration_alpha defines how far outside the hypercube/line spanned by the parents the children can be. (more specifically, y(i) = (1+2*alpha)*rand - alpha)



58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/charlie/list/list_crossover.rb', line 58

def BlendingCrossover(exploration_alpha=0.1,type=:cube)
  sz_rand = 1 + 2 * exploration_alpha
  Module.new{
    self.name = "BlendingCrossover(#{exploration_alpha},#{type})"
    if(type==:cube) 
      define_method(:cross){|parent1,parent2|
        c1 = []; c2=[]; g1 = parent1.genes; g2 = parent2.genes
        g1.each_with_index{|e,i|
          y  = rand*sz_rand - exploration_alpha 
          x2 = g2[i]
          c1 << y*e  + (1-y)*x2
          c2 << y*x2 + (1-y)*e
        }
        [c1,c2].map{|x| from_genes(x) }
      }
    elsif(type==:line) 
      define_method(:cross){|parent1,parent2|
        c1 = []; c2=[]; g1 = parent1.genes; g2 = parent2.genes
        y  = rand*sz_rand - exploration_alpha 
        g1.each_with_index{|e,i|
          x2 = g2[i]
          c1 << y*e  + (1-y)*x2
          c2 << y*x2 + (1-y)*e
        } 
        [c1,c2].map{|x| from_genes(x) }
      }
    else 
      raise ArgumentError,"Invalid BlendingCrossover type #{type}"
    end
  }
end

#CoTournamentSelection(group_size = 4, full_tournament = false, n_times = nil) ⇒ Object

Co-evolution: competition in tournaments selection.

  • Define a fight_points(other) function in your genotype to use this. The function should return [points for self,points for other]

  • Point-proportial selection is used within tournaments. Entire groups are replaced.

  • full_tournament = true calls both fight_points(population,population) AND fight_points(population,population) instead of only i < j

Does this n_times. n_times==nil takes population size / group_size , i.e. about the same number of new individuals as roulette selection etc.



191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
 
# File 'lib/charlie/selection.rb', line 191

def CoTournamentSelection(group_size=4,full_tournament=false,n_times=nil)
  Module::new{
    @@group_size = group_size
    @@full_tournament = full_tournament
    @@n_times    = n_times
    def next_generation(population)
      n_times = @@n_times || (population.size / @@group_size)     #(population.size / (@@group_size-2))
      n_times.times{
        population.shuffle!
        points = Array.new(@@group_size,0.0)
        for i in 0...@@group_size
         for j in 0...@@group_size
          next if j==i || (i > j && !@@full_tournament)
          r = population[i].fight_points(population[j])
          points[i] += r[0]
          points[j] += r[1]
         end
        end
       # points-proportional selection, with replacement b.c. 1 individual with 100% of the points is not implausible.

        partial_sum = []; sum = 0; points.each{|p| partial_sum << (sum += p) }
        partial_sum.map!{|x|x+1} if sum.abs < 1e-10 # sum==0 -> random
        newgroup = [];
        (@@group_size / 2.0).ceil.times{ 
          sel_ix = [0,0].map{ r=rand*sum; partial_sum.find_index{|ps| ps >= r } }
          newgroup += yield(population[sel_ix[0]],population[sel_ix[1]])
        }
        population[0...@@group_size] = newgroup[0...@@group_size]
      }
      population
    end
    self.name= "CoTournamentSelection(#{group_size},#{full_tournament},#{n_times.inspect})"
  }
end

#Elitism(sel_module, elite_n = 1) ⇒ Object

Generates a selection module with elitism from a normal selection module. Elitism is saving the best elite_n individuals each generation, to ensure the best solutions are never lost.



6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
# File 'lib/charlie/1.9fixes.rb', line 6

def Elitism(sel_module,elite_n=1) # :nodoc:
 ng_name = sel_module.to_s.gsub(/[^A-Za-z0-9]/,'_')
 Module.new{
  include sel_module
  alias_method ng_name, :next_generation
  @@elite_n = elite_n
  define_method :next_generation, ->(population,&block){
    population = population.sort_by(&:fitness)
    best = population[-@@elite_n..-1]
    population = send(ng_name,population,&block)
    # reset old best elite_n, but don't overwrite better ones
    population[-@@elite_n..-1] = best.zip_with(population[-@@elite_n..-1]){|old,new| [old,new].max }
    population
  }
  self.name= "Elitism(#{sel_module.to_s},#{elite_n})"
 }
end

#FloatListGenotype(n, range = 0..1) ⇒ Object

Genotype of n floats in the range range. Individuals are initialized as an array of n random numbers in this range. Note that mutations may cross range min/max.



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
# File 'lib/charlie/list/list_genotype.rb', line 8

def FloatListGenotype(n,range=0..1)
 Class.new(Genotype) {
  @@range = range
  [self,metaclass].each{|c| c.class_eval{ # include both in class and metaclass
   define_method(:size){ n }
  }}
  def initialize
    @genes = Array.new(size){ rand * (@@range.end - @@range.begin) + @@range.begin }
  end
  def to_s
    @genes.inspect
  end
  use ListMutator(), SinglePointCrossover.dup
 }
end

#FloatMatrixGenotype(rows, columns = rows, range = 0..1) ⇒ Object

Genotype for a 2D array of floats.



20
21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/charlie/list/matrix.rb', line 20

def FloatMatrixGenotype(rows,columns=rows,range=0..1)
 Class.new(MatrixGenotype(rows,columns)) {
  @@range = range
  def initialize
    self.genes = Array.new(rows){ Array.new(columns){  rand * (@@range.end - @@range.begin) + @@range.begin } }
  end
  def to_s
    @genes.inspect
  end
  use MatrixMutator()
 }
end

#GP(sel_module, crossover_probability = 0.75) ⇒ Object

Uses GP-style evolution (i.e. crossover OR mutation instead of crossover AND mutation) with a selection method.

  • Works by discarding and replacing the block given to next_generation in Population#evolve_block

  • Is not mandatory for GP, and can just as easily be used for GA or not used in GP.

  • Bit of a strange place to do this, but works nicely with the benchmarking



131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
 
# File 'lib/charlie/population.rb', line 131

def GP(sel_module,crossover_probability=0.75)
 ng_name = sel_module.to_s.gsub(/[^A-Za-z0-9]/,'_')
 Module.new{
  include sel_module.dup
  alias_method ng_name, :next_generation
  define_method(:next_generation){|population|
    send(ng_name,population){|*parents|
      if rand < crossover_probability
        [*parents[0].class.cross(*parents)]
      else
        parents.map{|c| c.mutate }
      end
    }
  }
  self.name= "GP(#{sel_module.to_s},#{crossover_probability})"
 }
end

#ListMutator(strategy = :expected_n, point_mutator = :uniform) ⇒ Object

Generates a module which can be used as a mutator for array-based genotypes like FloatListGenotype, BitStringGenotype and StringGenotype

  • strategy should be one of the MutationStrategies, or a proc

  • point_mutator should be one of the PointMutators, or a proc

  • nil is equivalent to proc{} for the point mutator

Raises:

  • (ArgumentError) 


48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/charlie/list/list_mutate.rb', line 48

def ListMutator(strategy=:expected_n ,point_mutator=:uniform)
  strat, *strat_args = *strategy
  pm   , *pm_args    = *point_mutator

  pm ||= proc{}

  strat = MutationStrategies[strat.intern] unless strat.is_a? Proc
  pm    = PointMutators[pm.intern]         unless pm.is_a? Proc
  
  raise ArgumentError,"Invalid mutation strategy" if strat.nil?
  raise ArgumentError,"Invalid point mutator"     if point_mutator.nil?

  if pm_args.empty?
    point_mutator_with_args = pm    
  else
    point_mutator_with_args = proc{|*args| pm.call(*(args+pm_args) ) }
  end

  Module.new{
    define_method(:mutate!) {
      strat.call(@genes,point_mutator_with_args,*strat_args)
      self
    }
    self.name= "ListMutator(#{strategy.inspect},#{point_mutator.inspect})"
  }
end

#MatrixGenotype(rows, columns = rows) ⇒ Object

Generic ancestor for matrix genotypes



5
6
7
8
9
10
11
12
13
14
15
16
17
 
# File 'lib/charlie/list/matrix.rb', line 5

def MatrixGenotype(rows,columns=rows)
 Class.new(Genotype) {
  [self,metaclass].each{|c| c.class_eval{
   define_method(:rows)    { rows }
   define_method(:columns) { columns }
   define_method(:size)    { rows * columns }
  }}
  def genes=(g)
    @genes = g.map(&:dup)
  end
  use MatrixUniformCrossover.dup
 }
end

#MatrixMutator(strategy = :expected_n, point_mutator = :uniform) ⇒ Object

Generates a module which can be used as a mutator for matrix-based genotypes like FloatMatrixGenotype and BitMatrixGenotype

  • strategy should be one of the MatrixMutationStrategies, or a proc

  • point_mutator should be one of the PointMutators (like in ListMutator), or a proc

  • nil is equivalent to proc{} for the point mutator

Raises:

  • (ArgumentError) 


96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
# File 'lib/charlie/list/matrix.rb', line 96

def MatrixMutator(strategy=:expected_n ,point_mutator=:uniform)
  strat, *strat_args = *strategy
  pm   , *pm_args    = *point_mutator

  pm ||= proc{}

  strat = MatrixMutationStrategies[strat.intern] unless strat.is_a? Proc
  pm    = PointMutators[pm.intern]         unless pm.is_a? Proc
  
  raise ArgumentError,"Invalid mutation strategy" if strat.nil?
  raise ArgumentError,"Invalid point mutator"     if point_mutator.nil?

  if pm_args.empty?
    point_mutator_with_args = pm    
  else
    point_mutator_with_args = proc{|*args| pm.call(*(args+pm_args) ) }
  end

  Module.new{
    define_method(:mutate!) {
      strat.call(@genes,point_mutator_with_args,*strat_args)
      self
    }
    self.name= "MatrixMutator(#{strategy.inspect},#{point_mutator.inspect})"
  }
end

#NeuralNetworkGenotype(input_n, hidden_n, output_n = 1, scaling = 1.0, hidden_f = NN_TANH, output_f = NN_TANH) ⇒ Object

Genotype for neural networks with a single hidden layer.

  • Inherits FloatListGenotype

  • input_n, hidden_n, output_n are the number of neurons at each layer

  • scaling determines how the floats in genes relate to the weights of the links (important for mutation size, initial values).

    • input to hidden weights are (list element) multiplied by scaling / input_n

    • hidden to output weights are (list element) multiplied by scaling / hidden_n

  • hidden_f, output_f are the (usually sigmoidal) functions to determine the output of nodes.

    • Output of hidden node i is hidden_f( weights . input - threshold)

functions of the returned class:

  • output(input) - runs the neural network in some input



19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/charlie/list/neural.rb', line 19

def NeuralNetworkGenotype(input_n,hidden_n,output_n=1,scaling=1.0,hidden_f=NN_TANH,output_f=NN_TANH)
  links_n = hidden_n * (input_n + output_n)
  thr_n = hidden_n  + output_n
  Class.new(FloatListGenotype(links_n+thr_n, -1..1 )) {
    define_method(:output){|input|
      raise ArgumentError unless input.size==input_n
      si = scaling / input_n
      sh = scaling / hidden_n

      wts = genes
      input = input.map{|i| i * si } # scale inputs instead of weights: same effect, but faster

      hidden_val = Array.new(hidden_n,0.0)
      output_val = Array.new(output_n,0.0)
      (0...hidden_n).each{|i|
        wi    = i * input_n
        thr = wts[links_n + i]
        v = 0.0
        (0...input_n).each{|j| v += input[j] * wts[wi + j] }
        hidden_val[i] = hidden_f.call(v - thr) * sh # again, scale this instead of hidden->output weights
      }
      oi = hidden_n * input_n
      (0...output_n).each{|i|
        wi = oi + i * hidden_n
        thr = wts[links_n + hidden_n + i]
        v = 0.0
        (0...hidden_n).each{|j| v +=  hidden_val[j] * wts[wi + j] }
        output_val[i] = output_f.call(v - thr)
      }
      output_val
    }
    use UniformCrossover.dup
  }
end

#NPointCrossover(n = 2) ⇒ Object

n point crossover, returns two children.



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/charlie/list/list_crossover.rb', line 14

def NPointCrossover(n=2)
 Module.new{
  self.name = "NPointCrossover(#{n})"
  define_method(:cross){|parent1,parent2|
    p1 = parent1.genes; p2 = parent2.genes
    upper_bnd = p1.size + 1
    cross_pts = (0...n).map{rand(upper_bnd)}.sort

    c1 = []; c2=[]
    ([0] + cross_pts << upper_bnd).each_cons(2){|cp1,cp2|
      c1 += p1[cp1...cp2]
      c2 += p2[cp1...cp2]
      p1,p2 = p2,p1
    }
    [c1,c2].map{|x| from_genes(x) }
  }
 }
end

#PCross(p, c1, c2 = NullCrossover) ⇒ Object

Takes crossover c1 with probability p, and crossover c2 with probability 1-p

Raises:

  • (ArgumentError) 


25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/charlie/crossover.rb', line 25

def PCross(p,c1,c2=NullCrossover)
  raise ArgumentError, "first argument to PCross should be numeric (probability)." unless p.is_a?(Numeric)
  return c1 if c1==c2
  c1_name, c2_name = [c1,c2].map{|c| '_cross_' + c.to_s.gsub(/[^A-Za-z0-9]/,'') }
  Module.new{
    include c1.dup # dup to avoid bugs on use PCross(..,c1) .. use c1
    alias_method c1_name, :cross
    include c2.dup
    alias_method c2_name, :cross

    define_method(:cross) {|*args|
      rand < p ? send(c1_name,*args) : send(c2_name,*args)
    }
    self.name= "PCross(#{p},#{c1},#{c2})"
  }
end

#PCrossN(hash) ⇒ Object

Variant of PCross for more than 2 crossovers.

  • Pass a hash of Module=>probability pairs. If sum(probability) < 1, NullCrossover will be used for the remaining probability.

  • example: PCrossN(SinglePointCrossover=>0.33,UniformCrossover=>0.33) for NullCrossover/SinglePointCrossover/UniformCrossover all with probability 1/3



45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/charlie/crossover.rb', line 45

def PCrossN(hash)
  tot_p = hash.inject(0){|s,(m,p)| s+p }
  if (tot_p - 1.0).abs > 0.01 # close to 1?
    raise ArgumentError, "PCrossN: sum of probabilities > 1.0" if tot_p > 1.0
    hash[NullCrossover] = (hash[NullCrossover] || 0.0) + (1.0 - tot_p)
  end
  partial_sums = hash.sort_by{|m,p| -p } # max probability first
  s = 0.0
  partial_sums.map!{|m,p| ['_cross_' + m.to_s.gsub(/[^A-Za-z0-9]/,'') , s+=p, m] }

  Module.new{
    partial_sums.each{|name,p,mod|
      include mod.dup
      alias_method name, :cross
    }
    define_method(:cross) {|*args|
      r = rand
      c_name = partial_sums.find{|name,p,mod| p >= r }.first
      send(c_name,*args)
    }
    self.name= "PCrossN(#{hash.inspect})"
  }
end

#PermutationGenotype(n, elements = 0...n) ⇒ Object

Generates a genotype class which represents a permutation of elements Includes the PermutationMutator and PermutationCrossover by default



5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
# File 'lib/charlie/permutation/permutation.rb', line 5

def PermutationGenotype(n,elements=0...n)
 elements = elements.chars if elements.is_a? String # string to array of chars
 elements = elements.to_a
 Class.new(Genotype) {
  define_method(:size)    { n }
  define_method(:elements){ elements }

  def initialize
    @genes = elements.dup.shuffle
  end

  def to_s
    @genes.inspect
  end
  use TranspositionMutator.dup , PCross(0.75,PermutationCrossover)
 }
end

#PMutate(p, m1, m2 = NullMutator) ⇒ Object

Takes mutator m1 with probability p, and mutator m2 with probability 1-p

Raises:

  • (ArgumentError) 


10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/charlie/mutate.rb', line 10

def PMutate(p,m1,m2=NullMutator)
  raise ArgumentError, "first argument to PMutate should be numeric (probability)." unless p.is_a?(Numeric)
  return m1 if m1==m2
  m1_name, m2_name = [m1,m2].map{|c| '_mutate_' + c.to_s.gsub(/[^A-Za-z0-9]/,'') + '!' }
  Module.new{
    include m1.dup # dup to avoid bugs on use PMutate(..,m1) .. use m1
    alias_method m1_name, :mutate!
    include m2.dup
    alias_method m2_name, :mutate!

    define_method(:mutate!) {
      rand < p ? send(m1_name) : send(m2_name)
    }
    self.name= "PMutate(#{p},#{m1},#{m2})"
  }
end

#PMutateN(hash) ⇒ Object

Variant of PMutate for more than 2 mutators

  • Pass a hash of Module=>probability pairs. If sum(probability) < 1, NullMutator will be used for the remaining probability.

  • example: PCrossN(SinglePointCrossover=>0.33,UniformCrossover=>0.33) for NullCrossover/SinglePointCrossover/UniformCrossover all with probability 1/3



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/charlie/mutate.rb', line 31

def PMutateN(hash)
  tot_p = hash.inject(0){|s,(m,p)| s+p }
  if (tot_p - 1.0).abs > 0.01 # close to 1?
    raise ArgumentError, "PMutateN: sum of probabilities > 1.0" if tot_p > 1.0
    hash[NullMutator] = (hash[NullMutator] || 0.0) + (1.0 - tot_p)
  end
  partial_sums = hash.sort_by{|m,p| -p } # max probability first
  s = 0.0
  partial_sums.map!{|m,p| ['_mutate_' + m.to_s.gsub(/[^A-Za-z0-9]/,'') + '!' , s+=p, m] }

  Module.new{
    partial_sums.each{|name,p,mod|
      include mod.dup
      alias_method name, :mutate!
    }
    define_method(:mutate!) {
      r = rand
      send partial_sums.find{|name,p,mod| p >= r }.first
    }
    self.name= "PMutateN(#{hash.inspect})"
  }
end

#ScaledRouletteSelection(&block) ⇒ Object

Scaled Roulette selection without replacement. Sorts by fitness, scales fitness by the values the given block yields for its index, then applies Roulette selection to the resulting fitness values. Default is Rank selection: {|x| x+1 }



83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
# File 'lib/charlie/selection.rb', line 83

def ScaledRouletteSelection(&block)
 Module.new{
  block = proc{|x|x+1} if block.nil?
  @@block = block
  @@index = nil
  @@index_size = 0 # population size used to generate index

  def next_generation(population)
 
   if @@index_size != population.size # build index, cache for constant population size
     @@index_size = population.size
     index = []
     (0...population.size).map(&@@block).each_with_index{|e,i| index += Array.new(e.round,i)  }
     @@index = index # ruby 1.9 fix, @@index can't be used in block(?) -- TODO:  figure out why
   end
   population = population.sort_by(&:fitness)

   new_pop = []
   index = @@index
   while new_pop.size < population.size
     i1 = index.at_rand
     i2 = index.at_rand
     if i1==i2
       i1,i2 = @@index.at_rand, @@index.at_rand until i1!=i2 # no replacement
     end
     new_pop += yield(population[i1],population[i2])
   end
   new_pop.pop until new_pop.size == population.size
   new_pop
  end

  self.name= "ScaledRouletteSelection[#{(0..3).map(&block).map(&:to_s).join(',')},...]"
 }
end

#SingleChild(crossover_module) ⇒ Object

Turns a two-children crossover module into a single-child crossover module. Usage: use SingleChild(UniformCrossover)



25
26
27
28
29
30
31
32
33
34
 
# File 'lib/charlie/1.9fixes.rb', line 25

def SingleChild(crossover_module) # :nodoc:
  crs_name =  '_cross_' + crossover_module.to_s.gsub(/[^A-Za-z0-9]/,'')
  Module.new{
    include crossover_module
    alias_method crs_name, :cross

    define_method(:cross){|*args| send(crs_name,*args).at_rand }
    self.name= "SingleChild(#{crossover_module})"
  }
end

#StringGenotype(n, elements) ⇒ Object

Genotype of n elements (not necessarily chars). Individuals are initialized as an array of n elements, each randomly chosen from the elements array.



43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/charlie/list/list_genotype.rb', line 43

def StringGenotype(n,elements)
 elements = elements.chars if elements.is_a? String # string to array of chars
 elements = elements.to_a
 Class.new(Genotype) {
  [self,metaclass].each{|c| c.class_eval{ # include both in class and metaclass
   define_method(:size){ n }
   define_method(:elements){ elements }
  }}
  def initialize
    @genes = Array.new(size){ elements.at_rand }
  end
  def to_s
    @genes.map(&:to_s).join
  end
  use ListMutator(:expected_n[2],:replace[*elements]), SinglePointCrossover.dup
 }
end

#TournamentSelection(group_size = 4, n_times = nil) ⇒ Object

Tournament selection

Default: selects the 2 individuals with the highest fitness out of a random population with size group_size and replaces the others with offspring of these 2.

Runs the selection for n_times. If n_times == nil (default), it sets it equal to population size / (group_size-2), i.e. about the same number of new individuals as roulette selection etc.



148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
 
# File 'lib/charlie/selection.rb', line 148

def TournamentSelection(group_size=4,n_times=nil)
  Module::new{
    @@group_size = group_size
    @@n_times    = n_times
    def next_generation(population)
      n_times = @@n_times || (population.size / (@@group_size-2))
      n_times.times{
        population.shuffle!
        ix = (0...@@group_size).sort_by{|i| population[i].fitness }
        p1,p2 = population[ix[-1]],population[ix[-2]]
        nw = []; 
        nw +=  yield(p1,p2) while nw.size < @@group_size-2
        (@@group_size-2).times{|i| population[ix[i]] = nw[i] }
      }
      population
    end
    self.name= "TournamentSelection(#{group_size},#{n_times.inspect})"
  }
end

#TreeEvalMutator(value_hash = Hash.new{0}) ⇒ Object

Replaces a random subtree by the result of its evaluation. value_hash is passed to eval_tree.



279
280
281
282
283
284
285
286
287
288
 
# File 'lib/charlie/tree/tree.rb', line 279

def TreeEvalMutator(value_hash=Hash.new{0})
 Module.new{
  self.name = "TreeEvalMutator(#{value_hash.inspect})"
  define_method(:mutate!) {
    st = random_subtree
    st.replace [:term,eval_tree(st,value_hash)]
    self
  }
 }
end

#TreeGenotype(terminals, unary_ops, binary_ops, init_depth = 3, init_type = :half) ⇒ Object

Tree genotype, for genetic programming etc.

  • Pass arrays of terminals/unary operators/binary operators to this function to generate a class.

  • terminals can be procs (eval’d on initialization), symbols (replaced by values in calls to eval_genes) or anything else (not changed, so make sure all operators are defined for these)

  • This needs more options. Depth of initial trees, etc. Also needs a better mutator.



73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
 
# File 'lib/charlie/tree/tree.rb', line 73

def TreeGenotype(terminals, unary_ops, binary_ops, init_depth = 3, init_type = :half)
  unary_ops  = nil if unary_ops.empty?
  Class.new(Genotype) {

    define_method(:unary_ops)  {unary_ops }
    define_method(:binary_ops) {binary_ops}
    define_method(:terminals)  {terminals }
    define_method(:init_depth) {init_depth}
    define_method(:init_type)  {init_type }

    def initialize
      self.genes = generate_random_tree(init_depth,init_type)
    end

    def genes=(g)
      class << g # ensures a genes.dup call is a deep copy
        def dup
          GPTreeHelper.dup_tree(self)
        end
      end
      @genes = g
    end

    def size
      tree_size(@genes)
    end

    def depth
      tree_depth(@genes)
    end


    # Generates a random tree.
    # * type = grow uses generate_random_tree_grow
    # * type = full uses generate_random_tree_full
    # * type = half uses one of them, with 50% probability each.
    def generate_random_tree(depth, type=:half)
      if type==:full || ( type == :half && rand < 0.5 )
        generate_random_tree_full(depth)
      else
        generate_random_tree_grow(depth,true)
      end
    end

    # Generates a random tree of a certain maximum depth.
    # * <tt>no_term=true</tt> makes sure the root node is a function.
    def generate_random_tree_grow(depth,no_term=nil)
      if depth.zero? || (rand(3).zero?  && !no_term)
        e = terminals.at_rand
        [:term, e.is_a?(Proc) ? e.call : e]
      else
        if unary_ops.nil? || rand(2).zero?
          [binary_ops.at_rand,generate_random_tree_grow(depth-1),generate_random_tree_grow(depth-1)]
        else
          [unary_ops.at_rand,generate_random_tree_grow(depth-1)]
        end
       end
    end

    # Generates a random tree, with all terminals at 'depth'.
    def generate_random_tree_full(depth)
      if depth.zero?
        e = terminals.at_rand
        [:term, e.is_a?(Proc) ? e.call : e]
      else
        if unary_ops.nil? || rand(2).zero?
          [binary_ops.at_rand,generate_random_tree_full(depth-1),generate_random_tree_full(depth-1)]
        else
          [unary_ops.at_rand,generate_random_tree_full(depth-1)]
        end
       end
    end

    def eval_genes(terminals_value_hash = {})
      eval_tree(@genes,terminals_value_hash)
    end

    def to_s
      @genes.inspect
    end

    use PCross(0.7,TreeCrossover), PMutate(0.5,TreeReplaceMutator) # TODO: test what options are best -- benchmark show that these are ok for simple settings.

    # make helper functions available at both class and instance level
    include GPTreeHelper
    class << self
      include GPTreeHelper
    end
  }
end

#TreeNumTerminalMutator(mutate = , &b) ⇒ Object

mutates a random numeric terminal using a point mutator (cf. ListMutator) or a block (e.g. {|x| x-rand+0.5}



255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
 
# File 'lib/charlie/tree/tree.rb', line 255

def TreeNumTerminalMutator(mutate=:uniform[0.1], &b)
 if block_given?
   mutate_proc = b
 else
  mut_name, *mut_arg = mutate
  mut_fn = PointMutators[mut_name]
  mutate_proc = proc{|x| mut_fn.call(x,*mut_arg) }
 end

 Module.new{
  self.name = "TreeNumTerminalMutator(#{mutate.inspect})"
  define_method(:mutate!) {
    numterms = all_terminals.select{|x| x[1].is_a? Numeric }
    unless numterms.empty?
      random_term = numterms.at_rand
      random_term[1] = mutate_proc.call(random_term[1])
    end
    self
  }
 }
end

#TreeReplaceMutator(depth = 2, type = :half) ⇒ Object

TreeReplaceMutator replaces a randomly chosen subtree with a new, randomly generated, subtree.

  • depth and type are arguments for TreeGenotype#generate_random_tree

  • depth == [1,2,3,..] or depth==(1..3) uses one of the elements in the range for the depth.

  • depth == :same to use the depth of the replaced subtree.

  • depth == :same for depth of the replaced subtree plus a random offset between min and max.



183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
 
# File 'lib/charlie/tree/tree.rb', line 183

def TreeReplaceMutator(depth=2,type=:half)
  Module.new{
     self.name = "TreeReplaceMutator(#{depth.inspect},#{type.inspect})"
    if depth.is_a? Numeric
      define_method(:mutate!) {
        random_subtree.replace generate_random_tree(depth,type)
        self
      }
    elsif depth==:same || (depth.is_a?(Array) && depth[0]==:same)
      s, dd_min, dd_max = *depth
      possible_deltas = (dd_min||0..dd_max||0).to_a
      define_method(:mutate!) {
        st = random_subtree
        st.replace generate_random_tree([tree_depth(st) + possible_deltas.at_rand,0].max, type)
        self
      }
    elsif depth.respond_to?(:to_a)
      possible_depths = depth.to_a
      define_method(:mutate!) {
        random_subtree.replace generate_random_tree(possible_depths.at_rand,type)
        self
      }
    else
      raise ArgumentError, "invalid option for depth"
    end
  }
end

#TruncationSelection(best = 0.3) ⇒ Object

Truncation selection takes the best invididuals with the highest fitness and crosses them randomly to replace all the others. best can be an float < 1 (fraction of population size), or a number >=1 (number of individuals)



17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/charlie/selection.rb', line 17

def TruncationSelection(best=0.3)
  Module.new{
    @@best = best
    def next_generation(population)
      k = if @@best >= 1  # best is an integer >= 1 -> select this much
            @@best.round
          else             # best is a float < 1 -> select this percentage
            [1,(@@best * population.size).round].max
          end
      n_new = population.size - k

      population = population.sort_by(&:fitness)
      best = population[-k..-1]
      new_pop = []
      new_pop += yield(best.at_rand,best.at_rand) while new_pop.size < n_new
      new_pop.pop until new_pop.size == n_new

      new_pop + best
    end
    self.name = "TruncationSelection(#{best})"
  }
end