differential_evolution.h

Go to the documentation of this file.

// 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_DIFFERENTIAL_EVOLUTION_H
#define PALLAS_DIFFERENTIAL_EVOLUTION_H

#include <cfloat>

#include "pallas/history_concept.h"
#include "pallas/types.h"
#include "pallas/internal/crossover_strategy.h"
#include "pallas/internal/mutation_strategy.h"
#include "pallas/internal/shuffler.h"
#include "pallas/internal/state.h"

namespace pallas {

    class DifferentialEvolution {
    public:
        struct Options {
            Options() {
                local_minimizer_options = GradientLocalMinimizer::Options();
                mutation_strategy = BEST_1;
                crossover_strategy = BINOMIAL;
                population_initialization = LATIN_HYPERCUBE;
                max_iterations = 1000;
                population_size = 15;
                tolerance = 0.01;
                minimum_cost = -DBL_MAX;
                dither << 0.5, 1.0;
                crossover_probability = 0.7;
                is_silent = true;
                polish_output = false;
                history_save_frequency = 0;
            };

            GradientLocalMinimizer::Options local_minimizer_options;

            MutationStrategyType mutation_strategy;

            CrossoverStrategyType crossover_strategy;

            PopulationInitializationType population_initialization;

            unsigned int max_iterations;


            unsigned int population_size;

            double minimum_cost;

            Vector2d dither;

            Vector upper_bounds;

            Vector lower_bounds;

            double crossover_probability;

            double tolerance;

            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;
            MutationStrategyType mutation_strategy;

            CrossoverStrategyType crossover_strategy;

            std::string message;
            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 cost_evaluation_time_in_seconds;
            bool was_polished;
            HistorySeries history;
        };

        struct HistoryOutput {

            HistoryOutput(unsigned int iteration_number,
                          const std::vector<Vector> &population,
                          double best_cost,
                          const Vector &best_solution)
                    : iteration_number(iteration_number),
                      population(population),
                      best_cost(best_cost),
                      best_solution(best_solution) {}
            unsigned int iteration_number;
            std::vector<Vector> population;
            double best_cost;
            Vector best_solution;
        };

        DifferentialEvolution() {};

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

        void init_mutation_strategy_(MutationStrategyType type);

        void init_crossover_strategy_(CrossoverStrategyType type,
                                      double crossover_probability);

        void init_random_dither_(const Vector2d& dither);

        void init_population_(PopulationInitializationType type);

        void scale_parameters_(const Vector& trial_in, Vector& trial_out);

        void unscale_parameters_(const Vector& trial_in, Vector& trial_out);

        void ensure_constraint_(Vector& trial);

        void update_std_dev_();

        void mutate_(Vector& candidate, unsigned int idx);

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

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

        scoped_ptr<internal::MutationStrategy> mutation_strategy_;
        scoped_ptr<internal::CrossoverStrategy> crossover_strategy_;
        Vector upper_bounds_;
        Vector lower_bounds_;
        scoped_ptr< internal::RandomNumberGenerator< double > > random_number_;
        scoped_ptr< internal::RandomNumberGenerator< double > > random_dither_;
        scoped_ptr< internal::Shuffler > shuffler_;
        double scale_; 
        double fractional_std_dev_;
        Vector scale_arg1_;
        Vector scale_arg2_;
        Vector population_energies_;
        std::vector<Vector> population_;
        Eigen::VectorXi population_idx_;
        internal::State global_minimum_state_;
        unsigned int num_parameters_;
        unsigned int population_size_;
        unsigned int num_iterations_;
    };

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

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

} // namespace pallas

#endif // PALLAS_DIFFERENTIAL_EVOLUTION_H