ant.cpp

简单实现蚁群算法的程序 vc++调试通过

// ant.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream.h>
#include<fstream.h>
#include<math.h>
#include<time.h>
#include<conio.h>
#include<stdlib.h>，
#include<iomanip.h>
#define N 30
#define M 30
double initao=1;
double tao[N][N];
double detatao[N][N];
double distance[N][N];
double yita[N][N];
int tabu[M][N];
int route[M][N];
double solution[M];
int bestroute[N];
double BestSolution=500000;
double alfa,beta,rou,Q;
int NcMax;
void initparameter();		//初始参数输入
double EvalueSolution(int *a);  ///解的评价，计算寻找到的路径的长度
void inCityXY(double x[],double y[]) ;//结点坐标输入
int t1,t2;
void main()
{
	int NC=0;
	initparameter();
	double x[N];
	double y[N];
	inCityXY(x,y);
	for(int i=0;i<N;i++)
		for(int j=i+1;j<N;j++){
		distance[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			distance[i][j]=distance[j][i];
		}
//自启发里的计算
	for(i=0;i<N;i++)
		for(int j=0;j<N;j++){
			tao[i][j]=initao;
				if(j!=i)
			yita[i][j]=100/(distance[i][j]+50-int(distance[i][j])%50);
		}
		for(int k=0;k<M;k++)
			for(i=0;i<N;i++)
			route[k][i]=-1;
			srand(time(NULL));
		for(k=0;k<M;k++){
			route[k][0]=(k+N)%N;
			tabu[k][route[k][0]]=1;
			}
//每个蚂蚁单独寻找路径
		do{
			int s=1;
			double partsum;
			double pper;
			double drand;
//蚂蚁选择一条路径，直到完成
		while(s<N){
			for(int k=0;k<M;k++){
				int jrand=rand()% 3000;
				drand=double(jrand)/3001;
				partsum=0; pper=0;
			for(int j=0;j<N;j++){
				if(tabu[k][j]=0)
	partsum+=pow(tao[route[k][s-1 ]][j],alfa)*pow(yita[route[k][s-1 ]][j],beta);
		}
		for(j=0;j<N;j++){
		if(tabu[k][j]==0)
	pper+=pow(tao[route[k][s-1]][j],alfa)*pow(yita[route[k][s-1]][j],beta)/partsum;
	if(pper>drand) break;
	}
		tabu[k][j]=1; route[k][s]=j;
	}
		s++;
	}
	//蚂蚁走完一条路径后轨迹浓度的更新
	for(i=0;i<N;i++)
		for(int j=0;j<N;j++){
			detatao[i][j]=0;
		}
	for(int k=0;k<M;k++){	
		solution[k]=EvalueSolution(route[k]);
	}
	for(k=1;k<M;k++)
		if(solution[k]<BestSolution){
		BestSolution=solution[k];
	for(s=0;s<N;s++) bestroute[s]=route[k][s];
	}
	for(k=0;k<M;k++){
		for(s=0;s<N-1;s++)
	detatao[route[k][s]][route[k][s+1]]+=Q/solution[k];
	detatao[route[k][N-1]][route[k][0]]+=Q/solution[k];
	}
	for(i=0;i<N;i++)
		for(int j=0;j<N;j++)
	{	tao[i][j]=rou*tao[i][j]+detatao[i][j];
		if(tao[i][j]<0.00001)tao[i][j]=0.00001;
		if(tao[i][j]>20) tao[i][j]=20;
		}
//一次循环后的蚂蚁性质的更新
	for(k=0;k<M;k++)
		for(int j=1;j<N;j++)
	{tabu[k][route[k][j]]=0; route[k][j]=-1;}
	NC++;
	}while(NC<NcMax);
	//结果输出
	fstream result;
	result.open("优化结果.dat",ios::app);
	if(!result)
	{cout<<"不能打开文件\n";
	abort();
	}
	result<<"*****************************"<<endl;
	result<<"算法参数如下:"<<endl;
	result<<"alfa="<<alfa<<",beta="<<beta<<endl;
	result<<"Q="<<Q<<",最大循环次数为"<<NcMax<<endl;
	result<<"挥发悉数为"<<rou<<endl;
	result<<"****************************"<<endl;
	for(i=0;i<N;i++)
		result<<bestroute[i]<<",";
	result<<endl;
	result.close();
	}
	double EvalueSolution(int *a){
	double dist=0;
	for(int i=0;i<N;i++)
		 t1=int(a+(i+N)%N);
		 t2=int(a+(i+N+1)%N);
	dist=dist+distance[t1][t2];
	return dist;
	}
	void InCityXY(double x[],double y[])
	{
	fstream inxyftle;
	inxyftle.open("城市坐标数据.dat",ios::in);
	if(!inxyftle){
	cout<<"不能打开文件\n";
	abort();
	}
	char ch1,ch2;
	while(! inxyftle.eof())
	{
	inxyftle.get(ch1);
	if(ch1=='{') break;
	}
	int i=0,j=0;
	x[0]=y[0]=0;
	while(!inxyftle.eof()){
	inxyftle.get(ch1);
	if(ch1>='0'&&ch1<='9'){
		ch2=ch1;
	while(ch2>='0'&&ch2<='9'){
	switch(i)
	{	case 0: break;
	case 1: x[j]=x[j]*10+(double(ch2)-48);break;
	case 2: y[j]=y[j]*10+(double(ch2)-48);break;
	}
	inxyftle.get(ch2);	
	}
	i=(++i)%3;
if(i==0&&j<N-1)
{
	j++;
	x[j]=0;y[j]=0;
}
}
}
}