acs.h

VC下的蚁群算法

/*
      ANT-CYCLE ALGORITHM FOR TSP
      File:    acs.h
      Author:  ehui928
      Purpose: some constants and functions used for acs
      Date:		2007-01-18
*/
#ifndef __ACS_H__
#define __ACS_H__

#include "logfile.h"

#define CITY_NUM	30		/* number of cities */
#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	4         /* number to test if tour is converged 500*/
//#define Real_CIrcle	100         /* number to test if tour is converged 500*/
typedef struct
{
	double x;
	double y;
} Point;

typedef struct
/*
	cur:	the current city which ant is at
	tabu:	tabu list ,it also used to record a tour which ant found
	allow:	contains cities that can be choosed 
			allow[N+1] initialize to 0;
			if city i has been visited , then set allow[i] to 1.
	length: length of the tour which current ant found
*/
{
    int cur;
    int *tabu;
    int *allow;
    double length;
} Ant;

class Acs
{
public:
	long int seed;	/* seed to generate random number */
	double alpha;			/* intensity of trail */
	double beta;		/* visibility of trail */
	double  rho;		/* 1-rho is the evaporate rate */
	double tao0;		/* initial pheromone */
	double Q;		/* const used to update pheromone */
	double q_0;		/* 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) */
	LogFile gLog;
	FILE *f_out;

	//for anolize
	double bestPerCircle[NC_MAX];
	double global_best_len;
protected:

	Point DataPoints[CITY_NUM+1];
	
public:
	Acs();
	~Acs();
	void read_data(char *filename);
	void initAll();

	double find_best_tour();
protected:
	void initialize_pheromone();
	int is_in_tour(int i, int j, int tour[], int n);

	void print_best_tour(int tour[], int n,double global_best_len);
	void initial_ant(Ant *pant);
	void destroy_ant(Ant *pant);
	double caculate_tour_length(Ant ant);
	int choose_next_city(Ant* pant);//1
	int choose_next_city_LunPanDu(Ant* pant);//2 使用轮盘赌法找下一个城市
	void print_ant_tour(Ant ant);



protected:
	double Euclid_distance(Point p1, Point p2);
	void caculate_distances();
	void print_distance(double distances[CITY_NUM+1][CITY_NUM+1]);	/* just for test */
	

	void print_coordinates(Point *p);	/* just for test */

	void reset_delta_tao();
	double ran01( long *idum );

};
#endif	/*__ACS_H__ */