組み合わせの種類(変数)が多く、どの組み合わせにすれば最適かという問題を「組み合わせ最適化問題」と言います。
もちろん全部の組み合わせを試せば最適解を見つけることができます。しかし変数の数が多くなればなるほど計算量は膨大となり、現実的では無くなっていきます。
勾配法
そのような場合に用いられる考え方が勾配法です。大雑把に言えば、「全パターン計算なんかやってられっか！もっと簡略化して計算量を減らしてやる！」という方法です。ちゃんとした説明は関数とか微分とかが出てきてややこしくなるのですが、そういうのは専門書でも読んでもらうとしてここでは図で見てみましょう。
黒丸のボールは計算結果です。一番低いところを最適解として、そこにボールが辿り着くことを目指します。
とりあえずまずは適当な値を代入してエイヤとボールを落としてみます。次に変数をちょっと変えてもう一度エイヤと落とした時に、前回の計算結果よりもボールが下に行けばそっちの方が良し、上に行くようであればダメ、として計算を繰り返します。そうやって繰り返すことでボールがどんどん下に向かっていき、全部のパターンを計算するよりも早く最適解に辿り着くことができるのです。つまりボールを一番下まで転がすようなイメージが勾配法です。AIに用いられているニューラルネットワークのようなプログラムでもよく使われています。
いや、まあ、簡略化し過ぎて厳密に言えばちょっと違って二回目以降にどう変数を変えるかがキモではあるのですが、詳細な説明は大変なのです。とりあえずボールを転がすようなイメージと思ってもらえれば。
ローカルミニマム
組み合わせ最適化問題を解くにはこの勾配法が一般的なのですが、実は弱点があります。それがローカルミニマムです。また図を用いて見てみましょう。
前回のようにただの凹形状であれば最適解である一番底までボールは転がっていきますが、今回の図のように凹が複数ある場合、最適解である一番下に辿り着く前に変なところでボールが止まってしまうことがあります。これを局所的(ローカル)な最小解(ミニマム)なのでローカルミニマムと言います。
この局所解に落ち込んでしまうと従来の計算方法では抜け出すことができません。なにせ下へ下へと向かう計算なので、隣に深い底があってもそれを見つけられないのです。そして世の中の組み合わせ問題は往々にしてこのような局所的最小解を複数持つことから、落ち込んだ時の解消方法が必要です。
解消方法にもいくつかありますが、一番シンプルで簡単なのは「初期値を複数試す」ことです。それも図で表してみましょう。
上の図のようにいくつかの落とし方を試せば、確率的に見てどれかは本当の最適解に辿り着くことになります。
応用編
このローカルミニマムという概念とその解消方法は、組み合わせ最適化問題に限らず他のことにも応用することができます。
例えば顧客の情報を管理する仕事があるとします。先輩に教わったやり方はExcelで管理することです。それが全て手入力でどうにも時間が掛かるとしましょう。そんな作業は馬鹿馬鹿しいので、テンプレートを作って入力箇所を減らす、マクロやVBAを駆使して作業時間を減らすといった改善をするかもしれません。
まさにこれこそがローカルミニマムに陥っている可能性がある行動です。真に最適な方法はExcelなんか投げ捨てて「顧客管理用のソフトウェアを購入する」ことかもしれないのです。
このローカルミニマムという袋小路は様々な事象で発生し、誰もが陥ってしまいがちな盲点です。物事のやり方に限らず、思考の方向性や、それこそ人生そのものにだってローカルミニマムは存在する可能性があります。ローカルミニマムに陥らず最適解を見つける方法、それは前述したように一度初期に立ち戻り別の方法を試してみることです。
まとめ
より良くしようと努力する姿勢は評価されるべき美点です。そういうことができる人はとても真面目で、熱心で、真剣な人です。そんな立派な人がローカルミニマムに陥ってしまうのは勿体無いとしか言いようがありません。しかしながら、ローカルミニマムはむしろそういう人こそハマってしまう罠なのです。視野狭窄に陥って貴重なリソースが無駄にならないよう、一度立ち止まって別の方法を試すゆとりを持つことが最適解に辿り着くためには必要です。