用遗传算法求解中国34个省会TSP地问题

实用文档实用文档题目：用遗传算法求解中国个省会问题源代码分享在本人博客:智能控制技术及其应用

大作业专业:控制工程学号：姓名：用遗传算法求解中国 个省会问题问题的描述旅行商问题（）可以具体描述为：已知个城市之间的相互距离，现有一个推销员从某一个城市出发，必须遍访这个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。现给出中国个省会数据，要求基于此数据使用遗传算法解决该 问题。内发占西施♦随E内发占西施♦随E江吉林澳门图1中国3个省会位置1西.藏2云.南3.四川个.青海5.宁夏6.甘肃 7内.蒙古8黑.龙江9.吉林10辽.宁11北.京12天津13河.北1个山.东15河.南16山.西 17陕西 18安.徽19江.苏20上.海21浙.江22江.西23湖.北 2个湖.南25贵,州 26广西 27广.东28福.建29海.南30澳.门1香.港32台.湾33重.庆3个新.疆像素坐标如下：二、遗传算法的介绍遗传算法遗传算法的基本原理是通过作用于染色体上的基因寻找好的染色体来求解问题，它需要对算法所产生的每个染色体进行评价，并基于适应度值来选择染色体，使适应性好的染色体有更多的繁殖机会，在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗产操作后的个体集合形成下一代新的种群，对这个新的种群进行下一轮的进化。遗传算法的过程遗传算法的基本过程是：初始化群体。计算群体上每个个体的适应度值由个体适应度值所决定的某个规则选择将进入下一代个体。按概率 进行交叉操作。按概率进行变异操作。.没有满足某种停止条件，则转第2步，否则进入第7步。.输出种群中适应度值最优的染色体作为问题的满意解或最优界。停止条件有两种：一是完成了预先给定的进化代数则停止；二是种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。遗传算法过程图如图2：

三、遗传算法解决图2遗传算法过程框图问题的程序实现1三、遗传算法解决图2遗传算法过程框图问题的程序实现程序首先读入34个省会城市坐标，计算任意两个城市的距离；设置遗传算法控制参数。种群数目%进化迭代次数%适应度归一化淘汰加速指数，取值不宜太大;%淘汰保护指数，范围0~，1为1时关闭保护生成矩阵计算城市距离矩阵下：遗传算法对求解问题本身是一无所知的，这里采用随机生成初始化种群，如下：用于存储种群随机生成初始化种群计算适应度本程序目标函数为经过34省会的总距离，适应度与目标函数的正相关，取值范围0~，1适应度计算公式为：其中， 为某组解的总距离， 为该次迭代中最短距离， 为该次迭代中最长距离，为适应度归一化淘汰加速指数，源程序如下：选择操作当个体适应度小于某一随机数值时，遭到淘汰，保留优秀个体，使它们有机会作为父代产生后代个体，源程序如下：为复制的个数适应度与随机数值相比较交叉操作许多生物的繁衍是通过染色体的交叉完成的，在遗传算法中使用这一概念，并把交叉作为遗传算法的一个操作算子，其实现过程是对选中用于繁殖下一代的个体，随机地选择两个个体的位置，按交叉概率P在选择的位置实行交换，目的在于产生新的基因组合，即新的个体，源代码如下：选择交叉的片段使用部分匹配交叉法进行交叉操作以下是交叉函数：%交叉算法采用的是由以下是交叉函数：%交叉算法采用的是由部分匹配交叉和于 年提出的部分匹配交叉a);确定交叉宽度随机选择交叉范围，从到交叉交换函数交换函数x=y;y=temp;本遗传算法中并未引入变异操作，当程序迭代次数满足设定条件时，程序得出近似最优解。四、程序结果分析初始值种群数目设为，淘汰保护指数设为0，时8，进化迭代次数为50，0归0一化淘汰加速指数设为运行程序，得最短距离为初始值种群数目设为，淘汰保护指数设为0，时8，进化迭代次数为50，0归0一化淘汰加速指数设为运行程序，得最短距离为，9结.果3如下：图3城市位置坐标（左）、初始解（中）、最终解（右）问题最优路径，图4种群数为50，0进化数为从图4可以看出，迭代次数超过50次0时，所得的解已接近近似最优解。只改变种群数量，进行多次计算，可得下表：种群数量最终解距离表一不同种群数量下最终解综上所述，种群越大、迭代越多求解的结果越优化，但是需要花费大量的运算时间；由于算法中存在多个随机参数，因此每次计算结果不一定相同，须根据需要设定初值进行多次计算取多组中最优解。另一种的遗传算法解决该问题上述算法中，只采用了遗传算法中交换操作，以下算法，则采用变异操作解决同一问题。算法核心思路是，在每次迭代中，解的个体随机按4个为1组，每组中只保留最优解，然后对此最优解进行左右翻转、交换、向前移位三种变异操作，生成三个新个体，再参与下次迭代。整个算法不需要计算归一化适应度，核心源代码如下：生成 每一列元素按照升序排列矩阵保留最佳个体，繁殖三个新个体左右翻转交换向前移动一位在此算法中，每次迭代淘汰率固定为75，%三种变异操作覆盖面比较广，直接以最短距离为适应函数，省去每次适应度的计算。初始值种群数目设为50，0进化迭代次数为50，0寻0得最优解为1295，.如7下2：

（右上）、最优路径（左下）、寻优历史（右下）图5省会位置（左上）、各省会距离分布（右上）、最优路径（左下）、寻优历史（右下）图5省会位置（左上）、各省会距离分布由上图及最终结果可以看出，该算法比上一算法所得结果更优化，从寻优历史可见，迭代次数在接近10次0才0能得到近似最优解（见表二），总体而言，该算法相对上一算法收敛性更好，但计算量稍大。种群数量最终解距离表二不同种群数量下最终解

图 种群数为 0进化数为 0问题最优路径总结本文采用 实现遗传算法求解 问题，对结果进行了分析，并对比了两种不同思路的遗传算法。遗传算法是一种智能优化算法，它的实现有些关键点，一是串的编码方式，本质就是问题编码，串长度及编码形式对算法收敛影响极大；二是适应函数的确定，这是选择的基础；三是自身参数的设定，其中重要的是群体大小，最大迭代次数，通过计算我们可以看到最大迭代次