机器学习实验报告遗传算法在旅行商问题中的应用
遗传算法在旅行商问题中的应用
一、旅行商（TSP）问题
旅行商问题中，一个售货员必须访问n个城市。
如果把该问题模型化为一个具有n个顶点的完全图，就可以说这个售货员希望进行一次巡回旅行，或经过哈密顿回路，恰好访问每个城市一次，并最终回到出发的城市。
从城市i到城市j 的旅行费用为一个整数c(i,j)，这个售货员希望使整个旅行的费用最低，而所需的全部费用是他旅行经过的各边费用之和。
旅行商问题是NP完全问题。
二、遗传算法
遗传算法(GA)是一种受生物进化启发的学习方法。
它不再是从一般到特殊或从简单到复杂的搜索假设，而是通过变异和重组当前已知的最好假设来生成后续假设。
GA研究的问题是搜索候选假设空间并确定最佳的假设。
在GA中，“最佳假设”被定义为是使适应度最优的假设，适应度是当前问题预先定义的数字数量。
遗传算法的共同结构：算法迭代更新一个假设池，这个假设池成为群体。
在每一次迭代中，根据适应度函数评估群体中的所有成员，然后从当前群体中用概率方法选取适应度最高的个体产生新一代群体。
在这些被选中的个体中，一部分保持原样地进入下一代群体，其他的被用作产生后代个体的基础，其中应用像交叉和变异这样的遗传方法。
遗传算法的输入包括：用来排序候选假设的适应度函数；定义算法终止时适应度的阈值；要维持的群体大小；决定如何产生后继群体的参数，即每一代群体中被淘汰的比例和变异率。
Fitness：适应度评分函数，为给定假设赋予一个评估分数
Fitness_threshold：指定终止判据的阈值
p：群体中包含的假设数量
r：每一步中通过交叉取代群体成员的比例
m：变异率
遗产算法原型的伪代码如下：
算法流程图如下：
图1 遗传算法流程图
三、算法实现
本文算法将每个城市用他们在数组中的下标来表示，用所有下标的一个排列来表示商人旅行的路线，而遗传算法中的一个单体就可以用一个商人旅行的路线来表示，一个种群就是一些旅行路线的集合。
遗传算法的初始化操作主要进行的是初始种群的生成和选取，在本程序中，采取随机生成旅行路线的方式来生成一组集合作为初始种群。
由于本文用遗传算法来求解TSP问题，因此，衡量一个解的质量好坏的标准就是这个旅行线路总的旅行长度，因此，我们用一个解的总体旅行距离来作为一个解的适应度，适应度越大则说明解越差。
本文采用旅行路径来作为基因编码，而每一种旅行路线都是一组相同的数字的排列，因此，变异操作随机选取一条旅行路径中的两个城市，交换这两个城市的位置即达到了变异的效果。
程序随机选取种群中的两个个体进行交叉操作，统计两个个体中对应路线顺序中不同的部分，按照一定的概率将其中不同的路线段进行交换，从而完成交叉工作。
其中选择交叉的两段路线，其所覆盖的城市是相同的。
四、实验及结果分析
4.1开发语言及运行环境
开发语言：Java
运行环境：Microsoft Windows 7操作系统
2G内存
4.2 问题范围
实验输入的训练样例如下：
该旅行商问题规模为一个包含34个节点的完全图，分别代表"北京","上海","天津","重庆","哈尔滨","长春","沈阳","呼和浩特","石家庄","太原","济南","郑州","西安","兰州","银川","西宁","乌鲁木齐","合肥","南京","杭州","长沙","南昌","武汉","成都","贵州","福建","台北","广州","海口","南宁","昆明","拉萨","香港","澳门"这32个城市，存放在一个长度为34的数组中。
城市i和城市j的距离为数组中对应元素的相对位移。
如"北京"与"上海"的距离为1，对应完全图中的边长为1; "北京"与"天津"的距离为2，对应完全图中的边长为2，以此类推。
求解目标为从一个城市出发进行一次巡回，经过每个城市一次最终回到出发城市，并使整个旅行的费用最低，即遍历的城市距离和最短。
4.3 数据结构
private class genotype {
int city[] = new int[cityNum]; //单个基因的城市序列
long fitness; //该基因的适应度
double selectP; //选择概率
double exceptp; //期望概率
int isSelected; //是否被选择
}
private genotype[] citys = new genotype[popSize];
private String cityName[]={"北京","上海","天津","重庆","哈尔滨","长春","沈
阳","呼和浩特","石家庄","太原","济南","郑州","
西安","兰州","银川","西宁","乌鲁木齐","合肥","
南京","杭州","长沙","南昌","武汉","成都","贵州
","福建","台北","广州","海口","南宁","昆明","拉
萨","香港","澳门"};
private int cityNum=cityName.length; //城市个数
private long[][] distance = new long[cityNum][cityNum]; //城市距离
private int popSize = 50; //种群数量
private int maxgens = 10000; //迭代次数
private double pxover = 0.8; //交叉概率
private double pmultation = 0.05; //变异概率
private int range = 2000; //用于判断何时停止的数组区间
4.4 实验结果
进行若干次重复试验，四类运行结果如下：
1、迭代10000次，得到最优的结果。
本次实验结果表示从”南京”出发，依次经过以下城市，最终到达”杭州”再回到”南京”，旅行路程为66。
2、迭代未满10000次，即连续2000次得到的结果相同，提前终止。
结果如下所示：在第6859次迭代后停止了算法，得到的解为从”郑州”出发，依次经过后续城市，最终到达”西安”后再返回”郑州”。
旅行路程为66。
3、迭代满10000次，但仍未得到最优结果。
程序运行结果如下图所示：得到的解为从”南昌”出发，依次经过后续城市，最终到达”合肥”后再返回”南昌”。
旅行路程为82，比最优解66要大。
4、迭代未满10000次，但有连续2000次得到相同结果，然而结果不是最优的，程序运行结果如下所示：得到的解为从”南宁”出发，依次经过后续城市，最终到达”杭州”后再返回”南宁”。
旅行路程为106，比最优解66要大。
其他对比实验
使用控制变量法，通过修改迭代次数和停止阈值可以得到不同的实验结果，理论上迭代次数与停止阈值越大，越可能得到最优解。
如将10000改成5000，则很难得到最优解，或者将2000改成500，则很容易在非最优解时停止迭代，同样很难得到优化解。
由此可见迭代次数与停止阈值能影响程序的遗传算法的优化效果。
五总结
遗传算法维护一个由竞争假设组成的多样化群体。
在每次迭代中，选出群体中适应度最高的成员来产生后代，替代群体中适应度最差的成员，假设常被编码成位串，可以通过交叉算子组合，位串上也可能发生随机变异。
遗传算法已经被普遍应用到机器学习以外的最优化问题中，如本程序的是遗传算法在旅行商问题中的应用。
同时，通过实验深刻理解了遗传算法求的最优解得到的结果是一个近似结果，并不是每次都能得到最优解（如上述实验结果中的后两种），但通过更多次的迭代，有更大的概率能得到最优解。