アーカイブ動画

最適化とはデータをもとに意思決定案を生み出す技術

NECソリューションイノベータ株式会社　吉村 元聖氏

まずは最適化とは何か。最適化とはデータをもとに意思決定案を出す技術である。AIやデータ分析と聞くと、分類や予測、可視化がキーワードとして思い浮かぶ人も多いのではないだろうか。

可視化はすでにあるデータから、人が傾向を分析する技術である。分類・予測はすでにあるデータから新しいデータを分類し、予測する技術だ。可視化や分類・予測でできることは、これから何が起きるのかという情報を提供するまで。その未来予想という情報をもとに、次のアクションの意思決定は人間が行う必要があった。

だが、最適化は膨大な選択肢の中から最適解を見つける技術であり、データをもとに意思決定自体をレコメンドしてくれる。AIが出力した意思決定案に沿ってアクションできるように、意思決定にかかる時間が短縮される。これが最適化のメリットだ。

では人間は何もしないのかというと、そうではない。機械が出した意思決定案を採用するかどうかの判断は人が行う必要がある。

「乗り換え案内アプリをイメージすると、わかりやすいと思います。乗り換え案内アプリで行き先を入力すると、乗り換え案がリコメンドされます。その案を採用して乗り換えるかどうかは人間が判断しますよね。それと同じです」（吉村氏）

例えば、ある会社ではAという商品とBという商品を生産しており、マーケット状況からAIが何個売れると予測したとする。

予測通りに生産できればよいが、現実問題として原材料の在庫や工場の稼働状況、人員などの制約がある。そこでAI予想と現実における制約を組み合わせて、良い感じの生産計画案を出力する。それが最適化だと吉村氏は語る。

「良い感じの解決案は、案件によって変わります。粗利が良くなる、純利益が高くなる、売上が上がるという案件で解決案は変わりますが、いずれも指標の良くなるものを出すのが最適化です」

「遠足のお菓子」の最適な組み合わせを解く

ではそもそも最適化問題とは何か、吉村氏は「遠足に持って行くお菓子の最適な組み合わせ」を例に説明を行った。

各お菓子の値段と満足度は図の通り。これらのお菓子からピックアップし、合計の値段が300円以内で、かつ満足度の合計がなるべく大きくなる組み合わせを見つけることが、最適化問題のイメージだ。

まず、最適化問題の簡単な定義が紹介された。最適化とは、制約条件を満たす解の中で目的関数を最大化（もしくは最小化）する解を見つけることである。

制約条件：意思決定する際に「必ず守らなければいけないルール」
目的関数：意思決定する際の「採用基準」
変数：意思決定する対象

これを先の例に当てはめると次のようになる。

最適化問題には、いくつかの分類の仕方がある。大きく分けると、変数が連続値か離散値かという分け方。連続値は小数点を含む連続した値。離散値とは小数点を含まない、整数として表現される値である。また、最適化問題では、目的関数・制約条件が線形・非線形に分類される。実案件の組み合わせ最適化問題では、この離散値を使うことがほとんどだという。

現実の問題を最適化問題として解くためのプロセスは以下となる。

1. 現実問題を最適化問題に定式化する
2. ソルバにインプットして、解を求める
3. 最適解がでてきたら、そのまま現実問題に適用して良いかどうかを検討する

実際にこのプロセスを、お菓子の例に当てはめていく。知りたいことは、「どのお菓子を持っていくか」。表の端に変数（持っていく、持っていかない）を追加する。

制約条件は、持っていくお菓子の値段の合計を300円以下にすること。値段の列と変数の列の内積の合計値で表すことができる。目的関数は持っていくお菓子の満足度。満足度の列と変数の内積の合計値である。

このように定式化できれば、ソルバを利用して最適化を解いていく。そこで使うのが「PuLP」というソルバを解くためのPythonライブラリだ。PuLPでソルバを実行すると、最適解を出力してくれる。お菓子の結果に当てはめると、最適解はチョコレート+飴+ドーナツ+キャラメルの組み合わせ（合計金額は290円。満足度が25点）。

無事に最適解は出たが、これが本当に最適化なのか、立ち止まって考えることも必要だと吉村氏は語る。

「例えば、もう少し健康に気を使った組み合わせを求めるのであれば、制約条件にカロリーを加えソルバを実行します。この例では重複を許していませんが、重複を許すのであれば、変数を0/1ではなく、整数値にすれば対応できます」

Pythonを用いて最適化問題を解く

続いては、実際にPythonを用いて最適化問題を解いていった。今回、吉村氏が複数ある最適化問題を解くために選んだPythonライブラリはPuLP。実装が比較的簡単で日本語の記事が多く、PuLPを理解すればその他のライブラリも使えるようになるからだという。

PuLPの基本的な使い方は、次の5ステップである。

１．モデルの作成
まずは問題を解くためのインスタンスを定義する。つまり、LpProblemをインスタンス化。最小化問題、最大化問題を解くモデルは次の通り。変数名はprobで表している。

２．変数を作成
LpVariable（変数名、Lowbound=最小値、upBound=最大値、cat=変数の種類）という4つのパラメータを指定。種類は連続変数なのか、2値変数、整数変数、連続離散値などで変わってくる。catはデフォルト値として連続変数が入ってくる。最小値0～10まで。整数変数のときは、integerを指定する。

