PaGMO  1.1.5
hv_fair_r_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 <boost/numeric/conversion/cast.hpp>
27 #include <utility>
28 #include <vector>
29 #include <algorithm>
30 
31 #include "../population.h"
32 #include "base.h"
33 #include "base_r_policy.h"
34 #include "hv_fair_r_policy.h"
35 #include "fair_r_policy.h"
36 
37 #include "../util/hypervolume.h"
38 
39 
40 using namespace pagmo::util;
41 
42 namespace pagmo { namespace migration {
43 
45 
52 hv_fair_r_policy::hv_fair_r_policy(const double &rate, rate_type type, const double nadir_eps):base_r_policy(rate,type), m_nadir_eps(nadir_eps) {}
53 
55 {
56  return base_r_policy_ptr(new hv_fair_r_policy(*this));
57 }
58 
59 // Selection implementation.
60 std::vector<std::pair<population::size_type,std::vector<population::individual_type>::size_type> >
61  hv_fair_r_policy::select(const std::vector<population::individual_type> &immigrants, const population &dest) const
62 {
63  // Fall back to fair_r_policy when facing a single-objective problem.
64  if (dest.problem().get_f_dimension() == 1) {
65  return fair_r_policy(m_rate, m_type).select(immigrants, dest);
66  }
67 
68  std::vector<population::individual_type> filtered_immigrants;
69  filtered_immigrants.reserve(immigrants.size());
70 
71  // Keeps information on the original indexing of immigrants after we filter out the duplicates
72  std::vector<unsigned int> original_immigrant_indices;
73  original_immigrant_indices.reserve(immigrants.size());
74 
75  // Remove the duplicates from the set of immigrants
76  std::vector<population::individual_type>::iterator im_it = (const_cast<std::vector<population::individual_type> &>(immigrants)).begin();
77  unsigned int im_idx = 0;
78  for( ; im_it != immigrants.end() ; ++im_it) {
79  decision_vector im_x((*im_it).cur_x);
80 
81  bool equal = true;
82  for ( unsigned int idx = 0 ; idx < dest.size() ; ++idx ) {
83  decision_vector isl_x(dest.get_individual(idx).cur_x);
84  equal = true;
85  for (unsigned int d_idx = 0 ; d_idx < im_x.size() ; ++d_idx) {
86  if (im_x[d_idx] != isl_x[d_idx]) {
87  equal = false;
88  break;
89  }
90  }
91  if (equal) {
92  break;
93  }
94  }
95  if (!equal) {
96  filtered_immigrants.push_back(*im_it);
97  original_immigrant_indices.push_back(im_idx);
98  }
99  ++im_idx;
100  }
101 
102  // Computes the number of immigrants to be selected (accounting for the destination pop size)
103  const population::size_type rate_limit = std::min<population::size_type>(get_n_individuals(dest), boost::numeric_cast<population::size_type>(filtered_immigrants.size()));
104 
105  // Defines the retvalue
106  std::vector<std::pair<population::size_type, std::vector<population::individual_type>::size_type> > result;
107 
108  // Skip the remaining computation if there's nothing to do
109  if (rate_limit == 0) {
110  return result;
111  }
112 
113  // Makes a copy of the destination population
114  population pop_copy(dest);
115 
116  // Merge the immigrants to the copy of the destination population
117  for (population::size_type i = 0; i < rate_limit; ++i) {
118  pop_copy.push_back(filtered_immigrants[i].cur_x);
119  }
120 
121  // Population fronts stored as indices of individuals.
122  std::vector< std::vector<population::size_type> > fronts_i = pop_copy.compute_pareto_fronts();
123 
124  // Population fronts stored as fitness vectors of individuals.
125  std::vector< std::vector<fitness_vector> > fronts_f (fronts_i.size());
126 
127  // Nadir point is established manually later, first point is a first "safe" candidate.
128  fitness_vector refpoint(pop_copy.get_individual(0).cur_f);
129 
130  // Fill fronts_f with fitness vectors and establish the nadir point
131  for (unsigned int f_idx = 0 ; f_idx < fronts_i.size() ; ++f_idx) {
132  fronts_f[f_idx].resize(fronts_i[f_idx].size());
133  for (unsigned int p_idx = 0 ; p_idx < fronts_i[f_idx].size() ; ++p_idx) {
134  fronts_f[f_idx][p_idx] = fitness_vector(pop_copy.get_individual(fronts_i[f_idx][p_idx]).cur_f);
135 
136  // Update the nadir point manually for efficiency.
137  for (unsigned int d_idx = 0 ; d_idx < fronts_f[f_idx][p_idx].size() ; ++d_idx) {
138  refpoint[d_idx] = std::max(refpoint[d_idx], fronts_f[f_idx][p_idx][d_idx]);
139  }
140  }
141  }
142 
143  // Epsilon is added to nadir point
144  for (unsigned int d_idx = 0 ; d_idx < refpoint.size() ; ++d_idx) {
145  refpoint[d_idx] += m_nadir_eps;
146  }
147 
148  // Vector for maintaining the original indices of points for augmented population as 0 and 1
149  std::vector<unsigned int> g_orig_indices(pop_copy.size(), 1);
150 
151  unsigned int no_discarded_immigrants = 0;
152 
153  // Store which front we process (start with the last front) and the number of processed individuals.
154  unsigned int front_idx = fronts_i.size(); // front_idx is equal to the size, since it's decremented right in the main loop
155  unsigned int processed_individuals = 0;
156 
157  // Pairs of (islander index, islander exclusive hypervolume)
158  // Second item is updated later
159  std::vector<std::pair<unsigned int, double> > discarded_islanders;
160 
161  std::vector<std::pair<unsigned int, double> > point_pairs;
162  // index of currently processed point in the point_pair vector.
163  // Initiated to its size (=0) in order to enforce the initial computation on penultimate front.
164  unsigned int current_point = point_pairs.size();
165 
166  // Stops when we reduce the augmented population to the size of the original population or when the number of discarded islanders reaches the limit
167  while (processed_individuals < filtered_immigrants.size() && discarded_islanders.size() < rate_limit) {
168 
169  // if current front was exhausted, load next one
170  if (current_point == point_pairs.size()) {
171  --front_idx;
172 
173  // Compute contributions
174  std::vector<double> c;
175 
176  // If there exist a dominated front for front at index front_idx
177  if (front_idx + 1 < fronts_f.size()) {
178  std::vector<fitness_vector> merged_front;
179  // Reserve the memory and copy the fronts
180  merged_front.reserve(fronts_f[front_idx].size() + fronts_f[front_idx + 1].size());
181 
182  copy(fronts_f[front_idx].begin(), fronts_f[front_idx].end(), back_inserter(merged_front));
183  copy(fronts_f[front_idx + 1].begin(), fronts_f[front_idx +1].end(), back_inserter(merged_front));
184 
185  hypervolume hv(merged_front, false);
186  c = hv.contributions(refpoint);
187  } else {
188  hypervolume hv(fronts_f[front_idx], false);
189  c = hv.contributions(refpoint);
190  }
191 
192  // Initiate the pairs and sort by second item (exclusive volume)
193  point_pairs.resize(fronts_f[front_idx].size());
194  for(unsigned int i = 0 ; i < fronts_f[front_idx].size() ; ++i) {
195  point_pairs[i] = std::make_pair(i, c[i]);
196  }
197  current_point = 0;
198  std::sort(point_pairs.begin(), point_pairs.end(), sort_point_pairs_asc);
199  }
200 
201  unsigned int orig_lc_idx = fronts_i[front_idx][point_pairs[current_point].first];
202 
203  if (orig_lc_idx < dest.size()) {
204  discarded_islanders.push_back(std::make_pair(orig_lc_idx, 0.0));
205  } else {
206  ++no_discarded_immigrants;
207  }
208 
209  // Flag given individual as discarded
210  g_orig_indices[orig_lc_idx] = 0;
211 
212  ++processed_individuals;
213  ++current_point;
214  }
215 
216  // Number of non-discarded immigrants
217  unsigned int no_available_immigrants = boost::numeric_cast<unsigned int>(filtered_immigrants.size() - no_discarded_immigrants);
218 
219  // Pairs of (immigrant index, immigrant exclusive hypervolume)
220  // Second item is updated later
221  std::vector<std::pair<unsigned int, double> > available_immigrants;
222  available_immigrants.reserve(no_available_immigrants);
223  for(unsigned int idx = dest.size() ; idx < pop_copy.size() ; ++idx) {
224  // If the immigrant was not discarded add it to the available set
225  if ( g_orig_indices[idx] == 1 ) {
226  available_immigrants.push_back(std::make_pair(idx, 0.0));
227  }
228  }
229 
230  // Aggregate all points to establish the hypervolume contribution of available immigrants and discarded islanders
231  std::vector<fitness_vector> merged_fronts;
232  merged_fronts.reserve(pop_copy.size());
233 
234  for(unsigned int idx = 0 ; idx < pop_copy.size() ; ++idx) {
235  merged_fronts.push_back(pop_copy.get_individual(idx).cur_f);
236  }
237 
238  hypervolume hv(merged_fronts, false);
239  std::vector<std::pair<unsigned int, double> >::iterator it;
240 
241  for(it = available_immigrants.begin() ; it != available_immigrants.end() ; ++it) {
242  (*it).second = hv.exclusive((*it).first, refpoint);
243  }
244 
245  for(it = discarded_islanders.begin() ; it != discarded_islanders.end() ; ++it) {
246  (*it).second = hv.exclusive((*it).first, refpoint);
247  }
248 
249  // Sort islanders and immigrants according to exclusive hypervolume
250  sort(available_immigrants.begin(), available_immigrants.end(), hv_fair_r_policy::ind_cmp);
251  sort(discarded_islanders.begin(), discarded_islanders.end(), hv_fair_r_policy::ind_cmp);
252 
253  // Number of exchanges is the minimum of the number of non discarded immigrants and the number of discarded islanders
254  unsigned int no_exchanges = std::min(boost::numeric_cast<unsigned int>(available_immigrants.size()), boost::numeric_cast<unsigned int>(discarded_islanders.size()));
255 
256  it = available_immigrants.begin();
257  std::vector<std::pair<unsigned int, double> >::reverse_iterator r_it = discarded_islanders.rbegin();
258 
259  // Match the best immigrant (forward iterator) with the worst islander (reverse iterator) no_exchanges times.
260  for(unsigned int i = 0 ; i < no_exchanges ; ++i) {
261  // Break if any islander is better than an immigrant
262  if ((*r_it).second > (*it).second) {
263  break;
264  }
265  // Push the pair (islander_idx, fixed_immigrant_idx) to the results
266  result.push_back(std::make_pair((*r_it).first, original_immigrant_indices[(*it).first - dest.size()]));
267  ++r_it;
268  ++it;
269  }
270 
271  return result;
272 }
273 
275 bool hv_fair_r_policy::sort_point_pairs_asc(const std::pair<unsigned int, double> &a, const std::pair<unsigned int, double> &b)
276 {
277  return a.second < b.second;
278 }
279 
281 bool hv_fair_r_policy::ind_cmp(const std::pair<unsigned int, double> &a, const std::pair<unsigned int, double> &b)
282 {
283  return a.second > b.second;
284 }
285 
286 }}
287 
288 BOOST_CLASS_EXPORT_IMPLEMENT(pagmo::migration::hv_fair_r_policy)
Root PaGMO namespace.
std::vector< double > decision_vector
Decision vector type.
Definition: types.h:40
Base class for migration replacement policies.
Definition: base_r_policy.h:57
fitness_vector cur_f
Current fitness vector.
Definition: population.h:89
hv_fair_r_policy(const double &rate=1, rate_type type=absolute, double nadir_eps=1.0)
Constructor from rate and rate type.
boost::shared_ptr< base_r_policy > base_r_policy_ptr
Shared pointer to base replacement policy.
Definition: base_r_policy.h:40
std::vector< std::pair< population::size_type, std::vector< population::individual_type >::size_type > > select(const std::vector< population::individual_type > &, const population &) const
Assign pairs of individuals for replacement during migration.
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
Fair replacement policy.
Definition: fair_r_policy.h:49
population::size_type get_n_individuals(const population &) const
Get number of individuals to migrate from/to input population.
std::vector< std::pair< population::size_type, std::vector< population::individual_type >::size_type > > select(const std::vector< population::individual_type > &, const population &) const
Assign pairs of individuals for replacement during migration.
base_r_policy_ptr clone() const
Clone method.
std::vector< double > contributions(const fitness_vector &, const hv_algorithm::base_ptr) const
Contributions method.
std::vector< double > fitness_vector
Fitness vector type.
Definition: types.h:42
util namespace.
Definition: util/config.h:42
container_type::size_type size_type
Population size type.
Definition: population.h:192
decision_vector cur_x
Current decision vector.
Definition: population.h:83
rate_type m_type
Migration rate type.
f_size_type get_f_dimension() const
Return fitness dimension.
Hypervolume class.
Definition: hypervolume.h:49
double m_rate
Migration rate.
double exclusive(const unsigned int, const fitness_vector &, const hv_algorithm::base_ptr) const
Compute exclusive contribution.
Replace the 'n' least contributors with the incoming set.
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.