Class: Operator::MutationSimplify

Inherits:
Object
  • Object
show all
Defined in:
../lib/mutation_simplify.rb

Overview

Algebraic simplification inspired by: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96.7953

MutationSimplify checks if the genotype-phenotype mapping tree contains the specific patterns and if it finds one it replaces the according part of the genotype with a new part folowing certain rules. The motivation is that the phenotype which represents the algebraic expression can be often simplified by algebraic rules eg.: 


 A * 1 -> A
 A * B + A * C -> A * (B + C)
 sin(0) -> 0
 ...
 etc.

This process incorporates a domain knowledge into the evolutionary process an may help to lower the average complexity of phenotypes. It can be seen as the kind of mutation so it is compatible with the mutation operator interface. The description of the patterns and replacements is stored in the yaml file with the syntax resembling ABNF grammar. MutationSimplify currently supports only DepthFirst and DepthLocus mappers.

The rules are stored in the YAML format file and read by the filename= method. The YAML file represents the array of modification rules, each rule is the YAML object which has the mandatory attributes (pattern, replacement) and can have optional attributes (comment, lambdas). Pattern and replacement attributes are arrays of derivation rules matching the grammar of the GE process. Symbols in pattern array have to be qualified in the form: 


 symbol.instance

The rule may have the right-hand side (it then represents a single derivation rule from the grammar) or the RHS may be omitted (the symbol.instance left-hand side then represents the subtree defined in the pattern section). If there are two occurences of the same subtree instances then both subtrees must match. See the example of the format: sample/toy_regression/simplify.yaml

Defined Under Namespace

Classes: Expansion, RuleCase, Subtree

Instance Attribute Summary (collapse)

Instance Method Summary (collapse)

Constructor Details

- (MutationSimplify) initialize(grammar)

Create the simplification operator. grammar is the valid grammar compatible with the simplification rules. 



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

def initialize grammar
  @grammar = grammar
  @rules = []
  @mapper_type = nil

  @grammar_texts = {}
  @grammar_texts2 = {}
  @grammar.each_pair do |symbol, alt| 
    rule = {}
    rule2 = {}       

    (0...alt.size).each do |i|
      rule[ alt_idx2text( symbol, i ) ] = i
      rule2[ alt2text( symbol, i ) ] = i         
    end

    @grammar_texts[symbol] = rule
    @grammar_texts2[symbol] = rule2       
  end
end

Instance Attribute Details

- (Object) mapper_type

must be set to DepthFirst or DepthLocus. Other mapper types are not supported. 



70
71
72
 
# File '../lib/mutation_simplify.rb', line 70

def mapper_type
  @mapper_type
end

- (Object) rules

Array of RuleCase structures representing the modification rules. See the class description for details. 



67
68
69
 
# File '../lib/mutation_simplify.rb', line 67

def rules
  @rules
end

Instance Method Details

- (Object) alt_idx2text(symbol, alt_idx) 



196
197
198
 
# File '../lib/mutation_simplify.rb', line 196

def alt_idx2text( symbol, alt_idx )
  (@grammar[symbol][alt_idx].map {|t| t.type == :symbol ? "<#{t.data}>" : t.data }).join     
end

- (Object) exp_args(track_reloc, matching, ptm) 



185
186
187
188
189
190
191
192
193
194
 
# File '../lib/mutation_simplify.rb', line 185

def exp_args( track_reloc, matching, ptm )
  res = []
  ptm.each_with_index do |node_idx,patt_idx|
    patt = matching[patt_idx]
    next unless patt.respond_to? 'alt_idx'
    next unless patt.alt_idx.nil? 
    res << alt_idx2text( patt.symbol, track_reloc[node_idx].alt_idx )
  end
  res
end

- (Object) filename=(fname)

Reads the modification rules from the YAML file. See the class description for details. 



74
75
76
 
# File '../lib/mutation_simplify.rb', line 74

def filename= fname
  @rules = parse_rules( YAML::load( File.open(fname) ) )
end

- (Object) match(track_reloc, patterns) 



101
102
103
104
105
106
107
108
 
# File '../lib/mutation_simplify.rb', line 101

def match( track_reloc, patterns )
  track_reloc.each_with_index do |node, index|
    next unless match_node?( node, patterns.first )
    ptm = match_patterns( track_reloc, patterns, index )
    return ptm unless ptm.empty?
  end
  []
end

- (Object) match_patterns(track_reloc, patterns, node_idx) 



110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
# File '../lib/mutation_simplify.rb', line 110

