antsystem.cpp

一个用VC的蚁群算法解决TSP问题

// AntSystem.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include ".\antsystem.h"
#include <math.h>
#include <time.h>

int _tmain(int argc, _TCHAR* argv[])
{
	CAntSystem antsys;
	antsys.ResetSize(10,5);
	srand( (unsigned)time( NULL ) );
	double tmp;
	int i,j;
	for( i=0;i<10;i++)
	{
		for(j=i;j<10;j++){
			tmp=rand();
			tmp/=RAND_MAX;
			antsys.SetData(i,j,tmp);
			antsys.SetData(j,i,tmp);
		}
	}
	antsys.GetRoad(i);
	return 0;
}

void CAntSystem::destroy(){
	if(m_matrix){
		for(int i=0;i<nu;i++)
			delete[]m_matrix[i];
		delete[]m_matrix;
		m_matrix=0;
	}
	if(trailIntensity){
		for(int i=0;i<nu;i++)
			delete[]trailIntensity[i];
		delete[]trailIntensity;
		trailIntensity=0;
	}
	if(d_trail){
		for(int i=0;i<nu;i++)
			delete[]d_trail[i];
		delete[]d_trail;
		d_trail=0;
	}
	if(tabu)
		delete[]tabu;
	if(road)
		delete[] road;
}
CAntSystem::CAntSystem(int n,int m,int max):NC_MAX(max),alfa(1.0),beita(1.0),luo(0.5),Q(100){
	Initial(n,m);
}
CAntSystem::CAntSystem(int max):nu(0),ants(0),NC_MAX(max),alfa(1.0),beita(1.0),luo(0.5),Q(100)
,road(0),tabu(0),d_trail(0),trailIntensity(0){
		m_matrix=0;
}
CAntSystem::~CAntSystem(){
		destroy();
}
bool CAntSystem::SetData(int i, int j, double v)
{
	if(i>=0&&i<nu&&j>=0&&j<nu){
		m_matrix[i][j]=v;
		return true;
	}
	return false;
}

bool CAntSystem::ResetSize(int n,int m)
{
	destroy();
	Initial(n,m);
	return false;
}

void CAntSystem::Initial(int n,int m)
{/*构造矩阵，并置所有的值为0，等价于没有边*/
	nu=n;ants=m;
	t=0;
	m_matrix=new double*[nu];
	int i;
	for(i=0;i<nu;i++)
		m_matrix[i]=new double[nu],fill(m_matrix[i],m_matrix[i]+nu,0.0);
	trailIntensity=new double*[nu];
	for( i=0;i<nu;i++)
		trailIntensity[i]=new double[nu],fill(trailIntensity[i],trailIntensity[i]+nu,0.01);
	d_trail=new double*[nu];
	for( i=0;i<nu;i++)
		d_trail[i]=new double[nu],fill(d_trail[i],d_trail[i]+nu,0.0);
	tabu=new set<int>[nu];
	road=new vector<int>[nu];
	L=new double[nu];
}

void CAntSystem::SetCoef(double a, double b, double p, double q)
{
	alfa=a,beita=b,luo=p,Q=q;
}

double CAntSystem::Probability(int i,int j,int k)
{
	if(tabu[k].find(j)!=tabu[k].end())
        return 0.0;
	if(abs(m_matrix[i][j])<0.00001)
		return 0.0;
	double value=pow(trailIntensity[i][j],alfa)*pow(1.0/m_matrix[i][j],beita);
	double tmp=0;
	for(int kk=0;kk<nu;kk++){
		if(tabu[k].find(kk)!=tabu[k].end())
			continue;
		if(abs(m_matrix[i][j])<0.00001)
			continue;
		tmp+=pow(trailIntensity[i][kk],alfa)*pow(1.0/m_matrix[i][kk],beita);
	}
	value/=tmp;
	return value;
}

void CAntSystem::start(void)
{
	srand( (unsigned)time( NULL ) );
	for(int i=0;i<ants;i++){
		int tmp=rand()%nu;
		tabu[i].insert(tmp);
		road[i].push_back(tmp);
	}
}

double CAntSystem::move(int &index)
{
	int k,i,j;
	for(k=0;k<ants;k++)
	{
		tabu[k].clear(),tabu[k].insert(road[k][0]);
		road[k].erase(road[k].begin()+1,road[k].end());
	}
	for( i=0;i<nu;i++)
		d_trail[i]=new double[nu],fill(d_trail[i],d_trail[i]+nu,0.0);
	while(tabu[0].size()<nu){
		for(k=0;k<ants;k++){
			int j=road[k][road[k].size()-1];
			double tmp=0.0;
			for(i=0;i<nu;i++){
				double tmp2=Probability(j,i,k);
				if(tmp2>tmp){
					tmp=tmp2;t=i;
				}
			}
			tabu[k].insert(t);
			road[k].push_back(t);
		}
	}
	fill(L,L+nu,0.0);
	for(k=0;k<ants;k++){
		for(i=0;i<nu-1;i++)
			L[k]+=m_matrix[road[k][i]][road[k][i+1]];
		L[k]+=m_matrix[road[k][i]][road[k][0]];
		for(i=0;i<nu-1;i++)
			d_trail[road[k][i]][road[k][i+1]]+=Q/L[k];
		d_trail[road[k][i]][road[k][0]]+=Q/L[k];
	}
	for(i=0;i<nu;i++)
		for(j=0;j<nu;j++)
			trailIntensity[i][j]+=d_trail[i][j];
	for(i=0;i<nu;i++)
		fill(d_trail[i],d_trail[i]+nu,0.0);
	index=0;
	double distance=L[0];
	for(k=1;k<ants;k++)
		if(L[k]<distance)
			distance=L[k],index=k;
	return distance;
}

double CAntSystem::GetRoad(int&index)
{
	FILE*fp=fopen("c:\\ants.txt","w");
	int i,j;
	for(i=0;i<nu;i++){
		for(j=0;j<nu;j++)
			fprintf(fp,"%g,",m_matrix[i][j]);
		fprintf(fp,"\n");
	}
	start();
	double prevalue,error=move(index);
	prevalue=error;
	double value;
	int NC=1;
	while(NC<NC_MAX&&error>0.001){
		value=move(index);
		error=abs(prevalue-value);
		prevalue=value;
		NC++;
	}
	for(i=0;i<road[index].size();i++)
		fprintf(fp,"%d ",road[index][i]);
	fprintf(fp,"\n%g\n",value);
	fclose(fp);
	return value;
}