下载文档原格式
用于求解TSP问题的遗传算法改进一、TSP问题简介TSP问题，全称Traveling Salesman Problem，即旅行商问题。
所谓TSP问题是指，给定一些点和每一对点之间的距离，求出一条遍历每个点恰好一次的最短路径，该问题的解决方法对实际问题中的路径规划和优化有着很大的参考价值。
二、遗传算法的基本思想遗传算法，是模拟自然界中生物遗传进化过程的一种演化计算方法。
它通过模拟生物的繁殖、变异、适应性等生命过程来寻找问题的最优解。
其基本的过程如下：1. 初始化：随机生成一个初始群体，每个个体表示一种可能的解决方案。
2. 选择：根据适应度函数，选择一定数量的优秀个体作为繁殖的父亲。
3. 交叉：将所选父亲进行交叉操作，生成新的子代个体。
4. 变异：对于一部分子代个体，进行变异操作。
5. 替换：用新的子代个体替换掉一部分原有的个体，形成新一代群体。
6. 结束条件：当某种条件达到时结束算法，否则返回步骤二。
在TSP问题中，遗传算法的基本实现方法如下：1.初始化：随机生成一个初始群体，每个个体表示一个解决方案，其中每个基因表示一个城市的编号。
例如，假设有10个城市，则每个个体就是由这10个城市编号随机排列组成的，例如：1-2-5-8-4-3-7-9-6-10等。
2.适应度函数：对于每个个体，计算其总路程，将总路程作为适应度函数的值。
4.交叉：将所选父亲进行交叉操作，生成新的子代个体，交叉方式一般有：顺序交叉法、部分映射交叉法、环形交叉法、边交叉法等。
5.变异：对于一部分子代个体，进行变异操作，变异的方式一般是：交换变异、倒位变异、随机抽样变异等。
7.结束条件：当达到一定条件时结束算法，比如迭代次数达到上限或者群体的适应度达到一定的水平。
传统的遗传算法在求解TSP问题时，存在一些问题：1.收敛速度慢：由于集合了交叉、变异等算子，每一代都要进行大量的计算，所以收敛速度慢。
2.易受陷入局部最优解：由于遗传算法采用的是局部搜索策略，所以可能会陷入到局部最优解中。
实验六：遗传算法求解TSP问题实验2篇第一篇：遗传算法的原理与实现1. 引言旅行商问题（TSP问题）是一个典型的组合优化问题，它要求在给定一组城市和每对城市之间的距离后，找到一条路径，使得旅行商能够在所有城市中恰好访问一次并回到起点，并且总旅行距离最短。
遗传算法作为一种生物启发式算法，在解决TSP问题中具有一定的优势。
本实验将运用遗传算法求解TSP问题，以此来探讨和研究遗传算法在优化问题上的应用。
2. 遗传算法的基本原理遗传算法是模拟自然界生物进化过程的一种优化算法。
其基本原理可以概括为：选择、交叉和变异。
（1）选择：根据问题的目标函数，以适应度函数来评估个体的优劣程度，并按照适应度值进行选择，优秀的个体被保留下来用于下一代。
（2）交叉：从选出的个体中随机选择两个个体，进行基因的交换，以产生新的个体。
交叉算子的选择及实现方式会对算法效果产生很大的影响。
（3）变异：对新生成的个体进行基因的变异操作，以保证算法的搜索能够足够广泛、全面。
通过选择、交叉和变异操作，不断迭代生成新一代的个体，遗传算法能够逐步优化解，并最终找到问题的全局最优解。
3. 实验设计与实施（1）问题定义：给定一组城市和每对城市之间的距离数据，要求找到一条路径，访问所有城市一次并回到起点，使得旅行距离最短。
（2）数据集准备：选择适当规模的城市数据集，包括城市坐标和每对城市之间的距离，用于验证遗传算法的性能。
（3）遗传算法的实现：根据遗传算法的基本原理，设计相应的选择、交叉和变异操作，确定适应度函数的定义，以及选择和优化参数的设置。
（4）实验流程：a. 初始化种群：随机生成初始种群，每个个体表示一种解（路径）。
b. 计算适应度：根据适应度函数，计算每个个体的适应度值。
c. 选择操作：根据适应度值选择一定数量的个体，作为下一代的父代。
d. 交叉操作：对父代进行交叉操作，生成新的个体。
e. 变异操作：对新生成的个体进行变异操作，以增加搜索的多样性。
利⽤遗传算法求解TSP问题⼀、摘要TSP问题是指给定平⾯上N个点及每点的坐标，求⼀条路径，遍历所有的点并回到起点，使这条路径长度最⼩。
TSP问题是⼀个组合优化问题。
该问题可以被证明具有NPC计算复杂性。
因此，任何能使该问题的求解得以简化的⽅法，都将受到⾼度的评价和关注。
遗传算法是⼈⼯智能⽅法的⼀种，⽤于求解各种传统⽅法不⽅便求解或耗时很长的问题。
下⾯给出遗传算法求解TSP问题的步骤。
在传统遗传算法求解TSP的基础上，提出了⼀种新的编码⽅式，并且讨论了⼀种优化⽅法的可⾏性。
本次实验的程序⾸先在matlab上验证了基本的算法，然⽽由于matlab运⾏较慢，故⼜移植到C++平台上，经过测试，实验结果良好。
⼆、算法实现遗传算法的实现主要包括编码、选择、交叉、编译、将个体放⼊新种群这么⼏个步骤，经过很多代的编译求解，以逼近最优解。
下⾯讨论每⼀个步骤的实现，其中编码⽅式是我在考虑了传统编码⽅式不利于计算的缺点下，重新设计的⼀种全新的编码⽅式。
编码在传统TSP问题中，编码可以直接采⽤⼆进制编码或⾃然编码的形式，⽐如直接把城市转化成（2,5,4,1,3,6）的形式，表⽰从2到5到4到1到3到6最后回到起点。
但是在求解TSP问题时，如果直接采⽤此种编码⽅式，会导致在交叉或变异时出现冲突的情况。
如（2,5,4,1,3,6）和（3,5,6,1,2,4）交换后变成了（2,5,6,1,2,6）和（3,5,4,1,3,4），显然路径出现了冲突的现象，传统的解决⽅式是通过逐步调整的⽅法来消除冲突，但是这种⽅法增加了编码的复杂度，不利于问题的求解，根据问题的特点，提出了采⽤⼀种插⼊序号的编码⽅式。
假设6个城市（1,2,3,4,5,6）现在有编码（1,1,2,2,1,3），让第n个编码表⽰n放在第⼏个空格处。
那么⽣成路径的规则是⾸先取1放在第⼀个（1），然后取2放在第⼀个空格处（2，1），然后取3放在第⼆个空格处（2,3,1），然后取4放在第⼆个空格处（2,4,3,1）然后取5放在第⼀个空格处（5,2,4,3,1）最后取6放在第3个空格处（5,2,6，4,3,1）。
TSP问题的遗传算法求解一、问题描述假设有一个旅行商人要拜访N个城市，要求他从一个城市出发，每个城市最多拜访一次，最后要回到出发的城市，保证所选择的路径长度最短。
二、算法描述（一）算法简介遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，通过模拟自然进化过程搜索最优解。
遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。
这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。
（摘自百度百科）。
（二）遗传算子遗传算法中有选择算子、交叉算子和变异算子。
选择算子用于在父代种群中选择进入下一代的个体。
交叉算子用于对种群中的个体两两进行交叉，有Partial-MappedCrossover、OrderCrossover、Position-basedCrossover等交叉算子。
变异算子用于对种群中的个体进行突变。
（三）算法步骤描述遗传算法的基本运算过程如下：1.初始化：设置进化代数计数器t=0、设置最大进化代数T、交叉概率、变异概率、随机生成M个个体作为初始种群P2.个体评价：计算种群P中各个个体的适应度3.选择运算：将选择算子作用于群体。
以个体适应度为基础，选择最优个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代4.交叉运算：在交叉概率的控制下，对群体中的个体两两进行交叉5.变异运算：在变异概率的控制下，对群体中的个体两两进行变异，即对某一个体的基因进行随机调整6.经过选择、交叉、变异运算之后得到下一代群体P1。
用遗传算法求解TSP问题遗传算法（Genetic Algorithm——GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J。
Holland教授于1975年首先提出的。
J.Holland 教授和它的研究小组围绕遗传算法进行研究的宗旨有两个：抽取和解释自然系统的自适应过程以及设计具有自然系统机理的人工系统。
遗传算法的大致过程是这样的:将每个可能的解看作是群体中的一个个体或染色体，并将每个个体编码成字符串的形式，根据预定的目标函数对每个个体进行评价,即给出一个适应度值。
开始时,总是随机的产生一些个体，根据这些个体的适应度，利用遗传算子-—选择（Selection）、交叉（Crossover)、变异（Mutation)对它们重新组合，得到一群新的个体.这一群新的个体由于继承了上一代的一些优良特性，明显优于上一代，以逐步向着更优解的方向进化.遗传算法主要的特点在于：简单、通用、鲁棒性强。
经过二十多年的发展，遗传算法已经在旅行商问题、生产调度、函数优化、机器学习等领域得到成功的应用。
遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比,主要有以下特点：1、遗传算法以决策变量的编码作为运算对象.传统的优化算法往往直接决策变量的实际植本身,而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子.2、遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。
3、遗传算法使用多个点的搜索信息,具有隐含并行性。
4、遗传算法使用概率搜索技术，而非确定性规则。
遗传算法是基于生物学的,理解或编程都不太难。
下面是遗传算法的一般算法步骤:1、创建一个随机的初始状态初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样;在那里,问题的初始状态已经给定了。
遗传算法求解TSP问题实验六遗传算法求解TSP问题⼀、实验⽬的熟悉和掌握遗传算法的原理、流程和编码策略，并利⽤遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。
⼆、实验内容1、参考实验系统给出的遗传算法核⼼代码，⽤遗传算法求解TSP的优化问题，分析遗传算法求解不同规模TSP问题的算法性能。
2、对于同⼀个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。
3、增加1种变异策略和1种个体选择概率分配策略，⽐较求解同⼀TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。
4、上交源代码。
三、遗传算法求解TSP问题的流程图四、遗传算法求解不同规模的TSP问题的算法性能（1）遗传算法执⾏⽅式说明：适应度值计算⽅法：当前路线的路径长度●个体选择概率分配⽅法：适应度⽐例⽅法●选择个体⽅法：轮盘赌选择●交叉类型：PMX交叉●变异类型: 两点互换变异（2）实验模拟结果：图1-1（3）分析由图1-1可知，遗传算法执⾏时间随着TSP问题规模的增⼤⽽增⼤，并且⼤致为线性增长。
五、不同参数下的计算结果对⽐最⼤迭代步数: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实验结果：在该情况下，交叉概率过低将使搜索陷⼊迟钝状态，得不到最优解。
种群规模：25最⼤迭代步数:100交叉概率：0.85实验结果：⼜表1-3可知，当变异概率过⼤或过低都将导致⽆法得到最优解。
注：（2）（3）的实验数据与（1）的实验数据不同，详见附录。
六、不同变异策略和个体选择概率分配策略对算法结果的影响（1）两点互换变异与插⼊变异的⽐较：●试验次数（CASNUM）：10●城市数(POINTCNT):10●种群规模(POPSIZE)：100●最⼤迭代步数(GENERATIONS):100●交叉概率(PC)：0.85●变异概率(PM):0.15●选择个体⽅法：轮盘赌选择●交叉类型：PMX交叉●个体选择概率分配⽅法：适应度⽐例⽅法a.变异类型: 两点互换变异b.变异类型: 插⼊变异分析：两点互换变异20次模拟中，4次得到⾮最优解；⽽插⼊变异只有2次；插⼊变异的最好适应度平均值⽐两点互换变异⼩0.14755，最差适应度平均值和总的适应度平均值都⽐两点互换下，并且在Release下，运⾏时间前者⽐后者快218.3ms。
一、旅行商问题所谓旅行商问题(Travelling Salesman Problem , TSP)，即最短路径问题，就是在给定的起始点S到终止点T的通路集合中，寻求距离最小的通路，这样的通路成为S点到T点的最短路径。
在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路径，还需要知道某个顶点到其他任意顶点间的最短路径。
遗传算法方法的本质是处理复杂问题的一种鲁棒性强的启发性随机搜索算法，用遗传算法解决这类问题，没有太多的约束条件和有关解的限制，因而可以很快地求出任意两点间的最短路径以及一批次短路径。
假设平面上有n个点代表n个城市的位置, 寻找一条最短的闭合路径, 使得可以遍历每一个城市恰好一次。
这就是旅行商问题。
旅行商的路线可以看作是对n 个城市所设计的一个环形, 或者是对一列n个城市的排列。
由于对n个城市所有可能的遍历数目可达(n- 1)!个, 因此解决这个问题需要0(n!)的计算时间。
假设每个城市和其他任一城市之间都以欧氏距离直接相连。
也就是说, 城市间距可以满足三角不等式, 也就意味着任何两座城市之间的直接距离都小于两城市之间的间接距离。
二、遗传算法1 遗传算法介绍遗传算法是由美国J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。
通过模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。
遗传算法在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方法。
其假设常描述为二进制位串，位串的含义依赖于具体应用。
搜索合适的假设从若干初始假设的群体集合开始。
当前种群成员通过模仿生物进化的方式来产生下一代群体，如随机变异和交叉。
TSP问题的遗传算法求解一、问题描述假设有一个旅行商人要拜访N个城市，要求他从一个城市出发，每个城市最多拜访一次，最后要回到出发的城市，保证所选择的路径长度最短。
二、算法描述（一）算法简介遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，通过模拟自然进化过程搜索最优解。
遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。
这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。
（摘自百度百科）。
（二）遗传算子遗传算法中有选择算子、交叉算子和变异算子。
选择算子用于在父代种群中选择进入下一代的个体。
交叉算子用于对种群中的个体两两进行交叉，有Partial-MappedCrossover、OrderCrossover、Position-basedCrossover等交叉算子。
变异算子用于对种群中的个体进行突变。
（三）算法步骤描述遗传算法的基本运算过程如下：1.初始化：设置进化代数计数器t=0、设置最大进化代数T、交叉概率、变异概率、随机生成M个个体作为初始种群P2.个体评价：计算种群P中各个个体的适应度3.选择运算：将选择算子作用于群体。
以个体适应度为基础，选择最优个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代4.交叉运算：在交叉概率的控制下，对群体中的个体两两进行交叉5.变异运算：在变异概率的控制下，对群体中的个体两两进行变异，即对某一个体的基因进行随机调整6.经过选择、交叉、变异运算之后得到下一代群体P1。
重复以上1-6，直到遗传代数为T，以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
三、求解说明（一）优化目标给定二维数据int[][]pos用于存储各个城市的坐标，采用欧式距离代表城市之间的距离。
利用遗传算法，找到不重复遍历所有城市的路径中，所走距离最短的路径。
（二）选择算子选择算子采用轮盘赌选择，以每个个体的适应度为基础，为每个个体计算累积概率。
个体1、2、3、4的个体适应度如上图所示。
适应度计算规则：染色体代表的路径实际距离作为个体的适应度，如下（distence[x][y]表示城市x到y的距离）染色体0213，适应度为distence[0][2]+distence[2][1]+distence[1][3]+distence[3][0]qa表示个体a的累积概率，如上图所示个体1、2、3、4的累积概率分别为0.14、0.53、0.69、1随机生成一个0到1的浮点数f，若qa<f<=qb，则个体b被选中。
（三）交叉算子1.Partial-MappedCrossover（部分映射交叉）2.OrderCrossover（顺序交叉）3.Position-basedCrossover（基于位置的交叉）（四）变异算子变异算子随机进行多次，每次在个体基因序列中选择两个位置的基因进行交换。
四、参考资料基于遗传算法求解TSP问题（JAVA）用遗传算法求解TSP问题五、源代码function ga_TSP% mainly amended by Chen Zhen, 2012~2016CityNum=35; %you chan choose 10, 35, 50, 75[dislist,Clist]=tsp(CityNum);inn=35; %³õʼÖÖȺ´óСgnmax=500; %最大代数pc=0.8; %交叉概率pm=0.8; %变异概率%产生初始种群s=zeros(inn,CityNum);for i=1:inns(i,:)=randperm(CityNum);end[~,p]=objf(s,dislist);gn=1;ymean=zeros(gn,1);ymax=zeros(gn,1);xmax=zeros(inn,CityNum);scnew=zeros(inn,CityNum);smnew=zeros(inn,CityNum);while gn<gnmax+1for j=1:2:innseln=sel(p); %选择操作scro=cro(s,seln,pc); %交叉操作scnew(j,:)=scro(1,:);scnew(j+1,:)=scro(2,:);smnew(j,:)=mut(scnew(j,:),pm); %变异操作 smnew(j+1,:)=mut(scnew(j+1,:),pm);ends=smnew; %产生了新的种群[f,p]=objf(s,dislist); %计算新种群的适应度%记录当前代最好和平均的适应度[fmax,nmax]=max(f);ymean(gn)=1000/mean(f);ymax(gn)=1000/fmax;%记录当前代的最佳个体x=s(nmax,:);xmax(gn,:)=x;drawTSP(Clist,x,ymax(gn),gn,0);gn=gn+1;end[min_ymax,index]=min(ymax);drawTSP(Clist,xmax(index,:),min_ymax,index,1);figure(2);plot(ymax,'r'); hold on;plot(ymean,'b');grid;title('搜索过程');legend('最优解','平均解');fprintf('遗传算法得到的最短距离:%.2f\n',min_ymax); fprintf('遗传算法得到的最短路线');disp(xmax(index,:));end%------------------------------------------------%计算所有种群的适应度function [f,p]=objf(s,dislist)inn=size(s,1); %读取种群大小f=zeros(inn,1);for i=1:innf(i)=CalDist(dislist,s(i,:)); %计算函数值，即适应度endf=1000./f'; %取距离倒数%根据个体的适应度计算其被选择的概率fsum=0;for i=1:innfsum=fsum+f(i)^15;% 让适应度越好的个体被选择概率越高endps=zeros(inn,1);for i=1:innps(i)=f(i)^15/fsum;end%计算累积概率p=zeros(inn,1);p(1)=ps(1);for i=2:innp(i)=p(i-1)+ps(i);endp=p';end%-------------------------------------------------- %根据变异概率判断是否变异function pcc=pro(pc)test(1:100)=0;l=round(100*pc);test(1:l)=1;n=round(rand*99)+1;pcc=test(n);end%-------------------------------------------------- %“选择”操作function seln=sel(p)seln=zeros(2,1);%从种群中选择两个个体，最好不要两次选择同一个个体for i=1:2r=rand; %产生一个随机数prand=p-r;j=1;while prand(j)<0j=j+1;endseln(i)=j; %选中个体的序号if i==2&&j==seln(i-1) %%若相同就再选一次r=rand; %产生一个随机数prand=p-r;j=1;while prand(j)<0j=j+1;endendendend%------------------------------------------------%“交叉”操作function scro=cro(s,seln,pc)bn=size(s,2);pcc=pro(pc); %根据交叉概率决定是否进行交叉操作，1则是，0则否scro(1,:)=s(seln(1),:);scro(2,:)=s(seln(2),:);if pcc==1c1=round(rand*(bn-2))+1; %在[1,bn-1]范围内随机产生一个交叉位 c2=round(rand*(bn-2))+1;chb1=min(c1,c2);chb2=max(c1,c2);middle=scro(1,chb1+1:chb2);scro(1,chb1+1:chb2)=scro(2,chb1+1:chb2);scro(2,chb1+1:chb2)=middle;for i=1:chb1 %似乎有问题while find(scro(1,chb1+1:chb2)==scro(1,i))zhi=find(scro(1,chb1+1:chb2)==scro(1,i));y=scro(2,chb1+zhi);scro(1,i)=y;endwhile find(scro(2,chb1+1:chb2)==scro(2,i))zhi=find(scro(2,chb1+1:chb2)==scro(2,i));y=scro(1,chb1+zhi);scro(2,i)=y;endendfor i=chb2+1:bnwhile find(scro(1,1:chb2)==scro(1,i))zhi=logical(scro(1,1:chb2)==scro(1,i));y=scro(2,zhi);scro(1,i)=y;endwhile find(scro(2,1:chb2)==scro(2,i))zhi=logical(scro(2,1:chb2)==scro(2,i));y=scro(1,zhi);scro(2,i)=y;endendendend%--------------------------------------------------%“变异”操作function snnew=mut(snew,pm)bn=size(snew,2);snnew=snew;pmm=pro(pm); %根据变异概率决定是否进行变异操作，1则是，0则否if pmm==1c1=round(rand*(bn-2))+1; %在[1,bn-1]范围内随机产生一个变异位 c2=round(rand*(bn-2))+1;chb1=min(c1,c2);chb2=max(c1,c2);x=snew(chb1+1:chb2);snnew(chb1+1:chb2)=fliplr(x);endend%------------------------------------------------%城市位置坐标function [DLn,cityn]=tsp(n)DLn=zeros(n,n);if n==10city10=[0.4 0.4439;0.2439 0.1463;0.1707 0.2293;0.2293 0.761;0.5171 0.9414;0.8732 0.6536;0.6878 0.5219;0.8488 0.3609;0.6683 0.2536;0.6195 0.2634];%10 cities d'=2.691for i=1:10for j=1:10DLn(i,j)=((city10(i,1)-city10(j,1))^2+(city10(i,2)-city10(j,2))^2)^0.5;endendcityn=city10;endif n==35city30=[116.41667 39.91667;121.43333 34.5;117.2 39.13333;114.122.2;113.23333 23.16667;113.51667 22.3114.06667 22.61667;120.2 30.26667;106.45 29.56667;120.33333 36.06667;118.1 24.46667;119.3 26.08333;103.73333 36.03333;106.71667 26.56667;113 28.21667;118.78333 32.05;115.9 28.68333;123.38333 41.8;112.53333 37.86667;104.06667 30.66667;91 29.6;87.68333 43.76667;102.73333 25.05;108.95 34.26667;101.75 36.56667;106.26667 38.46667;122.08333 46.06667;126.63333 45.75;125.3543.88333;114.31667 30.51667;113.65 34.76667;114.48333 38.03333;109.5 18.2;110.35 20.01667;113.5 22.2];%35 citiesd'=423.741 by D B Fogelfor i=1:35for j=1:35DLn(i,j)=((city35(i,1)-city35(j,1))^2+(city35(i,2)-city35(j,2))^2)^0.5;endendcityn=city35;endif n==50city50=[31 32;32 39;40 30;37 69;27 68;37 52;38 46;31 62;30 48;21 47;25 55;16 57;17 63;42 41;17 33;25 32;5 64;8 52;12 42;7 38;5 25; 10 77;45 35;42 57;32 22;27 23;56 37;52 41;49 49;58 48;57 58;39 10;46 10;59 15;51 21;48 28;52 33;58 27;61 33;62 63;20 26;5 6;13 13;21 10;30 15;36 16;62 42;63 69;52 64;43 67]; %50 cities d'=427.855 by D B Fogelfor i=1:50for j=1:50DLn(i,j)=((city50(i,1)-city50(j,1))^2+(city50(i,2)-city50(j,2))^2)^0.5; endendcityn=city50;endif n==75city75=[48 21;52 26;55 50;50 50;41 46;51 42;55 45;38 33;33 34;45 35;40 37;50 30;55 34;54 38;26 13;15 5;21 48;29 39;33 44;15 19;16 19;12 17;50 40;22 53;21 36;20 30;26 29;40 20;36 26;62 48;67 41;62 35;65 27;62 24;55 20;35 51;30 50;45 42;21 45;36 6;6 25;11 28;26 59;30 60;22 22;27 24;30 20;35 16;54 10;50 15;44 13;35 60;40 60;40 66;31 76;47 66;50 70;57 72;55 65;2 38;7 43;9 56;15 56;10 70;17 64;55 57;62 57;70 64;64 4;59 5;50 4;60 15;66 14;66 8;43 26];%75 cities d'=549.18 by D B Fogelfor i=1:75for j=1:75DLn(i,j)=((city75(i,1)-city75(j,1))^2+(city75(i,2)-city75(j,2))^2)^0.5; endendcityn=city75;endend%------------------------------------------------%适应度函数function F=CalDist(dislist,s)DistanV=0;n=size(s,2);for i=1:(n-1)DistanV=DistanV+dislist(s(i),s(i+1));endDistanV=DistanV+dislist(s(n),s(1));F=DistanV;end%------------------------------------------------%画图function drawTSP(Clist,BSF,bsf,p,f)CityNum=size(Clist,1);for i=1:CityNum-1plot([Clist(BSF(i),1),Clist(BSF(i+1),1)],[Clist(BSF(i),2),Clist(BSF(i+1),2 )],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g');text(Clist(BSF(i),1),Clist(BSF(i),2),[' ',int2str(BSF(i))]);text(Clist(BSF(i+1),1),Clist(BSF(i+1),2),[' ',int2str(BSF(i+1))]);hold on;endplot([Clist(BSF(CityNum),1),Clist(BSF(1),1)],[Clist(BSF(CityNum),2),Clist( BSF(1),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g' );title([num2str(CityNum),'城市TSP']);if f==0&&CityNum~=10text(5,5,['第 ',int2str(p),' 代',' 最短距离为 ',num2str(bsf)]);elsetext(5,5,['最终搜索结果：最短距离 ',num2str(bsf),'，在第 ',num2str(p),' 代达到']);endif CityNum==10if f==0text(0,0,['第 ',int2str(p),' 代',' 最短距离为 ',num2str(bsf)]);elsetext(0,0,['最终搜索结果：最短距离',num2str(bsf),'，在第',num2str(p),' 代达到']);endendhold off;pause(0.05);end。
