inout.c

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

      INPUT:          none
      OUTPUT:         none
      COMMENTS:       not used in the default implementation but may be useful anyway
*/
{

    long int i;
    
    for ( i = 0 ; i < n ; i++ ) {
	fprintf(stat_report," %ld %f %f\n",(*best_so_far_ant).tour[i],instance.nodeptr[(*best_so_far_ant).tour[i]].x, instance.nodeptr[(*best_so_far_ant).tour[i]].y);
    }
    printf("\n"); 
}



void exit_try( long int ntry ) 
/*    
      FUNCTION:       save some statistical information on a trial once it finishes
      INPUT:          trial number
      OUTPUT:         none
      COMMENTS:       
*/
{
  checkTour( (*best_so_far_ant).tour );
/*    printTourFile( (*best_so_far_ant).tour ); */

  printf("\n Best Solution in try %ld is %ld\n",ntry, (*best_so_far_ant).tour_length);
  fprintf(report,"Best: %ld\t Iterations: %6ld\t B-Fac %.5f\t Time %.2f\t Tot.time %.2f\n", (*best_so_far_ant).tour_length, found_best, found_branching, time_used, elapsed_time( VIRTUAL ));
  printf(" Best Solution was found after %ld iterations\n", found_best);

  best_in_try[ntry] = (*best_so_far_ant).tour_length;
  best_found_at[ntry] = found_best;
  time_best_found[ntry] = time_used;
  time_total_run[ntry] = elapsed_time( VIRTUAL );
  printf("\ntry %ld, Best %ld, found at iteration %ld, found at time %f\n",ntry, best_in_try[ntry], best_found_at[ntry], time_best_found[ntry]);

  fprintf(comp_report,"end try %ld\n\n",ntry);
  fprintf(stat_report,"end try %ld\n\n",ntry);
  TRACE (output_solution();)
  fflush(report); 
  fflush(comp_report); 
  fflush(stat_report); 

}



void exit_program( void ) 
/*    
      FUNCTION:       save some final statistical information on a trial once it finishes
      INPUT:          none
      OUTPUT:         none
      COMMENTS:       
*/
{
  long int best_tour_length, worst_tour_length;
  double   t_avgbest, t_stdbest, t_avgtotal, t_stdtotal;
  double   avg_sol_quality = 0., avg_cyc_to_bst = 0., stddev_best, stddev_iterations;

  best_tour_length = best_of_vector( best_in_try ,max_tries );
  worst_tour_length = worst_of_vector( best_in_try , max_tries );

  avg_cyc_to_bst = mean( best_found_at , max_tries );
  stddev_iterations = std_deviation( best_found_at, max_tries, avg_cyc_to_bst );

  avg_sol_quality = mean( best_in_try , max_tries );
  stddev_best = std_deviation( best_in_try, max_tries, avg_sol_quality);

  t_avgbest = meanr( time_best_found, max_tries );
  printf(" t_avgbest = %f\n", t_avgbest );
  t_stdbest = std_deviationr( time_best_found, max_tries, t_avgbest);

  t_avgtotal = meanr( time_total_run, max_tries );
  printf(" t_avgtotal = %f\n", t_avgtotal );
  t_stdtotal = std_deviationr( time_total_run, max_tries, t_avgtotal);

  fprintf(report,"\nAverage-Best: %.2f\t Average-Iterations: %.2f", avg_sol_quality, avg_cyc_to_bst);
  fprintf(report,"\nStddev-Best: %.2f \t Stddev Iterations: %.2f", stddev_best, stddev_iterations);
  fprintf(report,"\nBest try: %ld\t\t Worst try: %ld\n", best_tour_length, worst_tour_length);
  fprintf(report,"\nAvg.time-best: %.2f stddev.time-best: %.2f\n", t_avgbest, t_stdbest);  
  fprintf(report,"\nAvg.time-total: %.2f stddev.time-total: %.2f\n", t_avgtotal, t_stdtotal); 

  if ( optimal > 0 ) {
    fprintf(report," excess best = %f, excess average = %f, excess worst = %f\n",(double)(best_tour_length - optimal) / (double)optimal,(double)(avg_sol_quality - optimal) / (double)optimal,(double)(worst_tour_length - optimal) / (double)optimal);
  }

  fprintf(comp_report,"end problem %s\n",instance.name);
}



