基于自适应层次谱聚类与遗传优化的TSP算法
发布时间：2021-11-20 13:28
提出一种基于自适应层次谱聚类与遗传优化的算法求解大规模TSP,算法首先构建一种自适应相似矩阵,并应用到谱聚类算法中实现城市的初步聚类,当聚类城市规模超过设定阈值,用上述自适应谱聚类算法进行层次聚类,直到每类城市规模均小于阈值;其次,采用结合了最近邻与禁忌思想的改进遗传算法求解GTSP,得类间最短回路;最后,用改进遗传算法求解每类城市群的最优解,综合类间GTSP最短回路以及类内TSP最优解,即得大规模旅行商问题的最优解.实验结果表明,该算法能够取得相对较优解且求解效率显著提高.
【文章来源】：云南师范大学学报(自然科学版). 2020,40(01)
【文章页数】：8 页
【部分图文】：
改进遗传算法流程图
设该GTSP模型集合为G=V(,E），其中V=1{，2，…，s}，1～s表示类标号；E为类间连线的集合，边i(,j）的权值为Dij,i,j∈V，在该问题中，Dij取（5）式定义的距离函数；类间路径的优化是寻找G的最短巡回路线，该巡回路线是类间连线最短回路，且最终在每个类中均可找到两个类边界点．经过图V集中每个类顶点恰好两次（每类有两个边界点），即寻找经过V集的不同类边界点连线的最短巡回线路，图2为类边界点连线示意图．则类间最短路径总长度
为了验证提出的基于自适应层次谱聚类与遗传优化的算法的性能，在仿真环境Intel(R)Core(TM).i5-2450M CPU、4.00GB RAM、Window7(32bit）、MATLAB r2013a下，采用本文算法和传统遗传优化算法，选用TSP标准测试库TSPLIB[15]中的问题进行数值实验．在实验中，两算法参数设置相同，设置如下：种群大小Numpop=120、交叉概率crate=0.9、变异概率mrate=0.2、选择率srate=0.3、随机概率rrate=0.3和城市规模阈值thvalue=200，且设定类内进化代数、类间进化代数以及遗传算法进化代数均为Iteration=300．表1为9个不同TSP实例的遗传算法和本文算法实验数据，9个TSP实例数据规模分别为150、198、280、417、535、783、1 000、1 379和5 915，数据整体呈递增趋势．由表1可以看出本文算法的最优解均优于遗传算法最优解，运行时长更短，且遗传算法结果误差在10%～22%之间，本文算法结果误差在3%～11%之间．图3直观地展示了两算法在相同参数时，9个不同TSP实例的结果误差和运行时间的折线图．由图3(a）知，本文算法的结果误差总体小于遗传算法误差，且随着数据规模的增大，本文算法的结果优势更明显；由图3(b）知，本文算法的运行时间均小于遗传算法运行时间，当数据规模增大时，两算法运行时间整体呈上升趋势，且本文算法在TSP数据规模增大时，用时优势更加明显．由此可见，本文算法针对大规模TSP，有效避免收敛速度慢以及早熟现象，较大程度减少了运算时间，提高了计算效率．6 总结
【参考文献】：
期刊论文
[1]一种基于自适应相似矩阵的谱聚类算法[J]. 王贝贝,杨明,燕慧超,孙笑仙. 河北工业科技. 2018(02)
[2]基于改进遗传算法的孔群数控加工路径优化[J]. 龚玉玲,武美萍,徐晓栋,龚非. 组合机床与自动化加工技术. 2017(11)
[3]蚁群算法优化和路径规划问题的应用研究[J]. 潘晓萌,李冰. 科技通报. 2016(06)
[4]基于遗传蚁群混合算法的孔群加工路径优化[J]. 王春香,郭晓妮. 机床与液压. 2011(21)
[5]基于免疫记忆的人工免疫算法模型及其应用[J]. 王磊,肖人彬. 模式识别与人工智能. 2002(04)
硕士论文
[1]旅行商问题的两种智能算法[D]. 文永军.西安电子科技大学 2010
本文编号：3507421
【文章来源】：云南师范大学学报(自然科学版). 2020,40(01)
【文章页数】：8 页
【部分图文】：
改进遗传算法流程图
设该GTSP模型集合为G=V(,E），其中V=1{，2，…，s}，1～s表示类标号；E为类间连线的集合，边i(,j）的权值为Dij,i,j∈V，在该问题中，Dij取（5）式定义的距离函数；类间路径的优化是寻找G的最短巡回路线，该巡回路线是类间连线最短回路，且最终在每个类中均可找到两个类边界点．经过图V集中每个类顶点恰好两次（每类有两个边界点），即寻找经过V集的不同类边界点连线的最短巡回线路，图2为类边界点连线示意图．则类间最短路径总长度
为了验证提出的基于自适应层次谱聚类与遗传优化的算法的性能，在仿真环境Intel(R)Core(TM).i5-2450M CPU、4.00GB RAM、Window7(32bit）、MATLAB r2013a下，采用本文算法和传统遗传优化算法，选用TSP标准测试库TSPLIB[15]中的问题进行数值实验．在实验中，两算法参数设置相同，设置如下：种群大小Numpop=120、交叉概率crate=0.9、变异概率mrate=0.2、选择率srate=0.3、随机概率rrate=0.3和城市规模阈值thvalue=200，且设定类内进化代数、类间进化代数以及遗传算法进化代数均为Iteration=300．表1为9个不同TSP实例的遗传算法和本文算法实验数据，9个TSP实例数据规模分别为150、198、280、417、535、783、1 000、1 379和5 915，数据整体呈递增趋势．由表1可以看出本文算法的最优解均优于遗传算法最优解，运行时长更短，且遗传算法结果误差在10%～22%之间，本文算法结果误差在3%～11%之间．图3直观地展示了两算法在相同参数时，9个不同TSP实例的结果误差和运行时间的折线图．由图3(a）知，本文算法的结果误差总体小于遗传算法误差，且随着数据规模的增大，本文算法的结果优势更明显；由图3(b）知，本文算法的运行时间均小于遗传算法运行时间，当数据规模增大时，两算法运行时间整体呈上升趋势，且本文算法在TSP数据规模增大时，用时优势更加明显．由此可见，本文算法针对大规模TSP，有效避免收敛速度慢以及早熟现象，较大程度减少了运算时间，提高了计算效率．6 总结
【参考文献】：
期刊论文
[1]一种基于自适应相似矩阵的谱聚类算法[J]. 王贝贝,杨明,燕慧超,孙笑仙. 河北工业科技. 2018(02)
[2]基于改进遗传算法的孔群数控加工路径优化[J]. 龚玉玲,武美萍,徐晓栋,龚非. 组合机床与自动化加工技术. 2017(11)
[3]蚁群算法优化和路径规划问题的应用研究[J]. 潘晓萌,李冰. 科技通报. 2016(06)
[4]基于遗传蚁群混合算法的孔群加工路径优化[J]. 王春香,郭晓妮. 机床与液压. 2011(21)
[5]基于免疫记忆的人工免疫算法模型及其应用[J]. 王磊,肖人彬. 模式识别与人工智能. 2002(04)
硕士论文
[1]旅行商问题的两种智能算法[D]. 文永军.西安电子科技大学 2010
本文编号：3507421
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3507421.html
