進化アルゴリズムによる動的環境における二目的ルーティング問題の一解法

カテゴリ: 部門大会

論文No: TC5-2

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

発行日: 2007/09/04

タイトル(英語): Evolutionary Algorithm for Bicriteria Routing Problem in Stochastic and Dynamic Environment

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

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

キーワード: 二目的最短経路問題|多目的遺伝的アルゴリズム|ファジイ　ロジック　コントロール|動的環境|Bicriteria Shortest Path Problem|multiobjective Genetic Algorithm|Fuzzy Logic Control|Dynamic Environment

要約(日本語): Dynamic routing protocols not only perform these path determination and route table update functions but also determine the next-best path if the best path to a destination becomes unusable. The capability to compensate for topology changes is the most important advantage dynamic routing offers over static routing.　In this paper, we consider a bicriteria shortest path routing (bSPR) model dedicated to calculating nondominated paths in the dynamic environment for (1) the minimum total cost and (2) the minimum transmission delay. To solve this bSPR problem, we propose a new multiobjective genetic algorithm (moGA): (1) an efficient chromosome representation using the priority-based encoding method; (2) a new operator of GA parameters auto-tuning, is adaptively regulation of exploration and exploitation based on the change of the average fitness of parents and offspring which is occurred at each generation; and (3) an interactive adaptive-weight fitness assignment mechanism is implemented that assigns weights to each objective and combines the weighted objectives into a single objective function. Numerical experiments with various scales of network routing problems in the dynamic environment show the effectiveness and the efficiency of our approach by comparing with the recent researches.

PDFファイルサイズ: 11,463 Kバイト