|
PaGMO
1.1.5
|
Base TSP (Travelling Salesman Problem). More...
#include <base_tsp.h>
Public Types | |
| 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. | |
Public Member Functions | |
| base_tsp (int n_cities, int nc, int nic, encoding_type=CITIES) | |
| Constructor from dimensins and encoding. More... | |
| virtual double | distance (decision_vector::size_type, decision_vector::size_type) const =0 |
Getters. | |
| encoding_type | get_encoding () const |
| Getter for m_encoding. More... | |
| decision_vector::size_type | get_n_cities () const |
| Getter for m_n_cities. More... | |
Converters between encodings. | |
| 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... | |
| virtual base_ptr | clone () const =0 |
| Clone method. More... | |
| std::string | human_readable () const |
| Return human readable representation of the problem. More... | |
| virtual std::string | human_readable_extra () const |
| Extra information in human readable format. 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... | |
| virtual std::string | get_name () const |
| Get problem's name. 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 | |
| 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 void | compute_constraints_impl (constraint_vector &, const decision_vector &) const |
| Implementation of constraint computation. 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... | |
| virtual void | objfun_impl (fitness_vector &f, const decision_vector &x) const =0 |
| Objective function implementation. More... | |
Base TSP (Travelling Salesman Problem).
All pagmo::problem that are TSP variants must derive from this class Algorithms such as pagmo::algorithm::inverover and pagmo::aco can solve problem deriving from this class as they make use of the base_tsp::distance and the base_tsp::get_encoding methods
The virtual method base_tsp::distance is pure and must be reimplemented by the user in the derived class returning the distance between two cities
The sequence of cities visited can be encoded in one of the following ways:
1-CITIES This encoding represents the ids of the cities visited directly in the chromosome. e.g. [3,1,0,2]
2-RANDOMKEYS This encoding, first introduced in the paper Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA journal on computing, 6(2), 154-160. It essentially represents the tour as a sequence of doubles bounded in [0,1]. The tour is reconstructed by the argsort of the sequence. (e.g. [0.34,0.12,0.76,0.03] -> [3,1,0,2])
3-FULL The full encoding encodes the city tour in a matrix as detailed in http://en.wikipedia.org/wiki/Travelling_salesman_problem#Integer_linear_programming_formulation It is used to create TSP problems that are integer linear programming problems. (e.g. [0,1,0,1,0,0,0,0,1,0,1,0] -> [0,2,3,1])
Definition at line 64 of file base_tsp.h.
Mechanism used to encode the sequence of vertices to be visited.
| Enumerator | |
|---|---|
| RANDOMKEYS |
As a vector of doubles in [0,1]. |
| FULL |
As a matrix with ones and zeros. |
| CITIES |
As a sequence of cities ids. |
Definition at line 68 of file base_tsp.h.
| pagmo::problem::base_tsp::base_tsp | ( | int | n_cities, |
| int | nc, | ||
| int | nic, | ||
| encoding_type | encoding = CITIES |
||
| ) |
Constructor from dimensins and encoding.
| [in] | n_cities | number of cities |
| [in] | nc | total number of constraints |
| [in] | nic | total number of inequality constraints |
| [in] | encoding | encoding_type, i.e. one of base_tsp::CITIES, base_tsp::FULL, base_tsp::RANDOMKEYS |
Definition at line 39 of file base_tsp.cpp.
| pagmo::decision_vector pagmo::problem::base_tsp::cities2full | ( | const pagmo::decision_vector & | x | ) | const |
From CITIES to FULL encoding.
Transforms a chromosome in the CITIES encoding into a chromosome in the FULL encoding. If the starting chromosome is unfeasible also the resulting chromosome in the FULL encoding will be unfeasible.
| [in] | x | a chromosome in the CITIES encoding |
Definition at line 98 of file base_tsp.cpp.
| pagmo::decision_vector pagmo::problem::base_tsp::cities2randomkeys | ( | const pagmo::decision_vector & | cities, |
| const pagmo::decision_vector & | orig_random_keys | ||
| ) | const |
From CITIES to RANDOMKEYS encoding.
Transforms a chromosome in the CITIES encoding into a chromosome in the RANDOMKEYS encoding. If the starting chromosome is unfeasible, the resulting chromosome in the RANDOMKEYS encoding will contain zeros, and yet still be feasible. Its inversion using randomkeys2cities will result in a feasible tour.
| [in] | x | a chromosome in the CITIES encoding |
| [in] | orig_random_keys | a chromosome in the RANDOMKEYS encoding. |
Definition at line 156 of file base_tsp.cpp.
| pagmo::decision_vector pagmo::problem::base_tsp::full2cities | ( | const pagmo::decision_vector & | x | ) | const |
From FULL to CITIES encoding.
Transforms a chromosome in the FULL encoding into a chromosome in the CITIES encoding. If the starting chromosome is unfeasible also the resulting chromosome in the CITIES encoding will be unfeasible.
| [in] | x | a chromosome in the FULL encoding |
Definition at line 74 of file base_tsp.cpp.
| base_tsp::encoding_type pagmo::problem::base_tsp::get_encoding | ( | ) | const |
Getter for m_encoding.
Definition at line 184 of file base_tsp.cpp.
| decision_vector::size_type pagmo::problem::base_tsp::get_n_cities | ( | ) | const |
| pagmo::decision_vector pagmo::problem::base_tsp::randomkeys2cities | ( | const pagmo::decision_vector & | x | ) | const |
From RANDOMKEYS to CITIES encoding.
Transforms a chromosome in the RANDOMKEYS encoding into a chromosome in the CITIES encoding. If the starting chromosome is unfeasible also the resulting chromosome in the CITIES encoding will be unfeasible.
| [in] | x | a chromosome in the RANDOMKEYS encoding |
Definition at line 127 of file base_tsp.cpp.
1.8.9.1
