PaGMO  1.1.5
Public Member Functions | Friends
pagmo::problem::tsp_cs Class Reference

The City-Selection Travelling Salesman Problem. More...

#include <tsp_cs.h>

Inheritance diagram for pagmo::problem::tsp_cs:
Inheritance graph
[legend]

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_vectorget_lb () const
 Lower bounds getter. More...
 
const decision_vectorget_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...
 

Detailed Description

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 $ l<l^* $ 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 $ l<l^* $ constraint. Denoting its cumulated vertex value with $ P $ we also compute, the length of the whole Hamiltonian path, $ L $.

The problem will then be that of finding the Hamiltonian path maximizing $ P $ and having the largest $ L $.

NOTE: if $ l^* $ 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 $ l^* $ is, instead, smaller than the minimum weight across edges, the solution to this problem is trivial and its global minimum is exactly $ \max V $ (corrsponding to $ P=\max V $.

Author
Dario Izzo (dario.nosp@m..izz.nosp@m.o@gma.nosp@m.il.c.nosp@m.om)

Definition at line 57 of file tsp_cs.h.

Constructor & Destructor Documentation

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

Parameters
[in]weightsan std::vector of std::vector representing the edges weights
[in]valuesan std::vector representing the vertices values
[in]max_path_lengththe maximum path length allowed (for the travelling salesman)
[in]encodinga pagmo::problem::tsp::encoding representing the chosen encoding

Definition at line 61 of file tsp_cs.cpp.

Member Function Documentation

base_ptr pagmo::problem::tsp_cs::clone ( ) const
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

Parameters
[in]tourthe hamiltonian path encoded with a CITIES encoding (i.e. the list of cities ids)
[out]retval_pthe total cumulative value of the subpath
[out]retval_lthe total saved cumulative length of the subpath
[out]retval_it_lthe id of the city where the subpath starts
[out]retval_it_rthe id of the city where the subpath ends
Exceptions
value_errorif 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

Getter for m_max_path_value.

Returns
m_max_path_value

Definition at line 390 of file tsp_cs.cpp.

const std::vector< double > & pagmo::problem::tsp_cs::get_values ( ) const

Getter for m_values.

Returns
const reference to m_values

Definition at line 381 of file tsp_cs.cpp.

const std::vector< std::vector< double > > & pagmo::problem::tsp_cs::get_weights ( ) const

Getter for m_weights.

Returns
const reference to m_weights

Definition at line 372 of file tsp_cs.cpp.

std::string pagmo::problem::tsp_cs::human_readable_extra ( ) const
virtual

Extra human readable info for the problem.

Returns
a std::string containing a list of vertices and edges

Reimplemented from pagmo::problem::base.

Definition at line 405 of file tsp_cs.cpp.


The documentation for this class was generated from the following files: