用遗传算法解决旅行商问题
用遗传算法解决旅行商问题
姓名：王晓梅
学号：1301281
班级：系统工程6班
一、问题背景
有一个销售员，要到n 个城市推销商品，他要找出一个包含所有n 个城市的具有最短路程的环路。
现在假设有10个城市，他们之间的距离如下。
{ 0, 107, 241, 190, 124, 80, 316, 76, 152, 157},
{ 107, 0, 148, 137, 88, 127, 336, 183, 134, 95},
{ 241, 148, 0, 374, 171, 259, 509, 317, 217, 232},
{ 190, 137, 374, 0, 202, 234, 222, 192, 248, 42},
{ 124, 88, 171, 202, 0, 61, 392, 202, 46, 160},
{ 80, 127, 259, 234, 61, 0, 386, 141, 72, 167},
{ 316, 336, 509, 222, 392, 386, 0, 233, 438, 254},
{ 76, 183, 317, 192, 202, 141, 233, 0, 213, 188},
{ 152, 134, 217, 248, 46, 72, 438, 213, 0, 206},
{ 157, 95, 232, 42, 160, 167, 254, 188, 206, 0}
将这10个城市分别编码为0,1,2,3,4,5,6,7,8,9。要求走完这10个城市，目标是使走的距离最短。
二、建立模型
),...,1,(1)
,...,1,(1.
.)(min 11
11n j j i n i j i t s j i n j ij
n i ij ij n i n
j ij x x d x =≠==≠=≠∑∑∑∑==== 三、设计算法
1、种群初始化
（1）一条染色体的初始化
10个城市分别对应0~9这十个数，每个染色体代表一个解决方法，即0~9这十个数的一种排序方式，可随机产生一个数，用取余的方法得到一个0~9的数，依次得到与前面不重复的十个数，构成一个染色体。
（2）种群的初始化
这里假设种群有100个染色体，也就是循环100次染色体的初始化可得到一个种群。
2、适值的计算
求相邻两个城市的距离和代表适值，适值越小，表示结果越好。
3、交叉
交叉是指从种群中选两个染色体作为父代，交叉产生两个子代。
这里有两个问题：
（1）怎么选出那两对要交叉？
这里将100个染色体分成50组，产生50个0~1的随机数对应这50对父代，若产生的随机数小于交叉率，表示这对父代被选中，则进行交叉，否则不交叉，保留父代。
（2）怎么交叉？
采用单点的顺序交叉，就是随机产生一个交叉点，先将父代1交叉点前后的基因颠倒给一个中间变量new，然后比较new每一位与父代2交叉点后面的基因，若相同，令new该位为-1（目的就是找出并去掉new染色体中与父代2交叉点后面相同的基因），再将new中不是-1的基因先按顺序赋给子代1，再把父代2交叉点后的基因赋给子代1，这样子代1就产生了。
同样的方法产生子代2.，完成交叉。
4、变异
（1）选出变异的染色体
随机产生0~99的随机数，产生100个，分别与种群中100个染色体对应，比较所产生的随机数与变异率，若小于变异率，则变异，否则不变异，保留父代。
（2）进行变异
产生0~9的两个随机数，代表这个染色体当中被选中的两个基因位，进行交换即可。
5、选择
采用轮盘赌法，轮盘赌法是在圆盘中占得比例大的被选中的概率大，意味着好的解事占比例大的，而这里要求的是希望适值越小越好，为解决这个问题，设置一个最大适值，求它与每一个染色体的差，差越大对应适值越小，解也就越好，求这100个差的和，每一个差占100个差的比例，代表在圆盘中所占大小。
随机产生一个0~1的随机数rd，从第一个染色体开始，比较该随机数与染色体所占的比例，若小于表示这个染色体被选中，若不小于，将累加下一个染色体的比例，在比较，直到小于为止，所加的最后一个染色体就是被选中的染色体。循环一百次产生100个随机数来选择100个染色体作为下次迭代的父代。
6、主函数
先初始化种群，计算适值，选这一代中适值最好的，交叉变异选择，产生新的父代。
void main()
{
static int map[length][length]=
{
{ 0, 107, 241, 190, 124, 80, 316, 76, 152, 157},
{ 107, 0, 148, 137, 88, 127, 336, 183, 134, 95},
{ 241, 148, 0, 374, 171, 259, 509, 317, 217, 232},
{ 190, 137, 374, 0, 202, 234, 222, 192, 248, 42},
{ 124, 88, 171, 202, 0, 61, 392, 202, 46, 160},
{ 80, 127, 259, 234, 61, 0, 386, 141, 72, 167},
{ 316, 336, 509, 222, 392, 386, 0, 233, 438, 254},
{ 76, 183, 317, 192, 202, 141, 233, 0, 213, 188},
{ 152, 134, 217, 248, 46, 72, 438, 213, 0, 206},
{ 157, 95, 232, 42, 160, 167, 254, 188, 206, 0}
};
GA ga;
ga.initializePop(); //产生初始种群
for(int i=0;i { ga.sel_pop[0].sumfitness=0; ga.pool_pop.fitness=definenum; //用来比较筛选找种群中最小的适值for(int j=0;j ga.old_pop[j].evaluate(); } for(int j=0;j { if(ga.old_pop[j].fitness { for(int q=0;q { ga.pool_pop.code[q]=ga.old_pop[j].code[q]; } ga.pool_pop.fitness=ga.old_pop[j].fitness; } } ga.selectChr(); //选择 ga.crossover(); //交叉 ga.mutate(); //变异 cout<<"输出第“< ga.pool_pop.evaluate(); ga.pool_pop.toprint(); } system("pause"); } 四，结果 1、迭代50次，交叉率0.8，变异率0.3的结果。 2迭代50次，交叉率0.5，变异0.3的结果，结果很明显变得不好，说明交叉率太小，种群中染色体变化太小，会陷入局部最优，不利于结果向好的方向发展。 3、迭代50次，交叉率0.8，变异率0.9的结果，结果也是变差，说明变异率太大对会是结果向着不好的方向发展。 4、迭代100次，交叉率0.8，变异0.3的结果，相比较第一种情况而言，结果差不多，说明迭代50次，差不多已经达到稳定。 五、总结 在初始种群100，增大迭代次数会使结果向好的方向发展，直到达到稳定，结果基本不变化。交叉率过小的话，种群几本不更新，没法产生好的染色体，结果几本没变化，没法向好的方向发展，所以需要设置较大的交叉率，以保证种群中有新的染色体产生。变异率不宜 过大，变异率在自然界中本来发生的可能性就很小，不能设置的太大。 实验六：遗传算法求解TSP问题实验 一、实验目的 熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。用遗传算法对TSP问题进行了求解，熟悉遗传算法地算法流程，证明遗传算法在求解TSP问题时具有可行性。 二、实验内容 参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗传算法求解不同规模TSP问题的算法性能。 对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。 增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。 1. 最短路径问题 所谓旅行商问题(Travelling Salesman Problem , TSP)，即最短路径问题，就是在给定的起始点S到终止点T的通路集合中，寻求距离最小的通路，这样的通路成为S点到T点的最短路径。 在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路径，还需要知道某个顶点到其他任意顶点间的最短路径。遗传算法方法的本质是处理复杂问题的一种鲁棒性强的启发性随机搜索算法，用 遗传算法解决这类问题，没有太多的约束条件和有关解的限制，因而可以很快地求出任意两点间的最短路径以及一批次短路径。 假设平面上有n个点代表n个城市的位置, 寻找一条最短的闭合路径, 使得可以遍历每一个城市恰好一次。这就是旅行商问题。旅行商的路线可以看作是对n个城市所设计的一个环形, 或者是对一列n个城市的排列。由于对n个城市所有可能的遍历数目可达(n- 1)!个, 因此解决这个问题需要0(n!)的计算时间。假设每个城市和其他任一城市之间都以欧氏距离直接相连。也就是说, 城市间距可以满足三角不等式, 也就意味着任何两座城市之间的直接距离都小于两城市之间的间接距离。 2. 遗传算法 遗传算法是由美国J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。通过模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方法。其假设常描述为二进制位串，位串的含义依赖于具体应用。搜索合适的假设从若干初始假设的群体集合开始。当前种群成员通过模仿生物进化的方式来产生下一代群体，如随机变异和交叉。每一步，根据给定的适应度评估当前群体的假设，而后使用概率方法选出适应度最高的假设作为产生下一代的种子。 实验报告：用遗传算法解决旅行商问题的简单实现 实验目的：编写程序实现用遗传算法解决旅行商问题，研究遗传算法的工作原理和收敛性质。 实验者： 问题描述：TSP是一个具有广泛应用背景和重要理论价值的组合优化难题，TSP问题可以简单的描述为：已知N个城市之间的相互距离．现有一个旅行商必须遍历这N个城市，并且每个城市只能访一次，最后必须返回出发城市。如何安排他对这些城市的访问次序，可使旅行路线的总长度最短？ 本次实验的目标问题中国大陆31个大城市的公路旅行商问题，数据来源是《中国大城市公路里程表》（后附）。 需求分析：TSP已经被证明是一个NP—Hard问题，即找不到一种算法能在多项式时间内求得问题的最优解。利用遗传算法，在一定时间内求得近似最优解的可能性比较大。实验目标是： 1）设计用遗传算法解决TSP问题的程序； 2）求出该TSP问题的（近似）最短路程； 3）求得相应的城市遍历序列； 4）检查算法收敛性，求解决该问题的（近似）最优遗传参数。 算法分析： 1．算法基本流程 2．编码策略与初始群体设定 TSP的一般编码策略主要有二进制表示、次序表示、路径表示、矩阵表示和边表示等。而路径编码是最直观的方式，以城市序号作为遗传基因。在本实验中，我们用一个N维向量来表示一个个体，N是城市总数，元素表示城市遍历顺序，以最后一个到达的城市为结束。则群体用一个N * POP的矩阵表示，POP为群体中的人口（个体数）。初始群体在空间中自动生成。 3．适应度函数及结束条件 适应度函数采用题目的目标函数——路径的总路程（包括回到出发点）。适应度越低，个体越优秀。由于暂时无法先验估计收敛性和目标结果，所以以一个参数，最大遗传代数MAXGEN作为程序结束控制。 4．遗传算子设计 遗传算子的设计方法主要有两大类：自然算法和贪心算法。自然算法是以大自然的进化规律为依据，大体采用“优胜劣汰”的机制来进行遗传；贪心算法则是以迅速收敛为目标，对个体进行更严格的选择和遗传处理。 遗传算法解决TSP问题 姓名： 学号： 专业: 问题描叙 TSP问题即路径最短路径问题，从任意起点出发（或者固定起点），依次经过所有城市，一个城市只能进入和出去一次，所有城市必须经过一次，经过终点再到起点，从中寻找距离最短的通路。 通过距离矩阵可以得到城市之间的相互距离，从距离矩阵中的到距离最短路径，解决TSP问题的算法很多，如模拟退火算法，禁忌搜索算法，遗传算法等等，每个算法都有自己的优缺点，遗传算法收敛性好，计算时间少，但是得到的是次优解，得不到最有解。 算法设计 遗传算法属于进化算法的一种，它通过模仿自然界的选择与遗传的机理来寻找最优解. 遗传算法有三个基本算子：选择、交叉和变异。 数值方法求解这一问题的主要手段是迭代运算。一般的迭代方法容易陷入局部极小的陷阱而出现"死循环"现象，使迭代无法进行。遗传算法很好地克服了这个缺点，是一种全局优化算法。 生物在漫长的进化过程中，从低等生物一直发展到高等生物，可以说是一个绝妙的优化过程。这是自然环境选择的结果。人们研究生物进化现象，总结出进化过程包括复制、杂交、变异、竞争和选择。一些学者从生物遗传、进化的过程得到启发，提出了遗传算法。算法中称遗传的生物体为个体，个体对环境的适应程度用适应值（fitness）表示。适应值取决于个体的染色体，在算法中染色体常用一串数字表示，数字串中的一位对应一个基因。一定数量的个体组成一个群体。对所有个体进行选择、交叉和变异等操作，生成新的群体，称为新一代遗传算法计算程序的流程可以表示如下： 第一步准备工作 （1）选择合适的编码方案，将变量（特征）转换为染色体（数字串，串长为m）。通常用二进制编码。 （2）选择合适的参数，包括群体大小（个体数M）、交叉概率PC和变异概率Pm。 （3）确定适应值函数f（x）。f（x）应为正值。 第二步形成一个初始群体（含M个个体）。在边坡滑裂面搜索问题中，取已分析的可能滑裂面组作为初始群体。 第三步对每一染色体（串）计算其适应值fi，同时计算群体的总适应值。 第四步选择 1.遗传算法解决TSP 问题（附matlab源程序） 2.知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市 3.只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其 4.旅行路线的总长度最短？ 5.用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij) 6.是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶 7.点且每个顶点只通过一次的具有最短距离的回路。 8.这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商 9.问题(dij≠dji,,任意i,j=1,2,3，…,n)。 10.若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2,t3,…,ti,…,tn),其中 11.ti∈v(i=1,2,3,…,n)，且记tn+1= t1，则旅行商问题的数学模型为： 12.min l=σd(t(i),t(i+1)) （i=1,…,n） 13.旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目 14.与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法 15.求其近似解。 16.遗传算法： 17.初始化过程：用v1,v2,v3,…,vn代表所选n个城市。定义整数pop-size作为染色体的个数 18.，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。 19.适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i),t(i+1)). 20.评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中 21.的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被 22.选择产生后台的机会要大，设alpha∈(0,1)，本文定义基于序的评价函数为eval(vi)=al 23.pha*(1-alpha).^(i-1) 。[随机规划与模糊规划] 24.选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个 25.染色体。赌轮是按每个染色体的适应度进行选择染色体的。 26.step1 、对每个染色体vi,计算累计概率qi，q0=0;qi=σeval(vj) j=1,…,i;i=1, 27.…pop-size. 28.step2、从区间(0,pop-size)中产生一个随机数r； 29.step3、若qi-1 step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。 30.grefenstette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的 31.染色体，本文采用grefenstette编码《遗传算法原理及应用》可以避免这种情况的出现 32.。所谓的grefenstette编码就是用所选队员在未选（不含淘汰）队员中的位置，如： 33.8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1 34.对应： 35.8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。 36.交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从到pop-size重复以下过 37.程：从[0，1]中产生一个随机数r，如果r 将所选的父代两两组队，随机产生一个位置进行交叉，如： 38.8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1 39. 6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1 40.交叉后为： 41.8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1 42. 6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1 43.变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在r 选择多个染色体vi作为父代。对每一个 选择的父代，随机选择多个位置，使其在每位置 用遗传算法解决旅行商问题 姓名：王晓梅 学号：1301281 班级：系统工程6班 一、问题背景 有一个销售员，要到n 个城市推销商品，他要找出一个包含所有n 个城市的具有最短路程的环路。 现在假设有10个城市，他们之间的距离如下。 { 0, 107, 241, 190, 124, 80, 316, 76, 152, 157}, { 107, 0, 148, 137, 88, 127, 336, 183, 134, 95}, { 241, 148, 0, 374, 171, 259, 509, 317, 217, 232}, { 190, 137, 374, 0, 202, 234, 222, 192, 248, 42}, { 124, 88, 171, 202, 0, 61, 392, 202, 46, 160}, { 80, 127, 259, 234, 61, 0, 386, 141, 72, 167}, { 316, 336, 509, 222, 392, 386, 0, 233, 438, 254}, { 76, 183, 317, 192, 202, 141, 233, 0, 213, 188}, { 152, 134, 217, 248, 46, 72, 438, 213, 0, 206}, { 157, 95, 232, 42, 160, 167, 254, 188, 206, 0} 将这10个城市分别编码为0,1,2,3,4,5,6,7,8,9。要求走完这10个城市，目标是使走的距离最短。 二、建立模型 ),...,1,(1) ,...,1,(1. .)(min 11 11n j j i n i j i t s j i n j ij n i ij ij n i n j ij x x d x =≠==≠=≠∑∑∑∑==== 三、设计算法 1、种群初始化 （1）一条染色体的初始化 10个城市分别对应0~9这十个数，每个染色体代表一个解决方法，即0~9这十个数的一种排序方式，可随机产生一个数，用取余的方法得到一个0~9的数，依次得到与前面不重复的十个数，构成一个染色体。 （2）种群的初始化 这里假设种群有100个染色体，也就是循环100次染色体的初始化可得到一个种群。 基于聚类的遗传算法解决旅行商问题 摘要：遗传算法（GA）是解决旅行商问题（TSPs）的有效方法，然而，传统的遗传算法（CGA）对大规模旅行商问题的求解效果较差。为了克服这个问题，本文提出了两种基于聚类的改进的遗传算法，以寻找TSPs的最佳结果。它的主要过程是聚类、组内演进和组间连接操作。聚类包括两种方法来将大规模TSP划分为若干子问题，一种方法是k-均值（k-means）聚类算法，另一种是近邻传播（AP）聚类算法。每个子问题对应于一个组。然后我们使用GA找出每个子问题的最短路径长度。最后，我们设计一个有效的连接方法将所有这些组合成为一个，以得到问题的结果。我们尝试在基准实例上运行一组实验，用来测试基于k-means 聚类（KGA）和基于AP聚类（APGA）遗传算法的性能。实验结果表明了它们有效性和高效的性能。将结果与其他聚类遗传算法进行比较，表明KGA和APGA具有更强的竞争力和有效性。 关键词：大规模旅行商问题；遗传算法；聚类；k-means聚类；AP聚类 一、引言 旅行商问题（TSP ）是在所有城市搜索最短哈密尔顿路线的问题。TSP 是众所周知的NP-hard 问题。它有许多现实世界的应用[1,2]，如规划调度、物流配送、计算机网络和VLSI 路由。近年来研究人员已经研究了不同类型的TSP [3-6]。 TSP 问题可以用如下方式描述：有N 座城市，给出城市之间的距离矩阵为 () d ij N N D ?=。TSP 问题的要求是从所有路径中找到最短路径。如果()i π被定义 为在步骤 ( 1,,)i i N = 中访问的城市，则路线可以被看作城市从1到N 的循环排列。路线的表达式如下： 1 ()(1)()(1)1 minimize N i i N i f d d πππππ-+== +∑ （1） 如果对于1i j N ≤≤、，距离满足d d ij ji = ，则这种情况是对称TSP 。 TSP 可以模型化为加权图。每个顶点代表一个城市，每个边缘连接两个城市。 边的权重表示两个相连的城市之间的距离。现在一个TSP 问题实际上是一个哈密尔顿回路，最优的TSP 路径是最短的哈密顿回路。 用于求解TSP 的算法可以概括为两类，精确算法和启发式算法。精确的算法确保最终解决方案是最优的。分支切割算法是这一类中的典型示例[7,8]。这些算法的关键问题是它们相当复杂，并且在计算机性能方面非常苛刻[9]。自引入模拟退火[10]和禁忌搜索[11]以来，启发式算法有可能突破局限，从而找到路径的局部最优解。在过去的二十年中，提出了大量的自然启发或群体智能方法，例如蚁群算法[12,13]，粒子群算法[14]和遗传算法[15,16]来解决TSP 问题 。 遗传算法（GA ）是一种通过模拟自然演化过程来搜索最优解解决大规模搜索问题（例如TSP 问题）的有效方法，GA 的目的是通过几个遗传操作，如选择、交叉和突变获得大规模搜索问题的近似解。与其他精确搜索算法相比，其优点主要是通过使用群体的信息而不是仅仅一个个体来实现搜索[5]。除了上述内容之外，GA 通过适应度函数的数值来评估个体的质量，减少当使用启发式算法时被浸入在局部最优解中的风险。 虽然GA 是解决TSPs 的有效方法，但是，随着旅行城市的数量增长，经典遗传算法效果较差。为了使TSP 问题变得更容易并且可以有效地解决大规模TSP ， 人工智能实验报告 实验六遗传算法实验II 一、实验目的： 熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP 问题的流程并测试主要参数对结果的影响。 二、实验原理： 旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解。要求利用遗传算法求解TSP问题的最短路径。 三、实验内容： 1、参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗传算法求解不同规模TSP问题的算法性能。 2、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。 3、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。 4、上交源代码。 四、实验报告要求： 1、画出遗传算法求解TSP问题的流程图。 开始初始化种群（随机产生城市坐标）确定种群规模、迭代次数、个体选择方式、交叉概率、变异概率等 计算染色体适应度值（城市之间的欧氏距离）按某个选择概率选择个体YES个体交叉个体变异P<迭代总次数N输入适应度最高的结 基于遗传算法的TSP问题解决 —余小欢B07330230 概述：TSP问题是一个经典的运筹学的组合优化问题，针对此问题，研究人员提出了个中各样的算法，主要有贪婪算法，遗传算法，混沌搜索算法等。在本文中分别用贪婪算法和遗传算法去解决30个城市的最短路径问题，并把两者得到了最优解进行比较，发现用遗传算法解决TSP问题非常具有优越性，同时在文章的最后提出了对此遗传算法进行改进的方向。 1.贪婪算法 x=[18 87 74 71 25 58 4 13 18 24 71 64 68 83 58 54 51 37 41 2 7 22 25 62 87 91 83 41 45 44]; y=[54 76 78 71 38 35 50 40 40 40 42 44 60 58 69 69 62 67 84 94 99 64 60 62 32 7 38 46 26 21 35]; a=zeros(30,30); for i=1:30 for j=1:30 a(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2); %求取距离矩阵的值end a(i,i)=1000; %主对角线上的元素置为1000作为惩罚 end b=0; c=zeros(30); for j=1:30 [m,n]=min(a(:,j)); b=b+m; %得到的b值即为贪婪最佳路径的总距离 a(n,:)=1000; %已经选择的最小值对应的行的所有值置为1000作为惩罚 c(j)=n; end x1=zeros(30); y1=zeros(30); for t=1:30 x1(t)=x(c(t)); y1(t)=y(c(t)); end plot(x1,y1,'-or'); xlabel('X axis'), ylabel('Y axis'), title('ì°à·?·??'); axis([0,1,0,1]); axis([0,100,0,100]); axis on 用贪婪算法得出的最佳路径走遍30个城市所走的路程为449.3845km 其具体的路径图如下： 2.遗传算法 1主函数部分 clc; clear all; 3 旅行商问题 3.1 旅行商问题概述 3.1.1 旅行商问题的定义和数学模型 ① 定义 旅行商问题(Traveling Salesman Problem ，简记TSP)是组合数学中一个古老而又困难的问题，它易于描述但至今尚未彻底解决，现己归入所谓的NP 完全问题类，经典提法为： 有一货物推销员要去若干个城市推销货物，从城市1出发，经其余各城市一次，然后回到城市1，问选择怎样的行走路线，才能使总行程最短（各城市间距离为己知）。 该问题在图论的意义下就是所谓的最小Hamilton 圈问题，由于在许多领域中都有着广泛的应用，因而寻找其实际而有效的算法就显得颇为重要了。遗憾的是，计算复杂性理论给予我们的结论却是，这种可能性尚属未知。 若设城市数目为n 时，那么组合路径数则为(n-1)!。很显然，当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈指数级数规律急剧增长，以至达到无法计算的地步，这就是所谓的“组合爆炸问题”。假设现在城市的数目增为20个，组合路径数则为(20-1)! ，如此庞大的组合数目，若计算机以每秒检索1000万条路线的速度计算，也需要花上386年的时间。 尽管现在计算机的计算速度大大提高，而且已有一些指数级的算法可精确地求解旅行商问题，但随着它们在大规模问题上的组合爆炸，人们退而求其次，转向寻找近似算法或启发式算法，经过几十年的努力，取得了一定的进展。 ② 数学模型 设(,)G V E =为赋权图，{1,2,}V n ="为顶点集，E 为边集，各顶点间距离为ij c ，已知(0,,,)ij ij c c i j V >=+∞∈，并设 则旅行商问题的数学模型可写成如下的线性规划形式： ij ij i j MinZ c x ≠=∑ 1,(,)0,ij i j x ?=??边在最优路线上其它 #include "stdio.h" #include "stdlib.h" #include "conio.h" #include "math.h" #include "time.h" #define num_C 10 //城市个数 #define N 100 //群体规模为100 #define pc 0.9 //交叉概率为0.9 #define pm 0.1 //变异概率为10% #define ps 0.6 //进行选择时保留的比例 #define genmax 200 //最大代数200 int RandomInteger(int low,int high); void Initial_gen(struct unit group[N]); void Sort(struct unit group[N]); void Copy_unit(struct unit *p1,struct unit *p2); int search_son(int son[num_C],int k); void Cross(struct unit *p1,struct unit *p2); void Varation(struct unit group[N],int i); void Evolution(struct unit group[N]); void Calculate_cost(struct unit *p); void Print_optimum(struct unit group[N]); /* 定义个体信息*/ typedef struct unit { int path[num_C]; //个体的路径信息 int cost; //个体代价值 }; struct unit group[N]; //种群变量group int num_gen=0; //记录当前达到第几代 /***************************************************************************/ /* 城市间的距离信息：*/ /* 北京天津武汉深圳长沙成都杭州西安拉萨南昌*/ /* (0) (1) (2) (3) (4) (5) (6) (7) (8) (9) */ /* 北京(0) 0 118 1272 2567 1653 2097 1425 1177 3947 1574 */ /* 天津(1) 118 0 1253 2511 1633 2077 1369 1157 3961 1518 */ /* 武汉(2) 1272 1253 0 1462 380 1490 821 856 3660 385 */ /* 深圳(3) 2567 2511 1462 0 922 2335 1562 2165 3995 933 */ /* 长沙(4) 1653 1633 380 922 0 1700 1041 1135 3870 456 */ /* 成都(5) 2097 2077 1490 2335 1700 0 2311 920 2170 1920 */ /* 杭州(6) 1425 1369 821 1562 1041 2311 0 1420 4290 626 */ /* 西安(7) 1177 1157 856 2165 1135 920 1420 0 2870 1290 */ /* 拉萨(8) 3947 3961 3660 3995 3870 2170 4290 2870 0 4090 */ /* 南昌(9) 1574 1518 385 993 456 1920 626 1290 4090 0 */ /***************************************************************************/ 遗传算法求解TSP 问题MATLAB 实现 摘要：旅行商问题（TSP ）是一个经典的优化组合问题，本文采用遗传算法来求解TSP 问题，深入讨论了遗传算法解决TSP 问题的求解过程，并通过MATLAB 对算法进行了实现，最后对实验结果进行分析，并与粒子群算法进行对比和分析。 关键字：TSP ；遗传算法；粒子群算法 0.引言 旅行商问题是一个经典的优化组合问题，它可以扩展到很多问题，如电路布线、输油管路铺设等，但是，由于TSP 问题的可行解数目与城市数目N 是成指数型增长的，是一个NP 难问题，因而一般只能近似求解，遗传算法（GA ）是求解该问题的较有效的方法之一，当然还有如粒子群算法，蚁群算法，神经网络算法等优化算法也可以进行求解。遗传算法是美国学者Holland 根据自然界“物竞天择，适者生存”现象而提出的一种随机搜索算法，本文采用MATLAB 来实现遗传算法解决TSP 问题。 1.旅行商问题 旅行商问题可以具体描述为：已知n 个城市之间的相互距离，现有一个推销员从某一个城市出发，必须遍访这n 个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。用图论术语来表示，就是有一个图g=(v,e),其中v 是定点5，e 是边集，设d=(dij)是有顶点i 和顶点j 之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的最短距离的回路。若对与城市v={v1,v2,v3…vn}的一个访问顺序为t=(t1,t2,t3…,tn)，其中ti ∈v(i=1,2,..n),且记tn+1=t1,则旅行上问题的数学模型为式1： min ((),(1))(1,....,)I d t i t i i n δ =+ = （1） 2.遗传算法与粒子群算法 2.1遗传算法 遗传算法的基本原理是通过作用于染色体上的基因寻找好的染色体来求解问题，它需要对算法所产生的每个染色体进行评价，并基于适应度值来选择染色体，使适应性好的染色体有更多的繁殖机会，在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗产操作后的个体集合形成下一代新的种群，对这个新的种群进行下一轮的进化。 2.2遗传算法的过程 遗传算法的基本过程是： 1. 初始化群体。 2. 计算群体上每个个体的适应度值 3. 由个体适应度值所决定的某个规则选择将进入下一代个体。 4. 按概率Pc 进行交叉操作。 5. 按概率Pm 进行变异操作。 6. 没有满足某种停止条件，则转第2步，否则进入第7步。 %TSP问题（又名：旅行商问题，货郎担问题）遗传算法通用matlab程序 %D是距离矩阵，n为种群个数,建议取为城市个数的1~2倍， %C为停止代数，遗传到第C代时程序停止,C的具体取值视问题的规模和耗费的时间而定%m为适应值归一化淘汰加速指数,最好取为1,2,3,4 ,不宜太大 %alpha为淘汰保护指数,可取为0~1之间任意小数,取1时关闭保护功能,最好取为0.8~1.0 %R为最短路径,Rlength为路径长度 function [R,Rlength]=geneticTSP(D,n,C,m,alpha) [N,NN]=size(D); farm=zeros(n,N);%用于存储种群 for i=1:n farm(i,:)=randperm(N);%随机生成初始种群 end R=farm(1,:);%存储最优种群 len=zeros(n,1);%存储路径长度 fitness=zeros(n,1);%存储归一化适应值 counter=0; while counter 实验六遗传算法求解TSP问题 一、实验目的 熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。 二、实验内容 1、参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗传算法求解不同规模TSP问题的算法性能。 2、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。 3、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。 4、上交源代码。 三、遗传算法求解TSP问题的流程图 四、遗传算法求解不同规模的TSP问题的算法性能 （1）遗传算法执行方式说明： 适应度值计算方法：当前路线的路径长度 ●个体选择概率分配方法：适应度比例方法 ●选择个体方法：轮盘赌选择 ●交叉类型：PMX交叉 ●变异类型: 两点互换变异 （2）实验模拟结果： 图1-1 （3）分析 由图1-1可知，遗传算法执行时间随着TSP问题规模的增大而增大，并且大致为线性增长。 五、不同参数下的计算结果对比 （1）种群规模对算法结果的影响 实验次数：10 最大迭代步数:100 交叉概率：0.85 变异概率：0.15 如表1-1或3-1-0-9-2-4-8-5-7-6，注意到这是一圈，顺时针或者逆时针都可以。当种群规模为10，20时，并没有找到最优解。 （2）交叉概率对算法结果的影响 实验次数：15 种群规模：25 最大迭代步数:100 变异概率：0.15 实验结果： 在该情况下，交叉概率过低将使搜索陷入迟钝状态，得不到最优解。 （3）变异概率对算法结果的影响 实验次数：10 种群规模：25 最大迭代步数:100 交叉概率：0.85 实验结果： 又表1-3可知，当变异概率过大或过低都将导致无法得到最优解。注：（2）（3）的实验数据与（1）的实验数据不同，详见附录。 遗传算法解决TSP问题（C++版） 遗传算法流程： 交叉，编译，计算适应度，保存最优个体。 其中交叉过程是选择最优的两个染色体进行交叉操作，本文采用的是轮盘赌算法。 #include 实验五：用遗传算法解决旅行商问题 一．实验内容 使用MPI编写一个并行程序，利用遗传算法来解决旅行商问题。 二．实验原理 1) 旅行商问题概述 旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。旅行商问题可以归纳为寻找加权图中的最短回路问题。 由于TSP是NP问题，我们无法对该问题寻找多项式时间算法，因此只能构造一些启发式近似算法来求得问题的较优解。在这里，我们采用遗传算法来找出近似最佳路径。 2) 遗传算法概述 遗传算法（Genetic Algorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现。 初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。 3) 遗传算法并行化 在遗传算法中，种群的规模往往很大，并且要经过多代的进化和变异，因此其需要的计算量会很大。使用并行化方法可以极大的提高计算速率，并有利 遗传算法的TSP (旅行商问题)的求解 学生姓名：宗满意 指导老师：乔立红 摘要 TSP 问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种常用方法。本文针对解决TSP 问题,在MATLAB中用遗传算法施行对TSP问题进行了求解，进行了选择、交叉和变异算子进行了算法设计，最后在MATLAB软件上进行编程实现。最后探讨了遗传算法解决旅行商问题自身具备的特点[1]。 关键词：遗传算法；TSP问题；MATLAB软件 SOLVING TSP (Travelling Salesman Problem ) BASED ON GENETIC ALGORITHM Author : Zong Man-yi Tutor : Qiao Li-hong Abstract TSP( Traveling Salesman Problem) is a typical NP complete problem ,genetic algorithm is the perfect method for solving NP complete problem. This paper use genetic algorithm in the MATLAB software to solve the a typical TSP problem . It probes into the realization of genetic operator program through TSP solving by genetic algorithm , design the each function of each genetic operator(select, intercross,mutate).Finally ,We programm in Matlab language and discuss the characteristic of genetic algorithm in solving TSP Key words : genetic algorithm; TSP Matlab ; 题目：用遗传算法求解中国34 个省会TSP 问题源代码分享在本人博客：https://www.docsj.com/doc/6817398896.html, 2012-1-17 智能控制技术及其应用 大作业 专业: 控制工程 学号：XXXXXX 姓名：XXX 用遗传算法求解中国34 个省会TSP 问题 一、TSP 问题的描述 旅行商问题（TSP）可以具体描述为：已知n 个城市之间的相互距离，现有一个推销员从某一个城市出发，必须遍访这n 个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。 现给出中国34 个省会数据，要求基于此数据使用遗传算法解决该TSP 问题。 图1 中国34 省会位置 city = 1.西藏 2.云南 3.四川 4.青海 5.宁夏 6.甘肃 7.内蒙古 8.黑龙江 9.吉林 10.辽宁11.北京12 天津13.河北14.山东15.河南16.山西17. 陕西18.安徽 19.江苏20.上海21.浙江22.江西23.湖北24.湖南25,贵州26. 广西27.广东 28.福建29.海南30.澳门31.香港32.台湾33.重庆34.新疆 像素坐标如下： Columns 1 through 11 100 187 201 187 221 202 258 352 346 336 290 211 265 214 158 142 165 121 66 85 106 127 Columns 12 through 22 297 278 296 274 265 239 302 316 334 325 293 135 147 158 177 148 182 203 199 206 215 233 Columns 23 through 33 280 271 221 233 275 322 250 277 286 342 220 216 238 253 287 285 254 315 293 290 263 226 Column 34实验六：遗传算法求解TSP问题实验分析
实验报告：遗传算法在解决旅行商问题的应用
遗传算法解决TSP问题
遗传算法解决TSP问题的matlab程序
用遗传算法解决旅行商问题
基于聚类的遗传算法解决旅行商问题
遗传算法求解TSP问题实验报告推荐文档
基于遗传算法的TSP问题解决
改进的遗传算法求解TSP问题_3旅行商问题_24_34
遗传算法解决10城市TSP问题程序源代码
遗传算法求解TSP问题MATLAB实现
TSP遗传算法
遗传算法求解TSP问题
遗传算法解决TSP问题(C++)
实验五用遗传算法解决旅行商问题
遗传算法的TSP (旅行商问题)的求解
用遗传算法求解中国34个省会TSP的问题
- 遗传算法解决TSP问题的matlab程序
- 基于遗传算法的TSP问题解决
- 遗传算法求解TSP问题
- 遗传算法的TSP (旅行商问题)的求解
- 实验六：遗传算法求解TSP问题实验分析
- 基于聚类的遗传算法解决旅行商问题
- 遗传算法求解TSP问题MATLAB实现
- 遗传算法解决TSP问题(C++)
- 用遗传算法求解中国34个省会TSP的问题
- 遗传算法解决TSP问题
- 遗传算法解决TSP问题
- 遗传算法求解旅行商问题-Java实现方法
- 实验五用遗传算法解决旅行商问题
- 用遗传算法解决旅行商问题
- 遗传算法解决10城市TSP问题程序源代码
- 遗传算法求解TSP问题
- 用遗传算法解决旅行商问题
- 实验报告：遗传算法在解决旅行商问题的应用
- 完整word版遗传算法求解TSP问题实验报告
- TSP遗传算法