[1]杨玉,李慧,戴红伟,等.改进量子交叉遗传算法在TSP问题中的应用[J].南京师范大学学报(工程技术版),2012,12(03):043-48.
　Yang Yu,Li Hui,Dai Hongwei.Improved Quantum Crossover Based GA and Its Application to Traveling Salesman Problem[J].Journal of Nanjing Normal University(Engineering and Technology),2012,12(03):043-48.
点击复制

改进量子交叉遗传算法在TSP问题中的应用
分享到：

南京师范大学学报（工程技术版）[ISSN:1006-6977/CN:61-1281/TN]

卷:
12卷
期数:
2012年03期
页码:
043-48
栏目:
出版日期:
2012-09-20

文章信息/Info

Title:
Improved Quantum Crossover Based GA and Its Application to Traveling Salesman Problem
作者:
杨玉;李慧;戴红伟;
淮海工学院计算机工程学院，江苏连云港222005
Author(s):
Yang Yu; Li Hui; Dai Hongwei
School of Computer Engineering,Huaihai Institute of Technology,Lianyungang 222005,China
关键词:
旅行商问题; 遗传算法; 改进量子交叉; 优化问题
Keywords:
traveling salesman problem( TSP) ; genetic algorithm ( GA) ; improved quantum crossover; optimization problem
分类号:
TP18
摘要:
为提高遗传算法求解旅行商问题的效率,提出了一种改进量子交叉算子遗传算法.与经典量子全干扰交叉算子中城市的选择完全依赖于其位置的选择策略相比,新算子在选择城市时加入了父代优质解的有用信息,从而在维持解的多样性的同时,提高交叉所产生新解的质量.仿真算例结果表明,改进交叉算子遗传算法有着良好的全局搜索和局部挖掘能力,针对TSP问题的最优解、平均解均优于传统算法.
Abstract:
In order to improve the efficiency of Genetic Algorithm ( GA) to Traveling Salesman Problem ( TSP) ，an improved quantum crossover is proposed in this paper． Compared with the traditional quantum crossover in which a city is selected according to the position，the new crossover selects a city depending on the distance comparing． The new crossover can maintain the diversity of population and generate higher quality solutions． Simulation result shows that the improved quantum crossover based GA has good ability in global exploration and local exploitation． The best solution and the average solutions on TSP are all superior to those of traditional algorithm．

参考文献/References:

［1］李盼池，宋考平，杨二龙． 基于受控旋转门的量子神经网络模型算法及应用［J］． 控制与决策，2011，26( 6) : 898-901． Li Panchi，Song Kaoping，Yang Erlong． Controlled-rotating gate-based quantum neural networks model algorithm with application ［J］． Control and Decision，2011，26( 6) : 898-901． ( in Chinese)
［2］王凌，吴昊，唐芳，等． 混和量子遗传算法及其性能分析［J］． 控制与决策，2005，20( 2) : 156-160．Wang Ling，Wu Hao，Tang Fang，et al． Hybrid quantum genetic algorithms and performance analysis［J］． Control and Decision， 2005，20( 2) : 156-160． ( in Chinese)
［3］周明，孙树栋． 遗传算法原理及应用［M］． 北京: 国防工业出版社，1999． Zhou Ming，Sun Shudong． Genetic Algorithms: Theory and Applications［M］． Beijing: National Defence Industrial Press， 1999． ( in Chinese)
［4］封安辉，苏宏升． 一种改进的量子遗传算法及应用［J］． 计算机工程，2011，37( 5) : 199-201． Feng Anhui，Su Hongsheng． Improved quantum genetic algorithm and its application［J］． Computer Engineering，2011，37 ( 5) : 199-201． ( in Chinese)
［5］李英华，王宇平． 有效的混和量子遗传算法［J］． 系统工程理论与实践，2006，26( 11) : 116-124． Li Yinghua，Wan Yuping． An effective hybrid quantum genetic algorithm［J］． Systems Engineering-Theory and Practice， 2006，26( 11) : 116-124． ( in Chinese)
［6］Narayanan A，Moore M． Quantum-inspired genetic algorithms［C］/ /Proceeding of the IEEE International Conference Evolutionary Computation． Nagoya，1996: 61-66．
［7］李阳阳，焦李成． 量子克隆多播路由算法［J］． 软件学报，2007，18( 9) : 2 063-2 069． Li Yangyang，Jiao Licheng． Quantum clonal algorithm for multicast routing problem［J］． Journal of Software，2007，18( 9) : 2 063-2 069． ( in Chinese)
［8］董春龙，刘希玉． 基于遗传算法的家具造型创新设计［J］． 南京师范大学学报: 工程技术版，2010，10( 3) : 78-81． Dong Chunlong，Liu Xiyu． Creative design of furniture configuration based on genetic algorithm［J］． Journal of Nanjing Normal University: Engineering and Technology Edition，2010，10( 3) : 78-81． ( in Chinese) ［9］殷新春，杨洁． 基于遗传算法的S 盒的构造［J］． 计算机应用研究，2007，24( 3) : 91-93． Yin Xinchun，Yang Jie． Construction of S-boxes based on genetic algorithm［J］． Application Research of Computers，2007， 24( 3) : 91-93． ( in Chinese)
［10］雷秀娟，史忠科，王来军，等． 遗传算法多目标优化及其在决策支持系统中的应用［J］． 计算机应用研究，2006，23 ( 7) : 176-177． Lei Xiujuan，Shi Zhongke，Wang Laijun，et al． Multi-objective optimization of genetic algorithm and its application in DSS ［J］． Application Research of Computers，2006，23( 7) : 176-177． ( in Chinese)

