54 #include <boost/format.hpp> 55 #if BOOST_VERSION == 106000 56 #include <boost/type_traits/ice.hpp> 58 #include <boost/graph/adjacency_matrix.hpp> 59 #include <boost/graph/adjacency_list.hpp> 60 #include <boost/graph/graphml.hpp> 61 #include <boost/graph/graphviz.hpp> 62 #include <boost/graph/metric_tsp_approx.hpp> 63 #include <boost/property_map/dynamic_property_map.hpp> 64 #include <boost/range/algorithm_ext/iota.hpp> 66 typedef shark::IntVector
Tour;
72 { 0, 28, 57, 72, 81, 85, 80, 113, 89, 80 },
73 { 28, 0, 28, 45, 54, 57, 63, 85, 63, 63 },
74 { 57, 28, 0, 20, 30, 28, 57, 57, 40, 57 },
75 { 72, 45, 20, 0, 10, 20, 72, 45, 20, 45 },
76 { 81, 54, 30, 10, 0, 22, 81, 41, 10, 41 },
77 { 85, 57, 28, 20, 22, 0, 63, 28, 28, 63 },
78 { 80, 63, 57, 72, 81, 63, 0, 80, 89, 113 },
79 { 113, 85, 57, 45, 41, 28, 80, 0, 40, 80 },
80 { 89, 63, 40, 20, 10, 28, 89, 40, 0, 40 },
81 { 80, 63, 57, 45, 41, 63, 113, 80, 40, 0 }
86 typedef boost::adjacency_matrix< boost::undirectedS,
87 boost::property< boost::vertex_color_t, std::string >,
88 boost::property< boost::edge_weight_t, double,
89 boost::property< boost::edge_color_t, std::string >
93 typedef boost::graph_traits<Graph>::vertex_descriptor
Vertex;
94 typedef boost::graph_traits<Graph>::edge_descriptor
Edge;
95 typedef boost::property_map<Graph, boost::edge_weight_t>::type
WeightMap;
96 typedef boost::property_map<Graph, boost::edge_color_t>::type
ColorMap;
114 TspTourLength(
const shark::RealMatrix & costMatrix = shark::RealMatrix() ) : m_costMatrix( costMatrix )
117 std::string name()
const 118 {
return "TspTourLength"; }
120 std::size_t numberOfVariables()
const 121 {
return m_costMatrix.size1(); }
127 SIZE_CHECK( input.size() == m_costMatrix.size1() );
128 m_evaluationCounter++;
130 for( std::size_t i = 0; i < input.size() - 1; i++ ) {
131 result += m_costMatrix( input( i ), input( i+1 ) );
136 shark::RealMatrix m_costMatrix;
145 struct PartiallyMappedCrossover {
154 template<
typename Indiv
idualType>
155 std::pair<IndividualType, IndividualType> operator()(
156 const IndividualType & parent1,
157 const IndividualType & parent2 )
const 159 std::pair< IndividualType, IndividualType > offspring( parent1, parent2 );
167 while( cuttingPoint1 == cuttingPoint2 )
170 if( cuttingPoint1 > cuttingPoint2 )
171 std::swap( cuttingPoint1, cuttingPoint2 );
173 Tour r1( t1.size(), -1 ), r2( t2.size(), -1 );
175 for( std::size_t i = cuttingPoint1; i <= cuttingPoint2; i++ ) {
176 offspring.first.searchPoint()( i ) = t2( i );
177 offspring.second.searchPoint()( i ) = t1( i );
179 r1[ t2( i ) ] = t1( i );
180 r2[ t1( i ) ] = t2( i );
183 for( std::size_t i = 0; i < t1.size(); i++) {
184 if ((i >= cuttingPoint1) && (i <= cuttingPoint2))
continue;
186 std::size_t n1 = t1[i] ;
187 std::size_t m1 = r1[n1] ;
189 std::size_t n2 = t2[i] ;
190 std::size_t m2 = r2[n2] ;
200 offspring.first.searchPoint()[i] = n1 ;
201 offspring.second.searchPoint()[i] = n2 ;
210 int main(
int argc,
char ** argv ) {
215 boost::graph_traits<shark::Graph>::vertex_iterator v, v_end;
216 for( boost::tie(v,v_end) = boost::vertices(g); v != v_end; ++v )
217 boost::put(boost::vertex_color_t(), g, *v, ( boost::format(
"City_%1%" ) % *v ).str() );
224 bool inserted =
false;
226 shark::RealMatrix costMatrix( 10, 10 );
227 for( std::size_t i = 0; i < costMatrix.size1(); i++ ) {
228 for( std::size_t j = 0; j < costMatrix.size1(); j++ ) {
230 if( i == j )
continue;
232 costMatrix(i,j) =
cities[i][j];
235 boost::tie( e, inserted ) = boost::add_edge( i, j, g );
238 weightMap[ e ] =
cities[i][j];
240 colorMap[ e ] =
"blue";
248 shark::PartiallyMappedCrossover pmc;
250 shark::TspTourLength ttl( costMatrix );
253 const std::size_t mu = 100;
255 const std::size_t
lambda = 100;
263 Tour t( 10 ); boost::iota( t, 0 );
266 for( std::size_t i = 0; i < parents.size(); i++ ) {
267 parents[i].searchPoint() = t;
269 std::random_shuffle( parents[ i ].searchPoint().begin(), parents[ i ].searchPoint().end() );
271 parents[i].penalizedFitness() = parents[i].unpenalizedFitness() = ttl( parents[i].searchPoint() );
275 while( ttl.evaluationCounter() < 10000 ) {
276 shark::RealVector selectionProbabilities(parents.size());
277 for(std::size_t i = 0; i != parents.size(); ++i){
278 selectionProbabilities(i) = parents[i].unpenalizedFitness();
280 selectionProbabilities/=
sum(selectionProbabilities);
282 for( std::size_t i = 0; i < offspring.size() - 1; i+=2 ) {
287 shark::IndividualType
289 *rws( shark::Rng::globalRng, parents.begin(), parents.end(), selectionProbabilities ),
290 *rws( shark::Rng::globalRng, parents.begin(), parents.end(), selectionProbabilities )
292 offspring[ i ] = result.first;
293 offspring[ i + 1 ] = result.second;
296 offspring[ i ].penalizedFitness() =
297 offspring[ i ].unpenalizedFitness() = ttl( offspring[ i ].searchPoint() );
299 offspring[ i+1 ].penalizedFitness() =
300 offspring[ i+1 ].unpenalizedFitness() = ttl( offspring[ i+1 ].searchPoint() );
311 Tour final = parents.front().searchPoint();
314 bool extracted =
false;
315 for( std::size_t i = 0; i <
final.size() - 1; i++ ) {
319 colorMap[ e ] =
"green";
324 std::vector< shark::Vertex > approxTour;
325 boost::metric_tsp_approx( g, boost::make_tsp_tour_len_visitor( g, std::back_inserter( approxTour ) , len, weightMap ) );
327 for( std::size_t i = 0; i < approxTour.size() - 1; i++ ) {
328 boost::tie( e, extracted ) = boost::edge( approxTour[ i ], approxTour[ i+1 ], g );
331 colorMap[ e ] =
"red";
335 std::ofstream outGraphviz(
"graph.dot" );
336 boost::dynamic_properties dp;
337 dp.property(
"node_id",
boost::get( boost::vertex_color, g ) );
338 dp.property(
"weight",
boost::get( boost::edge_weight, g ) );
339 dp.property(
"label",
boost::get( boost::edge_weight, g ) );
340 dp.property(
"color",
boost::get( boost::edge_color, g ) );
341 boost::write_graphviz_dp( outGraphviz, g, dp );
344 std::cout << parents.front().searchPoint() <<
" -> " << parents.front().unpenalizedFitness() << std::endl;
346 std::cout <<
"Approx: " << len <<
" vs. GA: " << parents.front().unpenalizedFitness() << std::endl;
348 return( EXIT_SUCCESS );