anttsp.cpp

tsp问题的蚂蚁算法

#include <fstream.h>
#include <iomanip.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
//------------------------------
#define nAntNum 5
#define alpha   2
#define beta    3
#define fDisPara 0.75
#define fConst   0.01
#define fPara    1.0
#define nNodeNum 8
//------------------------------
void main()
{
	int i,j,n,k,nIte,nIndex,nTemp;
	float fDistMatrix[nNodeNum][nNodeNum];
	float fProbit[nAntNum][nNodeNum], fInfo[nNodeNum][nNodeNum], fInfoDelt[nNodeNum][nNodeNum];
	float fTemp, fRandom;
	int nTabuList[nAntNum][nNodeNum],nRoadBest[nNodeNum];
	int nPathList[nAntNum][nNodeNum],nRoadList[nAntNum][nNodeNum];
	float fRoadCost[nAntNum], fCostTemp[nAntNum], fBestCost;
	fstream inputdata("data.txt",ios::in);
	for(i = 0; i < nNodeNum; i++)
		for(j = 0; j < nNodeNum; j++)
			inputdata >> fDistMatrix[i][j];
	inputdata.close();
	fstream outputdata("result.txt",ios::out);
	for(i = 0; i < nNodeNum; i++)
		for(j = 0; j < nNodeNum; j++)
		{
			fInfo[i][j] = float(fConst);
			fInfoDelt[i][j] = 0.0;
		}
	nIte = 1;
	fBestCost = 99999.0;
	srand((unsigned)time(NULL));
	for(k = 0; k < nAntNum; k++)//确定出发点
	{
		fRoadCost[k] = 99999.0;
		nTemp = int(float(rand())/32768.0 * 7.0);///????????????????????
		for(nIndex = 0; nIndex < nNodeNum; nIndex++)
			if(nIndex == nTemp)	
				nPathList[k][0] = nTemp; //记录路径起始点,保持不变
			else				
				nPathList[k][nIndex] = nNodeNum;
	}
	do
	{
		for(k = 0; k < nAntNum; k++)//禁忌表
		{
			for(nIndex = 0; nIndex < nNodeNum; nIndex++)
				if(nIndex == nPathList[k][0])
					nTabuList[k][nIndex] = 1;//被禁忌
				else
					nTabuList[k][nIndex] = 0;//未被禁忌
			for(nIndex = 1; nIndex < nNodeNum; nIndex++)//0初始点已经确定
				nPathList[k][nIndex] = nNodeNum;
		}
		for(nIndex = 1; nIndex < nNodeNum; nIndex++)//nIndex节点计数器,nPathList为当前迭代路径,nRoadList为当前个体最好的路径
		{
			for(k = 0; k < nAntNum; k++)
			{
				fTemp = 0.0;
				for(n = 0; n < nNodeNum; n++)//计算转移概率
				{
					if(!nTabuList[k][n])//未被禁忌的结点,nPathList[k][nIndex - 1]为禁忌点
						fProbit[k][n] = float(pow(fInfo[nPathList[k][nIndex - 1]][n], alpha) 
											* pow(1.0/fDistMatrix[nPathList[k][nIndex - 1]][n], beta));
					else fProbit[k][n]=0.0;
					fTemp += fProbit[k][n];
				}
				for(n = 0; n < nNodeNum; n++)
					fProbit[k][n] = fProbit[k][n]/fTemp;
				fTemp = 0.0;
				for(n = 0; n < nNodeNum; n++)//计算轮盘,逐步递增
					if(fProbit[k][n])	{	fProbit[k][n] += fTemp;	fTemp = fProbit[k][n];	}
				fRandom = float((rand() + 1)) / float(32770.0);///////??????????????????/
				if(fProbit[k][n]>=1||fProbit[k][n]<=0) outputdata << setw(6) << "dsg";

				for(n = 0; n < nNodeNum; n++)//随机选择未被禁忌的节点
					if(!nTabuList[k][n])
						if(n == 0 &&  fRandom <= fProbit[k][0])
							{	nTabuList[k][0] = 1;	nPathList[k][nIndex] = 0;	break;	}
						else
							if(fRandom > fProbit[k][n - 1] && fRandom <= fProbit[k][n])
							{	nTabuList[k][n] = 1;	nPathList[k][nIndex] = n;	break;	}
			}
		}
		for(k = 0; k < nAntNum; k++)//计算环路费用
		{
			fCostTemp[k] = 0;
			for(nIndex = 0; nIndex < nNodeNum - 1; nIndex++)
				fCostTemp[k] += fDistMatrix[nPathList[k][nIndex]][nPathList[k][nIndex + 1]];
			fCostTemp[k] += fDistMatrix[nPathList[k][nNodeNum - 1]][nPathList[k][0]];
			if(fCostTemp[k] < fRoadCost[k])//求解自适应个体当前最好解
			{
				fRoadCost[k] = fCostTemp[k];
				for(n = 0; n < nNodeNum; n++)
					nRoadList[k][n] = nPathList[k][n];
			}
			if(fBestCost > fRoadCost[k])//记录整体最好解
			{
				fBestCost = fRoadCost[k];
				for(n = 0; n < nNodeNum; n++)
					nRoadBest[n] = nRoadList[k][n];
			}
		}
		for(k = 0; k < nAntNum; k++)//信息更新
		{
			for(n = 0; n < nNodeNum - 1; n++)
				fInfoDelt[nPathList[k][n]][nPathList[k][n+1]] += float(fPara/fCostTemp[k]);
			fInfoDelt[nPathList[k][n]][nPathList[k][0]] = float(fPara/fCostTemp[k]);
		}
		for(i = 0; i < nNodeNum; i++)
			for(j = 0; j < nNodeNum; j++)
			{
				fInfo[i][j] += float(fInfo[i][j] * fDisPara + fInfoDelt[i][j]);
				fInfoDelt[i][j] = 0;
			}
		for(n = 0; n < nAntNum; n++)
		{	outputdata << setw(6) << fCostTemp[n];		}

		    outputdata << setw(6) << fBestCost << setw(15) << fProbit[0][0]<< endl;

	}while(nIte++ < 1000);
	outputdata << "优化最好解" << fBestCost << endl;
	for(n = 0; n < nNodeNum; n++)
	outputdata << setw(6) << nRoadBest[n] + 1;
	  
	outputdata << endl;
	return;
}