PaGMO  1.1.5
population.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 // 04/01/2009: Initial version by Francesco Biscani.
26 
27 #include <algorithm>
28 #include <boost/numeric/conversion/cast.hpp>
29 #include <boost/random/uniform_int.hpp>
30 #include <boost/random/uniform_real.hpp>
31 #include <iterator>
32 #include <sstream>
33 #include <string>
34 #include <vector>
35 #include <limits>
36 
37 #include "problem/base.h"
38 #include "problem/base_stochastic.h"
39 #include "exceptions.h"
40 #include "population.h"
41 #include "rng.h"
42 #include "types.h"
43 #include "util/racing.h"
44 #include "util/race_pop.h"
45 
46 #include "algorithm/base.h"
47 #include "problem/con2uncon.h"
48 
49 namespace pagmo
50 {
51 
53 problem::base_ptr &population_access::get_problem_ptr(population &pop)
54 {
55  return pop.m_prob;
56 }
57 
59 
69 population::population(const problem::base &p, int n, const boost::uint32_t &seed):m_prob(p.clone()), m_pareto_rank(n), m_crowding_d(n), m_drng(seed),m_urng(seed)
70 {
71  if (n < 0) {
72  pagmo_throw(value_error,"number of individuals cannot be negative");
73  }
74  // Store sizes temporarily.
75  const size_type size = boost::numeric_cast<size_type>(n);
76  const fitness_vector::size_type f_size = m_prob->get_f_dimension();
77  const constraint_vector::size_type c_size = m_prob->get_c_dimension();
78  const decision_vector::size_type p_size = m_prob->get_dimension();
79  for (size_type i = 0; i < size; ++i) {
80  // Push back an empty individual.
81  m_container.push_back(individual_type());
82  m_dom_list.push_back(std::vector<size_type>());
83  m_dom_count.push_back(0);
84  // Resize individual's elements.
85  m_container.back().cur_x.resize(p_size);
86  m_container.back().cur_v.resize(p_size);
87  m_container.back().cur_c.resize(c_size);
88  m_container.back().cur_f.resize(f_size);
89  m_container.back().best_x.resize(p_size);
90  m_container.back().best_c.resize(c_size);
91  m_container.back().best_f.resize(f_size);
92  // Initialise randomly the individual.
93  reinit(i);
94  }
95 }
96 
98 
103 population::population(const population &p):m_prob(p.m_prob->clone()),m_container(p.m_container),m_dom_list(p.m_dom_list),m_dom_count(p.m_dom_count),
104  m_champion(p.m_champion), m_pareto_rank(p.m_pareto_rank), m_crowding_d(p.m_crowding_d),m_drng(p.m_drng),m_urng(p.m_urng)
105 {}
106 
108 
116 {
117  if (this != &p) {
118  pagmo_assert(m_prob && p.m_prob);
119  // Perform the copies.
120  m_prob = p.m_prob->clone();
121  m_container = p.m_container;
122  m_dom_list = p.m_dom_list;
123  m_dom_count = p.m_dom_count;
124  m_champion = p.m_champion;
125  m_pareto_rank = p.m_pareto_rank;
126  m_crowding_d = p.m_crowding_d;
127  m_drng = p.m_drng;
128  m_urng = p.m_urng;
129  }
130  return *this;
131 }
132 
133 // Update the domination list and the domination count when the individual at position n has changed
134 void population::update_dom(const size_type &n)
135 {
136  // The algorithm works as follow:
137  // 1) For each element in m_dom_list[n] decrease the domination count by one. (m_dom_count[m_dom_list[n][j]] -= 1)
138  // 2) We empty the dom_list and reinitialize m_dom_count[n] = 0-
139  // 3) We loop over the population (j) and construct again m_dom_list[n] and m_dom_count,
140  // taking care to also keep m_dom_list[j] correctly updated
141 
142  const size_type size = m_container.size();
143  pagmo_assert(m_dom_list.size() == size && m_dom_count.size() == size && n < size);
144 
145  // Decrease the domination count for the individuals that were dominated
146  for (size_type i = 0; i < m_dom_list[n].size(); ++i) {
147  m_dom_count[ m_dom_list[n][i] ]--;
148  }
149 
150  // Empty the domination list of individual at position n.
151  m_dom_list[n].clear();
152  // Reset the dom_count of individual at position n.
153  m_dom_count[n] = 0;
154 
155  for (size_type i = 0; i < size; ++i) {
156  if (i != n) {
157  // Check if individual in position i dominates individual in position n.
158  if (m_prob->compare_fc(m_container[i].best_f,m_container[i].best_c,m_container[n].best_f,m_container[n].best_c)) {
159  // Update the domination count in n.
160  m_dom_count[n]++;
161  // Update the domination list in i.
162  //If n is already present, do nothing, otherwise push_back.
163  if (std::find(m_dom_list[i].begin(),m_dom_list[i].end(),n) == m_dom_list[i].end()) {
164  m_dom_list[i].push_back(n);
165  }
166  } else {
167  // We need to erase n from the domination list, if present.
168  std::vector<size_type>::iterator it = std::find(m_dom_list[i].begin(),m_dom_list[i].end(),n);
169  if (it != m_dom_list[i].end()) {
170  m_dom_list[i].erase(it);
171  }
172  }
173  // Check if individual in position n dominates individual in position i.
174  if (m_prob->compare_fc(m_container[n].best_f,m_container[n].best_c,m_container[i].best_f,m_container[i].best_c)) {
175  m_dom_list[n].push_back(i);
176  m_dom_count[i]++;
177  }
178  }
179  }
180 }
181 
182 // Init randomly the velocity of the individual in position idx.
183 void population::init_velocity(const size_type &idx)
184 {
185  const decision_vector::size_type p_size = m_prob->get_dimension();
186  double width = 0;
187  for (decision_vector::size_type j = 0; j < p_size; ++j) {
188  // Initialise velocities so that in one tick the particles travel
189  // at most half the bounds distance.
190  width = (m_prob->get_ub()[j] - m_prob->get_lb()[j]) / 2;
191  m_container[idx].cur_v[j] = boost::uniform_real<double>(-width,width)(m_drng);
192  }
193 }
194 
197  const population::size_type pop_size(m_container.size());
198  if (pop_size == 0) {
199  pagmo_throw(zero_division_error,"Population has no individuals, no mean velocity can be computed.");
200  }
201  double ret=0, tmp;
202  const decision_vector::size_type p_size = m_prob->get_dimension();
203 
204  for (population::size_type i = 0; i<pop_size; ++i) {
205  tmp = 0;
206  for (decision_vector::size_type j = 0; j < p_size; ++j) {
207  tmp += m_container[i].cur_v[j]*m_container[i].cur_v[j];
208  }
209  ret += std::sqrt(tmp);
210  }
211  return (ret / pop_size);
212 }
213 
215 
219 {
220  for (size_type i = 0; i < size(); ++i)
221  {
222  reinit(i);
223  }
224 }
225 
227 
237 {
238  if (idx >= size()) {
239  pagmo_throw(index_error,"invalid index");
240  }
241  const decision_vector::size_type p_size = m_prob->get_dimension(), i_size = m_prob->get_i_dimension();
242  // Initialise randomly the continuous part of the decision vector.
243  for (decision_vector::size_type j = 0; j < p_size - i_size; ++j) {
244  m_container[idx].cur_x[j] = boost::uniform_real<double>(m_prob->get_lb()[j],m_prob->get_ub()[j])(m_drng);
245  }
246  // Initialise randomly the integer part of the decision vector.
247  for (decision_vector::size_type j = p_size - i_size; j < p_size; ++j) {
248  m_container[idx].cur_x[j] = boost::uniform_int<int>(m_prob->get_lb()[j],m_prob->get_ub()[j])(m_urng);
249  }
250  // Initialise randomly the velocity vector.
251  init_velocity(idx);
252  // Fill in the constraints.
253  m_prob->compute_constraints(m_container[idx].cur_c,m_container[idx].cur_x);
254  // Compute the fitness.
255  m_prob->objfun(m_container[idx].cur_f,m_container[idx].cur_x);
256  // Best decision vector is current decision vector, best fitness is current fitness, best constraints are current constraints.
257  m_container[idx].best_x = m_container[idx].cur_x;
258  m_container[idx].best_f = m_container[idx].cur_f;
259  m_container[idx].best_c = m_container[idx].cur_c;
260  // Update the champion.
261  update_champion(idx);
262  // Update the domination lists.
263  update_dom(idx);
264 }
265 
266 
268 
278 {
279  if (idx >= size()) {
280  pagmo_throw(index_error,"invalid index");
281  }
282  return m_container[idx];
283 }
284 
286 
296 const std::vector<population::size_type> &population::get_domination_list(const size_type &idx) const
297 {
298  if (idx >= size()) {
299  pagmo_throw(index_error,"invalid index");
300  }
301  return m_dom_list[idx];
302 }
303 
305 
315 {
316  if (idx >= size()) {
317  pagmo_throw(index_error,"invalid index");
318  }
319  return m_dom_count[idx];
320 }
321 
323 
335 {
336  if (idx >= m_pareto_rank.size()) {
337  pagmo_throw(index_error,"invalid index");
338  }
339  return m_pareto_rank[idx];
340 }
341 
343 
356 double population::get_crowding_d(const size_type &idx) const
357 {
358  if (idx >= m_crowding_d.size()) {
359  pagmo_throw(index_error,"invalid index");
360  }
361  return m_crowding_d[idx];
362 }
363 
364 // This functor is used to sort (minimization assumed) along a particular fitness dimension.
365 // Needed for the computations of the crowding distance
366 struct one_dim_fit_comp {
367  one_dim_fit_comp(const population &pop, fitness_vector::size_type dim):m_pop(pop), m_dim(dim) {};
368  bool operator()(const population::size_type& idx1, const population::size_type& idx2) const
369  {
370  return m_pop.get_individual(idx1).cur_f[m_dim] < m_pop.get_individual(idx2).cur_f[m_dim];
371  }
372  const population& m_pop;
373  fitness_vector::size_type m_dim;
374 };
375 
376 
378 
385  // Population size can change between calls and m_pareto_rank, m_crowding_d are updated if necessary
386  m_pareto_rank.resize(size());
387  m_crowding_d.resize(size());
388 
389  // We initialize the ranks and all distances to zero
390  std::fill(m_pareto_rank.begin(), m_pareto_rank.end(), 0);
391  std::fill(m_crowding_d.begin(), m_crowding_d.end(), 0);
392 
393  // We define some utility vectors .....
394  std::vector<population::size_type> F,S;
395 
396  // And make a copy of the domination count (number of individuals that dominating one individual)
397  std::vector<population::size_type> dom_count_copy(m_dom_count);
398 
399  // 1 - Find the first Pareto Front
400  for (population::size_type idx = 0; idx < m_container.size(); ++idx){
401  if (m_dom_count[idx] == 0) {
402  F.push_back(idx);
403  }
404  }
405 
406  unsigned int irank = 1;
407 
408  // We loop to find subsequent fronts
409  while (F.size()!=0) {
410  // update crowding distance of the current pareto front
411  population::update_crowding_d(F);
412  //For each individual F in the current front
413  for (population::size_type i=0; i < F.size(); ++i) {
414  //For each individual dominated by F
415  for (population::size_type j=0; j<m_dom_list[F[i]].size(); ++j) {
416  dom_count_copy[m_dom_list[F[i]][j]]--;
417  if (dom_count_copy[m_dom_list[F[i]][j]] == 0){
418  S.push_back(m_dom_list[F[i]][j]);
419  m_pareto_rank[m_dom_list[F[i]][j]] = irank;
420  }
421  }
422  }
423  F = S;
424  S.clear();
425  irank++;
426  }
427 }
428 
429 
431 
440 void population::update_crowding_d(std::vector<population::size_type> I) const {
441 
442  size_type lastidx = I.size() - 1;
443 
444  // we construct the comparison functor along the first fitness component
445  one_dim_fit_comp funct(*this,0);
446 
447  // we loop along fitness components
448  for (fitness_vector::size_type i = 0; i < problem().get_f_dimension(); ++i) {
449  funct.m_dim = i;
450  // we sort I along the fitness_dimension i
451  std::sort(I.begin(),I.end(), funct );
452  // assign Inf to the boundaries
453  m_crowding_d[I[0]] = std::numeric_limits<double>::max();
454  m_crowding_d[I[lastidx]] = std::numeric_limits<double>::max();
455  //and compute the crowding distance
456  double df = get_individual(I[lastidx]).cur_f[i] - get_individual(I[0]).cur_f[i];
457  for (population::size_type j = 1; j < lastidx; ++j) {
458  if (df == 0.0) { // handles the case in which the pareto front collapses to one single point
459  m_crowding_d[I[j]] += 0.0; // avoiding creation of nans that can't be serialized
460  } else {
461  m_crowding_d[I[j]] += (get_individual(I[j+1]).cur_f[i] - get_individual(I[j-1]).cur_f[i])/df;
462  }
463  }
464  }
465 }
466 
468 
475 std::vector<std::vector<population::size_type> > population::compute_pareto_fronts() const {
476  std::vector<std::vector<population::size_type> > retval;
477 
478  // Be sure to have actual information about pareto rank
480 
481  for (population::size_type idx = 0; idx < size(); ++idx) {
482  if (m_pareto_rank[idx] >= retval.size()) {
483  retval.resize(m_pareto_rank[idx] + 1);
484  }
485  retval[m_pareto_rank[idx]].push_back(idx);
486  }
487 
488  return retval;
489 }
490 
492 
501 
502  fitness_vector ideal(problem().get_f_dimension(),std::numeric_limits<double>::max());
503  for (population::size_type idx = 0; idx < size(); ++idx) {
504  if (m_pareto_rank[idx] == 0) { //it is in the first pareto front
505  for(fitness_vector::size_type i = 0; i < ideal.size(); ++i) {
506  if (m_container[idx].cur_f[i] < ideal[i]) {
507  ideal[i] = m_container[idx].cur_f[i];
508  }
509  }
510  }
511  }
512  return ideal;
513 }
514 
516 
525 
526  fitness_vector nadir(m_champion.f);
527  for (population::size_type idx = 0; idx < size(); ++idx) {
528  if (m_pareto_rank[idx] == 0) { //it is in the first pareto front
529  for(fitness_vector::size_type i = 0; i < nadir.size(); ++i) {
530  if (m_container[idx].cur_f[i] > nadir[i]) {
531  nadir[i] = m_container[idx].cur_f[i];
532  }
533  }
534  }
535  }
536  return nadir;
537 }
538 
540 
552 population::crowded_comparison_operator::crowded_comparison_operator(const population &pop):m_pop(pop)
553 {
554  if (m_pop.size() < 2) {
555  pagmo_throw(value_error, "the population seems to contain one or zero individuals, comparisons between individuals do not make sense");
556  }
557  if (m_pop.problem().get_f_dimension() < 2) {
558  pagmo_throw(value_error, "The crowded comparison operator can only operate on multi-objective problems.");
559  }
560 }
561 
563 
576 bool population::crowded_comparison_operator::operator()(const individual_type &i1, const individual_type &i2) const
577 {
578  if (!(&i1 >= &m_pop.m_container.front() && &i1 <= &m_pop.m_container.back())) {
579  pagmo_throw(value_error, "operator called on individuals that do not belong to the population");
580  }
581 
582  if (!(&i2 >= &m_pop.m_container.front() && &i2 <= &m_pop.m_container.back())) {
583  pagmo_throw(value_error, "operator called on individuals that do not belong to the population");
584  }
585  const size_type idx1 = &i1 - &m_pop.m_container.front(), idx2 = &i2 - &m_pop.m_container.front();
586  if (m_pop.m_pareto_rank[idx1] == m_pop.m_pareto_rank[idx2]) {
587  return (m_pop.m_crowding_d[idx1] > m_pop.m_crowding_d[idx2]);
588  }
589  else {
590  return (m_pop.m_pareto_rank[idx1] < m_pop.m_pareto_rank[idx2]);
591  }
592 }
593 
595 
608 bool population::crowded_comparison_operator::operator()(const size_type &idx1, const size_type &idx2) const
609 {
610  if (idx1 >= m_pop.size() || idx2 >= m_pop.size()) {
611  pagmo_throw(index_error, "operator called on out of bound indexes");
612  }
613 
614  if (m_pop.m_pareto_rank[idx1] == m_pop.m_pareto_rank[idx2]) {
615  return (m_pop.m_crowding_d[idx1] > m_pop.m_crowding_d[idx2]);
616  }
617  else {
618  return (m_pop.m_pareto_rank[idx1] < m_pop.m_pareto_rank[idx2]);
619  }
620 }
621 
623 
633 population::trivial_comparison_operator::trivial_comparison_operator(const population &pop):m_pop(pop) {}
634 
636 
644 bool population::trivial_comparison_operator::operator()(const individual_type &i1, const individual_type &i2) const
645 {
646  if (!(&i1 >= &m_pop.m_container.front() && &i1 <= &m_pop.m_container.back())) {
647  pagmo_throw(value_error, "operator called on individuals that do not belong to the population");
648  }
649 
650  if (!(&i2 >= &m_pop.m_container.front() && &i2 <= &m_pop.m_container.back())) {
651  pagmo_throw(value_error, "operator called on individuals that do not belong to population");
652  }
653  const size_type idx1 = &i1 - &m_pop.m_container.front(), idx2 = &i2 - &m_pop.m_container.front();
654  return m_pop.problem().compare_fc(m_pop.get_individual(idx1).cur_f, m_pop.get_individual(idx1).cur_c, m_pop.get_individual(idx2).cur_f,m_pop.get_individual(idx2).cur_c);
655 }
656 
658 
666 bool population::trivial_comparison_operator::operator()(const size_type &idx1, const size_type &idx2) const
667 {
668  if (idx1 >= m_pop.size() || idx2 >= m_pop.size()) {
669  pagmo_throw(index_error, "operator called on out of bound indexes");
670  }
671  return m_pop.problem().compare_fc(m_pop.get_individual(idx1).cur_f, m_pop.get_individual(idx1).cur_c, m_pop.get_individual(idx2).cur_f,m_pop.get_individual(idx2).cur_c);
672 }
673 
675 
692 population::size_type population::get_worst_idx() const
693 {
694  if (!size()) {
695  pagmo_throw(value_error,"empty population, cannot compute position of worst individual");
696  }
697  container_type::const_iterator it;
698  if (m_prob->get_f_dimension() == 1) {
699  it = std::max_element(m_container.begin(),m_container.end(),trivial_comparison_operator(*this));
700  }
701  else {
703  it = std::max_element(m_container.begin(),m_container.end(),crowded_comparison_operator(*this));
704  }
705  return boost::numeric_cast<size_type>(std::distance(m_container.begin(),it));
706 }
707 
709 
725 population::size_type population::get_best_idx() const
726 {
727  if (!size()) {
728  pagmo_throw(value_error,"empty population, cannot compute position of best individual");
729  }
730  container_type::const_iterator it;
731  if (m_prob->get_f_dimension() == 1) {
732  it = std::min_element(m_container.begin(),m_container.end(),trivial_comparison_operator(*this));
733  }
734  else {
736  it = std::min_element(m_container.begin(),m_container.end(),crowded_comparison_operator(*this));
737  } return boost::numeric_cast<size_type>(std::distance(m_container.begin(),it));
738 }
739 
741 
758 std::vector<population::size_type> population::get_best_idx(const population::size_type& N) const
759 {
760  if (!size()) {
761  pagmo_throw(value_error,"empty population, cannot compute position of best individual");
762  }
763  if (N > size()) {
764  pagmo_throw(value_error,"Best N individuals requested, but population has size smaller than N");
765  }
766  std::vector<population::size_type> retval;
767  retval.reserve(size());
768  for (population::size_type i=0; i<size(); ++i){
769  retval.push_back(i);
770  }
771  if (m_prob->get_f_dimension() == 1) {
772  std::sort(retval.begin(),retval.end(),trivial_comparison_operator(*this));
773  }
774  else {
776  std::sort(retval.begin(),retval.end(),crowded_comparison_operator(*this));
777  }
778  retval.resize(N);
779  return retval;
780 }
781 
782 
784 
794 void population::repair(const population::size_type &idx, const algorithm::base_ptr &repair_algo)
795 {
796  if (idx >= size()) {
797  pagmo_throw(index_error,"invalid individual position");
798  }
799 
800  const decision_vector &current_x = m_container[idx].cur_x;
801  const constraint_vector &current_c = m_container[idx].cur_c;
802 
803  // if feasible, nothing is done
804  if(m_prob->feasibility_c(current_c)) {
805  return;
806  }
807 
808  problem::con2uncon feasibility_problem(*m_prob,problem::con2uncon::FEASIBILITY);
809 
810  population pop_repair(feasibility_problem);
811  pop_repair.clear();
812  pop_repair.push_back(current_x);
813 
814  repair_algo->evolve(pop_repair);
815 
816  this->set_x(idx,pop_repair.champion().x);
817 
818 }
819 
820 
822 
831 std::string population::human_readable_terse() const
832 {
833  std::ostringstream oss;
834  oss << (*m_prob) << '\n';
835  oss << "Number of individuals: " << size() << '\n';
836  return oss.str();
837 }
838 
840 
848 std::string population::human_readable() const
849 {
850  std::ostringstream oss;
851  oss << human_readable_terse();
852  if (size()) {
853  oss << "\nList of individuals:\n";
854  for (size_type i = 0; i < size(); ++i) {
855  oss << '#' << i << ":\n";
856  oss << m_container[i] << "\tDominates:\t\t\t" << m_dom_list[i] << '\n';
857  oss << "\tIs dominated by:\t\t" << m_dom_count[i] << "\tindividuals" << '\n';
858  }
859  }
860  if (m_champion.x.size()) {
861  oss << "Champion:\n";
862  oss << m_champion << '\n';
863  } else {
864  pagmo_assert(!size());
865  oss << "No champion yet.\n";
866  }
867  return oss.str();
868 }
869 
870 // Update the champion with individual in position idx, if better or if the champion has not been set yet.
871 void population::update_champion(const size_type &idx)
872 {
873  pagmo_assert(idx < m_container.size());
874  if (!m_champion.x.size() || m_prob->compare_fc(m_container[idx].best_f,m_container[idx].best_c,m_champion.f,m_champion.c)) {
875  m_champion.x = m_container[idx].best_x;
876  m_champion.f = m_container[idx].best_f;
877  m_champion.c = m_container[idx].best_c;
878  }
879 }
880 
882 
888 void population::set_x(const size_type &idx, const decision_vector &x)
889 {
890  if (idx >= size()) {
891  pagmo_throw(index_error,"invalid individual position");
892  }
893  if (!m_prob->verify_x(x)) {
894  pagmo_throw(value_error,"decision vector is not compatible with problem");
895 
896  }
897  // Set decision vector.
898  m_container[idx].cur_x = x;
899  // Update current fitness vector.
900  m_prob->objfun(m_container[idx].cur_f,x);
901  // Update current constraints vector.
902  m_prob->compute_constraints(m_container[idx].cur_c,x);
903  // If needed, update the best decision, fitness and constraint vectors for the individual.
904  // NOTE: we update the bests in two cases:
905  // - the bests are empty, meaning they are not defined and we are being called by push_back()
906  // - the bests are defined, but they are worse than the currents.
907  pagmo_assert((!m_container[idx].best_x.size() && !m_container[idx].best_f.size()) ||
908  (m_container[idx].best_x.size() && m_container[idx].best_f.size()));
909  if (!m_container[idx].best_x.size() ||
910  m_prob->compare_fc(m_container[idx].cur_f,m_container[idx].cur_c,m_container[idx].best_f,m_container[idx].best_c))
911  {
912  m_container[idx].best_x = m_container[idx].cur_x;
913  m_container[idx].best_f = m_container[idx].cur_f;
914  m_container[idx].best_c = m_container[idx].cur_c;
915  }
916  // Update the champion.
917  update_champion(idx);
918  // Updated domination lists.
919  update_dom(idx);
920 }
921 
923 
932 void population::erase(const population::size_type & idx) {
933 
934  pagmo_assert(m_dom_list.size() == size() && m_dom_count.size() == size() && idx < size());
935 
936  if (idx >= size()) {
937  pagmo_throw(index_error,"invalid individual position");
938  }
939  for (population::size_type i = 0; i < m_dom_list[idx].size(); ++i) {
940  m_dom_count[m_dom_list[idx][i]]--;
941  }
942  m_container.erase(m_container.begin() + idx);
943  m_dom_count.erase(m_dom_count.begin() + idx);
944  m_dom_list.erase(m_dom_list.begin() + idx);
945  // Since an element is erased indexes in dom_list need an update
946  for (population::size_type i=0; i<m_dom_list.size(); ++i){
947  for(population::size_type j=0; j<m_dom_list[i].size();++j) {
948  if (m_dom_list[i][j] == idx) {
949  m_dom_list[i].erase(m_dom_list[i].begin()+j);
950  // If we did not erase the last individual
951  if (m_dom_list[i].size() > j) {
952  //check the next individual which would be skipped otherwise
953  if (m_dom_list[i][j] > idx) m_dom_list[i][j]--;
954  }
955  }
956  else if (m_dom_list[i][j] > idx) m_dom_list[i][j]--;
957  }
958  }
959 }
960 
962 
968 void population::push_back(const decision_vector &x)
969 {
970  if (!m_prob->verify_x(x)) {
971  pagmo_throw(value_error,"decision vector is not compatible with problem");
972 
973  }
974  // Store sizes temporarily.
975  const fitness_vector::size_type f_size = m_prob->get_f_dimension();
976  const constraint_vector::size_type c_size = m_prob->get_c_dimension();
977  const decision_vector::size_type p_size = m_prob->get_dimension();
978  // Push back an empty individual.
979  m_container.push_back(individual_type());
980  m_dom_list.push_back(std::vector<size_type>());
981  m_dom_count.push_back(0);
982  // Resize individual's elements.
983  m_container.back().cur_x.resize(p_size);
984  m_container.back().cur_v.resize(p_size);
985  m_container.back().cur_c.resize(c_size);
986  m_container.back().cur_f.resize(f_size);
987  // NOTE: do not allocate space for bests, as they are not defined yet. set_x will take
988  // care of it.
989  // Set the individual.
990  set_x(m_container.size() - 1,x);
991  // Initialise randomly the velocity vector.
992  init_velocity(m_container.size() - 1);
993 }
994 
996 
1002 void population::set_v(const size_type &idx, const decision_vector &v)
1003 {
1004  if (idx >= size()) {
1005  pagmo_throw(index_error,"invalid individual position");
1006  }
1007  if (v.size() != this->problem().get_dimension()) {
1008  pagmo_throw(value_error,"velocity vector is not compatible with problem");
1009  }
1010  // Set decision vector.
1011  m_container[idx].cur_v = v;
1012 }
1013 
1015 
1018 const problem::base &population::problem() const
1019 {
1020  return *m_prob;
1021 }
1022 
1024 
1027 const population::champion_type &population::champion() const
1028 {
1029  if (!m_champion.x.size()) {
1030  pagmo_assert(!size());
1031  pagmo_throw(value_error,"champion has not been determined yet");
1032  }
1033  return m_champion;
1034 }
1035 
1037 
1040 population::size_type population::size() const
1041 {
1042  return m_container.size();
1043 }
1044 
1046 
1050 void population::clear()
1051 {
1052  m_container.clear();
1053  m_dom_list.clear();
1054  m_dom_count.clear();
1055  m_crowding_d.clear();
1056  m_pareto_rank.clear();
1057  m_champion = champion_type();
1058 }
1059 
1061 
1064 population::const_iterator population::begin() const
1065 {
1066  return m_container.begin();
1067 }
1068 
1070 
1073 population::const_iterator population::end() const
1074 {
1075  return m_container.end();
1076 }
1077 
1079 
1096 std::pair<std::vector<population::size_type>, unsigned int> population::race(const size_type n_final, const unsigned int min_trials, const unsigned int max_count, double delta, const std::vector<size_type>& active_set, const bool race_best, const bool screen_output) const
1097 {
1098  unsigned int seed = m_urng();
1099  util::racing::race_pop m_race_pop(*this, seed);
1100  return m_race_pop.run(n_final, min_trials, max_count, delta, active_set, util::racing::race_pop::MAX_BUDGET, race_best, screen_output);
1101 }
1102 
1104 
1112 population::size_type population::n_dominated(const individual_type &ind) const
1113 {
1114  size_type retval = 0;
1115  for (size_type i = 0; i < m_container.size(); ++i) {
1116  if (m_prob->compare_fc(ind.best_f,ind.best_c,
1117  m_container[i].best_f,m_container[i].best_c))
1118  {
1119  ++retval;
1120  }
1121  }
1122  return retval;
1123 }
1124 
1125 
1127 
1135 std::ostream &operator<<(std::ostream &s, const population &pop)
1136 {
1137  s << pop.human_readable();
1138  return s;
1139 }
1140 
1142 
1150 std::ostream &operator<<(std::ostream &s, const population::individual_type &ind)
1151 {
1152  s << ind.human_readable();
1153  return s;
1154 }
1155 
1157 
1165 std::ostream &operator<<(std::ostream &s, const population::champion_type &champ)
1166 {
1167  s << champ.human_readable();
1168  return s;
1169 }
1170 
1171 }
boost::shared_ptr< base > base_ptr
Alias for shared pointer to base algorithm.
Root PaGMO namespace.
size_type get_domination_count(const size_type &) const
Get domination count.
Definition: population.cpp:314
boost::shared_ptr< base > base_ptr
Alias for shared pointer to base problem.
Definition: problem/base.h:62
population & operator=(const population &)
Assignment operator.
Definition: population.cpp:115
std::vector< double > decision_vector
Decision vector type.
Definition: types.h:40
The sum of the constraint violation is used as objective function of the transformed problem...
Definition: con2uncon.h:54
fitness_vector cur_f
Current fitness vector.
Definition: population.h:89
std::ostream & operator<<(std::ostream &s, const archipelago &a)
Overload stream operator for pagmo::archipelago.
const individual_type & get_individual(const size_type &) const
Get constant reference to individual at position n.
Definition: population.cpp:277
void update_pareto_information() const
Update Pareto Information.
Definition: population.cpp:384
Individuals stored in the population.
Definition: population.h:80
fitness_vector compute_ideal() const
Compute and return the ideal objective vector.
Definition: population.cpp:499
population(const problem::base &, int=0, const boost::uint32_t &seed=getSeed())
Constructor from problem::base and number of individuals.
Definition: population.cpp:69
Base problem class.
Definition: problem/base.h:148
Population class.
Definition: population.h:70
Fixed number of function evaluations.
Definition: race_pop.h:69
size_type get_dimension() const
Return global dimension.
decision_vector x
Decision vector.
Definition: population.h:149
fitness_vector f
Fitness vector.
Definition: population.h:153
const std::vector< size_type > & get_domination_list(const size_type &) const
Get domination list.
Definition: population.cpp:296
std::vector< double > fitness_vector
Fitness vector type.
Definition: types.h:42
double get_crowding_d(const size_type &) const
Get Crowding Distance.
Definition: population.cpp:356
std::vector< double > constraint_vector
Constraint vector type.
Definition: types.h:44
container_type::const_iterator const_iterator
Const iterator.
Definition: population.h:195
constraint_vector c
Constraint vector.
Definition: population.h:151
container_type::size_type size_type
Population size type.
Definition: population.h:192
double mean_velocity() const
Computes the mean curent velocity of all individuals in the population.
Definition: population.cpp:196
fitness_vector compute_nadir() const
Compute and return the nadir objective vector.
Definition: population.cpp:523
size_type get_pareto_rank(const size_type &) const
Get Pareto rank.
Definition: population.cpp:334
f_size_type get_f_dimension() const
Return fitness dimension.
void reinit()
Re-initialise all individuals.
Definition: population.cpp:218
std::vector< std::vector< size_type > > compute_pareto_fronts() const
Computes and returns the population Pareto fronts.
Definition: population.cpp:475