一种混合改进遗传算法的嵌套分区算法

doi:10.3969/j.issn.1006-2475.2014.07.002

计算机与现代化 ›› 2014, Vol. 0 ›› Issue (7): 8-15.doi: 10.3969/j.issn.1006-2475.2014.07.002

一种混合改进遗传算法的嵌套分区算法

(1.常熟理工学院计算机科学与工程学院，江苏常熟 215500; 2.江苏科技大学数理学院，江苏镇江 212003; 3.南京理工大学泰州科技学院计算机科学与技术系，江苏泰州 225300)

收稿日期:2014-05-20 出版日期:2014-07-16 发布日期:2014-07-17
作者简介:宗德才(1979-),男,江苏常熟人,常熟理工学院计算机科学与工程学院讲师,硕士,研究方向：智能优化算法，概率论和信息论; 王康康(1980-),男,江苏科技大学数理学院副教授,博士,研究方向：智能优化算法，概率论和信息论; 丁勇(1980-),男,南京理工大学泰州科技学院计算机科学与技术系讲师,研究方向：数据库理论与数据挖掘。
基金资助:
江苏省高校自然科学基础研究项目（13KJB110006）

Combined Nested Partitions Method Based on Improved Genetic Algorithm

(1. College of Computer Science and Engineering, Changshu Institute of Technology, Changshu 215500, China;
2. School of Mathematics and Physics, Jiangsu University of Science and Technology, Zhenjiang 212003, China;
3. Taizhou Institute of Technology, Nanjing University of Science and Technology, Taizhou 225300, China)

Received:2014-05-20 Online:2014-07-16 Published:2014-07-17

摘要/Abstract

摘要： 提出一种混合改进遗传算法的嵌套分区算法用于求解旅行商问题。该算法首先使用加权抽样法产生初始最可能域，用全局数组保存每个区域的历史最优解，设计子域交叉算子和子域变异算子，并用改进的遗传算法搜索每个子域和裙域的最好解，然后对Lin-Kernighan算法进行改进，并且在搜索裙域中最好解时，对种群中优秀个体用改进的Lin-Kernighan算法进行优化。对TSPLIB中问题实例的仿真结果表明，所提出的混合改进遗传算法的嵌套分区算法在求解旅行商问题时可以获得高质量的解。

关键词: 旅行商问题, 遗传算法, 子域交叉, 子域变异 , Lin-Kernighan算法

Abstract: This paper puts forward an improved nested partitions method using improved genetic algorithm to solve the small and medium scale traveling salesman problem. The algorithm adopts weighted sampling method to generate the initial most promising region, uses the global array to record the historical optimal solution of every region and designs the crossover operator and mutation operator of subregion. Then our algorithm uses an improved genetic algorithm to search the optimal solution of each subregion and surrounding region. In the search for the best solution of surrounding region, some excellent individual is improved by modified Lin-Kernighan algorithm. The simulation results for the 16 problems in TSPLIB show that the proposed improved nested partitions method using improved genetic algorithm can find solutions of high quality when applied to the traveling salesman problem.

Key words: traveling salesman problem, genetic algorithm, subregion crossover, subregion mutation, Lin-Kernighan algorithm

中图分类号:

TP301.6

宗德才1，王康康2，丁勇3. 一种混合改进遗传算法的嵌套分区算法[J]. 计算机与现代化, 2014, 0(7): 8-15.

ZONG De-cai1, WANG Kang-kang2, DING Yong3 . Combined Nested Partitions Method Based on Improved Genetic Algorithm[J]. Computer and Modernization, 2014, 0(7): 8-15.

参考文献

[1] 张家善,王志宏,陈应显,等. 一种求解旅行商问题的改进遗传算法[J]. 计算机系统应用, 2012,21(9):192-194.

[2] Shi Leyuan, Olafsson S. An integrated framework for deterministic and stochastic optimization[C]// Proceedings of the 1997 Winter Simulation Conference. 1997:358-365.

[3] Xia Li, Yin Wenjun, Dong Jin, et al. A hybrid nested partitions algorithm for banking facility location problems[J]. IEEE Transactions on Automation Science and Engineering, 2010,7(3):654-658.

[4] Yau Hoksung, Shi Leyuan. Nested partitions for the large-scale extended job shop scheduling problem[J]. Annals of Operations Research, 2009,168(1):23-39.

[5] Zhou Wei, Zheng Jianrong, Wang Junfeng. Nested partitions method for assembly sequences merging[J]. Expert Systems with Applications, 2011,38(8):9918-9923.

[6] 刘昌军,苏琴,卫军胡,等. 嵌套分割算法在旅行商问题上的应用[J]. 系统仿真学报, 2008,20(24):6858-6861.

[7] 武维,管晓宏,卫军胡. Flow shop问题的嵌套分区优化调度方法[J]. 控制理论与应用, 2009,26(3):233-237.

