actions

組合せ最適化

2018/8/19/ (日) 17:41時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
最適化問題 > 組合せ最適化

組合せ最適化(くみあわせさいてきか、: combinatorial optimization組み合わせ最適化、または組み合せ最適化とも表記される)は、応用数学情報工学での組合せ論最適化問題である。オペレーションズリサーチアルゴリズム理論、計算複雑性理論と関連していて、人工知能数学、およびソフトウェア工学などの交差する位置にある。組合せ最適化では、厳密解が簡単に求まる場合もあれば、そうでない場合もある。厳密解を求めるのが難しいと思われる問題を解くために、その問題の解空間を探索する場合もあり、そのためのアルゴリズムでは、効率的に探索するために解空間を狭めたりすることもある。

非形式的定義

組合せ最適化は、最適化問題の中でも最適解の集合が離散的であるか、離散的なものに減らすことができるものであり、その目的は最も良い解決法を見つけることである。

解が二値ベクトルの場合は0-1最適化問題: 0-1 optimization problem)とも言われる。

形式的定義

組合せ最適化問題のインスタンスは、 [math](X,P,Y,f,\mathrm{extr})[/math] の要素の (tuple) として形式的に記述できる。

ここで

  • X は解空間(solution space、その中に fP が定義されている)
  • P は実現可能かどうかを判定する関数
  • Y は実現可能な解の集合
  • f は最適化関数
  • extr は極値(extreme、最大または最小)

問題例

NP困難

計算複雑性理論の研究は、組合せ最適化に役立っている。いくつかの組合せ最適化問題が、NP困難である事に関係している。そのような問題は、一般的には効率的に解けるとは思われていない。しかし、複雑性理論の様々な近似は、これらの問題のいくつか(例えば「小さな」問題)が効率的に解けることを示唆する。組合せ最適化にも近似解法があり、そのような解法はしばしば重要な応用が可能である。

手法

一般的な手法

特定の問題に対する手法

ヒューリスティックを使用する物

メタヒューリスティック

以下の発見的探索法(メタヒューリスティックアルゴリズム)は、この種の問題を解くのに使われる。

近傍探索法

進化的計算

その他のアルゴリズム

関連項目

外部リンク

テンプレート:最適化アルゴリズム