PaGMO  1.1.5
hv_greedy_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 
29 #include "../population.h"
30 #include "base.h"
31 #include "base_s_policy.h"
32 #include "hv_greedy_s_policy.h"
33 #include "best_s_policy.h"
34 #include "../exceptions.h"
35 #include "../util/hypervolume.h"
36 
37 using namespace pagmo::util;
38 
39 namespace pagmo { namespace migration {
40 
42 
49 hv_greedy_s_policy::hv_greedy_s_policy(const double &rate, rate_type type, const double nadir_eps):base_s_policy(rate,type), m_nadir_eps(nadir_eps) { }
50 
52 {
53  return base_s_policy_ptr(new hv_greedy_s_policy(*this));
54 }
55 
56 std::vector<population::individual_type> hv_greedy_s_policy::select(population &pop) const
57 {
58  // Fall back to best_s_policy when facing a single-objective problem.
59  if (pop.problem().get_f_dimension() == 1) {
60  return best_s_policy(m_rate, m_type).select(pop);
61  }
62 
63  pagmo_assert(get_n_individuals(pop) <= pop.size());
64  // Gets the number of individuals to select
65  const population::size_type migration_rate = get_n_individuals(pop);
66  // Create a temporary array of individuals.
67  std::vector<population::individual_type> result;
68 
69  // Indices of fronts.
70  std::vector< std::vector< population::size_type> > fronts_i = pop.compute_pareto_fronts();
71 
72  // Fitness vectors of individuals according to the indices above.
73  std::vector< std::vector< fitness_vector> > fronts_f (fronts_i.size());
74 
75  // Nadir point is established manually later, first point is as a first "safe" candidate.
76  fitness_vector refpoint(pop.get_individual(0).cur_f);
77 
78  for (unsigned int f_idx = 0 ; f_idx < fronts_i.size() ; ++f_idx) {
79  fronts_f[f_idx].resize(fronts_i[f_idx].size());
80  for (unsigned int p_idx = 0 ; p_idx < fronts_i[f_idx].size() ; ++p_idx) {
81  fronts_f[f_idx][p_idx] = fitness_vector(pop.get_individual(fronts_i[f_idx][p_idx]).cur_f);
82 
83  // Update the nadir point manually for efficiency.
84  for (unsigned int d_idx = 0 ; d_idx < fronts_f[f_idx][p_idx].size() ; ++d_idx) {
85  refpoint[d_idx] = std::max(refpoint[d_idx], fronts_f[f_idx][p_idx][d_idx]);
86  }
87  }
88  }
89 
90  // Epsilon is added to nadir point
91  for (unsigned int d_idx = 0 ; d_idx < refpoint.size() ; ++d_idx) {
92  refpoint[d_idx] += m_nadir_eps;
93  }
94 
95  // Store which front we process (start with front 0) and the number of processed individuals.
96  unsigned int front_idx = 0;
97  unsigned int processed_individuals = 0;
98 
99  // Vector for maintaining the original indices of points
100  std::vector<unsigned int> orig_indices;
101 
102  while (processed_individuals < migration_rate) {
103  // If we need to pull every point from given front anyway, just push back the individuals right away
104  if (fronts_f[front_idx].size() <= (migration_rate - processed_individuals)) {
105  for(unsigned int i = 0 ; i < fronts_i[front_idx].size() ; ++i) {
106  result.push_back(pop.get_individual(fronts_i[front_idx][i]));
107  }
108 
109  processed_individuals += fronts_f[front_idx].size();
110  ++front_idx;
111  } else {
112  // Prepare the vector for the original indices
113  if (orig_indices.size() == 0) {
114  orig_indices.resize(fronts_i[front_idx].size());
115  iota(orig_indices.begin(), orig_indices.end(), 0);
116  }
117 
118  // Compute the greatest contributor
119  hypervolume hv(fronts_f[front_idx], false);
120  hv.set_copy_points(false);
121  unsigned int gc_idx = hv.greatest_contributor(refpoint);
122  result.push_back(pop.get_individual(fronts_i[front_idx][orig_indices[gc_idx]]));
123 
124  // Remove it from the front along with its index
125  orig_indices.erase(orig_indices.begin() + gc_idx);
126  fronts_f[front_idx].erase(fronts_f[front_idx].begin() + gc_idx);
127  ++processed_individuals;
128  }
129  }
130 
131  return result;
132 }
133 
134 }}
135 
136 BOOST_CLASS_EXPORT_IMPLEMENT(pagmo::migration::hv_greedy_s_policy)
hv_greedy_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
"Choose best" migration selection policy.
Definition: best_s_policy.h:48
base_s_policy_ptr clone() const
Clone method.
population::size_type get_n_individuals(const population &) const
Get number of individuals to migrate from/to input population.
std::vector< double > fitness_vector
Fitness vector type.
Definition: types.h:42
util namespace.
Definition: util/config.h:42
Choose 'n' successive greatest contributors migration policy.
boost::shared_ptr< base_s_policy > base_s_policy_ptr
Shared pointer to base selection policy.
Definition: base_s_policy.h:39
static void iota(ForwardIterator first, ForwardIterator last, T value)
Iota function, usefull to fill iterator range with increasing values.
container_type::size_type size_type
Population size type.
Definition: population.h:192
unsigned int greatest_contributor(const fitness_vector &, const hv_algorithm::base_ptr) const
Find the most contributing individual.
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.
std::vector< population::individual_type > select(population &) const
Select individuals to emigrate from the given population.
double m_rate
Migration rate.
void set_copy_points(const bool)
Setter for 'copy_points' flag.
Definition: hypervolume.cpp:99
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.