遗传算法解决TSP问题的Matlab程序

使用Matlab进行遗传算法优化问题求解的方法引言在现代科技发展的背景下，优化算法成为解决各种问题的重要工具之一。

遗传算法作为一种生物启发式算法，具有全局寻优能力和适应性强的特点，在许多领域中被广泛应用。

本文将介绍如何使用Matlab进行遗传算法优化问题求解，包括问题建模、遗传算子设计、遗传算法编码、适应度评价和求解过程控制等方面。

一、问题建模在使用遗传算法求解优化问题之前，我们首先需要将问题定义为数学模型。

这包括确定问题的目标函数和约束条件。

例如，假设我们要最小化一个多变量函数f(x)，其中x=(x1,x2,...,xn)，同时还有一些约束条件g(x)<=0和h(x)=0。

在Matlab中，我们可通过定义一个函数来表示目标函数和约束条件。

具体实现时，我们需要在目标函数和约束函数中设置输入参数，通过调整这些参数进行优化。

二、遗传算子设计遗传算法的核心是遗传算子的设计，包括选择（Selection）、交叉（Crossover）、变异（Mutation）和替代（Replacement）等。

选择操作通过一定的策略从种群中选择出适应度较高的个体，作为进行交叉和变异的父代个体。

交叉操作通过将两个父代个体的基因片段进行交换，产生新的子代个体。

变异操作通过改变个体某些基因的值，引入新的基因信息。

替代操作通过选择适应度较低的个体将其替换为新产生的子代个体。

三、遗传算法编码在遗传算法中，个体的编码方式决定了问题的解空间。

常见的编码方式有二进制编码和实数编码等。

当问题的变量是二进制形式时，采用二进制编码。

当问题的变量是实数形式时，采用实数编码。

在Matlab中，我们可以使用矩阵或向量来表示个体的基因型，通过制定编码方式来实现遗传算法的编码过程。

四、适应度评价适应度评价是遗传算法中判断个体优劣的指标。

在适应度评价过程中，我们将问题的目标函数和约束条件应用于个体的解，计算得到一个适应度值。

适应度值越大表示个体越优。

利⽤遗传算法求解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）。

报告题目：基于Matlab的遗传算法解决TSP问题说明：该文包括了基于Matlab的遗传算法解决TSP问题的基本说明，并在文后附录了实现该算法的所有源代码。

此代码经过本人的运行，没有发现错误，结果比较接近理论最优值，虽然最优路径图有点交叉。

因为本人才疏学浅，本报告及源代码的编译耗费了本人较多的时间与精力，特收取下载积分，还请见谅。

若有什么问题，可以私信，我们共同探讨这一问题。

希望能对需要这方面的知识的人有所帮助！1.问题介绍旅行商问题(Traveling Salesman Problem，简称TSP)是一个经典的组合优化问题。

它可以描述为：一个商品推销员要去若干个城市推销商品，从一个城市出发，需要经过所有城市后，回到出发地，应如何选择行进路线，以使总行程最短。

从图论的角度看，该问题实质是在一个带权完全无向图中。

找一个权值最小的Hemilton回路。

其数学描述为：设有一个城市集合其中每对城市之间的距离(),i j d c c R +∈，求一对经过C中每个城市一次的路线()12,,n c c c ΠΠΠ⋯使()()()1111min ,,n i n i i d c c d c c −ΠΠΠΠ+=+∑其中()12,,12n n ΠΠΠ⋯⋯是，的一个置换。

2.遗传算法2.1遗传算法基本原理遗传算法是由美国J.Holland 教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。

遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。

遗传算法，在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方法。

遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、负载平衡、电磁系统设计、生物科学、社会科学等方面都得到了应用。

matlab中的遗传算法【原创版】目录一、引言二、遗传算法的基本原理1.种群概念2.适应度函数3.选择操作4.交叉操作5.变异操作三、MATLAB 中遗传算法的实现1.准备工作2.遗传算法的实现四、遗传算法的应用案例1.旅行商问题2.装载问题五、遗传算法的优缺点六、结论正文一、引言遗传算法（Genetic Algorithm，GA）是一种模拟自然界生物进化过程的优化算法，其主要思想是将进化过程中的自然选择、交叉和变异等遗传操作应用到问题的求解过程中，从而实现对问题的优化求解。

遗传算法在解决复杂问题、非线性问题以及大规模问题等方面具有较强的优势，因此在各个领域得到了广泛的应用。

本文将介绍遗传算法的基本原理以及在MATLAB 中的实现。

二、遗传算法的基本原理1.种群概念遗传算法以一个种群作为优化过程的载体。

种群中的个体代表问题的解，每个个体由一组参数表示。

在优化过程中，种群会不断进化，最终收敛到问题的最优解。

2.适应度函数适应度函数是遗传算法的核心部分，用于评价种群中个体的优劣。

适应度函数的取值范围为 [0, 1]，其中 1 表示最优解，0 表示最劣解。

在遗传算法的优化过程中，适应度函数用于选择优秀的个体，从而指导种群的进化。

3.选择操作选择操作是基于适应度函数的一种选择策略，用于选择下一代的父代个体。

常见的选择方法有轮盘赌选择、锦标赛选择等。

4.交叉操作交叉操作是遗传算法中产生新个体的主要方式，通过将选中的优秀个体进行交叉操作，产生具有更好适应度的新个体。

常见的交叉方法有单点交叉、多点交叉、均匀交叉等。

5.变异操作变异操作是在遗传算法中引入随机性的一种方式，通过随机改变某些基因的值，使新个体在进化过程中具有一定的多样性。

变异操作的强度由变异概率控制。

三、MATLAB 中遗传算法的实现1.准备工作在 MATLAB 中实现遗传算法，首先需要定义适应度函数、选择操作、交叉操作和变异操作等。

此外，还需要设置遗传算法的参数，如迭代次数、种群大小、交叉概率、变异概率等。

遗传算法matlab程序代码遗传算法是一种优化算法，用于在给定的搜索空间中寻找最优解。

在Matlab中，可以通过以下代码编写一个基本的遗传算法：% 初始种群大小Npop = 100;% 搜索空间维度ndim = 2;% 最大迭代次数imax = 100;% 初始化种群pop = rand(Npop, ndim);% 最小化目标函数fun = @(x) sum(x.^2);for i = 1:imax% 计算适应度函数fit = 1./fun(pop);% 选择操作[fitSort, fitIndex] = sort(fit, 'descend');pop = pop(fitIndex(1:Npop), :);% 染色体交叉操作popNew = zeros(Npop, ndim);for j = 1:Npopparent1Index = randi([1, Npop]);parent2Index = randi([1, Npop]);parent1 = pop(parent1Index, :);parent2 = pop(parent2Index, :);crossIndex = randi([1, ndim-1]);popNew(j,:) = [parent1(1:crossIndex),parent2(crossIndex+1:end)];end% 染色体突变操作for j = 1:NpopmutIndex = randi([1, ndim]);mutScale = randn();popNew(j, mutIndex) = popNew(j, mutIndex) + mutScale;end% 更新种群pop = [pop; popNew];end% 返回最优解[resultFit, resultIndex] = max(fit);result = pop(resultIndex, :);以上代码实现了一个简单的遗传算法，用于最小化目标函数x1^2 + x2^2。

用遗传算法解决TSP问题设计思路：1.初始化城市距离采用以城市编号（i,j=1代表北京，=2代表上海，=3代表天津，=4代表重庆，=5代表乌鲁木齐）为矩阵行列标的方法，输入任意两个城市之间的距离，用矩阵city表示，矩阵中的元素city(i,j)代表第i个城市与第j个城市间的距离。

2.初始化种群通过randperm函数，生成一个一维随机向量（是整数1，2，3，4，5的任意排列），然后将其赋给二维数组group的第一列，作为一个个体。

如此循环N次（本例生成了50个个体），生成了第一代种群，种群的每个个体代表一条路径。

3.计算适应度采用的适应度函数为个体巡回路径的总长度的函数。

具体为adapt(1,i)=(5*maxdis-dis) (1) 在式（1）中，adapt(1,i)表示第i个个体的适应度函数，maxdis为城市间的最大距离，为4077km,dis为个体巡回路径的总长度，这样定义的适应度，当路经越短时适应度值越大。

在适应度值的基础上，给出的计算个体期望复制数的表达式为adaptnum(1,i)=(N* adapt(1,i)/ sumadapt) (2) 其中，sumadapt为种群适应度之和。

4.复制采用优秀个体的大比例保护基础上的随机数复制法。

具体做法为在生成下一代个体时，先将最大适应度对应的路径个体以较大的比例复制到下一代，然后再用随机数复制法生成下一代的其他个体。

其中，有一个问题必须考虑，即若某一次生成的随机数过大，结果能复制一个或极少个样本。

为了避免这一情况，采用了限制措施，即压低了随机数的上限。

5.交叉采用的方法为按步长的单点交叉，为随机选择一对样本，再随机选择一个交叉点位置，按一定的步长进行交叉点的选择。

选择一个步长而不是将其设为1，是因为若某一位置处的城市代码因为进行了交叉而发生了改变，则其经过该处的两个距离都会改变。

这种交叉兼有遗传和变异两方面的作用，因为若交叉点处的城市编号都相同，则对两个个体而言交叉后样本无变化，否则样本有变化。

