problem/base.h

/*****************************************************************************
 *   Copyright (C) 2004-2015 The PaGMO development team,                     *
 *   Advanced Concepts Team (ACT), European Space Agency (ESA)               *
 *                                                                           *
 *   https://github.com/esa/pagmo                                            *
 *                                                                           *
 *   act@esa.int                                                             *
 *                                                                           *
 *   This program is free software; you can redistribute it and/or modify    *
 *   it under the terms of the GNU General Public License as published by    *
 *   the Free Software Foundation; either version 2 of the License, or       *
 *   (at your option) any later version.                                     *
 *                                                                           *
 *   This program is distributed in the hope that it will be useful,         *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of          *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the           *
 *   GNU General Public License for more details.                            *
 *                                                                           *
 *   You should have received a copy of the GNU General Public License       *
 *   along with this program; if not, write to the                           *
 *   Free Software Foundation, Inc.,                                         *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.               *
 *****************************************************************************/

// 30/01/10 Created by Francesco Biscani.

#ifndef PAGMO_PROBLEM_BASE_H
#define PAGMO_PROBLEM_BASE_H

// This define was added for a MSVC compilation fix and later removed as it creates a potential
// problem when testing pagmo in debug
// #define BOOST_CB_DISABLE_DEBUG 

#include <algorithm>
#include <boost/circular_buffer.hpp>
#include <boost/numeric/conversion/cast.hpp>
#include <boost/shared_ptr.hpp>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <string>

#include "../config.h"
#include "../exceptions.h"
#include "../serialization.h"
#include "../types.h"
//#include "base_meta.h"

namespace pagmo
{
// Fwd declarations.
class population;
class island;


namespace problem {

class base;

typedef boost::shared_ptr<base> base_ptr;


class __PAGMO_VISIBLE base
{
                // Meta problems need to be able to access protected virtual functions
                friend class base_meta;
                // Underlying containers used for caching decision and fitness vectors.
                typedef boost::circular_buffer<decision_vector> decision_vector_cache_type;
                typedef boost::circular_buffer<fitness_vector> fitness_vector_cache_type;
                typedef boost::circular_buffer<constraint_vector> constraint_vector_cache_type;
        public:
                static const std::size_t cache_capacity = 5;
                typedef decision_vector::size_type size_type;
                typedef fitness_vector::size_type f_size_type;
                typedef constraint_vector::size_type c_size_type;
                base(int, int = 0, int = 1, int = 0, int = 0, const double & = 0);
                base(int, int, int, int, int, const std::vector<double> &);
                base(const double &, const double &, int, int = 0, int = 1, int = 0, int = 0, const double & = 0);
                base(const decision_vector &, const decision_vector &, int = 0, int = 1, int = 0, int = 0, const double & = 0);

                template <std::size_t N>
                base(const double (&v1)[N], const double (&v2)[N], int ni = 0, int nf = 1, int nc = 0, int nic = 0, const double &c_tol = 0):
                        m_i_dimension(boost::numeric_cast<size_type>(ni)),m_f_dimension(boost::numeric_cast<f_size_type>(nf)),
                        m_c_dimension(boost::numeric_cast<c_size_type>(nc)),m_ic_dimension(boost::numeric_cast<c_size_type>(nic)),
                        m_c_tol(nc,c_tol),
                        m_decision_vector_cache_f(boost::numeric_cast<decision_vector_cache_type::size_type>(cache_capacity)),
                        m_fitness_vector_cache(boost::numeric_cast<fitness_vector_cache_type::size_type>(cache_capacity)),
                        m_decision_vector_cache_c(boost::numeric_cast<decision_vector_cache_type::size_type>(cache_capacity)),
                        m_constraint_vector_cache(boost::numeric_cast<constraint_vector_cache_type::size_type>(cache_capacity))
                {
                        if (c_tol < 0) {
                                pagmo_throw(value_error,"constraints tolerance must be non-negative");
                        }
                        if (!m_f_dimension) {
                                pagmo_throw(value_error,"fitness dimension must be strictly positive");
                        }
                        if (m_ic_dimension > m_c_dimension) {
                                pagmo_throw(value_error,"inequality constraints dimension must not be greater than global constraints dimension");
                        }
                        construct_from_iterators(v1,v1 + N,v2,v2 + N);
                        if (m_i_dimension > m_lb.size()) {
                                pagmo_throw(value_error,"integer dimension must not be greater than global dimension");
                        }
                        // Resize properly temporary fitness and constraint storage.
                        m_tmp_f1.resize(m_f_dimension);
                        m_tmp_f2.resize(m_f_dimension);
                        m_tmp_c1.resize(m_c_dimension);
                        m_tmp_c2.resize(m_c_dimension);
                        // Normalise bounds.
                        normalise_bounds();
                }

