?? 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 + -