26 #include "../population.h"
28 namespace pagmo {
namespace problem {
38 std::vector<double> dumb(3,0);
39 m_weights = std::vector<std::vector<double> > (3,dumb);
47 m_values = std::vector<double>(3,1.0);
48 m_max_edge_length = 1;
63 compute_dimensions(weights.size(), encoding)[0],
64 compute_dimensions(weights.size(), encoding)[1],
66 ), m_weights(weights), m_values(values), m_max_path_length(max_path_length)
68 check_weights(m_weights);
69 if (weights.size() != values.size())
71 pagmo_throw(value_error,
"Size of weight matrix and values vector must be equal");
74 m_max_edge_length = 0;
75 for (std::vector<std::vector<double> >::
size_type i=0; i < weights.size(); ++i)
77 for (std::vector<std::vector<double> >::
size_type j=0; j < weights.size(); ++j)
79 m_max_edge_length = (weights[i][j] > m_max_edge_length) ? (weights[i][j]) : (m_max_edge_length);
98 void tsp_cs::check_weights(
const std::vector<std::vector<double> > &matrix)
const
100 decision_vector::size_type n_cols = matrix.size();
102 for (decision_vector::size_type i = 0; i < n_cols; ++i) {
103 decision_vector::size_type n_rows = matrix.at(i).size();
105 if (n_rows != n_cols)
106 pagmo_throw(value_error,
"adjacency matrix is not square");
108 for (
size_t j = 0; j < n_rows; ++j) {
109 if (i == j && matrix.at(i).at(j) != 0)
110 pagmo_throw(value_error,
"main diagonal elements must all be zeros.");
111 if (i != j && !matrix.at(i).at(j))
112 pagmo_throw(value_error,
"adjacency matrix contains zero values.");
113 if (i != j && (!matrix.at(i).at(j)) == matrix.at(i).at(j))
114 pagmo_throw(value_error,
"adjacency matrix contains NaN values.");
119 boost::array<int, 2> tsp_cs::compute_dimensions(decision_vector::size_type n_cities,
base_tsp::encoding_type encoding)
121 boost::array<int,2> retval;
124 retval[0] = n_cities*(n_cities-1)+2;
125 retval[1] = (n_cities-1)*(n_cities-2);
144 double cum_p, saved_length;
145 decision_vector::size_type dumb1, dumb2;
168 double ham_path_len = 0;
169 for (decision_vector::size_type i=0; i<n_cities-1; ++i)
171 ham_path_len += m_weights[tour[i]][tour[i+1]];
174 f[0] = -(cum_p) - (1 - ham_path_len / (n_cities * m_max_edge_length));
178 size_t tsp_cs::compute_idx(
const size_t i,
const size_t j,
const size_t n)
const
180 pagmo_assert( i!=j && i<n && j<n );
181 return i*(n-1) + j - (j>i? 1:0);
203 pagmo_throw(value_error,
"tour dimension must be equal to the city number");
208 decision_vector::size_type it_l = 0, it_r = 0;
209 bool cond_r =
true, cond_l =
true;
210 double cum_p = m_values[tour[0]];
211 double saved_length = m_max_path_length;
215 retval_l = saved_length;
226 saved_length -= m_weights[tour[it_r % n_cities]][tour[(it_r + 1) % n_cities]];
227 cum_p += m_values[tour[(it_r + 1) % n_cities]];
231 if (saved_length < 0 || (it_l % n_cities == it_r % n_cities))
235 else if (cum_p > retval_p)
238 retval_l = saved_length;
239 retval_it_l = it_l % n_cities;
240 retval_it_r = it_r % n_cities;
242 else if (cum_p == retval_p)
244 if (saved_length > retval_l)
247 retval_l = saved_length;
248 retval_it_l = it_l % n_cities;
249 retval_it_r = it_r % n_cities;
254 if (it_l % n_cities == it_r % n_cities)
261 saved_length += m_weights[tour[it_l % n_cities]][tour[(it_l + 1) % n_cities]];
262 cum_p -= m_values[tour[it_l]];
265 if (saved_length > 0)
268 if (cum_p > retval_p)
271 retval_l = saved_length;
272 retval_it_l = it_l % n_cities;
273 retval_it_r = it_r % n_cities;
275 else if (cum_p == retval_p)
277 if (saved_length > retval_l)
280 retval_l = saved_length;
281 retval_it_l = it_l % n_cities;
282 retval_it_r = it_r % n_cities;
286 if (it_l == n_cities)
303 for (
size_t i = 0; i < n_cities; i++) {
306 for (
size_t j = 0; j < n_cities; j++) {
308 decision_vector::size_type rows = compute_idx(i, j, n_cities);
309 decision_vector::size_type cols = compute_idx(j, i, n_cities);
311 c[i+n_cities] += x[cols];
314 c[i+n_cities] = c[i+n_cities]-1;
320 size_t next_city = 0,current_city = 0;
321 std::vector<int> u(n_cities);
322 for (
size_t i = 0; i < n_cities; i++) {
323 u[current_city] = i+1;
324 for (
size_t j = 0; j < n_cities; j++)
326 if (current_city==j)
continue;
327 if (x[compute_idx(current_city, j, n_cities)] == 1)
333 current_city = next_city;
336 for (
size_t i = 1; i < n_cities; i++) {
337 for (
size_t j = 1; j < n_cities; j++)
340 c[2*n_cities+count] = u[i]-u[j] + (n_cities+1) * x[compute_idx(i, j, n_cities)] - n_cities;
350 std::vector<population::size_type> range(n_cities);
351 for (std::vector<population::size_type>::size_type i=0; i<range.size(); ++i)
355 c[0] = !std::is_permutation(x.begin(),x.end(),range.begin());
365 return m_weights[i][j];
392 return m_max_path_length;
398 return "City-selection Travelling Salesman Problem (TSP-CS)";
407 std::ostringstream oss;
408 oss <<
"\n\tNumber of cities: " <<
get_n_cities() <<
'\n';
409 oss <<
"\tEncoding: ";
412 oss <<
"FULL" <<
'\n';
415 oss <<
"RANDOMKEYS" <<
'\n';
418 oss <<
"CITIES" <<
'\n';
421 oss <<
"\tCities Values: " << m_values << std::endl;
422 oss <<
"\tMax path length: " << m_max_path_length <<
'\n';
423 oss <<
"\tWeight Matrix: \n";
424 for (decision_vector::size_type i=0; i<
get_n_cities() ; ++i)
426 oss <<
"\t\t" << m_weights.at(i) <<
'\n';
429 oss <<
"\t\t..." <<
'\n';
void find_subsequence(const decision_vector &, double &, double &, decision_vector::size_type &, decision_vector::size_type &) const
Computes the best subpath of an hamilonian path satisfying the max_path_length constraint.
boost::shared_ptr< base > base_ptr
Alias for shared pointer to base problem.
std::vector< double > decision_vector
Decision vector type.
double distance(decision_vector::size_type, decision_vector::size_type) const
Definition of distance function.
const std::vector< std::vector< double > > & get_weights() const
Getter for m_weights.
const std::vector< double > & get_values() const
Getter for m_values.
double get_max_path_length() const
Getter for m_max_path_value.
The City-Selection Travelling Salesman Problem.
std::string human_readable_extra() const
Extra human readable info for the problem.
base_ptr clone() const
Copy constructor for polymorphic objects.
pagmo::decision_vector full2cities(const pagmo::decision_vector &) const
From FULL to CITIES encoding.
As a vector of doubles in [0,1].
decision_vector::size_type get_n_cities() const
Getter for m_n_cities.
encoding_type
Mechanism used to encode the sequence of vertices to be visited.
std::string get_name() const
Returns the problem name.
std::vector< double > fitness_vector
Fitness vector type.
std::vector< double > constraint_vector
Constraint vector type.
As a matrix with ones and zeros.
Base TSP (Travelling Salesman Problem).
As a sequence of cities ids.
pagmo::decision_vector randomkeys2cities(const pagmo::decision_vector &) const
From RANDOMKEYS to CITIES encoding.
decision_vector::size_type size_type
Problem's size type: the same as pagmo::decision_vector's size type.
encoding_type get_encoding() const
Getter for m_encoding.