基于改进轮盘选择的TSP遗传算法外文翻译资料

英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料

基于改进轮盘选择的TSP遗传算法

摘要：遗传算法是典型的基于自然选择和自然遗传机制的种群智能技术，它将人类的适者生存概念和自然界的基因遗传结合起来。由于遗传算法具有良好的全局搜搜能力，以及其他的类似的优点，目前已经被广泛应用于组合优化、机器学习、信号处理领域、自适应控制和人工生命等领域。它是现代智能计算的关键技术之一。作为遗传算法的一种常用选择方法，适应度比例选择通常采用轮盘选择方法来实现。本文提出了一种基于适应度比例选择的改进选择方法。计算结果表明，本文提出的方法通过求解TSP问题提高了结果精确度和收敛性。

关键字：遗传算法（GA）；适应度比例选择；轮盘选择；旅行商问题（TSP）

1. 引言

霍兰德教授于上世纪70年代出版了《自然与人工系统的适应》，系统地阐述了遗传算法地基本理论和方法，提出了遗传算法的基本定理——模式定理，从而奠定了遗传算法的理论基础。20世纪80年代，遗传算法在各个领域得到了广泛的应用。标准的遗传算法一般包括选择、交叉和变异三种算子，它们构成了遗传算法强大搜索能力的核心。选择是模拟自然界生命繁殖和自然选择的主要载体。它是指在当前种群中选择具有高适应性的个体进行交配的过程。近年来出现了适应度比例选择、玻尔兹曼选择、排名选择、锦标赛选择和精英选择等。作为一种基本的选择模型，适应度比例选择一直是遗传算法中的一种常用选择模型，通常是在轮盘选择模型中实现。

旅行商问题是一个经典的组合优化问题，也是一个NP难问题。很长时间来，相关的研究已经取得了很大进展，但问题仍未得到彻底解决。随着城市数量规模的增加，可选路线数量呈指数级增长。由于精确的最优解通常很难找到，因此找到一个有效的求解近似解算法是很重要的。由于遗传算法不受限制性假设的约束，对搜索空间没有连续性、可导性和单峰性的要求，并且具有全局优化、隐式并行性和健壮性等特点，因此在求解诸如组合优化、模式识别和计算机网络优化等复杂问题时，该方法表现出良好的性能和效果，而传统方法很难解决这些问题。人们将遗传算法应用于大规模的TSP问题的求解，已经取得了令人满意的结果。

本文仍然以典型的TSPs问题为研究对象，通过对遗传算法和改进后的算法的运行时间和满意解个数的分析，给出改进算法的性能评价。

1. 适应度比例选择模式和优化方法

对于适应度比例选择模型，首先计算所有个体的适应度值，然后计算其适应度在种群总适应度中的比例，它代表了在选择过程中这个个体被选择的概率。对于一个给定规模为n的种群，p = {a₁, a₂, . . . ,a_n}，个体的适应度为f (a_i)，a_i isin; p，我们可以通过公式（1）计算个体适应度的选择概率。

上述公式确定了后代种群中个体的概率分布，其中，亲代群体中的预期个体存活量为 这种选择模式的整体理念是使适应度高的个体更多地繁衍，适应度低的个体更少地甚至没有繁衍。总体上来说，父母一代的个体规模等于子女一代的个体规模。计算出来的预期数量通常不是一个整数。如果采用四舍五入法，则后代种群规模通常会发生变化。轮盘赌方法就是针对这个问题。

1. 轮盘赌选择

累计概率可以用所有个体的选择概率计算出来。第k个个体的累计概率可以通过公式（2）进行计算。

然后生成一个介于0和1的随机数e，并与进行比较来决定是否选择个体。如果，那么第k个个体被选择。这个过程重复n轮，产生n个后代个体。

1. 优化选择方法

预期的个体存活量向下四舍五入达到。的总和通过公式（3）进行计算。

然后，产生（n - m）个个体组成一个完整的后代。预期的所有个体存活量按降序排列。选择顶端的（n - m）个个体来组成一个完整的后代。例如：第k个个体在顶端的（n - m）个个体中，那么第k个个体在后代中的实际选择数量是。

1. 优化前后算法比较

（1）轮盘赌方法完全依靠随机数进行选择，这增加了选择的不确定性。可以说，本文提出的优化方法实现了轮盘赌方法最理想的性能。

（2）对于一个规模为n = 100的种群，平均选择的改率仅为0.01。当种群规模进一步扩大时，即使最好的个体被选择的概率也很低。对于轮盘赌法而言，随机性可能会导致优秀个体的损失。本文的优化方法保留了优秀的个体，避免了好的解决方案的损失。

