acotsp.c

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

void as_update( void )
/*
      FUNCTION:       manage global pheromone deposit for Ant System
      INPUT:          none
      OUTPUT:         none
      (SIDE)EFFECTS:  all ants deposit pheromones on matrix "pheromone"
*/
{
    long int   k;

    TRACE ( printf("Ant System pheromone deposit\n"); );

    for ( k = 0 ; k < n_ants ; k++ )
        global_update_pheromone( &ant[k] );
}



void eas_update( void )
/*
      FUNCTION:       manage global pheromone deposit for Elitist Ant System
      INPUT:          none
      OUTPUT:         none
      (SIDE)EFFECTS:  all ants plus elitist ant deposit pheromones on matrix "pheromone"
*/
{
    long int   k;

    TRACE ( printf("Elitist Ant System pheromone deposit\n"); );

    for ( k = 0 ; k < n_ants ; k++ )
        global_update_pheromone( &ant[k] );
    global_update_pheromone_weighted( best_so_far_ant, elitist_ants );
}



void ras_update( void )
/*
      FUNCTION:       manage global pheromone deposit for Rank-based Ant System
      INPUT:          none
      OUTPUT:         none
      (SIDE)EFFECTS:  the ras_ranks-1 best ants plus the best-so-far ant deposit pheromone
                      on matrix "pheromone"
      COMMENTS:       this procedure could be implemented slightly faster, but it is
                      anyway not critical w.r.t. CPU time given that ras_ranks is
		      typically very small.
*/
{
    long int i, k, b, target;
    long int *help_b;

    TRACE ( printf("Rank-based Ant System pheromone deposit\n"); );

    help_b = malloc( n_ants  * sizeof(long int) );
    for ( k = 0 ; k < n_ants ; k++ )
        help_b[k] = ant[k].tour_length;

    for ( i = 0 ; i < ras_ranks-1 ; i++ )
    {
        b = help_b[0];
        target = 0;
        for ( k = 0 ; k < n_ants ; k++ )
        {
            if ( help_b[k] < b )
            {
                b = help_b[k];
                target = k;
            }
        }
        help_b[target] = LONG_MAX;
        global_update_pheromone_weighted( &ant[target], ras_ranks-i-1 );
    }
    global_update_pheromone_weighted( best_so_far_ant, ras_ranks );
    free ( help_b );
}



void mmas_update( void )
/*
      FUNCTION:       manage global pheromone deposit for MAX-MIN Ant System
      INPUT:          none
      OUTPUT:         none
      (SIDE)EFFECTS:  either the iteration-best or the best-so-far ant deposit pheromone
                      on matrix "pheromone"
*/
{
    /* we use default upper pheromone trail limit for MMAS and hence we
       do not have to worry regarding keeping the upper limit */

    long int iteration_best_ant;

    TRACE ( printf("MAX-MIN Ant System pheromone deposit\n"); );

    if ( iteration % u_gb )
    {
        iteration_best_ant = find_best();
        global_update_pheromone( &ant[iteration_best_ant] );
    }
    else
    {
        if ( u_gb == 1 && (restart_found_best - iteration > 50))
            global_update_pheromone( best_so_far_ant );
        else
            global_update_pheromone( restart_best_ant );
    }

    if ( ls_flag )
    {
        /* implement the schedule for u_gb as defined in the
           Future Generation Computer Systems article or in Stuetzle's PhD thesis.
           This schedule is only applied if local search is used.
        */
        if ( ( iteration - restart_iteration ) < 25 )
            u_gb = 25;
        else if ( (iteration - restart_iteration) < 75 )
            u_gb = 5;
        else if ( (iteration - restart_iteration) < 125 )
            u_gb = 3;
        else if ( (iteration - restart_iteration) < 250 )
            u_gb = 2;
        else
            u_gb = 1;
    }
    else
        u_gb = 25;

}



void bwas_update( void )
/*
      FUNCTION:       manage global pheromone deposit for Best-Worst Ant System
      INPUT:          none
      OUTPUT:         none
      (SIDE)EFFECTS:  either the iteration-best or the best-so-far ant deposit pheromone
                      on matrix "pheromone"
*/
{
    long int   iteration_worst_ant, distance_best_worst;

    TRACE ( printf("Best-worst Ant System pheromone deposit\n"); );

    global_update_pheromone( best_so_far_ant );
    iteration_worst_ant = find_worst();
    bwas_worst_ant_update( best_so_far_ant, &ant[iteration_worst_ant] );
    distance_best_worst = distance_between_ants( best_so_far_ant, &ant[iteration_worst_ant]);
    /*    printf("distance_best_worst %ld, tour length worst %ld\n",distance_best_worst,ant[iteration_worst_ant].tour_length); */
    if ( distance_best_worst < (long int) (0.05 * (double) n) )
    {
        (*restart_best_ant).tour_length = INFTY;
        init_pheromone_trails( trail_0 );
        restart_iteration = iteration;
        restart_time = elapsed_time( VIRTUAL );
        printf("init pheromone trails with %.15f, iteration %ld\n",trail_0,iteration);
    }
    else
        bwas_pheromone_mutation();
}



