Class: Biopsy::TabuSearch

Inherits:
Object
  • Object
show all
Defined in:
lib/biopsy/optimisers/tabu_search.rb

Overview

A Tabu Search implementation with a domain-specific probabilistic learning heuristic for optimising over an unconstrained parameter space with costly objective evaluation.

Defined Under Namespace

Classes: Thread

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(parameter_ranges, threads = 8, limit = nil) ⇒ TabuSearch 



171
172
173
174
175
176
177
178
179
180
181
182
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
210
211
212
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 171

def initialize(parameter_ranges, threads=8, limit=nil)

  @ranges = parameter_ranges

  # solution tracking
  @best = nil

  # tabu list
  @tabu = Set.new
  @tabu_limit = nil
  @start_time = Time.now

  # neighbourhoods
  @max_hood_size = 5
  @starting_sd_divisor = 5
  @standard_deviations = {}
  @sd_increment_proportion = 0.05
  @hood_no = 1

  # adjustment tracking
  @recent_scores = []
  @jump_cutoff = 10

  # logging
  @score_history = []
  @best_history = []
  @log_data = false
  @logfiles = {}
  self.log_setup

  # backtracking
  @iterations_since_best = 0
  @backtrack_cutoff = 2
  @backtracks = 1.0

  # convergence
  @num_threads = 5
  @threads = []
  @convergence_alpha = 0.05
  @global_best = {:parameters => nil, :score => nil}

end

Instance Attribute Details

#backtrack_cutoff ⇒ Object

Returns the value of attribute backtrack_cutoff.



163
164
165
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 163

def backtrack_cutoff
  @backtrack_cutoff
end

#best ⇒ Object (readonly)

< OptmisationAlgorithm



161
162
163
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 161

def best
  @best
end

#current ⇒ Object (readonly)

< OptmisationAlgorithm



161
162
163
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 161

def current
  @current
end

#hood_no ⇒ Object (readonly)

< OptmisationAlgorithm



161
162
163
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 161

def hood_no
  @hood_no
end

#jump_cutoff ⇒ Object

Returns the value of attribute jump_cutoff.



163
164
165
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 163

def jump_cutoff
  @jump_cutoff
end

#max_hood_size ⇒ Object

Returns the value of attribute max_hood_size.



162
163
164
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 162

def max_hood_size
  @max_hood_size
end

#sd_increment_proportion ⇒ Object

Returns the value of attribute sd_increment_proportion.



162
163
164
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 162

def sd_increment_proportion
  @sd_increment_proportion
end

#starting_sd_divisor ⇒ Object

Returns the value of attribute starting_sd_divisor.



163
164
165
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 163

def starting_sd_divisor
  @starting_sd_divisor
end

Instance Method Details

#adjust_distributions_using_gradient ⇒ Object

use the gradient of recent best scores to update the distributions



369
370
371
372
373
374
375
376
377
378
379
380
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 369

def adjust_distributions_using_gradient
  return if @recent_scores.length < 3
  vx = (1..@recent_scores.length).to_a.to_scale
  vy = @recent_scores.reverse.to_scale
  r = Statsample::Regression::Simple.new_from_vectors(vx,vy)
  slope = r.b
  if slope > 0
    @distributions.each_pair { |k, d| d.tighten slope }
  elsif slope < 0
    @distributions.each_pair { |k, d| d.loosen slope }
  end
end

#backtrack ⇒ Object 



356
357
358
359
360
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 356

def backtrack
  @backtracks += 1.0
  # debug('backtracked to best')
  @distributions.each_pair { |k, d| d.tighten }
end

#backtrack_or_continue ⇒ Object

return the correct ‘best’ location to form a new neighbourhood around deciding whether to continue progressing from the current location or to backtrack to a previous good location to explore further



340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 340

def backtrack_or_continue
  best = nil
  if (@iterations_since_best / @backtracks) >= @backtrack_cutoff * @max_hood_size
    self.backtrack
    best = @best
  else
    best = @current_hood.best
    self.adjust_distributions_using_gradient
  end
  if best[:parameters].nil?
    # this should never happen!
    best = @best        
  end
  best
