ant.cpp

来自「蚂蚁算法解TSP问题 为华中科技大学硕士毕业论文原代码。」· C++ 代码 · 共 165 行

#include "iostream.h"
#include "fstream.h"
#include "math.h"
#include "conio.h"
#include "stdlib.h"
#include "time.h"
#include "iomanip.h"
#define N 30
#define M 30
double inittao=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[]);//结点坐标输入

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]=inittao;
       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++)
dist+=distance[*(a+(i+N)%N)][*(a+(i+N+1)%N)];
return dist;}
void InCityXY(double x[],double y[]){
fstream inxyfile;
inxyfile.open("城市坐标数据.dat",ios::in);
if(!inxyfile){
cout<<"不能打开文件\n";
abort();
}
char ch1,ch2;
while(!inxyfile.eof()){
inxyfile.get(ch1);
if(ch1=='{') break;
}
int i=0,j=0;
x[0]=y[0]=0;
while(!inxyfile.eof()){
inxyfile.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;
}
inxyfile.get(ch2);
}
i=(++i)%3;
if(i==0&&j<N-1){
j++;
x[j]=0;y[j]=0;
}
}
}
}