ants.c

蚁群算法解决TSP问题的源代码

	}
    }
    if ( next_city == n )
	/* all cities in nearest neighbor list were already visited */
	choose_best_next( a, phase );
    else {
	DEBUG( assert ( 0 <= next_city && next_city < n); )
	DEBUG( assert ( value_best > 0.0 ); )
	DEBUG( assert ( (*a).visited[next_city] == FALSE ); )
	(*a).tour[phase] = next_city;
	(*a).visited[next_city] = TRUE;
    }
}



void choose_closest_next( ant_struct *a, long int phase )
/*    
      FUNCTION:      Chooses for an ant the closest city as the next one 
      INPUT:         pointer to ant and the construction step "phase" 
      OUTPUT:        none 
      (SIDE)EFFECT:  ant moves to the chosen city
*/
{ 
    long int city, current_city, next_city, min_distance;
  
    next_city = n;
    DEBUG( assert ( phase > 0 && phase < n ); );
    current_city = (*a).tour[phase-1];
    min_distance = INFTY;             /* Search shortest edge */    
    for ( city = 0 ; city < n ; city++ ) {
	if ( (*a).visited[city] ) 
	    ; /* city already visited */
	else {
	    if ( instance.distance[current_city][city] < min_distance) {
		next_city = city;
		min_distance = instance.distance[current_city][city];
	    }
	} 
    }
    DEBUG( assert ( 0 <= next_city && next_city < n); );
    (*a).tour[phase] = next_city;
    (*a).visited[next_city] = TRUE;
}



void neighbour_choose_and_move_to_next( ant_struct *a , long int phase )
/*    
      FUNCTION:      Choose for an ant probabilistically a next city among all 
                     unvisited cities in the current city's candidate list. 
		     If this is not possible, choose the closest next
      INPUT:         pointer to ant the construction step "phase" 
      OUTPUT:        none 
      (SIDE)EFFECT:  ant moves to the chosen city
*/
{ 
    long int i, help; 
    long int current_city;
    double   rnd, partial_sum = 0., sum_prob = 0.0;
    /*  double   *prob_of_selection; */ /* stores the selection probabilities 
	of the nearest neighbor cities */
    double   *prob_ptr;



    if ( (q_0 > 0.0) && (ran01( &seed ) < q_0)  ) {
	/* with a probability q_0 make the best possible choice
	   according to pheromone trails and heuristic information */
	/* we first check whether q_0 > 0.0, to avoid the very common case
	   of q_0 = 0.0 to have to compute a random number, which is
	   expensive computationally */
	neighbour_choose_best_next(a, phase);
	return;
    }

    prob_ptr = prob_of_selection;

    current_city = (*a).tour[phase-1]; /* current_city city of ant k */
    DEBUG( assert ( current_city >= 0 && current_city < n ); )
    for ( i = 0 ; i < nn_ants ; i++ ) {
	if ( (*a).visited[instance.nn_list[current_city][i]] ) 
	    prob_ptr[i] = 0.0;   /* city already visited */
	else {
	    DEBUG( assert ( instance.nn_list[current_city][i] >= 0 && instance.nn_list[current_city][i] < n ); )
	    prob_ptr[i] = total[current_city][instance.nn_list[current_city][i]];
	    sum_prob += prob_ptr[i];
	} 
    }

    if (sum_prob <= 0.0) {
	/* All cities from the candidate set are tabu */
	choose_best_next( a, phase );
    }     
    else {  
	/* at least one neighbor is eligible, chose one according to the
	   selection probabilities */
	rnd = ran01( &seed );
	rnd *= sum_prob;
	i = 0;
	partial_sum = prob_ptr[i];
	while ( partial_sum <= rnd ) {
	    i++;
	    partial_sum += prob_ptr[i]; 
	}
	DEBUG( assert ( 0 <= i && i < nn_ants); );
	DEBUG( assert ( prob_ptr[i] >= 0.0); );
	help = instance.nn_list[current_city][i];
	DEBUG( assert ( help >= 0 && help < n ); )
	DEBUG( assert ( (*a).visited[help] == FALSE ); )
	(*a).tour[phase] = help; /* instance.nn_list[current_city][i]; */
	(*a).visited[help] = TRUE;
    }
}




