PaGMO  1.1.5
inverover.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 <vector>
26 #include <algorithm>
27 #include <boost/random/uniform_int.hpp>
28 #include <boost/random/uniform_real.hpp>
29 #include <boost/random/variate_generator.hpp>
30 #include <iostream>
31 
32 #include "../config.h"
33 #include "../serialization.h"
34 #include "../population.h"
35 #include "../problem/base_tsp.h"
36 #include "../algorithm/nn_tsp.h"
37 #include "base.h"
38 #include "inverover.h"
39 
40 namespace pagmo { namespace algorithm {
41 
43 
49 inverover::inverover(int gen, double ri, initialization_type ini_type)
50  :base(),m_gen(gen),m_ri(ri),m_ini_type(ini_type)
51 {
52  if (gen < 0) {
53  pagmo_throw(value_error,"number of generations must be nonnegative");
54  }
55  if (ri > 1 || ri < 0) {
56  pagmo_throw(value_error,"random invert probability must be in the [0,1] range");
57  }
58 }
59 
60 
63 {
64  return base_ptr(new inverover(*this));
65 }
66 
67 
69 
74 void inverover::evolve(population &pop) const
75 {
76  const problem::base_tsp* prob;
77  //check if problem is of type pagmo::problem::base_tsp
78  try {
79  const problem::base_tsp& tsp_prob = dynamic_cast<const problem::base_tsp &>(pop.problem());
80  prob = &tsp_prob;
81  }
82  catch (const std::bad_cast& e) {
83  pagmo_throw(value_error,"Problem not of type pagmo::problem::base_tsp");
84  }
85 
86  // Let's store some useful variables.
87  const population::size_type NP = pop.size();
88  const problem::base::size_type Nv = prob->get_n_cities();
89 
90  // Initializing the random number generators
91  boost::uniform_real<double> uniform(0.0, 1.0);
92  boost::variate_generator<boost::lagged_fibonacci607 &, boost::uniform_real<double> > unif_01(m_drng, uniform);
93  boost::uniform_int<int> NPless1(0, NP - 2);
94  boost::variate_generator<boost::mt19937 &, boost::uniform_int<int> > unif_NPless1(m_urng, NPless1);
95  boost::uniform_int<int> Nv_(0, Nv - 1);
96  boost::variate_generator<boost::mt19937 &, boost::uniform_int<int> > unif_Nv(m_urng, Nv_);
97  boost::uniform_int<int> Nvless1(0, Nv - 2);
98  boost::variate_generator<boost::mt19937 &, boost::uniform_int<int> > unif_Nvless1(m_urng, Nvless1);
99 
100  //create own local population
101  std::vector<decision_vector> my_pop(NP, decision_vector(Nv));
102 
103  //check if some individuals in the population that is passed as a function input are feasible.
104  bool feasible;
105  std::vector<int> not_feasible;
106  for (size_t i = 0; i < NP; i++) {
107  feasible = prob->feasibility_x(pop.get_individual(i).cur_x);
108  if(feasible) { //if feasible store it in my_pop
109  switch(prob->get_encoding()) {
111  my_pop[i] = prob->full2cities(pop.get_individual(i).cur_x);
112  break;
114  my_pop[i] = prob->randomkeys2cities(pop.get_individual(i).cur_x);
115  break;
117  my_pop[i] = pop.get_individual(i).cur_x;
118  break;
119  }
120  } else {
121  not_feasible.push_back(i);
122  }
123  }
124 
125  //replace the not feasible individuals by feasible ones
126  int i;
127  switch (m_ini_type) {
128  case 0:
129  {
130  //random initialization (produces feasible individuals)
131  for (size_t ii = 0; ii < not_feasible.size(); ii++) {
132  i = not_feasible[ii];
133  for (size_t j = 0; j < Nv; j++) {
134  my_pop[i][j] = j;
135  }
136  }
137  int tmp;
138  size_t rnd_idx;
139  for (size_t j = 1; j < Nv-1; j++) {
140  boost::uniform_int<int> dist_(j, Nv - 1);
141  boost::variate_generator<boost::mt19937 &, boost::uniform_int<int> > dist(m_urng,dist_);
142 
143  for (size_t ii = 0; ii < not_feasible.size(); ii++) {
144  i = not_feasible[ii];
145  rnd_idx = dist();
146  tmp = my_pop[i][j];
147  my_pop[i][j] = my_pop[i][rnd_idx];
148  my_pop[i][rnd_idx] = tmp;
149  }
150 
151  }
152  break;
153  }
154  case 1:
155  {
156  //initialize with nearest neighbor algorithm
157  std::vector<int> starting_notes(std::max(Nv,not_feasible.size()));
158  for (size_t j = 0; j < starting_notes.size(); j++) {
159  starting_notes[j] = j;
160  }
161  //std::shuffle(starting_notes.begin(), starting_notes.end(), m_urng);
162  for (size_t ii = 0; ii < not_feasible.size(); ii++) {
163  i = not_feasible[ii];
164  pagmo::population one_ind_pop(pop.problem(), 1);
165  std::cout << starting_notes[i] << ' ';
166  pagmo::algorithm::nn_tsp algo(starting_notes[i] % Nv);
167  algo.evolve(one_ind_pop);
168  switch( prob->get_encoding() ) {
170  my_pop[i] = prob->full2cities(one_ind_pop.get_individual(0).cur_x);
171  break;
173  my_pop[i] = prob->randomkeys2cities(one_ind_pop.get_individual(0).cur_x);
174  break;
176  my_pop[i] = one_ind_pop.get_individual(0).cur_x;
177  break;
178  }
179  std::cout << i << ' ' << one_ind_pop.get_individual(0).cur_f << std::endl;
180  }
181  break;
182  }
183  default:
184  pagmo_throw(value_error,"Invalid initialization type");
185  }
186 
187  std::vector<fitness_vector> fitness(NP, fitness_vector(1));
188  for(size_t i=0; i < NP; i++){
189  switch( prob->get_encoding() ) {
191  fitness[i] = prob->objfun(prob->full2cities(my_pop[i]));
192  break;
194  fitness[i] = prob->objfun(prob->cities2randomkeys(my_pop[i], pop.get_individual(i).cur_x));
195  break;
197  fitness[i] = prob->objfun(my_pop[i]);
198  break;
199  }
200  }
201 
202 
203  decision_vector tmp_tour(Nv);
204  bool stop, changed;
205  size_t rnd_num, i2, pos1_c1, pos1_c2, pos2_c1, pos2_c2; //pos2_c1 denotes the position of city1 in parent2
206  fitness_vector fitness_tmp;
207 
208  //InverOver main loop
209  for(int iter = 0; iter < m_gen; iter++) {
210  for(size_t i1 = 0; i1 < NP; i1++) {
211  tmp_tour = my_pop[i1];
212  pos1_c1 = unif_Nv();
213  stop = false;
214  changed = false;
215  while(!stop){
216  if(unif_01() < m_ri) {
217  rnd_num = unif_Nvless1();
218  pos1_c2 = (rnd_num == pos1_c1? Nv-1:rnd_num);
219  } else {
220  i2 = unif_NPless1();
221  i2 = (i2 == i1? NP-1:i2);
222  pos2_c1 = std::find(my_pop[i2].begin(),my_pop[i2].end(),tmp_tour[pos1_c1])-my_pop[i2].begin();
223  pos2_c2 = (pos2_c1 == Nv-1? 0:pos2_c1+1);
224  pos1_c2 = std::find(tmp_tour.begin(),tmp_tour.end(),my_pop[i2][pos2_c2])-tmp_tour.begin();
225  }
226  stop = (abs(pos1_c1-pos1_c2)==1 || static_cast<problem::base::size_type>(abs(pos1_c1-pos1_c2))==Nv-1);
227  if(!stop) {
228  changed = true;
229  if(pos1_c1<pos1_c2) {
230  for(size_t l=0; l < (double (pos1_c2-pos1_c1-1)/2); l++) {
231  std::swap(tmp_tour[pos1_c1+1+l],tmp_tour[pos1_c2-l]);
232  }
233  pos1_c1 = pos1_c2;
234  } else {
235  //inverts the section from c1 to c2 (see documentation Note3)
236  for(size_t l=0; l < (double (pos1_c1-pos1_c2-1)/2); l++) {
237  std::swap(tmp_tour[pos1_c2+l],tmp_tour[pos1_c1-l-1]);
238  }
239  pos1_c1 = (pos1_c2 == 0? Nv-1:pos1_c2-1);
240  }
241 
242  }
243  } //end of while loop (looping over a single indvidual)
244  if(changed) {
245  switch(prob->get_encoding()) {
247  fitness_tmp = prob->objfun(prob->full2cities(tmp_tour));
248  break;
249  case problem::base_tsp::RANDOMKEYS: //using "randomly" index 0 as a temporary template
250  fitness_tmp = prob->objfun(prob->cities2randomkeys(tmp_tour, pop.get_individual(0).cur_x));
251  break;
253  fitness_tmp = prob->objfun(tmp_tour);
254  break;
255  }
256  if(prob->compare_fitness(fitness_tmp,fitness[i1])) { //replace individual?
257  my_pop[i1] = tmp_tour;
258  fitness[i1][0] = fitness_tmp[0];
259  }
260  }
261  } // end of loop over population
262  } // end of loop over generations
263 
264  //change representation of tour
265  for (size_t ii = 0; ii < NP; ii++) {
266  switch(prob->get_encoding()) {
268  pop.set_x(ii,prob->cities2full(my_pop[ii]));
269  break;
271  pop.set_x(ii,prob->cities2randomkeys(my_pop[ii],pop.get_individual(ii).cur_x));
272  break;
274  pop.set_x(ii,my_pop[ii]);
275  break;
276  }
277  }
278 } // end of evolve
279 
280 
282 std::string inverover::get_name() const
283 {
284  return "InverOver Algorithm";
285 }
286 
288 
292 {
293  std::ostringstream s;
294  s << "generations: " << m_gen << " ";
295  s << "mutation probability: " << m_ri << " ";
296  std::string ini_str = (m_ini_type==0) ? ("Random") : ("Nearest Neighbour");
297  s << "initialization method: " << ini_str;
298  return s.str();
299 }
300 
301 }} //namespaces
302 
303 BOOST_CLASS_EXPORT_IMPLEMENT(pagmo::algorithm::inverover)
boost::shared_ptr< base > base_ptr
Alias for shared pointer to base algorithm.
Root PaGMO namespace.
bool feasibility_x(const decision_vector &) const
Test feasibility of decision vector.
base_ptr clone() const
Clone method.
Definition: inverover.cpp:62
std::vector< double > decision_vector
Decision vector type.
Definition: types.h:40
inverover(int gen=10000, double ri=0.05, initialization_type ini_type=random)
Constructor.
Definition: inverover.cpp:49
const individual_type & get_individual(const size_type &) const
Get constant reference to individual at position n.
Definition: population.cpp:277
Base algorithm class.
Population class.
Definition: population.h:70
std::string get_name() const
Algorithm name.
Definition: inverover.cpp:282
pagmo::decision_vector full2cities(const pagmo::decision_vector &) const
From FULL to CITIES encoding.
Definition: base_tsp.cpp:74
bool compare_fitness(const fitness_vector &, const fitness_vector &) const
Compare fitness vectors.
As a vector of doubles in [0,1].
Definition: base_tsp.h:69
decision_vector::size_type get_n_cities() const
Getter for m_n_cities.
Definition: base_tsp.cpp:193
fitness_vector objfun(const decision_vector &) const
Return fitness of pagmo::decision_vector.
pagmo::decision_vector cities2full(const pagmo::decision_vector &) const
From CITIES to FULL encoding.
Definition: base_tsp.cpp:98
Nearest Neighbor Algorithm (NN)
Definition: nn_tsp.h:45
Inver-Over Algorithm (IO)
Definition: inverover.h:55
std::vector< double > fitness_vector
Fitness vector type.
Definition: types.h:42
void evolve(population &) const
Evolve implementation.
Definition: nn_tsp.cpp:60
container_type::size_type size_type
Population size type.
Definition: population.h:192
std::string human_readable_extra() const
Extra human readable algorithm info.
Definition: inverover.cpp:291
decision_vector cur_x
Current decision vector.
Definition: population.h:83
rng_uint32 m_urng
Random number generator for unsigned integer values.
As a matrix with ones and zeros.
Definition: base_tsp.h:70
Base TSP (Travelling Salesman Problem).
Definition: base_tsp.h:64
rng_double m_drng
Random number generator for double-precision floating point values.
As a sequence of cities ids.
Definition: base_tsp.h:71
pagmo::decision_vector cities2randomkeys(const pagmo::decision_vector &, const pagmo::decision_vector &) const
From CITIES to RANDOMKEYS encoding.
Definition: base_tsp.cpp:156
pagmo::decision_vector randomkeys2cities(const pagmo::decision_vector &) const
From RANDOMKEYS to CITIES encoding.
Definition: base_tsp.cpp:127
void evolve(population &) const
Evolve implementation.
Definition: inverover.cpp:74
decision_vector::size_type size_type
Problem's size type: the same as pagmo::decision_vector's size type.
Definition: problem/base.h:160
encoding_type get_encoding() const
Getter for m_encoding.
Definition: base_tsp.cpp:184