simulated_annealing.h

// Pallas Solver
// Copyright 2015. All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright notice,
//   this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice,
//   this list of conditions and the following disclaimer in the documentation
//   and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.
//
// Author: ryan.latture@gmail.com (Ryan Latture)

#ifndef PALLAS_SIMULATED_ANNEALING_H
#define PALLAS_SIMULATED_ANNEALING_H

#include <cfloat>

#include "pallas/cooling_schedule.h"
#include "pallas/history_concept.h"
#include "pallas/step_function.h"
#include "pallas/types.h"
#include "pallas/internal/state.h"
#include "pallas/internal/metropolis.h"
#include "pallas/scoped_ptr.h"


namespace pallas {
    class SimulatedAnnealing {
    public:
        struct Options {
            Options () {
                cooling_schedule_options = CoolingSchedule::Options();
                local_minimizer_options = GradientLocalMinimizer::Options();
                scoped_ptr<StepFunction> default_step(new DefaultStepFunction(1.0));
                step_function.swap(default_step);
                max_iterations = 1000;
                max_stagnant_iterations = 100;
                dwell_iterations = 20;
                minimum_cost = -DBL_MAX;
                is_silent = true;
                polish_output = false;
                history_save_frequency = 0;
            };

            void set_step_function(scoped_ptr<StepFunction>& user_step_function) {
                swap(user_step_function, step_function);
            };

            CoolingSchedule::Options cooling_schedule_options;

            GradientLocalMinimizer::Options local_minimizer_options;

            scoped_ptr<StepFunction> step_function;

            unsigned int max_iterations;

            unsigned int max_stagnant_iterations;

            unsigned int dwell_iterations;

            double minimum_cost;

            bool polish_output;

            bool is_silent;

            unsigned int history_save_frequency;
        };

        struct Summary {
            Summary();

            std::string BriefReport() const;
            std::string FullReport() const;
            TerminationType termination_type;
            CoolingScheduleType cooling_schedule;

            std::string message;
            double initial_cost;
            double final_cost;
            GradientLocalMinimizer::Summary local_minimization_summary;
            unsigned int num_parameters;
            unsigned int num_iterations;
            double total_time_in_seconds;
            double local_minimization_time_in_seconds;
            double step_time_in_seconds;
            double cost_evaluation_time_in_seconds;
            bool was_polished;
            HistorySeries history;
        };

        struct HistoryOutput {

            HistoryOutput(unsigned int iteration_number,
                          unsigned int stagnant_iterations,
                          double temperature,
                          const Vector &current_solution,
                          double best_cost,
                          const Vector &best_solution)
                    : iteration_number(iteration_number),
                      stagnant_iterations(stagnant_iterations),
                      temperature(temperature),
                      current_solution(current_solution),
                      best_cost(best_cost),
                      best_solution(best_solution) {}
            unsigned int iteration_number;
            unsigned int stagnant_iterations;
            double temperature;
            Vector current_solution;
            double best_cost;
            Vector best_solution;
        };

        SimulatedAnnealing() {};

        void Solve(const SimulatedAnnealing::Options& options,
                   const GradientProblem& problem,
                   double* parameters,
                   SimulatedAnnealing::Summary* global_summary);

    private:
        bool check_for_termination_(const SimulatedAnnealing::Options& options,
                                    std::string *message,
                                    TerminationType * termination_type);

        void prepare_final_summary_(SimulatedAnnealing::Summary *global_summary,
                                    const GradientLocalMinimizer::Summary &local_summary);

        scoped_ptr<CoolingSchedule> cooling_schedule_;
        internal::Metropolis metropolis_;
        internal::State current_state_;
        internal::State candidate_state_;
        internal::State global_minimum_state_;
        unsigned int num_iterations_;
        unsigned int num_stagnant_iterations_;
    };

    void Solve(const SimulatedAnnealing::Options& options,
               const GradientProblem& problem,
               double* parameters,
               SimulatedAnnealing::Summary* summary);

    void dump(const SimulatedAnnealing::HistoryOutput &h, HistoryWriter& writer);

} // namespace pallas

#endif // PALLAS_SIMULATED_ANNEALING_H