首页 >
论文范文 >
自然科学论文 >
数学论文 >
运筹学论文 >
关于TSP问题高效率演化算法的探究
摘要：旅行商(TSP)问题是一个被证明具有NP计算复杂性的组合优化问题.郭涛算法在求解TSP问题的高效率是得到广泛认可的，其算法的核心在于Inver-over算子的设计.当节点数量较多时，该算法在寻找近似最优解仍然有很好的表现，但其寻找全局最优解的能力却会下降.提出的基于基因片段插入的演化算法，它能以较高的概率找到TSP问题的最优解.文中提出一种新的演化算法，将基于基因片段插入与Inver-over算子进行融合.实验证明：新算法可有效防止解的早熟，增强了算法的全局搜索能力，使算法获得全局最优解的概率大大提高，同时仍然具备高效率的特性.
加入收藏
1948年由美国兰德公司推动的TSP是一个较古老的巡回旅行商问题[1]，成为近代组合优化领域的一个典型难题，已被证明为NP难题.TSP描述为在一个加权无向图中，寻找一个边的权值之和最小的Hamilton圈.
随着TSP的研究和利用的不断扩展，图的复杂程度不断加大，导致TSP求解的搜索空间不断加大.诸多学者也提出了多种不同的求解TSP问题的算法.其中，湖水能量算法[2]就是一种高效的求解算法，但其缺点在于找到最优解的概率较低.郭涛算法[3](GT）是一种改进遗传演化算法，被证明是一种效率很高的算法.但是，随着图的规模和复杂度增大，GT算法找到最优解的概率不断下降.蔡之华[4]，谢大同[5]等给出了一种对郭涛算法或其Inver-over算子[3]进行改进的求解TSP问题的演化算法，经过实验证明其找到最优解的能力虽有改善，但仍不够理想，其在实例CHN144上找到最优解的概率仅为0.7.本文采用粒子群[6]的基因片段插入[7,8]与Inver-over算子结合，随机的在粒子中插入其他粒子的片段，以达到扩大粒子搜索范围的作用，从而防止算法解的早熟.
1、新的演化算法
为方便算法描述，先对算法中使用的参数、符号和数据作以下说明.
给定n个城市{1,2,…,n}以及对应的坐标值，记两个城市i和j之间的距离d(i,j).用c1c2…cn来表示TSP的一个解的路径（其中1≤ci≤n,且c1c2…cn互不相同），并称c1c2…cn为一个个体p，一组个体的集合称为P，第i个个体称为Pi.c1c2…cn个体的长度定义为d(c1,c2)+d(c2,c3)+⋯+d(cn-1,cn)+d(cn,c1).设1≤t≤n-1,长度为l的路径cici+1…ci+t称为个体c1c2…cn的一个起始位置为i，长度为t的基因片段(若下标大于n,则将此下标除n取余数).
1.1郭涛算法
郭涛算法提出的Inver-over算子具有杂交和变异的演化特征，算法在设置群体规模参数后，按照随机倒置概率ρ对个体进行盲目或自适应的两种方式倒置，直到满足结束条件，算法结束.其中，倒置操作作用于个体的局部，随机倒置概率ρ一般设置很小，大部分倒置操作来自群体中的其他个体，达到加快收敛的目的；极少部分随机产生，其作用打破收敛趋势，增加搜索全局最优解的可能性.郭涛算法对个体Pi操作如图1所示.
图1郭涛算法的Inver-over算子
TSP结果得到的路径是个闭合的环路，每次操作都对基因片段进行反转，算法运行的速度快.因此，郭涛算法相比于其他演化算法在求解质量和速度上都有较好效果，这主要在于算法中群体趋优信息得到了充分的利用.但是在试验中也发现，郭涛算法对于小规模TSP问题的求解效果优异，但是对于解决规模较大的TSP问题，其寻找全局最优解的效果就大为下降.这主要是由于该算法的操作迭代在前期的收敛速度很快，而到了后期，群体中的粒子所表示的解的路径都是没有交叉的较优环形路径，所以算法在后期的收敛速度明显变慢，且容易陷入局部最优解.
1.2基因片段插入运算
基因片段插入对个体Pi的运算如图2所示.
图2基因片段插入运算
取Q(j),R(j)中的最小值，若最小值为Q(m)，则将基因片段S正序插入到Pi'的cm与cm+1之间，若最小值为R(m),则将基因片段S逆序插入到Pi'的cm与cm+1之间，得到新的个体.
基因片段插入运算的主要思想是在于通过从群体的其它个体中截取部分基因片段插入到原个体，以达到保持个体的多样性和改善个体局部的目的.
1.3混合算法
根据算法分析和试验结果，本文将郭涛算法的Inver-over算子与基因片段插入算法相融合，提出了一个新的算法.混合算法描述如下.
Input：城市数n及各城市对应位置坐标.
Output：输出全局最优解global＿best及其路径长度gb＿length.
Step1：设置种群中个体个数N＿ALL(一般设置为N＿ALL=4n)及算法迭代次数T.
初始化所有个体，其中n个个体利用贪心算法从城市i开始产生{P1,P2,⋯,Pn-1,Pn}，其余N＿ALL＿n个个体采用随机方式产生，得到N＿ALL个个体的种群{P1,P2,⋯,Pn,Pn+1,⋯,PN＿ALL}，记迭代计数变量T＿number=0.
Step2：将个体Pi的值保存到R，即(R=Pi).
1）使用郭涛算法对个体R进行操作.
2）生成3个随机数j(1≤j≤N＿ALL,j≠i)、s(1≤wz≤n)、k(2≤k≤n/6),其中k=2+(int)((rand()%(n/6-1))*(1-T＿number%(2*n)*0.98/(2*n))).然后，从个体Pj的起始位置为s，长为k的基因片段gene，并把gene采用基因片段插入算法插入到个体R中.若R的路径长度小于Pi路径长度，则Pi=R.
Step3:T＿number=T＿number+1.
Step4：如果T＿number<T,则执行Step2；否则转至Step5.
Step5：从种群中找出最优个体,并将个体及其路径长度分别保存至global＿best和gb＿length.
此算法不仅保持种群中个体的多样性，扩大种群对解的搜索能力，同时对个体的局部进行有针对性的改良.算法中，空间复杂度主要体现在种群的存储空间，为O(n2).郭涛算法的时间复杂度为O(n2)，基因片段插入的时间复杂度为O(n3)，迭代次数为T，因此算法的时间复杂度为O(n3T).
2、仿真试验
仿真试验采用TSPLIB中的Eil51、st70、ch150、pr226以及中国144个城市的Ch144等5个实例作为试验用例.在试验过程中，将5组用例分别采用郭涛算法、基因片段插入算法和混合算法各重复运行50次，以最多迭代n2次为限制，得到对比数据如表1所示.
表1测试结果对比
从表1中的试验对比数据可见，使用郭涛算法单独求解时，当图的规模变大后，其迭代次数极具增加，且找到最优解的概率也不断下降.而单独使用基因片段插入算法进行求解时，效率较不稳定，且找到最优解的概率也不够理想.但采用两个算法结合的混合算法，对上述5个试验用例进行50次试验均找到最优解.虽然该混合算法的时间复杂度较高，但其优异的搜索能力和收敛速度，其找到最优解的迭代次数远低于n2，也低于其它两个算法的迭代次数，即使在图的规模增大的情况下，其迭代次数也未明显增加.
3、结论
本文将两种算法融合产生一种新的求解旅行商问题的演化算法.试验结果表明，该算法不仅能够有效地提高找到最优解的概率，而且运行效率很高，是一种有效可行的算法.
参考文献：
[2]冯翔,马美怡,虞慧群.TSP湖水能量优化算法[J].计算机研究与发展,2013,50(9):2015-2027.
[4]蔡之华,彭锦国,高伟,等.一种改进的求解TSP问题的演化算法[J].计算机学报,2005,28(5):823-827.
[5]谢大同,李程俊,康立山.基于改进Inver-over算子的并行TSP演化算法[J].计算机工程与设计,2007,28(10):2248-2251.
[6]郭文忠,陈国龙.离散粒子群优化算法及其应用[M].北京:清华大学出版社,2012.
[7]杨辉,康立山,陈毓屏.一种基于构建基因库求解TSP问题的遗传算法[J].计算机学报,2003,26(12):1753-1758.
[8]刘欣欣,陈宝兴.基于基因片段插入的旅行商问题的演化算法研究[J].闽南师范大学学报(自然科学版),2014,27(3):34-36.
许冲,钟玮,刘欣欣.一种求解旅行商问题的演化算法研究[J].闽南师范大学学报(自然科学版),2020,33(02):44-48.
基金:福建省中青年项目(JAT170351,JAT170361).
分享：
2020年5月28日，教育部印发《高等学校课程思政建设指导纲要》，全面推进高校课程思政建设。《纲要》指出，全面推进高校课程思政建设是深入贯彻习近平总书记关于教育的重要论述和全国教育大会精神、落实立德树人根本任务的战略举措，高校要深化教育教学改革，充分挖掘各类课程思想政治资源，发挥好每门课程的育人作用，全面提高人才培养质量。
2020-11-21
随着现代科学技术的飞速发展,运筹学相关研究日渐深入,应用范围日趋广泛,在军事领域中的作用也越来越重要。军事运筹学是应用数学和计算机等科学技术方法系统研究各类军事活动,并为决策优化提供理论和方法的军事学科,具有多学科综合交叉、注重实际应用、应用范围广、注重方案的最优性等特点。
2020-08-10
《运筹学》是一门把科学的方法应用于建立和求解数学模型，以便采取行动解决实际问题的科学。也就是运用科学的方法（如分析、试验、量化等）来决定如何最佳地运营和设计各种系统的一门学科。[1,2]运筹学也是一门综合性学科，其整合了数学、计算机及其其他相关科学内容，以期获得最优的结果做出最准确的决策。
2020-08-10
在全球能源消费日益增长的背景下，除了建造新的发电厂外，“需求响应”为缓解紧张的电力需求提供了一个经济有效的方法。在需求响应模式下，供电商在电力批发市场价格升高或系统可靠性受威胁时给电力用户发出电力价格变更信号或诱导性调整负荷通知，电力用户根据这些信号改变习惯用电模式，错峰用电，从而保障电网稳定，并抑制电价上升的短期行为。
2020-07-08
RGV是一种无人驾驶、能在固定轨道上自由运行的智能车。它根据指令来控制移动方向还有距离，具有一个机械手臂、两只机械手爪加一个物料的清洗槽，能够完成上下料及清洗物料等任务。2003年，Malmborg教授及其课题组首先提出自动小车存取系统，它主要包括轨道导引小车系统，通过RGVS小车进行货物存取。
2020-07-08
专利是知识产权的主要表达形式，在当今知识经济、科技引领的时代下，已成为企业发展和竞争的制高点。专利质量体系与企业的运营发展息息相关，企业传统的产品市场占有量发展模式逐步采用创新竞争模式。对于企业而言，专利是保护自身产品、防御对他人侵权的重要武器；是企业技术创新能力的证明；是企业规划开辟多源收入的重要手段。
2020-07-08
在工程设计中，材料不均匀、安装误差等问题的存在，往往会对结构性能造成各种影响甚至破坏。传统结构设计没有考虑施工过程中的不确定因素，而实际施工中载荷和材料性质等不断变化，这些不确定因素会使失效概率不断增大。为了确保产品的结构可靠性，有必要对不确定结构可靠度分析方法进行研究。
2020-07-08
“魔鬼在细节”。做好国际工程项目，要如履薄冰，因为往往一个细节的疏忽，就会导致项目成本大幅增加。做好一个项目，业主和承包商之间需要一种良好的合作氛围。对于承包商来说，不能过于计较一城一池的得失，该放弃的放弃，该争取的争取，最终会形成一个共赢的局面。
2020-07-08
依据《孙子兵法》对国家情报战略进行系统运筹，能够明确在国际情报对抗中的情报主体与情报客体的资源与结构，所面临的问题和所受的限制，指导国家情报工作有目的地进行“造形”与“治气”，创造情报主体的行动优势，取得情报对抗的胜利，为国家安全与发展保驾护航。
2020-07-08
自由粒子优化算法作为基于量子算法模型中的骨架模型，结构简洁，易于实现，通过对算法进行策略的改进，会使得算法的性能得到很好的提升。在自由粒子模型下的零势阱和谐振子模型下的高斯势阱的启发下，将优化问题中的目标函数进行势阱等效和泰勒近似实现量子模型下的转化，通过粒子在空间中的存在形式指导优化算法的寻优过程，实现量子模型的搜索机制。
2020-07-08
人气：3213
人气：2792
人气：2635
人气：2550
人气：1561
我要评论
期刊名称：运筹与管理
期刊人气：3026
主管单位：中国科学技术协会
主办单位：中国运筹学会
出版地方：安徽
专业分类：科学
国际刊号：1007-3221
国内刊号：34-1133/G3
邮发代号：16-191
创刊时间：1992年
发行周期：月刊
期刊开本：大16开
见刊时间：一年半以上
影响因子：0.553
影响因子：0.322
影响因子：0.352
影响因子：0.000
影响因子：0.000
科普杂志阅读、期刊信息查询、论文下载、文献查询、原创文章检测等多项服务。
服务热线
您的论文已提交，我们会尽快联系您，请耐心等待！
你的密码已发送到您的邮箱，请查看！
2020-07-08
235
上传者：管理员
