遺伝的アルゴリズムによる多目的ナップサック問題の一解法

カテゴリ: 部門大会

論文No: OS5-3

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

発行日: 2003/08/29

タイトル(英語): A Genetic Algorithm for Multi-objective Knapsack Problem

著者名: 井田 憲一(前橋工科大学),菅 良平(前橋工科大学),玄 光男(早稲田大学)

著者名(英語): Kenichi Ida(Maebashi Institute Technology),Ryouhei Suga(Maebashi Institute Technology),Mitsuo Gen(Waseda University )

キーワード: 遺伝的アルゴリズム|ナップサック問題|多目的問題多目的問題|Genetic Algorithm|Knapsack Problem|Multi-objective Problem

要約(日本語): 　近年、遺伝的アルゴリズム(GA:Genetic Algorithm)が,ナップサック問題のような組合せ最適化問題をはじめとした様々な最適化問題へ盛んに適用されるようになった.その理由の1つにGAの大域探索能力の高さが挙げられるが,解空間が広大で複雑な場合局所解におち込んだり、探索に長時間を要し最適解に到達できないケースも多い.この対策としては,何らかの方法を用いて対象問題の解空間を分割、縮小することにより探索範囲を狭めることが効果的であるとされてる.

　本研究では,貪欲解法の導入により解の探索範囲の縮小を実現するとともに,局所探索による探索効率の向上を目指したGAを提案する。さらに提案手法を多目的0-1ナップサック問題に適用し、その有効性を検証する.

PDFファイルサイズ: 2,287 Kバイト