相似文献/References:

[1]张金龙,赵芙生.基于遗传算法的三维重构图像阈值分割[J].南京师范大学学报(工程技术版),2005,05(01):005.
　ZHANG Jinlong,ZHAO Fusheng.Image Threshold Segmentation of 3D Reconstruction Based on Genetic Algorithm[J].Journal of Nanjing Normal University(Engineering and Technology),2005,05(03):005.
[2]刘清.多点正交交叉的遗传算法研究[J].南京师范大学学报(工程技术版),2005,05(02):042.
　LIU Qing.Research on Genetic Algorithm with Multi-Point Orthogonal Crossover Operation[J].Journal of Nanjing Normal University(Engineering and Technology),2005,05(03):042.
[3]李宇中,刘红星,张　胜.猴王遗传算法的改进[J].南京师范大学学报(工程技术版),2004,04(03):053.
　LI Yuzhong,LIU Hongxing,ZHANG Shen.Improving Monkey-King Genetic Algorithm[J].Journal of Nanjing Normal University(Engineering and Technology),2004,04(03):053.
[4]张广帅,张煜东,吉根林.蚁群算法求解TSP综述[J].南京师范大学学报(工程技术版),2014,14(04):039.
　Zhang Guangshuai,Zhang Yudong,Ji Genlin.Survey on Ant Colony Algorithm for the Traveling Salesman Problem[J].Journal of Nanjing Normal University(Engineering and Technology),2014,14(03):039.
[5]王　雷,蔡劲草,李　明.基于正交试验的遗传算法参数优化[J].南京师范大学学报(工程技术版),2016,16(02):081.[doi:10.3969/j.issn.1672-1292.2016.02.013]
　Wang Lei,Cai Jingcao,Li Ming.Parameter Optimization of Genetic AlgorithmBased on Orthogonal Experiment[J].Journal of Nanjing Normal University(Engineering and Technology),2016,16(03):081.[doi:10.3969/j.issn.1672-1292.2016.02.013]
[6]黄宏运,吴礼斌,李诗争.GA优化的SVM在量化择时中的应用[J].南京师范大学学报(工程技术版),2017,17(01):072.[doi:10.3969/j.issn.1672-1292.2017.01.011]
　Huang Hongyun,Wu Libin,Li Shizheng.Application of SVM Optimized by Genetic Algorithmin Quantization Timing Selection[J].Journal of Nanjing Normal University(Engineering and Technology),2017,17(03):072.[doi:10.3969/j.issn.1672-1292.2017.01.011]
[7]赵世田,付莹莹,曾 勇,等.基于非线性自适应度函数的遗传算法求取自由曲面最大主曲率研究[J].南京师范大学学报(工程技术版),2018,18(03):019.[doi:10.3969/j.issn.1672-1292.2018.03.003]
　Zhao Shitian,Fu Yingying,Zeng Yong,et al.Research in Calculation of Principal Curvature of Free-formSurface Based on Non-linear Automatic FitnessFunction of Genetic Algorithm[J].Journal of Nanjing Normal University(Engineering and Technology),2018,18(03):019.[doi:10.3969/j.issn.1672-1292.2018.03.003]
[8]陈 超,陈振中.基于遗传算法的综合布线路径布局研究[J].南京师范大学学报(工程技术版),2020,20(04):051.[doi:10.3969/j.issn.1672-1292.2020.04.008]
　Chen Chao,Chen Zhenzhong.Research on Route Planning of Generic CablingBased on Genetic Algorithm[J].Journal of Nanjing Normal University(Engineering and Technology),2020,20(03):051.[doi:10.3969/j.issn.1672-1292.2020.04.008]
[9]余凌浩,陆铁文,李 晨,等.基于子带谱熵法和PSO-GA-SVM的汽车鸣笛识别[J].南京师范大学学报(工程技术版),2021,21(02):027.[doi:10.3969/j.issn.1672-1292.2021.02.005]
　Yu Linghao,Lu Tiewen,Li Chen,et al.Car Whistle Recognition Based on Sub-Band SpectralEntropy Method and PSO-GA-SVM[J].Journal of Nanjing Normal University(Engineering and Technology),2021,21(03):027.[doi:10.3969/j.issn.1672-1292.2021.02.005]
[10]汤云峰,赵 静,谢 非,等.基于改进遗传算法的机器人路径规划方法[J].南京师范大学学报(工程技术版),2021,21(03):049.[doi:10.3969/j.issn.1672-1292.2021.03.007]
　Tang Yunfeng,Zhao Jing,Xie Fei,et al.Robot Path Planning Method Based on Improved Genetic Algorithm[J].Journal of Nanjing Normal University(Engineering and Technology),2021,21(03):049.[doi:10.3969/j.issn.1672-1292.2021.03.007]

备注/Memo

备注/Memo:
基金项目: 淮海工学院自然科学基金( Z2011033，Z2011139) ．通讯联系人: 杨玉，讲师，研究方向: 人工神经网络、软件外包． E-mail: yangyuyy@ hotmail． com
更新日期/Last Update: 2013-03-11