PaGMO  1.1.5
tsp.cpp
1 /*****************************************************************************
2  * Copyright (C) 2004-2014 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 "tsp.h"
26 #include "../population.h"
27 
28 namespace pagmo { namespace problem {
29 
31 
35  tsp::tsp() : base_tsp(3, 0, 0 , base_tsp::RANDOMKEYS), m_weights()
36  {
37  std::vector<double> dumb(3,0);
38  m_weights = std::vector<std::vector<double> > (3,dumb);
39  m_weights[0][1] = 1;
40  m_weights[0][2] = 1;
41  m_weights[2][1] = 1;
42  m_weights[1][0] = 1;
43  m_weights[2][0] = 1;
44  m_weights[1][2] = 1;
45  }
46 
48 
53  tsp::tsp(const std::vector<std::vector<double> >& weights, const base_tsp::encoding_type& encoding):
54  base_tsp(weights.size(),
55  compute_dimensions(weights.size(), encoding)[0],
56  compute_dimensions(weights.size(), encoding)[1],
57  encoding
58  ), m_weights(weights)
59  {
60  check_weights(m_weights);
61  }
62 
65  {
66  return base_ptr(new tsp(*this));
67  }
68 
70 
77  void tsp::check_weights(const std::vector<std::vector<double> > &matrix) const
78  {
79  decision_vector::size_type n_cols = matrix.size();
80 
81  for (decision_vector::size_type i = 0; i < n_cols; ++i) {
82  decision_vector::size_type n_rows = matrix[i].size();
83  // check if the matrix is square
84  if (n_rows != n_cols)
85  pagmo_throw(value_error, "adjacency matrix is not square");
86 
87  for (size_t j = 0; j < n_rows; ++j) {
88  if (i == j && matrix.at(i).at(j) != 0)
89  pagmo_throw(value_error, "main diagonal elements must all be zeros.");
90  if (i != j && !matrix.at(i).at(j)) // fully connected
91  pagmo_throw(value_error, "adjacency matrix contains zero values.");
92  if (i != j && (!matrix.at(i).at(j)) == matrix[i][j]) // fully connected
93  pagmo_throw(value_error, "adjacency matrix contains NaN values.");
94  }
95  }
96  }
97 
98  boost::array<int, 2> tsp::compute_dimensions(decision_vector::size_type n_cities, base_tsp::encoding_type encoding)
99  {
100  boost::array<int,2> retval;
101  switch( encoding ) {
102  case FULL:
103  retval[0] = n_cities*(n_cities-1)+2;
104  retval[1] = (n_cities-1)*(n_cities-2);
105  break;
106  case RANDOMKEYS:
107  retval[0] = 0;
108  retval[1] = 0;
109  break;
110  case CITIES:
111  retval[0] = 1;
112  retval[1] = 0;
113  break;
114  }
115  return retval;
116  }
117 
118  void tsp::objfun_impl(fitness_vector &f, const decision_vector& x) const
119  {
120  f[0]=0;
121  decision_vector tour;
122  decision_vector::size_type n_cities = get_n_cities();
123  switch( get_encoding() ) {
124  case FULL:
125  {
126  tour = full2cities(x);
127  for (decision_vector::size_type i=0; i<n_cities-1; ++i) {
128  f[0] += m_weights[tour[i]][tour[i+1]];
129  }
130  f[0]+= m_weights[tour[n_cities-1]][tour[0]];
131  break;
132  }
133  case RANDOMKEYS:
134  {
135  tour = randomkeys2cities(x);
136  for (decision_vector::size_type i=0; i<n_cities-1; ++i) {
137  f[0] += m_weights[tour[i]][tour[i+1]];
138  }
139  f[0]+= m_weights[tour[n_cities-1]][tour[0]];
140  break;
141  }
142  case CITIES:
143  {
144  for (decision_vector::size_type i=0; i<n_cities-1; ++i) {
145  f[0] += m_weights[x[i]][x[i+1]];
146  }
147  f[0]+= m_weights[x[n_cities-1]][x[0]];
148  break;
149  }
150  }
151  return;
152  }
153 
154  size_t tsp::compute_idx(const size_t i, const size_t j, const size_t n) const
155  {
156  pagmo_assert( i!=j && i<n && j<n );
157  return i*(n-1) + j - (j>i? 1:0);
158  }
159 
160  void tsp::compute_constraints_impl(constraint_vector &c, const decision_vector& x) const
161  {
162  decision_vector::size_type n_cities = get_n_cities();
163 
164  switch( get_encoding() )
165  {
166  case FULL:
167  {
168  // 1 - We set the equality constraints
169  for (size_t i = 0; i < n_cities; i++) {
170  c[i] = 0;
171  c[i+n_cities] = 0;
172  for (size_t j = 0; j < n_cities; j++) {
173  if(i==j) continue; // ignoring main diagonal
174  decision_vector::size_type rows = compute_idx(i, j, n_cities);
175  decision_vector::size_type cols = compute_idx(j, i, n_cities);
176  c[i] += x[rows];
177  c[i+n_cities] += x[cols];
178  }
179  c[i] = c[i]-1;
180  c[i+n_cities] = c[i+n_cities]-1;
181  }
182 
183  //2 - We set the inequality constraints
184  //2.1 - First we compute the uj (see http://en.wikipedia.org/wiki/Travelling_salesman_problem#Integer_linear_programming_formulation)
185  // we start always out tour from the first city, without loosing generality
186  size_t next_city = 0,current_city = 0;
187  std::vector<int> u(n_cities);
188  for (size_t i = 0; i < n_cities; i++) {
189  u[current_city] = i+1;
190  for (size_t j = 0; j < n_cities; j++)
191  {
192  if (current_city==j) continue;
193  if (x[compute_idx(current_city, j, n_cities)] == 1)
194  {
195  next_city = j;
196  break;
197  }
198  }
199  current_city = next_city;
200  }
201  int count=0;
202  for (size_t i = 1; i < n_cities; i++) {
203  for (size_t j = 1; j < n_cities; j++)
204  {
205  if (i==j) continue;
206  c[2*n_cities+count] = u[i]-u[j] + (n_cities+1) * x[compute_idx(i, j, n_cities)] - n_cities;
207  count++;
208  }
209  }
210  break;
211  }
212  case RANDOMKEYS:
213  break;
214  case CITIES:
215  {
216  std::vector<population::size_type> range(n_cities);
217  for (std::vector<population::size_type>::size_type i=0; i<range.size(); ++i)
218  {
219  range[i]=i;
220  }
221  c[0] = !std::is_permutation(x.begin(),x.end(),range.begin());
222  break;
223  }
224  }
225  return;
226  }
227 
229  double tsp::distance(decision_vector::size_type i, decision_vector::size_type j) const
230  {
231  return m_weights[i][j];
232  }
233 
235 
238  const std::vector<std::vector<double> >& tsp::get_weights() const
239  {
240  return m_weights;
241  }
242 
244  std::string tsp::get_name() const
245  {
246  return "Travelling Salesman Problem (TSP-ATSP)";
247  }
248 
250 
253  std::string tsp::human_readable_extra() const
254  {
255  std::ostringstream oss;
256  oss << "\n\tNumber of cities: " << get_n_cities() << '\n';
257  oss << "\tEncoding: ";
258  switch( get_encoding() ) {
259  case FULL:
260  oss << "FULL" << '\n';
261  break;
262  case RANDOMKEYS:
263  oss << "RANDOMKEYS" << '\n';
264  break;
265  case CITIES:
266  oss << "CITIES" << '\n';
267  break;
268  }
269  oss << "\tWeight Matrix: \n";
270  for (decision_vector::size_type i=0; i<get_n_cities() ; ++i)
271  {
272  oss << "\t\t" << m_weights[i] << '\n';
273  if (i>5)
274  {
275  oss << "\t\t..." << '\n';
276  break;
277  }
278  }
279  return oss.str();
280  }
281 
282 
283 }} //namespaces
284 
285 BOOST_CLASS_EXPORT_IMPLEMENT(pagmo::problem::tsp)
Root PaGMO namespace.
boost::shared_ptr< base > base_ptr
Alias for shared pointer to base problem.
Definition: problem/base.h:62
std::vector< double > decision_vector
Decision vector type.
Definition: types.h:40
const std::vector< std::vector< double > > & get_weights() const
Getter for m_weights.
Definition: tsp.cpp:238
base_ptr clone() const
Copy constructor for polymorphic objects (deep copy)
Definition: tsp.cpp:64
double distance(decision_vector::size_type, decision_vector::size_type) const
Definition of distance function.
Definition: tsp.cpp:229
pagmo::decision_vector full2cities(const pagmo::decision_vector &) const
From FULL to CITIES encoding.
Definition: base_tsp.cpp:74
As a vector of doubles in [0,1].
Definition: base_tsp.h:69
tsp()
Default constructor.
Definition: tsp.cpp:35
decision_vector::size_type get_n_cities() const
Getter for m_n_cities.
Definition: base_tsp.cpp:193
encoding_type
Mechanism used to encode the sequence of vertices to be visited.
Definition: base_tsp.h:68
std::vector< double > fitness_vector
Fitness vector type.
Definition: types.h:42
std::vector< double > constraint_vector
Constraint vector type.
Definition: types.h:44
A static Travelling Salesman Problem.
Definition: tsp.h:49
std::string human_readable_extra() const
Extra human readable info for the problem.
Definition: tsp.cpp:253
As a matrix with ones and zeros.
Definition: base_tsp.h:70
Base TSP (Travelling Salesman Problem).
Definition: base_tsp.h:64
As a sequence of cities ids.
Definition: base_tsp.h:71
pagmo::decision_vector randomkeys2cities(const pagmo::decision_vector &) const
From RANDOMKEYS to CITIES encoding.
Definition: base_tsp.cpp:127
encoding_type get_encoding() const
Getter for m_encoding.
Definition: base_tsp.cpp:184
std::string get_name() const
Returns the problem name.
Definition: tsp.cpp:244