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, id, threads = 8, limit = nil) ⇒ TabuSearch

Returns a new instance of 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
213
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 171

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

  @ranges = parameter_ranges
  @id = id

  # 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 = true
  @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_numeric
  vy = @recent_scores.reverse.to_numeric
  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 



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

def backtrack
  @backtracks += 1.0
  @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



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

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



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

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

Returns:

  • (Boolean) 


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

def finished?
  return false unless @threads.all? do |t|
    t.recent_scores.size == @jump_cutoff
  end
  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

Returns:

  • (Boolean) 


429
430
431
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 429

def knows_starting_point?
  true
end

#load_next_thread ⇒ Object 



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

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 



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

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 



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

def log_setup
  if @log_data
    require 'csv'
    @logfiles[:standard_deviations] = CSV.open("#{@id}_standard_deviations.csv", 'w')
    @logfiles[:best] = CSV.open("#{@id}_best.csv", 'w')
    @logfiles[:score] = CSV.open("#{@id}_score.csv", 'w')
    @logfiles[:params] = CSV.open("#{@id}_params.csv", 'w')
  end
end

#log_teardown ⇒ Object 



456
457
458
459
460
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 456

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 



470
471
472
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 470

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



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

def recent_scores_combination_test
  combinations =
  @threads.map{ |t| t.recent_scores.to_numeric }.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



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

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



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

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

#select_starting_point ⇒ Object 



466
467
468
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 466

def select_starting_point
  self.random_start_point
end

#setup(start_point) ⇒ Object

initialize



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

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

#setup_threads ⇒ Object

run_one_iteration



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
262
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 236

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 



462
463
464
 
# File 'lib/biopsy/optimisers/tabu_search.rb', line 462

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

#update_best? ⇒ Boolean

Returns:

  • (Boolean) 


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

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



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

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



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

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 



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

def write_data
  require 'csv'
  pathmod = Settings.instance.no_tempdirs ? '' : '../'
  path = File.expand_path("#{pathmod}#{@id}_scores.csv")
  CSV.open(path, "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
  # puts "wrote TabuSearch run data to #{path}"
end