end

#define_neighbourhood_structure ⇒ Object

use probability distributions to define the initial neighbourhood structure



299
300
301
302
303
304
305
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 299

def define_neighbourhood_structure
  # probabilities
  @distributions = {}
  @current[:parameters].each_pair do |param, value|
    self.update_distribution(param, value)
  end
end

#finished? ⇒ Boolean

check termination conditions and return true if met



403
404
405
406
407
408
409
410
411
412
413
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 403

def finished?
  return false unless @threads.all? { |t| t.recent_scores.size == @jump_cutoff }
  probabilities = self.recent_scores_combination_test
  n_significant = 0
  probabilities.each do |mann_u, levene| 
    if mann_u <= @adjusted_alpha && levene <= @convergence_alpha
      n_significant += 1 
    end
  end
  finish = n_significant >= probabilities.size * 0.5
end

#knows_starting_point? ⇒ Boolean

True if this algorithm chooses its own starting point



427
428
429
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 427

def knows_starting_point?
  true
end

#load_next_thread ⇒ Object 



263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 263

def load_next_thread
  thread = @threads[@current_thread]
  if thread.loaded
    thread.members.each do |sym|
      ivar = self.sym_to_ivar_sym sym
      thread[sym] = self.instance_variable_get(ivar)
    end
  else
    thread.loaded = true
  end
  @current_thread = (@current_thread + 1) % @num_threads
  thread = @threads[@current_thread]
  thread.members.each do |sym|
    ivar = self.sym_to_ivar_sym sym
    self.instance_variable_set(ivar, thread[sym])
  end
end

#log ⇒ Object 



441
442
443
444
445
446
447
448
449
450
451
452
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 441

def log
  if @current[:score]
    @score_history << @current[:score]
    @best_history << @best[:score]
  end
  if @log_data
    @logfiles[:standard_deviations] << @distributions.map { |k, d| d.sd }
    @logfiles[:best] << [@best[:score]]
    @logfiles[:score] << [@current[:score]]
    @logfiles[:params] << @current[:parameters].map { |k, v| v }
  end
end

#log_setup ⇒ Object 



431
432
433
434
435
436
437
438
439
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 431

def log_setup
  if @log_data
    require 'csv'
    @logfiles[:standard_deviations] = CSV.open('standard_deviations.csv', 'w')
    @logfiles[:best] = CSV.open('best.csv', 'w')
    @logfiles[:score] = CSV.open('score.csv', 'w')
    @logfiles[:params] = CSV.open('params.csv', 'w')
  end
end

#log_teardown ⇒ Object 



454
455
456
457
458
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 454

def log_teardown
  @logfiles.each_pair do |k, f|
    f.close
  end
end

#next_candidate ⇒ Object

get the next neighbour to explore from the current hood



391
392
393
394
395
396
397
398
399
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 391

def next_candidate
  @current[:parameters] = @current_hood.next
  @current[:score] = nil
  # exhausted the neighbourhood?
  if @current_hood.last?
    # debug(@current_hood.best)
    self.next_hood
  end
end

#next_hood ⇒ Object

shift to the next neighbourhood



383
384
385
386
387
388
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 383

def next_hood
  @hood_no += 1
  # debug("entering hood # #{@hood_no}")
  self.update_neighbourhood_structure
  @current_hood = Hood.new(@distributions, @max_hood_size, @tabu)
end

#random_start_point ⇒ Object 



468
469
470
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 468

def random_start_point
  Hash[@ranges.map { |p, r| [p, r.sample] }] 
end

#recent_scores_combination_test ⇒ Object

returns a matrix of correlation probabilities for recent scores between all threads



417
418
419
420
421
422
423
424
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 417

def recent_scores_combination_test
  combinations = 
  @threads.map{ |t| t.recent_scores.to_scale }.combination(2).to_a
  combinations.map do |a, b|
    [Statsample::Test.u_mannwhitney(a, b).probability_exact,
     Statsample::Test::Levene.new([a,b]).probability]
  end
end

#run_one_iteration(parameters, score) ⇒ Object

given the score for a parameter set, return the next parameter set to be scored