第１３卷㊀第７期Ｖｏｌ．１３Ｎｏ．７㊀㊀智㊀能㊀计㊀算㊀机㊀与㊀应㊀用ＩｎｔｅｌｌｉｇｅｎｔＣｏｍｐｕｔｅｒａｎｄＡｐｐｌｉｃａｔｉｏｎｓ㊀㊀２０２３年７月㊀Ｊｕｌ．２０２３㊀㊀㊀㊀㊀㊀文章编号：２０９５－２１６３（２０２３）０７－００５８－０６中图分类号：ＴＰ３９１．４１文献标志码：Ａ基于遗传算法求解ＴＳＰ问题的研究及Ｍａｔｌａｂ实现杨锦涛，赵春香，杨成福（云南师范大学信息学院，昆明６５０５００）摘㊀要：ＴＳＰ问题属于组合优化问题，同时也是一个ＮＰＣ问题，因此人们一直致力于为其寻找有效的近似求解算法㊂遗传算法是模仿生物进化而构建的一种随机搜索方法，具有较强的全局搜索能力㊁潜在的并行性以及良好的可扩展性，能有效求解ＴＳＰ问题㊂然而，如何确定遗传参数和选择遗传操作一直是一个难题，本文针对ＴＳＰ问题的求解构建完整的遗传算法体系，选择合适的参数，设计多组交叉算子和变异算子，分别对ＴＳＰ问题进行求解㊂通过多次实验以及对实验结果的分析比较，探究不同的交叉算子和变异算子求解ＴＳＰ问题的效果，为遗传操作中交叉算子和变异算子的选择提供一定的参考㊂关键词：ＴＳＰ问题；组合优化；遗传算法ＲｅｓｅａｒｃｈｏｎｓｏｌｖｉｎｇＴＳＰｐｒｏｂｌｅｍｂａｓｅｄｏｎｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍａｎｄＭａｔｌａｂｉｍｐｌｅｍｅｎｔａｔｉｏｎＹＡＮＧＪｉｎｔａｏ，ＺＨＡＯＣｈｕｎｘｉａｎｇ，ＹＡＮＧＣｈｅｎｇｆｕ（ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎ，ＹｕｎｎａｎＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｋｕｎｍｉｎｇ６５０５００，Ｃｈｉｎａ）ʌＡｂｓｔｒａｃｔɔＴｈｅＴＳＰｐｒｏｂｌｅｍｂｅｌｏｎｇｓｔｏｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓａｎｄｉｓａｌｓｏａｎＮＰＣｐｒｏｂｌｅｍ，ｓｏｐｅｏｐｌｅｈａｖｅｂｅｅｎｔｒｙｉｎｇｔｏｆｉｎｄｔｈｅｃｏｒｒｅｓｐｏｎｄｉｎｇｅｆｆｅｃｔｉｖｅａｐｐｒｏｘｉｍａｔｉｏｎｓｏｌｖｉｎｇａｌｇｏｒｉｔｈｍｓ．Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｉｓａｒａｎｄｏｍｓｅａｒｃｈｍｅｔｈｏｄｂｕｉｌｔｔｏｉｍｉｔａｔｅｂｉｏｌｏｇｉｃａｌｅｖｏｌｕｔｉｏｎ，ｗｉｔｈｓｔｒｏｎｇｇｌｏｂａｌｓｅａｒｃｈａｂｉｌｉｔｙ，ｐｏｔｅｎｔｉａｌｐａｒａｌｌｅｌｉｓｍａｎｄｇｏｏｄｓｃａｌａｂｉｌｉｔｙ，ｗｈｉｃｈｃａｎｅｆｆｅｃｔｉｖｅｌｙｓｏｌｖｅＴＳＰｐｒｏｂｌｅｍｓ．Ｈｏｗｅｖｅｒ，ｈｏｗｔｏｄｅｔｅｒｍｉｎｅｇｅｎｅｔｉｃｐａｒａｍｅｔｅｒｓａｎｄｓｅｌｅｃｔｇｅｎｅｔｉｃｍａｎｉｐｕｌａｔｉｏｎｈａｓａｌｗａｙｓｂｅｅｎａｄｉｆｆｉｃｕｌｔｐｒｏｂｌｅｍ．Ｉｎｔｈｉｓｐａｐｅｒ，ａｃｏｍｐｌｅｔｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓｙｓｔｅｍｉｓｃｏｎｓｔｒｕｃｔｅｄｆｏｒｔｈｅｓｏｌｕｔｉｏｎｏｆＴＳＰｐｒｏｂｌｅｍｓ，ａｐｐｒｏｐｒｉａｔｅｐａｒａｍｅｔｅｒｓａｒｅｓｅｌｅｃｔｅｄ，ａｎｄｍｕｌｔｉｐｌｅｓｅｔｓｏｆｃｒｏｓｓｏｐｅｒａｔｏｒｓａｎｄｍｕｔａｔｉｏｎｏｐｅｒａｔｏｒｓａｒｅｄｅｓｉｇｎｅｄｔｏｓｏｌｖｅＴＳＰｐｒｏｂｌｅｍｓｓｅｐａｒａｔｅｌｙ．Ｔｈｒｏｕｇｈｍｕｌｔｉｐｌｅｅｘｐｅｒｉｍｅｎｔｓａｎｄｔｈｅａｎａｌｙｓｉｓａｎｄｃｏｍｐａｒｉｓｏｎｏｆｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓ，ｔｈｅｅｆｆｅｃｔｏｆｄｉｆｆｅｒｅｎｔｃｒｏｓｓｏｖｅｒｏｐｅｒａｔｏｒｓａｎｄｍｕｔａｔｉｏｎｏｐｅｒａｔｏｒｓｉｎｓｏｌｖｉｎｇＴＳＰｐｒｏｂｌｅｍｓｉｓｅｘｐｌｏｒｅｄ，ｗｈｉｃｈｐｒｏｖｉｄｅｓａｃｅｒｔａｉｎｒｅｆｅｒｅｎｃｅｆｏｒｔｈｅｓｅｌｅｃｔｉｏｎｏｆｃｒｏｓｓｏｖｅｒｏｐｅｒａｔｏｒｓａｎｄｍｕｔａｔｉｏｎｏｐｅｒａｔｏｒｓｉｎｇｅｎｅｔｉｃｏｐｅｒａｔｉｏｎｓ．ʌＫｅｙｗｏｒｄｓɔＴＳＰｐｒｏｂｌｅｍ；ｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ基金项目：云南师范大学博士科研启动基金（２０２１ＺＢ０１９）㊂作者简介：杨锦涛（２００２－），女，本科生，主要研究方向：深度学习；赵春香（２０００－），女，本科生，主要研究方向：深度学习；杨成福（１９８６－），男，博士，讲师，硕士生导师，主要研究方向：信息超材料㊁深度学习㊁人工智能㊂通讯作者：杨成福㊀㊀Ｅｍａｉｌ：ｙａｎｇｃｈｅｎｇｆｕ＠ｙｎｎｕ．ｅｄｕ．ｃｎ收稿日期：２０２２－１２－１８０㊀引㊀言ＴＳＰ问题㊁即巡回旅行商问题，是组合优化领域中的一个典型问题㊂现实生活中的很多实际应用问题都可以简化为ＴＳＰ问题㊂ＴＳＰ问题可以用图论描述为：已知带权完全图Ｇ，求一条使得路径总和最小㊁且经过所有顶点的回路㊂ＴＳＰ问题虽然描述简单㊁容易理解，但是求解是很困难的㊂当问题的规模较小时，仅使用枚举法就能找到一条最优路径，但当城市数量较多时，即使用计算机也无法将解全部列举，要求出ＴＳＰ问题的最优解是不可能的㊂遗传算法是一种自组织㊁自适应的全局寻优算法，因其潜在的并行性㊁较高的鲁棒性，在应用研究方面取得了很多可观的成果，被广泛应用于函数优化㊁组合优化㊁生产调度㊁自适应控制㊁图像处理㊁机器学习㊁数据挖掘㊁人工生命㊁遗传编程等领域㊂１９７５年，Ｈｏｌｌａｎｄ［１］受生物学中生物进化和自然选择学说的启发，提出了著名的遗传算法㊂２００６年，何燕［２］对遗传算法进行改进，将其应用到车间调度领域㊂２０１０年，蒋波［３］将遗传算法应用于车辆路径优化问题，指出遗传算法求解该问题的优越性，并对其做出了改进，实验证明改进后的遗传算法能Copyright ©博看网. All Rights Reserved.够有效解决此类问题㊂２０１３年，乔阳［４］将遗传算法和Ｏｓｔｕ图像分割法进行改进后结合在一起进行图像分割实验，得到了满意的结果㊂遗传算法是模拟生物进化的过程发展而来的一种算法，从一定规模的解集（初始种群）开始，通过选择㊁交叉和变异，将适应度低的解（个体）淘汰掉，将适应度高的解（个体）保留下来，并产生新的解（个体），生成新的解集（种群），通过不断地迭代，使解集（种群）中的解（个体）越来越接近问题的最优解㊂生物学和遗传算法概念之间的对应关系见表１㊂表１㊀生物学和遗传算法概念对照Ｔａｂ．１㊀Ｃｏｍｐａｒｉｓｏｎｏｆｂｉｏｌｏｇｉｃａｌａｎｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｃｏｎｃｅｐｔｓ生物学遗传算法外界环境约束条件个体问题的一个可行解个体对环境的适应度可行解的质量种群一定数量可行解的集合生物的繁衍算法的迭代种群的进化过程可行解的优化过程㊀㊀本文针对ＴＳＰ问题构建完整的遗传算法体系，将求解ＴＳＰ问题几种常用的交叉算子和变异算子两两组合在一起，分别对具体的ＴＳＰ问题实例进行求解，从所得的最优解和求解的时间两方面对实验结果进行分析和总结，探究使用不同的交叉算子和变异算子时遗传算法求解对称式ＴＳＰ问题的效果［５］㊂１㊀遗传算法求解ＴＳＰ问题１．１㊀编码编码是指按照一定的构造方法，将问题的可行解转变为遗传算法能直接处理的个体㊂常用的编码方式有二进制编码㊁近邻编码㊁次序编码㊁路径编码［６］㊂使用路径编码求解ＴＳＰ问题，不仅编码过程简单易操作，而且编码结果非常直观，即首先对城市进行编号，然后以城市编号作为城市的编码，因此本文选择使用路径编码方式对城市进行编码㊂１．２㊀初始种群一般地，初始种群采用随机方法生成，如果种群规模为Ｍ，则随机生成Ｍ个个体㊂１．３㊀适应度函数适应度函数用于对种群中的个体进行优劣程度的评价，由于算法在搜索最优解的过程中主要以个体的适应度作为依据，所以如果适应度函数构建不当，很可能导致算法的收敛速度缓慢㊁甚至无法收敛，即适应度函数直接决定着算法的收敛能力和寻优能力㊂对于ＴＳＰ问题，适应度函数一般取路径总和的倒数，具体定义公式见如下：ｆ（ｘ）＝１ðｎ－１ｉ＝１ｄ（ｔｉ，ｔｉ＋１）＋ｄ（ｔｎ，ｔ１）（１）㊀㊀其中，ｎ表示城市的数量；Ｔ＝（ｔ１，ｔ２， ，ｔｎ）为种群中的一个个体；ｄ（ｔｉ，ｔｊ）表示城市ｉ到城市ｊ的距离㊂ＴＳＰ问题为最小值问题，由适应度函数可知，路径总和与个体适应度呈倒数关系㊂１．４㊀遗传操作１．４．１㊀选择算子选择是用选择算子对个体进行筛选的过程，这一过程中，差的个体被保留下来的概率小，好的个体被保留下来的概率大，会使种群中的个体向最优解进化㊂常用的选择算子有轮盘赌选择㊁最佳个体保存选择㊁锦标赛选择和排序选择［７］㊂轮盘赌选择是ＴＳＰ问题求解最常用的选择算子，即使用适应度值计算出每个个体被选择的概率，并根据该概率值对种群中的个体进行选择㊂本文也使用轮盘赌选择作为选择算子，并在轮盘赌的基础上添加最佳个体保存选择，即把种群中出现过的适应度值最高的个体保留下来，避免种群中优秀的个体在遗传操作中被淘汰或破坏㊂１．４．２㊀交叉算子个体交叉是为了实现种群的更新，而交叉算子是进行交叉的手段，定义了个体之间以怎样的方式交叉㊂对于不同问题，由于编码方式的不同，交叉算子也有所不同㊂对此拟做研究分述如下㊂（１）部分匹配交叉（ＰＭＸ）：首先采用随机方式在父体中确定２个位置，由２个位置确定一个交叉段，然后将２个父体的交叉段进行交换，最后根据交叉段之间的映射关系消除子代中的重复基因㊂（２）顺序交叉（ＯＸ）：首先从父体中随机选择２个位置，由２个位置确定一个基因段，然后将父体Ａ的该基因段复制到子代Ａ 的对应位置，最后将父体Ｂ除父体Ａ被选择的基因段之外的基因依次复制到子代Ａ 的其余位置，同理可得到子代Ｂ ㊂（３）循环交叉（ＣＸ）：首先将父体Ａ的第一个基因复制到子代，然后在父体Ｂ中的相同位置查看基因，随后在父体Ａ中找到该基因复制到子代的相同位置，并在父体Ｂ中查看相同位置的基因，重复此步骤，直到在父体Ｂ中找到的基因已经在子代中，停止循环，在父体Ｂ中找到剩余的基因，并按照顺序复制到子代中的剩余位置㊂９５第７期杨锦涛，等：基于遗传算法求解ＴＳＰ问题的研究及Ｍａｔｌａｂ实现Copyright©博看网. All Rights Reserved.１．４．３㊀变异算子变异操作的主要目的是维持种群多样性，在遗传算法后期，个体交叉产生新个体的能力弱，通过个体变异可以进一步产生新个体，扩大搜索空间㊂接下来给出剖析论述如下㊂（１）对换变异㊂首先用随机方式在父体中确定２个位置，然后交换这２个位置上的基因㊂（２）倒位变异㊂用随机方式在父体中确定２个位置，以确定一个基因段，然后将其进行逆序排列㊂（３）插入变异㊂用随机方式在父体中确定一个位置，以确定一个待插入的基因，再用随机方式确定２个位置，以确定插入点，最后将待插入的基因放入插入点㊂１．５㊀遗传算法求解ＴＳＰ问题具体步骤根据上文选择的实现技术构建完整的遗传算法体系后，对ＴＳＰ问题实例进行求解的具体步骤如下：Ｓｔｅｐ１㊀获取城市数据，对城市进行编号㊂Ｓｔｅｐ２㊀初始化种群㊂Ｓｔｅｐ３㊀适应度评价㊂Ｓｔｅｐ４㊀执行选择操作，采用轮盘赌选择对个体进行筛选，选出足够数量的个体㊂Ｓｔｅｐ５㊀执行交叉操作，将选择操作中选出的个体两两组合作为父染色体，判断是否进行交叉，如果进行交叉，则按照选定的交叉算子进行交叉㊂Ｓｔｅｐ６㊀执行变异操作，将执行交叉操作后的每个个体作为父染色体，判断是否进行变异，如果进行变异，则按照选定的变异算子进行变异㊂Ｓｔｅｐ７㊀完成变异后，执行最佳个体保存策略，判断当前种群中的最优解是否优于历史最优解㊂如果是，更新历史最优解，否则找出种群中最差的解，用最优解将其替换掉㊂Ｓｔｅｐ８㊀判断是否继续进行迭代，若是，回到Ｓｔｅｐ３；否则，结束迭代，输出最优解㊂㊀㊀将前述的３种交叉算子和３种变异算子两两组合在一起，共有９种组合方式，见表２㊂基于表２中列出的９种组合，重复对ＴＳＰ问题进行求解㊂表２㊀９组交叉算子和变异算子Ｔａｂ．２㊀９ｓｅｔｓｏｆｃｒｏｓｓｏｖｅｒａｎｄｍｕｔａｔｉｏｎｏｐｅｒａｔｏｒｓ组合编号交叉算子变异算子第一组部分匹配交叉对换变异第二组部分匹配交叉倒位变异第三组部分匹配交叉插入变异第四组循序交叉对换变异第五组循环交叉倒位变异第六组循环交叉插入变异第七组顺序交叉对换变异第八组顺序交叉倒位变异第九组顺序交叉插入变异２㊀实验及结果分析２．１㊀实验仿真本文使用Ｍａｔｌａｂ实现上文构建的遗传算法，从ＴＳＰＬＩＢ中选择测试样例进行具体分析㊂ＴＳＰＬＩＢ是包含对称旅行商问题㊁哈密顿回路问题㊁以及非对称旅行商问题的多种实例数据的文件库，数据规模多样㊂本文在对每个测试样例进行求解时，改变算法的交叉算子和变异算子，进行多次重复的实验，从问题的最优解和求解时间两方面对几组交叉算子和变异算子求解ＴＳＰ问题的效果进行分析比较㊂在完成算法的编程后，初步设置参数，对实例Ｏｌｉｖｅｒ３０进行求解，根据实验结果对算法的参数进行调整，最终选定迭代次数Ｇ为５００，交叉概率Ｐｃ为０．９，变异概率Ｐｍ为０．２，种群规模Ｍ根据待求解问题的规模来确定㊂一般地，城市个数越多，种群规模越大，对３０个城市的实例Ｏｌｉｖｅｒ３０，种群规模取１００㊂用上述９组交叉算子和变异算子分别对Ｏｌｉｖｅｒ３０求解１０次的结果见表３㊂表３㊀遗传算法求解Ｏｌｉｖｅｒ３０Ｔａｂ．３㊀ＧｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒＯｌｉｖｅｒ３０序号第一组第二组第三组第四组第五组第六组第七组第八组第九组１５１１．９８４２５．１０５２６．４０５１０．０３４２５．４８４９６．３４５３２．７５４２５．７２４７２．３６２５６５．５６４２９．６２４５１．６９５３８．１０４２３．７４４７９．０１５０１．０９４２８．０４４９５．３５３４９５．８０４３２．６６４６８．３２４９６．６５４７６．１２４９５．１９５１４．３０４２８．８４４７６．０９４４９６．８４４２５．１０４３３．０９５３４．１４４２４．１２４５７．７３５０１．５４４３１．７１４５７．７４５５４１．８０４６０．１７４６４．９１５３６．８９４５１．７２４４５．９７４９６．２４４３５．３１４７４．２１６５００．８８４２９．８３４９４．４５５２５．４４４３８．３８４８３．９２５０７．５７４５０．４１４７８．８０７５０１．９２４３２．６６５２１．３３５１４．３０４２５．２７４６６．６５５６１．８５４２８．４６４６０．７４８５１４．９０４５０．６９４９７．４６４８８．２１４２５．３１４８４．１８５１５．１３４２３．７４４７４．７３９５２９．０６４４７．２１４８７．６０４８２．６１４３４．６１５００．１８５７１．７９４３１．７６４６６．６９１０５５６．３１４２５．７３５０７．６４５１０．６１４３３．５４４７１．１８４５６．７９４３８．３８４８３．２７０６智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１３卷㊀Copyright©博看网. All Rights Reserved.㊀㊀以文献［８］中求得的最优解４２３．７４作为参考值，从表３可以看出第２组㊁第５组㊁第８组交叉算子和变异算子的求解结果都比较接近参考最优解，且较稳定，说明参数设置较合理㊂其中一次求解的收敛曲线如图１所示，最优路线如图２所示㊂其中，以圆圈标记的点为路线起点，其与路线终点用虚线相连，其余路线用实线连接㊂12001000800600400200400600迭代次数最优解图１㊀Ｏｌｉｖｅｒ３０收敛曲线Ｆｉｇ．１㊀ＣｏｎｖｅｒｇｅｎｃｅｃｕｒｖｅｏｆＯｌｉｖｅｒ３０1008060402020406080100城市横坐标城市纵坐标图２㊀Ｏｌｉｖｅｒ３０最优路线图Ｆｉｇ．２㊀ＯｐｔｉｍａｌｒｏａｄｍａｐｏｆＯｌｉｖｅｒ３０２．２㊀实验结果从ＴＳＰＬＩＢ中选择测试样例进行求解，本文总共选择了５个实例，分别是ｕｌｙｓｓｅｓ１６㊁ｄａｎｔｚｉｇ４２㊁ｅｉｌ５１㊁ｅｉｌ７６㊁ｅｉｌ１０１，根据问题的规模为每个实例设置合适的种群规模（Ｍ）㊂其中，ｕｌｙｓｓｅｓ１６㊁ｄａｎｔｚｉｇ４２㊁ｅｉｌ５１实例的种群规模取１００，ｅｉｌ７６实例的种群规模取１５０，ｅｉｌ１０１实例的种群规模取２００，分别用上述９组交叉算子和变异算子求解１０次，记录１０次求解结果的最好值（Ｂｅｓｔ）㊁平均值（ＡＶＲ）和偏差率（Ｄｒ），以及求解的平均时间（Ｔｉｍｅ），这里的偏差率可由式（２）来计算：Ｄｒ＝Ｂｅｓｔ－ＯｐｔＯｐｔ（２）㊀㊀其中，Ｏｐｔ是ＴＳＰＬＩＢ数据集提供的最优解㊂实验结果见表４ 表８㊂表４㊀遗传算法求解ｕｌｙｓｓｅｓ１６Ｔａｂ．４㊀Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｕｌｙｓｓｅｓ１６序号ＡＶＧＢｅｓｔＯｐｔＤｒＴｉｍｅ／ｓ第１组第２组第３组第４组第５组第６组第７组第８组第９组７５．０１７４．０１７４．２４７４．３６７４．０５７４．２０７４．６０７４．０９７４．２８７４．００７３．９９７３．９９７３．９９７３．９９７３．９９７３．９９７３．９９７３．９９７４０．０００．０００．０００．０００．０００．０００．０００．０００．００１．２１．１１．４０．７０．７０．７０．５０．５０．５表５㊀遗传算法求解ｄａｎｔｚｉｇ４２Ｔａｂ．５㊀Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｄａｎｔｚｉｇ４２序号ＡＶＧＢｅｓｔＯｐｔＤｒＴｉｍｅ／ｓ第１组第２组第３组第４组第５组第６组第７组第８组第９组１０２２．３４７５６．４９９１５．６９９４４．０２７３３．００８９４．３２１０６１．２１７６０．７３９３７．２２８６４．８９７１３．９９８３８．３８８５８．２６６９８．９８７９４．０２８９３．３５７２５．３７８４６．４１６９９０．２４０．０２０．２００．２３０．０００．１４０．２８０．０４０．２１１．４１．６２．８１．０１．０１．００．７０．６０．７表６㊀遗传算法求解ｅｉｌ５１Ｔａｂ．６㊀Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｅｉｌ５１序号ＡＶＧＢｅｓｔＯｐｔＤｒＴｉｍｅ／ｓ第１组第２组第３组第４组第５组第６组第７组第８组第９组６４２．６６５１６．３５５９２．００６４６．０９５０３．９７５８０．３９６５７．４８５１１．９１６０７．４２６１３．８７４８７．９５５３２．９０５５９．６８４８１．６７５３４．４１６０４．８１４６５．２８５５１．７０４２６０．４４０．１５０．２５０．３１０．１３０．２５０．４２０．０９０．３０１．４１．８３．６１．１１．１１．１０．７０．７０．７１６第７期杨锦涛，等：基于遗传算法求解ＴＳＰ问题的研究及Ｍａｔｌａｂ实现Copyright ©博看网. All Rights Reserved.表７㊀遗传算法求解ｅｉｌ７６Ｔａｂ．７㊀Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｅｉｌ７６序号ＡＶＧＢｅｓｔＯｐｔＤｒＴｉｍｅ／ｓ第１组第２组第３组第４组第５组第６组第７组第８组第９组１０３７．９４８８０．６４１００２．０１１０１２．３２８３５．３７９９３．６９１０７３．７８８３３．７７９９２．８９９７１．９６８０６．５３９１６．５２９４９．１７７９２．３９９２５．７４１０１４．８６７８１．８８８９４．４７５３８０．８１０．５００．７００．７６０．４７０．７２０．８９０．４５０．６６２．２３．２９．５１．８１．８１．８０．９１．０１．０表８㊀遗传算法求解ｅｉｌ１０１Ｔａｂ．８㊀Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｅｉｌ１０１序号ＡＶＧＢｅｓｔＯｐｔＤｒＴｉｍｅ／ｓ第１组第２组第３组第４组第５组第６组第７组第８组第９组１４７０．９４１３４０．３３１４５２．０２１４６８．１７１１９４．４９１４０８．３３１４７９．１２１２３８．６８１４３８．３９１３６１．７８１２８６．６４１３６３．６７１３５２．２４１１４２．１９１２９７．４３１３９７．６９１１６８．２５１３４０．９３６２９１．１６１．０５１．１７１．１５０．８２１．０６１．２２０．８６１．１３３．２５．３２０．４２．７２．７２．７１．２１．２１．２㊀㊀为了方便对比，将每个实例求解结果中的偏差率（Ｄｒ）和求解的平均时间（Ｔｉｍｅ）分别统计在一起，由于实例ｕｌｙｓｓｅｓ１６问题规模小，坐标数据也容易处理，不管选择哪种交叉算子和变异算子，求解结果都很接近最优解，因此在进行偏差率的比较时不将其考虑在内，具体见表９㊁表１０㊂表９㊀偏差率对比Ｔａｂ．９㊀Ｄｅｖｉａｔｉｏｎｒａｔｅｃｏｍｐａｒｉｓｏｎ序号ｄａｎｔｚｉｇ４２ｅｉｌ５１ｅｉｌ７６ｅｉｌ１０１第１组第２组第３组第４组第５组第６组第７组第８组第９组０．２４０．０２０．２００．２３０．０００．１４０．２８０．０４０．２１０．４４０．１５０．２５０．３１０．１３０．２５０．４２０．０９０．３００．８１０．５００．７００．７６０．４７０．７２０．８９０．４５０．６６１．１６１．０５１．１７１．１５０．８２１．０６１．２２０．８６１．１３表１０㊀求解平均时间对比Ｔａｂ．１０㊀Ｃｏｍｐａｒｉｓｏｎｏｆａｖｅｒａｇｅｓｏｌｖｉｎｇｔｉｍｅ序号ｕｌｙｓｓｅｓ１６ｄａｎｔｚｉｇ４２ｅｉｌ５１ｅｉｌ７６ｅｉｌ１０１第１组第２组第３组第４组第５组第６组第７组第８组第９组１．２１．１１．４０．７０．７０．７０．５０．５０．５１．４１．６２．８１．０１．０１．００．７０．６０．７１．４１．８３．６１．１１．１１．１０．７０．７０．７２．２３．２９．５１．８１．８１．８０．９１．０１．０３．２５．３２０．４２．７２．７２．７１．２１．２１．２３㊀实验结论根据上述实验结果，可以得出如下结论：（１）表９中的偏差率描述了采用不同的交叉算子和变异算子时，所求得的最优解与ＴＳＰＬＩＢ中给出的最优解的差距，偏差率越小，说明算法求得的结果越接近最优解，算法的寻优能力越好㊂从表９中可以看出，第２组数据总是小于第１组和第３组㊁第５组数据总是小于第４组和第６组㊁第８组数据总是小于第７组和第９组，这说明每种交叉算子和逆转变异组合在一起时，问题的求解结果总是比与对换变异和插入变异组合在一起时更接近最优解㊂由此可知，遗传算法使用逆转变异作为变异算子时比选择对换变异和插入变异作为变异算子的寻优能力更强㊂（２）表１０是采用每组交叉算子和变异算子求解每个实例１０次所花时间的平均值，所花的时间越少，说明算法的搜索速度越快，执行效率越高，由于变异操作比较简单，所以遗传算法的执行效率主要由交叉操作决定㊂从表１０中可以看出，遗传算法采用顺序交叉和循环交叉时，即使采用不同的变异算子，所花的时间也基本相同，但是采用部分匹配交叉所花的时间会因为变异算子的不同而有所不同㊂对于每一个实例，在得到的解的质量差别不大的情况下，遗传算法使用部分匹配交叉所花的时间最多，使用循环交叉所花的时间最少㊂综上所述，对于比较简单的ＴＳＰ问题，由于使用遗传算法总能求得与最优解很接近的解，所以选择何种交叉算子和变异算子对算法的寻优能力影响不大，但是使用部分匹配交叉会花费比较多的时间，会导致算法的执行效率低，因此交叉算子选择循环２６智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１３卷㊀Copyright©博看网. All Rights Reserved.交叉比较合适㊂对于不是总能求得最优解的ＴＳＰ问题，与对换变异和插入变异相比，使用逆转变异会使算法具有更强的寻优能力，找到的最优解更接近最优解，使用部分匹配交叉和顺序交叉会花费比循环交叉更多的时间，使算法的执行效率变低，而且找到的最优解也不会更优㊂４　结束语本文对几种常用的交叉算子和变异算子求解ＴＳＰ问题的效果进行了研究㊂实验结果表明，在几种常用的交叉算子和变异算子中，选择循环交叉和逆转变异算法的执行效率最高，寻优能力最好，这能为遗传算法中交叉算子和变异算子的选择提供一定的参考，同时有利于设计出更好的交叉算子和变异算子，提高算法的性能㊂参考文献［１］ＨＯＬＬＡＮＤＪ．Ａｄａｐｔａｔｉｏｎｉｎｎａｔｕｒａｌａｎｄａｒｔｉｆｉｃｉａｌｓｙｓｔｅｍｓ：ａｎｉｎｔｒｏ⁃ｄｕｃｔｏｒｙａｎａｌｙｓｉｓｗｉｔｈａｐｐｌｉｃａｔｉｏｎｔｏｂｉｏｌｏｇｙ［Ｊ］．ＣｏｎｔｒｏｌＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ，１９７５．［２］何燕．基于遗传算法的车间调度优化及其仿真［Ｄ］．武汉：武汉理工大学，２００６．［３］蒋波．基于遗传算法的带时间窗车辆路径优化问题研究［Ｄ］．北京：北京交通大学，２０１０．［４］乔阳．基于改进遗传算法的图像分割方法［Ｄ］．成都：电子科技大学，２０１３．［５］张家善，王志宏，陈应显，等．一种求解旅行商问题的改进遗传算法［Ｊ］．计算机系统应用，２０１２，２１（０９）：１９２－１９４，１９１．［６］王娜．求解ＴＳＰ的改进遗传算法［Ｄ］．西安：西安电子科技大学，２０１０．［７］于丰瑞．基于改进的遗传算法求解ＴＳＰ问题［Ｄ］．呼和浩特：内蒙古农业大学，２０１６．［８］闫茹．基于改进遗传算法的旅游路线优化研究与应用［Ｄ］．银川：北方民族大学，２０２１．（上接第５７页）［３］田浩杰，杨晓庆，翟晓雨．基于深度学习的线圈炮缺陷自动检测与分类［Ｊ］．现代计算机，２０２２，２８（１０）：８６－９１．［４］张浩，吴陈，徐影．基于深度学习在海缆表面缺陷检测中的应用［Ｊ］．电脑知识与技术，２０２２，１８（１５）：８８－９１．［５］陈宗仁，谢文达，余君，等．基于深度学习的金属机械零件表面缺陷检测方法［Ｊ］．制造业自动化，２０２１，４３（１２）：１７０－１７３．［６］王昊，李俊峰．基于深度学习的车载导航导光板表面缺陷检测研究［Ｊ］．软件工程，２０２２，２５（０３）：３４－３８，１６．［７］刘瑞珍，孙志毅，王安红，等．基于深度学习的偏光片缺陷实时检测算法［Ｊ］．太原理工大学学报，２０２０，５１（０１）：１２５－１３０．［８］王鸣霄，范娟娟，周磊，等．基于深度学习的排水管道缺陷自动检测与分类［Ｊ］．给水排水，２０２０，４６（１２）：１０６－１１１．［９］施恺杰，王颖，王嘉璐，等．基于深度学习的电子换向器表面缺陷检测［Ｊ］．网络安全技术与应用，２０２１（０６）：１１３－１１５．［１０］于宏全，袁明坤，常建涛，等．基于深度学习的铸件缺陷检测方法［Ｊ］．电子机械工程，２０２１，３７（０６）：５９－６４．［１１］ＬＥＣＵＮＹ，ＢＯＴＴＯＵＬ，ＢＥＮＧＩＯＹ，ｅｔａｌ．Ｇｒａｄｉｅｎｔ－ｂａｓｅｄｌｅａｒｎｉｎｇａｐｐｌｉｅｄｔｏｄｏｃｕｍｅｎｔｒｅｃｏｇｎｉｔｉｏｎ［Ｊ］．ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＩＥＥＥ，１９９８，８６（１１）：２２７８－２３２４．［１２］ＫＲＩＺＨＥＶＳＫＹＡ，ＳＵＴＳＫＥＶＥＲＩ，ＨＩＮＴＯＮＧＥ．Ｉｍａｇｅｎｅｔｃｌａｓｓｉｆｉｃａｔｉｏｎｗｉｔｈｄｅｅｐｃｏｎｖｏｌｕｔｉｏｎａｌｎｅｕｒａｌｎｅｔｗｏｒｋｓ［Ｊ］．ＣｏｍｍｕｎｉｃａｔｉｏｎｓｏｆｔｈｅＡＣＭ，２０１７，６０（６）：８４－９０．［１３］ＳＩＭＯＮＹＡＮＫ，ＺＩＳＳＥＲＭＡＮＡ．Ｖｅｒｙｄｅｅｐｃｏｎｖｏｌｕｔｉｏｎａｌｎｅｔｗｏｒｋｓｆｏｒｌａｒｇｅ－ｓｃａｌｅｉｍａｇｅｒｅｃｏｇｎｉｔｉｏｎ［Ｊ］．ａｒＸｉｖｐｒｅｐｒｉｎｔａｒＸｉｖ：１４０９．１５５６，２０１４．［１４］ＳＺＥＧＥＤＹＣ，ＬＩＵＷｅｉ，ＪＩＡＹａｎｑｉｎｇ，ｅｔａｌ．Ｇｏｉｎｇｄｅｅｐｅｒｗｉｔｈｃｏｎｖｏｌｕｔｉｏｎｓ［Ｃ］／／ＩＥＥＥＣｏｎｆｅｒｅｎｃｅｏｎＣｏｍｐｕｔｅｒＶｉｓｉｏｎａｎｄＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ（ＣＶＰＲ）．Ｂｏｓｔｏｎ，ＭＡ，ＵＳＡ：ＩＥＥＥ，２０１５：１－９．［１５］ＨＥＫａｉｍｉｎｇ，ＺＨＡＮＧＸｉａｎｇｙｕ，ＲＥＮＳｈａｏｑｉｎｇ，ｅｔａｌ．Ｄｅｅｐｒｅｓｉｄｕａｌｌｅａｒｎｉｎｇｆｏｒｉｍａｇｅｒｅｃｏｇｎｉｔｉｏｎ［Ｃ］／／ＩＥＥＥＣｏｎｆｅｒｅｎｃｅｏｎＣｏｍｐｕｔｅｒＶｉｓｉｏｎａｎｄＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ（ＣＶＰＲ）．ＬａｓＶｅｇａｓ，ＮＶ，ＵＳＡ：ＩＥＥＥ，２０１６：７７０－７７８．３６第７期杨锦涛，等：基于遗传算法求解ＴＳＰ问题的研究及Ｍａｔｌａｂ实现Copyright©博看网. All Rights Reserved.。