（3）采用轮盘赌方法，后代的个体不能完全依据亲代个体的适应度进行选择，而本文的优化方法则可以这样做。它充分地显示了“适者生存、劣者淘汰”的规则，这促进了收敛。

1. 实施和实验结果

本文所采用的利用遗传算法求解TSP问题的机制是自适应交叉和自适应变异算子，并且采用每代交叉和变异后保留最优值的策略。通过改进机制，可以更好地反映出不同的选择方式对遗传算法的影响。遗传算法的迭代过程如图1所示。

图1 遗传算法的流程

遗传算法和优化的遗传算法都是用C 实现的。对于遗传算法，是采用轮盘赌方法进行个体选择，而优化的遗传算法结合了改进的轮盘赌方法进行个体选择。

我们为实验选择了以下三个TSPs参照标准：BAYG29、ATT48、CH130和A280。表1给出了个别问题的参数，对于所有的情况，最大迭代次数设置为500。对于遗传算法和改进的遗传算法，种群的规模和城市的数量相同，而每个个体的基因数量相同。每种情况重复50次来进行数据分析，所有的的模拟都是在同一台计算机上进行，以便稍后的比较可以公平。

表1显示了我们的实验结果在最佳解的准确性方面的统计数据。已知的最佳解来自TSP库（TSPLIB）。在对所有情况进行500次迭代后，令人惊讶的是，优化遗传算法寻找最优解的效率显著提高。

表2显示了我们在运行时间和迭代次数方面的实验结果统计数据。可以看出，在所有情况下，经过500次迭代之后，优化遗传算法的运行时间和迭代次数均优于遗传算法。

1. 结论

适应度比例选择作为遗传算法的一种常用选择方法， 通常采用轮盘赌选择方法来实现。本文对轮盘赌选择模式进行了改进，使其更符合“适者生存”的规律。通过求解TSP问题得到的实验结果验证了该方法的有效性，该方法提高了结果的精度，促进了算法的收敛。本文中的选择方法是适应度比例选择的一种补充方法。由于遗传算法一种具有随机性的优化算法，因此应该根据实际的优化问题在这两种方法之间进行选择。

致谢

这项工作得到了中国国家自然科学基金(61063004,61363016)、内蒙古自治区自然科学基金会（2015MS0626,2015MS0605）和内蒙古自治区高校科研重点项目（NZJJ14100）的资助。

参考文献

1. J.H. Holland.自然系统与人工系统的适应. 密歇根大学出版社. 安娜堡. 1975.
2. De Jong , K .A.一类遗传自适应系统的行为分析[M] .密歇根大学 , No.79 -9381 , 1975.
3. D Applexgate, R Bixby, et al.实施DantingFulkerman-Johnson算法求解大型旅行商问题. 数学规划. 2003, 97(1-2). 91-98.
4. 李敏强，寇继松，等.基础理论与应用 遗传算法。北京：科学出版社。 2002.34-50。
5. Dong G, Fu X, Xue H.求解旅行商问题的蚁群辅助算法[J]. 国际计算机技术进步杂,2012, 4(5):165- 171.
6. Rafiei H , Rabbani M , Gholizadeh H , et al.一种新的用于求解具有序列相关设置时间的集成单元形成-作业调度问题的混合SA/GA算法[J]. 国际管理科学与工程管理杂志, 2015:1-9.
7. 刘丽丽，胡瑞生，胡新平，等.一种用于机床生产中作业车间调度的混合PSO-GA算法[J]。国际生产研究杂志，2015：1-27.
8. Umbarkar A J，Sheth P D，Babar S V.使用混合TLBO-GA算法求解0/1背包问题[J]。智能系统与计算进展，2015,335：1-10.
9. 吴连平, 杨晓翔. 基于神经网络与遗传算法的关节轴承挤压模具优化[J]. 中国机械工程, 2015, 26(10):1351-1355.
10. 高明芳，傅学良，董盖芳，李洪辉。针对旅行商问题的自适应变异多粒子群优化，第三届材料、机械和制造工程国际会议（IC3ME 2015），2015:1003-1007.

表1 采用遗传算法和优化遗传算法的TSP实验结果（每种情况下运行50次）

表2 遗传算法和优化遗传算法的运行时间和迭代次数（每种情况下运行50次）

作者

冯瑞玉（第一作者）计算机科学与信息学院工程类 内蒙古农业大学 中国 583939046@qq.com

富学良（第二作者）计算机科学与信息学院工程类 内蒙古农业大学 中国 fxliang@126.com

李宏辉（第三作者）计算机科学与信息学院工程类 内蒙古农业大学 中国Lihh_chf@163.com

董改芳（第四作者）计算机科学与信息学院工程类 内蒙古农业大学 中国Donggf@imau.edu.cn

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[20008]，资料为PDF文档或Word文档，PDF文档可免费转换为Word