こんにちは！今回は組み合わせ最適化問題のさまざまな解法について紹介していきます。
組み合わせ最適化問題の例
組み合わせ最適化とは、多くの選択肢がある中で目的に最も一致する解を導き出す方法です。というのも、総当たりで求めようとすると因子の数次第では爆発的に組み合わせが増えてしまうNP問題がほとんどだからです。それを効率よく求めるためにさまざまな方法が取られてきました。
実際の組み合わせ最適化問題としては次のようなものが挙げられます。
- 最適選択問題
- 配送計画問題
- 最適経路問題
- 最小木問題
- スケジューリング問題
- 配置問題
特徴としてはグラフで表現できるケースが多く、グラフ理論との組み合わせた解法が多く用いられています。
組み合わせ最適化の解法
よく用いられる解法を大まかに分類すると、次の4種類に分けられます。
- 基礎的な探索
- OR(オペレーションズ・リサーチ)
- ヒューリスティック探索
- メタヒューリスティック探索
基礎的な探索
総当たりなどの単純なアルゴリズムで最適解を出します。探索の方法を工夫して素早く最適解を出せるようになっていますが、問題によっては計算量が膨大になるため解が出るまでにかなりの時間がかかってしまいます。
アルゴリズム例
- 幅優先探索
- 深さ優先探索
- ダイグストラ法
- 動的計画法
OR(オペレーションズ・リサーチ)
意思決定に関わる科学的なアプローチで解析的に最適解を出すことができます。ただし、条件を複雑にすると解が消失します。なので、型にはまった問題（解があることが分かっている条件）の最適解を求める際に利用します。
アルゴリズム例
- 線形計画法・多目的線形計画法
- AHP(Analytics Hierarchy)
- 決定木
- PERT(Program Evaluation and Review Technique)
ヒューリスティック探索
発展的手法と呼ばれ、評価基準を細分化して逐次的に解を求めていくことで最適解を求めます。最適解に対する信頼度はやや低いですが、高速に解が求まり、多種多様な問題に対応できるため、動的な環境の変化に強いことも大きな特徴です。
アルゴリズム例
- 最良優先探索
- Aスターアルゴリズム
- オークションアルゴリズム
メタヒューリスティック探索
ヒューリスティック探索を一般化したアルゴリズムで、細かい問題設定を省いて最適解を求めます。これも最適解に対する信頼度はやや低いですが、解が求まる速度が速いのでいろいろな問題を同じアルゴリズムで解くことができます。
アルゴリズム例
- 遺伝的アルゴリズム
- アントコロニー最適化（群知能）
ちなみに他にもかなりたくさんあります（笑）
引用：最適化手法:メタヒューリスティクスのアルゴリズム（池田 伸太郎）
https://ikeda-lab.com/webarchivefiles/overview_metaheuristics.pdf
一口に組み合わせ最適化問題と言ってもかなりの解法があるくらい長く注目されてきた分野なので、アルゴリズム大好き人間にとっては楽しい内容なのではないでしょうか。
どれを選ぶかについては、問題をキチンと理解し実行時間と最適解への一致性で決めるべきです（ココが一番難しい）。
