gbas.cpp

本程序主要用链表实现了蚁群算法

/****************************************************************
                
				           蚁群算法
    针对TSP问题
****************************************************************/


#include"iostream.h"
#include"string.h"
#include"fstream.h"
#include"ctype.h"
#include"stdlib.h"
#include"math.h" //数学函数
#include"conio.h"
#include "iomanip.h"
#include"time.h"

#include"gbas.h"



/****************************************************************
                   全局变量的定义
****************************************************************/
int N=5;//距离矩阵的维数（默认为4）
int m=4;//初始路径的数目
linklist List[4];//4表示有4只蚂蚁
double kp=0.8;//挥发系数

paths Tr;
linklist R;//保留解，以备作比较
linklist W;//最好解，用整数表示顶点

//W,List[]的第一项均为起点0
linklist T;//表示(i,l)是弧，但l不在当前L(s)中，再减去起始点的集合
//T的第一项不表示任何东西
double Max=100;//


/****************************************************************
						子函数的定义
****************************************************************/

void GetDist();//返回距离矩阵
void InitTr();//信息素痕迹初始化
void InitW();//初始化最好解
void InitT();//初始化T集合
double Func(linklist array);//目标函数
int Existl(int curr,linklist array);//是否存在l，(i,l)是弧，但l不在当前L(s)中
double GetVal(int i,int j);//从矩阵中获得当前坐标的数值
void GetT(int curr,linklist lt);//
double GetA(int i,int j);//
int Selectj(int i);//涉及T
void GetMin();//获得当前最好解W
void Reforce();//增强挥发

void Eval();//将蚂蚁路径初始化

void OutRes(linklist array);//
void OutPath(paths lp);//

int random();
int Isequal(linklist a,linklist b);
/****************************************************************
							主函数
****************************************************************/

void InitOpen()
{
	fstream file;
	double in[10]={2.2361, 3.6056, 4, 2.8284,
		            2     , 3.6056, 4.1231,
                    2.2361, 4.1231,
                    2.8284};
	double array[5][5];
	file.open("gbas.txt",ios::in|ios::out);
	int i,j;
	int m=0;
	for(i=0;i<4;i++)
	{
		for(j=i+1;j<5;j++)
		{
			array[i][j]=in[m];
			array[j][i]=in[m];
			m++;
		}
	}
	for(i=0;i<5;i++)
		array[i][i]=0;
	for(i=0;i<5;i++)
	{
		for(j=0;j<5;j++)
			file<<setw(12)<<array[i][j]<<" ";
		file<<'\n';
	}
	file.close();

}



void main()
{
	InitPath(p);
	InitOpen();
	GetDist();//返回距离矩阵
	InitW();
	InitTr();
	InitL(R);
	InitL(T);	
	OutPath(Tr);
	int ant,j;
	linklist lt;
	int curr,Kstop=0;//curr表当前蚂蚁所在城市
	int Knum=0;
	for(int i=0;i<m;i++)
	{
		InitL(List[i]);
	}
	srand( (unsigned)time( NULL ) );
//	Eval();

//	GetMin();
//	Func(W);
//	cout<<endl<<endl<<endl;	    
//	OutRes(W);
//	cout<<endl<<endl<<endl;
	while(Knum<20)
	{
		if(Kstop==3 || Knum==19) //2次出现相同的最好解，则输出结果
		{
			cout<<"The best TSP length :"<<Func(W)<<endl;
			OutRes(W);//输出结果
			cout<<"OK"<<endl;
		
			break;
		}
		for(ant=0;ant<m;ant++)
		{
			curr=0;
			while(1)
			{
				if(ListLen(List[ant])==N || Existl(curr,List[ant]))
				{
					break;
				}
				else if(ListLen(List[ant])!=N)
				{
					GetT(curr,List[ant]);
					lt=(linklist)malloc(sizeof(link));
					if(ListLen(List[ant])==0)
					{
					
					//	lt=(linklist)malloc(sizeof(link));
						lt->node=(random()*N/RAND_MAX)%(N-1)+1;
						curr=lt->node;
						InsertL(List[ant],lt);
				//		cout<<"The first "<<lt->node<<endl;
					}
					else 
					{
						if(ListLen(T)!=0)
						{
							j=Selectj(curr);
							lt->node=j;
							InsertL(List[ant],lt);
							curr=j;
						}
						else
						{
							lt->node=0;
							InsertL(List[ant],lt);
							curr=0;//将当前城市置为0
						}
				//		cout<<"The second "<<endl;
					}
					Clear(T);//将T清空
				}
				
			}//while(1)	
		}
//		getch();
		GetMin();
		Reforce();
		Knum++;
	//	if(ListLen(R)==ListLen(W))
		if(Isequal(R,W))
		{
			Kstop++;
	//		cout<<"R:";
	//		OutRes(R);
	//		cout<<"W:";
	//		OutRes(W);
		}
	}
	cout<<"Kstop "<<Kstop<<endl;
	

}


