英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料
一种新的遗传选择算子amp;CSM求解TSP的算法
摘要
遗传算法是一种模拟生物进化的局部搜索算法。它会根据物竞天择，适者生存的原理编码出可能的解决方案并组合他们，最后筛选出最优的解。遗传算法中最重要的算子之一是选择运算符。本文提出了一种新的选择算子，称之为聚类选择法（CSM）。此方法已经开始实施并在解决商旅问题得到测验。我们对提出的CSM算法进行了测试然后和其他选择算法进行对比，例如随机选择，轮盘赌轮选择和竞赛选择。结果表明，在应用于解决100个城市的商旅问题时，CSM的效果最好，因为它只有8840次迭代就达到了最优路径，最小距离为79.7234。
遗传算法；旅行商问题；
遗传算法算子；聚类；选择算子
- 引言
遗传算法（GA）是一种进化算法（EAs），这是一种基于自然进化的算法[2，4，6]。
GA使用随机搜索技术，现在已经发展成一种强力的、求解复杂随机组合优化问题的方法。在为特定设计筛选出一组可用的解决方案时，这种算法被认为是最重要的技术之一。
遗传算法（GA）最早是由John Holland提出来，它的依据是达尔文的折中主义原则[1，6]。
商旅问题是最常见的深入研究计算数学难题的问题之一，这是一个不确定的多项式时间问题，TSP需要求出往返各城市之间最有效率的路径（即-最小总距离）。已知的TSP问题解决方案中没有主流解法。TSP关注于优化路径解决方案，销售人员可以通过和访问的城市每个只有一次，最后回到家乡[2，7]。
在遗传算法过程中，选择方法是从种群中选择亲本进行重组，以及主要是在选择步骤之前加上适应值基于目标值的赋值。其中使用不同选择方法的遗传算法的性能是通常用收敛速度和达到问题的最优解的代数[5]。GAs中使用的选择方法有很多种，在本文中，作者将提出一种新的选择算子。
在本文中提出了一种新的选择算法，此算法已经经过了测试，并与其它选择方法进行比较，其结果显示新方法通过减少世代来加强了遗传算法的性能。
本文包括以下几个部分：引言为第一部分，GA将会在第二部分着重讨论，第三部分将会介绍TSP问题，第四部分阐释所研究的问题报告，然后选择方法会在第五节中描述，提出的方法将会在第六节中讨论，接着第七节会进行实验测试，最后在第八节阐明结论。
- 遗传算法
遗传算法一般由两个部分组成，第一个过程是选择父代对象，复制到下一代[4, 6]。第二个过程是操纵选定的父代对象来改变关于适应度的交叉和变异算子对新生后代的价值[3]。
图1展示了遗传算法的过程[1]，其中GA包括以下步骤：[6，7]
- [开始] 产生n个染色体的随机群体对它们进行编码。
- [适应度] 评估每个染色体的适应度f（x）人口中的x。
- [新人口] 通过重复以下步骤，直到新的人口填充完成：
- [选择] 根据群体的健康状况来选择父代染色体。
- [交叉] 交叉是概率杂交选定的父母以产生新的后代
- [变异] 变异是概率是变异新的后代。
- [接受] 把新的后代放在一个新的人口上。
- [替换] 将新生成的填充用于进一步运行算法。
- [测试] 如果满足终止条件，则停止算法，返回当前最佳解人口。
- 旅行商问题
旅行商问题由以下几个部分组合而成：一定数量的城市，每对城市都有相等的距离，这个推销员的目标是能游览所有的城市。所以，总的来说行驶距离将会最小化。
TSP在概念上很简单，尽管很难得到n之间最短路径的最优解城市。这个问题的主要困难在于可能的路径，由（n-1）！/n来估算n个城市。这个当城市的数量增加后，有效路径的变化数也为增加。一些研究人员试图通过利用GA来找到TSP问题的最佳路径[2, 7]。
- 问题陈述
下一代的父母选择是最重要的遗传算法中的算子，因为问题的解依赖于那个复制者，其重要性在于它将选取能创造下一代的后代。有很多种选择算法法，如轮盘赌，等级等。其中一些方法在其他人通过排序选择父代对象，然后选择最健康最有价值的父母，这种做法不一定会保证筛选出来的最终后代是最优解。 因此，进化的世代数取决于是否达成了可接受的解决方案最优或当迭代次数是否超过时。因此，为了最佳的预期表现，如何获得最佳使用最小生成数的解决方案成为了重点，以确保效率更高，速度更快。
- 选择方法
选择机制决定了哪些人会选择交配（繁殖）以繁殖新一代。选择方法的主要目的是选择可以在种群达到最优解[3]。选择方法的主要目的是选择可以在种群中达到最优解。在遗传算法中，关于选择方法最重要的思考方向是该如何确定最合适的选择方法来增加速度，增加TSP中的距离达到最小最优路径的进化速度[8]。
选择方法有很多种，如轮盘赌选拔；锦标赛选拔；精英选拔；排名选择；随机普适抽样；局部选择；截断选择等等[8]。
- 提出的聚类选择方法
提出的聚类选择方法（CSM），基于从每个聚类的个体数目不同的聚类中选择双亲，通过将所有与其适应度值最接近的个体收集在同一个聚类中来创建聚类，如图2所示。然后，根据适应度函数，从相对于最高或最低适应度值具有更多元素的簇中选择父对象。
CSM首先将种群中的个体按照其适应值的升序或降序进行排序。在这之后，使用方程（1）评估ALFA值（alpha;），使用标准差（STD），因为它是分布数的度量，或者一个群体中的个体（pop）在平均值周围分布的程度。alpha;值将用于确定簇（即评估种群中个体之间的离散量）。其中，低标准差意味着数据是紧密聚集的；高标准差意味着数据是广泛分散的，并且通过使用STD的平方根将有更多的机会确定最接近的个体来创建聚集。
ALFA = SQRT (STD (pop)) (1)
之后，根据种群中个体之间的离散量来划分种群。种群根据alpha;值进行划分，alpha;值将创建多个簇，其中每个簇包含不同数量的个体。
然后，对于每个聚类，使用方程（2）计算STD和差分（D）来计算聚类值（CV）。通过计算集群子种群（CS_pop）中所有个体的STD，并通过计算CS_pop中所有个体的精细度值之间的D。通过在D中加1来避免除以0（当健身在CS_pop中等于或没有差异时）。
然后通过比较所有聚类的CV值，“最高CV”意味着这个聚类包含最接近的个体和大量的个体，这就是我们的目标。然后我们将考虑这个高CV的聚类，从中选出下一代的亲本。对于最大化问题，考虑从该簇中选择最高适应值作为父节点；对于最小化问题，考虑选择最低适应值作为父节点。如图3所示。
- 实验测试
将该方法应用于遗传算法中，并用MATLAB对10、20、30、40、50、60、70、80、90和100个城市的TSP进行了求解。该系统每种情况下执行10000代，或直到找到最佳路径，采用表1中列出的不同选择方法。
表2：用不同的选择方法和建议的CSM演示了系统实施的最终结果，其中：
· Dis：n个城市之间的平均距离。
· 外径：所有路径距离的升序顺序，如果有任何相等的值，它们将具有相同的顺序。
· Itr：达到最佳路径的平均迭代次数。
· O.I：迭代的顺序，如果有任何相等的值，它们将具有相同的顺序。
· O.T:O.I乘以O.D。
表3：总结了10-100个城市TSP的最终分析结果。结果表明，基于和Dis和和O.T值的CSM
方法是最优的，因为它们比其他选择方法具有最小值。而总和Itr则是轮盘赌的最佳选择方法。
此外，还对该系统进行了三种不同的选择方法，以解决100个城市的TSP问题。
图4示出了随机选择方法（Ga）的系统结果，其中最优路径距离为80.5908，迭代次数为9159次。
最佳路径的距离为79.9358，轮盘赌轮选择方法所需的迭代次数为8864，如图5所示。
如图6所示，锦标赛选择方法在9458次迭代和距离等于82.0521的情况下达到最优路径。
所提出的方法CSM具有最好的结果，因为它仅用8840次迭代就达到了最优路径，最小距离为79.7234，如图7所示。
表4总结了图4、图5、图6和图7的结果，这些结果显示了每种方法的距离和迭代次数。
|
Method |
Distance |
Iterations |
|
Ga |
80.5908 |
9159 |
|
Roulette Wheel |
79.9358 |
8864 |
|
Tournament |
82.0521 |
9458 |
|
CSM |
79.7234 |
8840 |
- 结论
遗传算法有多种算子用于求解优化问题，如选择算子、交叉算子和变异算子。其中选择算子被认为是遗传算法中最重要的算子之一，因为它选择双亲进行重组，并对再生过程中的其他算子产生影响。
有人提出了一种新的选择亲本的方法，称为聚类选择法（CSM）。它通过收集所有最接近的个体在同一个簇中的适应度值，将种群划分为多个簇，然后从每个簇中具有不同数量个体的簇中选择父（个体）。然后，CSM将根据所选的簇来选择适合度值最高或最低的父簇，具体取决于簇值（CV）。
已经考虑了TSP对不同数量城市的检验方法，提出的城市分别为10、20、30、40、50、70、80、90和100个城市。对系统进行了10000代的测试，结果表明该方法在随机选择、轮盘赌选择和锦标赛选择方法中是最好的。
提出的CSM结果如下：Sum Dis为546.638，Sum O.T为66；这是最小值。
当系统在100个城市再次测试时，CSM也显示出了最好的结果，因为它在最小距离79.7234和8840次迭代的情况下达到了最优路径。
在以后的工作中，作者可以通过生成新的ALFA方程来修改所提出的方法，以获得更好的结果。
参考文献：
[1] S. Owais, V. Snasel, P. Kromer, and A. Abraham, “Survey: Using Genetic Algorithm Approach in Intrusion Detection Systems Techniques”, 7th Computer Information Systems and Industrial Management Applications, IEEE, 2008, pp. 300-307, June 2008.
[2] F. H. Khan, N. Khan, S. Inayatulla, And S. T. Nizami, “Solving ISP Problem by Using Genetic Algorithm “, International Journal of Basic amp; Applied Sciences IJBAS-IJENS vol. 09, no. 10, 2009, pp. 55-60.
[3] N. M. Razali, and J. Geraghty, “Genetic Algorithm Performance with Different Selection Strategies in Solving TSP”, Proceedings of the World Congress on Engineering, 2011, London, U.K., vol. II, July 2011.
[4] S. Karakatič, and V. Podgorelec, “A survey of genetic algorithms for solving multi depot vehicle routing problem”, Applied Soft Computing, vol. 27, pp. 519–532, 2015.
[5] A. Sharma, and A. Mehta, “Review Paper of Various Selection Methods in Genetic Algorithm”, Int
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[241490]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
