recruitingantcolonysystemtsp.cc

这是用RecruitingAntColonySystem 解决tsp问题的C++源码 希望对大家研究蚂蚁算法有所帮助

		}
		double sum = RACS->sum_transition(CURRENT_CITY, ALLOWED);
		double p = rand() / (double)RAND_MAX;
		double p_j = 0.0;
			
		for (int j = 0; j < N; j++)
		{
			if (ALLOWED[j] == 1) 
				p_j += RACS->transition(CURRENT_CITY, j) / sum;
			if ((p < p_j) && (ALLOWED[j] == 1))
				return j;
		}
		return -1;
	}
}
		
inline Tour *TransportAnt::follow()
{
	CURRENT_CITY = START_CITY;
	CURRENT_TOUR_INDEX = 0;
	for (int i = 0; i < N; i++)
		ALLOWED[i] = 1;
	ALLOWED[CURRENT_CITY] = 0;
	while (sum_sequence(ALLOWED, N) > 0)
		moveTo(choose());
	ALLOWED[START_CITY] = 1;
	moveTo(START_CITY);
	return &CURRENT_TOUR;
}

/******************************************************************************/
		
RecruitingAntColonySystem::RecruitingAntColonySystem(double alpha, double beta, double rho, 
double q0)
{
	ALPHA = alpha;
	BETA = beta;
	RHO = rho;
	Q0 = q0;
}

inline double RecruitingAntColonySystem::calc_tau0()
{
	double best_length = (double)N * max_dist();
	
	for (int n = 0; n < N; n++)
	{
		NNAnt *nnANT = new NNAnt(n);
		Tour tour;
		tour = *(nnANT->search());
		double tour_length = calc_length(tour);
		if (tour_length < best_length)
			best_length = tour_length;
		delete nnANT;
	}
	return 1.0 / ((double)N * best_length);
}

inline void RecruitingAntColonySystem::init_tau_by_value(double value)	
{
	TAU0 = value;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			TAU[i][j] = TAU0;
}

inline void RecruitingAntColonySystem::init_theta_by_value(double value)	
{
	for (int k = 0; k < R0; k++)
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				THETA[k][i][j] = value;
}

inline void RecruitingAntColonySystem::init_tau_by_matrix(doubleMatrix matrix)	
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			TAU[i][j] = matrix[i][j];
}

inline void RecruitingAntColonySystem::init_theta_by_matrix(doubleMatrix matrix)	
{
	for (int k = 0; k < R0; k++)
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				THETA[k][i][j] = matrix[i][j];
}

inline void	RecruitingAntColonySystem::init_uniform()
{
	// uniformly distributed
	for (int k = 0; k < M; k++)
		SEARCH_ANTS[k] = new SearchAnt(this, (k % N));
}

inline void	RecruitingAntColonySystem::init_random()
{	
	// randomly distributed
	for (int k = 0; k < M; k++)
		SEARCH_ANTS[k] = new SearchAnt(this, (int)((double)N * (rand() / (double)RAND_MAX)));
}

inline void	RecruitingAntColonySystem::init_randomMOAPC()
{	
	// randomly distributed with MOAPC (most one ant per city)
	bool MOAPCarray[N];
	assert(M <= N);
	
	for (int n = 0; n < N; n++)
		MOAPCarray[n] = false;
	for (int k = 0; k < M; k++)
	{
		int c;
		do
		{
			c = (int)((double)N * (rand() / (double)RAND_MAX));
		}
		while (MOAPCarray[c]);
		
		MOAPCarray[c] = true;
		SEARCH_ANTS[k] = new SearchAnt(this, c);
	}
}

inline double RecruitingAntColonySystem::ETA(int i, int j)
{
	return ( 1.0 / D[i][j] );
}
		
inline double RecruitingAntColonySystem::transition(int i, int j)	
{
	if (i != j)
		return ( TAU[i][j] * pow( ETA(i, j), BETA ) );
	else
		return(0.0);
}

inline double RecruitingAntColonySystem::theta_transition(int k, int i, int j)	
{
	if (i != j)
		return ( THETA[k][i][j] * pow( ETA(i, j), BETA ) );
	else
		return(0.0);
}

inline double RecruitingAntColonySystem::sum_transition(int i, int allowed[])
{
	double sum = 0.0;
	for (int j = 0; j < N; j++) 
		sum += ((double)allowed[j] * transition(i, j));
	return (sum);
}

inline double RecruitingAntColonySystem::sum_theta_transition(int k, int i, int allowed[])
{
	double sum = 0.0;
	for (int j = 0; j < N; j++) 
		sum += ((double)allowed[j] * theta_transition(k, i, j));
	return (sum);
}

inline void RecruitingAntColonySystem::local_update_rule(int i, int j)
{
	TAU[i][j] = (1.0 - RHO) * TAU[i][j] + RHO * TAU0;
	// symmetric TSP
	TAU[j][i] = TAU[i][j];
}
	
inline void	RecruitingAntColonySystem::clear_global_update()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			dTAU[i][j] = 0.0;
}

