遗传算法解TSP(3)-效果验证

引言

本章是遗传算法求解TSP问题的最后一章,主要做一些收尾的工作。介绍一下如何用GeneticAlgorithm这个类去驱动遗传算法工作流程的执行,以及遗传算法所涉及的可配置参数Constant,最后给出遗传算法分别在10个城市、20个城市和31个城市的TSP问题中的效果表现。

工作流程

正如前面提到过的,遗传算法先后经过初始化种群、计算适应度、选择操作、交叉操作、变异操作和收敛条件判断,最后选出适应度最优的个体作为最终解。所以现在我们需要把前面的各种操作组合起来,使得能完整地执行一轮遗传算法的工作流程,在这个基础上,再迭代(遗传)若干代,最后收敛到某个较优解。

落实到代码上,我们仍采用面向对象思想,将initSpeciesList()、calFitness()、select()、cross()和mutate()这些方法归在GeneticAlogrithm类中,然后顺次调用,如下面所示:

//开始遗传
SpeciesNode run()
{
    //创建初始种群
    List<SpeciesNode> speciesList = initSpeciesList();
    
    //遗传迭代
    for(int i=1;i<=Constant.DEVELOP_NUM;i++)
    {
        //选择
        select(speciesList);
        
        //交叉
        crossover(speciesList);
        
        //变异
        mutate(speciesList);
    }	
    
    //返回最优解
    return getBest(speciesList);
}

参数配置

从前面对遗传算法的讲述中不难发现,算法涉及许多不变的常量,比如地图数据、种群数、进化代数、交叉概率、变异概率,甚至更多对遗传算法改进后涉及的参数,写出来就像下面这样:

//常量类
public class Constant 
{
    //遗传算法参数
    static final int SPECIES_NUM = 200; //种群数
    static final int DEVELOP_NUM = 100; //进化代数
    static final float tp = 0.25; //精英复制比重
    static final float pcl = 0.6f, pch = 0.95f;//交叉概率
    static final float pm = 0.4f;//变异概率
    
    //地图数据
    static int CITY_NUM; //城市数
    static final float[][] disMap; //路线长度
    static
    {
        //城市坐标
        int[][] cityPosition={
                {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}}; //20个城市(最优解:870)

        //初始化计算完全图所有路线长度
        CITY_NUM=cityPosition.length;
        disMap=new float[CITY_NUM][CITY_NUM];
        for(int i=0;i<CITY_NUM;i++)
        {
            for(int j=i;j<CITY_NUM;j++)
            {
                float dis = (float) Math.sqrt(Math.pow((cityPosition[i][0] - cityPosition[j][0]),2) + Math.pow((cityPosition[i][1] - cityPosition[j][1]),2));
                
                disMap[i][j]=dis;
                disMap[j][i]=disMap[i][j];
            }
        }	
    }
}

实验结果

Constant类中的cityPosition参数用来配置城市的坐标数据,所以我分别选取了网上一些公认的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

下面是本文遗传算法求得的最短路线及长度数据:

城市数最短路长(最优解)最短路长(遗传算法)最短路径(遗传算法)
10147.34147.348,7,9,5,10,6,1,3,4,2,8
20870.26897.536,3,1,5,9,10,13,12,15,18,
19,16,20,17,14,11,7,2,4,8,6
3114705.5515647.022,4,16,5,6,23,11,26,21,22,
18,3,17,19,24,20,25,30,29,28,
27,31,1,15,14,12,13,7,10,9,8,2

结语

从上表不难发现,随着问题规模的扩大,遗传算法发现全局最优解的几率仍然很大(通过对比后续文章蚁群算法解TSP(3)-效果验证可以发现),这不失为它的优点。但缺点是收敛性不高,这是因为受选择算子、交叉算子、变异算子的影响较大,解群容易波动,故而不太稳定,有时需要消耗更多的计算时间去弥补收敛性不好的缺陷。

遗传算法的用途显然不仅限于TSP问题,任何需要优化模型参数的问题都可以用它来解决,比如排课排班、机器人路径规划甚至应用于人工神经网络等,从而曲线式地避免了利用穷举方法产生的高昂成本与低效。

遗传算法求解TSP问题的相关内容就写到这里啦。当然需要声明的是,本文仅仅是给出了一个朴素遗传算法的实现方案,更多对其优化的方案可以去网上查阅,相信那里肯定还有一片新的天地。然后注意本文给出的代码都是一些代码片段,并不能完整运行,有的地方不是探讨的核心内容,所以甚至索性省去了。如果需要完整代码可以在我的GitHub上下载。后续会再写一个用“蚁群算法”求解TSP问题的系列文章,欢迎大家关注。

Leave a Comment.