recruitingantsystemtsp.cc

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

/*  >->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->
    RecruitingAntSystemTSP.cc, Heiko Stamer <[e-mail]>

      Recruiting Ant System (RAS) for the Traveling Salesman Problem (TSP)
	  
	     [The Recruiting Ant System:
                  Extending the Ant System by a Group Recruitment Strategy]
					   
         [The Ant System: Optimization by a colony of cooperating agents]
                  by M. Dorigo, V. Maniezzo, A. Colorni
    IEEE Transactions on Systems, Man and Cybernetics - Part B, Vol.26-1 1996
	
            http://stinfwww.informatik.uni-leipzig.de/~mai97ixb
    >->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->

  Copyright (C) 2001-until_the_end_of_the_ants  <Heiko Stamer>

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.                 */
	
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <unistd.h>
#include <time.h>

#define N 70

double C[N][2] = { {64 , 96} , {80 , 39} , {69 , 23} , {72 , 42} , {48 , 67} , {58 ,
43} , {81 , 34} , {79 , 17} , {30 , 23} , {42 , 67} , {7 , 76} , {29 , 51} , {78
, 92} , {64 , 8} , {95 , 57} , {57 , 91} , {40 , 35} , {68 , 40} , {92 , 34} ,
{62 , 1} , {28 , 43} , {76 , 73} , {67 , 88} , {93 , 54} , {6 , 8} , {87 , 18} ,
{30 , 9} , {77 , 13} , {78 , 94} , {55 , 3} , {82 , 88} , {73 , 28} , {20 , 55}
, {27 , 43} , {95 , 86} , {67 , 99} , {48 , 83} , {75 , 81} , {8 , 19} , {20 ,
18} , {54 , 38} , {63 , 36} , {44 , 33} , {52 , 18} , {12 , 13} , {25 , 5} , {58
, 85} , {5 , 67} , {90 , 9} , {41 , 76} , {25 , 76} , {37 , 64} , {56 , 63} ,
{10 , 55} , {98 , 7} , {16 , 74} , {89 , 60} , {48 , 82} , {81 , 76} , {29 , 60}
, {17 , 22} , {5 , 45} , {79 , 70} , {9 , 100} , {17 , 82} , {74 , 67} , {10 ,
68} , {48 , 19} , {83 , 86} , {84 , 94} };

typedef int Tour[N][2];
typedef double doubleMatrix[N][N];

doubleMatrix D;

double dist(int i, int j)
{
	return (sqrt(pow((C[i][0]-C[j][0]), 2.0) + pow((C[i][1]-C[j][1]), 2.0)));
}

void calc_dist()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			D[i][j] = dist(i, j);
}

double calc_length(Tour tour)
{
	double l = 0.0;
	for (int n = 0; n < N; n++)
	{
		int i = tour[n][0];
		int j = tour[n][1];
		l += D[i][j];
	}
	return (l);
}

void print_tour(Tour tour)
{
	for (int n = 0; n < N; n++)
		printf("( %d , %d ) ", tour[n][0], tour[n][1]);
	printf("\n");
}

int sum_sequence(int array[], int count)
{
	int sum = 0;
	for (int i = 0; i < count; i++)
		sum += array[i];
	return (sum);
}

class RecruitingAntSystem;
class TransportAnt;

class SearchAnt
{
	friend class RecruitingAntSystem;
	friend class TransportAnt;
	
	private:
		RecruitingAntSystem *AS;
		int START_CITY, CURRENT_CITY;
		int ALLOWED[N];
		Tour CURRENT_TOUR;
		int CURRENT_TOUR_INDEX;
		
	public:
        SearchAnt(RecruitingAntSystem *as, int start_city);		
		inline void moveTo(int to_city);
		inline int choose();
		inline Tour *search();
};

class TransportAnt
{
	private:
		RecruitingAntSystem *AS;
		int START_CITY, CURRENT_CITY;
		int ALLOWED[N];
		Tour FOLLOW_TOUR, CURRENT_TOUR;
		int FOLLOW_TOUR_INDEX, CURRENT_TOUR_INDEX;
		bool LOST_FOLLOW_TOUR;
		
	public:	
        TransportAnt(RecruitingAntSystem *as, SearchAnt ant);		
		inline void moveTo(int to_city);
		inline int choose();
		inline Tour *follow();
};

