TSP.cpp File Reference
#include <shark/ObjectiveFunctions/AbstractObjectiveFunction.h>
#include <shark/Algorithms/DirectSearch/FitnessExtractor.h>
#include <shark/Algorithms/DirectSearch/Operators/Selection/RouletteWheelSelection.h>
#include <shark/Algorithms/DirectSearch/Individual.h>
#include <shark/LinAlg/Base.h>
#include <boost/format.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphml.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/metric_tsp_approx.hpp>
#include <boost/property_map/dynamic_property_map.hpp>
#include <boost/range/algorithm_ext/iota.hpp>

Go to the source code of this file.

Namespaces

 shark
 AbstractMultiObjectiveOptimizer.
 

Typedefs

typedef shark::IntVector Tour
 A 10-city traveling salesman problem. More...
 
typedef boost::adjacency_matrix< boost::undirectedS, boost::property< boost::vertex_color_t, std::string >, boost::property< boost::edge_weight_t, double, boost::property< boost::edge_color_t, std::string > >, boost::no_property > shark::Graph
 
typedef boost::graph_traits< Graph >::vertex_descriptor shark::Vertex
 
typedef boost::graph_traits< Graph >::edge_descriptor shark::Edge
 
typedef boost::property_map< Graph, boost::edge_weight_t >::type shark::WeightMap
 
typedef boost::property_map< Graph, boost::edge_color_t >::type shark::ColorMap
 
typedef Individual< Tour, double > shark::IndividualType
 
typedef std::vector< IndividualType > shark::Population
 

Functions

bool shark::compare_fitness (const IndividualType &a, const IndividualType &b)
 
int main (int argc, char **argv)
 

Variables

const double cities [10][10]
 Defines the problem, i.e., its cost matrix. More...
 

Typedef Documentation

§ Tour

typedef shark::IntVector Tour

A 10-city traveling salesman problem.

The implementation follows:

D. E. Goldberg and R. Lingle, Alleles, loci, and traveling salesman problem. In Proc. of the International Conference on Genetic Algorithms and Their Applications, pages 154-159, Pittsburg, PA, 1985

The traveling salsman problem is a combinatorial optimization task. A salesman is supposed to visit $n$ cities. Each travelling connection is associated with a cost (i.e. the time fot the trip). The problem is to find the cheapest round-route that visits each city exactly once and returns to the starting point.

Author
T. Voss
Date
-
Copyright 1995-2015 Shark Development Team



This file is part of Shark. http://image.diku.dk/shark/

Shark is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

Shark is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with Shark. If not, see http://www.gnu.org/licenses/.

Definition at line 66 of file TSP.cpp.

Function Documentation

§ main()

int main ( int  argc,
char **  argv 
)

Variable Documentation

§ cities

const double cities[10][10]
Initial value:
= {
{ 0, 28, 57, 72, 81, 85, 80, 113, 89, 80 },
{ 28, 0, 28, 45, 54, 57, 63, 85, 63, 63 },
{ 57, 28, 0, 20, 30, 28, 57, 57, 40, 57 },
{ 72, 45, 20, 0, 10, 20, 72, 45, 20, 45 },
{ 81, 54, 30, 10, 0, 22, 81, 41, 10, 41 },
{ 85, 57, 28, 20, 22, 0, 63, 28, 28, 63 },
{ 80, 63, 57, 72, 81, 63, 0, 80, 89, 113 },
{ 113, 85, 57, 45, 41, 28, 80, 0, 40, 80 },
{ 89, 63, 40, 20, 10, 28, 89, 40, 0, 40 },
{ 80, 63, 57, 45, 41, 63, 113, 80, 40, 0 }
}

Defines the problem, i.e., its cost matrix.

Definition at line 71 of file TSP.cpp.

Referenced by main().