222
223
224
225
226
227
228
229
230
231
232
233
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 222

def run_one_iteration(parameters, score)
  @current = {:parameters => parameters, :score => score}
  # update best score?
  self.update_best?
  # log any data
  self.log
  # cycle threads
  self.load_next_thread
  # get next parameter set to score
  self.next_candidate
  @current[:parameters]
end

#sd_for_param(param, range) ⇒ Object

return the standard deviation to use for :param



333
334
335
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 333

def sd_for_param(param, range)
  @standard_deviations.empty? ? (range.size.to_f / @starting_sd_divisor) : @standard_deviations[param]
end

#select_starting_point ⇒ Object 



464
465
466
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 464

def select_starting_point
  self.random_start_point
end

#setup(start_point) ⇒ Object

initialize



214
215
216
217
218
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 214

def setup start_point
  @current = {:parameters => start_point, :score => nil}
  @best = @current
  self.setup_threads
end

#setup_threads ⇒ Object

run_one_iteration



235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 235

def setup_threads
  @num_threads.times do
    @threads << Thread.new
  end
  @threads.each do |thread|
    @current = {
      :parameters => self.random_start_point,
      :score => nil
    }
    @best = @current
    @standard_deviations = {}
    @recent_scores = []
    @score_history = []
    @best_history = []
    @tabu = Set.new
    self.define_neighbourhood_structure
    @current_hood = Biopsy::Hood.new(@distributions, @max_hood_size, @tabu)
    thread.members.each do |sym|
      ivar = self.sym_to_ivar_sym sym
      thread[sym] = self.instance_variable_get(ivar)
    end
    thread.loaded = false
  end
  @current_thread = @num_threads - 2
  # adjust the alpha for multiple testing in convergence
  @adjusted_alpha = @convergence_alpha / @num_threads
end

#sym_to_ivar_sym(sym) ⇒ Object 



460
461
462
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 460

def sym_to_ivar_sym sym
  "@#{sym.to_s}".to_sym
end

#update_best? ⇒ Boolean 



281
282
283
284
285
286
287
288
289
290
291
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 281

def update_best?
  @current_hood.update_best? @current
  if @best[:score].nil? || @current[:score] > @best[:score]
    @best = @current.clone
  else
    @iterations_since_best += 1
  end
  if @global_best[:score].nil? || @best[:score] > @global_best[:score]
    @global_best = @best.clone
  end
end

#update_distribution(param, value) ⇒ Object

set the distribution for parameter :param to a new one centered around the index of value



322
323
324
325
326
327
328
329
330
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 322

def update_distribution(param, value)
  mean = @ranges[param].index(value)
  range = @ranges[param]
  sd = self.sd_for_param(param, range)
  @distributions[param] = Biopsy::Distribution.new(mean, 
                                                  range,
                                                  @sd_increment_proportion,
                                                  sd)
end

#update_neighbourhood_structure ⇒ Object

update the neighbourhood structure by adjusting the probability distributions according to total performance of each parameter



309
310
311
312
313
314
315
316
317
318
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 309

def update_neighbourhood_structure
  self.update_recent_scores
  best = self.backtrack_or_continue
  unless @distributions.empty?
    @standard_deviations = Hash[@distributions.map { |k, d| [k, d.sd] }]
  end
  best[:parameters].each_pair do |param, value|
    self.update_distribution(param, value)
  end
end

#update_recent_scores ⇒ Object

update the array of recent scores



363
364
365
366
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 363

def update_recent_scores
  @recent_scores.unshift @best[:score]
  @recent_scores = @recent_scores.take @jump_cutoff
end

#write_data ⇒ Object 



472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 472

def write_data
  require 'csv'
  now = Time.now.to_i
  CSV.open("../#{now}_scores.csv", "w") do |c|
    c << %w(iteration thread score best)
    @threads.each_with_index do |t, t_idx|
      sh = t.score_history
      bh = t.best_history
      sh.zip(bh).each_with_index do |pair, i|
        c << [i, t_idx] + pair
      end
    end
  end
  path = File.expand_path("../#{now}_scores.csv")
  puts "wrote TabuSearch run data to #{path}"
end