26 #include <boost/numeric/conversion/cast.hpp>
31 #include "../population.h"
33 #include "base_r_policy.h"
34 #include "hv_fair_r_policy.h"
35 #include "fair_r_policy.h"
37 #include "../util/hypervolume.h"
42 namespace pagmo {
namespace migration {
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) {}
60 std::vector<std::pair<population::size_type,std::vector<population::individual_type>::size_type> >
68 std::vector<population::individual_type> filtered_immigrants;
69 filtered_immigrants.reserve(immigrants.size());
72 std::vector<unsigned int> original_immigrant_indices;
73 original_immigrant_indices.reserve(immigrants.size());
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) {
82 for (
unsigned int idx = 0 ; idx < dest.size() ; ++idx ) {
85 for (
unsigned int d_idx = 0 ; d_idx < im_x.size() ; ++d_idx) {
86 if (im_x[d_idx] != isl_x[d_idx]) {
96 filtered_immigrants.push_back(*im_it);
97 original_immigrant_indices.push_back(im_idx);
106 std::vector<std::pair<population::size_type, std::vector<population::individual_type>::size_type> > result;
109 if (rate_limit == 0) {
118 pop_copy.push_back(filtered_immigrants[i].cur_x);
125 std::vector< std::vector<fitness_vector> > fronts_f (fronts_i.size());
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) {
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]);
144 for (
unsigned int d_idx = 0 ; d_idx < refpoint.size() ; ++d_idx) {
145 refpoint[d_idx] += m_nadir_eps;
149 std::vector<unsigned int> g_orig_indices(pop_copy.size(), 1);
151 unsigned int no_discarded_immigrants = 0;
154 unsigned int front_idx = fronts_i.size();
155 unsigned int processed_individuals = 0;
159 std::vector<std::pair<unsigned int, double> > discarded_islanders;
161 std::vector<std::pair<unsigned int, double> > point_pairs;
164 unsigned int current_point = point_pairs.size();
167 while (processed_individuals < filtered_immigrants.size() && discarded_islanders.size() < rate_limit) {
170 if (current_point == point_pairs.size()) {
174 std::vector<double> c;
177 if (front_idx + 1 < fronts_f.size()) {
178 std::vector<fitness_vector> merged_front;
180 merged_front.reserve(fronts_f[front_idx].size() + fronts_f[front_idx + 1].size());
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));
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]);
198 std::sort(point_pairs.begin(), point_pairs.end(), sort_point_pairs_asc);
201 unsigned int orig_lc_idx = fronts_i[front_idx][point_pairs[current_point].first];
203 if (orig_lc_idx < dest.size()) {
204 discarded_islanders.push_back(std::make_pair(orig_lc_idx, 0.0));
206 ++no_discarded_immigrants;
210 g_orig_indices[orig_lc_idx] = 0;
212 ++processed_individuals;
217 unsigned int no_available_immigrants = boost::numeric_cast<
unsigned int>(filtered_immigrants.size() - no_discarded_immigrants);
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) {
225 if ( g_orig_indices[idx] == 1 ) {
226 available_immigrants.push_back(std::make_pair(idx, 0.0));
231 std::vector<fitness_vector> merged_fronts;
232 merged_fronts.reserve(pop_copy.size());
234 for(
unsigned int idx = 0 ; idx < pop_copy.size() ; ++idx) {
239 std::vector<std::pair<unsigned int, double> >::iterator it;
241 for(it = available_immigrants.begin() ; it != available_immigrants.end() ; ++it) {
242 (*it).second = hv.
exclusive((*it).first, refpoint);
245 for(it = discarded_islanders.begin() ; it != discarded_islanders.end() ; ++it) {
246 (*it).second = hv.
exclusive((*it).first, refpoint);
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);
254 unsigned int no_exchanges = std::min(boost::numeric_cast<unsigned int>(available_immigrants.size()), boost::numeric_cast<unsigned int>(discarded_islanders.size()));
256 it = available_immigrants.begin();
257 std::vector<std::pair<unsigned int, double> >::reverse_iterator r_it = discarded_islanders.rbegin();
260 for(
unsigned int i = 0 ; i < no_exchanges ; ++i) {
262 if ((*r_it).second > (*it).second) {
266 result.push_back(std::make_pair((*r_it).first, original_immigrant_indices[(*it).first - dest.size()]));
275 bool hv_fair_r_policy::sort_point_pairs_asc(
const std::pair<unsigned int, double> &a,
const std::pair<unsigned int, double> &b)
277 return a.second < b.second;
281 bool hv_fair_r_policy::ind_cmp(
const std::pair<unsigned int, double> &a,
const std::pair<unsigned int, double> &b)
283 return a.second > b.second;
std::vector< double > decision_vector
Decision vector type.
Base class for migration replacement policies.
fitness_vector cur_f
Current fitness vector.
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.
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.
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.
container_type::size_type size_type
Population size type.
decision_vector cur_x
Current decision vector.
rate_type m_type
Migration rate type.
f_size_type get_f_dimension() const
Return fitness dimension.
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.
rate_type
Type of migration rate.