📄 ant_system_alogrithm.cpp
字号:
// Ant_System_Alogrithm.cpp: implementation of the CAnt_System_Alogrithm class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "ASA.h"
#include "stdlib.h"
#include "stdio.h"
#include "math.h"
#include "Ant_System_Alogrithm.h"
#include "GamblingPad.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CAnt_System_Alogrithm::CAnt_System_Alogrithm()
{
}
//功能：初始化环境和蚁群信息
void CAnt_System_Alogrithm::init()
{
FILE *fp;
if((fp=fopen("el51.txt","r"))==NULL)
{
::AfxMessageBox("cannot open kroa100 file");
exit(0);
}
int i,j,x,y;
for(j=0; j<CITY_NUM; j++)
{
fscanf(fp,"%d%d%d",&i,&x,&y);
citypos[i-1].x=x;
citypos[i-1].y=y;
}
fclose(fp);
//初始化城市距离dis_city[i][j]，η[i][j],г[i][j]
for(i=0; i<CITY_NUM-1; i++)
{
dis_city[i][i] = 0;
yita[i][i]=1;
tao[i][i]=C+0.5;
for(j=i+1; j<CITY_NUM; j++)
{
dis_city[i][j] =(int)( sqrt( pow(citypos[i].x-citypos[j].x,2 )
+pow(citypos[i].y-citypos[j].y, 2) ) +0.5
);
dis_city[j][i] =dis_city[i][j];
yita[i][j]=yita[j][i]=1.0/dis_city[i][j];
tao [i][j]=tao [j][i]=C+0.5;
}
}
//初始化每只蚂蚁信息
::srand( (unsigned)time( NULL ) );
for (i=0; i<ANT_NUM; i++)
{
Ant[i].len=0; //当前累积长度为0
Ant[i].tailpos=0; //路径末尾指示器为0
Ant[i].curpos = rand()%CITY_NUM; //当前位置随机设定
//路径信息为空，所有顶点都未访问
for (j=0; j<CITY_NUM+1; j++)
{
Ant[i].path[j]=-1;
Ant[i].flag[j]=FALSE;
}
//将当前位置加入路径信息
Ant[i].path[Ant[i].tailpos++]=Ant[i].curpos;
Ant[i].flag[Ant[i].curpos]=TRUE;
}
bestresult.len=999999; //初始化最优解长度
}
//功能：执行蚁群算法
void CAnt_System_Alogrithm::run()
{
int i,k;
int nc;
int minlen=10000000;
int NOofbestAnt =0;
//反复执行NCMAX次训练
for (nc=0; nc<NCMAX+50; nc++)
{
//每只蚂蚁都遍历城市一遍
for (k=0; k<ANT_NUM; k++)
{
findPath(k);
if (Ant[k].len<minlen)
{
minlen=Ant[k].len;
NOofbestAnt=k;
}
}
//与最优解比较，更新最优解
if (Ant[NOofbestAnt].len<bestresult.len) bestresult=Ant[NOofbestAnt];
//更新信息素
updateTao();
//初始化每只蚂蚁的信息，准备下一次循环
for (k=0; k<ANT_NUM; k++)
{
Ant[k].len=0; //当前累积长度为0
Ant[k].tailpos=0; //路径末尾指示器为0
//Ant[k].curpos = rand()%CITY_NUM; //当前位置随机设定
for (i=0; i<CITY_NUM; i++) //访问标志清空
Ant[k].flag[i]=FALSE;
//将当前位置加入路径信息
Ant[k].path[Ant[k].tailpos++]=Ant[k].curpos;
Ant[k].flag[Ant[k].curpos]=TRUE;
}
}//end of for (nc=0; nc<NCMAX; nc++)
}
void CAnt_System_Alogrithm::updateTao()
{
int i,j,k;
double temp;
double tempdeltatao[ANT_NUM][CITY_NUM][CITY_NUM];
double deltatao[CITY_NUM][CITY_NUM];
//初始化tempdeltatao[k][i][j]
for (k=0; k<ANT_NUM; k++)
for (i=0; i<CITY_NUM; i++)
for (j=0; j<CITY_NUM; j++)
tempdeltatao[k][i][j]=0;
//初始化deltatao[i][j]
for (i=0; i<CITY_NUM; i++)
for (j=0; j<CITY_NUM; j++)
deltatao[i][j]=0;
//计算tempdeltatao[k][i][j]
for (k=0; k<ANT_NUM; k++)
{
for (int cnt=0; cnt<Ant[k].tailpos; cnt++)
{
temp=tempdeltatao[k][ Ant[k].path[cnt] ][ Ant[k].path[cnt+1] ]=Q/Ant[k].len;
tempdeltatao[k][ Ant[k].path[cnt+1] ][ Ant[k].path[cnt] ]=temp;
}
}
//计算delta г[i][j]
for (i=0; i<CITY_NUM; i++)
for (j=0; j<CITY_NUM; j++)
for (k=0; k<ANT_NUM; k++)
deltatao[i][j]+=tempdeltatao[k][i][j];
//更新г[i][j]
for (i=0; i<CITY_NUM; i++)
for (j=0; j<CITY_NUM; j++)
tao[i][j]=ROU*tao[i][j]+(1-ROU)*deltatao[i][j];
}
//功能：对第k只蚂蚁所得路径进行二次交叉
void CAnt_System_Alogrithm::intercross(int k)
{
int i=1;
int j=1;
int temp;
//随机生成位置i,j
while(TRUE)
{
i=rand()%(CITY_NUM-2)+1;
j=rand()%(CITY_NUM-2)+1;
if (i>j)
{
temp=i;i=j;j=temp;
}
if (i+2<=j) break;
}
int formerlen,latterlen;
formerlen = dis_city[Ant[k].path[i-1]][Ant[k].path[i]]+dis_city[Ant[k].path[i]][Ant[k].path[i+1]]
+dis_city[Ant[k].path[j-1]][Ant[k].path[j]]+dis_city[Ant[k].path[j]][Ant[k].path[j+1]];
latterlen = dis_city[Ant[k].path[i-1]][Ant[k].path[j]]+dis_city[Ant[k].path[j]][Ant[k].path[i+1]]
+dis_city[Ant[k].path[j-1]][Ant[k].path[i]]+dis_city[Ant[k].path[i]][Ant[k].path[j+1]];
if (latterlen<formerlen)
{
Ant[k].len=Ant[k].len-formerlen+latterlen;
temp=Ant[k].path[i];
Ant[k].path[i]=Ant[k].path[j];
Ant[k].path[j]=temp;
}
}
//功能：第i只蚂蚁遍历CITY_NUM个城市得到一条路径
void CAnt_System_Alogrithm::findPath(int i)
{
GamblingPad gmbpad;//将转移概率放入赌盘
int j; //记录下一个城市的序号
for (int cnt=0; cnt<CITY_NUM-1; cnt++)//循环CITY_NUM-1次
{
getTransferProbability(i,gmbpad);
j = gmbpad.getCity(); //用赌盘法计算下一个城市
//更新蚂蚁路径信息
Ant[i].flag[j] =TRUE; //标记为已访问过的城市
Ant[i].len += dis_city[Ant[i].curpos][j]; //累积走过的路径长度
Ant[i].curpos =j; //当前位置移到j城市
Ant[i].path[Ant[i].tailpos++]=j; //将城市序号j纳入蚂蚁路径
gmbpad.citycnt=0;
gmbpad.type=gmbpad.YUANSHIPRO;
}
//蚂蚁的最后一步是回到原点
Ant[i].path[Ant[i].tailpos] = Ant[i].path[0];
Ant[i].len += dis_city[Ant[i].curpos][Ant[i].path[0]];
Ant[i].curpos =Ant[i].path[0];
//对所得路径进行二次交叉
intercross(i);
}
//功能：计算第i只蚂蚁从当前位置到其余未访问节点的转移概率，结果放入赌盘
void CAnt_System_Alogrithm::getTransferProbability(int i,GamblingPad& gmbpad)
{
int j;
double total_tao_yita=0;
double tao_yita[CITY_NUM];
for (j=0; j<CITY_NUM; j++)
{
if (Ant[i].flag[j]==FALSE/*表示未访问过*/)
{
tao_yita[gmbpad.citycnt] = tao[Ant[i].curpos][j]
*pow(yita[Ant[i].curpos][j],BETA);
total_tao_yita += tao_yita[gmbpad.citycnt];
gmbpad.city[gmbpad.citycnt]=j; //记录城市序号
gmbpad.citycnt++; //城市数加一
}
}
for (j=0; j<gmbpad.citycnt; j++)
gmbpad.pr[j]=tao_yita[j]/total_tao_yita;//得到去每个未访问城市的转移概率
}
//功能：显示结果
void CAnt_System_Alogrithm::displayResult(CDC* pDC)
{
CString str;
CPoint point(100,60);
str.Format("最优长度＝%d",bestresult.len);
pDC->TextOut(0,0,str);
pDC->TextOut(0,30,"路径序列：");
pDC->MoveTo(citypos[bestresult.path[0]].x*5,citypos[bestresult.path[0]].y*5);
for (int i=0; i<=bestresult.tailpos; i++)
{
pDC->LineTo(citypos[bestresult.path[i]].x*5,citypos[bestresult.path[i]].y*5);
point.x =100 + (i%10)*50; point.y = 60 + (i/10)*30;
str.Format("%d",bestresult.path[i]);
pDC->TextOut(point.x,point.y,str);
}
}
CAnt_System_Alogrithm::~CAnt_System_Alogrithm()
{
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -