PaGMO  1.1.5
hv_best_s_policy.cpp
1 /*****************************************************************************
2  * Copyright (C) 2004-2015 The PaGMO development team, *
3  * Advanced Concepts Team (ACT), European Space Agency (ESA) *
4  * *
5  * https://github.com/esa/pagmo *
6  * *
7  * act@esa.int *
8  * *
9  * This program is free software; you can redistribute it and/or modify *
10  * it under the terms of the GNU General Public License as published by *
11  * the Free Software Foundation; either version 2 of the License, or *
12  * (at your option) any later version. *
13  * *
14  * This program is distributed in the hope that it will be useful, *
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
17  * GNU General Public License for more details. *
18  * *
19  * You should have received a copy of the GNU General Public License *
20  * along with this program; if not, write to the *
21  * Free Software Foundation, Inc., *
22  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
23  *****************************************************************************/
24 
25 #include <algorithm>
26 #include <vector>
27 #include <set>
28 #include <cmath>
29 
30 #include "../population.h"
31 #include "base.h"
32 #include "base_s_policy.h"
33 #include "hv_best_s_policy.h"
34 #include "best_s_policy.h"
35 #include "../exceptions.h"
36 #include "../util/hypervolume.h"
37 
38 using namespace pagmo::util;
39 
40 namespace pagmo { namespace migration {
41 
43 
50 hv_best_s_policy::hv_best_s_policy(const double &rate, rate_type type, const double nadir_eps):base_s_policy(rate,type), m_nadir_eps(nadir_eps) { }
51 
53 {
54  return base_s_policy_ptr(new hv_best_s_policy(*this));
55 }
56 
57 bool hv_best_s_policy::sort_point_pairs_desc(const std::pair<unsigned int, double> &a, const std::pair<unsigned int, double> &b)
58 {
59  return a.second > b.second;
60 }
61 
62 std::vector<population::individual_type> hv_best_s_policy::select(population &pop) const
63 {
64  // Fall back to best_s_policy when facing a single-objective problem.
65  if (pop.problem().get_f_dimension() == 1) {
66  return best_s_policy(m_rate, m_type).select(pop);
67  }
68 
69  pagmo_assert(get_n_individuals(pop) <= pop.size());
70 
71  // Gets the number of individuals to select
72  const population::size_type migration_rate = get_n_individuals(pop);
73 
74  // Create a temporary array of individuals.
75  std::vector<population::individual_type> result;
76 
77  // Indices of fronts.
78  std::vector< std::vector< population::size_type> > fronts_i = pop.compute_pareto_fronts();
79 
80  // Fitness vectors of individuals according to the indices above.
81  std::vector< std::vector< fitness_vector> > fronts_f (fronts_i.size());
82 
83  // Nadir point is established manually later, first point is as a first "safe" candidate.
84  fitness_vector refpoint(pop.get_individual(0).cur_f);
85 
86  for (unsigned int f_idx = 0 ; f_idx < fronts_i.size() ; ++f_idx) {
87  fronts_f[f_idx].resize(fronts_i[f_idx].size());
88  for (unsigned int p_idx = 0 ; p_idx < fronts_i[f_idx].size() ; ++p_idx) {
89  fronts_f[f_idx][p_idx] = fitness_vector(pop.get_individual(fronts_i[f_idx][p_idx]).cur_f);
90 
91  // Update the nadir point manually for efficiency.
92  for (unsigned int d_idx = 0 ; d_idx < fronts_f[f_idx][p_idx].size() ; ++d_idx) {
93  refpoint[d_idx] = std::max(refpoint[d_idx], fronts_f[f_idx][p_idx][d_idx]);
94  }
95  }
96  }
97 
98  // Epsilon is added to nadir point
99  for (unsigned int d_idx = 0 ; d_idx < refpoint.size() ; ++d_idx) {
100  refpoint[d_idx] += m_nadir_eps;
101  }
102 
103  // Store which front we process (start with front 0) and the number of processed individuals.
104  unsigned int front_idx = 0;
105  unsigned int remaining_individuals = migration_rate;
106 
107  while (remaining_individuals > 0) {
108  unsigned int front_size = fronts_f[front_idx].size();
109 
110  // If we need every individual from this front anyway skip the computation
111  if (remaining_individuals >= front_size) {
112  for(unsigned int i = 0 ; i < front_size ; ++i) {
113  result.push_back(pop.get_individual(fronts_i[front_idx][i]));
114  }
115  remaining_individuals -= front_size;
116  } else {
117  // Store the original (true) size of the front in case it gets extended
118  unsigned int true_front_size = fronts_f[front_idx].size();
119 
120  // If there is a lower front available, merge it as well
121  if (front_idx + 1 < fronts_f.size()) {
122  // Make room for the new front
123  fronts_f[front_idx].resize(true_front_size + fronts_f[front_idx + 1].size());
124  for(unsigned int i = 0 ; i < fronts_f[front_idx + 1].size() ; ++i) {
125  fronts_f[front_idx][true_front_size + i] = fronts_f[front_idx + 1][i];
126  }
127 
128  }
129  hypervolume hv(fronts_f[front_idx], false);
130  std::vector<double> c = hv.contributions(refpoint);
131 
132  std::vector<std::pair<unsigned int, double> > point_pairs;
133  point_pairs.resize(true_front_size);
134 
135  for(unsigned int i = 0 ; i < true_front_size ; ++i) {
136  point_pairs[i] = std::make_pair(i, c[i]);
137  }
138 
139  std::sort(point_pairs.begin(), point_pairs.end(), sort_point_pairs_desc);
140 
141  // Number of individuals that will be pulled from this front
142  for(unsigned int i = 0 ; i < remaining_individuals ; ++i) {
143  result.push_back(pop.get_individual(fronts_i[front_idx][point_pairs[i].first]));
144  }
145  remaining_individuals = 0;
146  }
147  ++front_idx;
148  }
149 
150  return result;
151 }
152 
153 }}
154 
155 BOOST_CLASS_EXPORT_IMPLEMENT(pagmo::migration::hv_best_s_policy)
hv_best_s_policy(const double &rate=1, rate_type type=absolute, double nadir_eps=1.0)
Constructor from migration rate and type.
Root PaGMO namespace.
fitness_vector cur_f
Current fitness vector.
Definition: population.h:89
Base class for migration selection policies.
Definition: base_s_policy.h:54
const individual_type & get_individual(const size_type &) const
Get constant reference to individual at position n.
Definition: population.cpp:277
Population class.
Definition: population.h:70
std::vector< population::individual_type > select(population &) const
Select individuals to emigrate from the given population.
"Choose best" migration selection policy.
Definition: best_s_policy.h:48
population::size_type get_n_individuals(const population &) const
Get number of individuals to migrate from/to input population.
Choose 'n' greatest contributors migration policy.
std::vector< double > contributions(const fitness_vector &, const hv_algorithm::base_ptr) const
Contributions method.
base_s_policy_ptr clone() const
Clone method.
std::vector< double > fitness_vector
Fitness vector type.
Definition: types.h:42
util namespace.
Definition: util/config.h:42
boost::shared_ptr< base_s_policy > base_s_policy_ptr
Shared pointer to base selection policy.
Definition: base_s_policy.h:39
container_type::size_type size_type
Population size type.
Definition: population.h:192
rate_type m_type
Migration rate type.
f_size_type get_f_dimension() const
Return fitness dimension.
Hypervolume class.
Definition: hypervolume.h:49
std::vector< population::individual_type > select(population &) const
Select individuals to emigrate from the given population.
double m_rate
Migration rate.
std::vector< std::vector< size_type > > compute_pareto_fronts() const
Computes and returns the population Pareto fronts.
Definition: population.cpp:475
rate_type
Type of migration rate.