                template <class Iterator1, class Iterator2>
                base(Iterator1 start1, Iterator1 end1, Iterator2 start2, Iterator2 end2, int ni = 0, int nf = 1, int nc = 0, int nic = 0, const double &c_tol = 0):
                        m_i_dimension(boost::numeric_cast<size_type>(ni)),m_f_dimension(boost::numeric_cast<f_size_type>(nf)),
                        m_c_dimension(boost::numeric_cast<c_size_type>(nc)),m_ic_dimension(boost::numeric_cast<c_size_type>(nic)),
                        m_c_tol(nc,c_tol),
                        m_decision_vector_cache_f(boost::numeric_cast<decision_vector_cache_type::size_type>(cache_capacity)),
                        m_fitness_vector_cache(boost::numeric_cast<fitness_vector_cache_type::size_type>(cache_capacity)),
                        m_decision_vector_cache_c(boost::numeric_cast<decision_vector_cache_type::size_type>(cache_capacity)),
                        m_constraint_vector_cache(boost::numeric_cast<constraint_vector_cache_type::size_type>(cache_capacity))
                {
                        if (c_tol < 0) {
                                pagmo_throw(value_error,"constraints tolerance must be non-negative");
                        }
                        if (!m_f_dimension) {
                                pagmo_throw(value_error,"fitness dimension must be strictly positive");
                        }
                        if (m_ic_dimension > m_c_dimension) {
                                pagmo_throw(value_error,"inequality constraints dimension must not be greater than global constraints dimension");
                        }
                        construct_from_iterators(start1,end1,start2,end2);
                        if (m_i_dimension > m_lb.size()) {
                                pagmo_throw(value_error,"integer dimension must not be greater than global dimension");
                        }
                        // Properly resize temporary fitness and constraint storage.
                        m_tmp_f1.resize(m_f_dimension);
                        m_tmp_f2.resize(m_f_dimension);
                        m_tmp_c1.resize(m_c_dimension);
                        m_tmp_c2.resize(m_c_dimension);
                        // Normalise bounds.
                        normalise_bounds();
                }
                virtual ~base();
                const decision_vector &get_lb() const;
                const decision_vector &get_ub() const;
                void set_bounds(const decision_vector &, const decision_vector &);

                template <class Iterator1, class Iterator2>
                void set_bounds(Iterator1 start1, Iterator1 end1, Iterator2 start2, Iterator2 end2)
                {
                        typedef typename std::iterator_traits<Iterator1>::difference_type d_type1;
                        typedef typename std::iterator_traits<Iterator2>::difference_type d_type2;
                        const d_type1 d1 = std::distance(start1,end1);
                        const d_type2 d2 = std::distance(start2,end2);
                        if (d1 != d2 || d1 != std::distance(m_lb.begin(),m_lb.end())) {
                                pagmo_throw(value_error,"invalid or inconsistent bounds dimensions in set_bounds()");
                        }
                        verify_bounds(start1,end1,start2,end2);
                        std::copy(start1,end1,m_lb.begin());
                        std::copy(start2,end2,m_ub.begin());
                        // Normalise bounds.
                        normalise_bounds();
                }

                template <std::size_t N>
                void set_bounds(const double (&v1)[N], const double (&v2)[N])
                {
                        if (m_lb.size() != N) {
                                pagmo_throw(value_error,"invalid bounds dimensions in set_bounds()");
                        }
                        verify_bounds(v1,v1 + N,v2,v2 + N);
                        std::copy(v1,v1 + N,m_lb.begin());
                        std::copy(v2,v2 + N,m_ub.begin());
                        // Normalise bounds.
                        normalise_bounds();
                }
                void set_bounds(const double &, const double &);
                void set_bounds(int, const double &, const double &);
                void set_lb(const decision_vector &);
                void set_lb(int, const double &);
                void set_lb(const double &);

