引言

本章是遗传算法求解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

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

城市数	最短路长(最优解)	最短路长(遗传算法)	最短路径(遗传算法)
10	147.34	147.34	8,7,9,5,10,6,1,3,4,2,8
20	870.26	897.53	6,3,1,5,9,10,13,12,15,18, 19,16,20,17,14,11,7,2,4,8,6
31	14705.55	15647.02	2,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问题的系列文章，欢迎大家关注。