/*       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:    InOut.c      Author:  Thomas Stuetzle      Purpose: mainly input / output / statistic routines      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 <stdlib.h>#include <stdio.h>#include <string.h>#include <assert.h>#include <math.h>#include <limits.h>#include <time.h>#include "InOut.h"#include "TSP.h"#include "timer.h"#include "utilities.h"#include "ants.h"#include "ls.h"#include "parse.h"long int *best_in_try;long int *best_found_at;double   *time_best_found;double   *time_total_run;long int n_try;             /* try counter */long int n_tours;           /* counter of number constructed tours */long int iteration;         /* iteration counter */long int restart_iteration; /* remember iteration when restart was done if any */double   restart_time;      /* remember time when restart was done if any */long int max_tries;         /* maximum number of independent tries */long int max_tours;         /* maximum number of tour constructions in one try */double   lambda;            /* Parameter to determine branching factor */double   branch_fac;        /* If branching factor < branch_fac => update trails */double   max_time;          /* maximal allowed run time of a try  */double   time_used;         /* time used until some given event */double   time_passed;       /* time passed until some moment*/long int optimal;           /* optimal solution or bound to find */double   mean_ants;         /* average tour length */double   stddev_ants;       /* stddev of tour lengths */double   branching_factor;  /* average node branching factor when searching */double   found_branching;   /* branching factor when best solution is found */long int found_best;        /* iteration in which best solution is found */long int restart_found_best;/* iteration in which restart-best solution is found *//* ------------------------------------------------------------------------ */FILE *report, *comp_report, *stat_report;char name_buf[LINE_BUF_LEN];int  opt;struct point * read_etsp(const char *tsp_file_name) /*          FUNCTION: parse and read instance file      INPUT:    instance name      OUTPUT:   list of coordinates for all nodes      COMMENTS: Instance files have to be in TSPLIB format, otherwise procedure fails*/{    FILE         *tsp_file;    char         buf[LINE_BUF_LEN];    long int     i, j;    struct point *nodeptr;    tsp_file = fopen(tsp_file_name, "r");    if ( tsp_file == NULL ) {	fprintf(stderr,"No instance file specified, abort\n");	exit(1);    }    assert(tsp_file != NULL);    printf("\nreading tsp-file %s ... \n\n", tsp_file_name);    fscanf(tsp_file,"%s", buf);    while ( strcmp("NODE_COORD_SECTION", buf) != 0 ) {	if ( strcmp("NAME", buf) == 0 ) {	    fscanf(tsp_file, "%s", buf);	    TRACE ( printf("%s ", buf); )	    fscanf(tsp_file, "%s", buf);	    strcpy(instance.name, buf);	    TRACE ( printf("%s \n", instance.name); )	    buf[0]=0;	}	else if ( strcmp("NAME:", buf) == 0 ) {	    fscanf(tsp_file, "%s", buf);	    strcpy(instance.name, buf);	    TRACE ( printf("%s \n", instance.name); )	    buf[0]=0;	}	else if ( strcmp("COMMENT", buf) == 0 ){	    fgets(buf, LINE_BUF_LEN, tsp_file);	    TRACE ( printf("%s", buf); )	    buf[0]=0;	}	else if ( strcmp("COMMENT:", buf) == 0 ){	    fgets(buf, LINE_BUF_LEN, tsp_file);	    TRACE ( printf("%s", buf); )	    buf[0]=0;	}	else if ( strcmp("TYPE", buf) == 0 ) {	    fscanf(tsp_file, "%s", buf);	    TRACE ( printf("%s ", buf); )	    fscanf(tsp_file, "%s", buf);	    TRACE ( printf("%s\n", buf); )	    if( strcmp("TSP", buf) != 0 ) {		fprintf(stderr,"\n Not a TSP instance in TSPLIB format !!\n");		exit(1);	    }	    buf[0]=0;	}	else if ( strcmp("TYPE:", buf) == 0 ) {	    fscanf(tsp_file, "%s", buf);	    TRACE ( printf("%s\n", buf); )	    if( strcmp("TSP", buf) != 0 ) {		fprintf(stderr,"\n Not a TSP instance in TSPLIB format !!\n");		exit(1);	    }	    buf[0]=0;	}	else if( strcmp("DIMENSION", buf) == 0 ){	    fscanf(tsp_file, "%s", buf);	    TRACE ( printf("%s ", buf); );	    fscanf(tsp_file, "%ld", &n);	    instance.n = n;	    TRACE ( printf("%ld\n", n); );	    assert ( n > 2 && n < 6000);	    buf[0]=0;	}	else if ( strcmp("DIMENSION:", buf) == 0 ) {	    fscanf(tsp_file, "%ld", &n);	    instance.n = n;	    TRACE ( printf("%ld\n", n); );	    assert ( n > 2 && n < 6000);	    buf[0]=0;	}	else if( strcmp("DISPLAY_DATA_TYPE", buf) == 0 ){	    fgets(buf, LINE_BUF_LEN, tsp_file);	    TRACE ( printf("%s", buf); );	    buf[0]=0;	}	else if ( strcmp("DISPLAY_DATA_TYPE:", buf) == 0 ) {	    fgets(buf, LINE_BUF_LEN, tsp_file);	    TRACE ( printf("%s", buf); );	    buf[0]=0;	}	else if( strcmp("EDGE_WEIGHT_TYPE", buf) == 0 ){	    buf[0]=0;	    fscanf(tsp_file, "%s", buf);	    TRACE ( printf("%s ", buf); );	    buf[0]=0;	    fscanf(tsp_file, "%s", buf);	    TRACE ( printf("%s\n", buf); );	    if ( strcmp("EUC_2D", buf) == 0 ) {		distance = round_distance;	    }	    else if ( strcmp("CEIL_2D", buf) == 0 ) {		distance = ceil_distance;	    }	    else if ( strcmp("GEO", buf) == 0 ) {		distance = geo_distance;	    }	    else if ( strcmp("ATT", buf) == 0 ) {		distance = att_distance;	    }	    else		fprintf(stderr,"EDGE_WEIGHT_TYPE %s not implemented\n",buf);	    strcpy(instance.edge_weight_type, buf);	    buf[0]=0;	}	else if( strcmp("EDGE_WEIGHT_TYPE:", buf) == 0 ){	    /* set pointer to appropriate distance function; has to be one of 	       EUC_2D, CEIL_2D, GEO, or ATT. Everything else fails */	    buf[0]=0;	    fscanf(tsp_file, "%s", buf);	    TRACE ( printf("%s\n", buf); )		printf("%s\n", buf);	    printf("%s\n", buf);	    if ( strcmp("EUC_2D", buf) == 0 ) {		distance = round_distance;	    }	    else if ( strcmp("CEIL_2D", buf) == 0 ) {		distance = ceil_distance;	    }	    else if ( strcmp("GEO", buf) == 0 ) {		distance = geo_distance;	    }	    else if ( strcmp("ATT", buf) == 0 ) {		distance = att_distance;	    }	    else {		fprintf(stderr,"EDGE_WEIGHT_TYPE %s not implemented\n",buf);		exit(1);	    }	    strcpy(instance.edge_weight_type, buf);	    buf[0]=0;	}	buf[0]=0;	fscanf(tsp_file,"%s", buf);    }    if( strcmp("NODE_COORD_SECTION", buf) == 0 ){	TRACE ( printf("found section contaning the node coordinates\n"); )	    }    else{	fprintf(stderr,"\n\nSome error ocurred finding start of coordinates from tsp file !!\n");	exit(1);    }    if( (nodeptr = malloc(sizeof(struct point) * n)) == NULL )	exit(EXIT_FAILURE);    else {	for ( i = 0 ; i < n ; i++ ) {	    fscanf(tsp_file,"%ld %lf %lf", &j, &nodeptr[i].x, &nodeptr[i].y );	}    }    TRACE ( printf("number of cities is %ld\n",n); )    TRACE ( printf("\n... done\n"); )	return (nodeptr);}void write_report( void )/*          FUNCTION: output some info about trial (best-so-far solution quality, time)      INPUT:    none      OUTPUT:   none      COMMENTS: none*/{    printf("best %ld, iteration: %ld, time %.2f\n",(*best_so_far_ant).tour_length,iteration,elapsed_time( VIRTUAL));    fprintf(comp_report,"best %ld\t iteration %ld\t tours %ld\t time %.3f\n",(*best_so_far_ant).tour_length,iteration,n_tours,time_used);}void print_default_parameters() /*          FUNCTION: output default parameter settings      INPUT:    none      OUTPUT:   none      COMMENTS: none*/{    fprintf(stderr,"\nDefault parameter settings are:\n\n");    fprintf(stderr,"max_tries\t\t %ld\n", max_tries);    fprintf(stderr,"max_tours\t\t %ld\n", max_tours);    fprintf(stderr,"max_time\t\t %.2f\n", max_time);    fprintf(stderr,"optimum\t\t\t %ld\n", optimal);    fprintf(stderr,"n_ants\t\t\t %ld\n", n_ants);    fprintf(stderr,"nn_ants\t\t\t %ld\n", nn_ants);    fprintf(stderr,"alpha\t\t\t %.2f\n", alpha);    fprintf(stderr,"beta\t\t\t %.2f\n", beta);    fprintf(stderr,"rho\t\t\t %.2f\n", rho);    fprintf(stderr,"q_0\t\t\t %.2f\n", q_0);    fprintf(stderr,"elitist_ants\t\t 0\n");    fprintf(stderr,"ras_ranks\t\t 6\n");    fprintf(stderr,"ls_flag\t\t\t %ld\n", ls_flag);    fprintf(stderr,"nn_ls\t\t\t %ld\n", nn_ls);    fprintf(stderr,"dlb_flag\t\t %ld\n", dlb_flag);    fprintf(stderr,"as_flag\t\t\t %ld\n", as_flag);    fprintf(stderr,"eas_flag\t\t %ld\n", eas_flag);    fprintf(stderr,"ras_flag\t\t %ld\n", ras_flag);    fprintf(stderr,"mmas_flag\t\t %ld\n", mmas_flag);    fprintf(stderr,"bwas_flag\t\t %ld\n", bwas_flag);    fprintf(stderr,"acs_flag\t\t %ld\n", acs_flag);}void set_default_parameters() /*          FUNCTION: set default parameter settings      INPUT:    none      OUTPUT:   none      COMMENTS: none*/{    ls_flag        = 3;     /* per default run 3-opt*/    dlb_flag       = TRUE;  /* apply don't look bits in local search */    nn_ls          = 20;    /* use fixed radius search in the 20 nearest neighbours */    n_ants         = 25;    /* number of ants */    nn_ants        = 20;    /* number of nearest neighbours in tour construction */    alpha          = 1.0;    beta           = 2.0;    rho            = 0.5;    q_0            = 0.0;    max_tries      = 10;    max_tours      = 100;    max_time       = 10.0;    optimal        = 1;    branch_fac     = 1.00001;    as_flag        = FALSE;    eas_flag       = FALSE;    ras_flag       = FALSE;    mmas_flag      = TRUE;     u_gb           = INFTY;    bwas_flag      = FALSE;     acs_flag       = FALSE;    ras_ranks      = 6;    elitist_ants   = 100;}void population_statistics ( void )/*          FUNCTION:       compute some population statistics like average tour length,                       standard deviations, average distance, branching-factor and 		      output to a file gathering statistics      INPUT:          none      OUTPUT:         none      (SIDE)EFFECTS:  none*/{    long int j, k;    long int *l;    double   pop_mean, pop_stddev, avg_distance = 0.0;        l = calloc(n_ants, sizeof(long int));    for( k = 0 ; k < n_ants ; k++ ) {	l[k] = ant[k].tour_length;    }        pop_mean = mean( l, n_ants);    pop_stddev = std_deviation( l, n_ants, pop_mean );    branching_factor = node_branching(lambda);        for ( k = 0 ; k < n_ants-1 ; k++ ) 	for ( j = k+1 ; j < n_ants ; j++) {	    avg_distance += (double)distance_between_ants( &ant[k], &ant[j]);	}    avg_distance /= ((double)n_ants * (double)(n_ants-1) / 2.);         fprintf(stat_report,"%ld\t%.1f\t%.5f\t%.7f\t%.5f\t%.1f\t%.1f\t%.5f\n",iteration, pop_mean, pop_stddev, pop_stddev / pop_mean, branching_factor,  (branching_factor - 1.) * (double)n, avg_distance, avg_distance / (double)n);}double node_branching(double l) /*          FUNCTION:       compute the average node lambda-branching factor       INPUT:          lambda value       OUTPUT:         average node branching factor       (SIDE)EFFECTS:  none      COMMENTS:       see the ACO book for a definition of the average node                       lambda-branching factor */{  long int  i, m;  double    min, max, cutoff;  double    avg;  double    *num_branches;  num_branches = calloc(n, sizeof(double));  for ( m = 0 ; m < n ; m++ ) {    /* determine max, min to calculate the cutoff value */    min = pheromone[m][instance.nn_list[m][1]];    max = pheromone[m][instance.nn_list[m][1]];    for ( i = 1 ; i < nn_ants ; i++ ) {      if ( pheromone[m][instance.nn_list[m][i]] > max )	max = pheromone[m][instance.nn_list[m][i]];      if ( pheromone[m][instance.nn_list[m][i]] < min )	min = pheromone[m][instance.nn_list[m][i]];    }    cutoff = min + l * (max - min);        for ( i = 0 ; i < nn_ants ; i++ ) {          if ( pheromone[m][instance.nn_list[m][i]] > cutoff )	num_branches[m] += 1.;    }  }  avg = 0.;  for ( m = 0 ; m < n ; m++ ) {    avg += num_branches[m];  }  free ( num_branches );  /* Norm branching factor to minimal value 1 */  return ( avg / (double) (n * 2)  );}void output_solution( void ) /*          FUNCTION:       output a solution together with node coordinates