期刊文献+

改进的紧致遗传算法求解族状旅行商问题 被引量:2

An Improvement of the Compact Genetic Algorithm for Solving Clustering Traveling Salesman Problem
下载PDF
导出
摘要 相比经典的标准遗传算法求解旅行商问题,紧致遗传算法对存储的要求较少,但可行解的产生需要花费大量的时间.针对城市节点成族状分布的旅行商问题,在紧致遗传算法中设计"轮盘赌"的个体编码产生方式以避免时间耗费的缺点,并在基于节点聚类分析的基础上设计出符合问题特点的概率矩阵初始化方法和更新方法,以提高算法搜索最优解的准确性和搜索速度.最后通过对公开数据集TSPLib的测试证实设计的改进紧致遗传算法确实能提高问题求解的效率. Compared with classical genetic algorithm for solving traveling salesman problem(TSP), compact genetic algorithm (CGA) exploited without significantly increasing memory requirements, but the computational cost of generation of feasible Tours increased. Facing the characteristic of city nodes distributing as cluster in clustering TSP,the roulette wheel is applied in generating individuals chromosomes of CGA to overcome the drawbacks of expensive computation. Based on the cluster analysis of city nodes in clustering TSP, the initialization operator and update protocol of the probability matrix corresponding to the characteristic of clustering TSP is proposed to improve the speed of convergence efficiently and capacity of global optimization. The results of experiments conducted on TSP instances in open datasets TSPLib shows the efficacy of the improved compact genetic algorithm.
作者 叶苗 程小辉
出处 《微电子学与计算机》 CSCD 北大核心 2013年第8期7-12,共6页 Microelectronics & Computer
基金 国家自然科学基金(61063001/F020207 61262075/F020702) 广西自然科学基金项目(桂科自0832264) 广西高等学校重大科研项目(201201ZD012)
关键词 紧致遗传算法 概率模型 聚类分析 族状旅行商问题 compact genetic algorithm probability model cluster analysis clustering traveling salesman problem
  • 相关文献

参考文献8

  • 1Padberg M, Rinaldi G. Optimization of a 532 - citysymmetric genetic traveling salesman problem bybranch and cut[J]. Oper. Res. Lett ? 1987,6(1) : 1~7.
  • 2Lin S,Kemighan B W. An effective heuristic algorithmfor the traveling salesman problem [J], Oper. Res.,1973,21(2):498-516.
  • 3王建忠,唐红.TSP问题的一种快速求解算法[J].微电子学与计算机,2011,28(1):7-10. 被引量:11
  • 4Baraglia R, Hidalgo J I, Perego R. A hybrid heuristicfor the traveling salesman problem[J]. IEEE Trans-actions on Evolutionary Computation, 2001,5(6) :613-622.
  • 5Harik G,Goldberg D,Miller B. The gamblers ruinproblem, genetic algorithms, and the sizing of popu-lationsK[C]// Proceedings of the Fourth InternationalConference on Evolutionary Computation, 1997. Pis-cataway, NJ: IEEE Press, 1997:7-12.
  • 6王剑,赵永翔,熊盛武.多线程并行紧致遗传算法的种群多样性研究[J].武汉理工大学学报(信息与管理工程版),2009,31(2):204-207. 被引量:1
  • 7Thilagamani S,Shanthi N. A survey on image segmen-tation through clustering[J]. International Journal ofResearch and Reviews in Information Sciences,2011,1(1):14-17.
  • 8ReineltG. TSPLIB~A traveling salesman problem librar-y[J], ORSA J. Comput ,1991,3(4) : 376-384.

二级参考文献18

  • 1江雷.基于并行遗传算法的弹性TSP研究[J].微电子学与计算机,2005,22(8):130-133. 被引量:10
  • 2周涛.基于改进遗传算法的TSP问题研究[J].微电子学与计算机,2006,23(10):104-106. 被引量:19
  • 3GOLDBERG D E. Genetic algorithms in search, optimization, and machine learning [ M ]. MA : Addison - Wesley, 1989 : 18 - 59.
  • 4JIRI O. Parallel estimation of distribution algorithms [ M ]. [ s.l. ] : Faculty of Information Technology of Brno University of Technology,2002:39 - 102.
  • 5HARIK G, LOBO F, GOLDBERG D E. The compact genetic algorithm [ C ].//Proceedings of the 1998 IEEE Conference on Evolutionary Computation. [ s. l. ]:Is. n. ] ,1998:523 -528.
  • 6HARIK G. Linkage learning via probabilistic modeling in the ECGA[ R]. IlliGAL Reprot No. 99010,1999.
  • 7BONET DE J S, ISBELL C L, VIOLA P. MIMIC : finding optima by estimating probability densities [ J ]. Advances in Neural Information Processing Systems, 1997 (9) :424-428.
  • 8FERNANDO G L, CLUDIO F L. An architecture for massive parallelization of the compact genetic algorithm [ J ]. Computer Science,2004 ( 3103 ) :412 - 413.
  • 9KAMEL S M. New algorithms for solving the fuzzy c - means clustering problem [ J ]. Pattern Recognition, 1994 (27) :4-15.
  • 10LARRANAGA P, LOZANO J A. Estimation of distribution algorithms:a new tool for evolutionary computation [ M]. [ s. l. ] : Kluwer Academic Publishers,2002:18 - 128.

共引文献10

同被引文献23

  • 1刘新亮,张涛,郭波.基于分布估计算法的备件优化配置[J].系统工程理论与实践,2009,29(2):144-150. 被引量:9
  • 2轩华,唐立新.实时无等待HFS调度的一种拉格朗日松弛算法[J].控制与决策,2006,21(4):376-380. 被引量:25
  • 3周树德,孙增圻.分布估计算法综述[J].自动化学报,2007,33(2):113-124. 被引量:209
  • 4张文修 梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社,2003..
  • 5Harik G R, Lobo F G, Goldberg D E. The compact genetic al- gorithm[ J ]. IEEE Transactions on Evolutionary Computation, 1999,3(4) :287-297.
  • 6Amr B, Ibtehal M, Basma M, et al. Solving protein folding problem using elitism-based compact genetic algorithm[ J]. Journal of Computer Science,2008,4 (7) :525-529.
  • 7Soheil R, Hadi A, Guy V. A simple real-coded compact genet- ic algorithm and its application to antenna optimization[ C ]// Proceedings of Asia-Pacific microwave conference. [ s. 1. ] : [ s. n. ] ,2007.
  • 8Droste S. A rigorous analysis of the compact genetic algorithm for linear functions [ J ]. Natural Computing, 2006,5 ( 3 ) : 257 - 283.
  • 9Seok J H, Lee J J. A novel compact genetic algorithm using offspring survival evolutionary strategy [ J ]. Artificial Life and Robotics, 2009,14 ( 4 ) :489-493.
  • 10Ahn C, Ramakrishna R. Elitism-based compact genetic algo- rithms[ J]. IEEE Transactions on Evolutionary Computation, 2003,7(4) :367-385.

引证文献2

二级引证文献4

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部