大規模組合せ最適化問題に対するメタ戦略のロバスト性に関する研究

点击翻译按钮获取中文摘要

多くのシステム工学的,情報工学的問題は,組合せ最適化問題として定式化できる.しかし,その多くに対し,取り扱おうとする問題の規模が大きい場合,厳密な最適解を求めることが極めて困難である.このような問題に現実的に対処するための一手法として,良質の近似解を出来るだけ効率良く求めようとする近似解法がある.最近では,従来の近似解法よりも多少時間はかかっても,より良質の解を求めようとする,メタ戦略の研究が盛んである.これらメタ戦略の魅力は,「与えられた問題に対するとりわけ深い洞察がなくても簡単にプログラムが作れる」簡潔さ,および,「代表的なオペレータのみを用いて適当に作ったものでもある程度の性能が期待できる」ロバスト性にあるといえる.そこで,出来るだけ一般性のあるデータや知識を蓄積していくことで,メタ戦略を設計する際の指針を示すことを目的とし,研究を行った.具体的な対象としては,1機械スケジューリング問題(SMP)を取り上げた.これは,与えられたn個の仕事を1台の機械で処理する際のコスト最小の順列を求めるという問題で,NP困難であることが知られている.メタ戦略としては,多スタート局所探索法(MLS法),GRASP法,遺伝アルゴリズム(GA法),アニーリング法(SA法),および,タブ-探索法(TS法)を取り上げた.n=100までの問題例に対する計算実験の結果,以下のような傾向が観察できた.なお,MLS法は,メタ戦略の中では最も単純であるが,本研究で取り扱ったSMPに対しては比較的良好な結果が得られたため,他のメタ戦略の性能を評価する際の基準として用いた.1)GRASP法の性能は,用いる欲張り法に大きく依存し,MLS法に比べて性能が向上する場合もあれば,劣る場合もある.2)MLS法の変形である反復局所探索法の性能は,用いる近傍によってやや傾向が異なるが,MLS法に比べ有効である.とくに,ある設定の下では,調べた他のメタ戦略のいずれよりも高い性能が得られた.3)GA法は,多くの場合,MLS法と同等,あるいはそれ以下の性能を持つ.一方,GA法に局所探索法を組合せた方法は,比較的長い計算時間が与えられた場合,MLS法より有効である.また,これらの性能は,内部オペレータの一つである交叉法に関してロバストである.4)SA法も,比較的長い計算時間が許される場合は有効であり,その性能はパラメータの値に大きくは依存しない.5)TS法の性能は,用いるパラメータの値などに大きく依存し,MLS法に比べて性能が向上する場合もあれば,劣る場合もある.6)近傍の定義は,GA法を除く全ての戦略において極めて重要である.