読者です 読者をやめる 読者になる 読者になる

最適化一口話

仕事として数理最適化を実践している立場から、その中身や可能性について概説しております。

あれもこれも良くしたいのだけど..(2:重み調整に頼らない方法)

前回は数理最適化を使って、利便性と安全性を共に追求する地点を探そうとして目的関数を

(利便性重み)×(地点の利便性) + (安全性重み)×(地点の安全性)

という「重み付き平均」にしたは良いのですが、 候補になる土地の形が直線的なときにちゃんと「按分」された結果が出ないという話でした。

f:id:optimizationTanabe:20160714102055p:plain

重みの按分は上の図の青い点線の傾きに反映していて、 傾きが緩ければ A 地点が最適解(左の図)、きつければ B 地点が最適解(一番右の図)。 問題は利便性重みと安全性重みが同じ(真ん中の図)ケースで、 A 地点、B 地点とその中間地点がすべて「最適解」となってユーザーを襲います。

プログラム開発作法の文脈での数の数え方は「1 つ、2 つ、沢山」。未開の民族の言語みたいですが、要するに 3つ以上あるならば汎用化を意識しろという意味です。 実務的な数理最適化における最適解の数は「まれに 1 つ、普通は沢山、じつは無限個」。 「最適(最も良いもの)」という言葉の印象から我々は無意識に「最適解」は唯一だと思っているフシがありますが、この例に見るように最適解が一つに定まらないケースが結構あって、 最も基本的かつ強力な数理最適化である線形計画法でも出現してしまうのです。 上で無数の最適解が「襲う」と言いましたが、 同等の無数の解がある、ということがユーザーに「見える」わけではなくて、数理最適化ソルバーの都合で無数の最適解があってもそのうちのどれか一個が出てくるだけ。 さて、そんなときにユーザーとの対話を通じて無数の最適解候補を具体的に出力させる常套手段を紹介しましょう。

適当に軸になる目的関数の尺度(仮に安全性)を決め、 まず安全性だけで最適化、結果として得られる A 地点が持つ安全性の値("1" とします)をどこまで折り合えるか(例えば 0.8 とします)を考え、

安全性が 0.8 を下回らない中で、可能な限り利便性を最大化する

という問題を解きます。そうすると、結果として許される領域は小さくなって、 安全性が 0.8 を下回らない範囲で利便性を最大化した「地点 C」が最適解として出ます。

f:id:optimizationTanabe:20160714102120p:plain

あとは同様で、この "0.8" という値を変化させてこれを繰り返せば、 最適解のバリエーションが一つずつ出力されてゆきます。

f:id:optimizationTanabe:20160714102136p:plain

線形計画問題の答が按分された答になってくれないのは「シーソー」がわずかな重さの差でも必ずどちらがが上がり切ってしまうことに似ています。目的関数の重みは両側に載せる重しのようなものなのでここをいかに按分調整しても(完全に釣り合わせることができない限り)結果は二通りしか出てきません。

f:id:optimizationTanabe:20160714102211p:plain

ここで紹介した、制約を追加して探りを入れる、 という方法はシーソーの片側を手で抑えて、力を加減することに相当します。 こうすればシーソーを自然に任せた場合とは本質的に違う結果を見ることができる、というわけです。少々面倒ですがいろいろな状況で使うことができる汎用性が高い方法ですから、二つ以上の目的関数があるとき、重み調整の代替手段としてぜひご検討ください。