蟻群算法
今天雨下的不小，無事可幹，來研究研究蟻群算法。
蟻群優化算法概述
蟻群優化算法(Ant Colony Optimization，ACO)起源于對簡單螞蟻社會系統的模拟，是對螞蟻群落食物采集過程的模拟，是一種群智能算法。目前，螞蟻算法因其較強的魯棒性，并行性，分布式計算機制，易于實作等特點，已在組合優化、網絡路由、函數優化、資料挖掘、機器人路徑規劃、無線傳感器網絡性能優化等領域得到廣泛的應用。
蟻群算法的生物學背景
蟻群優化(ACO)算法其靈感來源于真實蟻群的覓食行為(foraging)，也就是螞蟻怎樣找到食物源與自己的巢穴之間的最短路徑。螞蟻沒有視力，它在蟻群與食物源之間建立起最短的路徑，并且傳回，其個體之間資訊通信的媒介就是資訊素。初始的時候，螞蟻按照随機的方式在自己的巢穴周圍找尋食物。一旦一隻螞蟻找到食物，它會估計食物的數量和品質并且帶一些食物回巢穴。在傳回巢穴期間，這隻螞蟻留在路徑上的“資訊素”(Pheromone)的數量與其所攜帶的食物的數量和品質有關。一隻孤立的螞蟻的基本移動是随機的，螞蟻如果檢測到路徑上有前面螞蟻遺留下的資訊素，那麼螞蟻會選擇資訊素濃度高的路徑行走，同時也用自己的資訊素加強了所選擇路徑上的資訊素濃度。這種集體行為表現的是一種叫做autocatalytic(自身催化)的行為，即越多的螞蟻追尋一條資訊素，這條資訊素對後續的螞蟻就越有吸引力。”資訊素”作為蟻群前往食物所在地的标記也會逐漸揮發，如果2
隻螞蟻同時找到同一食物，又采取不同路線回到巢中，那麼比較繞遠的一條路上資訊素的氣味會比較淡，後續的螞蟻在選擇路徑的時候會傾向于選擇資訊素濃度較高的路徑。而這一過程就是螞蟻之間通過資訊素所進行的間接通信，即stigmergy。螞蟻通過這種方式能夠找到巢穴與食物源之間的最短路徑。
蟻群算法解決TSP問題
在解決組合優化問題，如TSP 問題時，ACO 算法設計虛拟的"螞蟻"将搜尋不同路線，并留下會随時間逐漸消失的虛拟"資訊素"。虛拟的"資訊素"也會揮發，每隻螞蟻每次随機選擇要走的路徑，它們傾向于選擇路徑比較短的、資訊素比較濃的路徑。根據“資訊素較濃的路線更近”的原則，即可選擇出最佳路線。由于這個算法利用了正回報機制，使得較短的路徑能夠有較大的機會得到選擇，并且由于采用了機率算法，是以它能夠不局限于局部最優解。
通常，ACO 算法通過兩個疊代步驟解決優化問題：
(1) 用資訊素模型建構候選解 即，在解空間中參數化機率分布；
(2) 用候選解來修正資訊素的值 其前提是朝着獲得高品質解的方向進行采樣。
每一隻螞蟻就是一個主體(agent)，它具有以下特性：其所選擇城市的機率是城市間距離與連線上遺留資訊量的函數；不允許螞蟻向已經通路過的城市轉移，直到整個旅行結束，該過程由禁忌表控制；當其完成一次旅行之後，螞蟻在經過的邊(i, j)上放置資訊素。
令 ζ (t) ij τ 為連線(i, j)上資訊素的濃度。資訊素濃度根據下式更新：
k指螞蟻的序号
#pragma once
#include <iostream>
#include <math.h>
#include <time.h>
const double ALPHA=1.0; //啟發因子，資訊素的重要程度
const double BETA=2.0; //期望因子，城市間距離的重要程度
const double ROU=0.5; //資訊素殘留參數
const int N_ANT_COUNT=34; //螞蟻數量
const int N_IT_COUNT=1000; //疊代次數
const int N_CITY_COUNT=51; //城市數量
const double DBQ=100.0; //總的資訊素
const double DB_MAX=10e9; //一個标志數，10的9次方
double g_Trial[N_CITY_COUNT][N_CITY_COUNT]; //兩兩城市間資訊素，就是環境資訊素
double g_Distance[N_CITY_COUNT][N_CITY_COUNT]; //兩兩城市間距離
//eil51.tsp城市坐标資料
double x_Ary[N_CITY_COUNT]=
{
37,49,52,20,40,21,17,31,52,51,
42,31,5,12,36,52,27,17,13,57,
62,42,16,8,7,27,30,43,58,58,
37,38,46,61,62,63,32,45,59,5,
10,21,5,30,39,32,25,25,48,56,
30
};
double y_Ary[N_CITY_COUNT]=
{
52,49,64,26,30,47,63,62,33,21,
41,32,25,42,16,41,23,33,13,58,
42,57,57,52,38,68,48,67,48,27,
69,46,10,33,63,69,22,35,15,6,
17,10,64,15,10,39,32,55,28,37,
40
};
//傳回指定範圍内的随機整數
int rnd(int nLow,int nUpper)
{
return nLow+(nUpper-nLow)*rand()/(RAND_MAX+1);
}
//傳回指定範圍内的随機浮點數
double rnd(double dbLow,double dbUpper)
{
double dbTemp=rand()/((double)RAND_MAX+1.0);
return dbLow+dbTemp*(dbUpper-dbLow);
}
//傳回浮點數四舍五入取整後的浮點數
double ROUND(double dbA)
{
return (double)((int)(dbA+0.5));
}
//定義螞蟻類
class CAnt
{
public:
CAnt(void);
~CAnt(void);
public:
int m_nPath[N_CITY_COUNT]; //螞蟻走的路徑
double m_dbPathLength; //螞蟻走過的路徑長度
int m_nAllowedCity[N_CITY_COUNT]; //沒去過的城市
int m_nCurCityNo; //目前所在城市編号
int m_nMovedCityCount; //已經去過的城市數量
public:
int ChooseNextCity(); //選擇下一個城市
void Init(); //初始化
void Move(); //螞蟻在城市間移動
void Search(); //搜尋路徑
void CalPathLength(); //計算螞蟻走過的路徑長度
};
//構造函數
CAnt::CAnt(void)
{
}
//析構函數
CAnt::~CAnt(void)
{
}
//初始化函數，螞蟻搜尋前調用
void CAnt::Init()
{
for (int i=0;i<N_CITY_COUNT;i++)
{
m_nAllowedCity[i]=1; //設定全部城市為沒有去過
m_nPath[i]=0; //螞蟻走的路徑全部設定為0
}
//螞蟻走過的路徑長度設定為0
m_dbPathLength=0.0;
//随機選擇一個出發城市
m_nCurCityNo=rnd(0,N_CITY_COUNT);
//把出發城市儲存入路徑數組中
m_nPath[0]=m_nCurCityNo;
//辨別出發城市為已經去過了
m_nAllowedCity[m_nCurCityNo]=0;
//已經去過的城市數量設定為1
m_nMovedCityCount=1;
}
//選擇下一個城市
//傳回值 為城市編号
int CAnt::ChooseNextCity()
{
int nSelectedCity=-1; //傳回結果，先暫時把其設定為-1
//==============================================================================
//計算目前城市和沒去過的城市之間的資訊素總和
double dbTotal=0.0;
double prob[N_CITY_COUNT]; //儲存各個城市被選中的機率
for (int i=0;i<N_CITY_COUNT;i++)
{
if (m_nAllowedCity[i] == 1) //城市沒去過
{
prob[i]=pow(g_Trial[m_nCurCityNo][i],ALPHA)*pow(1.0/g_Distance[m_nCurCityNo][i],BETA); //該城市和目前城市間的資訊素
dbTotal=dbTotal+prob[i]; //累加資訊素，得到總和
}
else //如果城市去過了，則其被選中的機率值為0
{
prob[i]=0.0;
}
}
//==============================================================================
//進行輪盤選擇
double dbTemp=0.0;
if (dbTotal > 0.0) //總的資訊素值大于0
{
dbTemp=rnd(0.0,dbTotal); //取一個随機數
for (int i=0;i<N_CITY_COUNT;i++)
{
if (m_nAllowedCity[i] == 1) //城市沒去過
{
dbTemp=dbTemp-prob[i]; //這個操作相當于轉動輪盤，如果對輪盤選擇不熟悉，仔細考慮一下
if (dbTemp < 0.0) //輪盤停止轉動，記下城市編号，直接跳出循環
{
nSelectedCity=i;
break;
}
}
}
}
//==============================================================================
//如果城市間的資訊素非常小 ( 小到比double能夠表示的最小的數字還要小 )
//那麼由于浮點運算的誤差原因，上面計算的機率總和可能為0
//會出現經過上述操作，沒有城市被選擇出來
//出現這種情況，就把第一個沒去過的城市作為傳回結果
//題外話：剛開始看的時候，下面這段代碼困惑了我很長時間，想不通為何要有這段代碼，後來才搞清楚。
if (nSelectedCity == -1)
{
for (int i=0;i<N_CITY_COUNT;i++)
{
if (m_nAllowedCity[i] == 1) //城市沒去過
{
nSelectedCity=i;
break;
}
}
}
//==============================================================================
//傳回結果，就是城市的編号
return nSelectedCity;
}
//螞蟻在城市間移動
void CAnt::Move()
{
int nCityNo=ChooseNextCity(); //選擇下一個城市
m_nPath[m_nMovedCityCount]=nCityNo; //儲存螞蟻走的路徑
m_nAllowedCity[nCityNo]=0;//把這個城市設定成已經去過了
m_nCurCityNo=nCityNo; //改變目前所在城市為選擇的城市
m_nMovedCityCount++; //已經去過的城市數量加1
}
//螞蟻進行搜尋一次
void CAnt::Search()
{
Init(); //螞蟻搜尋前，先初始化
//如果螞蟻去過的城市數量小于城市數量，就繼續移動
while (m_nMovedCityCount < N_CITY_COUNT)
{
Move();
}
//完成搜尋後計算走過的路徑長度
CalPathLength();
}
//計算螞蟻走過的路徑長度
void CAnt::CalPathLength()
{
m_dbPathLength=0.0; //先把路徑長度置0
int m=0;
int n=0;
for (int i=1;i<N_CITY_COUNT;i++)
{
m=m_nPath[i];
n=m_nPath[i-1];
m_dbPathLength=m_dbPathLength+g_Distance[m][n];
}
//加上從最後城市傳回出發城市的距離
n=m_nPath[0];
m_dbPathLength=m_dbPathLength+g_Distance[m][n];
}
//tsp類
class CTsp
{
public:
CTsp(void);
~CTsp(void);
public:
CAnt m_cAntAry[N_ANT_COUNT]; //螞蟻數組
CAnt m_cBestAnt; //定義一個螞蟻變量，用來儲存搜尋過程中的最優結果
//該螞蟻不參與搜尋，隻是用來儲存最優結果
public:
//初始化資料
void InitData();
//開始搜尋
void Search();
//更新環境資訊素
void UpdateTrial();
};
//構造函數
CTsp::CTsp(void)
{
}
CTsp::~CTsp(void)
{
}
//初始化資料
void CTsp::InitData()
{
//先把最優螞蟻的路徑長度設定成一個很大的值
m_cBestAnt.m_dbPathLength=DB_MAX;
//計算兩兩城市間距離
double dbTemp=0.0;
for (int i=0;i<N_CITY_COUNT;i++)
{
for (int j=0;j<N_CITY_COUNT;j++)
{
dbTemp=(x_Ary[i]-x_Ary[j])*(x_Ary[i]-x_Ary[j])+(y_Ary[i]-y_Ary[j])*(y_Ary[i]-y_Ary[j]);
dbTemp=pow(dbTemp,0.5);
g_Distance[i][j]=ROUND(dbTemp);
}
}
//初始化環境資訊素，先把城市間的資訊素設定成一樣
//這裡設定成1.0，設定成多少對結果影響不是太大，對算法收斂速度有些影響
for (int i=0;i<N_CITY_COUNT;i++)
{
for (int j=0;j<N_CITY_COUNT;j++)
{
g_Trial[i][j]=1.0;
}
}
}
//更新環境資訊素
void CTsp::UpdateTrial()
{
//臨時數組，儲存各隻螞蟻在兩兩城市間新留下的資訊素
double dbTempAry[N_CITY_COUNT][N_CITY_COUNT];
memset(dbTempAry,0,sizeof(dbTempAry)); //先全部設定為0
//計算新增加的資訊素,儲存到臨時數組裡
int m=0;
int n=0;
for (int i=0;i<N_ANT_COUNT;i++) //計算每隻螞蟻留下的資訊素
{
for (int j=1;j<N_CITY_COUNT;j++)
{
m=m_cAntAry[i].m_nPath[j];
n=m_cAntAry[i].m_nPath[j-1];
dbTempAry[n][m]=dbTempAry[n][m]+DBQ/m_cAntAry[i].m_dbPathLength;
dbTempAry[m][n]=dbTempAry[n][m];
}
//最後城市和開始城市之間的資訊素
n=m_cAntAry[i].m_nPath[0];
dbTempAry[n][m]=dbTempAry[n][m]+DBQ/m_cAntAry[i].m_dbPathLength;
dbTempAry[m][n]=dbTempAry[n][m];
}
//==================================================================
//更新環境資訊素
for (int i=0;i<N_CITY_COUNT;i++)
{
for (int j=0;j<N_CITY_COUNT;j++)
{
g_Trial[i][j]=g_Trial[i][j]*ROU+dbTempAry[i][j]; //最新的環境資訊素 = 留存的資訊素 + 新留下的資訊素
}
}
}
void CTsp::Search()
{
char cBuf[256]; //列印資訊用
//在疊代次數内進行循環
for (int i=0;i<N_IT_COUNT;i++)
{
//每隻螞蟻搜尋一遍
for (int j=0;j<N_ANT_COUNT;j++)
{
m_cAntAry[j].Search();
}
//儲存最佳結果
for (int j=0;j<N_ANT_COUNT;j++)
{
if (m_cAntAry[j].m_dbPathLength < m_cBestAnt.m_dbPathLength)
{
m_cBestAnt=m_cAntAry[j];
}
}
//更新環境資訊素
UpdateTrial();
//輸出目前為止找到的最優路徑的長度
sprintf(cBuf,"\n[%d] %.0f",i+1,m_cBestAnt.m_dbPathLength);
printf(cBuf);
}
} 版權聲明：