inout.c

是从一个国外的蚁群算法网站上下载的源程序,是用蚁群算法解TSP问题的源程序!感谢开放源程序

/*

       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