引言
按照上一章的算法流程作煌，本章給出一個自己用Java代碼及面向?qū)ο笏悸穼崿F(xiàn)的蟻群算法清蚀。盡量追求代碼的質(zhì)量、可讀性和優(yōu)雅性揉忘，但也難免會有寫得不達標(biāo)的地方跳座，希望大家能去粗取精，獲取到對自己有益的部分即可泣矛。
道路類-Road
每條道路有它的距離和信息素濃度疲眷，所以需要抽象出一個這個Road類，勢必能為后續(xù)操作帶來很大便利~就像下面一樣：
class Road
{
float distance; //距離
float pheromone; //信息素
//構(gòu)造函數(shù)
......
}
城市類-City
為方便螞蟻k選出下一步要走的城市j您朽，我們還需建立一個City類狂丝，臨時存儲與螞蟻k當(dāng)前所處城市i相鄰的所有城市j的選擇概率、能見度與信息素濃度和（存儲該值是為方便后續(xù)計算所有相鄰城市的總和用）哗总。如下所示：
class NeighborCity
{
int id;
float rate; //被選擇概率
float vap; //能見度和信息素濃度總和
//構(gòu)造函數(shù)
......
}
螞蟻類-Ant
為刻畫螞蟻尋徑過程中的各種行為几颜，如隨機化初始出生城市、選擇城市讯屈、到達城市等蛋哭，建立Ant類，如下所示：
class Ant
{
int[] passed;//已經(jīng)過的城市列表（禁忌表）
float passedLength;//環(huán)游長度
int curCity;//螞蟻當(dāng)前所在城市
int curIndex;//下一城市需加入禁忌表的對應(yīng)位置
//初始化螞蟻數(shù)據(jù)
void init()
{
initPassed();
passedLength=0.0f;
curIndex=0;
initBeginCity();
}
//初始化禁忌表
void initPassed()
{
passed=new int[Constant.CITY_NUM+1];
for(int i=0;i<passed.length;i++)
passed[i]=Integer.MIN_VALUE;
}
//初始化螞蟻所在城市
void initBeginCity()
{
Random rand=new Random();
int beginCity=rand.nextInt(Constant.CITY_NUM);
reachNextCity(beginCity);
}
//到達下一個城市
void reachNextCity(int nextCity)
{
//累加周游距離
passedLength += Constant.roads[curCity][nextCity].distance;
//前進
curCity=nextCity;
passed[curIndex++]=nextCity+1;
}
//判斷城市nCity是否在禁忌表中
boolean isPassedCity(int nCity)
{
for(int i=0;passed[i] != Integer.MIN_VALUE;i++)
{
if(passed[i] == nCity) //存在的城市
return true;
}
return false;
}
}
蟻群算法類-AntAlgorithm
該類對蟻群算法的各環(huán)節(jié)進行總控調(diào)度涮母，模擬螞蟻出生谆趾、螞蟻選擇路線、螞蟻環(huán)游叛本、信息素更新沪蓬、多輪環(huán)游等過程，具體實現(xiàn)如下：
class AntAlgorithm
{
private Ant[] ants;//蟻群
float minLength = Float.MAX_VALUE;//當(dāng)前最短距離
int[] minRoute; //當(dāng)前最短路線
//構(gòu)造函數(shù)
AntAlgorithm()
{
ants=new Ant[Constant.ANT_NUM];
for(int i=0;i<Constant.ANT_NUM;i++)
ants[i]=new Ant();
minRoute=new int[Constant.CITY_NUM];
}
//算法流程開始
void run()
{
for(int nc = 1; nc <= Constant.NC; nc++) //迭代次數(shù)
{
//初始化螞蟻數(shù)據(jù)
for(int k = 0; k < Constant.ANT_NUM; k++)
ants[k].init();
//遍歷所有城市
for(int look = 1; look < Constant.CITY_NUM; look++)
{
for(int k = 0; k < Constant.ANT_NUM; k++)//每只螞蟻
{
int nextCity = select(ants[k]);//選擇下一個城市
ants[k].reachNextCity(nextCity);//到達下一個城市
}
}
//返回起點城市并計算最優(yōu)路徑
for(int k = 0; k < Constant.ANT_NUM; k++)//每只螞蟻
{
ants[k].reachNextCity(ants[k].passed[0]-1);
if(minLength > ants[k].passedLength)
{
minLength = ants[k].passedLength; //記錄最短距離
writeRoute(ants[k].passed); //記錄最短路線
}
}
//對roads進行信息素更新
for(int i = 0; i < Constant.CITY_NUM; i++)
{
for(int j = 0; j < Constant.CITY_NUM; j++)
{
//所有路徑的信息素均蒸發(fā)
Constant.roads[i][j].pheromone *= Contant.p;
for(int k = 0; k < Constant.ANT_NUM; k++)
{
for(int n = 0; n < Constant.CITY_NUM; n++)
{
int curCity = ants[k].passed[n]-1;
int nextCity = ants[k].passed[(n+1) % Constant.CITY_NUM]-1;
if(curCity == i && nextCity == j)//出現(xiàn)過這段路徑
{
//更新路徑curCity,nextCity信息素
float dp = Constant.Q / ants[k].passedLength;//信息素增量
Constant.roads[i][j].pheromone += dp;
}
}
}
}
}
}
}
//計算選擇概率+輪賭
int select(Ant ant)
{
float totalVap = 0.0f;
List<NeighborCity> neighborCityList = new LinkedList<NeighborCity>();
NeighborCity neighborCity;
for(int nextCity = 0; nextCity < Constant.CITY_NUM; nextCity++)
{
if(!ant.isPassedCity(nextCity+1))//可選擇城市
{
double pheromone = Constant.roads[ant.curCity][nextCity].pheromone;
pheromone = Math.pow(pheromone, Constant.alpha);
double visibility=1.0f / Constant.roads[ant.curCity][nextCity].distance;//能見度
visibility=Math.pow(visibility, Constant.beta);
float vap = (float) visibility + (float) pheromone;
totalVap += vap; //累加VAP
neighborCity = new NeighborCity(nextCity, vap);
neighborCityList.add(neighborCity);//添加
}
}
//計算每個城市被選中的概率
ListIterator<NeighborCity> iterator = neighborCityList.listIterator(); //獲取迭代器
while (iterator.hasNext())
{
neighborCity = iterator.next(); //取城市
neighborCity.rate = neighborCity.vap / totalVap; //計算概率
}
//賭輪選擇其中一個城市
float rate = (float) Math.random();
iterator = neighborCityList.listIterator(); // 獲取迭代器
while (iterator.hasNext())
{
neighborCity = iterator.next();
if(rate <= neighborCity.rate)
return neighborCity.id; //選擇該城市来候！
else
rate -= neighborCity.rate;
}
//概率精度所致跷叉，人為返回最后一個城市
iterator = neighborCityList.listIterator();
while (iterator.hasNext())
{
neighborCity = iterator.next();
if(iterator.hasNext() == false) //選擇最后一個城市!
return neighborCity.id;
}
return neighborCity.id;
}
//記錄最短路線
void writeRoute(int[] route)
{
for(int i = 0; i < minRoute.length; i++)
minRoute[i] = route[i];
}
}
結(jié)語
核心代碼已經(jīng)貼完。下一章對蟻群算法所涉及的參數(shù)進行一些代碼上的說明营搅，并給出算法的實際運行結(jié)果云挟，同時與前面遺傳算法的運行結(jié)果進行對比分析。
