inout.c

ACO解决TSP问题(蚁群优化)源码!!!

    return ( avg / (double) (n * 2)  );
}



void output_solution( void )
/*
      FUNCTION:       output a solution together with node coordinates
      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");
}