0-1組合せ最適化問題に対する連続緩和によるヒューリスティック解法

カテゴリ: 部門大会

論文No: PS4-11

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

発行日: 2012/09/05

タイトル(英語): Heuristic Methods for 0-1Combinational Optimization Problems by Using Continuous Relaxation Approaches

著者名: 友永 真太郎(慶應義塾大学),相吉英太郎 (慶應義塾大学)

著者名(英語): Shintaro Tomonaga(Keio University),Eitaro Aiyoshi(Keio University)

キーワード: 組合せ最適化ナップサック問題|ナップサック問題|連続緩和|combinational optimization|particle swarm optimization|knapsack problem|continuous relaxation

要約(日本語): 離散変数最適化問題に対して，離散空間での探索における「組合せの爆発」を回避するために，0-1 組合せ変数を0以上1 以下の連続変数の問題に緩和した問題(連続変数緩和問題) を定式化しなおして解く解法が従来から存在する．その代表的な解法がHopfield 型ニューラルネットワークであるが，このような解法が有効なのは，目的関数が離散変数に対して線形または2 次関数の場合に限られ，一般に複雑な関数形を目的関数にもつ問題やその関数形自体が表現できない問題には，こうした連続緩和は行うことができない．そこで，本研究では，一般的な目的関数をもつ離散変数最適化問題に対して，この緩和操作も考慮した等価な連続変数緩和問題を定式化し，この変換問題に固有のヒューリスティックな新しい連続変数最適化手法を，Particle Swarm Optimization(PSO) をヒントに提案し，0-1 変数を直接扱う遺伝的アルゴリズム(GA)とその計算性能を比較する．

PDFファイルサイズ: 1,979 Kバイト