引言
按照上一章的算法流程，本章给出一个自己用Java代码及面向对象思路实现的蚁群算法。尽量追求代码的质量、可读性和优雅性，但也难免会有写得不达标的地方，希望大家能去粗取精，获取到对自己有益的部分即可。
道路类-Road
每条道路有它的距离和信息素浓度，所以需要抽象出一个这个Road类，势必能为后续操作带来很大便利~就像下面一样：
class Road
{
float distance; //距离
float pheromone; //信息素
//构造函数
......
}
城市类-City
为方便蚂蚁k选出下一步要走的城市j，我们还需建立一个City类，临时存储与蚂蚁k当前所处城市i相邻的所有城市j的选择概率、能见度与信息素浓度和（存储该值是为方便后续计算所有相邻城市的总和用）。如下所示：
class NeighborCity
{
int id;
float rate; //被选择概率
float vap; //能见度和信息素浓度总和
//构造函数
......
}
蚂蚁类-Ant
为刻画蚂蚁寻径过程中的各种行为，如随机化初始出生城市、选择城市、到达城市等，建立Ant类，如下所示：
class Ant
{
int[] passed;//已经过的城市列表（禁忌表）
float passedLength;//环游长度
int curCity;//蚂蚁当前所在城市
int curIndex;//下一城市需加入禁忌表的对应位置
//初始化蚂蚁数据
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
该类对蚁群算法的各环节进行总控调度，模拟蚂蚁出生、蚂蚁选择路线、蚂蚁环游、信息素更新、多轮环游等过程，具体实现如下：
class AntAlgorithm
{
private Ant[] ants;//蚁群
float minLength = Float.MAX_VALUE;//当前最短距离
int[] minRoute; //当前最短路线
//构造函数
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++) //迭代次数
{
//初始化蚂蚁数据
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);//到达下一个城市
}
}
//返回起点城市并计算最优路径
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++)
{
//所有路径的信息素均蒸发
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)//出现过这段路径
{
//更新路径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];
}
}
结语
核心代码已经贴完。下一章对蚁群算法所涉及的参数进行一些代码上的说明，并给出算法的实际运行结果，同时与前面遗传算法的运行结果进行对比分析。
网友评论