遗传算法在旅行商及网络优化问题中的研究与应用
摘要
自然界的生物进化是一个不断循环的过程,在这一个过程中,生物群体也就不断的完善和发展。可见,生物进化过程本质上是一种优化过程,在计算科学上具有直接的借鉴意义。人们模仿生物的遗传和进化机制,提出了遗传算法。由于遗传算法的普适性和鲁棒性,遗传算法在机器人路径规划,公路路径设计等许多工程领域都发挥了重要的作用。
由于TSP(Traveling Salesman Problem)与众多网络优化问题在形式上有一定的相似性,所以研究遗传算法在TSP问题中的应用对后续问题的展开有一定的指导意义。
随着程控交换机的大量运用,中国七号信令网在我国的应用已经全面铺开。因此NO.7信令网的规划就显的日益重要。其中,A/B平面划分是一个用传统方法难以解决的NPC(Nondeterministic Polynomial complete)问题,它和图的划分问题有类似的地方,但也有其自身的特点。
本文所做的主要工作概括如下:
1.建立了TSP问题的数学模型,在介绍传统遗传算法和贪婪算法的基本原理的基础上,研究了用传统的遗传算法和贪婪算法解决问题的方法,并且对国际通行的TSPLIB中两个不同规模的问题进行了仿真。
2.本文提出了一种新型的遗传变异算子,该算子针对遗传算法在求解TSP问题后期遇到收敛瓶颈的缺点,有目地的加大了种群的搜索空间,使得种群最优值能够迅速的向函数最优值靠拢。仿真试验表明,改进后的遗传算法在性能上有了显著的改进。
3.比较传统遗传算法、贪婪算法,改进遗传算法在解决TSP问题时的性能,指出了三种算法在寻优性能上的差距,解释了改进后算法性能改变的原因。
4.建立了七号信令网A/B平面划分的数学模型,并且用传统的遗传算法和本文提出的遗传算法对数学模型进行仿真,比较了两种算法在网络优化问题上的性能差异。最后就新旧算法耗时和网络的规模关系进行了仿真。
The evolutionary of nature is a cycle process. In this process,the biotic population continuously develop and improve themselves, It is obviously that the evolutionary process is alike an optimization process. we can directly learn it in compute science. People simulate the biological evolution and inheritance system, then they give a new optimization algorithm--GA (genetic algorithm). Because of the common adaptation and the robustness, GA is extensively used in many aspects of engineering. For example in the route planning of robot and the design of road. So the research of the GA is meaningful.
Because the TSP problem (Traveling Salesman Problem) is often used to test the performance of algorithm and it has some degree likeness of many network route optimization questions, the application of GA in TSP can give some guides to solve the net route optimization question.
With the use of SPC exchange,NO.7 signal network has become a supporting network of telephone network, so the planning of NO.7 network become more important than past. In this problem, The division of A/B plane is a NPC problem for a traditional algorithm, it have some degree likeness with other figure division questions, but it also have some unique characteristics.
The major work of this paper can be summarized as follows:
1. This paper establishes the model of TSP problem. Based on the traditional genetic algorithm and greedy genetic algorithm, the method of solving TSP problem based on two algorithms are introduced. Then, this paper get the simulation figures of two examples of TSPLIB.
2. In order to overcome the difficulty of slow convergence of GA, This paper give a new mutation operator to solve this problem. The operator purposefully enlarge the searching space and make the best value of population converge to the best value of function. The simulation shows the improve algorithm can make the algorithm performance become better.
3. To compare the performances of three algorithms, it points out the difference of three alogirithms in searching the best value respect and explains the cause of the change of the algorithm performance.
4.This paper establishes A/B devision model, devised the traditional genetic algorithm and improving algorithm to simulate the problem. It also compare the performance difference of two algorithms. Lastly,the paper also simulated the relation of cost time and net-scale.
由于TSP(Traveling Salesman Problem)与众多网络优化问题在形式上有一定的相似性,所以研究遗传算法在TSP问题中的应用对后续问题的展开有一定的指导意义。
随着程控交换机的大量运用,中国七号信令网在我国的应用已经全面铺开。因此NO.7信令网的规划就显的日益重要。其中,A/B平面划分是一个用传统方法难以解决的NPC(Nondeterministic Polynomial complete)问题,它和图的划分问题有类似的地方,但也有其自身的特点。
本文所做的主要工作概括如下:
1.建立了TSP问题的数学模型,在介绍传统遗传算法和贪婪算法的基本原理的基础上,研究了用传统的遗传算法和贪婪算法解决问题的方法,并且对国际通行的TSPLIB中两个不同规模的问题进行了仿真。
2.本文提出了一种新型的遗传变异算子,该算子针对遗传算法在求解TSP问题后期遇到收敛瓶颈的缺点,有目地的加大了种群的搜索空间,使得种群最优值能够迅速的向函数最优值靠拢。仿真试验表明,改进后的遗传算法在性能上有了显著的改进。
3.比较传统遗传算法、贪婪算法,改进遗传算法在解决TSP问题时的性能,指出了三种算法在寻优性能上的差距,解释了改进后算法性能改变的原因。
4.建立了七号信令网A/B平面划分的数学模型,并且用传统的遗传算法和本文提出的遗传算法对数学模型进行仿真,比较了两种算法在网络优化问题上的性能差异。最后就新旧算法耗时和网络的规模关系进行了仿真。
The evolutionary of nature is a cycle process. In this process,the biotic population continuously develop and improve themselves, It is obviously that the evolutionary process is alike an optimization process. we can directly learn it in compute science. People simulate the biological evolution and inheritance system, then they give a new optimization algorithm--GA (genetic algorithm). Because of the common adaptation and the robustness, GA is extensively used in many aspects of engineering. For example in the route planning of robot and the design of road. So the research of the GA is meaningful.
Because the TSP problem (Traveling Salesman Problem) is often used to test the performance of algorithm and it has some degree likeness of many network route optimization questions, the application of GA in TSP can give some guides to solve the net route optimization question.
With the use of SPC exchange,NO.7 signal network has become a supporting network of telephone network, so the planning of NO.7 network become more important than past. In this problem, The division of A/B plane is a NPC problem for a traditional algorithm, it have some degree likeness with other figure division questions, but it also have some unique characteristics.
The major work of this paper can be summarized as follows:
1. This paper establishes the model of TSP problem. Based on the traditional genetic algorithm and greedy genetic algorithm, the method of solving TSP problem based on two algorithms are introduced. Then, this paper get the simulation figures of two examples of TSPLIB.
2. In order to overcome the difficulty of slow convergence of GA, This paper give a new mutation operator to solve this problem. The operator purposefully enlarge the searching space and make the best value of population converge to the best value of function. The simulation shows the improve algorithm can make the algorithm performance become better.
3. To compare the performances of three algorithms, it points out the difference of three alogirithms in searching the best value respect and explains the cause of the change of the algorithm performance.
4.This paper establishes A/B devision model, devised the traditional genetic algorithm and improving algorithm to simulate the problem. It also compare the performance difference of two algorithms. Lastly,the paper also simulated the relation of cost time and net-scale.
引文
[1]Holland J H,Adaptation in Natuural and Artificial Systems,Ann Arbor,The University of Michigan Press,1975
[2]Fogel L J,Owens A J,Walsh M J,Artificial Intelligence through Simulated Evolution.,New York,John Wiley,1966,3
[3]Rechenberg I,Cybernetic solution path of an experimental problem.,Roy Aircr Establ,libr transl 1222 Hants.UK:Famborough,1965
[4]Schwefel H P,Numerical,Optimization of Computer Models.Chichester:Wiley,1981
[5]雷英杰,MATLAB遗传算法工具箱及应用。西安电子科技大学出版社,2005:46-57
[6]Goldberg D E.Genetic Algorithms in Search,Optimization and Machine Learning Reading,MA:Addison-Wesley,1989
[7]Goldberg,D.E.,Deb,K,Kargupta,H.,and Hank,G.Rapid,Accurate optimization of difficult problems using fast messy genetic algorithms,In Proceedings of the Fifth International Conference on Genetic Algorithms(ICGA5),Whitley,L.D.(ed.),SanMateo,CA,Morgan Kaufmann,1993:56-64
[8]Goldberg D E,Korb B,and Deb K.Messy,Genetic algorithms:motivation,analysis,and firstresultso Complex systems,1989,3:493-530
[9]Davis,L,(ed.),Handbook of Genetic Algorithms,Van Nostrand Reinhold,New York,1991
[10]Koza.J.R,Genetic programming 1,Cambridge,MA:The MITPress,1992
[11]Koza.J.R,Genetic programming.1,Cambridge,MA:The MIT Press,1994
[12]Melame Mithcell,An introduction to Genetic algorithms.Cambridge,MA:The Mit Press,1996
[13]Torn,A.and zilinskas,A Global optimization.Berlin,Springer-Verlag,1989
[14]李敏强,寇纪淞,林丹等,遗传算法的基本理论与应用,科学出版社,2002:79-80
[15]Melanie Mitchell,ABradford book,MITPress,1996:15-25
[16]Barrie M.Baker,M.A.Ayechew,A genetic algorithm for the vehicle routing problem,Computers & Operations Research,Volume 30,Issue 5,April 2003:787-800
[17]邹鹏,求解TSP问题的多级规约算法,软件学报,Vol14,No.1,2003:35-41
[18]M.R加里,D.S.约翰逊著,张立昂等译,《计算机与难解性》-NP完全性理论导引,科学出版社,1987
[19]孙守宇,郑君里,Hopfield网络求解TSP的一种改进算法和理论证明,电子学报,1995,1:73-78
[20]王伟,人工神经网络原理与应用,北京:北京航空航天大学出版社,1995:148-158
[21]Clarke G,Wright JW,Scheduling of vehicles from a central depot to a number of delivery points,Operations Research,1964,12:568-581
[22]Christofides N,Worst-Case,analysis of a new heuristic for the traveling salesman problem.Technical Report,No.388,Pittsburgh,PA:Graduate School of Industrial Administration,Carnegie Mellon University,1976
[23]Kirkpatrick S,Gelatt CD,Vecchi MP,Optimization by simulated annealing.Science,1983,220(4598):671-680
[24]Croes GA,A method for solving traveling salesman problems,Operations Research,1958,6:791-812
[25]Lin S,Computer solutions to the traveling salesman problem.Bell System Technical Journal,1965,44(10):2245-2269
[26]Lin S,Kernighan BW,An effective heuristic algorithm for the traveling salesman problem,Operations Research,1973,21:498-516.
[27]Johnson DS.,Local optimization and the traveling salesman problem,In:Proceedings of the 17th Colloquium on Automata,Language,and Programming.Lecture Notes in Computer Science 443,Berlin:Springer-Verlag,1990.446-461.
[28]Arora S.,Polynomial time approximation schemes for Euclidean TSP and other geometric problems,In:Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science,1996,2-11.http://citeseer.nj.nec.com/arora96polynomial.html
[29]蔡之华,彭锦国,高伟等,一种改进的求解TSP问题演化算法,计算机学报,2005,28(5):823-828
[30]雷英杰.,MATLAB遗传算法工具箱及应用.西安电子科技大学出版社,2005:46-57
[31]Sangit Chatterjee.Genetic algorithms and traveling salesman problems.Europen Journal of Operational Research 93(1996)490-510.
[32]Grefenstette J,et al.Genetic Algorithms for the Traveling SalesmanProblem In:Proc,of 1st Int,Conf.on Genetic Algorithms and Their Applications,Lawrence Erlbaun Association,1985:166-168
[33]Grefenstette J,et al.Genetic Algorithms for the Traveling Salesman Problem In:Proc,of 1st Int.Conf.on Genetic Algorithms and Their Applications,Lawrence Erlbaun Association,1987
[34]Davis Led.Handbook of Genetic Algorithms.Van Nostrand Reinhold,1991
[35]Grefenstette J J.Optimization of control parameters for genetic algorithms,IEEE Traps Syst Man and Cybern.1986,16:122-128
[36]刘海.改进遗传算子在求解TSP问题,华南理工大学学报,Vol30,No.12,2002:71-73
[37]彭丹平,一种求解旅行商问题的新算法,中南民族大学学报,Vo125,No.1,Mar,2006:79-87
[38]Garey M R,Johnson D S,Computers and Intractability-a guide to the theory of NP-completeness[M],San Francisco:W.H.Freeman and Company.1980:221-281.
[39]Thomas H.Cormen,Charles E.Leiserson,Ronald,L.Rivest,etc,潘金贵译,算法导论机械工业出版社,2006,
[40]《公共信道NO.7信令网》,吴立贞,张延川,人民邮电出版社,1998
[41]顾学道,数字电话网自适应选路方式,Vol.141,NO.10,10,1991
[42]周炯磐,《通信网理论基础》,人民邮电出版社
[43]忻展红,吴启程,莫文冬,七号信令网的A/B平面划分问题及其启发式解法,北京邮电大学学报,Vol.24 No.1,Mar.2001:22-27
[44]忻展红,许涛,七号信令网的拓扑结构优化,北京邮电大学学报,Vo1.21,No.2,Jun,1998 1-5
[45]赵蕾,遗传算法在通信网优化中的实现,[学位论文],济南,山东大学,2005
[46]TSPLIB.http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.April,2006
[47]DING Chao(丁超),CHENG Ye(成 晔),HE Miao(何苗),Two-Level Genetic Algorithm for Clustered Traveling SalesmanProblem with Application in Large-Scale TSPs,Tsinghua Science and Technology,August 2007,12(4):459-465
[48]王宏亮,基于遗传算法的网络优化的研究与实现,[学位论文],沈阳,东北大学,2005
[49]陈国良,王煦法,庄镇泉等,遗传算法及其应用,人民邮电出版社,1996年
[50]华令群,基于遗传算法的旅行商问题仿真研究,[学位论文],西安,西北大学,2006:49
[51]康晓东,基于遗传算法的仿真问题研究,[学位论文],天津,南开大学,2005
[2]Fogel L J,Owens A J,Walsh M J,Artificial Intelligence through Simulated Evolution.,New York,John Wiley,1966,3
[3]Rechenberg I,Cybernetic solution path of an experimental problem.,Roy Aircr Establ,libr transl 1222 Hants.UK:Famborough,1965
[4]Schwefel H P,Numerical,Optimization of Computer Models.Chichester:Wiley,1981
[5]雷英杰,MATLAB遗传算法工具箱及应用。西安电子科技大学出版社,2005:46-57
[6]Goldberg D E.Genetic Algorithms in Search,Optimization and Machine Learning Reading,MA:Addison-Wesley,1989
[7]Goldberg,D.E.,Deb,K,Kargupta,H.,and Hank,G.Rapid,Accurate optimization of difficult problems using fast messy genetic algorithms,In Proceedings of the Fifth International Conference on Genetic Algorithms(ICGA5),Whitley,L.D.(ed.),SanMateo,CA,Morgan Kaufmann,1993:56-64
[8]Goldberg D E,Korb B,and Deb K.Messy,Genetic algorithms:motivation,analysis,and firstresultso Complex systems,1989,3:493-530
[9]Davis,L,(ed.),Handbook of Genetic Algorithms,Van Nostrand Reinhold,New York,1991
[10]Koza.J.R,Genetic programming 1,Cambridge,MA:The MITPress,1992
[11]Koza.J.R,Genetic programming.1,Cambridge,MA:The MIT Press,1994
[12]Melame Mithcell,An introduction to Genetic algorithms.Cambridge,MA:The Mit Press,1996
[13]Torn,A.and zilinskas,A Global optimization.Berlin,Springer-Verlag,1989
[14]李敏强,寇纪淞,林丹等,遗传算法的基本理论与应用,科学出版社,2002:79-80
[15]Melanie Mitchell,ABradford book,MITPress,1996:15-25
[16]Barrie M.Baker,M.A.Ayechew,A genetic algorithm for the vehicle routing problem,Computers & Operations Research,Volume 30,Issue 5,April 2003:787-800
[17]邹鹏,求解TSP问题的多级规约算法,软件学报,Vol14,No.1,2003:35-41
[18]M.R加里,D.S.约翰逊著,张立昂等译,《计算机与难解性》-NP完全性理论导引,科学出版社,1987
[19]孙守宇,郑君里,Hopfield网络求解TSP的一种改进算法和理论证明,电子学报,1995,1:73-78
[20]王伟,人工神经网络原理与应用,北京:北京航空航天大学出版社,1995:148-158
[21]Clarke G,Wright JW,Scheduling of vehicles from a central depot to a number of delivery points,Operations Research,1964,12:568-581
[22]Christofides N,Worst-Case,analysis of a new heuristic for the traveling salesman problem.Technical Report,No.388,Pittsburgh,PA:Graduate School of Industrial Administration,Carnegie Mellon University,1976
[23]Kirkpatrick S,Gelatt CD,Vecchi MP,Optimization by simulated annealing.Science,1983,220(4598):671-680
[24]Croes GA,A method for solving traveling salesman problems,Operations Research,1958,6:791-812
[25]Lin S,Computer solutions to the traveling salesman problem.Bell System Technical Journal,1965,44(10):2245-2269
[26]Lin S,Kernighan BW,An effective heuristic algorithm for the traveling salesman problem,Operations Research,1973,21:498-516.
[27]Johnson DS.,Local optimization and the traveling salesman problem,In:Proceedings of the 17th Colloquium on Automata,Language,and Programming.Lecture Notes in Computer Science 443,Berlin:Springer-Verlag,1990.446-461.
[28]Arora S.,Polynomial time approximation schemes for Euclidean TSP and other geometric problems,In:Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science,1996,2-11.http://citeseer.nj.nec.com/arora96polynomial.html
[29]蔡之华,彭锦国,高伟等,一种改进的求解TSP问题演化算法,计算机学报,2005,28(5):823-828
[30]雷英杰.,MATLAB遗传算法工具箱及应用.西安电子科技大学出版社,2005:46-57
[31]Sangit Chatterjee.Genetic algorithms and traveling salesman problems.Europen Journal of Operational Research 93(1996)490-510.
[32]Grefenstette J,et al.Genetic Algorithms for the Traveling SalesmanProblem In:Proc,of 1st Int,Conf.on Genetic Algorithms and Their Applications,Lawrence Erlbaun Association,1985:166-168
[33]Grefenstette J,et al.Genetic Algorithms for the Traveling Salesman Problem In:Proc,of 1st Int.Conf.on Genetic Algorithms and Their Applications,Lawrence Erlbaun Association,1987
[34]Davis Led.Handbook of Genetic Algorithms.Van Nostrand Reinhold,1991
[35]Grefenstette J J.Optimization of control parameters for genetic algorithms,IEEE Traps Syst Man and Cybern.1986,16:122-128
[36]刘海.改进遗传算子在求解TSP问题,华南理工大学学报,Vol30,No.12,2002:71-73
[37]彭丹平,一种求解旅行商问题的新算法,中南民族大学学报,Vo125,No.1,Mar,2006:79-87
[38]Garey M R,Johnson D S,Computers and Intractability-a guide to the theory of NP-completeness[M],San Francisco:W.H.Freeman and Company.1980:221-281.
[39]Thomas H.Cormen,Charles E.Leiserson,Ronald,L.Rivest,etc,潘金贵译,算法导论机械工业出版社,2006,
[40]《公共信道NO.7信令网》,吴立贞,张延川,人民邮电出版社,1998
[41]顾学道,数字电话网自适应选路方式,Vol.141,NO.10,10,1991
[42]周炯磐,《通信网理论基础》,人民邮电出版社
[43]忻展红,吴启程,莫文冬,七号信令网的A/B平面划分问题及其启发式解法,北京邮电大学学报,Vol.24 No.1,Mar.2001:22-27
[44]忻展红,许涛,七号信令网的拓扑结构优化,北京邮电大学学报,Vo1.21,No.2,Jun,1998 1-5
[45]赵蕾,遗传算法在通信网优化中的实现,[学位论文],济南,山东大学,2005
[46]TSPLIB.http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.April,2006
[47]DING Chao(丁超),CHENG Ye(成 晔),HE Miao(何苗),Two-Level Genetic Algorithm for Clustered Traveling SalesmanProblem with Application in Large-Scale TSPs,Tsinghua Science and Technology,August 2007,12(4):459-465
[48]王宏亮,基于遗传算法的网络优化的研究与实现,[学位论文],沈阳,东北大学,2005
[49]陈国良,王煦法,庄镇泉等,遗传算法及其应用,人民邮电出版社,1996年
[50]华令群,基于遗传算法的旅行商问题仿真研究,[学位论文],西安,西北大学,2006:49
[51]康晓东,基于遗传算法的仿真问题研究,[学位论文],天津,南开大学,2005