遗传算法Matlab源代码完整可以运行的数值优化遗传算法源代码function[X,MaxFval,BestPop,Trace]=fga(FUN,bounds,MaxEranum,PopSiz e,options,pCross,pMutation,pInversion)%[X,MaxFval,BestPop,Trace]=fga(FUN,bounds,MaxEranum,PopSiz e,options,pCross,pMutation,pInversion)% Finds a maximum of a function of several variables.% fga solves problems of the form:% max F(X) subject to: LB = X = UB (LB=bounds(:,1),UB=bounds(:,2))% X - 最优个体对应自变量值% MaxFval - 最优个体对应函数值% BestPop - 最优的群体即为最优的染色体群% Trace - 每代最佳个体所对应的目标函数值% FUN - 目标函数% bounds - 自变量范围% MaxEranum - 种群的代数,取50--500(默认200)% PopSize - 每一代种群的规模；此可取50--200(默认100)% pCross - 交叉概率,一般取0.5--0.85之间较好(默认0.8)% pMutation - 初始变异概率,一般取0.05-0.2之间较好(默认0.1)% pInversion - 倒位概率,一般取0.05－0.3之间较好(默认0.2) % options - 1*2矩阵,options(1)=0二进制编码(默认0),option(1)~=0十进制编码,option(2)设定求解精度(默认1e-4)T1=clock;%检验初始参数if nargin2, error('FMAXGA requires at least three input arguments'); endif nargin==2, MaxEranum=150;PopSize=100;options=[1 1e-4];pCross=0.85;pMutation=0.1;pInversion=0.25;endif nargin==3, PopSize=100;options=[1 1e-4];pCross=0.85;pMutation=0.1;pInversion=0.25;endif nargin==4, options=[1 1e-4];pCross=0.85;pMutation=0.1;pInversion=0.25;endif nargin==5, pCross=0.85;pMutation=0.1;pInversion=0.25;endif nargin==6, pMutation=0.1;pInversion=0.25;endif nargin==7, pInversion=0.25;endif (options(1)==0|options(1)==1)find((bounds(:,1)-bounds(:,2))0)error('数据输入错误,请重新输入:');end% 定义全局变量global m n NewPop children1 children2 VarNum% 初始化种群和变量precision = options(2);bits = ceil(log2((bounds(:,2)-bounds(:,1))' ./ precision));%由设定精度划分区间VarNum = size(bounds,1);[Pop] = InitPop(PopSize,bounds,bits,options);%初始化种群[m,n] = size(Pop);fit = zeros(1,m);NewPop = zeros(m,n);children1 = zeros(1,n);children2 = zeros(1,n);pm0 = pMutation;BestPop = zeros(MaxEranum,n);%分配初始解空间BestPop,TraceTrace = zeros(1,MaxEranum);完整可以运行的数值优化遗传算法源代码Lb = ones(PopSize,1)*bounds(:,1)';Ub = ones(PopSize,1)*bounds(:,2)';%二进制编码采用多点交叉和均匀交叉，并逐步增大均匀交叉概率%浮点编码采用离散交叉（前期）、算术交叉（中期）、AEA重组（后期）OptsCrossOver = [ones(1,MaxEranum)*options(1);...round(unidrnd(2*(MaxEranum-[1:MaxEranum]))/MaxEranum)]';%浮点编码时采用两种自适应变异和一种随机变异（自适应变异发生概率为随机变异发生的2倍）OptsMutation = [ones(1,MaxEranum)*options(1);unidrnd(5,1,MaxEranum)]';if options(1)==3D=zeros(n);CityPosition=bounds;D = sqrt((CityPosition(:, ones(1,n)) - CityPosition(:, ones(1,n))').^2 +...(CityPosition(:,2*ones(1,n)) - CityPosition(:,2*ones(1,n))').^2 );end%========================================================================== % 进化主程序%%===================================== ===================================== eranum = 1;H=waitbar(0,'Please wait...');while(eranum=MaxEranum)for j=1:mif options(1)==1%eval(['[fit(j)]=' FUN '(Pop(j,:));']);%但执行字符串速度比直接计算函数值慢fit(j)=feval(FUN,Pop(j,:));%计算适应度elseif options(1)==0%eval(['[fit(j)]=' FUN '(b2f(Pop(j,:),bounds,bits));']);fit(j)=feval(FUN,(b2f(Pop(j,:),bounds,bits)));elsefit(j)=-feval(FUN,Pop(j,:),D);endend[Maxfit,fitIn]=max(fit);%得到每一代最大适应值Meanfit(eranum)=mean(fit);BestPop(eranum,:)=Pop(fitIn,:);Trace(eranum)=Maxfit;if options(1)==1Pop=(Pop-Lb)./(Ub-Lb);%将定义域映射到[0,1]：[Lb,Ub]--[0,1] ,Pop--(Pop-Lb)./(Ub-Lb)endswitch round(unifrnd(0,eranum/MaxEranum))%进化前期尽量使用实行锦标赛选择，后期逐步增大非线性排名选择case {0} [selectpop]=TournamentSelect(Pop,fit,bits);%锦标赛选择case {1}[selectpop]=NonlinearRankSelect(Pop,fit,bits);%非线性排名选择end完整可以运行的数值优化遗传算法源代码[CrossOverPop]=CrossOver(selectpop,pCross,OptsCrossOver(er anum,:));%交叉[MutationPop]=Mutation(CrossOverPop,fit,pMutation,VarNum,O ptsMutation(eranum,:)); %变异[InversionPop]=Inversion(MutationPop,pInversion);%倒位%更新种群if options(1)==1Pop=Lb+InversionPop.*(Ub-Lb);%还原PopelsePop=InversionPop;endpMutation=pm0+(eranum^3)*(pCross/2-pm0)/(eranum^4); %逐步增大变异率至1/2交叉率percent=num2str(round(100*eranum/MaxEranum));waitbar(eranum/MaxEranum,H,['Evolution complete ',percent,'%']);eranum=eranum+1;endclose(H);% 格式化输出进化结果和解的变化情况t=1:MaxEranum;plot(t,Trace,t,Meanfit);legend('解的变化','种群的变化');title('函数优化的遗传算法');xlabel('进化世代数');ylabel('每一代最优适应度');[MaxFval,MaxFvalIn]=max(Trace);if options(1)==1|options(1)==3X=BestPop(MaxFvalIn,:);elseif options(1)==0X=b2f(BestPop(MaxFvalIn,:),bounds,bits);endhold on;plot(MaxFvalIn,MaxFval,'*');text(MaxFvalIn+5,MaxFval,['FMAX=' num2str(MaxFval)]);str1=sprintf(' Best generation:\n %d\n\n Best X:\n %s\n\n MaxFval\n %f\n',...MaxFvalIn,num2str(X),MaxFval);disp(str1);% -计时T2=clock;elapsed_time=T2-T1;if elapsed_time(6)0elapsed_time(6)=elapsed_time(6)+60;elapsed_time(5)=elapsed_time(5)-1;endif elapsed_time(5)0elapsed_time(5)=elapsed_time(5)+60;elapsed_time(4)=elapsed_t ime(4)-1;end完整可以运行的数值优化遗传算法源代码str2=sprintf('elapsed_time\n %d (h) %d (m) %.4f (s)',elapsed_time(4),elapsed_time(5),elapsed_time(6));disp(str2);%===================================== ===================================== % 遗传操作子程序%%===================================== ===================================== % -- 初始化种群--% 采用浮点编码和二进制Gray编码(为了克服二进制编码的Hamming悬崖缺点)function [initpop]=InitPop(popsize,bounds,bits,options)numVars=size(bounds,1);%变量数目rang=(bounds(:,2)-bounds(:,1))';%变量范围if options(1)==1initpop=zeros(popsize,numVars);initpop=(ones(popsize,1)*rang).*(rand(popsize,numVars))+(ones (popsize,1)*bounds(:,1)');elseif options(1)==0precision=options(2);%由求解精度确定二进制编码长度len=sum(bits);initpop=zeros(popsize,len);%The whole zero encoding individualfor i=2:popsize-1pop=round(rand(1,len));pop=mod(([0 pop]+[pop 0]),2);%i=1时,b(1)=a(1);i1时,b(i)=mod(a(i-1)+a(i),2)%其中原二进制串:a(1)a(2)...a(n),Gray串:b(1)b(2)...b(n)initpop(i,:)=pop(1:end-1);endinitpop(popsize,:)=ones(1,len);%The whole one encoding individualelsefor i=1:popsizeinitpop(i,:)=randperm(numVars);%为Tsp问题初始化种群endend% -- 二进制串解码--function [fval] = b2f(bval,bounds,bits)% fval - 表征各变量的十进制数% bval - 表征各变量的二进制编码串% bounds - 各变量的取值范围% bits - 各变量的二进制编码长度scale=(bounds(:,2)-bounds(:,1))'./(2.^bits-1); %The range of the variablesnumV=size(bounds,1);cs=[0 cumsum(bits)];for i=1:numVa=bval((cs(i)+1):cs(i+1));fval(i)=sum(2.^(size(a,2)-1:-1:0).*a)*scale(i)+bounds(i,1);end% -- 选择操作--完整可以运行的数值优化遗传算法源代码% 采用基于轮盘赌法的非线性排名选择% 各个体成员按适应值从大到小分配选择概率：% P(i)=(q/1-(1-q)^n)*(1-q)^i, 其中P(0)P(1)...P(n), sum(P(i))=1function [NewPop]=NonlinearRankSelect(OldPop,fit,bits) global m n NewPopfit=fit';selectprob=fit/sum(fit);%计算各个体相对适应度(0,1)q=max(selectprob);%选择最优的概率x=zeros(m,2);x(:,1)=[m:-1:1]';[y x(:,2)]=sort(selectprob);r=q/(1-(1-q)^m);%标准分布基值newfit(x(:,2))=r*(1-q).^(x(:,1)-1);%生成选择概率newfit=[0 cumsum(newfit)];%计算各选择概率之和rNums=rand(m,1);newIn=1;while(newIn=m)NewPop(newIn,:)=OldPop(length(find(rNums(newIn)newfit)),:);newIn=newIn+1;end% -- 锦标赛选择(含精英选择) --function [NewPop]=TournamentSelect(OldPop,fit,bits)global m n NewPopnum=floor(m./2.^(1:10));num(find(num==0))=[];L=length(num);a=sum(num);b=m-a;PopIn=1;while(PopIn=L)r=unidrnd(m,num(PopIn),2^PopIn);[LocalMaxfit,In]=max(fit(r),[],2);SelectIn=r((In-1)*num(PopIn)+[1:num(PopIn)]');NewPop(sum(num(1:PopIn))-num(PopIn)+1:sum(num(1:PopIn)),:)=OldPop(SelectIn,:);PopIn=PopIn+1;r=[];In=[];LocalMaxfit=[];endif b1NewPop((sum(num)+1):(sum(num)+b-1),:)=OldPop(unidrnd(m,1,b-1),:);end[GlobalMaxfit,I]=max(fit);%保留每一代中最佳个体NewPop(end,:)=OldPop(I,:);% -- 交叉操作--function [NewPop]=CrossOver(OldPop,pCross,opts)global m n NewPopr=rand(1,m);完整可以运行的数值优化遗传算法源代码y1=find(rpCross);y2=find(r=pCross);len=length(y1);if len==1|(len2mod(len,2)==1)%如果用来进行交叉的染色体的条数为奇数，将其调整为偶数y2(length(y2)+1)=y1(len);y1(len)=[];endi=0;if length(y1)=2if opts(1)==1%浮点编码交叉while(i=length(y1)-2)NewPop(y1(i+1),:)=OldPop(y1(i+1),:);NewPop(y1(i+2),:)=OldPop(y1(i+2),:);if opts(2)==0n1%discret crossoverPoints=sort(unidrnd(n,1,2));NewPop(y1(i+1),Points(1):Points(2))=OldPop(y1(i+2),Points(1):Po ints(2));NewPop(y1(i+2),Points(1):Points(2))=OldPop(y1(i+1),Points(1):Po ints(2));elseif opts(2)==1%arithmetical crossoverPoints=round(unifrnd(0,pCross,1,n));CrossPoints=find(Points==1);r=rand(1,length(CrossPoints));NewPop(y1(i+1),CrossPoints)=r.*OldPop(y1(i+1),CrossPoints)+(1 -r).*OldPop(y1(i+2),CrossPoints);NewPop(y1(i+2),CrossPoints)=r.*OldPop(y1(i+2),CrossPoints)+(1 -r).*OldPop(y1(i+1),CrossPoints); else %AEA recombination Points=round(unifrnd(0,pCross,1,n));CrossPoints=find(Points==1);v=unidrnd(4,1,2);NewPop(y1(i+1),CrossPoints)=(floor(10^v(1)*OldPop(y1(i+1),Cro ssPoints))+...10^v(1)*OldPop(y1(i+2),CrossPoints)-floor(10^v(1)*OldPop(y1(i+2),CrossPoints)))/10^v(1);NewPop(y1(i+2),CrossPoints)=(floor(10^v(2)*OldPop(y1(i+2),Cro ssPoints))+...10^v(2)*OldPop(y1(i+1),CrossPoints)-floor(10^v(2)*OldPop(y1(i+1),CrossPoints)))/10^v(2);endi=i+2;endelseif opts(1)==0%二进制编码交叉while(i=length(y1)-2)if opts(2)==0[NewPop(y1(i+1),:),NewPop(y1(i+2),:)]=EqualCrossOver(OldPop( y1(i+1),:),OldPop(y1(i+2),:)); else[NewPop(y1(i+1),:),NewPop(y1(i+2),:)]=MultiPointCross(OldPop( y1(i+1),:),OldPop(y1(i+2),:)); endi=i+2;endelse %Tsp问题次序杂交for i=0:2:length(y1)-2xPoints=sort(unidrnd(n,1,2));NewPop([y1(i+1)y1(i+2)],xPoints(1):xPoints(2))=OldPop([y1(i+2)y1(i+1)],xPoints(1):xPoints(2));完整可以运行的数值优化遗传算法源代码%NewPop(y1(i+2),xPoints(1):xPoints(2))=OldPop(y1(i+1),xPo ints(1):xPoints(2));temp=[OldPop(y1(i+1),xPoints(2)+1:n)OldPop(y1(i+1),1:xPoints(2))];for del1i=xPoints(1):xPoints(2)temp(find(temp==OldPop(y1(i+2),del1i)))=[];endNewPop(y1(i+1),(xPoints(2)+1):n)=temp(1:(n-xPoints(2)));NewPop(y1(i+1),1:(xPoints(1)-1))=temp((n-xPoints(2)+1):end);temp=[OldPop(y1(i+2),xPoints(2)+1:n)OldPop(y1(i+2),1:xPoints(2))];for del2i=xPoints(1):xPoints(2)temp(find(temp==OldPop(y1(i+1),del2i)))=[];endNewPop(y1(i+2),(xPoints(2)+1):n)=temp(1:(n-xPoints(2)));NewPop(y1(i+2),1:(xPoints(1)-1))=temp((n-xPoints(2)+1):end);endendendNewPop(y2,:)=OldPop(y2,:);% -二进制串均匀交叉算子function[children1,children2]=EqualCrossOver(parent1,parent2) global n children1 children2hidecode=round(rand(1,n));%随机生成掩码crossposition=find(hidecode==1);holdposition=find(hidecode==0);children1(crossposition)=parent1(crossposition);%掩码为1，父1为子1提供基因children1(holdposition)=parent2(holdposition);%掩码为0，父2为子1提供基因children2(crossposition)=parent2(crossposition);%掩码为1，父2为子2提供基因children2(holdposition)=parent1(holdposition);%掩码为0，父1为子2提供基因% -二进制串多点交叉算子function[Children1,Children2]=MultiPointCross(Parent1,Parent2)%交叉点数由变量数决定global n Children1 Children2 VarNumChildren1=Parent1;Children2=Parent2;Points=sort(unidrnd(n,1,2*VarNum));for i=1:VarNumChildren1(Points(2*i-1):Points(2*i))=Parent2(Points(2*i-1):Points(2*i));Children2(Points(2*i-1):Points(2*i))=Parent1(Points(2*i-1):Points(2*i));end% -- 变异操作--function[NewPop]=Mutation(OldPop,fit,pMutation,VarNum,opts) global m n NewPopNewPop=OldPop;r=rand(1,m);MutIn=find(r=pMutation);L=length(MutIn);完整可以运行的数值优化遗传算法源代码i=1;if opts(1)==1%浮点变异maxfit=max(fit);upfit=maxfit+0.05*abs(maxfit);if opts(2)==1|opts(2)==3while(i=L)%自适应变异（自增或自减）Point=unidrnd(n);T=(1-fit(MutIn(i))/upfit)^2;q=abs(1-rand^T);%if q1%按严格数学推理来说，这段程序是不能缺少的% q=1%endp=OldPop(MutIn(i),Point)*(1-q);if unidrnd(2)==1NewPop(MutIn(i),Point)=p+q;elseNewPop(MutIn(i),Point)=p;endi=i+1;endelseif opts(2)==2|opts(2)==4%AEA变异（任意变量的某一位变异）while(i=L)Point=unidrnd(n);T=(1-abs(upfit-fit(MutIn(i)))/upfit)^2;v=1+unidrnd(1+ceil(10*T));%v=1+unidrnd(5+ceil(10*eranum/MaxEranum));q=mod(floor(OldPop(MutIn(i),Point)*10^v),10);NewPop(MutIn(i),Point)=OldPop(MutIn(i),Point)-(q-unidrnd(9))/10^v;i=i+1;endelsewhile(i=L)Point=unidrnd(n);if round(rand)NewPop(MutIn(i),Point)=OldPop(MutIn(i),Point)*(1-rand);elseNewPop(MutIn(i),Point)=OldPop(MutIn(i),Point)+(1-OldPop(MutIn(i),Point))*rand; endi=i+1;endendelseif opts(1)==0%二进制串变异if L=1while i=Lk=unidrnd(n,1,VarNum); %设置变异点数(=变量数)for j=1:length(k)if NewPop(MutIn(i),k(j))==1NewPop(MutIn(i),k(j))=0;else完整可以运行的数值优化遗传算法源代码NewPop(MutIn(i),k(j))=1;endendi=i+1;endendelse%Tsp变异if opts(2)==1|opts(2)==2|opts(2)==3|opts(2)==4numMut=ceil(pMutation*m);r=unidrnd(m,numMut,2);[LocalMinfit,In]=min(fit(r),[],2);SelectIn=r((In-1)*numMut+[1:numMut]');while(i=numMut)mPoints=sort(unidrnd(n,1,2));if mPoints(1)~=mPoints(2)NewPop(SelectIn(i),1:mPoints(1)-1)=OldPop(SelectIn(i),1:mPoints(1)-1);NewPop(SelectIn(i),mPoints(1):mPoints(2)-1)=OldPop(SelectIn(i),mPoints(1)+1:mPoints(2));NewPop(SelectIn(i),mPoints(2))=OldPop(SelectIn(i),mPoints(1));NewPop(SelectIn(i),mPoints(2)+1:n)=OldPop(SelectIn(i),mPoints( 2)+1:n);elseNewPop(SelectIn(i),:)=OldPop(SelectIn(i),:);endi=i+1;endr=rand(1,m);MutIn=find(r=pMutation);L=length(MutIn);while i=LmPoints=sort(unidrnd(n,1,2));rIn=randperm(mPoints(2)-mPoints(1)+1);NewPop(MutIn(i),mPoints(1):mPoints(2))=OldPop(MutIn(i),mPoin ts(1)+rIn-1);i=i+1;endendend% -- 倒位操作--function [NewPop]=Inversion(OldPop,pInversion)global m n NewPopNewPop=OldPop;r=rand(1,m);PopIn=find(r=pInversion);len=length(PopIn);if len=1while(i=len)d=sort(unidrnd(n,1,2));完整可以运行的数值优化遗传算法源代码NewPop(PopIn(i),d(1):d(2))=OldPop(PopIn(i),d(2):-1:d(1)); i=i+1;。

matlab遗传算法求解指派问题
遗传算法（Genetic Algorithm）是一种模拟自然界遗传和进化过程的优化算法，在解决指派问题（Assignment Problem）中具有较好的效果。

指派问题是在给定的
N个任务和N个工人之间，如何分配任务，使得总成本或总效益达到最优化的问题。

使用MATLAB编程语言，我们可以实现遗传算法来求解指派问题。

首先，我
们需要定义一个适应度函数来衡量每个个体的优劣程度。

对于指派问题，适应度函数可以是总成本的负数，或者总效益的正数。

接下来，我们需要定义遗传算法的基本操作，包括选择、交叉和变异。

选择操
作根据个体的适应度进行概率选择，选择适应度较高的个体作为父代。

交叉操作通过交换父代个体的基因片段来产生新的子代个体。

变异操作随机改变个体的某个基因值，增加种群的多样性。

在编写遗传算法代码之前，我们首先需要构建指派问题的数学模型，并使用MATLAB提供的优化函数（如linprog）求解这个模型。

然后，我们可以使用遗传
算法对结果进行进一步优化，以获得更好的解。

在编写遗传算法代码时，我们需要定义种群大小、迭代次数、交叉概率和变异
概率等参数。

通过多次迭代，遗传算法能够搜索到较优的解，并逐渐收敛到最优解。

最后，我们可以将遗传算法求解的指派问题结果与其他方法进行比较，评估遗
传算法在解决指派问题中的效果。

综上所述，遗传算法是一种有效求解指派问题的方法，在MATLAB中实现遗
传算法可以帮助我们得到更好的解。

使用合适的适应度函数和遗传算法操作，我们可以提高算法的性能，并得到最优的任务分配方案。

遗传算法解决旅行商(TSP)问题旅行商问题(traveling saleman problem,简称tsp)：已知N个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。

如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？本程序使用MATLAB软件，利用遗传算法解决TSP问题。

程序使用如下：gatsp 为主程序，cityNum为城市个数，在此程序中可以设置为30、50和70。

Inn是种群个数，gnmax是最大迭代次数，pc是交叉概率，pm是变异概率。

算法程序运行结果如下：算法程序如下（不同的function需放在不同的.m文件中）：注：红色部分不属于算法内容，仅作间隔标致。

-------------------------------------------------------------------------------------------------------%主程序：%遗传算法求解tspfunction gaTSPCityNum=30;[dislist,Clist]=tsp(CityNum);inn=100; %初始种群大小gnmax=1000; %最大代数pc=0.9; %交叉概率pm=0.08; %变异概率%产生初始种群for i=1:inns(i,:)=randperm(CityNum);end[f,p]=objf(s,dislist);gn=1;while gn<gnmax+1for j=1:2:innseln=sel(s,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,:);drawTSP(Clist,x,ymax(gn),gn,0);gn=gn+1;%pause;endgn=gn-1;figure(2);plot(ymax,'r'); hold on;plot(ymean,'b');grid;title('搜索过程');legend('最优解','平均解');string1=['最终度',num2str(ymax(gn))];gtext(string1);End----------------------------------------------------------------- %交叉程序：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:chb1while 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=find(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=find(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 [f,p]=objf(s,dislist);inn=size(s,1); %读取种群大小for i=1:innf(i)=caldist(dislist,s(i,:)); %计算函数值，即适应度endf=1000./f';%计算选择概率fsum=0;for i=1:innfsum=fsum+f(i)^15;endfor i=1:innps(i)=f(i)^15/fsum;end%计算累积概率p(1)=ps(1);for i=2:innp(i)=p(i-1)+ps(i);endp=p';end----------------------------------------------------------------- %选着个体程序：function seln=sel(s,p);inn=size(p,1);%从种群中选择两个个体for i=1:2r=rand; %产生一个随机数prand=p-r;j=1;while prand(j)<0j=j+1;endseln(i)=j; %选中个体的序号endend-----------------------------------------------------------------%城市坐标：function [DLn,cityn]=tsp(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:10DL10(i,j)=((city10(i,1)-city10(j,1))^2+(city10(i,2)-city10(j,2))^ 2)^0.5;endendDLn=DL10;cityn=city10;endif n==30city30=[41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50];%30 cities d'=423.741 by D B Fogelfor i=1:30for j=1:30DL30(i,j)=((city30(i,1)-city30(j,1))^2+(city30(i,2)-city30(j,2))^ 2)^0.5;endendDLn=DL30;cityn=city30;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;6369;52 64;43 67];%50 cities d'=427.855 by D B Fogelfor i=1:50for j=1:50DL50(i,j)=((city50(i,1)-city50(j,1))^2+(city50(i,2)-city50(j,2))^ 2)^0.5;endendDLn=DL50;cityn=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:75DL75(i,j)=((city75(i,1)-city75(j,1))^2+(city75(i,2)-city75(j,2))^ 2)^0.5;endendDLn=DL75;cityn=city75;endend----------------------------------------------------------------- %根据交叉概率决定是否进行交叉操作：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 F=caldist(dislist,s)distan=0;n=size(s,2);for i=1:n-1distan=distan+dislist(s(i),s(i+1));enddistan=distan+dislist(s(n),s(1));F=distan;----------------------------------------------------------------- %作图：function m=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(B SF(i+1),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFace Color','g');hold on;endplot([Clist(BSF(CityNum),1),Clist(BSF(1),1)],[Clist(BSF(CityNum), 2),Clist(BSF(1),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','Ma rkerFaceColor','g');title([num2str(CityNum),'城市TSP']);if f==0text(1.5,1.5,['第',int2str(p),' 步',' 最短距离为',num2str(bsf)]);elsetext(1,1,['最终搜索结果：最短距离 ',num2str(bsf)]);endhold off;pause(0.05)-----------------------------------------------------------------。

基于遗传算法的旅行商问题求解摘要采用MATLAB，对TSP问题进行基于遗传算法的求解。

TSP 问题是典型的NP完全问题，通过MATLAB进行遗传算法编程，从而有效提出一个较好的TSP解，实现对问题的解答。

进而讨论遗传算法的特点，以及对本问题的可行性。

关键词：TSP问题遗传算法一．问题重述假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。

路径的选择目标是要求得的路径路程为所有路径之中的最小值。

TSP 问题是一个组合优化问题。

该问题可以被证明具有NPC 计算复杂性。

因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。

二．遗传算法（GA ）概述遗传算法（Genetic Algorithm ）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan 大学J.Holland 教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems 》，GA 这个名称才逐渐为人所知，J.Holland 教授所提出的GA 通常为简单遗传算法（SGA ）。

三．问题分析TSP 问题就是寻找一条最短的遍历n 个城市的最短路径, 即搜索自然数子集W={ 1 ,2 , ⋯, n} ( W 的元素表示对n 个城市的编号) 的一个排列π( W) = { V1 , V2 , ⋯, Vn} , 使len = ∑ d ( Vi , Vi+1) + d ( V1 , Vn)取最小值, 式中的d ( Vi , Vi+1) 表示城市Vi 到城市Vi + 1的距离.遗传算法是具有“生成+检测”的迭代过程的搜索算法。

它的基本处理流程如图1所示。

由此流程图可见，遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。

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)=al23.pha*(1-alpha).^(i-1) 。

遗传算法（Genetic Algorithm，GA）是一种模拟生物进化过程的搜索和优化算法，通过模拟生物的遗传、交叉和变异操作来寻找问题的最优解。

它以一种迭代的方式生成和改进解决方案，并通过评估每个解决方案的适应度来选择下一代解决方案。

在Matlab中，遗传算法优化工具箱提供了方便的函数和工具，可以帮助用户快速开发和实现遗传算法优化问题。

下面，我们以一个简单的最优化问题为例，演示在Matlab中如何使用遗传算法优化工具箱进行优化。

假设我们要优化一个简单的函数f(x)，其中x是一个实数。

我们的目标是找到使得f(x)取得最小值的x值。

具体来说，我们将优化以下函数： f(x) = x² - 4x + 4首先，我们在Matlab中定义目标函数f(x)的句柄（用于计算函数值）和约束条件（如果有的话）。

代码如下：function y = testfunction(x)y = x^2 - 4*x + 4;end接下来，我们需要使用遗传算法优化工具箱的函数ga来进行优化。

我们需要指定目标函数的句柄、变量的取值范围和约束条件（如果有的话），以及其他一些可选参数。

以下是一个示例代码：options = gaoptimset('Display', 'iter'); % 设置显示迭代过程lb = -10; % 变量下界ub = 10; % 变量上界[x, fval] = ga(@testfunction, 1, [], [], [], [], lb, ub, [], options);在上面的代码中，gaoptimset函数用于设置遗传算法的参数。

在这里，我们使用了可选参数'Display'，它的值设置为'iter'，表示显示迭代过程。

变量lb和ub分别指定了变量的取值范围，我们在这里将其设置为-10到10之间的任意实数。

横线[]表示没有约束条件。

function [R,Rlength]= GA_TSP(xyCity,dCity,Population,nPopulation,pCrossover,percent,pMutation,generation,nR,rr,rang eCity,rR,moffspring,record,pi,Shock,maxShock)clear allA=load('d.txt');AxyCity=[A(1,:);A(2,:)]; %x,y为各地点坐标xyCityfigure(1)grid onhold onscatter(xyCity(1,:),xyCity(2,:),'b+')grid onnCity=50;nCityfor i=1:nCity %计算城市间距离for j=1:nCitydCity(i,j)=abs(xyCity(1,i)-xyCity(1,j))+abs(xyCity(2,i)-xyCity(2,j));endend %计算城市间距离xyCity; %显示城市坐标dCity %显示城市距离矩阵%初始种群k=input('取点操作结束'); %取点时对操作保护disp('-------------------')nPopulation=input('种群个体数量：'); %输入种群个体数量if size(nPopulation,1)==0nPopulation=50; %默认值endfor i=1:nPopulationPopulation(i,:)=randperm(nCity-1); %产生随机个体endPopulation %显示初始种群pCrossover=input('交叉概率：'); %输入交叉概率percent=input('交叉部分占整体的百分比：'); %输入交叉比率pMutation=input('突变概率：'); %输入突变概率nRemain=input('最优个体保留最大数量：');pi(1)=input('选择操作最优个体被保护概率：');%输入最优个体被保护概率pi(2)=input('交叉操作最优个体被保护概率：');pi(3)=input('突变操作最优个体被保护概率：');maxShock=input('最大突变概率：');if size(pCrossover,1)==0pCrossover=0.85;endif size(percent,1)==0percent=0.5;endif size(pMutation,1)==0pMutation=0.05;endShock=0;rr=0;Rlength=0;counter1=0;counter2=0;R=zeros(1,nCity-1);[newPopulation,R,Rlength,counter2,rr]=select(Population,nPopulation,nCity,dCity,Rlength,R,coun ter2,pi,nRemain);R0=R;record(1,:)=R;rR(1)=Rlength;Rlength0=Rlength;generation=input('算法终止条件A.最多迭代次数：');%输入算法终止条件if size(generation,1)==0generation=200;endnR=input('算法终止条件B.最短路径连续保持不变代数：');if size(nR,1)==0nR=10;endwhile counter1<generation&counter2<nRif counter2<nR*1/5Shock=0;elseif counter2<nR*2/5Shock=maxShock*1/4-pMutation;elseif counter2<nR*3/5Shock=maxShock*2/4-pMutation;elseif counter2<nR*4/5Shock=maxShock*3/4-pMutation;elseShock=maxShock-pMutation;endcounter1newPopulationoffspring=crossover(newPopulation,nCity,pCrossover,percent,nPopulation,rr,pi,nRemain);offspringmoffspring=Mutation(offspring,nCity,pMutation,nPopulation,rr,pi,nRemain,Shock);[newPopulation,R,Rlength,counter2,rr]=select(moffspring,nPopulation,nCity,dCity,Rlength,R,coun ter2,pi,nRemain);counter1=counter1+1;rR(counter1+1)=Rlength;record(counter1+1,:)=R;endR0;Rlength0;R;Rlength;minR=min(rR);disp('最短路经出现代数:')rr=find(rR==minR)disp('最短路经:')record(rr,:);mR=record(rr(1,1),:)disp('终止条件一:')counter1disp('终止条件二:')counter2disp('最短路经长度:')minRdisp('最初路经长度:')rR(1)figure(2)plotaiwa(xyCity,mR,nCity)figure(3)i=1:counter1+1;plot(i,rR(i))grid onfunction[newPopulation,R,Rlength,counter2,rr]=select(Population,nPopulation,nCity,dCity,Rlength,R,coun ter2,pi,nRemain)Distance=zeros(nPopulation,1); %零化路径长度Fitness=zeros(nPopulation,1); %零化适应概率Sum=0; %路径长度for i=1:nPopulation %计算个体路径长度for j=1:nCity-2Distance(i)=Distance(i)+dCity(Population(i,j),Population(i,j+1));end %对路径长度调整，增加起始点到路径首尾点的距离Distance(i)=Distance(i)+dCity(Population(i,1),nCity)+dCity(Population(i,nCity-1),nCity);Sum=Sum+Distance(i); %累计总路径长度end %计算个体路径长度if Rlength==min(Distance)counter2=counter2+1;elsecounter2=0;endRlength=min(Distance); %更新最短路径长度Rlength;rr=find(Distance==Rlength);R=Population(rr(1,1),:); %更新最短路径for i=1:nPopulationFitness(i)=(max(Distance)-Distance(i)+0.001)/(nPopulation*(max(Distance)+0.001)-Sum); %适应概率=个体/总和。