inline void	RecruitingAntColonySystem::clear_theta_update()
{
	for (int k = 0; k < R0; k++)
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				dTHETA[k][i][j] = 0.0;
}				

inline void RecruitingAntColonySystem::add_global_update(Tour tour, double length)
{
	for (int n = 0; n < N; n++)
	{
		int i = tour[n][0];
		int j = tour[n][1];
		dTAU[i][j] += (1.0 / length);
		// symmetric TSP
		dTAU[j][i] += (1.0 / length);
	}
}

inline void RecruitingAntColonySystem::add_theta_update(int k, Tour tour, double length)
{
	for (int n = 0; n < N; n++)
	{
		int i = tour[n][0];
		int j = tour[n][1];
		dTHETA[k][i][j] += (1.0 / length);
		// symmetric TSP
		dTHETA[k][j][i] += (1.0 / length);
	}
}

inline void RecruitingAntColonySystem::global_update_rule()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			TAU[i][j] = (1.0 - ALPHA) * TAU[i][j] + ALPHA * dTAU[i][j];
}

inline void RecruitingAntColonySystem::theta_update_rule()
{
	for (int k = 0; k < R0; k++)
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				THETA[k][i][j] = (1.0 - ALPHA) * THETA[k][i][j] + ALPHA *
				dTHETA[k][i][j];
}

inline doubleMatrix *RecruitingAntColonySystem::get_tau()
{
	return &TAU;
}

inline void RecruitingAntColonySystem::sort_search_ants()
{
	SearchAnt *tmp;
	bool xchg = true;
	int last, up;
	
	last = M - 1;
	while (xchg)
	{
		xchg = false;
		up = last;
		for (int i = 1; i < up; i++)
			if (calc_length(SEARCH_ANTS[i-1]->CURRENT_TOUR) > 
			calc_length(SEARCH_ANTS[i]->CURRENT_TOUR))
			{
				tmp = SEARCH_ANTS[i];
				SEARCH_ANTS[i] = SEARCH_ANTS[i-1];
				SEARCH_ANTS[i-1] = tmp;
				xchg = true;
				last = i;
			}
	}
}
	
inline Tour *RecruitingAntColonySystem::search(int T)
{
	Tour best_tour, tour;
	double best_length = (double)N * max_dist(), tour_length;
	clear_global_update();
	
	// do T iterations of ant-cycle algorithm
	int t;
	for (t = 0; t < T; t++)
	{	
		// Search Ants
		for (int k = 0; k < M; k++)
		{
			tour = *(SEARCH_ANTS[k]->search());
			tour_length = calc_length(tour);
			if (tour_length < best_length)
			{
				best_tour = tour;
				best_length = tour_length;
				clear_global_update();
				add_global_update(tour, tour_length);
				//printf("search [%d / %d]: %lf \n", t, T, tour_length);
				//print_tour(best_tour);
			}
		}
				
		// R0 local best Search Ants recruit R1 Transport Ants from nest
		sort_search_ants();
		init_theta_by_value(0.0);
		clear_theta_update();
		for (int k = 0; k < R0; k++)
		{
			add_theta_update(k, SEARCH_ANTS[k]->CURRENT_TOUR, 
				calc_length(SEARCH_ANTS[k]->CURRENT_TOUR));
			for (int l = 0; l < R1; l++)
				TRANSPORT_ANTS[(k * R1) + l] = 
				new TransportAnt(this, k, 1.00);
		}
		theta_update_rule();
		clear_theta_update();
		
		// Transport Ants
		for (int k = 0; k < R; k++)
		{
			tour = *(TRANSPORT_ANTS[k]->follow());
			tour_length = calc_length(tour);
			if ((tour_length + .0001) < best_length)
			{
				best_tour = tour;
				best_length = tour_length;
				clear_global_update();
				add_global_update(tour, tour_length);
				//printf("transport [%d / %d]: %lf \n", t, T, tour_length);
				//print_tour(best_tour);	
			}
		}
		// Transport Ants go back to nest
		for (int k = 0; k < R; k++)
			delete TRANSPORT_ANTS[k];
			
		global_update_rule();
	}
		
	//printf("[%d/%d] best tour (length = %f):\n", t, T, best_length);
	//print_tour(best_tour);
	//printf("[%d/%d] iterations done\n", t, T);
	printf("%f\n", best_length);
	return (&best_tour);
}

int main(int argc, char* argv[])
{
	// PRNG initalisieren
	time_t timer; time(&timer);
	pid_t pid = getpid() + getppid();	
	unsigned long seed = (timer * pid);
	if (seed == 0) 
	{
	    time(&timer);
	    seed = 7 * timer * pid;
	    if (seed == 0) seed = pid; else seed = seed % 56000;
	} else seed = seed % 56000;
	srand((unsigned int)seed);
	
	// EUC2D
	calc_dist();
	
	// Recruiting Ant Colony System		
	RecruitingAntColonySystem *racs = 
		new RecruitingAntColonySystem(0.1, 2.0,	0.1, 0.9);

	double tau0 = racs->calc_tau0();
	racs->init_tau_by_value(tau0);
	racs->init_random();
	racs->search(1000);
	
	return 0;
}