Mathematical Analysis for Metaheuristics and its Application

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

組合せ最適化問題は，スケジューリング問題，配置問題など様々な意思決定問題で利用されている．これらの問題を解くための手法としてメタヒューリスティクスと呼ばれる一群の近似解法がある．そしてメタヒューリスティクスが経験的に良い解を導き出すことは多くの研究でも示されている．しかし，“なぜ，メタヒューリスティクスが良い解を導き出してくれるのか？” は一つの謎でもある．そこで本研究では，組合せ最適化問題の解空間に特徴的な性質が存在する仮定のもと，その解空間および解の探索過程を数理的にモデル化し，求まる近似解のコスト値などを推定する．それによりメタヒューリスティクスの各手法の性能を理論的（数理的）に解析し，その能力の謎を解き明かすことを目指す．そのために，申請者 は，組合せ最適化問題の解空間における解のランダムウォークにおいて，現在の解のコスト値が一つ前のコスト値に依存するAR(1)プロセスとなる性質を示した．その性質を利用し解の近傍の解析を行い，近傍の統計量を汎用的に導き出していく．統計量とは，近傍の分布構造を表すパラメータ，近傍の最小コスト値の推定値である. この近傍の統計量が推定できれば，メタヒューリスティクス自体の性能を，近傍の統計量に基づき，問題に依存することなく理論的に導き出すことが可能となるであろう．本年度は，多くの問題に対して解のランダムウォークがこのAR(1)の性質を満足しているか調査し，AR(1)としてモデル化し近傍の統計量を導き出すことが可能であるかの検証をおこなった．この特徴が多くの問題に見出すことが出来れば，特定の問題および近傍に限ることなく多くの問題に利用がはかれることとなる．すなわち，解空間がAR(1)を満足するという前提から，様々な問題に利用可能である数理的モデルが構築され，汎用的に適用可能な理論的解析の世界を築くことが可能となる．