初めに
数理最適化という言葉を聞くと、
- 常に「最適解」を求めるもの
- コンピュータが完璧な答えを出してくれるもの
というイメージを持たれがちです。
しかし、実際の現場で扱う問題では、
- 制約が多い
- 問題規模が大きい
- 組み合わせが指数関数的に増える
といった理由から、理論上の最適解を求めること自体が現実的でない 場面が多くあります。
そこで重要になるのが、
- まず制約を満たす解とは何か
- 「最適」とは何を基準に決めているのか
- なぜ近似解という考え方が必要なのか
といった、解に対する基本的な考え方です。
この回の目的は、数理最適化では「どのような種類の解を、どのような理由で使い分けているのか」 を直感的に理解してもらうことです。
本記事を通して、
- 「最適解が出ない＝失敗ではない」
- 「現場で使われている最適化は、実は近似解が中心である」
という点を感じ取っていただければ幸いです。
実行可能解
実行可能解とは
実行可能解（Feasible Solution） とは、
すべての制約条件を満たしている解
のことです。
数理最適化では、まず制約を満たす解（実行可能解）を見つけ、 その中からより良い解を探索していく
という手順をとります。
最適解
最適解とは
最適解（Optimal Solution） とは、
実行可能解（すべての制約条件を満たしている解）の中で、目的関数の値が最も良い解
です。
目的関数の定義によって、
- 最大化問題では「値が最大」の解
- 最小化問題では「値が最小」の解
が最適解となります。
グローバル最適解とローカル最適解
- グローバル最適解（Global Optimum）
- 解の探索空間全体の中で、最も良い解
- 理論的に、これ以上良い解は存在しません
- ローカル最適解（Local Optimum）
- 周囲の解と比べると良いが、全体では最良とは限らない解
最小化問題の場合、値が最小の解がグローバル最適解であり、値が極小の解がローカル最適解となります。
アルゴリズムによっては、ローカル最適解に収束しないように工夫を加えることが重要になります。
近似解
近似解とは
近似解（Approximate Solution） とは、
最適解ではないが、十分に良いと判断できる解
のことです。
なぜ近似解が必要か
現実の問題では、
- 問題規模が大きい
- 制約が多い
- 組み合わせが指数関数的に増える
といった理由から、最適解を求めることが現実的でない場合が多くあります。
例えば、
20個の荷物を、2台のトラックのどちらに載せるか
を考えてみます。
- 1つの荷物には、どちらのトラックに載せるか、 2 通りの選択肢がある
- 荷物が 20 個ある
そのため、割り当ての組み合わせは
にもなります。さらに荷物が1つ増えるだけで
- 21個 → 約200万通り
- 22個 → 約400万通り
と、問題サイズが少し大きくなるだけで、組み合わせ数は倍々で増えていきます。
ここに、
- 積載量
- 順序
といった制約が加わると、探索すべき組み合わせはさらに複雑になり、すべてを調べて最適解を求めることは困難になります。
そのため数理最適化では、
- 短時間で
- 実用上問題ない品質の解
を得ることを目的として、近似解が使われます。
まとめ
数理最適化では、まず制約を満たす実行可能解を見つけ、その中から最適解を探索していきます。しかし現実の問題では、組み合わせが指数関数的に増加するため、厳密な最適解を求めることが困難な場合が多くあります。そのため実務では、短時間で十分に良い判断を支える近似解が重要な役割を果たします。
コメント