基于遗传策略的过多指定点路由算法的研究

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (19): 160-163.

基于遗传策略的过多指定点路由算法的研究

肖晓丽，胡宁静，李春芳，田悦宏，黄继红

长沙理工大学计算机与通信工程学院，长沙 410076

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-07-01 发布日期:2007-07-01
通讯作者: 肖晓丽

Research of designated multi-node routing based on hierarchic genetic algorithm

XIAO Xiao-li，HU Ning-jing，LI Chun-fang，TIAN Yue-hong，HUANG Ji-hong

College of Computer and Communication Engineering，Changsha University of Science and Technology，Changsha 410076，China

Received:1900-01-01 Revised:1900-01-01 Online:2007-07-01 Published:2007-07-01
Contact: XIAO Xiao-li

摘要/Abstract

摘要： 提出了一种求解移动IP中过多指定节点的最短路由问题的分层遗传算法。通过对已有的求解路由模型进行分析，建立了通过多个指定节点的网络模型;根据所给的指定节点来划分解的可行域的层次，来求解移动IP的最短路由问题;该算法采用了可变长度染色体的编码方法，并使用了随机遍历抽样的选择方法，根据网络的拓扑信息进行交叉和变异操作，同时使用修正函数以消除遗传操作中产生的不可行解。各个子种群间独立地并行运行遗传算法，最后得到一条经过多个指定节点的最短路由。并建立随机网络拓扑对该算法进行仿真，实验结果表明，该算法能够有效地求出通过多个指定节点的最短路由，并且受网络规模和问题的复杂性影响比较小。

Abstract: A hierarchic genetic algorithm for calculation of the shortest routing problem of mobile IP via the designated multi-node is presented in this paper and a new model is built by analyzing the current routing model.The hierarchy of solutions is plotted according to designated nodes，Variable-length chromosomes are employed in our genetic algorithm and the stochastic universal sampling is adopted as the selective operation.Crossover and mutation use the topological information from network to operate.A repair function is used to eliminate the unfeasible solution produced by genetic operations.The shortest routing problem of mobile IP via the designated multi-node is gained by executing independently genetic algorithm in multi sub-populations in parallel.Simulation results from random network topology show that the algorithm can reach the expected purpose and the effect from the size of network and the complexity is smaller than traditional methods.

肖晓丽，胡宁静，李春芳，田悦宏，黄继红. 基于遗传策略的过多指定点路由算法的研究[J]. 计算机工程与应用, 2007, 43(19): 160-163.

XIAO Xiao-li，HU Ning-jing，LI Chun-fang，TIAN Yue-hong，HUANG Ji-hong. Research of designated multi-node routing based on hierarchic genetic algorithm[J]. Computer Engineering and Applications, 2007, 43(19): 160-163.