蚁群算法解TSP(3)-效果验证

引言

蚁群算法差不多已经水落石出了，本章作为该系列的最后一章，再提一些小细节供大家参考。一方面是蚁群算法涉及的一些参数，比如：挥发速率、能见度与信息素的控制因子、信息素增量的控制因子等；另一方面给出蚁群算法分别在10个城市、20个城市和31个城市的TSP问题中找到的最短环游路径结果，并与前面的遗传算法进行纵向比较。

参数配置

把所有可配置的参数归到Constant类，在其他类里通过静态变量的形式获取。当然更优雅的办法是写入一个properties.xml的文本文件中，规定好固定的key-value格式，然后调用java.util.Properties相关类读取，这样把静态或不易改变的数据从动态的程序中解耦出来，让数据由文本文件决定，从而完全不用再次编译程序，为后续维护、测试与调试带来极大便利（当然这个程序很小，所以基本或完全不需要这些考虑）。

class Constant 
{
    static int CITY_NUM; //城市数
    static Road[][] roads; //道路
    static final float C = 10.0f; //信息素初值
    static final int NC = 10; //环游总轮数
    static final int ANT_NUM = 10; //蚂蚁数
    static final int alpha = 2; //信息素控制因子
    static final int beta = 3; //能见度控制因子
    static final float p = 0.3f; //挥发速率
    static final float Q = 300.0f; //信息素增量控制因子
    
    static
    {
        //城市坐标
        int[][] cityPoint={
                {0,0},{12,32},{5,25},{8,45},{33,17},
                {25,7},{15,15},{15,25},{25,15},{41,12}};
        
        
        //确定城市数、构建道路
        CITY_NUM=cityPoint.length;
        roads = new Road[CITY_NUM][CITY_NUM];
        for(int i=0;i<CITY_NUM;i++)
            for(int j=0;j<CITY_NUM;j++)
                roads[i][j]=new Road();
        for(int i=0;i<CITY_NUM;i++)
        {
            for(int j=i;j<CITY_NUM;j++)
            {
                //计算长度
                float dis=(float)Math.sqrt(Math.pow((cityPoint[i][0] - cityPoint[j][0]),2) + Math.pow((cityPoint[i][1] - cityPoint[j][1]),2));
                //装入距离
                roads[i][j].distance=dis;
                roads[j][i].distance=dis;
            }
        }
    }
}

实验结果

我们分别选取网上一些公认的10个城市、20个城市和31个城市的坐标数据，及它们的最优解，来与本文的蚁群算法得到的解进行对比。下面是公认的地图数据：

本文的蚁群算法与遗传算法解TSP(3)-效果验证的对比结果如下表所示：

结语

仅依据上表显示结果的结果来看，我们不难得出以下一些结论：

• 蚁群算法在城市较少时（10-20个城市）的性能相比遗传算法更好，但随着问题的规模增大（城市数目增加），蚁群算法容易陷入局部最优，很难发现全局最优解。
• 遗传算法特有的选择算子、交叉算子、变异算子带来的随机性较大，导致收敛性不如蚁群算法。
• 时间效率方面（本文未给出时间方面的结果），如果要找出长度大致相同的解，蚁群算法的速度更快。但遗传算法在问题规模、时间效率、解的质量三方面的平均效果更优。
  以上是本系列全部内容。若需要完整代码，可在我的GitHub上找到，对于代码和算法本身肯定都还有很多可以优化的地方，本文仅是给出了此算法的一个基本示例，更多深层次问题就等待大家去查阅、比较和实践了。