wedding-planner/app/services/vns/engine.rb

# Copyright (C) 2024 Manuel Bustillo

module VNS
  class Engine
    class << self
      def sequence(elements)
        elements = elements.to_a
        (elements + elements.reverse).chunk(&:itself).map(&:first)
      end
    end

    def target_function(&function)
      @target_function = function
    end

    def add_perturbation(klass)
      @perturbations ||= Set.new
      @perturbations << klass
    end

    attr_writer :initial_solution

    def run
      raise 'No target function defined' unless @target_function
      raise 'No perturbations defined' unless @perturbations
      raise 'No initial solution defined' unless @initial_solution

      @best_solution = @initial_solution
      @best_score = @target_function.call(@best_solution)

      self.class.sequence(@perturbations).each do |perturbation|
        optimize(perturbation)
      end

      @best_solution
    end

    private

    def optimize(perturbation_klass)
      loop do
        optimized = false

        perturbation_klass.new(@best_solution).each do |alternative_solution|
          score = @target_function.call(alternative_solution)
          next if score >= @best_score

          @best_solution = alternative_solution.deep_dup
          @best_score = score
          optimized = true

          break
        end

        return unless optimized
      end
    end
  end
end