蚁群算法解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个城市的坐标数据,及它们的最优解,来与本文的蚁群算法得到的解进行对比。下面是公认的地图数据:

城市数坐标集合最优解
10(0,0),(12,32),(5,25),(8,45),(33,17),
(25,7),(15,15),(15,25),(25,15),(41,12)
147.34
20(60,200),(180,200),(80,180),(140,180),(20,160),
(100,160),(200,160),(140,140),(40,120),(100,120),
(180,100),(60,80),(120,80),(180,60),(20,40),
(100,40),(200,40),(20,20),(60,20),(160,20)
870.26
31(1304,2312),(3639,1315),(4177,2244),(3712,1399),(3488,1535),
(3326,1556),(3238,1229),(4196,1004),(4312,790),(4386,570),
(3007,1970),(2562,1756),(2788,1491),(2381,1676),(1332,695),
(3715,1678),(3918,2179),(4061,2370),(3780,2212),(3676,2578),
(4029,2838),(4263,2931),(3429,1908),(3507,2367),(3394,2643),
(3439,3201),(2935,3240),(3140,3550),(2545,2357),(2778,2826),
(2370,2975)
14705.55

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

城市数最短路长(最优解)最短路长(蚁群算法)最短路长(遗传算法)
10147.34147.34147.34
20870.26871.12897.53
3114705.5516263.7515647.02

结语

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

1) 蚁群算法在城市较少时(10-20个城市)的性能相比遗传算法更好,但随着问题的规模增大(城市数目增加),蚁群算法容易陷入局部最优,很难发现全局最优解。

2) 遗传算法特有的选择算子、交叉算子、变异算子带来的随机性较大,导致收敛性不如蚁群算法。

3) 时间效率方面(本文未给出时间方面的结果),如果要找出长度大致相同的解,蚁群算法的速度更快。但遗传算法在问题规模、时间效率、解的质量三方面的平均效果更优。

以上是本系列全部内容。若需要完整代码,可在我的GitHub上找到,对于代码和算法本身肯定都还有很多可以优化的地方,本文仅是给出了此算法的一个基本示例,更多深层次问题就等待大家去查阅、比较和实践了。

Leave a Comment.