ベイズ最適化で線形計画法を解いてみた

ベイズ最適化を用いた材料調達額の最適化

材料調達計画の最適化の問題に対して、ベイズ最適化を使った手法について説明します。
PuLPを用いて線形計画法として解く手法を試されている方が大多数(実際、問題に適合していると思います。)ですが、最近はやりのベイズ最適化というものに取り組んでみました。

例題

日ごとの原材料費用、調達量のデータから原材料費用を最小に抑えるように調達タイミングを最適化するような場合を想定します。

ベイズ最適化とは

ベイズ最適化とは、一言で言えば観測点から確率的に良質な点を予測する手法です。パラメータ最適化の課題に対しては、ある入力パラメータに対して得られる出力を観測したとして、そこから次に探索すべきパラメータ(の組)を考えながら最適値を求めることができます。したがって、ユーザーが用意した格子点状のパラメータを網羅的に探索するグリッドサーチよりかなり効率的に入力パラメータを探索できます。確率的な予測を何によって行うかにはいくつか手法はありますが、本稿では割愛します。

Optunaを用いた多目的最適化

Optunaはベイズ最適化を行うためのフレームワークで、主に機械学習のハイパーパラメータの調整に良く使われています。ハイパーパラメータチューニングに使用する際は、モデルによる学習結果を出力とし、それに対するハイパーパラメータを入力として最適なハイパーパラメータを探索することになります。total_costを出力とし、各原材料の調達量を入力パラメータとして最適な発注量の組、すなわち発注計画を見つけることにOptunaを用いました。実装は以下のような記事を参考にして行いました。
https://qiita.com/pontyo4/items/0a56528988c1e9e3a65e

実装

参考資料を写経するだけで動きます。今回の問題に適用すると、trial.suggest_intで発注量の探索範囲を設定し、事前に作った関数CALCにて所与データと調達量から各原材料のコストを計算し、その計算結果のコストを最小化するようなコードになります。trial.suggest_intの第二、第三引数で入力パラメータの最小値、最大値を設定し、探索空間を定義しています。探査空間の定義法には連続値や離散値もありますが、ググればすぐに出てきます。
(例えばこんなん https://qiita.com/motoyuki1963/items/31da1d9c5f7c7290b105)

# 目的関数を設定
def objectives(trial):
    # optunaでのパラメータ探索範囲の設定 
　　# この場合はorder_min_* ~ order_max_*(*原材料名)の間で発注量
    order_A = trial.suggest_int('order_A', order_min_A, order_max_A)
    order_B = trial.suggest_int('order_B', order_min_B, order_max_B)
    ・・・
        } #原材料はA,B, ...とした
        
    # 調達計画量のリストにする
    ORDER　= [####]　
    
    # コストの計算
    total_cost = CALC(ORDER)
    
    # スコアの計算
    # デフォルトでスコアを最小化を行うようになっています。
    return  total_cost

# optunaによる最適化呼び出し
study = optuna.multi_objective.create_study()
# 最適化の実行
#n_trials で探索する繰り返し回数を設定します
study.optimize(objectives,n_trials=100)

最適化の結果

実際に今回の例題に似たようなコンペに出場した際、日毎、各材料毎の発注量を入力パラメータとしてOptunaで最適化した結果はtotal_costはPuLPで計算した結果と比較し、15％程度スコアが上がったような結果となりました。
単純な線形計画の問題を解くのにはやはりPuLPに軍配が上がりますが、コードが簡単で実行しやすいのがOptunaを用いた利点かなと思います。Optunaの方が圧倒的に汎用性が高い気がするので、これからベイズ最適化の実装を始めようとしている方の一助になればと思います。