acotsp.c

aco for TSP problem source code

/*

       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);
    }
}