|
|
发表于 2012-5-5 17:48:39
|
显示全部楼层
本帖最后由 refla 于 2012-5-5 17:50 编辑
我写了一个 MMAS 的程序，供大家一起讨论与学习，限于篇幅，这里只给出程序主架构，完成程序我已经打包上传，供大家下载。- struct _tsp tsp;
- void fuck_tsp()
- {
- implement_mmas_plan();
- output( FLAG_SO_FAR_BEST );
- }
- void implement_mmas_plan() // enterance
- {
- initialize();
- int iteration = 0;
- while( ! dose_meet_termination_condition( iteration ) )
- {
- printf( "interation %d ", iteration );
- construct_solutions( iteration );
- local_search(); // optional
- update_statistics();
- update_pheromone_trails();
- output( FLAG_ITERATION_BEST );
- iteration++;
- }// while( ! dose_meet_termination_condition() )
- }
- void initialize()
- {
- set_default_parameters();
- tsp.random_seed = (long) time( NULL );
- tsp.so_far_best_ant.tour_length = NO_ROUTE;
-
- read_instance();
- compute_primary_info();
- }
- void set_default_parameters()
- {
- tsp.parameter.alpha = 1;
- tsp.parameter.beta = 2;
- tsp.parameter.rou = 0.02;
- tsp.parameter.quantity = 1.0;
- tsp.parameter.tau_min_factor = 0.2;
- tsp.parameter.tau_max = 1.0;
- tsp.parameter.tau_min = tsp.parameter.tau_max * tsp.parameter.tau_min_factor;
- }
- void construct_solutions(int iteration)
- {
- struct _ant *ant = tsp.ant;
- int k;
- for( k = 0; k < tsp.parameter.ants; k++ ) // to empty the memory of ants
- {
- memset( ant[ k ].visited, FLAG_UNVISITED, sizeof(int) * (MAX_CITIES + 1) );
- ant[ k ].visited[ tsp.cities ] = iteration;
- }
- for( k = 0; k < tsp.parameter.ants; k++ ) // to place ants
- {
- int start = pickup_start_city();
- ant[ k ].tour[ 0 ] = start;
- ant[ k ].visited[ start ] = FLAG_VISITED;
- }
- int step = 1; // The start city has been determined.
- while( step < tsp.cities )
- {
- for( k = 0; k < tsp.parameter.ants; k++ )
- tour( k, step );
- step++;
- }
- for( k = 0; k < tsp.parameter.ants; k++ )
- {
- ant[ k ].tour[ tsp.cities ] = ant[ k ].tour[ 0 ];
- compute_tour_length( ant + k );
- }
- }
- int pickup_start_city()
- {
- int result = (int)( Oh_Fortuna() * tsp.cities );
- return result;
- }
- void tour(int k, int step)
- {
- struct _ant *ant = tsp.ant;
- int i = ant[ k ].tour[ step - 1 ];
- double sum_probabilities = 0.0;
- double selection_probability[ MAX_CITIES ];
-
- int j;
- for( j = 0; j < tsp.cities; j++ )
- if( ant[ k ].visited[ j ] )
- selection_probability[ j ] = 0.0;
- else
- {
- selection_probability[ j ] = tsp.choice_info[ i ][ j ];
- sum_probabilities += selection_probability[ j ];
- }
- double roulette_wheel = Oh_Fortuna() * sum_probabilities;
- j = 0;
- double p = selection_probability[j];
- while( p < roulette_wheel )
- {
- j++;
- p += selection_probability[j];
- }
- ant[k].tour[ step ] = j;
- ant[k].visited[j] = FLAG_VISITED;
- }
- void update_statistics()
- {
- double rou = tsp.parameter.rou;
- double quantity = tsp.parameter.quantity;
- double tau_max = tsp.parameter.tau_max;
- double tau_min = tsp.parameter.tau_min;
- double tau_min_factor = tsp.parameter.tau_min_factor;
- struct _ant *ant = tsp.ant;
- struct _ant *iter_ant = &( tsp.iteration_best_ant );
- struct _ant *sofar_ant = &( tsp.so_far_best_ant );
- int k = find_iteration_best();
- memcpy( iter_ant, ant+k, sizeof( struct _ant ) );
- if( iter_ant->tour_length < sofar_ant->tour_length )
- {
- memcpy( sofar_ant, ant+k, sizeof( struct _ant ) );
- tau_max = quantity / ( rou * sofar_ant->tour_length );
- tau_min = tau_max * tau_min_factor;
- }
- }
- void update_pheromone_trails()
- {
- mmas_pheromone_update();
- }
- void mmas_pheromone_update()
- {
- evaporate_pheromone();
- struct _ant *elite_ant = &( tsp.iteration_best_ant );
- if( dose_use_so_far_best_ant() )
- elite_ant = &( tsp.so_far_best_ant );
- deposit_pheromone( elite_ant ); // MMAS allows only one ant to deposit its pheromone.
- limit_pheromone();
- compute_choice_information();
- }
- void output(int which)
- {
- static const struct _ant *ant[2] = { &( tsp.so_far_best_ant ), &( tsp.iteration_best_ant ) };
- static const char *hint[2] =
- {
- "\nAt last, the best tour length is %d.\n",
- "length = %d\n"
- };
- printf( hint[ which ], ant[ which ]->tour_length );
- printf( "route: " );
- int step;
- for( step = 0; step <= tsp.cities; step++ )
- printf( "%d ", ant[ which ]->tour[ step ] );
- printf( "\n" );
- }
|
|
发表于 2012-5-5 18:15:35