acotsp.c

蚁群算法的程序

/*

 AAAA    CCCC   OOOO   TTTTTT   SSSSS  PPPPP
 AA  AA  CC     OO  OO    TT    SS      PP  PP
 AAAAAA  CC     OO  OO    TT     SSSS   PPPPP
 AA  AA  CC     OO  OO    TT        SS  PP
 AA  AA   CCCC   OOOO     TT    SSSSS   PP
 
  ######################################################
  ##########    ACO algorithms for the TSP    ##########
  ######################################################
  
   Version: 1.0
   File:    main.c
   Author:  Thomas Stuetzle
   Purpose: main routines and control for the ACO algorithms
   Check:   README and gpl.txt
   Copyright (C) 2002  Thomas Stuetzle
*/

/***************************************************************************

 Program's name: acotsp
 
  Ant Colony Optimization algorithms (AS, ACS, EAS, RAS, MMAS, BWAS) for the 
  symmetric TSP 
  
   Copyright (C) 2004  Thomas Stuetzle
   
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.
	
	 This program 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 General Public License for more details.
	 
	  You should have received a copy of the GNU General Public License
	  along with this program; if not, write to the Free Software
	  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
	  
	   email: stuetzle no@spam informatik.tu-darmstadt.de
	   mail address: Universitaet Darmstadt
	   Fachbereich Informatik
	   Hochschulstr. 10
	   D-64283 Darmstadt
	   Germany
	   
***************************************************************************/


#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#include "ants.h"
#include "utilities.h"
#include "InOut.h"
#include "TSP.h"
#include "timer.h"
#include "ls.h"



long int termination_condition( void )
/*    
FUNCTION:       checks whether termination condition is met 
INPUT:          none
OUTPUT:         0 if condition is not met, number neq 0 otherwise
(SIDE)EFFECTS:  none
*/
{
	return ( ((n_tours >= max_tours) && (elapsed_time( VIRTUAL ) >= max_time)) || 
		((*best_so_far_ant).tour_length <= optimal)); 
}



void construct_solutions( void )
/*    
FUNCTION:       manage the solution construction phase
INPUT:          none
OUTPUT:         none
(SIDE)EFFECTS:  when finished, all ants of the colony have constructed a solution  
*/
{
    long int k;        /* counter variable */
    long int step;    /* counter of the number of construction steps */
	
    TRACE ( printf("construct solutions for all ants\n"); );
	
    /* Mark all cities as unvisited */
    for ( k = 0 ; k < n_ants ; k++) {
		ant_empty_memory( &ant[k] );
    }
    
    step = 0; 
    /* Place the ants on same initial city */
    for ( k = 0 ; k < n_ants ; k++ )
		place_ant( &ant[k], step);
	
    while ( step < n-1 ) {
		step++;
		for ( k = 0 ; k < n_ants ; k++ ) {
			neighbour_choose_and_move_to_next( &ant[k], step);
			if ( acs_flag )
				local_acs_pheromone_update( &ant[k], step );
		}
    }
	
    step = n;
    for ( k = 0 ; k < n_ants ; k++ ) {
		ant[k].tour[n] = ant[k].tour[0];
		ant[k].tour_length = compute_tour_length( ant[k].tour );
		if ( acs_flag )
			local_acs_pheromone_update( &ant[k], step );
    }
    n_tours += n_ants;
}



void init_try( long int ntry ) 
/*    
FUNCTION: initilialize variables appropriately when starting a trial
INPUT:    trial number
OUTPUT:   none
COMMENTS: none
*/
{
	
    TRACE ( printf("INITIALIZE TRIAL\n"); );
	
    start_timers();
    time_used = elapsed_time( VIRTUAL );
    time_passed = time_used;
	
    fprintf(comp_report,"seed %ld\n",seed);
    fflush(comp_report);
    /* Initialize variables concerning statistics etc. */
	
    n_tours      = 1;
    iteration    = 1;
    restart_iteration = 1;
    lambda       = 0.05;            
    (*best_so_far_ant).tour_length = INFTY;
    found_best   = 0;
	
    /* Initialize the Pheromone trails, only if ACS is used, pheromones
	have to be initialized differently */
    if ( !(acs_flag || mmas_flag || bwas_flag) ) {
		trail_0 = 1. / ( (rho) * nn_tour() );
		/* in the original papers on Ant System, Elitist Ant System, and
		Rank-based Ant System it is not exactly defined what the
		initial value of the pheromones is. Here we set it to some
		small constant, analogously as done in MAX-MIN Ant System.  
		*/
		init_pheromone_trails( trail_0 );
    } 
    if ( bwas_flag ) {
		trail_0 = 1. / ( (double) n * (double) nn_tour()) ;
		init_pheromone_trails( trail_0 );
    } 
    if ( mmas_flag ) {
		trail_max = 1. / ( (rho) * nn_tour() );
		trail_min = trail_max / ( 2. * n );
		init_pheromone_trails( trail_max );   
    }
    if ( acs_flag ) {
		trail_0 = 1. / ( (double) n * (double) nn_tour( ) ) ;
		init_pheromone_trails( trail_0 );
    }
	
    /* Calculate combined information pheromone times heuristic information */
    compute_total_information();
    
    fprintf(comp_report,"begin try %li \n",ntry);
    fprintf(stat_report,"begin try %li \n",ntry);
}



