引言
本章是遗传算法求解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个城市的坐标数据，及它们的最优解，来与我写的遗传算法得到的解进行对比。下面是公认的地图数据：
下面是本文遗传算法求得的最短路线及长度数据：
结语
从上表不难发现，随着问题规模的扩大，遗传算法发现全局最优解的几率仍然很大（通过对比后续文章蚁群算法解TSP(3)-效果验证可以发现），这不失为它的优点。但缺点是收敛性不高，这是因为受选择算子、交叉算子、变异算子的影响较大，解群容易波动，故而不太稳定，有时需要消耗更多的计算时间去弥补收敛性不好的缺陷。
遗传算法的用途显然不仅限于TSP问题，任何需要优化模型参数的问题都可以用它来解决，比如排课排班、机器人路径规划甚至应用于人工神经网络等，从而曲线式地避免了利用穷举方法产生的高昂成本与低效。
遗传算法求解TSP问题的相关内容就写到这里啦。当然需要声明的是，本文仅仅是给出了一个朴素遗传算法的实现方案，更多对其优化的方案可以去网上查阅，相信那里肯定还有一片新的天地。然后注意本文给出的代码都是一些代码片段，并不能完整运行，有的地方不是探讨的核心内容，所以甚至索性省去了。如果需要完整代码可以在我的GitHub上下载。后续会再写一个用“蚁群算法”求解TSP问题的系列文章，欢迎大家关注。
