基于遗传算法的最短路径路由优化算法  

Shortest Path Routing Optimization Algorithms Based on Genetic Algorithms

作　　者：孙宝林[1,2] 李腊元[1] 陈华[3] 

机构地区：[1]武汉理工大学计算机科学与技术学院 [2]武汉科技学院数理系,武汉430073 [3]武汉科技学院数理系

出　　处：《计算机工程》2005年第6期142-144,162,共4页Computer Engineering

基　　金：国家自然科学基金资助项目( 60172035; 90304018);湖北省自然科学基金资助项目( 2004ABA014);湖北省高等学校教学研究基金资助项目(20040231)

摘　　要：论述了用启发式遗传算法解决最短路径路由的优化问题,采用可变长度染色体(路由串)和它的基因(节点)应用于编码问题,交叉操作在交叉点进行部分染色体(部分路由)交换,变异操作维持种群的多样性。该算法采用简单维护操作维护好所有的不可行的染色体。交叉操作和变异操作相结合保证了最优解的搜索能力和解的全局收敛性。计算机仿真实验表明该算法快速有效、可靠性高。This paper presents a heuristic genetic algorithmic to solve shortest path routing optimization problem. Variable-length chromosomes (routing strings) and their genes (nodes) are used for encoding the problem. The crossover operation exchanges partial chromosomes (partial-routes) at positional independent crossing sites and the mutation operation maintains the genetic diversity of the population. The algorithm can cure all the infeasible chromosomes with a simple repair operation. Crossover and mutation together provide a search capability that results in improved quality of solution and enhanced rate of convergence. Computer simulations have verified that the algorithm is efficient and effective.

关 键 词：路由 最短路径路由 路由优化 遗传算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]