util/hv_algorithm/base.cpp

/*****************************************************************************
 *   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.               *
 *****************************************************************************/

#include "base.h"

namespace pagmo { namespace util { namespace hv_algorithm {

base::~base() {}


void base::assert_minimisation(const std::vector<fitness_vector> &points, const fitness_vector &r_point) const
{
        for(std::vector<fitness_vector>::size_type idx = 0 ; idx < points.size() ; ++idx) {
                bool outside_bounds = false;
                bool all_equal = true;

                for(fitness_vector::size_type f_idx = 0 ; f_idx < points[idx].size() ; ++f_idx) {
                        outside_bounds |= (r_point[f_idx] < points[idx][f_idx]);
                        all_equal &= (r_point[f_idx] == points[idx][f_idx]);
                }
                if (all_equal || outside_bounds) {
                        // Prepare error message.
                        std::stringstream ss;
                        std::string str_p("("), str_r("(");
                        for(fitness_vector::size_type f_idx = 0 ; f_idx < points[idx].size() ; ++f_idx) {
                                        str_p += boost::lexical_cast<std::string>(points[idx][f_idx]);
                                        str_r += boost::lexical_cast<std::string>(r_point[f_idx]);
                                if (f_idx < points[idx].size() - 1) {
                                        str_p += ", ";
                                        str_r += ", ";
                                } else {
                                        str_p += ")";
                                        str_r += ")";
                                }
                        }
                        ss << "Reference point is invalid: another point seems to be outside the reference point boundary, or be equal to it:" << std::endl;
                        ss << " P[" << idx << "]\t= " << str_p << std::endl;
                        ss << " R\t= " << str_r << std::endl;
                        pagmo_throw(value_error, ss.str());
                }
        }
}


double base::exclusive(const unsigned int p_idx, std::vector<fitness_vector> &points, const fitness_vector &r_point) const
{
        if (points.size() == 1) {
                return compute(points, r_point);
        }
        std::vector<fitness_vector> points_less;
        points_less.reserve(points.size() - 1);
        copy(points.begin(), points.begin() + p_idx, back_inserter(points_less));
        copy(points.begin() + p_idx + 1, points.end(), back_inserter(points_less));

        return compute(points, r_point) - compute(points_less, r_point);
}


unsigned int base::extreme_contributor(std::vector<fitness_vector> &points, const fitness_vector &r_point, bool (*cmp_func)(double, double)) const
{
        // Trivial case
        if (points.size() == 1) {
                return 0;
        }

        std::vector<double> c = contributions(points, r_point);

        unsigned int idx_extreme = 0;

        // Check the remaining ones using the provided comparison function
        for(unsigned int idx = 1 ; idx < c.size() ; ++idx) {
                if (cmp_func(c[idx], c[idx_extreme])) {
                        idx_extreme = idx;
                }
        }

        return idx_extreme;
}


bool base::cmp_least(const double a, const double b)
{
        return a < b;
}



bool base::cmp_greatest(const double a, const double b)
{
        return a > b;
}


unsigned int base::least_contributor(std::vector<fitness_vector> &points, const fitness_vector &r_point) const
{
        return extreme_contributor(points, r_point, base::cmp_least);
}


unsigned int base::greatest_contributor(std::vector<fitness_vector> &points, const fitness_vector &r_point) const
{
        return extreme_contributor(points, r_point, base::cmp_greatest);
}


std::vector<double> base::contributions(std::vector<fitness_vector> &points, const fitness_vector &r_point) const
{
        std::vector<double> c;
        c.reserve(points.size());

        // Trivial case
        if (points.size() == 1) {
                c.push_back(volume_between(points[0], r_point));
                return c;
        }

        // Compute the total hypervolume for the reference
        std::vector<fitness_vector> points_cpy(points.begin(), points.end());
        double hv_total = compute(points_cpy, r_point);

        // Points[0] as a first candidate
        points_cpy = std::vector<fitness_vector>(points.begin() + 1, points.end());
        c.push_back(hv_total - compute(points_cpy, r_point));

        // Check the remaining ones using the provided comparison function
        for(unsigned int idx = 1 ; idx < points.size() ; ++idx) {
                std::vector<fitness_vector> points_less;
                points_less.reserve(points.size() - 1);
                copy(points.begin(), points.begin() + idx, back_inserter(points_less));
                copy(points.begin() + idx + 1, points.end(), back_inserter(points_less));
                double delta = hv_total - compute(points_less, r_point);

                if (fabs(delta) < 1e-8) {
                        delta = 0.0;
                }
                c.push_back(delta);
        }

        return c;
}


double base::volume_between(const fitness_vector &a, const fitness_vector &b, unsigned int dim_bound)
{
        if (dim_bound == 0) {
                dim_bound = a.size();
        }
        double volume = 1.0;
        for (fitness_vector::size_type idx = 0; idx < dim_bound ; ++idx) {
                volume *= (a[idx] - b[idx]);
        }
        return (volume < 0 ? -volume : volume);
}


double base::volume_between(double* a, double* b, unsigned int size)
{
        double volume = 1.0;
        while(size--) {
                volume *= (b[size] - a[size]);
        }
        return (volume < 0 ? -volume : volume);
}


int base::dom_cmp(const fitness_vector &a, const fitness_vector &b, unsigned int dim_bound)
{
        if (dim_bound == 0) {
                dim_bound = a.size();
        }
        for(fitness_vector::size_type i = 0; i < dim_bound ; ++i) {
                if (a[i] > b[i]) {
                        for(fitness_vector::size_type j = i + 1; j < dim_bound ; ++j) {
                                if (a[j] < b[j]) {
                                        return DOM_CMP_INCOMPARABLE;
                                }
                        }
                        return DOM_CMP_B_DOMINATES_A;
                }
                else if (a[i] < b[i]) {
                        for(fitness_vector::size_type j = i + 1 ; j < dim_bound ; ++j) {
                                if (a[j] > b[j]) {
                                        return DOM_CMP_INCOMPARABLE;
                                }
                        }
                        return DOM_CMP_A_DOMINATES_B;
                }
        }
        return DOM_CMP_A_B_EQUAL;
}


int base::dom_cmp(double* a, double* b, unsigned int size)
{
        for(fitness_vector::size_type i = 0; i < size ; ++i) {
                if (a[i] > b[i]) {
                        for(fitness_vector::size_type j = i + 1; j < size ; ++j) {
                                if (a[j] < b[j]) {
                                        return DOM_CMP_INCOMPARABLE;
                                }
                        }
                        return DOM_CMP_B_DOMINATES_A;
                }
                else if (a[i] < b[i]) {
                        for(fitness_vector::size_type j = i + 1 ; j < size ; ++j) {
                                if (a[j] > b[j]) {
                                        return DOM_CMP_INCOMPARABLE;
                                }
                        }
                        return DOM_CMP_A_DOMINATES_B;
                }
        }
        return DOM_CMP_A_B_EQUAL;
}


fitness_vector_cmp::fitness_vector_cmp(int dim, char cmp_type)
{
        if (cmp_type == '<') {
                m_cmp_obj = boost::shared_ptr<cmp_fun>(new cmp_le(dim));
        }
        else {
                m_cmp_obj = boost::shared_ptr<cmp_fun>(new cmp_ge(dim));
        }
}


std::string base::get_name() const
{
        return typeid(*this).name();
}

} } }