基于文化混合优化算法的旅行商问题求解

计算机工程与科学

基于文化混合优化算法的旅行商问题求解

马晗，常安定，陈童，李江杰

（长安大学理学院，陕西西安 710064）

收稿日期:2018-06-11 修回日期:2018-10-17 出版日期:2019-07-25 发布日期:2019-07-25

A hybrid culture algorithm optimization strategy

for traveling salesman problem

MA Han，CHANG Anding，CHEN Tong，LI Jiangjie

(College of Mathematical and Physics,Chang’an University,Xi’an 710064,China)

Received:2018-06-11 Revised:2018-10-17 Online:2019-07-25 Published:2019-07-25

摘要/Abstract

摘要：

为更好地求解TSP问题，将遗传算法与模拟退火算法结合并纳入文化算法体系，提出一种求解旅行商问题的文化混合优化算法。该算法空间可分为独立并行的两部分：种群空间和信度空间。种群空间按照遗传退火混合算法实现进化，并将进化中的较优个体提供给信度空间，信度空间提取并利用较优个体所包含的信息来引导种群进化。通过求解TSP标准测试问题，将文化混合优化算法所求得的最优路径与其他优化算法所求结果相比，算法偏差均可降低0.6%～13.01%，表明了文化混合优化算法求解TSP问题的有效性与优越性。

关键词: 旅行商问题, 遗传算法, 模拟退火算法, Metropolis准则, 文化算法

Abstract:

Combining the genetic algorithm and simulated annealing algorithm with the culture algorithm, we design a hybrid culture optimization algorithm to solve the traveling salesman problem (TSP). The strategy contains two parts: the population space and the reliability space. The population space evolves according to the hybrid genetic annealing algorithm and sends optimal individuals to the reliability space. The reliability space extracts the information contained by the optimal individuals to guide population evolution. Experiments on TSP benchmark show that compared with other optimization algorithms, the hybrid cultural optimization strategy can reduce the deviation rate of the result to be 0.6% to 13.01% when obtaining the optimal path. Experiments verify the effectiveness and superiority of the hybrid cultural optimization strategy for solving the TSP.

Key words: traveling salesman problem, genetic algorithm, simulated annealing algorithm, Metropolis criterion, cultural algorithm

马晗，常安定，陈童，李江杰. 基于文化混合优化算法的旅行商问题求解[J]. 计算机工程与科学.

MA Han，CHANG Anding，CHEN Tong，LI Jiangjie.

A hybrid culture algorithm optimization strategy

for traveling salesman problem

[J]. Computer Engineering & Science.

[1]	李成冉, 方佳豪, 尹首一, 魏少军, 胡杨. 基于遗传算法的晶圆级芯片映射算法研究[J]. 计算机工程与科学, 2024, 46(06): 993-1000.
[2]	任晟岐, 宋伟. 基于GGInformer模型的多维时间序列特征提取与预测研究[J]. 计算机工程与科学, 2024, 46(04): 590-598.
[3]	孙睿男, 初翔, 陈昱, 闫明宁. 基于混合启发式算法的快递末端选址路径优化研究[J]. 计算机工程与科学, 2024, 46(01): 159-169.
[4]	郭艺, 何廷年, 李爱斌, 毛君宇. 融合GA-CART和Deep-IRT的知识追踪模型[J]. 计算机工程与科学, 2023, 45(09): 1691-1700.
[5]	申晓宁, 潘红丽, 陈庆洲, 游璇, 黄遥. 引入启发信息的粒子群算法在低碳TSP中的应用[J]. 计算机工程与科学, 2022, 44(06): 1114-1125.
[6]	赵炳巍, 贾峰, 曹岩, 孙瑜, 刘一鸿. 基于模拟退火算法的人工势场法路径规划研究[J]. 计算机工程与科学, 2022, 44(04): 746-752.
[7]	毛媛媛, 石恩雅, 蒋从锋, 仇烨亮, 贾刚勇, 万健, 闫龙川. 基于遗传算法的数据中心能效仿真[J]. 计算机工程与科学, 2021, 43(08): 1341-1352.
[8]	胡新荣, 刘嘉文, 刘军平, 彭涛, 何儒汉, . 基于改进GA-BP-MC神经网络的人体三维尺寸预测[J]. 计算机工程与科学, 2021, 43(08): 1443-1453.
[9]	李静, 莫思敏 . 基于改进遗传算法的深度神经网络优化研究[J]. 计算机工程与科学, 2021, 43(08): 1503-1511.
[10]	袁也, 王刚, 刘晓光, 李雨森. 新型电路版图布局布线算法设计[J]. 计算机工程与科学, 2021, 43(07): 1185-1191.
[11]	李晶晶, 许少华. 基于组合核函数的径向基过程神经网络及其在示功图诊断中的应用[J]. 计算机工程与科学, 2021, 43(04): 746-752.
[12]	季子豪, 江凌云. 一种基于遗传算法的多站点协同计算卸载算法[J]. 计算机工程与科学, 2021, 43(03): 426-434.
[13]	贾俊杰, 秦海涛. 基于遗传算法的动态轨迹匿名算法[J]. 计算机工程与科学, 2021, 43(01): 142-150.
[14]	李丹莲, 曹倩, 徐菲. 基于改进遗传算法的连锁便利店配送路径优化[J]. 计算机工程与科学, 2020, 42(11): 2096-2102.
[15]	陈旺虎，田真，张礼智，梁小燕，高雅琼. 基于插值的高维稀疏数据离群点检测方法[J]. 计算机工程与科学, 2020, 42(06): 966-972.