首页 >
论文范文 >
自然科学论文 >
数学论文 >
运筹学论文 >
探讨TSP问题中混合粒子群算法的应用
摘要：粒子群优化算法具有快速搜索的能力,并且因为容易实现而得到广泛的应用。而传统的粒子群算法存在容易陷入局部最优解的问题,本文借助经典的TSP问题提出一种融入遗传算法中选择、交叉、变异算子的混合粒子群算法,通过与蚁群算法的实验结果进行对比分析,能够证明混合粒子群算法能够优化算法的性能,得到更好的实验结果。
加入收藏
粒子群优化算法是一种基于群体的进化算法,每一组粒子在设定空间中都是所研究的优化问题的一个解。由于PSO具有快速搜索的能力,并且参数设置简单而得到了广泛的应用。但也存在全局搜索能力弱,容易陷入局部最优的缺点,在算法后期种群的多样性会降低等问题。
目前已经提出很多种改进粒子群算法的方式,其中,遗传算法能够使用交叉算子加强粒子之间的信息交换,增加种群的多样性,对个体最优以及种群最优的情况进行调整,使算子不再局限于局部最优,从而获得全局最优。通过查阅相关文献,本文根据粒子群算法的基本理论,提出基于遗传算法思想的混合粒子群算法用以解决TSP问题[1],在控制一定实验时间的基础上进行实例分析,并使用蚁群算法多次实验对比验证。
一、基本粒子群优化算法
在TSP问题中,每个粒子都代表了遍历所有城市的方案,算法的目的是从中找出最符合实验要求的遍历路线。每个粒子都有自己的位置以及运动的速度,依靠速度可以调整粒子遍历城市的方案,最终将粒子的信息进行转化就能够得到最终遍历所有城市的方案。粒子群算法需要随机生成一定数量的粒子,通过不断的迭代最终的最优解。每一次的迭代过程中,粒子需要依靠个体遍历城市的最优值和整个粒子群体遍历城市得到的最优值来调整目前所在的位置。通过不断搜索逼近最优解,从而获得最终的解决方案。对应粒子的位置和速度计算公式[1]:
式中,表示在第t次迭代中第i个粒子在第d维上的速度,ω为惯性权重,是第i个粒子在d维上的个体极值,是全局极值,c1、c2是调节调节个体极值与全局极值相对重要程度的正常数,r1、r2是rand()随机生成的在区间[0,1]上的随机数。
速度调整公式的第一项是依据自身的速度通过ω的值来调整对下一刻的影响沉程度,第二项是利用粒子自身的历史信息来改变粒子的运动方向和速度,第三项是学习相领粒子的信息,不断向最优粒子靠近的过程。PSO算法的基本思想就是利用个体与群体的信息不断进行学习和调整,而其中的参数ω、c1、c2、r1、r2增强了算法的灵活性,可以调整参数使算法更适用于不同问题求得最优解的过程。
二、混合粒子群优化算法
标准粒子群算法在极值寻优的过程中,根据粒子的变化状况,除了自身的属性之外只能这个群体中粒子的属性,实验发现随着迭代次数的增加,粒子之间越来越相似,导致无法跳出局部解。而混合粒子群算法在保留粒子群算法原本的性质之外,通过引入遗传算法中的交叉、变异的方式[2],粒子与个体极值与群体极值交叉以及自身的变异来对粒子种群的多样性问题进行改进,直接对粒子携带遍历城市的信息进行交叉、变异处理,从而直接改变粒子原本想要表达的遍历方案,从而搜索最优解。
2.1个体编码
粒子个体编码采用整数编码的方式,将粒子的呈现形式转化为在TSP问题中的遍历路径,根据整数的数字来对应每一个城市,编码的位置则代表整个遍历方案的实际内容,每个粒子能够表达出遍历的方式,通过粒子的编码直接解读出遍历所有城市的方案[3]。
2.2交叉操作
个体通过和个体极值和群体极值交叉来更新,交叉方法采用整数交叉法[3]。既能够一定程度上保证粒子的独立性质,又能够保证粒子所反映出的方案是可行的。若交叉后存在位置重复的情况,使用个体中未包括的城市编号去代替原本重复出现的城市。
2.3变异操作
变异方法采用个体内部两位互换方法,通过变异的形式去实现更多不同的遍历方式,从而增加遍历方式的多样性。当变异后的粒子适应度优于原来的粒子则完成更新过程,否则保持原来的粒子状态。
三、仿真结果
将搜集的31个城市的数据作为本文TSP问题的实验数据,分别使用混合粒子群算法和蚁群算法进行优化计算[4]。在考虑到时间和结果的最优性,对进行初步的参数调试之后,设定粒子群算法最大迭代次数Nmax=200,粒子数m=1000;设定蚁群算法最大迭代次数Nmax=200,蚂蚁数量m=100,信息素浓度因子α=1,期望启发因子β=5,信息素挥发系数ρ=0.1,信息素强度Q=100。
为了保证算法的有效性,分别使用两种算法对研究数据分别测试30次。并针对实验结果适当调整参数来寻找算法对待此类问题的一般规律。
表1两种算法测试结果
根据实验结果,根据寻找出路径的长度来看,能够发现使用混合粒子群算法求解的结果整体优于蚁群算法,在调整参数的过程中,发现蚁群算法中蚂蚁数量的增加会明显增加计算的时间,而混合粒子群算法粒子数量的增加并不会给计算机带来过大的负担,整体多次实验中收敛时间以及实验结果也能够验证出其优越性。
比较混合粒子群算法不同进化次数下的最优解以及收敛速度,发现该算法基本在140代以后才能完成收敛,并且随着进化次数增加,能够得到更加理想的最优解。对于收敛速度,在测试中发现蚁群算法的收敛大致在90代,比混合粒子群算法的收敛速度快,但迭代次数的增加并不会明显改变路径的最优值。比较CPU占用时间,蚁群算法平均占用90.0s,混合粒子群算法平均占用103.1s,可以看出混合粒子群算法的CPU占用时间略长[5]。
四、结语
本文对提出基于遗传算法思想的混合粒子群算法进行实例分析,应用于一般的TSP问题,并与蚁群算法的实验进行对比。仿真结果表明,混合粒子群算法在实际应用中能够得到更好的优化结果,在增加问题的复杂度之后,一般的蚁群算法会大大增加计算时间,而混合粒子群算法则能够较好地解决这一问题,实现了算法改进的预期效果。
图1两种算法最优路径图
参考文献：
[1]李俊纬.物流配送TSP问题的研究[D].哈尔滨工业大学,2017.
[2]段佳炜.混合粒子群算法在云计算任务调度中的应用研究[D].大连交通大学,2017.
[3]朱莹莹,王宇嘉.求解复杂旅行商问题的混合粒子群算法[J].轻工机械,2015,33(03):42-45+49.
[4]张超.粒子群算法与蚁群算法的改进研究[D].西安工程大学,2019.
[5]侯颖,何建军,米阁,谢日华,何汶俊.基于混合粒子群算法求解TSP问题[J].电子测试,2016(16):49+34.
王玮,吴天红,姜英姿,史平.混合粒子群算法在TSP问题中的研究[J].中国新通信,2020,22(09):126-127.
分享：
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
人气：3212
人气：2788
人气：2629
人气：2543
人气：1559
我要评论
期刊名称：运筹与管理
期刊人气：3023
主管单位：中国科学技术协会
主办单位：中国运筹学会
出版地方：安徽
专业分类：科学
国际刊号：1007-3221
国内刊号：34-1133/G3
邮发代号：16-191
创刊时间：1992年
发行周期：月刊
期刊开本：大16开
见刊时间：一年半以上
影响因子：0.553
影响因子：0.322
影响因子：0.352
影响因子：0.000
影响因子：0.000
科普杂志阅读、期刊信息查询、论文下载、文献查询、原创文章检测等多项服务。
服务热线
您的论文已提交，我们会尽快联系您，请耐心等待！
你的密码已发送到您的邮箱，请查看！
2020-07-08
252
上传者：管理员