def match_patterns( track_reloc, patterns, node_idx )
  ptx = [node_idx]
  stack = [node_idx]

  patterns[1...patterns.size].each do |pattern|
    found = track_reloc.find { |n| n.back == stack.last and n.loc_idx == pattern.parent_arg }
    return [] if found.nil?       

    return [] if pattern.kind_of?(Expansion) and not match_node?( found, pattern )
    
    node_idx = track_reloc.index( found )
    ptx << node_idx

    case pattern.dir
    when -1
      stack.push node_idx
    when 0
    else
      pattern.dir.times { stack.pop }
    end

  end
  ptx
end

- (Object) mutation(parent, track)

Perform the mutation according the modification rules. See the class description for details. parent is the original genotype. track is the genotype-prenotype process track (see mappers descriptions). Return the mutated copy of the orig. genotype. 



82
83
84
85
86
87
88
89
90
91
92
93
 
# File '../lib/mutation_simplify.rb', line 82

def mutation( parent, track )
  mutant = wrapped_copy( parent, track )     
  track_reloc = reloc(track)     

  @rules.each do |rule|
    ptm = match( track_reloc, rule.match )
    next if ptm.empty?
    next unless check_equals( track_reloc, rule.equals, ptm )
    return replace( mutant, ptm, rule.match, rule.outcome, track_reloc )
  end
  mutant
end

- (Object) nodes_equal(track_reloc, node1_idx, node2_idx) 



175
176
177
178
179
180
181
182
183
 
# File '../lib/mutation_simplify.rb', line 175

def nodes_equal( track_reloc, node1_idx, node2_idx )
  tree1 = load_tree( track_reloc, node1_idx )
  tree2 = load_tree( track_reloc, node2_idx )
  return false if tree1.size != tree2.size
  tree1.each_with_index do |idx1,i|
    return false unless match_node?( track_reloc[idx1], track_reloc[tree2[i]] )
  end
  true
end

- (Object) parse_depths(patterns, refs, uses) 



250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
 
# File '../lib/mutation_simplify.rb', line 250

def parse_depths( patterns, refs, uses )
  stack = [ DepthStack.new( [refs.first], 0, 0 ) ]

  patterns.each_with_index do |pattern, index|
    raise "MutationSimplify: parsing error" if stack.empty?
    current_symb = stack.last.symbols.shift
    raise  "MutationSimplify: wrong order: required '#{refs[index]}', declared '#{current_symb}'" if current_symb != refs[index] 
    current_depth = stack.last.depth
    pattern.parent_arg = stack.last.loc
    stack.last.loc += 1

    stack.pop if stack.last.symbols.empty?

    expansions = uses[index].clone
    stack <<  DepthStack.new( expansions, current_depth-1, 0 ) unless expansions.empty?

    pattern.dir = stack.empty? ? -current_depth : stack.last.depth - current_depth
  end
  raise "MutationSimplify: some symbols undefined" unless stack.empty?
end

- (Object) parse_equals(refs) 



311
312
313
314
315
316
317
318
319
 
# File '../lib/mutation_simplify.rb', line 311

def parse_equals refs
  res = []
  refs.each_with_index do |ref,idx|
    for i in idx+1 ... refs.size
      res << [idx, i] if ref == refs[i]
    end
  end
  res
end

- (Object) parse_lambdas(texts, patterns, refs) 



271
272
273
274
275
276
277
278
279
280
281
282
283
 
# File '../lib/mutation_simplify.rb', line 271

def parse_lambdas( texts, patterns, refs )
  lambdas = {}
  var_idxs = []
  patterns.each_with_index { |p,i| var_idxs << i if p.alt_idx.nil? }     

  texts.each_pair do |key,value|
    text = "lambda do |a|\n#{value.clone}\nend"
    var_idxs.each_with_index { |v,i| text.gsub!( refs[v], "a[#{i}]" ) }
    lambdas[key] = eval(text)
  end

  lambdas
end

- (Object) parse_pattern(texts) 



220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
 
# File '../lib/mutation_simplify.rb', line 220