                template <class Iterator>
                void set_lb(Iterator start, Iterator end)
                {
                        if (std::distance(start,end) != std::distance(m_lb.begin(),m_lb.end())) {
                                pagmo_throw(value_error,"invalid bounds dimension in set_lb()");
                        }
                        verify_bounds(start,end,m_ub.begin(),m_ub.end());
                        std::copy(start,end,m_lb.begin());
                        // Normalise bounds.
                        normalise_bounds();
                }

                template <std::size_t N>
                void set_lb(const double (&v)[N])
                {
                        if (N != m_lb.size()) {
                                pagmo_throw(value_error,"invalid bounds dimension in set_lb()");
                        }
                        verify_bounds(v,v + N,m_ub.begin(),m_ub.end());
                        std::copy(v,v + N,m_lb.begin());
                        // Normalise bounds.
                        normalise_bounds();
                }
                void set_ub(const decision_vector &);
                void set_ub(int, const double &);
                void set_ub(const double &);

                template <class Iterator>
                void set_ub(Iterator start, Iterator end)
                {
                        if (std::distance(start,end) != std::distance(m_lb.begin(),m_lb.end())) {
                                pagmo_throw(value_error,"invalid bounds dimension in set_ub()");
                        }
                        verify_bounds(m_lb.begin(),m_lb.end(),start,end);
                        std::copy(start,end,m_ub.begin());
                        // Normalise bounds.
                        normalise_bounds();
                }

                template <std::size_t N>
                void set_ub(const double (&v)[N])
                {
                        if (N != m_lb.size()) {
                                pagmo_throw(value_error,"invalid bounds dimension in set_ub()");
                        }
                        verify_bounds(m_lb.begin(),m_lb.end(),v,v + N);
                        std::copy(v,v + N,m_ub.begin());
                        // Normalise bounds.
                        normalise_bounds();
                }

                unsigned int get_fevals() const;
                unsigned int get_cevals() const;
                size_type get_dimension() const;
                size_type get_i_dimension() const;
                f_size_type get_f_dimension() const;
                c_size_type get_c_dimension() const;
                c_size_type get_ic_dimension() const;
                const std::vector<double>& get_c_tol() const;
                double get_diameter() const;
                virtual std::string get_name() const;
                constraint_vector compute_constraints(const decision_vector &) const;
                void compute_constraints(constraint_vector &, const decision_vector &) const;
                bool compare_constraints(const constraint_vector &, const constraint_vector &) const;
                bool test_constraint(const constraint_vector &, const c_size_type &) const;
                bool feasibility_x(const decision_vector &) const;
                bool feasibility_c(const constraint_vector &) const;

                virtual base_ptr clone() const = 0;
                std::string human_readable() const;
                virtual std::string human_readable_extra() const;
                bool operator==(const base &) const;
                bool operator!=(const base &) const;
                bool is_compatible(const base &) const;
                bool compare_x(const decision_vector &, const decision_vector &) const;
                bool verify_x(const decision_vector &) const;
                bool compare_fc(const fitness_vector &, const constraint_vector &, const fitness_vector &, const constraint_vector &) const;
                virtual void pre_evolution(population &) const;
                virtual void post_evolution(population &) const;
        protected:
                virtual bool equality_operator_extra(const base &) const;
                virtual void compute_constraints_impl(constraint_vector &, const decision_vector &) const;
                virtual bool compare_constraints_impl(const constraint_vector &, const constraint_vector &) const;
                virtual bool compare_fc_impl(const fitness_vector &, const constraint_vector &, const fitness_vector &, const constraint_vector &) const;
                void estimate_sparsity(const decision_vector &, int& lenG, std::vector<int>& iGfun, std::vector<int>& jGvar) const;
                void estimate_sparsity(int& lenG, std::vector<int>& iGfun, std::vector<int>& jGvar) const;
        public:
                virtual void set_sparsity(int& lenG, std::vector<int>& iGfun, std::vector<int>& jGvar) const;
                fitness_vector objfun(const decision_vector &) const;
                void objfun(fitness_vector &, const decision_vector &) const;
                bool compare_fitness(const fitness_vector &, const fitness_vector &) const;
                void reset_caches() const;
        public:
                const std::vector<constraint_vector>& get_best_c(void) const;
                const std::vector<decision_vector>& get_best_x(void) const;
                const std::vector<fitness_vector>& get_best_f(void) const;
                void set_best_x(const std::vector<decision_vector>&);
        protected:
                virtual bool compare_fitness_impl(const fitness_vector &, const fitness_vector &) const;