３．目的関数の設定
1で「prob」という名前で作成したオブジェクトに対して、+=で目的関数を指摘する。

４．制約条件の追加
制約条件は1で作成したオブジェクト「prob +=目的関数」というように、目的関数と似た定義の仕方となる。その違いは、+=から右は条件式にする必要があること。

５．すべて設定できれば最適化問題を解く
最適化問題を解く場合は、solveという関数を使用。printという関数で最適地を確認できる。最適解の中身を確認することもできる。

続いて、簡単な問題を用いた実装例が紹介された。

表の見方は、次のようになる。例えばスタンドカラーシャツを1着作る場合は、45のアルパカと10のポリエステルが消費される。一番下の在庫とは各材料の在庫である。

「この生産計画問題をPythonで実装します。今回はPythonのPuLPを使うので、定式化は次のような形で表しました」

変数：各商品を何個生産するか
目的関数：売上の最大化
制約条件：生産で使用する原料

PuLPの実行環境として使ったのは、Jupiter NotebooK。使い勝手はPythonのインタラクティブモードに近い。そして外部ライブラリであるPuLPをJupiter NotebooKにインストール。解析したデータを見やすいようPandasもインストールする。

まずはproductsというデータフレームで、各商品の名前と商品価格のファイルを読み込む。次にmaterialsというデータフレームで、各商品の生産に消費する材料の数のファイルを読み込む。

さらにstockという在庫情報のファイルを読み込む。ここまでが最適化問題を解くための前準備ができたところで、最適化オブジェクトを作成する。

次に変数を定義。今回は商品の種類ごとに定義が異なるので、各商品に対応する変数を作成する。LpVariableというクラスをインスタンス化する。生産個数にマイナスはないので、最小値は0とし、上限値を設け、変数は連続値ではなく整数値を指定している。

続いて目的関数を設定。今回の目的関数は売上なので、商品価格×生産数（内積）の合計となる。さらに材料ごとに制約条件を定義していく。

すべて設定できたら、最適化問題を実行するのだが、その前に正しく目的関数や制約条件が設定されているかどうかを、print(prob)で確認する。

よければソルブを実行。今回の最適化問題では、次のような解が提供された。

この衣服の生産問題に、生産する商品の個数はAIによる需要予測を超えないという制約条件を付け加えた吉村氏。その理由をこう語る。

「生産すればするほど全部売れる前提でしたが、現実にはそんなことはないからです」

従って、定式化は次のようになる。

需要予測が入った商品情報ファイルを読み込む。そして、需要予測の値を上限として指定。先と同様、ソルブを実行する。その結果は以下のようになる。

最後に吉村氏は以下のように語り、セッションを締めた。

「実際に解決すべき問題は制約条件も複雑で、データ数もかなり多くなります。基本的には制約条件を加え、目的関数をチューニングしていくことで、最適解を見つけていきます。最適解は、AIによる予測の次のステップとして有用です。PuLPを用いれば最適化問題を解くことができます。ぜひ、関心を持った方は試してみてください」

丁寧な吉村氏の解説は、最適化問題の基礎を知りたいエンジニアにとって、非常に有意義な時間になったのではないだろうか。

質問が続々と寄せられたQ&Aタイム

講演終了後はQ&Aタイム。本イベントの参加者から多くの質問が吉村氏に寄せられた。

Q．定式化する際、普段から数式に触れていないと難しいと思うが、社内メンバーに教えるときはどのような工夫をしているのか

吉村：ここは一番難しいところですが、私は完璧に数式に落とし込む必要はないと考えています。ortools Pythonに落とし込める範囲で定式化すれば良いと思います。

Q．遠足のお菓子の問題で、目的関数が満足度最大化かつ所有個数最小化などとしたい場合
・正規化は各関数で0-1などにすればいいのか
・どちらかの関数に-1を乗じた和算を目的関数としてよいのか

吉村：お菓子の数の合計なので、例えば、変数として2種類設定すれば良いと思います。ですが、目的関数が複数ある場合は、PuLPでは解けません。

Q．ソルバで出てきた解が本当に最適解なのか、どのようにチェックすればいいか

吉村：例えばExcelのソルバの機能など、別のソルバを使うと良いと思います。

Q．機器の運転時間・運転回数の最適化をPythonで表現できるか

吉村：目的関数や制約条件が解れば、Pythonで表現できますが、データ次第だと思います。

Q．目的関数に内積などの線形和だけでなく、任意の非線形関数を設定することもできるか

吉村：PuLPでは少なくともできません。別のライブラリが必要です。

Q．最適解が求まらない場合もある？

吉村：明らかに矛盾している二つの制約条件を定義した場合などは、最適解が存在しないことがあります。

Q．購買データから購買確率の高い顧客をAIで予測した後、売上を最大化する顧客を抽出する手段として最適化問題は適用できるか。その場合、制約条件はどうなるのか

吉村：購買確率の高い顧客をピックアップすると、そのコストが制約条件になります。

NECソリューションイノベータ株式会社
https://www.nec-solutioninnovators.co.jp/

NECソリューションイノベータ株式会社の採用情報
https://www.nec-solutioninnovators.co.jp/career/