Bicriteria Network Design Problem Using Priority-based GA and Weighted-sum Approach

カテゴリ: 部門大会

論文No: OS6-5

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

発行日: 2004/09/02

タイトル(英語): Bicriteria Network Design Problem Using Priority-based GA and Weighted-sum Approach

著者名: 玄 光男(早稲田大学),林 林(早稲田大学),程潤偉 (JANA Solutions,Inc.)

著者名(英語): Mitsuo Gen(Waseda University),Lin Lin(Waseda University),Runwei Cheng(JANA Solutions,Inc.)

キーワード: Multiobjective Genetic Algorithm|Bicriteria Network Design Problem|maximum flow problem|shortest path problem|Pareto optimal solutionspriority-based encoding method

要約(日本語): This paper considers the Bicriteria Network Design Problem (BNP) with the two conflicting objectives of minimizing cost and maximizing flow. Network design problems where even one flow measure be maximized, are often NP-hard problems. But, in real-life applications, it is often the case that the network to be built is required to optimize multi-criteria simultaneously. Thus the calculation of the multi-criteria network design problems is a difficult task. This paper propose a new Multiobjective Genetic Algorithm (MOGA) approach that priority-based encoding method, a new crossover operator called as Weight Mapping Crossover (WMX) and immigration operator considered. These methods provide a search capability that results in improved quality of solution and enhanced rate of convergence. And also weighted-sum approach is employed to evaluate solutions found in the search process, nondominated sorting technique is used to obtain Pareto optimal solutions. Numerical analyses show that 1) the proposed approach has a higher rate of convergence than other GA approaches using different genetic representation methods; 2) the weighted-sum approach exhibits a better quality of Pareto solutions than other different fitness assignment approaches by MOGAs.Index Terms— Bicriteria network design problem, maximum flow problem, multiobjective genetic algorithm, priority-based encoding method, Pareto optimal solutions, shortest path problem.

PDFファイルサイズ: 7,654 Kバイト