class RecruitingAntSystem
{
    private:
		double ALPHA, BETA, RHO, Q, XI;
		doubleMatrix TAU, dTAU;
		int ACTIVE[N][N];
		static const int M = N;
		static const int R0 = 5;
		static const int R1 = M;
		static const int R = R0 * R1;
		SearchAnt *SEARCH_ANTS[M];
		TransportAnt *TRANSPORT_ANTS[R];
		double BEST_LENGTH;
		Tour BEST_TOUR;
		
	public:	
        RecruitingAntSystem(double alpha, double beta, double rho, double q,
		double xi);
		inline void init_tau_by_value(double value);
		inline void init_tau_by_matrix(doubleMatrix matrix);
		inline void	init_uniform();
		inline void	init_random();
		inline double get_XI();
		inline double ETA(int i, int j);
		inline double transition(int i, int j);
		inline double sum_transition(int i, int allowed[]);
		inline void	clear_update_transitions();
		inline int check_active(int what);
		inline void add_update_transitions(Tour tour, double length);
		inline void update_transitions();
		inline doubleMatrix *get_tau();
		inline void sort_search_ants();
		inline Tour *search(int T);
};

SearchAnt::SearchAnt(RecruitingAntSystem *as, int start_city)
{
	AS = as;
	START_CITY = start_city;
}
		
inline void SearchAnt::moveTo(int to_city)
{
	ALLOWED[to_city] = 0;
	CURRENT_TOUR[CURRENT_TOUR_INDEX][0] = CURRENT_CITY;
	CURRENT_TOUR[CURRENT_TOUR_INDEX][1] = to_city;
	CURRENT_TOUR_INDEX++;
	CURRENT_CITY = to_city;
}
		
inline int SearchAnt::choose()
{
	double sum = AS->sum_transition(CURRENT_CITY, ALLOWED);
	double p = (double)rand() / RAND_MAX;
	double p_j = 0.0;
			
	for (int j = 0; j < N; j++)
	{
		if (ALLOWED[j] == 1) p_j += AS->transition(CURRENT_CITY, j) / sum;
		if ((p < p_j) && (ALLOWED[j] == 1))
			return (j);
	}
	return (-1);
}
		
inline Tour *SearchAnt::search()
{
	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);
}

TransportAnt::TransportAnt(RecruitingAntSystem *as, SearchAnt ant)
{
	AS = as;
	int sc = (int)(N * (rand() / RAND_MAX));
	FOLLOW_TOUR_INDEX = 0;
	for (int i = sc; i < N; i++)
	{
		FOLLOW_TOUR[FOLLOW_TOUR_INDEX][0] = ant.CURRENT_TOUR[i][0];
		FOLLOW_TOUR[FOLLOW_TOUR_INDEX][1] = ant.CURRENT_TOUR[i][1];
		FOLLOW_TOUR_INDEX++;
	}
	for (int i = 0; i < sc; i++)
	{
		FOLLOW_TOUR[FOLLOW_TOUR_INDEX][0] = ant.CURRENT_TOUR[i][0];
		FOLLOW_TOUR[FOLLOW_TOUR_INDEX][1] = ant.CURRENT_TOUR[i][1];
		FOLLOW_TOUR_INDEX++;
	}
	START_CITY = FOLLOW_TOUR[0][0];
}
		
inline void TransportAnt::moveTo(int to_city)
{
	ALLOWED[to_city] = 0;
	CURRENT_TOUR[CURRENT_TOUR_INDEX][0] = CURRENT_CITY;
	CURRENT_TOUR[CURRENT_TOUR_INDEX][1] = to_city;
	CURRENT_TOUR_INDEX++;
	FOLLOW_TOUR_INDEX++;
	CURRENT_CITY = to_city;
}
		
inline int TransportAnt::choose()
{
	double q = (double)rand() / RAND_MAX;
	if (LOST_FOLLOW_TOUR || (q < AS->get_XI()))
	{
		LOST_FOLLOW_TOUR = true;
		double sum = AS->sum_transition(CURRENT_CITY, ALLOWED);
		double p = (double)rand() / RAND_MAX;
		double p_j = 0.0;
			
		for (int j = 0; j < N; j++)
		{
			if (ALLOWED[j] == 1) p_j += AS->transition(CURRENT_CITY, j) / sum;
			if ((p < p_j) && (ALLOWED[j] == 1))
				return (j);
		}
		return (-1);
	}
	else
	{
		return (FOLLOW_TOUR[FOLLOW_TOUR_INDEX][1]);
	}
}
		
inline Tour *TransportAnt::follow()
{
	CURRENT_CITY = START_CITY;
	CURRENT_TOUR_INDEX = 0;
	FOLLOW_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);
}

