向量编码遗传算法求解TSP问题的研究
|
摘要
本文首先对遗传算法的原理、技术、理论做了介绍,然后描述了TSP问题,并给出其数学模型.在提出改进的遗传算法之前,先对求解TSP问题常用的遗传算法技术进行介绍,充分分析了矩阵编码的缺点之后,提出了一种新的编码技术——向量编码,并利用基于向量编码的遗传算法求解了TSP问题。作者编写了基于向量编码遗传算法的Matlab程序,试验表明,向量编码遗传算法对求解TSP问题效果较为理想。
在改进的遗传算法编码方案中,提出了Hamilton矩阵的概念;根据向量编码的形式,提出一种比较好的不可行解修正技术,这种技术的优点是尽最大程度不破坏染色体的结构,尽力保持父代和子代个体相似度,以便染色体结构遗传到下一代,使得优良模式生存下去;为了使读者能够更加深刻地理解本文提出向量编码方案的动机,也为了让读者不至于混淆向量编码和矩阵编码,在提出向量编码遗传算法和相关的技术之后,将向量编码遗传算法和矩阵编码遗传算法在理论上作了比较,并对矩阵编码遗传算法的缺点和向量编码的优点进行了分析。
最后,本文采用改进的遗传算法对TSP问题的求解过程进行了算法设计和实现,通过试验,得出了一个较理想的结果,验证了本文提出的遗传编码方案的正确性和可行性。
The principle and the technology and the theory of genetic algorithm were firstly introduced in this paper, then the travel salesman problem was depicted and its mathematical model was presented. Popular and general algorithm technology was introduced before the improved algorithm was putted, after completely analyzing the disadvantage of the matrix coding, I putted a new coding technique named vector coding, and the algorithm technology based on the vector coding was used for the solution of the TSP. The author presented the MATLAB program based vector coding algorithm for the solution of TSP, the experimentation indicated that the vector coding genetic algorithm take good effect in the solution of the TSP.
Hamilton matrix was produced as a new concept in the vector coding technique, according to the vector coding form, a better illegal revising technique was putted forward. The excellence of the technique is to make great efforts not to destroy chromosome’s structure and maintain the similarity of parents and children, which makes chromosome’s structure get inherited in next generation, so the excellent model will be survived. For the sake of the reader being able to understand the motion and the aim of the vector coding technique putted in this paper profoundly, and not making reader confused about vector coding and matrix coding, after putting forward the vector coding genetic algorithm and related technique, the paper narrates the comparison of the vector coding genetic algorithm and the matrix coding genetic algorithm on theory and their essence difference and the analysis on the advantage of the matrix coding technique and the disadvantage of the vector coding technique for the TSP solution.
At last, I used the improved genetic algorithm according to the resolving process of the TSP to design and implement, by experiment I gained a perfect result, which verified the correctness and feasibility of the genetic coding project putted in the paper.
在改进的遗传算法编码方案中,提出了Hamilton矩阵的概念;根据向量编码的形式,提出一种比较好的不可行解修正技术,这种技术的优点是尽最大程度不破坏染色体的结构,尽力保持父代和子代个体相似度,以便染色体结构遗传到下一代,使得优良模式生存下去;为了使读者能够更加深刻地理解本文提出向量编码方案的动机,也为了让读者不至于混淆向量编码和矩阵编码,在提出向量编码遗传算法和相关的技术之后,将向量编码遗传算法和矩阵编码遗传算法在理论上作了比较,并对矩阵编码遗传算法的缺点和向量编码的优点进行了分析。
最后,本文采用改进的遗传算法对TSP问题的求解过程进行了算法设计和实现,通过试验,得出了一个较理想的结果,验证了本文提出的遗传编码方案的正确性和可行性。
The principle and the technology and the theory of genetic algorithm were firstly introduced in this paper, then the travel salesman problem was depicted and its mathematical model was presented. Popular and general algorithm technology was introduced before the improved algorithm was putted, after completely analyzing the disadvantage of the matrix coding, I putted a new coding technique named vector coding, and the algorithm technology based on the vector coding was used for the solution of the TSP. The author presented the MATLAB program based vector coding algorithm for the solution of TSP, the experimentation indicated that the vector coding genetic algorithm take good effect in the solution of the TSP.
Hamilton matrix was produced as a new concept in the vector coding technique, according to the vector coding form, a better illegal revising technique was putted forward. The excellence of the technique is to make great efforts not to destroy chromosome’s structure and maintain the similarity of parents and children, which makes chromosome’s structure get inherited in next generation, so the excellent model will be survived. For the sake of the reader being able to understand the motion and the aim of the vector coding technique putted in this paper profoundly, and not making reader confused about vector coding and matrix coding, after putting forward the vector coding genetic algorithm and related technique, the paper narrates the comparison of the vector coding genetic algorithm and the matrix coding genetic algorithm on theory and their essence difference and the analysis on the advantage of the matrix coding technique and the disadvantage of the vector coding technique for the TSP solution.
At last, I used the improved genetic algorithm according to the resolving process of the TSP to design and implement, by experiment I gained a perfect result, which verified the correctness and feasibility of the genetic coding project putted in the paper.
引文
[1]王小平,曹立明.遗传算法理论、应用与软件实现.西安交通大学出版社,2002.1.
[2]陈国良.遗传算法及其应用.人民邮电出版社,1999
[3]周明.遗传算法原理及应用.国防工业出版社,2000
[4]朱成娟.遗传算法的改进及其若干应用.中国期刊网优秀硕博论文,2004.5
[5] Andrew Chipperfield Peter Fleming HartmutPohlheim Carlos Fonseca. Genetic Algorithm Toolbox Users Guide. 2004.3
[6]李玮,关于旅行商问题的改进遗传算法.中国期刊网优秀硕博论文,2004.5
[7] Holland,J.H.,Genetic algorithms,Scientific American,4(1992)
[8]周明,孙树栋.遗传算法原理与应用.国际工业出版社.2001
[9]雷英杰,张善文,李续武.MATLAB遗传算法工具箱及应用.西安电子科技大学出版社,2005.4.
[10]陈国良,王煦法,庄镇泉等.遗传算法及其应用.人民邮电出版社,1996 4
[11] Joachim S.Parallel Genetic Algorithms:Theory and Applications,ISO Press,1993
[12]Tam,K,Y.,Genetic algorithms,function optimization,and facility layout design,European Journal of Operational Research,63(1994).
[13]邢文训,谢金星.现代优化计算方法.清华大学出版社,1998.
[14]李敏强.遗传算法基本理论及应用.科学出版社,2002.
[15]陆金贵.遗传算法原理与工程应用.科学出版社1997.
[16]玄光男,程润伟.遗传算法与工程优化.清华大学出版社,2004.1
[17]徐宗本,计算智能—模拟进化计算.高等教育出版社,2004..2
[18]汪近能,陈丽燕,吴新余.遗传算法的改进及应用.南京邮电学院学报.1997,(12):165—169
[19]林焰,郝聚民,纪卓尚.隔离小生境遗传算法研究.系统工程学报,2000.15(1)86—92
[20]戴晓明,许超,龚向阳,邵惠鹤.并行遗传算法收敛性分析及优化运算.计算机工程,2002 Vol.18 No.1.
[21]胡能发,康立山,陈毓屏.构建“基因库”求解TSP问题的混合遗传算法.计算机工程与应用,2003.11.
[22]马良.TSP及其扩展问题的混合型启发式算法.上海理工大学学报,Vol.21,No.1,1999.
[23]孙建永,申建中等.一类自适应遗传算法.西安交通大学学报.2000.(10):84—89
[24]吴志远等.一种新的自适应遗传算法及其在多峰值函数优化中的应用[J].控制理论和应用,1999:16(1):127—129
[25]张文修,梁怡.遗传算法的数学基础.西安:西安交通大学出版社,2000.5
[26]潘正君,康立山,陈毓屏.演化计算,清华大学出版社,广西科学技术出版社,1998.
[27] Oliver L.M.A study of permucation Crossover Operators on Traveling Salesman Problem.Lawrence Erlbaum Aasociates,1987,224-230
[28]马欣等.旅行商问题的一种改进遗传算法.计算机仿真,2003,20(:4)36-37
[29]谢胜利,张燕姑,李广.基于遗传算法的旅游推销商问题求解.温州师范学院学报,Vol.23.No.3,June 2002.
[30]王树禾.图论及其算法.中国科学技术大学出版社,1990
[31]马良.最小Hami1ton路问题的算法.计算机工程与应用,1992.
[32]陈志平,徐宗本.计算机数学—计算复杂性理论与NPC,NP难问题的求解.科学出版.2001.8.
[33]陈斌,徐华中.一种改进遗传算法及其在TSP问题中的应用.人工智能及识别技术,Vol.28.No.9,September 2002.
[34]黄厚生.求解旅行商问题的新方法研究.中国期刊网优秀硕博论文,2005.5
[35]马欣等.旅行商问题的一种改进遗传算法.计算机仿真,2003,20(:4)36-37
[36] David A,Robert B,William C. On the Solution of Traveling Salesman problems[R].USA: Rice University,1998.
[37]唐立新.旅行商问题(TSP)的改进遗传算法.东北大学学报,1999,120(1):40
[38]刘海,林智勇,郝志峰.改进遗传交叉算子求解TSP问题.华南理工大学学报(自然科学版),2002 Vol.30 No.12
[39]张良杰,毛志宏,李衍达.遗传算法中突变算子的数学分析及改进策略.电子科学学刊,1996,(6):590~595
[40]王凌,郑大钟.TSP问题次优化求解方法的比较〔J〕.控制与决策,1998,13(1)79一82.
[41]刘琼芳.基于矩阵编码的遗传算法与TSP求解.中国期刊网优秀硕博论文,2001.
[42]宋兆基,徐流美.MATLAB6.5在科学计算中的应用.北京:清华大学出版社,2005
[43]张瑞喜,姚予疆.MATLAB6.O科学运算完整解决方案.北京:人民邮电出版社,2001
[44]马均水等.改进遗传算法搜索性能的大变异操作.控制理论和应用. 1998:15(:3) 404~407
[2]陈国良.遗传算法及其应用.人民邮电出版社,1999
[3]周明.遗传算法原理及应用.国防工业出版社,2000
[4]朱成娟.遗传算法的改进及其若干应用.中国期刊网优秀硕博论文,2004.5
[5] Andrew Chipperfield Peter Fleming HartmutPohlheim Carlos Fonseca. Genetic Algorithm Toolbox Users Guide. 2004.3
[6]李玮,关于旅行商问题的改进遗传算法.中国期刊网优秀硕博论文,2004.5
[7] Holland,J.H.,Genetic algorithms,Scientific American,4(1992)
[8]周明,孙树栋.遗传算法原理与应用.国际工业出版社.2001
[9]雷英杰,张善文,李续武.MATLAB遗传算法工具箱及应用.西安电子科技大学出版社,2005.4.
[10]陈国良,王煦法,庄镇泉等.遗传算法及其应用.人民邮电出版社,1996 4
[11] Joachim S.Parallel Genetic Algorithms:Theory and Applications,ISO Press,1993
[12]Tam,K,Y.,Genetic algorithms,function optimization,and facility layout design,European Journal of Operational Research,63(1994).
[13]邢文训,谢金星.现代优化计算方法.清华大学出版社,1998.
[14]李敏强.遗传算法基本理论及应用.科学出版社,2002.
[15]陆金贵.遗传算法原理与工程应用.科学出版社1997.
[16]玄光男,程润伟.遗传算法与工程优化.清华大学出版社,2004.1
[17]徐宗本,计算智能—模拟进化计算.高等教育出版社,2004..2
[18]汪近能,陈丽燕,吴新余.遗传算法的改进及应用.南京邮电学院学报.1997,(12):165—169
[19]林焰,郝聚民,纪卓尚.隔离小生境遗传算法研究.系统工程学报,2000.15(1)86—92
[20]戴晓明,许超,龚向阳,邵惠鹤.并行遗传算法收敛性分析及优化运算.计算机工程,2002 Vol.18 No.1.
[21]胡能发,康立山,陈毓屏.构建“基因库”求解TSP问题的混合遗传算法.计算机工程与应用,2003.11.
[22]马良.TSP及其扩展问题的混合型启发式算法.上海理工大学学报,Vol.21,No.1,1999.
[23]孙建永,申建中等.一类自适应遗传算法.西安交通大学学报.2000.(10):84—89
[24]吴志远等.一种新的自适应遗传算法及其在多峰值函数优化中的应用[J].控制理论和应用,1999:16(1):127—129
[25]张文修,梁怡.遗传算法的数学基础.西安:西安交通大学出版社,2000.5
[26]潘正君,康立山,陈毓屏.演化计算,清华大学出版社,广西科学技术出版社,1998.
[27] Oliver L.M.A study of permucation Crossover Operators on Traveling Salesman Problem.Lawrence Erlbaum Aasociates,1987,224-230
[28]马欣等.旅行商问题的一种改进遗传算法.计算机仿真,2003,20(:4)36-37
[29]谢胜利,张燕姑,李广.基于遗传算法的旅游推销商问题求解.温州师范学院学报,Vol.23.No.3,June 2002.
[30]王树禾.图论及其算法.中国科学技术大学出版社,1990
[31]马良.最小Hami1ton路问题的算法.计算机工程与应用,1992.
[32]陈志平,徐宗本.计算机数学—计算复杂性理论与NPC,NP难问题的求解.科学出版.2001.8.
[33]陈斌,徐华中.一种改进遗传算法及其在TSP问题中的应用.人工智能及识别技术,Vol.28.No.9,September 2002.
[34]黄厚生.求解旅行商问题的新方法研究.中国期刊网优秀硕博论文,2005.5
[35]马欣等.旅行商问题的一种改进遗传算法.计算机仿真,2003,20(:4)36-37
[36] David A,Robert B,William C. On the Solution of Traveling Salesman problems[R].USA: Rice University,1998.
[37]唐立新.旅行商问题(TSP)的改进遗传算法.东北大学学报,1999,120(1):40
[38]刘海,林智勇,郝志峰.改进遗传交叉算子求解TSP问题.华南理工大学学报(自然科学版),2002 Vol.30 No.12
[39]张良杰,毛志宏,李衍达.遗传算法中突变算子的数学分析及改进策略.电子科学学刊,1996,(6):590~595
[40]王凌,郑大钟.TSP问题次优化求解方法的比较〔J〕.控制与决策,1998,13(1)79一82.
[41]刘琼芳.基于矩阵编码的遗传算法与TSP求解.中国期刊网优秀硕博论文,2001.
[42]宋兆基,徐流美.MATLAB6.5在科学计算中的应用.北京:清华大学出版社,2005
[43]张瑞喜,姚予疆.MATLAB6.O科学运算完整解决方案.北京:人民邮电出版社,2001
[44]马均水等.改进遗传算法搜索性能的大变异操作.控制理论和应用. 1998:15(:3) 404~407