void init_program( long int argc, char *argv[] ) 
/*    
      FUNCTION:       initialize the program, 
      INPUT:          program arguments, needed for parsing commandline
      OUTPUT:         none
      COMMENTS:       
*/
{

  char temp_buffer[LINE_BUF_LEN];

  printf(PROG_ID_STR);
  set_default_parameters();
  setbuf(stdout,NULL);
  parse_commandline(argc, argv);

  assert (n_ants < MAX_ANTS-1);
  assert (nn_ants < MAX_NEIGHBOURS);
  assert (nn_ants > 0);
  assert (nn_ls > 0);
  assert (max_tries <= MAXIMUM_NO_TRIES);
  
  best_in_try = calloc(max_tries, sizeof(long int));
  best_found_at = calloc(max_tries, sizeof(long int));
  time_best_found = calloc(max_tries, sizeof(double));
  time_total_run = calloc(max_tries, sizeof(double));
   
  seed = (long int) time( NULL );
  
  TRACE ( printf("read problem data  ..\n\n"); )
  instance.nodeptr = read_etsp(name_buf);
  TRACE ( printf("\n .. done\n\n"); )

  nn_ls = MIN(n-1,nn_ls);
  
  sprintf(temp_buffer,"best.%s",instance.name);
  TRACE ( printf("%s\n",temp_buffer); )
  report = fopen(temp_buffer, "w");
  sprintf(temp_buffer,"cmp.%s",instance.name);
  TRACE ( printf("%s\n",temp_buffer); )
  comp_report = fopen(temp_buffer, "w");
  sprintf(temp_buffer,"stat.%s",instance.name);
  TRACE ( printf("%s\n",temp_buffer); )
  stat_report = fopen(temp_buffer, "w");
   
  printf("calculating distance matrix ..\n\n");
  instance.distance = compute_distances();
  printf(" .. done\n");
  write_params();
  fprintf(comp_report,"begin problem %s\n",name_buf);
  printf("allocate ants' memory ..\n\n");
  allocate_ants();
  printf(" .. done\n");
  DEBUG ( assert ( nn_ls < n && 0 < nn_ls ); )

  printf("\nFinally set ACO algorithm specific parameters, typically done as proposed in literature\n\n");
  /* default setting for elitist_ants is 0; if EAS is applied and
     option elitist_ants is not used, we set the default to
     elitist_ants = n */
  if ( eas_flag && elitist_ants == 0 )
    elitist_ants = n;
}



void printDist(void) 
/*    
      FUNCTION:       print distance matrix 
      INPUT:          none
      OUTPUT:         none
*/
{
  long int i,j;

  printf("Distance Matrix:\n");
  for ( i = 0 ; i < n ; i++) {
    printf("From %ld:  ",i);
    for ( j = 0 ; j < n - 1 ; j++ ) {
      printf(" %ld", instance.distance[i][j]);
    }
    printf(" %ld\n", instance.distance[i][n-1]);
    printf("\n");
  }
  printf("\n");
}



void printHeur(void) 
/*    
      FUNCTION:       print heuristic information 
      INPUT:          none
      OUTPUT:         none
*/
{
  long int i, j;

  printf("Heuristic information:\n");
  for ( i = 0 ; i < n ; i++) {
    printf("From %ld:  ",i);
    for ( j = 0 ; j < n - 1 ; j++ ) {
      printf(" %.3f ", HEURISTIC(i,j));
    }
    printf(" %.3f\n", HEURISTIC(i,j));
    printf("\n");
  }
  printf("\n");
}