RecruitingAntSystem::RecruitingAntSystem(double alpha, double beta, double rho,
double q, double xi)
{
	ALPHA = alpha;
	BETA = beta;
	RHO = rho;
	Q = q;
	XI = xi;
	for (int i = 0; i < N; i++)
	{
		BEST_TOUR[i][0] = i;
		if (i == (N - 1))
			BEST_TOUR[i][1] = 0;
		else
			BEST_TOUR[i][1] = i + 1;
	}
	BEST_LENGTH = calc_length(BEST_TOUR);
}

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

inline void RecruitingAntSystem::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	RecruitingAntSystem::init_uniform()
{
	// uniformly distributed
	for (int k = 0; k < M; k++)
		SEARCH_ANTS[k] = new SearchAnt(this, (k % N));
}

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

inline double RecruitingAntSystem::get_XI()
{
	return ( XI );
}

inline double RecruitingAntSystem::ETA(int i, int j)
{
	return ( 1.0 / D[i][j] );
}
		
inline double RecruitingAntSystem::transition(int i, int j)	
{
	if (i != j)
		return ( pow( TAU[i][j], ALPHA ) * pow( ETA(i, j), BETA ) );
	else
		return(0.0);
}
	
inline double RecruitingAntSystem::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 void	RecruitingAntSystem::clear_update_transitions()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			dTAU[i][j] = 0.0;
			ACTIVE[i][j] = 0;
		}
}
				
inline int RecruitingAntSystem::check_active(int what)
{
	int	sum = 0;
	for (int i = 0; i < N; i++)
	{	
		sum += sum_sequence(ACTIVE[i], N);
		if (sum > what)
			return (1);
	}
	return (0);
}

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

inline void RecruitingAntSystem::update_transitions()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			TAU[i][j] = RHO * TAU[i][j] + dTAU[i][j];
}

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

inline void RecruitingAntSystem::sort_search_ants()
{
	SearchAnt *tmp;
	bool xchg = true;
	int last, up;
	
	last = N - 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 *RecruitingAntSystem::search(int T)
{
	Tour tour;
	double tour_length;
	int	no_action_runs = 0;
	int	max_no_action_runs = 10;

	// do T iterations 
	int t;
	for (t = 0; t < T; t++)
	{
//printf(".\n");
		// Search Ants
		clear_update_transitions();
		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;
				//printf("Search Ant: %f \n", tour_length);
				//print "[%s/%s] best tour (length = %s): %s"\
				//% (t + 1, T, best_length, best_tour)
			}
			add_update_transitions(tour, tour_length);
		}
		update_transitions();
		
		// R0 local best Search Ants recruit R1 Transport Ants from nest
		sort_search_ants();
		for (int k = 0; k < R0; k++)
			for (int l = 0; l < R1; l++)
				TRANSPORT_ANTS[(k * R1) + l] = 
				new TransportAnt(this, *SEARCH_ANTS[k]);
		
		// Transport Ants
		clear_update_transitions();
		for (int k = 0; k < R; k++)
		{
			tour = *(TRANSPORT_ANTS[k]->follow());
			tour_length = calc_length(tour);
			if (tour_length < BEST_LENGTH)
			{
				BEST_TOUR = tour;
				BEST_LENGTH = tour_length;
				//printf("Follow Ant: %f \n", tour_length);
				//print "[%s/%s] best tour (length = %s): %s"\
				//% (t + 1, T, best_length, best_tour)
			}
			add_update_transitions(tour, tour_length);
		}
		update_transitions();
		
		// destroy Transport Ants
		for (int k = 0; k < R; k++)
			delete TRANSPORT_ANTS[k];
		
		// checking for stagnation behaviour
		if (!(check_active(2 * N)))
			no_action_runs += 1;
		if (no_action_runs > max_no_action_runs)
			break;
	}
	
	printf("%f\n", BEST_LENGTH);
	//printf("[%d/%d] best tour (length = %f):\n", t, T, BEST_LENGTH);
	//print_tour(BEST_TOUR);
	//printf("[%d/%d] iterations done\n", t, T);
	return (&BEST_TOUR);
}

int main(int argc, char* argv[])
{
	// initalize PRNG
	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 System		
	RecruitingAntSystem *as = new RecruitingAntSystem(1.0, 5.0, 0.5, 100.0, 0.01);
	as->init_tau_by_value(0.01);
	as->init_uniform();
	as->search(100);
	
	return(0);
}