void local_search( void )
/*    
FUNCTION:       manage the local search phase; apply local search to ALL ants; in 
dependence of ls_flag one of 2-opt, 2.5-opt, and 3-opt local search
is chosen.
INPUT:          none
OUTPUT:         none
(SIDE)EFFECTS:  all ants of the colony have locally optimal tours
COMMENTS:       typically, best performance is obtained by applying local search 
to all ants. It is known that some improvements (e.g. convergence 
speed towards high quality solutions) may be obtained for some 
ACO algorithms by applying local search to only some of the ants.
Overall best performance is typcially obtained by using 3-opt.
*/
{
    long int k;
	
    TRACE ( printf("apply local search to all ants\n"); );
	
    for ( k = 0 ; k < n_ants ; k++ ) {
		if ( ls_flag == 1 )
			two_opt_first( ant[k].tour );    /* 2-opt local search */
		else if ( ls_flag == 2 )
			two_h_opt_first( ant[k].tour );  /* 2.5-opt local search */
		else if ( ls_flag == 3 )
			three_opt_first( ant[k].tour );  /* 3-opt local search */
		else {
			fprintf(stderr,"type of local search procedure not correctly specified\n");
			exit(1);
		}
		ant[k].tour_length = compute_tour_length( ant[k].tour );
    }
}



void update_statistics( void )
/*    
FUNCTION:       manage some statistical information about the trial, especially
if a new best solution (best-so-far or restart-best) is found and
adjust some parameters if a new best solution is found
INPUT:          none
OUTPUT:         none
(SIDE)EFFECTS:  restart-best and best-so-far ant may be updated; trail_min 
and trail_max used by MMAS may be updated
*/
{
	
    long int iteration_best_ant;
    double p_x; /* only used by MMAS */
	
    iteration_best_ant = find_best(); /* iteration_best_ant is a global variable */
	
    if ( ant[iteration_best_ant].tour_length < (*best_so_far_ant).tour_length ) {
		
		time_used = elapsed_time( VIRTUAL ); /* best sol found after time_used */
		copy_from_to( &ant[iteration_best_ant], best_so_far_ant );
		copy_from_to( &ant[iteration_best_ant], restart_best_ant );
		
		found_best = iteration;
		restart_found_best = iteration;
		found_branching = node_branching(lambda);
		branching_factor = found_branching;
		if ( mmas_flag ) {
			if ( !ls_flag ) {
				p_x = exp(log(0.05)/n); 
				trail_min = 1. * (1. - p_x) / (p_x * (double)((nn_ants + 1) / 2));
				trail_max = 1. / ( (rho) * (*best_so_far_ant).tour_length );
				trail_0 = trail_max;
				trail_min = trail_max * trail_min; 
			} else {
				trail_max = 1. / ( (rho) * (*best_so_far_ant).tour_length );
				trail_min = trail_max / ( 2. * n );
				trail_0 = trail_max;
			}
		}
		write_report();
    }
    if ( ant[iteration_best_ant].tour_length < (*restart_best_ant).tour_length ) {
		copy_from_to( &ant[iteration_best_ant], restart_best_ant );
		restart_found_best = iteration;
		printf("restart best: %ld, restart_found_best %ld, time %.2f\n",(*restart_best_ant).tour_length, restart_found_best, elapsed_time ( VIRTUAL )); 
    }
}



void search_control_and_statistics( void )
/*    
FUNCTION:       occasionally compute some statistics and check whether algorithm 
is converged 
INPUT:          none
OUTPUT:         none
(SIDE)EFFECTS:  restart-best and best-so-far ant may be updated; trail_min 
and trail_max used by MMAS may be updated
*/
{
    TRACE ( printf("SEARCH CONTROL AND STATISTICS\n"); );
	
    if (!(iteration % 100)) {
		population_statistics();
		branching_factor = node_branching(lambda);
		printf("\nbest so far %ld, iteration: %ld, time %.2f, b_fac %.5f\n",(*best_so_far_ant).tour_length,iteration,elapsed_time( VIRTUAL),branching_factor);
		
		if ( mmas_flag && (branching_factor < branch_fac) && (iteration - restart_found_best > 250) ) {
		/* MAX-MIN Ant System was the first ACO algorithm to use
	       pheromone trail re-initialisation as implemented
		   here. Other ACO algorithms may also profit from this mechanism.
			*/
			printf("INIT TRAILS!!!\n"); (*restart_best_ant).tour_length = INFTY; 
			init_pheromone_trails( trail_max );
			compute_total_information();
			restart_iteration = iteration;
			restart_time = elapsed_time( VIRTUAL );
		}
		printf("try %li, iteration %li, b-fac %f \n\n", n_try,iteration,branching_factor);
    }
}