                virtual void objfun_impl(fitness_vector &f, const decision_vector &x) const = 0;
        private:
                void normalise_bounds();
                // Construct from iterators.
                template <class Iterator1, class Iterator2>
                void construct_from_iterators(Iterator1 start1, Iterator1 end1, Iterator2 start2, Iterator2 end2)
                {
                        m_lb.insert(m_lb.end(),start1,end1);
                        m_ub.insert(m_ub.end(),start2,end2);
                        if (m_lb.size() != m_ub.size() || m_lb.size() == 0) {
                                pagmo_throw(value_error,"null or inconsistent dimension(s) for upper/lower bounds while constructing problem");
                        }
                        verify_bounds(m_lb.begin(),m_lb.end(),m_ub.begin(),m_ub.end());
                }
                // Verify upper/lower bounds. This must be called only after having made sure that the iterator distances
                // are consistent.
                template <class Iterator1, class Iterator2>
                static void verify_bounds(Iterator1 start1, Iterator1 end1, Iterator2 start2, Iterator2 end2)
                {
                        for (; start1 != end1 && start2 != end2; ++start1, ++start2) {
                                if (*start1 > *start2) {
                                        pagmo_throw(value_error,"lower bound is greater than upper bound");
                                }
                        }
                }
        private:
                friend class boost::serialization::access;
                template <class Archive>
                void serialize(Archive &ar, const unsigned int)
                {
                        ar & const_cast<size_type &>(m_i_dimension);
                        ar & const_cast<f_size_type &>(m_f_dimension);
                        ar & const_cast<c_size_type &>(m_c_dimension);
                        ar & const_cast<c_size_type &>(m_ic_dimension);
                        ar & m_lb;
                        ar & m_ub;
                        ar & const_cast<std::vector<double> &>(m_c_tol);
                        ar & m_decision_vector_cache_f;
                        ar & m_fitness_vector_cache;
                        ar & m_decision_vector_cache_c;
                        ar & m_constraint_vector_cache;
                        ar & m_tmp_f1;
                        ar & m_tmp_f2;
                        ar & m_tmp_c1;
                        ar & m_tmp_c2;
                        ar & m_best_x;
                        ar & m_best_f;
                        ar & m_best_c;
                        ar & m_fevals;
                        ar & m_cevals;
                }

                // Data members.
                // Size of the integer part of the problem.
                const size_type                         m_i_dimension;
                // Size of the fitness vector.
                const f_size_type                       m_f_dimension;
                // Global constraints dimension.
                const c_size_type                       m_c_dimension;
                // Inequality constraints dimension
                const c_size_type                       m_ic_dimension;
                // Lower bounds.
                decision_vector                         m_lb;
                // Upper bounds.
                decision_vector                         m_ub;
                // Tolerance for constraints analysis.
                const std::vector<double>   m_c_tol;
                // Decision vector cache for fitness.
                mutable decision_vector_cache_type      m_decision_vector_cache_f;
                // Fitness vector cache.
                mutable fitness_vector_cache_type       m_fitness_vector_cache;
                // Decision vector cache for constraints.
                mutable decision_vector_cache_type      m_decision_vector_cache_c;
                // Constraint vector cache.
                mutable constraint_vector_cache_type    m_constraint_vector_cache;
                // Temporary storage used during decision_vector comparisons.
                mutable fitness_vector                  m_tmp_f1;
                mutable fitness_vector                  m_tmp_f2;
                // Temporary storage used during constraints satisfaction testing and constraints comparison.
                mutable constraint_vector               m_tmp_c1;
                mutable constraint_vector               m_tmp_c2;

                // Best known vectors
                std::vector<decision_vector> m_best_x;
                std::vector<fitness_vector> m_best_f;
                std::vector<constraint_vector> m_best_c;

                // Number of function and constraints evaluations
                mutable unsigned int                    m_fevals;
                mutable unsigned int                    m_cevals;
};

std::ostream __PAGMO_VISIBLE_FUNC &operator<<(std::ostream &, const base &);

}
}

BOOST_SERIALIZATION_ASSUME_ABSTRACT(pagmo::problem::base)

#endif