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

最適化一口話

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

最適化で何が実現できるのか(2)

最適化でいろいろやった結果何が実現できているのか、という話の続きです。 どんどん行きましょう。

実行可能性チェックによる安心感

数理最適化という手法のメリットの一つに、出た結果は少なくとも制約式を満たしている、 ということが挙げられます。 実務的に複雑で重要な意思決定であるほど、それを計算機にさせるということには考えも及ばず、 本来は単純作業であるはずの制約式のチェックも含め、まるごと人が請け負うことになっている現場も数多くあります。 そんなときに数理最適化を導入してまず喜んで頂けるのは「最適かどうかはわからないけど、 とにかく実行可能をチェックした結果が出る」というポイントだったりします。

もっともらしい推測

前回から文章ばかりが続いていますので、ここではちょっと例を出しましょう。 次は 8時から18時まで操業している工場を出入りした人数です。

f:id:optimizationTanabe:20160729084305p:plain

工場から出た人数のうち、青いところがわからないので、 推測するという課題を解いてみます。 負の数や小数以外ならば何を入れてもありな気がしますが、 できるだけもっともらしくしたい。 方法の一つとして隣り合った前後でそんなに人数は急激に変化しないように、 すなわち青い部分が前後の時間帯の平均に近くなるように、 適当に数字を埋める、という手を思いつきました(どうやってやるのか気になる方へ:数理最適化でももちろんできますが、一次方程式を解けばできます)。 結果は次のようになります。

f:id:optimizationTanabe:20160729084349p:plain

グラフはこんな感じ。

f:id:optimizationTanabe:20160729084427p:plain

確かになんとなくもっともらしいのですが、この方法には欠点があります。 入った人数の合計が 474人なのに、 出ている人数の合計が 518人でつじつまが合っていません。 差の 44人を解消するにはどうすればよいでしょう。いくら推測とはいえ恣意的に手でいじるのは気が引ける。 こういう場合、数理最適化がもっと良い方法を提供します。 それは数字が従う事実を「制約」として組み込んでしまうのです。 この場合では工場のオープンとクローズ時の人数はゼロで、 工場に入った人は必ず出てゆき、消滅したり増えたりしない(「保存」)。 もっと細かく言うと例えば15時台に入った人はそれ以降の時刻に出てゆく、 時間を遡って13時台に出ることはありません。 細かくなるので述べませんが、この制約は 「保存」タイプ の数理最適化です。 この制約を満たしながら、人数が前後の時刻の平均に近いようにした結果が次(推測2)です。

f:id:optimizationTanabe:20160729084526p:plain

どうでしょう。確かに合計がちゃんと揃っています。 グラフで比較してみましょう。

f:id:optimizationTanabe:20160729145519p:plain

データが不足している状況でスタンダードな回帰など普通の統計的予測モデルを作ろうとしているとき、あまりに自由度が高く汎化性能の低いモデルができてしまう場合があります。 そんなときに有効なのが、例えば回帰だったら回帰係数に制約を入れるなど「モデルに構造を入れる」方法です。この例では人数の保存を表現する制約を入れたわけです。 数理最適化は追加する制約の自由度がかなり高く、このアプローチには有用な解析手法です。 得られる情報が増えると、予測の確からしさを増やすことができることもこのアプローチのメリットです。例えばこの工場のケースでは「工場における一人の平均滞在時間」が手に入ったと考えると、制約はもっと詳細化できて予測はより精緻になりますね。

また次回。この話題をもうすこし続けます。