A Random Key-based GA Approach for Shortest Path Routing Problem in OSPF

カテゴリ: 部門大会

論文No: MC2-1

グループ名: 【C】平成17年電気学会電子・情報・システム部門大会講演論文集

発行日: 2005/09/06

タイトル(英語): A Random Key-based GA Approach for Shortest Path Routing Problem in OSPF

著者名: 林 林(早稲田大学),玄 光男(早稲田大学)

著者名(英語): Lin Lin(Waseda University),Mitsuo Gen(Waseda University)

キーワード: Open Shortest Path First|Shortest Path Routing|Genetic Algorithm|Random Key-based Encoding

要約(日本語): In this paper, we present a Genetic Algorithm (GA) approach to the Shortest Path Routing (SPR) problem in Open Shortest Path First (OSPF), called OSPF routing problem. The SPR algorithm calculates the shortest (least cost) path between the routers and all the networks of the internetwork. The SPR problem with a negative cycle is substantially harder to solve than is the shortest path problem without a negative cycle. SPR problem is an NP-complete problem; no polynomial-time algorithm for this problem is likely to exist. For respecting to path optimality (quality of solution) and convergence speed, we propose a paths growth procedure and a combination of arithmetical crossover operator, swap mutation, and immigration operator by the random key-based genetic representation. Numerical analyses for various scale of network design problems show the proposed random key-based genetic algorithm (rkGA) approach has a higher search capability that enhanced rate of convergence and improve computation time than other GA approaches using different genetic representation methods.

PDFファイルサイズ: 6,411 Kバイト