int Isequal(linklist a,linklist b)
{
	int temp=0;
	while(a!=NULL &&b!=NULL)
	{
		if(a->node==b->node)
			temp++;
		else 
			return 0;
		a=a->next;
		b=b->next;
	}
	if(temp==N)
		return 1;
	return 0;
}


int random()
{
	int i;
	for(i=0;i<20000;i++)
	{
		rand();
	}
	return rand();
}


/*****************************************************************
 1.获取距离矩阵的维数；
 2.申请dist的空间；
*****************************************************************/

void GetDist()
{
	fstream file;
	int n=0;
	int i=0,j;
	double temp;
//	char fname[81];
	char str[100];
	char sep[]=" \t\n";
	char *token;
	char *stopstring;
	paths s;
//	cin.getline(fname,81,'\n');
//	file.open(fname,ios::in|ios::out);
	file.open("gbas.txt",ios::in|ios::out);
	while(!file.eof())
	{
		file.getline(str,100,'\n');
		token=strtok(str,sep);
		j=0;
		if(token!=NULL)
		{
			while(token!=NULL)
			{
				temp=strtod(token,&stopstring);
				if(temp!=0)
				{
					s=(paths)malloc(sizeof(path));
					s->hnode=i;
					s->tnode=j;
					s->value=temp;
					InsertPath(p,s);
				}
				j++;
				token=strtok(NULL,sep);
			}
			i++;
		}
	}
	file.close();
//	cout<<"This is GetDist()"<<endl;
}


/*****************************************************************
						信息素痕迹初始化
*****************************************************************/
void InitTr()
{
	double temp;
	paths pl,pt;
	pl=p->next;
	temp=p->value;
	InitPath(Tr);
	while(pl!=NULL)
	{
		pt=(paths)malloc(sizeof(path));
		pt->hnode=pl->hnode;
		pt->tnode=pl->tnode;
		pt->value=1/temp;
		InsertPath(Tr,pt);
		pl=pl->next;
	}
}


/*****************************************************************
							初始化最好解
	W为0......N-1,0
*****************************************************************/
//int Array[5]={2,3,1,4,0};//原始解
void InitW()
{
	InitL(W);
	linklist lt;

	for(int i=0;i<N;i++)
	{
		lt=(linklist)malloc(sizeof(link));
		lt->node=(i+1)%N;//Array[i];
		InsertL(W,lt);
	}
//	cout<<"This is InitW()"<<endl;
}


void Eval()//将蚂蚁路径初始化
{
	int i,j;
	linklist lt;
	int array[4][5]={{1,3,2,4,0},{3,1,2,4,0},{1,3,4,2,0},{4,2,3,1,0}};//
	for(i=0;i<m;i++)
	{
		for(j=0;j<N;j++)
		{
			lt=(linklist)malloc(sizeof(link));
			lt->node=array[i][j];
			InsertL(List[i],lt);
		}
		Func(List[i]);
		cout<<"初始路径："<<i<<":"<<endl;
		OutRes(List[i]);
	}

//	cout<<"This is Eval()"<<endl;
}


/*****************************************************************
			是否存在l，(i,l)是有效弧，但l不在当前L(s)中
			1表示不存在，0表示存在
*****************************************************************/
int Existl(int curr,linklist array)
{
	int i,temp;
	linklist lt;
	for(i=0;i<N;i++)
	{
		if(GetVal(curr,i)!=0)//从矩阵中获得当前坐标的数值
		{
			lt=array->next;
			temp=0;
			while(lt!=NULL)
			{
				if(i==ListLen(lt))
					break;
				else
					temp++;
				lt=lt->next;
			}
			if(temp==ListLen(array))
				return 0;
		}
	}
//	cout<<"This is Existl()"<<endl;
	return 1;

}