/****************************************************************
 ****************************************************************
Procedures specific to MAX-MIN Ant System
 ****************************************************************
****************************************************************/



void mmas_evaporation_nn_list( void )
/*    
      FUNCTION:      simulation of the pheromone trail evaporation for MMAS
      INPUT:         none
      OUTPUT:        none
      (SIDE)EFFECTS: pheromones are reduced by factor rho
      REMARKS:       if local search is used, this evaporation procedure 
                     only considers links between a city and those cities
		     of its candidate list
*/
{ 
    long int    i, j, help_city;

    TRACE ( printf("mmas specific evaporation on nn_lists\n"); );

    for ( i = 0 ; i < n ; i++ ) {
	for ( j = 0 ; j < nn_ants ; j++ ) {
	    help_city = instance.nn_list[i][j];
	    pheromone[i][help_city] = (1 - rho) * pheromone[i][help_city];
	    if ( pheromone[i][help_city] < trail_min )
		pheromone[i][help_city] = trail_min;
	}
    }
}



void check_pheromone_trail_limits( void )
/*    
      FUNCTION:      only for MMAS without local search: 
                     keeps pheromone trails inside trail limits
      INPUT:         none
      OUTPUT:        none
      (SIDE)EFFECTS: pheromones are forced to interval [trail_min,trail_max]
*/
{ 
    long int    i, j;

    TRACE ( printf("mmas specific: check pheromone trail limits\n"); );

    for ( i = 0 ; i < n ; i++ ) {
	for ( j = 0 ; j < i ; j++ ) {
	    if ( pheromone[i][j] < trail_min ) {
		pheromone[i][j] = trail_min;
		pheromone[j][i] = trail_min;
	    } else if ( pheromone[i][j] > trail_max ) {
		pheromone[i][j] = trail_max;
		pheromone[j][i] = trail_max;
	    }
	}
    }
}



void check_nn_list_pheromone_trail_limits( void )
/*    
      FUNCTION:      only for MMAS with local search: keeps pheromone trails 
                     inside trail limits
      INPUT:         none
      OUTPUT:        none
      (SIDE)EFFECTS: pheromones are forced to interval [trail_min,trail_max]
      COMMENTS:      currently not used since check for trail_min is integrated
                     mmas_evaporation_nn_list and typically check for trail_max 
		     is not done (see FGCS paper or ACO book for explanation 
*/
{ 
    long int    i, j, help_city;

    TRACE ( printf("mmas specific: check pheromone trail limits nn_list\n"); );

    for ( i = 0 ; i < n ; i++ ) {
	for ( j = 0 ; j < nn_ants ; j++ ) {
	    help_city = instance.nn_list[i][j];
	    if ( pheromone[i][help_city] < trail_min )
		pheromone[i][help_city] = trail_min;
	    if ( pheromone[i][help_city] > trail_max )
		pheromone[i][help_city] = trail_max;
	}
    }
}



/****************************************************************
 ****************************************************************
Procedures specific to Ant Colony System
 ****************************************************************
****************************************************************/



void global_acs_pheromone_update( ant_struct *a )
/*    
      FUNCTION:      reinforces the edges used in ant's solution as in ACS
      INPUT:         pointer to ant that updates the pheromone trail 
      OUTPUT:        none
      (SIDE)EFFECTS: pheromones of arcs in ant k's tour are increased
*/
{  
    long int i, j, h;
    double   d_tau;

    TRACE ( printf("acs specific: global pheromone update\n"); );

    d_tau = 1.0 / (double) (*a).tour_length;

    for ( i = 0 ; i < n ; i++ ) {
	j = (*a).tour[i];
	h = (*a).tour[i+1];

	pheromone[j][h] = (1. - rho) * pheromone[j][h] + rho * d_tau;
	pheromone[h][j] = pheromone[j][h];

	total[h][j] = pow(pheromone[h][j], alpha) * pow(HEURISTIC(h,j),beta);
	total[j][h] = total[h][j];
    }
}



