机器学习报告(修改版)

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