• 论文 • 上一篇    下一篇

改进的进化算法解最短路问题

李慧贤,李英华   

  1. 西北工业大学计算机学院;大连理工大学数学系 西安710072;辽宁大连116024
  • 出版日期:2007-01-20 发布日期:2007-01-20

李慧贤,李英华. 改进的进化算法解最短路问题[J]. 数值计算与计算机应用, 2007, 28(1): 47-55.

A IMPROVED EVOLUTIONARY ALGORITHM FOR THE SHORTEST PATH ROUTING PROBLEM

  1. Li Huixian (Department of Computer Science,Northwestern Polytechnical University,Xi'an 710072,China) Li Yinghua (Department of Applied Mathematice,Dalian University of Technology,Dalian 116024,Liaoning,China)
  • Online:2007-01-20 Published:2007-01-20
最短路问题是组合优化中的经典问题之一,对其设计有效的算法具有广泛的应用价值和重要的理论意义.为了减少对初始种群选取的限制,扩大种群的多样性,本文提出了一种新的杂交方式.根据一对染色体中不同位相同基因对的数目,设计了分类杂交.这种杂交不仅增加了种群的多样性,还避免了不可行解的出现.与杂交算子相对应设计了具有局部搜索功能的收缩—扩张式变异算子,使得本算法效率有了极大提高,并在理论上证明该算法以概率1收敛到全局最优解.最后的数值试验也表明此算法是十分有效的.
The shortest path routing problem(SP for short)is a class of combinatorial optimization problems.It is of great importance in both theory and applications. To decrease the limitation of choosing the initial population and increase the di- versity of the population,a new crossover operator called classification crossover operator is proposed.It can improve the diversity of the population and can al- ways generate feasible offspring.Furthermore,a novel mutation operator called contraction-extension mutation operator is designed.It has the function of local search and can largely enhance exploration ability of the algorithm.Based on these,an effective evolutionary algorithm for SP is proposed and its convergence to global optimal solution with probability one is proved.At last,the numerical experiments are made and the results indicate the proposed algorithm is efficient.
()

[1]W.Stalling,High-SpeedNetworks:TCP/IP and ATM Design Principles.Englewood Cliffs,NJ: Prentice-Hall,1998.
[2]M.K.Ali and F.Kamoun,“Neural networks for shortest path computation and routing in com- puter networks,”IEEE Trans.Neural Networks,4(1993),941-954.
[3]D.C.Park and S.E.Choi,“A neural network based multi-destination routing algorithm for com- munication network,”in Proc.Joint ConfNeural Networks,1998,1673-1678.
[4]C.W.Anh,R.S.Ramakrishna,C.G.Kang,and I.C.Choi,“Shortest path routing algorithm using hopfield neuralentwork,”Electron.lett.37:19(2001),1176-1178.
[5]M.Munemoto,Y.Takai,and Y.Sato,“A migration scheme for the genetic adaptive routing algorithm,”in Proc.IEEE Int.Conf.Sy-stems,Man,and Cybernetics,1998,2774-2779.
[6]J.Inagaki,M.Haseyama,and H.Kitajima,“A genetic algorithm for determining multip-le routes and its applications,”in Proc.IEEE Int.Symp.Circuits and System,1999,137-140.
[7]Y.Leung,G.Li,and Z.B.Xu,“A genetic algorithm for the multiple destination routing problems,”IEEETrans.Evol.Comput,2(1998),150-161.
[8]J.H.Holland,Adaptation in Natural and ArtificiaSysterns.AnnArbor,MI:Univ.Michigan Press, 1992.
[9]X.Hue,“Genetical gorithms for optimize- tion:Background and applications,”Edinburgh Parallel Computing Centre,Univ.Edinburgh,Edinburgh,Scotland,Vet 1.0,Feb.1997.
[10]G.Harik,E.Cantu-Paz,D.E.Goldberg,and B.L.Miller,“The Gambler's ruin problem,gen-tic algorithms,and the sizing of populations,”Evol.Compute,7:3(1999),231-253.
[11]M.Gorges-Schleuter,“Asparagos 96 and the travelling salesman problem,”in proceedings of the fourth International Conference on Evolutionary Computation,T.B(?)ck,Ed.Piscataway,NJ:IEEE press,171-174,1997.
No related articles found!
阅读次数
全文


摘要