ant.c

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

/*
      ANT-CYCLE ALGORITHM FOR TSP
      File:    ant.c
      Author:  ehui928
      Purpose: implementation of ant.h
      Date:		2007-01-18
*/

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


extern double distances[CITY_NUM+1][CITY_NUM+1];
extern double tao[CITY_NUM+1][CITY_NUM+1];
extern double alpha;
extern double beta;
extern FILE *f_out;

long int seed = 12345678;	/* seed to generate random number */

void initial_ant(Ant *pant)
{
    pant->cur = 0;
    pant->length = 0.0;
    pant->tabu = (int *) malloc(sizeof(int) * (CITY_NUM+1));
    pant->allow = (int *) malloc(sizeof(int) * (CITY_NUM+1));
    memset(pant->tabu, 0, sizeof(int) * (CITY_NUM+1));
    memset(pant->allow, 0, sizeof(int) * (CITY_NUM+1));

	/*  if you want the seed changes every time when the 
	    program runs, then uncomment the following line
	 */
	/*	seed = (long int)time(NULL); */
}


void destroy_ant(Ant *pant)
{
    free(pant->tabu);
    free(pant->allow);
}




int choose_next_city(Ant *pant)
/*
	FUNCTION:		choose the next city according to transition rule
	INPUT:			the poiter to Ant---pant
	RETURN:			next city been choosed
*/

{
	extern double ran01( long *idum );
	extern double q_0;
/*
	i---------------city index
	j---------------next city to choose 
	k---------------index of f_tmp
	s---------------index of prob[]
	n---------------actual size of candidate

	candidate---candidate cities can be chosen
	tmp---------record the values of 
				tao[current_city][candidate_city]^alpha * yita[current_city][candidate_city]^beta;
				which yita[i][j] is defined as (1/distances[i][j]).

	max --------max values of tmp
    sum---------sum of tmp	
	prob--------probabilities of each candidate city to be choosen
	q-----------random generate q to decide using which transition rule
*/

    int i;
    int j;
    int k = 1;
    int s = 1;
	int n;
	int candidate[CITY_NUM+1];

    
    double tmp[CITY_NUM+1];
	double max = -1;
    double sum = 0;
	
	double prob[CITY_NUM+1] = {0};
	
	double q;	/* random generate q to decide using which transition rule */


    for (i = 1; i <= CITY_NUM; i++)
    {
        if (!pant->allow[i])
        {
            /* city i is not visited */
			candidate[s++] = i;
            tmp[k] = pow(tao[pant->cur][i], alpha) * pow(1/distances[pant->cur][i], beta);
			
            if (tmp[k] >= max)
            {
                max = tmp[k];
                j = i;
            }
            sum += tmp[k];
            k++;
        }
    }
		n = k - 1;

	for (i = 1; i <= n; i++)
	{
		prob[i] = tmp[i] / sum;
	}

		/* generate a random double number between [0,1] */
		q = ran01( &seed );


	if ( (q_0 > 0.0) && (q < q_0)  )
		/* 
			choose next city according to 
			pheromone maximum multiply heuristic values
		*/
	{
		return j;
	}

	else
		/* choose a random city  according to probabilities */
	{
		double rnd;
		double partial_sum;
		rnd = ran01( &seed );

		i = 1;

		partial_sum = prob[i];
		while ( partial_sum <= rnd ) 
		{
			i++;
			partial_sum += prob[i];
		}

		return candidate[i];
	}

}


double caculate_tour_length(Ant ant)
{
    int i;
    double len = 0.0;

    for (i = 1; i < CITY_NUM; i++)
        len += distances[ant.tabu[i]][ant.tabu[i+1]];

    len += distances[ant.tabu[CITY_NUM]][ant.tabu[1]];

    return len;
}

void print_ant_tour(Ant ant)
/*
	FUNCTION:		print a tour an ant found
	INPUT:			Ant ant
	RETURN:			none
*/
{
    int i;
    for (i = 1; i < CITY_NUM+1; i++)
		fprintf(f_out, "%d-", ant.tabu[i]);
	fprintf(f_out, "%d\n", ant.tabu[1]);
    /*
    printf("%d-", ant.tabu[i]);
    printf("%d\n", ant.tabu[1]);
	*/
}




/* 
	constants for a random number generator, 
	for details see numerical recipes in C 
*/

#define IA 16807
#define IM 2147483647
#define AM (1.0/IM)
#define IQ 127773
#define IR 2836

double ran01( long *idum )
/*    
      FUNCTION:       generate a random number that is uniformly distributed in [0,1]
      INPUT:          pointer to variable with the current seed
      OUTPUT:         random number uniformly distributed in [0,1]
      (SIDE)EFFECTS:  random number seed is modified (important, this has to be done!)
      ORIGIN:         numerical recipes in C
*/
{
  long k;
  double ans;

  k =(*idum)/IQ;
  *idum = IA * (*idum - k * IQ) - IR * k;
  if (*idum < 0 ) *idum += IM;
  ans = AM * (*idum);
  return ans;
}