void acs_global_update( void )
/*
      FUNCTION:       manage global pheromone deposit for Ant Colony System
      INPUT:          none
      OUTPUT:         none
      (SIDE)EFFECTS:  the best-so-far ant deposits pheromone on matrix "pheromone"
      COMMENTS:       global pheromone deposit in ACS is done per default using
                      the best-so-far ant; Gambardella & Dorigo examined also iteration-best
		      update (see their IEEE Trans. on Evolutionary Computation article),
		      but did not use it for the published computational results.
*/
{
    TRACE ( printf("Ant colony System global pheromone deposit\n"); );

    global_acs_pheromone_update( best_so_far_ant );
}



void pheromone_trail_update( void )
/*
      FUNCTION:       manage global pheromone trail update for the ACO algorithms
      INPUT:          none
      OUTPUT:         none
      (SIDE)EFFECTS:  pheromone trails are evaporated and pheromones are deposited
                      according to the rules defined by the various ACO algorithms.
*/
{
    /* Simulate the pheromone evaporation of all pheromones; this is not necessary
       for ACS (see also ACO Book) */
    if ( as_flag || eas_flag || ras_flag || bwas_flag || mmas_flag )
    {
        if ( ls_flag )
        {
            if ( mmas_flag )
                mmas_evaporation_nn_list();
            else
                evaporation_nn_list();
            /* evaporate only pheromones on arcs of candidate list to make the
               pheromone evaporation faster for being able to tackle large TSP
               instances. For MMAS additionally check lower pheromone trail limits.
            */
        }
        else
        {
            /* if no local search is used, evaporate all pheromone trails */
            evaporation();
        }
    }

    /* Next, apply the pheromone deposit for the various ACO algorithms */
    if ( as_flag )
        as_update();
    else if ( eas_flag )
        eas_update();
    else if ( ras_flag )
        ras_update();
    else if ( mmas_flag )
        mmas_update();
    else if ( bwas_flag )
        bwas_update();
    else if ( acs_flag )
        acs_global_update();

    /* check pheromone trail limits for MMAS; not necessary if local
       search is used, because in the local search case lower pheromone trail
       limits are checked in procedure mmas_evaporation_nn_list */
    if ( mmas_flag && !ls_flag )
        check_pheromone_trail_limits();

    /* Compute combined information pheromone times heuristic info after
       the pheromone update for all ACO algorithms except ACS; in the ACS case
       this is already done in the pheromone update procedures of ACS */
    if ( as_flag || eas_flag || ras_flag || mmas_flag || bwas_flag )
    {
        if ( ls_flag )
        {
            compute_nn_list_total_information();
        }
        else
        {
            compute_total_information();
        }
    }
}



/* --- main program ------------------------------------------------------ */

int main(int argc, char *argv[])
{
    /*
          FUNCTION:       main control for running the ACO algorithms
          INPUT:          none
          OUTPUT:         none
          (SIDE)EFFECTS:  none
          COMMENTS:       this function controls the run of "max_tries" independent trials

    */

    long int i;

    start_timers();

    init_program(argc, argv);

    seed = (long int) time(NULL);

    instance.nn_list = compute_nn_lists();
    pheromone = generate_double_matrix( n, n );
    total = generate_double_matrix( n, n );

    time_used = elapsed_time( VIRTUAL );
    printf("Initialization took %.10f seconds\n",time_used);

    for ( n_try = 0 ; n_try < max_tries ; n_try++ )
    {

        init_try(n_try);

        while ( !termination_condition() )
        {

            construct_solutions();

            if ( ls_flag > 0 )
                local_search();

            update_statistics();

            pheromone_trail_update();

            search_control_and_statistics();

            iteration++;
        }
        exit_try(n_try);
    }
    exit_program();

    free( instance.distance );
    free( instance.nn_list );
    free( pheromone );
    free( total );
    free( best_in_try );
    free( best_found_at );
    free( time_best_found );
    free( time_total_run );
    for ( i = 0 ; i < n_ants ; i++ )
    {
        free( ant[i].tour );
        free( ant[i].visited );
    }
    free( ant );
    free( (*best_so_far_ant).tour );
    free( (*best_so_far_ant).visited );
    free( prob_of_selection );
    return(0);
}