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

最適化一口話

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

あれもこれも良くしたいのだけど..(1:「重み係数」の怪)

エネルギー最適化における、CO2排出量とエネルギーコスト。 積み付けにおける、作業効率とスペース効率。 はたまた生産計画問題における在庫切れリスクと商品廃棄コスト、 そうかと思うとポートフォリオのリスクとリターン、といった具合に 実務的な数理最適化モデルは「あちらが立てばこちらが立たず」という状況(トレードオフ)だらけで、「あなたの満たしたい要件はこうすればすべて OK 」という結果が出ることはほぼありえない、と言って良い状況です。

我々:    「こういう結果になりました」
お客さま:「おおっ、これは思いもよらなかったよ、すばらしい!」

とかいう絵に描いたような展開になることはそうそうなくて、

我々:    「こういう結果になりました」
お客さま:「やっぱ、そうだよねえ。。うーん。」

という感じが普通です。 まあすべて良くなる方向が見えているのならば、 別に我々に頼んで最適化するまでもない、ということかもしれませんね。

今回はトレードオフのあるケースにおける定式のテクニックについて述べます。「そんなん簡単。適当に重み付けして目的関数を足し算すればよいんじゃないの?」というのが通り相場です。然り。我々専門家もこういう定式化を自ら提案したりします。ただ、注意は必要で、結果は必ずしも「重み」に従ってくれない場合もあるよという、ちょっと怖い話をしましょう。 例で説明します。次のような形の工場用地を持っている会社があったとして、 倉庫をどこに建てるかを決めたい、とします。

f:id:optimizationTanabe:20160706142038p:plain

工場は右の方にあるので、倉庫は右に建てるほど利便性は高い。 ただ、図の下は海岸に近くて津波とかが心配。 将来のことも考えると図の上の方に建てる方が安全です。 そんなわけで可能な限り安全で利便性の高い場所を適当な折り合いで決定したい。 こんなとき数理最適化の目的関数は、例によって重み付き足し算になります。

目的関数(最大化): (利便性重み)×(地点の利便性) + (安全性重み)×(地点の安全性)

出てくる答は大体予想が付きます。 安全性最高のA地点と、利便性最高のB地点の間、黄色い境界線上のどこかですよね。 なぜなら C 地点のような場所は中途半端で同じ利便性でより安全な場所、 あるいは同じ安全性でより利便性の高い場所が存在するので最適解にはなり得ない。 利便性/安全性どちらかの意味で「最適性」をつきつめて行くと境界になってしまうわけです。

さて、百聞は一見に如かず。利便性と安全性の重みが足して 1 になるように 振ってみて、数理最適化によって導かれる場所がどうなるか見てみましょう (数式表現が気になる方へ、用地の境界は円弧で、x 座標、y 座標で地点を現わすとします。 4分の1円を実行可能領域として適当な線形関数を最大化します)。

f:id:optimizationTanabe:20160706142112p:plain

利便性の重みが 0 の場合には最も安全な A 地点が選択され、 利便性の重みが増えるにつれて、境界上を最適地点が動いてゆき B 地点に至っています。 全くもって期待通りで、面白みがない結果ですが、 じつはこれ、重みの設定に従って結果がちゃんと動いてくれる、 かなり幸運なケースなのです。

ここで、次のように用地の形が三角形の場合について同じ問題を解いてみます。

f:id:optimizationTanabe:20160706142143p:plain

最適な場所の所在についての考察は丸い場合と全く一緒。 やはり境界上にいろんな度合いで按分した答があります。 同じ目的関数でやってみましょう。どういう結果になるでしょうか。

f:id:optimizationTanabe:20160706142220p:plain

どうでしょう。 まとめて眺めると、安全性の重みがちょっとでも大きければ A 地点、 利便性の重みがちょっとでも大きければ B 地点、ということなのだなとわかりますが、 重みを触っている当事者になってみるとこの応答は「不気味」の一言。 ちょっとつついても全く反応がない。と思ったら、 「ばしゃ!」とばかりいきなり跳ねる、魚みたいです。じつは ビーズをどっちの店で買ったらよいか問題 で起きていたのも同じ現象でした。

これはいったいどうしたわけなのか? 実はこの問題、数理最適化ソルバーを持ち出さずとも結果の見当は付きます。 図をそのまま、x-y 平面だとしますと、 この場合の最適化とは三角形の領域内の点で、 その点を通る、ある直線のy軸の交点(y切片) を最大にするものを見つけることに相当しています。 その「直線」は目的関数(の等高線の一つ)になっていて、 傾きは安全性と利便性の重みの相対的な大きさから決まります。 安全性の重みが大きければ傾きは緩いので A 地点(左の図)、 利便性の重みが大きければ傾きはきついので、B 地点(右の図)がそれぞれ答になります。

f:id:optimizationTanabe:20160706142254p:plain

安全性と利便性の傾きが丁度同じ場合には、 境界のどの点を取っても目的関数は同じになるので、 じつは答は一つに定まりません。言ってみれば境界上が全部答で、上の表では代表として、中点が出ているだけです。 こういうときにどれを出すかは数理最適化アルゴリズムの個性が出るところで、 「民主的に」中点を出すのは私がこの問題を解くのに用いた「内点法」という数理最適化アルゴリズムの特徴です。

ここでは重みつき按分で目的関数を設定しても出てくるのは A 地点とか B 地点という極端な結果の「二択」になってしまう例をご紹介しました。問題の構造に依りますが、一般に按分重みに対して結果は滑らかに反応するとは限らず、バランスの取れた解が出てこない場合もあること、どうかご注意ください。 この場合には結果のありかを目で「見る」ことができたのでそうと気づくことができましたが、 実務的な応用だと規模が大きくて複雑ですからどういう答が出るかというのはわからないのが普通です。極端な解が出てきていることにすら気づかないという危険だってあります。

次回は「重み按分」よりも、確実に多様な解を出す方法をご紹介しましょう。