54 #include <boost/format.hpp> 55 #include <boost/graph/adjacency_matrix.hpp> 56 #include <boost/graph/adjacency_list.hpp> 57 #include <boost/graph/graphml.hpp> 58 #include <boost/graph/graphviz.hpp> 59 #include <boost/graph/metric_tsp_approx.hpp> 60 #include <boost/property_map/dynamic_property_map.hpp> 61 #include <boost/range/algorithm_ext/iota.hpp> 63 typedef shark::IntVector
Tour;
69 { 0, 28, 57, 72, 81, 85, 80, 113, 89, 80 },
70 { 28, 0, 28, 45, 54, 57, 63, 85, 63, 63 },
71 { 57, 28, 0, 20, 30, 28, 57, 57, 40, 57 },
72 { 72, 45, 20, 0, 10, 20, 72, 45, 20, 45 },
73 { 81, 54, 30, 10, 0, 22, 81, 41, 10, 41 },
74 { 85, 57, 28, 20, 22, 0, 63, 28, 28, 63 },
75 { 80, 63, 57, 72, 81, 63, 0, 80, 89, 113 },
76 { 113, 85, 57, 45, 41, 28, 80, 0, 40, 80 },
77 { 89, 63, 40, 20, 10, 28, 89, 40, 0, 40 },
78 { 80, 63, 57, 45, 41, 63, 113, 80, 40, 0 }
83 typedef boost::adjacency_matrix< boost::undirectedS,
84 boost::property< boost::vertex_color_t, std::string >,
85 boost::property< boost::edge_weight_t, double,
86 boost::property< boost::edge_color_t, std::string >
90 typedef boost::graph_traits<Graph>::vertex_descriptor
Vertex;
91 typedef boost::graph_traits<Graph>::edge_descriptor
Edge;
92 typedef boost::property_map<Graph, boost::edge_weight_t>::type
WeightMap;
93 typedef boost::property_map<Graph, boost::edge_color_t>::type
ColorMap;
111 TspTourLength(
const shark::RealMatrix & costMatrix = shark::RealMatrix() ) : m_costMatrix( costMatrix )
114 std::string name()
const 115 {
return "TspTourLength"; }
117 std::size_t numberOfVariables()
const 118 {
return m_costMatrix.size1(); }
124 SIZE_CHECK( input.size() == m_costMatrix.size1() );
125 m_evaluationCounter++;
127 for( std::size_t i = 0; i < input.size() - 1; i++ ) {
128 result += m_costMatrix( input( i ), input( i+1 ) );
133 shark::RealMatrix m_costMatrix;
142 struct PartiallyMappedCrossover {
151 template<
typename Indiv
idualType>
152 std::pair<IndividualType, IndividualType> operator()(
153 const IndividualType & parent1,
154 const IndividualType & parent2 )
const 156 std::pair< IndividualType, IndividualType > offspring( parent1, parent2 );
161 std::size_t cuttingPoint1 = shark::Rng::discrete( 0, t1.size() - 1 );
162 std::size_t cuttingPoint2 = shark::Rng::discrete( 0, t2.size() - 1 );
164 while( cuttingPoint1 == cuttingPoint2 )
165 cuttingPoint2 = shark::Rng::discrete( 0, t2.size() - 1 );
167 if( cuttingPoint1 > cuttingPoint2 )
168 std::swap( cuttingPoint1, cuttingPoint2 );
170 Tour r1( t1.size(), -1 ), r2( t2.size(), -1 );
172 for( std::size_t i = cuttingPoint1; i <= cuttingPoint2; i++ ) {
173 offspring.first.searchPoint()( i ) = t2( i );
174 offspring.second.searchPoint()( i ) = t1( i );
176 r1[ t2( i ) ] = t1( i );
177 r2[ t1( i ) ] = t2( i );
180 for( std::size_t i = 0; i < t1.size(); i++) {
181 if ((i >= cuttingPoint1) && (i <= cuttingPoint2))
continue;
183 std::size_t n1 = t1[i] ;
184 std::size_t m1 = r1[n1] ;
186 std::size_t n2 = t2[i] ;
187 std::size_t m2 = r2[n2] ;
197 offspring.first.searchPoint()[i] = n1 ;
198 offspring.second.searchPoint()[i] = n2 ;
207 int main(
int argc,
char ** argv ) {
212 boost::graph_traits<shark::Graph>::vertex_iterator v, v_end;
213 for( boost::tie(v,v_end) = boost::vertices(g); v != v_end; ++v )
214 boost::put(boost::vertex_color_t(), g, *v, ( boost::format(
"City_%1%" ) % *v ).str() );
221 bool inserted =
false;
223 shark::RealMatrix costMatrix( 10, 10 );
224 for( std::size_t i = 0; i < costMatrix.size1(); i++ ) {
225 for( std::size_t j = 0; j < costMatrix.size1(); j++ ) {
227 if( i == j )
continue;
229 costMatrix(i,j) =
cities[i][j];
232 boost::tie( e, inserted ) = boost::add_edge( i, j, g );
235 weightMap[ e ] =
cities[i][j];
237 colorMap[ e ] =
"blue";
245 shark::PartiallyMappedCrossover pmc;
247 shark::TspTourLength ttl( costMatrix );
250 const std::size_t mu = 100;
252 const std::size_t
lambda = 100;
260 Tour t( 10 ); boost::iota( t, 0 );
263 for( std::size_t i = 0; i < parents.size(); i++ ) {
264 parents[i].searchPoint() = t;
266 std::random_shuffle( parents[ i ].searchPoint().begin(), parents[ i ].searchPoint().end() );
268 parents[i].penalizedFitness() = parents[i].unpenalizedFitness() = ttl( parents[i].searchPoint() );
272 while( ttl.evaluationCounter() < 10000 ) {
273 shark::RealVector selectionProbabilities(parents.size());
274 for(std::size_t i = 0; i != parents.size(); ++i){
275 selectionProbabilities(i) = parents[i].unpenalizedFitness();
277 selectionProbabilities/=
sum(selectionProbabilities);
279 for( std::size_t i = 0; i < offspring.size() - 1; i+=2 ) {
284 shark::IndividualType
286 *rws( parents.begin(), parents.end(), selectionProbabilities ),
287 *rws( parents.begin(), parents.end(), selectionProbabilities )
289 offspring[ i ] = result.first;
290 offspring[ i + 1 ] = result.second;
293 offspring[ i ].penalizedFitness() =
294 offspring[ i ].unpenalizedFitness() = ttl( offspring[ i ].searchPoint() );
296 offspring[ i+1 ].penalizedFitness() =
297 offspring[ i+1 ].unpenalizedFitness() = ttl( offspring[ i+1 ].searchPoint() );
308 Tour final = parents.front().searchPoint();
311 bool extracted =
false;
312 for( std::size_t i = 0; i <
final.size() - 1; i++ ) {
316 colorMap[ e ] =
"green";
321 std::vector< shark::Vertex > approxTour;
322 boost::metric_tsp_approx( g, boost::make_tsp_tour_len_visitor( g, std::back_inserter( approxTour ) , len, weightMap ) );
324 for( std::size_t i = 0; i < approxTour.size() - 1; i++ ) {
325 boost::tie( e, extracted ) = boost::edge( approxTour[ i ], approxTour[ i+1 ], g );
328 colorMap[ e ] =
"red";
332 std::ofstream outGraphviz(
"graph.dot" );
333 boost::dynamic_properties dp;
334 dp.property(
"node_id",
boost::get( boost::vertex_color, g ) );
335 dp.property(
"weight",
boost::get( boost::edge_weight, g ) );
336 dp.property(
"label",
boost::get( boost::edge_weight, g ) );
337 dp.property(
"color",
boost::get( boost::edge_color, g ) );
338 boost::write_graphviz_dp( outGraphviz, g, dp );
341 std::cout << parents.front().searchPoint() <<
" -> " << parents.front().unpenalizedFitness() << std::endl;
343 std::cout <<
"Approx: " << len <<
" vs. GA: " << parents.front().unpenalizedFitness() << std::endl;
345 return( EXIT_SUCCESS );