一种最短路由问题的遗传算法研究  

A Research of a Genetic Algorithm for Shortest Path Routing Problem

作　　者：张永军[1] 高兰芳[1] 顾畹仪[1] 

机构地区：[1]北京邮电大学光通信与光波技术教育部重点实验室,北京100876

出　　处：《北京理工大学学报》2007年第11期1005-1008,共4页Transactions of Beijing Institute of Technology

基　　金：国家"八六三"计划项目(2006AA01Z244);国家教委留学回国人员科研资助项目

摘　　要：研究最短路由问题的遗传算法.采用可变长度染色体的编码方法,在固定网络和随机网络环境下,用C语言得出的仿真结果及与Dijkstra算法相比表明:大多解与Dijkstra算法的解相同,存在少数的不同解偏离不大;种群越大,路由的失败比率越小,收敛的速率越慢;当种群一定,增大网络规模时,解的质量下降,网络收敛速率急剧提高.Variable-length chromosomes routing problem of a genetic algorithm. and their genes have been used for solving the shortest path Under random and fixed network, computer simulations with C and comparing with Dijkstra algorithm showed that most of the results are equal to the results of Dijkstra. Meanwhile, the results showed that the larger the population-sizing, the smaller the failure of ratio and the slower the rate of convergence. With population-sizing being fixed, the larger the population-sizing, the poorer the quality of results, and the higher rate of convergence.

关 键 词：最短路由 遗传算法 可变步长编码方法 种群 

分 类 号：TP393.01[自动化与计算机技术—计算机应用技术] TN915.02[自动化与计算机技术—计算机科学与技术]