26 #include "../population.h"
28 namespace pagmo {
namespace problem {
37 std::vector<double> dumb(3,0);
38 m_weights = std::vector<std::vector<double> > (3,dumb);
55 compute_dimensions(weights.size(), encoding)[0],
56 compute_dimensions(weights.size(), encoding)[1],
60 check_weights(m_weights);
77 void tsp::check_weights(
const std::vector<std::vector<double> > &matrix)
const
79 decision_vector::size_type n_cols = matrix.size();
81 for (decision_vector::size_type i = 0; i < n_cols; ++i) {
82 decision_vector::size_type n_rows = matrix[i].size();
85 pagmo_throw(value_error,
"adjacency matrix is not square");
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))
91 pagmo_throw(value_error,
"adjacency matrix contains zero values.");
92 if (i != j && (!matrix.at(i).at(j)) == matrix[i][j])
93 pagmo_throw(value_error,
"adjacency matrix contains NaN values.");
98 boost::array<int, 2> tsp::compute_dimensions(decision_vector::size_type n_cities,
base_tsp::encoding_type encoding)
100 boost::array<int,2> retval;
103 retval[0] = n_cities*(n_cities-1)+2;
104 retval[1] = (n_cities-1)*(n_cities-2);
127 for (decision_vector::size_type i=0; i<n_cities-1; ++i) {
128 f[0] += m_weights[tour[i]][tour[i+1]];
130 f[0]+= m_weights[tour[n_cities-1]][tour[0]];
136 for (decision_vector::size_type i=0; i<n_cities-1; ++i) {
137 f[0] += m_weights[tour[i]][tour[i+1]];
139 f[0]+= m_weights[tour[n_cities-1]][tour[0]];
144 for (decision_vector::size_type i=0; i<n_cities-1; ++i) {
145 f[0] += m_weights[x[i]][x[i+1]];
147 f[0]+= m_weights[x[n_cities-1]][x[0]];
154 size_t tsp::compute_idx(
const size_t i,
const size_t j,
const size_t n)
const
156 pagmo_assert( i!=j && i<n && j<n );
157 return i*(n-1) + j - (j>i? 1:0);
169 for (
size_t i = 0; i < n_cities; i++) {
172 for (
size_t j = 0; j < n_cities; j++) {
174 decision_vector::size_type rows = compute_idx(i, j, n_cities);
175 decision_vector::size_type cols = compute_idx(j, i, n_cities);
177 c[i+n_cities] += x[cols];
180 c[i+n_cities] = c[i+n_cities]-1;
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++)
192 if (current_city==j)
continue;
193 if (x[compute_idx(current_city, j, n_cities)] == 1)
199 current_city = next_city;
202 for (
size_t i = 1; i < n_cities; i++) {
203 for (
size_t j = 1; j < n_cities; j++)
206 c[2*n_cities+count] = u[i]-u[j] + (n_cities+1) * x[compute_idx(i, j, n_cities)] - n_cities;
216 std::vector<population::size_type> range(n_cities);
217 for (std::vector<population::size_type>::size_type i=0; i<range.size(); ++i)
221 c[0] = !std::is_permutation(x.begin(),x.end(),range.begin());
229 double tsp::distance(decision_vector::size_type i, decision_vector::size_type j)
const
231 return m_weights[i][j];
246 return "Travelling Salesman Problem (TSP-ATSP)";
255 std::ostringstream oss;
256 oss <<
"\n\tNumber of cities: " <<
get_n_cities() <<
'\n';
257 oss <<
"\tEncoding: ";
260 oss <<
"FULL" <<
'\n';
263 oss <<
"RANDOMKEYS" <<
'\n';
266 oss <<
"CITIES" <<
'\n';
269 oss <<
"\tWeight Matrix: \n";
270 for (decision_vector::size_type i=0; i<
get_n_cities() ; ++i)
272 oss <<
"\t\t" << m_weights[i] <<
'\n';
275 oss <<
"\t\t..." <<
'\n';
boost::shared_ptr< base > base_ptr
Alias for shared pointer to base problem.
std::vector< double > decision_vector
Decision vector type.
const std::vector< std::vector< double > > & get_weights() const
Getter for m_weights.
base_ptr clone() const
Copy constructor for polymorphic objects (deep copy)
double distance(decision_vector::size_type, decision_vector::size_type) const
Definition of distance function.
pagmo::decision_vector full2cities(const pagmo::decision_vector &) const
From FULL to CITIES encoding.
As a vector of doubles in [0,1].
tsp()
Default constructor.
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::vector< double > fitness_vector
Fitness vector type.
std::vector< double > constraint_vector
Constraint vector type.
A static Travelling Salesman Problem.
std::string human_readable_extra() const
Extra human readable info for the problem.
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.
encoding_type get_encoding() const
Getter for m_encoding.
std::string get_name() const
Returns the problem name.