tabu_search-01bag.rb

ITEMS = [
  { weight: 3, value: 200},
  { weight: 10, value: 500},
  { weight: 100, value: 30},
  { weight: 200, value: 2000},
  { weight: 300, value: 500},
  { weight: 50, value: 50},
  { weight: 190, value: 1000},
  { weight: 200, value: 1500},
]

MAX_WEIGHT = 400

class Unit
  attr_accessor :genome, :tabu_list, :tabu_size, :best_genome, :best_value

  def self.search(times = 10, tabu_size = 10)
    unit = self.random_new
    unit.tabu_size = tabu_size
    times.times { unit.search }
    unit.genome = unit.best_genome
    unit
  end

  def self.random_new
    self.new(ITEMS.map { rand(2) == 1 })
  end

  def initialize(genome)
    @genome = genome.dup
    @tabu_list = []
    @best_genome =genome.dup
    @best_value = value
  end

  def value
    total_value = 0
    total_weight = 0
    genome.each_with_index do |item, index|
      next unless item
      total_value += ITEMS[index][:value]
      total_weight += ITEMS[index][:weight]
    end
    return -total_weight if total_weight > MAX_WEIGHT
    total_value
  end

  def weight
    total_weight = 0

    genome.each_with_index do |item, index|
      next unless item
      total_weight += ITEMS[index][:weight]
    end

    return total_weight
  end

  def length
    genome.length
  end

  def search
    index, action, value = search_neighbour

    genome[index] = action
    if value > best_value
      self.best_value = value
      self.best_genome = genome.dup
    end

    id = "#{index}-#{action}"
    unless tabu_list.index(id)
      tabu_list << id
      tabu_list.shift if tabu_list.length > tabu_size
    end
  end

  def inspect
    "#{object_id} #{self.value}|#{self.weight} = #{genome.map {|i| i ? 1 : 0 }.join(', ')}"
  end


  private

  def search_neighbour
    actions = []
    length.times do |i|
      origin = genome[i]
      genome[i] = !origin
      actions << [i, !origin, value]
      genome[i] = origin
    end

    sort_actions = actions.sort_by {|i, a, f| -f }
    return sort_actions[0] if sort_actions[0][-1] > best_value

    sort_actions.each do |i, a, f|
      return [i, a, f] unless tabu_list.index("#{i}-#{a}")
    end
    return sort_actions.first
  end
end


require 'benchmark'

r = {}
Benchmark.bm do |x|
  x.report('a') do
    1000.times do
      unit = Unit.search(10, ITEMS.length - 1)
      print unit.inspect + "\r"
      r[unit.value] ||= 0
      r[unit.value] += 1
    end
    puts "\n"
  end
end

puts "\n100 times result: "
r.each do |val, times|
  puts "#{val}: #{times} times"
end