void local_acs_pheromone_update( ant_struct *a, long int phase )
/*    
      FUNCTION:      removes some pheromone on edge just passed by the ant
      INPUT:         pointer to ant and number of constr. phase
      OUTPUT:        none
      (SIDE)EFFECTS: pheromones of arcs in ant k's tour are increased
      COMMENTS:      I did not do experiments with with different values of the parameter 
                     xi for the local pheromone update; therefore, here xi is fixed to 0.1 
		     as suggested by Gambardella and Dorigo for the TSP. If you wish to run 
		     experiments with that parameter it may be reasonable to use it as a 
		     commandline parameter
*/
{  
    long int  h, j;
    
    DEBUG ( assert ( phase > 0 && phase <= n ); )
	j = (*a).tour[phase];

    h = (*a).tour[phase-1];
    DEBUG ( assert ( 0 <= j && j < n ); )
	DEBUG ( assert ( 0 <= h && h < n ); )
	/* still additional parameter has to be introduced */
	pheromone[h][j] = (1. - 0.1) * pheromone[h][j] + 0.1 * trail_0;
    pheromone[j][h] = pheromone[h][j];
    total[h][j] = pow(pheromone[h][j], alpha) * pow(HEURISTIC(h,j),beta);
    total[j][h] = total[h][j];
}



/****************************************************************
 ****************************************************************
Procedures specific to Best-Worst Ant System
 ****************************************************************
****************************************************************/



void bwas_worst_ant_update( ant_struct *a1, ant_struct *a2)
/*    
      FUNCTION:      uses additional evaporation on the arcs of iteration worst
                     ant that are not shared with the global best ant
      INPUT:         pointer to the best (a1) and the worst (a2) ant
      OUTPUT:        none
      (SIDE)EFFECTS: pheromones on some arcs undergo additional evaporation
*/
{  
    long int    i, j, h, pos, pred;
    long int    distance;
    long int    *pos2;        /* positions of cities in tour of ant a2 */ 

    TRACE ( printf("bwas specific: best-worst pheromone update\n"); );

    pos2 = malloc(n * sizeof(long int));
    for ( i = 0 ; i < n ; i++ ) {
	pos2[(*a2).tour[i]] = i;
    }
 
    distance = 0;
    for ( i = 0 ; i < n ; i++ ) {
	j = (*a1).tour[i];
	h = (*a1).tour[i+1];
	pos = pos2[j];
	if (pos - 1 < 0)
	    pred = n - 1;
	else 
	    pred = pos - 1;
	if ((*a2).tour[pos+1] == h)
	    ; /* do nothing, edge is common with a1 (best solution found so far) */
	else if ((*a2).tour[pred] == h)
	    ; /* do nothing, edge is common with a1 (best solution found so far) */
	else {   /* edge (j,h) does not occur in ant a2 */       
	    pheromone[j][h] = (1 - rho) * pheromone[j][h];
	    pheromone[h][j] = (1 - rho) * pheromone[h][j];
	}
    }
    free ( pos2 );
}



