蚁群算法解TSP(2)-核心代码

引言

按照上一章的算法流程,本章给出一个自己用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];
    }
}

结语

核心代码已经贴完。下一章对蚁群算法所涉及的参数进行一些代码上的说明,并给出算法的实际运行结果,同时与前面遗传算法的运行结果进行对比分析。

 

Leave a Comment.