組合せ最適化
組合せ最適化(くみあわせさいてきか、英: combinatorial optimization、組み合わせ最適化、または組み合せ最適化とも表記される)は、応用数学や情報工学での組合せ論の最適化問題である。オペレーションズリサーチ、アルゴリズム理論、計算複雑性理論と関連していて、人工知能、数学、およびソフトウェア工学などの交差する位置にある。組合せ最適化では、厳密解が簡単に求まる場合もあれば、そうでない場合もある。厳密解を求めるのが難しいと思われる問題を解くために、その問題の解空間を探索する場合もあり、そのためのアルゴリズムでは、効率的に探索するために解空間を狭めたりすることもある。
非形式的定義
組合せ最適化は、最適化問題の中でも最適解の集合が離散的であるか、離散的なものに減らすことができるものであり、その目的は最も良い解決法を見つけることである。
解が二値ベクトルの場合は0-1最適化問題(英: 0-1 optimization problem)とも言われる。
形式的定義
組合せ最適化問題のインスタンスは、 の要素の組 (tuple) として形式的に記述できる。
ここで
- X は解空間(solution space、その中に f と P が定義されている)
- P は実現可能かどうかを判定する関数
- Y は実現可能な解の集合
- f は最適化関数
- extr は極値(extreme、最大または最小)
問題例
- 巡回セールスマン問題
- 中国人郵便配達問題
- 最小全域木問題
- 最短経路問題
- 線形計画問題(基底にするべき変数を選ぶ問題と見なすと組合せ的になる)
- 整数計画問題
- エイト・クイーン(制約充足問題の一種)
- ナップサック問題
- 最大フロー問題
- 最小カット問題
- 最大マッチング問題
- 劣モジュラ関数最小化
- 劣モジュラ関数最大化
NP困難
計算複雑性理論の研究は、組合せ最適化に役立っている。いくつかの組合せ最適化問題が、NP困難である事に関係している。そのような問題は、一般的には効率的に解けるとは思われていない。しかし、複雑性理論の様々な近似は、これらの問題のいくつか(例えば「小さな」問題)が効率的に解けることを示唆する。組合せ最適化にも近似解法があり、そのような解法はしばしば重要な応用が可能である。
手法
一般的な手法
特定の問題に対する手法
- 最短経路問題
- 最小全域木
- 最大フロー問題・最小カット問題
- 巡回セールスマン問題
ヒューリスティックを使用する物
メタヒューリスティック
以下の発見的探索法(メタヒューリスティックアルゴリズム)は、この種の問題を解くのに使われる。
その他のアルゴリズム
- GRASP
- Population-based incremental learning
- シミュレーティド・エボリューション
- Reactive search
関連項目
外部リンク
- 組合せ最適化(研究者向けの解説)
- 組合せ最適化応用例
- 簡単そうで難しい組合せ最適化(PDF)
- Andrew Lucas:"Ising formulations of many NP problems", Front.Phys (Feb. 2014)
| ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
非線形(無制約) |
| ![]() | ||||||||||||
非線形(制約付き) |
| |||||||||||||
凸最適化 |
| |||||||||||||
組合せ最適化 |
| |||||||||||||
メタヒューリスティクス | ||||||||||||||
|