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

最適化一口話

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

「厳密さ」は人を惑わす(ビーズ問題その1)

ここは手作りアクセサリーの店。 ビーズの残りがなくなってきました。良く使うタイプなので多めに、予算 6000 円で調達します。 調達先の候補をネットショップでざっと探してみると次のような感じです。

店舗 価格(一袋あたり) 分量
A 250円 100個
B 1000円 約400個 (70g)
C 1500円 約600個 (105g)

店によって袋の大きさは様々ですが、ビーズの単価はどれも似たりよったりで、 どこで買うのでもよいかなあというところですが、 ここに、何事もきっちりとしないと気が済まない今回の主人公 M 君が登場します。 そもそも分量の「約」というのは何事だと、サンプルを取り寄せて数え始めた彼を、 誰にも止めることはできません。結果、

B店の袋には 406個、C店の袋には 610個入ってた!

そうな(これがその店が売っているすべての袋に通用すると思い込んでしまう彼の単純さはとりあえずおいておきます)。せっかく苦労して得たデータなんだし有効に使わないと意味ないっす。 と彼、最近どこかのブログで読んだ数理最適化という手法を使ってこれを解くことにしました。 A、B、C から一袋購入すると、ビーズと費用が「セットになってやってくる」。 こう考えるとこれは 「重ね合わせ」タイプ のモデルです。

f:id:optimizationTanabe:20160623002617p:plain

さて、M君、自分で苦労して得たデータを入れて解きました。 答は「C店の袋だけ4つ買う」です。 データ取りも、定式化も慣れない中あんなに苦労したのになんだか面白くない。 A,B,C 全部取り混ぜて買う、とか苦労に見合った思いもよらない答が出ればよいのになあと思いつつふと気がつくと机の上にビーズが一個転がっているのを見つけました。 どうやら B店の袋にあったのを一つ数え上げ忘れていて、B 店の袋のビーズの個数は都合 407個 だったようです。きっちりした彼のことなので、最適化のデータを 406 から 407 に変更して、数理最適化をやりなおしてみました。 するとどうでしょう、がらっと答が変わってしまいました。 沢山買っていた C 店の袋は一切無視して、「B 店の袋を6袋」という答です。 入力はわずかしか変えてないのになぜこんなことが起きるのかと彼はPCを前に首をひねっています。

M 君、自分の業務に数理最適化を積極的に役立てるのはとても素晴しいのですが、ちゃんとした予測を立てずに計算を走らせるだけでは機械が出す結果に振り回されてしまいます。最初は結果を想像しながら手を動かしてみて計算機の答を「評価」してやるべきですね。 B 店の袋と C 店の袋で1円あたりで買えるビーズの個数を計算してみましょう。最初の設定だと B 店の袋では 406個/1000円 = 0.406個/円なのに対して、C店の袋では 600個/1500円 = 0.4067個/円と僅かに多い。 じつは数理最適化がC 店の袋をすべて買うべしとしていたのは、この差に反応してのことでした。 その差がB 店の袋にビーズが一個余計に入っていると逆転されてしまうくらい僅かだったので、 B 店の袋のデータを修正すると今度は B 店の袋をすべて買う、という答になった、というわけです。 そんなに固いこと言わずにC 店の袋でもそんなに悪くないんだから派手に変える必要ないじゃないかね? それは人間の適当な(実は別の判断基準を導入している)発想というもので、 数理最適化は一旦 C 店の袋よりも B 店の袋の方がコストパフォーマンスが良いと判明し、 B 店の袋で予算を使い切れるとわかったら、C 店の袋を一つも買いません。 そうでなければ、「最適解を見つけよ」との命令に忠実でないことになってしまうから。

非常に単純なケースで説明しましたので、 何をあたりまえのことを言ってるんだと思われるかもしれませんが、 これは頭で追い切れないくらい複雑な問題についても起き得て、 時折数理最適化ユーザーを惑わすので注意が必要です。

それほどデータは変化させてないのに・・・

  • 「先月はこのポンプが動いてたけど、今月は全く動かない結果になったぞ!」
  • 「先月まで掃除ばかりしてた人が今月は掃除を全くやらなくなったぞ!」
  • 「ポートフォリオががらっと変化したぞ!」

一体どうしたんだ?といった具合。

これは多くの場合拮抗した結果(目的関数値)を出す、様相の違う答が複数存在することを示唆しています。 ビーズ問題の場合、「B店のみ買う」「C店のみ買う」、という全然違った二つの答がもたらす結果の差は、二千を超えるビーズの個数にして数個でした。 この二つの答がいわば「水面下」で争っていて、 数理最適化は僅かなデータの差で一番に来たものを拾いあげて報告するので、 結果だけ見ているこちらはびっくりさせられるわけです。

掴むのは常に1番の答だけで 2番を掴まない、 というのが数理最適化アルゴリズムの「精度の良さ」とか「厳密性」というもちろん誇るべき性能ですが、 選ぼうとする答のもたらす結果が僅差である場合、 ときに人を惑わすことがあるのは知っておいて頂いて良いことだと思います。 特にスケジューリングなどに多いのですが、実務の現場でははっきりした良し悪しがつけられない答が大量に発生するので、厳密な1番に拘らずにキーワード検索のように最適解の周辺の答 2,3 個をなんとなく表示してくれている方がよほどありがたいのになあ、と思うことも多々あります。 ただいかんせん、現在スタンダードな数理最適化アルゴリズムの多くは 「最適でないものを早い段階で削る」という動き方をして速度を稼いでいますので、 これはちょっと先のことになるかもしれません。 将来はぜひこういう複数解提案型アルゴリズムの普及に期待するとして、 「厳密すぎる」アルゴリズムに対するユーザー側には、データを変化させて沢山の答を出して目を慣らしておく、「前回の答と大きくは違わない」といった制約を入れる、目的関数を工夫してあり得る答に差をつける、といった自衛策が必要になります。このあたりはまた別の機会にお話ししましょう。

さて、次回は予算上限を変化させて、まさにM君が望んでいた「面白い答」が出るようにしてみます。