def parse_pattern texts
  patterns = []
  refs = []
  uses = [] 

  texts.each_with_index do |text,index|
    symb_dot,rule = text.split('=')
    symb_dot.strip!
    symb,dot = symb_dot.split('.')
    raise "MutationSimplify: '#{symb_dot}' must follow symbol.var syntax" if dot.nil?

    if rule.nil?
      # Subtree 
      patterns << Subtree.new()
      uses << []
    else
      # Expansion
      raise  "MutationSimplify: '#{symb_dot}' is defined more times" unless refs.index(symb_dot).nil?
      uses << rule.scan(/[a-zA-Z_\-][a-zA-Z0-9_\-]*\.[a-zA-Z_\-][a-zA-Z0-9_\-]*/)
      rule = rule.strip.gsub(/\.[a-zA-Z_\-][a-zA-Z0-9_\-]*/,'')
      alt_idx = (rule == '?') ? nil : text2alt( symb, rule )
      patterns << Expansion.new( symb, alt_idx )        
    end
    refs << symb_dot
   
  end
  
  return [patterns, refs, uses] 
end

- (Object) parse_replacement(texts, refs, lambdas) 



285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
 
# File '../lib/mutation_simplify.rb', line 285

def parse_replacement( texts, refs, lambdas )
  replacement = []

  texts.each do |line|
    idx = refs.index line.strip
    if idx.nil?
      symb,rule = line.split('=')
      raise "MutationSimplify: replacement '#{line}' unknown" if rule.nil?
      symb.strip!
      rule.strip!
      all,fn = /([a-zA-Z_\-][a-zA-Z0-9_\-]*)\(\)/.match(rule).to_a
      if fn.nil?
        alt_idx = text2alt( symb, rule )   
      else
        raise "MutationSimplify: unknown lambda '#{fn}()'" unless lambdas.has_key? fn
        alt_idx = lambdas[fn]
      end
      replacement << Expansion.new( symb, alt_idx )
    else
      replacement << idx
    end
  end

  replacement
end

- (Object) parse_rules(input) 



208
209
210
211
212
213
214
215
216
217
218
 
# File '../lib/mutation_simplify.rb', line 208

def parse_rules input
  rules = []
  input.each do |rule_case|
    patterns, refs, uses = parse_pattern rule_case['pattern']
    parse_depths( patterns, refs, uses )
    lambdas = rule_case.has_key?('lambdas') ? parse_lambdas( rule_case['lambdas'], patterns, refs ) : []
    replacement = parse_replacement( rule_case['replacement'], refs, lambdas )
    rules << RuleCase.new(patterns,replacement,parse_equals(refs))
  end
  rules
end

- (Object) reloc(track) 



162
163
164
165
166
167
168
169
170
171
172
173
 
# File '../lib/mutation_simplify.rb', line 162

def reloc track
  case @mapper_type     
  when 'DepthFirst'
    reloc_first track
  when 'DepthLocus'
    reloc_locus track
  when nil
    raise "MutationSimplify: mapper_type not selected"
  else
    raise "MutationSimplify: mapper_type not supported"
  end
end

- (Object) replace(genome, ptm, patterns, replacement, track_reloc) 



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
 
# File '../lib/mutation_simplify.rb', line 135

def replace( genome, ptm, patterns, replacement, track_reloc )
 args = exp_args( track_reloc, patterns, ptm )
 root_node = track_reloc[ptm.first]
 res = genome[0 ... root_node.from].clone

 replacement.each_with_index do |replacing,i|
   if replacing.kind_of? Expansion
     res << (i==0 ? root_node.loc_idx : 0) if @mapper_type == 'DepthLocus' # TODO: different Codon types?
     if replacing.alt_idx.respond_to? 'call'
       out = replacing.alt_idx.call args
       return genome.clone if out.nil?  
       res << text2alt_idx( replacing.symbol, out )
     else 
       res << replacing.alt_idx
     end
   else # replacing is the subtree index
     node = track_reloc[ ptm[replacing] ]
     subtree = genome[node.from .. node.to].clone
     subtree[0] = root_node.loc_idx if @mapper_type == 'DepthLocus' and i==0 # TODO: different Codon types?
     res.concat subtree
   end
 end

 res.concat genome[(root_node.to+1) ... genome.size] 
 res
end

- (Object) text2alt_idx(symbol, text, hash = @grammar_texts) 



200
201
202
203
204
205
206
 
# File '../lib/mutation_simplify.rb', line 200

def text2alt_idx( symbol, text, hash=@grammar_texts )
  found = hash[symbol]
  raise "MutationSimplify: altidx for symbol '#{symbol}' not found" if found.nil?
  res = found[text]
  raise "MutationSimplify: altidx for RuleAlt '#{text}' (symbol '#{symbol}') not found" if res.nil?
  res
end

- (Object) wrapped_copy(parent, track) 



95
96
97
98
99
 
# File '../lib/mutation_simplify.rb', line 95

def wrapped_copy( parent, track )
  mutant = []
  mutant += parent.clone while mutant.size < track.first.to+1
  mutant
end