void printTrail(void) 
/*    
      FUNCTION:       print pheromone trail values 
      INPUT:          none
      OUTPUT:         none
*/
{
  long int i,j;

  printf("pheromone Trail matrix, iteration: %ld\n\n",iteration);
  for ( i = 0 ; i < n ; i++) {
    printf("From %ld:  ",i);
    for ( j = 0 ; j < n ; j++ ) {
      printf(" %.10f ", pheromone[i][j]);
      if ( pheromone[i][j] > 1.0 )
	printf("XXXXX\n");
    }
    printf("\n");
  }
  printf("\n");
}



void printTotal(void) 
/*    
      FUNCTION:       print values of pheromone times heuristic information 
      INPUT:          none
      OUTPUT:         none
*/
{
  long int i, j;

  printf("combined pheromone and heuristic info\n\n");
  for (i=0; i < n; i++) {
    for (j = 0; j < n - 1 ; j++) {
      printf(" %.15f &", total[i][j]);
      if ( total[i][j] > 1.0 )
	printf("XXXXX\n");
    }
    printf(" %.15f\n", total[i][n-1]);
    if ( total[i][n-1] > 1.0 )
      printf("XXXXX\n");
  }
  printf("\n");
}



void printProbabilities(void) 
/*    
      FUNCTION:       prints the selection probabilities as encountered by an ant 
      INPUT:          none
      OUTPUT:         none
      COMMENTS:       this computation assumes that no choice has been made yet. 
*/
{
  long int i, j;
  double   *p;
  double   sum_prob;

  printf("Selection Probabilities, iteration: %ld\n",iteration);
  p = calloc( n, sizeof(double) );

  for (i=0; i < n; i++) {
    printf("From %ld:  ",i);
    sum_prob = 0.;
    for ( j = 0 ; j < n ; j++) {
      if ( i == j )
	p[j] = 0.;
      else
	p[j] = total[i][j];
      sum_prob += p[j];
    }
    for ( j = 0 ; j < n ; j++) {
      p[j] = p[j] / sum_prob;
    }
    for ( j = 0 ; j < n-1 ; j++) {
      printf(" %.5f ", p[j]);
    }
    printf(" %.5f\n", p[n-1]);
    if (!(j % 26)) {
      printf("\n");
    }
    printf("\n");
  }
  printf("\n");
  free ( p );
}



void printTour( long int *t ) 
/*    
      FUNCTION:       print the tour *t
      INPUT:          pointer to a tour
      OUTPUT:         none
*/
{
    long int   i;

    printf("\n");
    for( i = 0 ; i <= n ; i++ ) {
	if (!i%25)
	    printf("\n");
	printf("%ld ", t[i]);
    }
    printf("\n");
    printf("Tour length = %ld\n\n",compute_tour_length( t ));
}



void printTourFile( long int *t ) 
/*    
      FUNCTION:       print the tour *t to cmp.tsplibfile
      INPUT:          pointer to a tour
      OUTPUT:         none
*/
{
    long int   i;

    fprintf(comp_report,"begin solution\n");
    for( i = 0 ; i < n ; i++ ) {
	fprintf(comp_report,"%ld ", t[i]);
    }
    fprintf(comp_report,"\n");
    fprintf(comp_report,"Tour length %ld\n",compute_tour_length( t ));
    fprintf(comp_report,"end solution\n");
}



void checkTour( long int *t ) 
/*    
      FUNCTION:       make a simple check whether tour *t can be feasible
      INPUT:          pointer to a tour
      OUTPUT:         none
*/
{
    long int   i, sum=0;

    for( i = 0 ; i < n ; i++ ) {
	sum += t[i];
    }
    if ( sum != (n-1) * n / 2 ) {
	fprintf(stderr,"Next tour must be flawed !!\n");
	printTour( t );
	exit(1);
    }
}



