class VNS::VNS

Constants

PERTURBATION_COUNT

Attributes

max_allocation[R]
people[R]
preferences[R]
sessions[R]

Public Class Methods

new(people, sessions, preferences, max_allocation, &inspection) click to toggle source
# File lib/vns.rb, line 11
def initialize(people, sessions, preferences, max_allocation, &inspection)
  @people = people.map.with_index { |person, i| Person.new(i, person) }
  @sessions = sessions.map.with_index { |session, i| Session.new(i, session) }
  @preferences = preferences
  @inspection = inspection
  @max_allocation = max_allocation
end

Public Instance Methods

print() click to toggle source
run() click to toggle source
# File lib/vns.rb, line 19
def run
  initial_groups = people.in_groups(sessions.count).map(&:compact)
  initial_solution = sessions.zip(initial_groups).to_h
  @solution = global_optimize(initial_solution)

  self
end
target_function(solution = @solution) click to toggle source
# File lib/vns.rb, line 41
def target_function(solution = @solution)
  return Float::INFINITY unless solution

  solution.map do |session, people|
    people.map do |person|
      preferences[person.id][session.id]
    end
  end.flatten.inject(:+)
end

Private Instance Methods

clone(solution) click to toggle source
# File lib/vns.rb, line 81
def clone(solution)
  solution.map do |k, v|
    [k, v.dup]
  end.to_h
end
combinations_of_two(solution) click to toggle source
# File lib/vns.rb, line 133
def combinations_of_two(solution)
  solution.values
          .combination(2)
          .map { |(a, b)| a.product(b) }
          .flatten(1)
end
feasible?(solution) click to toggle source
# File lib/vns.rb, line 144
def feasible?(solution)
  solution.values.all? { |group| group.size <= max_allocation }
end
find_session(solution, person) click to toggle source
# File lib/vns.rb, line 162
def find_session(solution, person)
  sessions.detect { |s| solution[s].include?(person) }
end
global_optimize(initial_solution) click to toggle source
# File lib/vns.rb, line 53
def global_optimize(initial_solution)
  best_solution = initial_solution

  first_solution = initial_solution.dup
  local_optimize(first_solution)

  puts "First solution => #{target_function(first_solution)}"
  best_solution = first_solution

  PERTURBATION_COUNT.times do |counter|
    temporary_solution = clone(best_solution)
    perturbate(temporary_solution)
    local_optimize(temporary_solution)

    puts "Perturbation #{counter + 1} => #{target_function(temporary_solution)} vs #{target_function(best_solution)}"

    if target_function(temporary_solution) < target_function(best_solution)
      puts 'Updated best solution'
      best_solution = temporary_solution
    end

    progress = (counter + 1) * 1.0 / PERTURBATION_COUNT
    @inspection&.call(progress, target_function(best_solution), public_format(best_solution))
  end

  best_solution
end
happiness(person) click to toggle source
# File lib/vns.rb, line 140
def happiness(person)
  preferences[person.id][find_session(@solution, person).id]
end
local_optimize(solution) click to toggle source
# File lib/vns.rb, line 87
def local_optimize(solution)
  shift_optimization(solution)
  swap_optimization(solution)
end
perturbate(solution) click to toggle source
# File lib/vns.rb, line 120
def perturbate(solution)
  2.times do
    extracted = []
    solution.each do |_, people|
      extracted << people.delete_at(rand(people.length))
    end

    extracted.shuffle.each_with_index do |person, i|
      solution.values[i] << person
    end
  end
end
public_format(solution) click to toggle source
# File lib/vns.rb, line 166
def public_format(solution)
  solution.map { |k, v| [k.name, v.map(&:name)] }.to_h
end
shift(solution, session, person) click to toggle source
# File lib/vns.rb, line 157
def shift(solution, session, person)
  solution[find_session(solution, person)].delete(person)
  solution[session] << person
end
shift_optimization(solution) click to toggle source
# File lib/vns.rb, line 92
def shift_optimization(solution)
  initial_value = target_function(solution)

  people.product(sessions).each do |(person, session)|
    original_session = find_session(solution, person)
    shift(solution, session, person)

    if feasible?(solution) && target_function(solution) < initial_value
      return local_optimize(solution)
    else
      shift(solution, original_session, person)
    end
  end
end
swap(solution, person1, person2) click to toggle source
# File lib/vns.rb, line 148
def swap(solution, person1, person2)
  session1 = find_session(solution, person1)
  session2 = find_session(solution, person2)
  solution[session1].delete(person1)
  solution[session2].delete(person2)
  solution[session1] << person2
  solution[session2] << person1
end
swap_optimization(solution) click to toggle source
# File lib/vns.rb, line 107
def swap_optimization(solution)
  initial_value = target_function(solution)

  combinations_of_two(solution).each do |(p1, p2)|
    swap(solution, p1, p2)
    if target_function(solution) < initial_value
      return local_optimize(solution)
    else
      swap(solution, p2, p1)
    end
  end
end