acs.c

C语言版本的蚁群系统算法

/*
      ANT-CYCLE ALGORITHM FOR TSP
      File:    acs.c
      Author:  ehui928
      Purpose: implementation of acs.h
	  Date:		2007-01-18
	  Reference:  Dorigo M --"The Ant System: Optimization by 
			      a colony of cooperating agents"  IEEE 1996
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include "acs.h"
#include "tsp.h"
#include "ant.h"


#define ANT_NUM	 30				/* number of ants */
#define NC_MAX	1000			/* max iterations for m ants */
#define EPSLON	1e-4			/* used to compare with double values */
#define COVERG_NUM	500         /* number to test if tour is converged */


const double alpha = 1;			/* intensity of trail */
const double beta = 4.5;		/* visibility of trail */
const double  rho = 0.5;		/* 1-rho is the evaporate rate */
const double tao0 = 1e-6;		/* initial pheromone */
const double Q = 	100;		/* const used to update pheromone */
const double q_0 = 0.25;		/* used to decide which transition rule to be choosed */
/* Best q_0 for Oliver30.tsp is 0.25, length = 423.245 */


double distances[CITY_NUM+1][CITY_NUM+1];	/* distance matrix */
double tao[CITY_NUM+1][CITY_NUM+1];			/* pheromone matrix */
double delta_tao[CITY_NUM+1][CITY_NUM+1];	/* pheromone increment on edge(i,j) */


/* f_out defined in main.c, used to record results */
extern FILE *f_out;

void initialize_pheromone()
/*
	FUNCTION:		initial pheromone on all edge(i,j) to tao0
	INPUT:			none
	RETURN:			none
*/
{
    int i, j;
    for (i = 1; i < CITY_NUM+1; i++)
        for (j = 1; j < CITY_NUM+1; j++)
            tao[i][j] = tao0;
}

void reset_delta_tao()
/*
	FUNCTION:		clear the delta_tao matrix, set it all to 0
	INPUT:			none
	RETURN:			none
*/
{
    int i, j;
    for (i = 1; i < CITY_NUM+1; i++)
        for (j = 1; j < CITY_NUM+1; j++)
            delta_tao[i][j] = 0.0;
}



double find_best_tour()
/*
	FUNCTION:		find the global best tour of TSP problem
	INPUT:			none
	RETURN:			the length of global best tour
	SIDE EFFECTS:	print the global best tour
*/
{
    /*
    	NC --------------------iterator time
    	i,j--------------------city index
    	k----------------------ant index
    	s----------------------tabu index
		ants-------------------ants which used to find tours
					ants[0] is not used, so as the L[0],best_tour[0] etc.
    	start------------------starting city
    	best_tour--------------best tour ever find by ANT_NUM ants
    	best_ant_index---------index of ant which found the best tour
    	L[ANT_NUM+1]-----------------tour lengths  ANT_NUM ant found
    	best_len---------------record best tour length all ants find one iteration
    	global_best_len--------global best length
    	converge---------------test convergence
    */
    int NC = 0;
    int i, j;
    int k;
    int s;
    Ant ants[ANT_NUM+1];
    int start = 1;
    int best_tour[CITY_NUM+1];
    int best_ant_index = 1;

    double L[ANT_NUM+1];
    double best_len = 10000;
    double global_best_len = 10000;

    int converge = 0;

    /* initialize pheromone on city edges */
    initialize_pheromone();

    while (NC < NC_MAX)
    {
        s = 1;	/* tabu list index */

        /* put each ant to starting city */
        for (k = 1; k <= ANT_NUM; k++)
        {
            initial_ant(&ants[k]);
            ants[k].cur = start;
            ants[k].allow[start] = 1;
            ants[k].tabu[s] = start;
        }

        /* CITY_NUM-1 cities to choose */
        for (i = 1; i < CITY_NUM; i++)
        {
            s++;

            for (k = 1; k <= ANT_NUM; k++)
            {
                int t;	/* save next city to move */
                t = choose_next_city(&ants[k]);
                ants[k].tabu[s] = t;
                ants[k].allow[t] = 1;
                ants[k].cur = t;
            }
        }

        /*
        	caculate the length of every tour that ants found,
        	and update the pheromone.
        */

        for (k = 1; k <= ANT_NUM; k++)
        {
			/* 
				print tour each ant found,just for debug
			*/
			print_ant_tour(ants[k]);
			
            L[k] = caculate_tour_length(ants[k]);
            if (L[k] < best_len)
            {
                best_len = L[k];
                best_ant_index = k;
            }
        }


        /* compute delta_tao[i][j] on every edge of cities */
        for (i = 1; i <= CITY_NUM; i++)
            for (j = 1; j <= CITY_NUM; j++)
            {
                for (k = 1; k <= ANT_NUM; k++)
                {
                    if (is_in_tour(i, j, ants[k].tabu, CITY_NUM))
                        delta_tao[i][j] += Q/L[k];
                }

            }

        /* update pheromone on every edge on a tour */
        for (i = 1; i <= CITY_NUM; i++)
            for (j = 1; j <= CITY_NUM; j++)
            {
                tao[i][j] = rho * tao[i][j] + delta_tao[i][j];
            }


        /* check if converge to one best tour */
        if (fabs(best_len - global_best_len) < EPSLON)
        {
            converge++;
            if (converge >= COVERG_NUM)
                break;
        }
        else 
		if (best_len < global_best_len)
            {
                converge = 0;

                global_best_len = best_len;

                /* save best tour */
                for (i = 1; i <= CITY_NUM; i++)
                {
                    best_tour[i] = ants[best_ant_index].tabu[i];
                }
            }

        NC++;

        /* set delta_tao[i][j] to 0 */
        reset_delta_tao();

    } /* end while */

	/* free resources that ants are occupying */
    for (k = 1; k <= ANT_NUM; k++)
        destroy_ant(&ants[k]);

    print_best_tour(best_tour, CITY_NUM);
    return global_best_len;
}




int is_in_tour(int i, int j, int tour[], int n)
/*
	FUNCTION:	check whether edge(i,j) is in tour
	INPUT:		i, j---city index
				tour[]----tour an ant build
				n---------size of tour[]
	RETURN:		if edge(i,j) is in tour, then return 1;
				otherwise return 0.
	EFFECTS:	print the global best tour
*/

{
    int s;
    for (s = 1; s < n; s++)
    {
        if (i == tour[s] && j == tour[s+1])
            return 1;
    }

    if (i == tour[s] && j == 1)
        return 1;

    return 0;
}

void print_best_tour(int tour[], int n)
/*
	FUNCTION:	print global best tour
	INPUT:		tour[]----global best tour
				n---------size of tour[]
	RETURN:		none
	EFFECTS:	print the global best tour
*/
{
    int i;
	
    printf("Find best tour: ");
	fprintf(f_out, "Find best tour: ");

    for (i = 1; i <= n; i++)
	{
        printf("%d-", tour[i]);
		fprintf(f_out, "%d-", tour[i]);
	}

    printf("%d\n", tour[1]);
	fprintf(f_out, "%d\n", tour[1]);

	fclose(f_out);

}