/*****************************************************************
			从矩阵中获得当前坐标的数值
*****************************************************************/
double GetVal(int i,int j)
{
	paths lp;
	lp=p->next;
	while(lp!=NULL)
	{
		if(lp->hnode==i && lp->tnode==j)
			return lp->value;
		lp=lp->next;
	}
//	cout<<"This is GetVal()"<<endl;
	return 0;
	
}


/*****************************************************************
			获得满足条件的集合T
*****************************************************************/
void GetT(int curr,linklist lt)
{
	linklist tp,lp;
	int i,temp;
//	cout<<"This is the begin of GetT()"<<endl;
	for(i=1;i<N;i++)
	{
		if(GetVal(curr,i)!=0)//从矩阵中获得当前坐标的数值
		{
			tp=lt->next;
			temp=0;
			while(tp!=NULL)
			{
				if(i==tp->node)
					break;
				else
					temp++;
				tp=tp->next;
			}
			if(temp==ListLen(lt))
			{
				lp=(linklist)malloc(sizeof(link));
				lp->node=i;
				InsertL(T,lp);
			}
		}
	}
//	cout<<"This is the end of GetT()"<<endl;
	//getch();
}


int Selectj(int i)
{
	linklist lt;
	paths pt;
	double temp;
	int j=-1;
	pt=Tr->next ;
	while(pt!=NULL)
	{
		if(pt->hnode==i)
		{
			lt=T->next ;
			while(lt!=NULL)
			{
				if(pt->tnode==lt->node)
				{
			//		sum+=GetA(i,lt->node);
					if(j==-1)
						temp=pt->value;
					else if(temp<pt->value)
					{
						temp=pt->value;
					}
					j=pt->tnode;
				}
				lt=lt->next;
			}
		}
		pt=pt->next;
	}
//	cout<<"This is Selectj()  j is : "<<j<<endl;
	return j;
}


void GetMin()
{
	int i,res=0;
	double temp=Max,length;
	for(i=0;i<m;i++)
	{
		if(ListLen(List[i])==N)
		{
			length=Func(List[i]);
		}
		else
			length=Max;
		if(temp>length)
		{
			temp=length;
			res=i;
		}
	}

	if(Func(List[res])<=Func(W))
	{
	//	Clear(W);
	//	W=List[res];
		ListCopy(R,W);
		ListCopy(W,List[res]);
	}
	cout<<"最新路径  :"<<endl<<endl;
	for(i=0;i<m;i++)
	{		
		OutRes(List[i]);
		Clear(List[i]);
	}
//	cout<<"This is GetMin()"<<endl;
}



double Func(linklist array)
{
	linklist lt;
	double length=0;
//	lt=array->next;
	lt=array;
	while(lt->next !=NULL)
	{
		length+=GetElem(lt->node,lt->next->node);
		lt=lt->next;
	}
//	cout<<"length :"<<length<<endl;
	return length;
}



void Reforce()
{
	linklist lt;
	paths ptr;
	int count;
	ptr=Tr;
	ptr=ptr->next;
	double length=Func(W);
	while(ptr!=NULL)
	{
		lt=W;
		count=0;
		while(lt->next!=NULL)
		{
			if(ptr->hnode==lt->node && ptr->tnode==lt->next->node)
			{
				ptr->value=(1-kp)*ptr->value+kp/length;
				break;
			}
			else
				count++;
			lt=lt->next;
		}
		if(count==ListLen(W))
		{
			ptr->value=(1-kp)*ptr->value;
		}
		ptr=ptr->next;
	}
	OutPath(Tr);
}



void OutRes(linklist array)
{
	linklist lt;
	lt=array;
	cout<<lt->node;
	lt=lt->next;
	while(lt!=NULL)
	{
		cout<<"--->"<<lt->node;
		lt=lt->next;
	}
	cout<<endl;
}


void OutPath(paths lp)
{
	paths pt;
	int i,sum=0;
	pt=lp->next;
	while(pt!=NULL)
	{
		for(i=0;i<N;i++)
		{
			if(pt!=NULL&&pt->tnode==i)
			//	cout<<"("<<pt->hnode<<","<<pt->tnode<<")   "<<pt->value<<endl;
			{
				cout<<setw(12)<<pt->value;
				pt=pt->next;
			}
			else
			//	cout<<"("<<m<<","<<i<<")   "<<0<<endl;
				cout<<setw(12)<<0;
		}
		cout<<endl;
		sum++;
		if(sum>N-1)
			break;
	}
	cout<<endl<<endl;
}