void write_params( void ) 
/*    
      FUNCTION:       writes chosen parameter settings in standard output and in 
                      report files 
      INPUT:          none
      OUTPUT:         none
*/
{
  printf("\nParameter-settings: \n\n");
  printf("max-tries %ld\n", max_tries);
  printf("max-tours %ld\n", max_tours);
  printf("optimum %ld\n", optimal);
  printf("time %f\n", max_time);
  printf("num-ants %ld\n", n_ants);
  printf("num-neigh %ld\n", nn_ants);
  printf("alpha %f\n", alpha);
  printf("beta %f\n", beta);
  printf("rho %f\n", rho);
  printf("q_0 %f\n", q_0);
  printf("branch-up %f\n", branch_fac);
  printf("ls_flag %ld\n", ls_flag);
  printf("nn_ls %ld\n", nn_ls);
  printf("dlb_flag %ld\n", dlb_flag);
  printf("as_flag %ld\n", as_flag);
  printf("eas_flag %ld\n", eas_flag);
  printf("ras_flag %ld\n", ras_flag);
  printf("mmas_flag %ld\n", mmas_flag);
  printf("bwas_flag %ld\n", bwas_flag);
  printf("acs_flag %ld\n", acs_flag);
  printf("\n");
  fprintf(report,"\nParameter-settings: \n\n");
  fprintf(report,"max-tries %ld\n", max_tries);
  fprintf(report,"max-tours %ld\n", max_tours);
  fprintf(report,"optimum %ld\n", optimal);
  fprintf(report,"time %f\n", max_time);
  fprintf(report,"num-ants %ld\n", n_ants);
  fprintf(report,"num-neigh %ld\n", nn_ants);
  fprintf(report,"alpha %f\n", alpha);
  fprintf(report,"beta %f\n", beta);
  fprintf(report,"rho %f\n", rho);
  fprintf(report,"q_0 %f\n", q_0);
  fprintf(report,"branch-up %f\n", branch_fac);
  fprintf(report,"ls_flag %ld\n", ls_flag);
  fprintf(report,"nn_ls %ld\n", nn_ls);
  fprintf(report,"dlb_flag %ld\n", dlb_flag);
  fprintf(report,"as_flag %ld\n", as_flag);
  fprintf(report,"eas_flag %ld\n", eas_flag);
  fprintf(report,"ras_flag %ld\n", ras_flag);
  fprintf(report,"mmas_flag %ld\n", mmas_flag);
  fprintf(report,"bwas_flag %ld\n", bwas_flag);
  fprintf(report,"acs_flag %ld\n", acs_flag);
  fprintf(report,"\n");
  fprintf(comp_report,"%s",PROG_ID_STR);
  fprintf(comp_report,"\nParameter-settings: \n\n");
  fprintf(comp_report,"max-tries %ld\n", max_tries);
  fprintf(comp_report,"max-tours %ld\n", max_tours);
  fprintf(comp_report,"optimum %ld\n", optimal);
  fprintf(comp_report,"time %f\n", max_time);
  fprintf(comp_report,"num-ants %ld\n", n_ants);
  fprintf(comp_report,"num-neigh %ld\n", nn_ants);
  fprintf(comp_report,"alpha %f\n", alpha);
  fprintf(comp_report,"beta %f\n", beta);
  fprintf(comp_report,"rho %f\n", rho);
  fprintf(comp_report,"q_0 %f\n", q_0);
  fprintf(comp_report,"branch-up %f\n", branch_fac);
  fprintf(comp_report,"ls_flag %ld\n", ls_flag);
  fprintf(comp_report,"nn_ls %ld\n", nn_ls);
  fprintf(comp_report,"dlb_flag %ld\n", dlb_flag);
  fprintf(comp_report,"as_flag %ld\n", as_flag);
  fprintf(comp_report,"eas_flag %ld\n", eas_flag);
  fprintf(comp_report,"ras_flag %ld\n", ras_flag);
  fprintf(comp_report,"mmas_flag %ld\n", mmas_flag);
  fprintf(comp_report,"bwas_flag %ld\n", bwas_flag);
  fprintf(comp_report,"acs_flag %ld\n", acs_flag);
  fprintf(comp_report,"\n");
}