PaGMO
1.1.5
|
The City-Selection Travelling Salesman Problem. More...
#include <tsp_cs.h>
Public Member Functions | |
tsp_cs () | |
Constructors. More... | |
tsp_cs (const std::vector< std::vector< double > > &, const std::vector< double > &, const double, const base_tsp::encoding_type &=CITIES) | |
Constructor. More... | |
base_ptr | clone () const |
Copy constructor for polymorphic objects. More... | |
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. More... | |
Getters | |
const std::vector< std::vector< double > > & | get_weights () const |
Getter for m_weights. More... | |
const std::vector< double > & | get_values () const |
Getter for m_values. More... | |
double | get_max_path_length () const |
Getter for m_max_path_value. More... | |
Implementation of virtual methods | |
std::string | get_name () const |
Returns the problem name. | |
std::string | human_readable_extra () const |
Extra human readable info for the problem. More... | |
double | distance (decision_vector::size_type, decision_vector::size_type) const |
Definition of distance function. | |
Public Member Functions inherited from pagmo::problem::base_tsp | |
base_tsp (int n_cities, int nc, int nic, encoding_type=CITIES) | |
Constructor from dimensins and encoding. More... | |
encoding_type | get_encoding () const |
Getter for m_encoding. More... | |
decision_vector::size_type | get_n_cities () const |
Getter for m_n_cities. More... | |
pagmo::decision_vector | full2cities (const pagmo::decision_vector &) const |
From FULL to CITIES encoding. More... | |
pagmo::decision_vector | cities2full (const pagmo::decision_vector &) const |
From CITIES to FULL encoding. More... | |
pagmo::decision_vector | randomkeys2cities (const pagmo::decision_vector &) const |
From RANDOMKEYS to CITIES encoding. More... | |
pagmo::decision_vector | cities2randomkeys (const pagmo::decision_vector &, const pagmo::decision_vector &) const |
From CITIES to RANDOMKEYS encoding. More... | |
Public Member Functions inherited from pagmo::problem::base | |
base (int, int=0, int=1, int=0, int=0, const double &=0) | |
Constructor from global dimension, integer dimension, fitness dimension, global constraints dimension, inequality constraints dimension and constraints tolerance. More... | |
base (int, int, int, int, int, const std::vector< double > &) | |
Constructor from global dimension, integer dimension, fitness dimension, global constraints dimension, inequality constraints dimension and constraints tolerance. More... | |
base (const double &, const double &, int, int=0, int=1, int=0, int=0, const double &=0) | |
Constructor from values for lower and upper bounds, global dimension, integer dimension, fitness dimension, global constraints dimension, inequality constraints dimension and constraints tolerance. More... | |
base (const decision_vector &, const decision_vector &, int=0, int=1, int=0, int=0, const double &=0) | |
Constructor from upper/lower bounds, integer dimension, fitness dimension, global constraints dimension, inequality constraints dimension and constraints tolerance. More... | |
template<std::size_t N> | |
base (const double(&v1)[N], const double(&v2)[N], int ni=0, int nf=1, int nc=0, int nic=0, const double &c_tol=0) | |
Constructor from raw arrays, integer dimension, fitness dimension, global constraints dimension, inequality constraints dimension and constraints tolerance. More... | |
template<class Iterator1 , class Iterator2 > | |
base (Iterator1 start1, Iterator1 end1, Iterator2 start2, Iterator2 end2, int ni=0, int nf=1, int nc=0, int nic=0, const double &c_tol=0) | |
Constructor from iterators, integer dimension, fitness dimension, global constraints dimension, inequality constraints dimension and constraints tolerance. More... | |
virtual | ~base () |
Trivial destructor. More... | |
std::string | human_readable () const |
Return human readable representation of the problem. More... | |
bool | operator== (const base &) const |
Equality operator. More... | |
bool | operator!= (const base &) const |
Inequality operator. More... | |
bool | is_compatible (const base &) const |
Compatibility operator. More... | |
bool | compare_x (const decision_vector &, const decision_vector &) const |
Compare decision vectors. More... | |
bool | verify_x (const decision_vector &) const |
Verify compatibility of decision vector x with problem. More... | |
bool | compare_fc (const fitness_vector &, const constraint_vector &, const fitness_vector &, const constraint_vector &) const |
Simultaneous fitness-constraint comparison. More... | |
virtual void | pre_evolution (population &) const |
Pre-evolution hook. More... | |
virtual void | post_evolution (population &) const |
Post-evolution hook. More... | |
virtual void | set_sparsity (int &lenG, std::vector< int > &iGfun, std::vector< int > &jGvar) const |
Sets the sparsity pattern of the gradient. More... | |
const decision_vector & | get_lb () const |
Lower bounds getter. More... | |
const decision_vector & | get_ub () const |
Upper bounds getter. More... | |
void | set_bounds (const decision_vector &, const decision_vector &) |
Bounds setter from pagmo::decision_vector. More... | |
template<class Iterator1 , class Iterator2 > | |
void | set_bounds (Iterator1 start1, Iterator1 end1, Iterator2 start2, Iterator2 end2) |
Bounds setter from iterators. More... | |
template<std::size_t N> | |
void | set_bounds (const double(&v1)[N], const double(&v2)[N]) |
Bounds setter from raw arrays. More... | |
void | set_bounds (const double &, const double &) |
Set bounds to specified values. More... | |
void | set_bounds (int, const double &, const double &) |
Set bounds to specified values. More... | |
void | set_lb (const decision_vector &) |
Set lower bounds from pagmo::decision_vector. More... | |
void | set_lb (int, const double &) |
Set specific lower bound to value. More... | |
void | set_lb (const double &) |
Set all lower bounds to value. More... | |
template<class Iterator > | |
void | set_lb (Iterator start, Iterator end) |
Lower bounds setter from iterators. More... | |
template<std::size_t N> | |
void | set_lb (const double(&v)[N]) |
Lower bounds setter from raw array. More... | |
void | set_ub (const decision_vector &) |
Set upper bounds from pagmo::decision_vector. More... | |
void | set_ub (int, const double &) |
Set specific upper bound to value. More... | |
void | set_ub (const double &) |
Set all upper bounds to value. More... | |
template<class Iterator > | |
void | set_ub (Iterator start, Iterator end) |
Upper bounds setter from iterators. More... | |
template<std::size_t N> | |
void | set_ub (const double(&v)[N]) |
Upper bounds setter from raw array. More... | |
unsigned int | get_fevals () const |
Return number of function evaluations. More... | |
unsigned int | get_cevals () const |
Return number of constraints function evaluations. More... | |
size_type | get_dimension () const |
Return global dimension. More... | |
size_type | get_i_dimension () const |
Return integer dimension. More... | |
f_size_type | get_f_dimension () const |
Return fitness dimension. More... | |
c_size_type | get_c_dimension () const |
Return global constraints dimension. More... | |
c_size_type | get_ic_dimension () const |
Return inequality constraints dimension. More... | |
const std::vector< double > & | get_c_tol () const |
Return constraints tolerance. More... | |
double | get_diameter () const |
Get the diameter of the problem. More... | |
constraint_vector | compute_constraints (const decision_vector &) const |
Compute constraints and return constraint vector. More... | |
void | compute_constraints (constraint_vector &, const decision_vector &) const |
Compute constraints and write them into contraint vector. More... | |
bool | compare_constraints (const constraint_vector &, const constraint_vector &) const |
Compare constraint vectors. More... | |
bool | test_constraint (const constraint_vector &, const c_size_type &) const |
Test i-th constraint of c (using tolerance information). More... | |
bool | feasibility_x (const decision_vector &) const |
Test feasibility of decision vector. More... | |
bool | feasibility_c (const constraint_vector &) const |
Test feasibility of constraint vector. More... | |
fitness_vector | objfun (const decision_vector &) const |
Return fitness of pagmo::decision_vector. More... | |
void | objfun (fitness_vector &, const decision_vector &) const |
Write fitness of pagmo::decision_vector into pagmo::fitness_vector. More... | |
bool | compare_fitness (const fitness_vector &, const fitness_vector &) const |
Compare fitness vectors. More... | |
void | reset_caches () const |
Reset internal caches. More... | |
const std::vector< constraint_vector > & | get_best_c (void) const |
Get the best known constraint vector. More... | |
const std::vector< decision_vector > & | get_best_x (void) const |
Get the best known decision vector. More... | |
const std::vector< fitness_vector > & | get_best_f (void) const |
Get the best known fitness vector. More... | |
void | set_best_x (const std::vector< decision_vector > &) |
Sets the best known decision vectors. More... | |
Friends | |
class | boost::serialization::access |
Additional Inherited Members | |
Public Types inherited from pagmo::problem::base_tsp | |
enum | encoding_type { RANDOMKEYS = 0, FULL = 1, CITIES = 2 } |
Mechanism used to encode the sequence of vertices to be visited. More... | |
Public Types inherited from pagmo::problem::base | |
typedef decision_vector::size_type | size_type |
Problem's size type: the same as pagmo::decision_vector's size type. | |
typedef fitness_vector::size_type | f_size_type |
Fitness' size type: the same as pagmo::fitness_vector's size type. | |
typedef constraint_vector::size_type | c_size_type |
Constraints' size type: the same as pagmo::constraint_vector's size type. | |
Static Public Attributes inherited from pagmo::problem::base | |
static const std::size_t | cache_capacity = 5 |
Capacity of the internal caches. | |
Protected Member Functions inherited from pagmo::problem::base | |
virtual bool | equality_operator_extra (const base &) const |
Extra requirements for equality. More... | |
virtual bool | compare_fc_impl (const fitness_vector &, const constraint_vector &, const fitness_vector &, const constraint_vector &) const |
Implementation of simultaneous fitness-constraint comparison. More... | |
void | estimate_sparsity (const decision_vector &, int &lenG, std::vector< int > &iGfun, std::vector< int > &jGvar) const |
Heuristics to estimate the sparsity pattern of the problem. More... | |
void | estimate_sparsity (int &lenG, std::vector< int > &iGfun, std::vector< int > &jGvar) const |
Heuristics to estimate the sparsity pattern of the problem. More... | |
virtual bool | compare_constraints_impl (const constraint_vector &, const constraint_vector &) const |
Implementation of constraint vector comparison. More... | |
virtual bool | compare_fitness_impl (const fitness_vector &, const fitness_vector &) const |
Implementation of fitness vectors comparison. More... | |
The City-Selection Travelling Salesman Problem.
This is a class representing a new variant of the TSP which was firstly introduced (by us) in the context of asteroid/space debris selection problems.
Given a fully connected graph (V,E), where E is a list of weighted edges and V a list of valued vertices, the problem is that of finding a path of length accumulating the largest possible vertex value. We encode a solution to this problem as an Hamiltonian path and evaluate its merit finding, along it, the best sequence satisfying the constraint. Denoting its cumulated vertex value with we also compute, the length of the whole Hamiltonian path, .
The problem will then be that of finding the Hamiltonian path maximizing and having the largest .
NOTE: if is larger than than the shortest Hamiltonian path (i.e. the solution to the static TSP), the solution to this problem is the solution to the static TSP. If is, instead, smaller than the minimum weight across edges, the solution to this problem is trivial and its global minimum is exactly (corrsponding to .
pagmo::problem::tsp_cs::tsp_cs | ( | ) |
Constructors.
Default constructor.
This constructs a 3-cities symmetric problem (naive TSP_CS) with weight matrix [[0,1,1], [1,0,1], [1,1,0]], value vector [1,1,1] maximum path length of 1 and RANDOMKEYS encoding
Definition at line 36 of file tsp_cs.cpp.
pagmo::problem::tsp_cs::tsp_cs | ( | const std::vector< std::vector< double > > & | weights, |
const std::vector< double > & | values, | ||
const double | max_path_length, | ||
const base_tsp::encoding_type & | encoding = CITIES |
||
) |
Constructor.
Constructs a City-Selction TSP from the weights/values definition, a maximum path length and the chosen encoding
[in] | weights | an std::vector of std::vector representing the edges weights |
[in] | values | an std::vector representing the vertices values |
[in] | max_path_length | the maximum path length allowed (for the travelling salesman) |
[in] | encoding | a pagmo::problem::tsp::encoding representing the chosen encoding |
Definition at line 61 of file tsp_cs.cpp.
|
virtual |
Copy constructor for polymorphic objects.
Clone method.
Implements pagmo::problem::base.
Definition at line 85 of file tsp_cs.cpp.
void pagmo::problem::tsp_cs::find_subsequence | ( | const decision_vector & | tour, |
double & | retval_p, | ||
double & | retval_l, | ||
decision_vector::size_type & | retval_it_l, | ||
decision_vector::size_type & | retval_it_r | ||
) | const |
Computes the best subpath of an hamilonian path satisfying the max_path_length constraint.
Computes the best subpath of an hamilonian path satisfying the max_path_length constraint. If the input tour does not represent an Hamiltonian path, (i.e. its an unfeasible chromosome) the algorithm behaviour is undefined
[in] | tour | the hamiltonian path encoded with a CITIES encoding (i.e. the list of cities ids) |
[out] | retval_p | the total cumulative value of the subpath |
[out] | retval_l | the total saved cumulative length of the subpath |
[out] | retval_it_l | the id of the city where the subpath starts |
[out] | retval_it_r | the id of the city where the subpath ends |
value_error | if the input tour length is not equal to the city number |
Definition at line 199 of file tsp_cs.cpp.
double pagmo::problem::tsp_cs::get_max_path_length | ( | ) | const |
const std::vector< double > & pagmo::problem::tsp_cs::get_values | ( | ) | const |
const std::vector< std::vector< double > > & pagmo::problem::tsp_cs::get_weights | ( | ) | const |
Getter for m_weights.
Definition at line 372 of file tsp_cs.cpp.
|
virtual |
Extra human readable info for the problem.
Reimplemented from pagmo::problem::base.
Definition at line 405 of file tsp_cs.cpp.