void bwas_pheromone_mutation( void )
/*    
      FUNCTION: implements the pheromone mutation in Best-Worst Ant System
      INPUT:    none  
      OUTPUT:   none
*/
{
    long int     i, j, k;
    long int     num_mutations;
    double       avg_trail = 0.0, mutation_strength = 0.0, mutation_rate = 0.3;

    TRACE ( printf("bwas specific: pheromone mutation\n"); );

    /* compute average pheromone trail on edges of global best solution */
    for ( i = 0 ; i < n ; i++ ) {
	avg_trail +=  pheromone[(*best_so_far_ant).tour[i]][(*best_so_far_ant).tour[i+1]];
    }
    avg_trail /= (double) n;
  
    /* determine mutation strength of pheromone matrix */ 
    if ( max_time > 0.1 )
	mutation_strength = 4. * avg_trail * (elapsed_time(VIRTUAL) - restart_time) / (max_time - restart_time);
    else if ( max_tours > 100 )
	mutation_strength = 4. * avg_trail * (iteration - restart_iteration) / (max_tours - restart_iteration);
    else
	printf("apparently no termination condition applied!!\n");

    /* finally use fast version of matrix mutation */
    mutation_rate = mutation_rate / n * nn_ants;
    num_mutations = n * mutation_rate / 2;   
    /* / 2 because of adjustment for symmetry of pheromone trails */
 
    if ( restart_iteration < 2 )
	num_mutations = 0; 

    for ( i = 0 ; i < num_mutations ; i++ ) {
	j =   (long int) (ran01( &seed ) * (double) n);
	k =   (long int) (ran01( &seed ) * (double) n);
	if ( ran01( &seed ) < 0.5 ) {
	    pheromone[j][k] += mutation_strength;
	    pheromone[k][j] = pheromone[j][k];
	}
	else {
	    pheromone[j][k] -= mutation_strength;
	    if ( pheromone[j][k] <= 0.0 ) {
		pheromone[j][k] = EPSILON;
	    }
	    pheromone[k][j] = pheromone[j][k]; 
	}
    }
}



/**************************************************************************
 **************************************************************************
Procedures specific to the ant's tour manipulation other than construction
***************************************************************************
 **************************************************************************/



void copy_from_to(ant_struct *a1, ant_struct *a2) 
{
/*    
      FUNCTION:       copy solution from ant a1 into ant a2
      INPUT:          pointers to the two ants a1 and a2 
      OUTPUT:         none
      (SIDE)EFFECTS:  a2 is copy of a1
*/
    int   i;
  
    (*a2).tour_length = (*a1).tour_length;
    for ( i = 0 ; i < n ; i++ ) {
	(*a2).tour[i] = (*a1).tour[i];
    }
    (*a2).tour[n] = (*a2).tour[0];
}



long int nn_tour( void )
/*    
      FUNCTION:       generate some nearest neighbor tour and compute tour length
      INPUT:          none
      OUTPUT:         none
      (SIDE)EFFECTS:  needs ant colony and one statistic ants
*/
{
    long int phase, help;

    ant_empty_memory( &ant[0] );

    phase = 0; /* counter of the construction steps */
    place_ant( &ant[0], phase);

    while ( phase < n-1 ) {
	phase++;
	choose_closest_next( &ant[0],phase);
    }
    phase = n;
    ant[0].tour[n] = ant[0].tour[0];
    if ( ls_flag ) {
	two_opt_first( ant[0].tour );
    }
    n_tours += 1;
/*   copy_from_to( &ant[0], best_so_far_ant ); */
    ant[0].tour_length = compute_tour_length( ant[0].tour );

    help = ant[0].tour_length;
    ant_empty_memory( &ant[0] );
    return help;
}



long int distance_between_ants( ant_struct *a1, ant_struct *a2)
/*    
      FUNCTION: compute the distance between the tours of ant a1 and a2
      INPUT:    pointers to the two ants a1 and a2
      OUTPUT:   distance between ant a1 and a2
*/
{  
    long int    i, j, h, pos, pred;
    long int    distance;
    long int    *pos2;        /* positions of cities in tour of ant a2 */ 

    pos2 = malloc(n * sizeof(long int));
    for ( i = 0 ; i < n ; i++ ) {
	pos2[(*a2).tour[i]] = i;
    }

    distance = 0;
    for ( i = 0 ; i < n ; i++ ) {
	j = (*a1).tour[i];
	h = (*a1).tour[i+1];
	pos = pos2[j];
	if (pos - 1 < 0)
	    pred = n - 1;
	else 
	    pred = pos - 1;
	if ((*a2).tour[pos+1] == h)
	    ; /* do nothing, edge is common with best solution found so far */
	else if ((*a2).tour[pred] == h)
	    ; /* do nothing, edge is common with best solution found so far */
	else {   /* edge (j,h) does not occur in ant a2 */       
	    distance++;
	}
    }
    free ( pos2 );
    return distance;
}