[8] 武维,卫军胡,管晓宏. 一种求解QAP问题的混合嵌套分区优化算法[J]. 控制与决策, 2010,25(6):889-893.

[9] 宋建强,马良. 基于禁忌搜索的复合嵌套分割算法[J]. 计算机应用研究, 2011,28(4):1260-1262.

[10] 刘晓娟,邓子渊. 改进的嵌套分割算法及其在节能惰行中的应用[J]. 计算机工程与应用, 2013,49(10):239-242.

[11] 路晓伟,蒋馥. 基于模拟退火的复合嵌套分割算法[J]. 系统工程与电子技术, 2004,26(1):99-102.

[12] 宗德才,王康康. 改进的嵌套分区算法求解旅行商问题[J]. 计算机工程与应用, 2011,47(24):54-57.

[13] Lin Shen, Kernighan B W. An effective heuristic algorithm for the traveling salesman problem[J]. Operations Research, 1973,21(2):498-516.

[14] 田伟,田国会,张攀,等. 考虑非对称情形的一类拣选问题的改进LK算法求解[J]. 中国工程科学, 2004,6(11):47-52.

[15] 杨玉,李慧,戴红伟. 改进量子交叉遗传算法在TSP问题中的应用[J]. 南京师范大学学报(工程技术版), 2012,12(3):43-48.

[16] 申铉京,刘阳阳,黄永平等. 求解TSP问题的快速蚁群算法[J]. 吉林大学学报(工学版), 2013,43(1):147-151.,

[17] 柳寅,马良模糊人工蜂群算法的旅行商问题求解[J]. 计算机应用研究, 2013,30(9):2694-2696..

[18] 盛虹平,马良求解大规模旅行商问题的改进大洪水算法[J]. 小型微型计算机系统, 2012,33(2):259-262..

一种混合改进遗传算法的嵌套分区算法

Combined Nested Partitions Method Based on Improved Genetic Algorithm

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王佳1, 顾文俊1, 鞠炜刚2, 李玉维1, 张云龙2, 米传民3, 周志鹏3. 基于多元级差优良化遗传算法的环境拓扑结构任务调度[J]. 计算机与现代化, 2024, 0(10): 65-73.
[2]	王志强, 郑爽. 基于半监督学习的StyleGAN图像生成模型[J]. 计算机与现代化, 2024, 0(06): 14-18.
[3]	王东岳, 刘浩. 基于多智能体遗传算法的云平台抗虚假数据注入攻击方法 #br# #br#[J]. 计算机与现代化, 2024, 0(04): 21-26.
[4]	林启钊, 彭志平, 郭棉, 崔得龙. 基于双向多步预测的炉管温度场重构方法[J]. 计算机与现代化, 2024, 0(01): 53-58.
[5]	刘显茁, 邓韦斯, 谢恩彦. 考虑分布式发电并网的配电网自适应保护系统[J]. 计算机与现代化, 2023, 0(09): 120-126.
[6]	张志霞, 谢宝强. 基于FCGA-LSTM与迁移学习的天然气负荷预测[J]. 计算机与现代化, 2023, 0(07): 7-12.
[7]	汪敏, 徐英豪, 朱习军. 基于改进遗传算法优化BP神经网络的糖尿病并发症预测模型#br#[J]. 计算机与现代化, 2022, 0(11): 69-74.
[8]	王扬, 陈梅, 李晖. FOCoR:一种基于特征选择优化的课程推荐技术[J]. 计算机与现代化, 2022, 0(10): 1-7.
[9]	冉昊杰, 王宏智. 基于改进模拟退火算法的生鲜农产品配送中心选址[J]. 计算机与现代化, 2022, 0(10): 36-40.
[10]	战俊伟, 庄毅. 基于能耗与延迟优化的移动边缘计算任务卸载模型及算法[J]. 计算机与现代化, 2022, 0(08): 86-93.
[11]	吴代漾, 赵洁, 梁家铭, 董振宁, 梁周扬. C2C在线短租跨平台房东匹配算法[J]. 计算机与现代化, 2022, 0(06): 43-48.
[12]	徐胜超, 熊茂华. 基于遗传算法的容器云资源配置优化[J]. 计算机与现代化, 2022, 0(01): 108-112.
[13]	徐明, 张剑铭, 陈松航, 陈豪. 柔性作业车间调度问题的多目标优化算法[J]. 计算机与现代化, 2021, 0(12): 1-6.
[14]	张林鹏, 汪西原, 李强. 基于双池化特征加权结构CNN的图像分类[J]. 计算机与现代化, 2021, 0(11): 67-71.
[15]	陈春燕, 刘梦赤. 基于粒子群遗传算法的智能组卷策略[J]. 计算机与现代化, 2021, 0(08): 16-23.