注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Bioinformatics home

 
 
 

日志

 
 

基本蚁群算法代码C版  

2011-04-18 23:09:24|  分类: algorithm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

//Basic Ant Colony Algorithm for TSP
#include <iostream.h>
#include <fstream.h>
#include <math.h>
#include <time.h>
#include <conio.h>
#include <stdlib.h>
#include <iomanip.h>

#define N 31 //city size
#define M 31 //ant number

double inittao=1; //初始信息量的多少
double tao[N][N]; //每条路径上的信息量
double detatao[N][N]; //Δτ,代表相应路径上的信息素增量
double distance[N][N]; //城市距离矩阵
double yita[N][N]; //启发函数,其值yita[i][j]=1/distance[i][j]
int tabu[M][N]; //禁忌表,tabu[i][j]=1表示蚂蚁i已经走过了j城市?
int route[M][N]; //保存蚂蚁k的路径的数组为route[k][N]
double solution[M];
int BestRoute[N];
double BestSolution=10000000000;
double alfa,beta,rou,Q; //Pijk(t)表示t时刻蚂蚁k由城市i转移到城市j的状态转移概率,
//alfa是信息启发式因子,表示轨迹的相对重要性,反映蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用,其值越大,则该蚂蚁越倾向于选择其他蚂蚁经过的路径,蚂蚁之间的协作性越强
//beta是期望启发式因子,表示能见度的相对重要性,反映在运动过程中启发信息在蚂蚁选择路径中的受重视程度,其值越大,则该状态转移概率越接近于贪心规则
//rou是信息残留因子(与书上不同,书上用rou表示信息挥发系数,而用1-rou表示信息残留因子)
//Q为信息素强度,用于计算蚂蚁留在路径上的信息量
int NcMax; //迭代次数
void initparameter(void); // initialize the parameters of basic ACA
double EvalueSolution(int *a); // evaluate the solution of TSP, and calculate the length of path
void InCityXY( double x[], double y[], char *infile ); // input the nodes' coordinates of TSP

void initparameter(void)
{
alfa=1; beta=5; rou=0.9; Q=100;
NcMax=200; //最大迭代次数
}

void main(void)
{
int NC=0;
initparameter();
double x[N];
double y[N];
InCityXY( x, y, "city31.tsp" );

//初始化距离矩阵
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];
}

// calculate the heuristic parameters:计算启发式因子
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]; //the dividend should be 1 here
yita[i][j]=1/distance[i][j];
}
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; //设置初始城市
tabu[k][route[k][0]]=1; //设置初始城市被访问标记
}
//each ant try to find the optimal path
do {
int s=1;
double partsum;
double pper;
double drand;
//ant choose one whole path
while(s<N)
{
//开始计算第k只蚂蚁的路径
for(k=0;k<M;k++)
{
int jrand=rand()%3000; //生成一个0到3000之间的随机数.
drand=jrand/3001.0; //哇这里可以加个‘.’让3000变成doube!
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);
//route[k][s-1]表示蚂蚁k第s-1步走到的城市,s==1表示蚂蚁从初始城市出发



 
//tao[route[k][s-1]][j]表示蚂蚁k经过的前一个城市到下一个没被访问的城市j的信息量
}
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) //当drand落在第j个城市上时,选择j城市
break;
}
tabu[k][j]=1; //禁忌表置访问标志
route[k][s]=j; //保存蚂蚁k的第s步经过的城市
}
s++;
}
//在N次循环后,所有蚂蚁的禁忌表都已填满

//计算每个蚂蚁走过的路径的长度,并找到最短路径保存,记录此路径并更改信息素。
// the pheromone is updated
for(i=0;i<N;i++)
for(int j=0;j<N;j++)
detatao[i][j]=0;

//计算每个蚂蚁经过路径的长度,保存到当前代为止最好的解路径及其长度
for(k=0;k<M;k++)
{
solution[k]=EvalueSolution(route[k]); //蚂蚁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) //信息素上界,避免94行和101行中,启发信息被路径信息淹没
tao[i][j]=20;
}

//将蚂蚁的路径再重新置空,为下一次循环做准备,要不然每个蚂蚁的路径都已经满了,则没有办法进行下一次迭代了.
for(k=0;k<M;k++)
for(int j=1;j<N;j++) //注意起始城市,即j=0没有被清空
{
tabu[k][route[k][j]]=0;
route[k][j]=-1;
}
NC++;
} while(NC<NcMax);
//output the calculating results
fstream result;
result.open("optimal_results.log", ios::app);
if(!result)
{
cout<<"can't open the <optimal_results.log> file!\n";
exit(0);
}
result<<"*-------------------------------------------------------------------------*"<<endl;
result<<"the initialized parameters of ACA are as follows:"<<endl;
result<<"alfa="<<alfa<<", beta="<<beta<<", rou="<<rou<<", Q="<<Q<<endl;
result<<"the maximum iteration number of ACA is:"<<NcMax<<endl;
result<<"the shortest length of the path is:"<<BestSolution<<endl;
result<<"the best route is:"<<endl;
for(i=0;i<N;i++)
result<<BestRoute[i]<<" ";
result<<endl;
result<<"*-------------------------------------------------------------------------*"<<endl<<endl;
result.close();
cout<<"the shortest length of the path is:"<<BestSolution<<endl;
}


double EvalueSolution(int *a)
{
double dist=0;
for(int i=0;i<N-1;i++)
dist+=distance[a[i]][a[i+1]];
dist+=distance[a[i]][a[0]];
return dist;
}


void InCityXY( double x[], double y[], char *infile )
{
fstream inxyfile( infile, ios::in | ios::nocreate );
if( !inxyfile )
{
cout<<"can't open the <"<<infile<<"> file!\n";
exit(0);
}
int i=0;
while( !inxyfile.eof() )
{
inxyfile>>x[i]>>y[i];
if( ++i >= N ) break;
}
}

/*31个城市坐标:
1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
3238 1229
4196 1004
4312 790
4386 570
3007 1970
2562 1756
2788 1491
2381 1676
1332 695
3715 1678
3918 2179
4061 2370
3780 2212
3676 2578
4029 2838
4263 2931
3429 1908
3507 2367
3394 2643
3439 3201
2935 3240
3140 3550
2545 2357
2778 2826
2370 2975
运行后可得到15602的巡游路径*/
  评论这张
 
阅读(2451)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017