大規模組合せ最適化問題に対するメタ戦略のロバスト性に関する実験的解析

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

多くのシステム工学的,情報工学的問題は,組合せ最適化問題として定式化できる.しかし,その多くに対し,取り扱おうとする問題の規模が大きい場合,厳密な最適解を求めることが極めて困難である.このような問題に現実的に対処するための一手法として,良質の近似解を出来るだけ効率良く求めようとする近似解決がある.最近では,従来の近似解決よりも多少時間はかかっても,より良質の解を求めようとする,メタ戦略の研究が盛んである.これらメタ戦略の魅力は,「与えられた問題に対するとりわけ深い洞察がなくても簡単にプログラムが作れる」簡潔さ,および,「代表的なオペレータのみを用いて適当に作ったものでもある程度の性能が期待できる」ロバスト性にあるといえる.そこで,出来るだけ一般性のあるデータや知識を蓄積していくことで,メタ戦略を設計する際の指針を示すことを目的とし,研究を行った.具体的な対象として,1機械スケジューリング問題(SMP)と最大充足可能性問題(MAXSAT)の2つを取り上げ,メタ戦略としては,多スタート局所探索法(MLS法),GRASP法,遺伝アルゴリズム(GA法),アニーリング法(SA法),タブー探索法(TS法),および反復局所探索法(ILS法)などを取り上げ,計算実験を行った.その結果,様々な傾向が観測されたわけだがロバスト性の観点からは,以下の2点が特に重要な結論と思われる.1)メタ戦略の性能は基本となる局所探索法の近傍に大きく左右され,その性能差は,メタ戦路間の性能差よりも大きい場合がある.2)ILS法は開発が最も簡単であるが高い性能が得られる場合が多い.これらの傾向は,2つ性質が異なる問題に対して同様であったので,幅広い問題に対して共通に成り立つ汎用性の高い結果と言える.なお,上記1は,近傍に問題構造をうまく取り入れることの重要性を示すものであるが,MAXSATに対しては,これを確認するため,様々な近傍の比較を行った.その過程で,従来開発されていたものよりも優れた近傍を開発することに成功した.この近傍に対しては,近傍サイズと計算量を理論的に解析し,興味深い結果が得られている.また,上記1により重要性が確認された近傍をより柔軟に探索する手法として,可変近傍探索法(variabledepthsearch)と呼ばれる手法がある.この手法は,やや複雑で,適用例が少ないが,上の結論より,今後の発展が期待できる.一例として,一般化割当問題(generalizedassignmentproblem)への適用を試みた.その結果,従来法に比べて非常に優れた解法の開発に成功した.研究費により購入した計算機器は上述の計算実験を遂行し,また,それらの結果を取りまとめるのに利用した.また,研究成果を報告するための海外渡航費としても利用した.