2.3K Views
May 31, 24
スライド概要
BPStudy#201〜数理最適化問題をAIに解かせてみよう
「 Pythonで学ぶ数理最適化による問題解決入門」の 最適化問題をAIに解かせてみた (株)ビープラウド 斎藤 努 BPStudy#201 BeProudのサービス紹介 connpass PyQ IT エンジニアをつなぐ 勉強会支援プラットフォーム 1 Python独学プラットフォーム 技術書 冊分の価格ではじめる TRACERY システム開発のためのドキュメントサービス お前誰よ 2024年現在、株式会社ビープラウド、トヨタ自動車株式会社に勤務 数理最適化案件などを担当 技術士(情報工学) 概要 AI 簡単な最適化問題を が解けるか試してみました。 ChatGPT3.5 ChatGPT4o OptiMUS 最適化問題の解き方を学ぶ書籍の紹介 最適化問題 1200g、バターは900gしか クッキーとケーキを作るのに、次のように薄力粉とバターを使います。薄力粉は ありません。クッキーとケーキの合計重量を最大化するには、それぞれ何個作ればよいでしょうか? 1 110gで、1gあたり薄力粉0.3gとバター0.3gが必要 ケーキ1個は200gで、1gあたり薄力粉0.4gとバター0.2gが必要 ※「Pythonで学ぶ数理最適化による問題解決入門」5章より クッキー 個は 書籍のコード
Pythonでモデル化しました。2変数2制約条件の簡単なモデルです。 書籍では、次のように m = Model() v = m.add_var("v", var_type="I") # クッキーの個数 w = m.add_var("w", var_type="I") # ケーキの個数 m.objective = maximize(110 * v + 200 * w) m += 0.3 * 110 * v + 0.4 * 200 * w <= 1200 m += 0.3 * 110 * v + 0.2 * 200 * w <= 900 20個、ケーキ6個の3400gになります。 これを解くと最適解は、クッキー ChatGPT3.5 ChatGPT3.5でやってみます。 最初に、
残念。不正解です。 クッキーとケーキの組み合わせを求めないといけないのに、クッキーの最大個数を求めて決め打ちし ている ケーキを作るのにバターを使っていない 3回繰り返すと毎回異なる結果になりましたが、いずれも不正解でした。 ChatGPT4o(解を聞く) ChatGPT4oでやってみます。 次に、
手順がよくなりましたが、こちらも不正解です。
連立方程式を解いて、正しい実数解を得ている しかし、実数解を切り捨てて整数にしているため正しくない 重量の計算を実数解からしているため、整数解と対応していない ChatGPT4o(Pythonのコードを聞く) 今回の問題は、数理最適化という手法を使って解くことができます。 数理最適化のモデルは数理最適化ソル ChatGPTではソルバーの実行まではしてくれません。 ここでは、ソルバーの実行が可能 バーで解きますが、 Pythonのコードの作成を依頼してみました。下記は何度か繰り返した結果です。 な
ほぼ正解です。 変数は個数なので、連続変数(Continuous)ではなく整数変数(Integer)にすると正解 になります。 OptiMUS AI OptiMUSというものがあります。 OptiMUSは、下記から使えます。 https://optimus-solver.vercel.app/ なお、OptiMUSはスタンフォード大の先生が試験的に公開しているようです。 紹介動画 https://www.youtube.com/watch?v=_vN3pwB-PKI 数理最適化に特化した として、 Step1:問題の入力 最初に問題を入力します。英語のサイトですが、試しに日本語のまま入れています。
Analyzeボタンを押して次に進みます。 Step2:パラメーターの抽出 英語に変換されて、パラメーターの抽出が行われました。抽出されたパラメーターは表になっています。
英語の文章を日本語に翻訳してみます。翻訳しやすいように、表現を変えています。 英語 To produce cookies and cakes, we have the following quantities of flour and butter: $F$ grams of flour and $B$ grams of butter. How many cookies and cakes can be produced to maximize the total weight of the baked goods? One cookie weighs $Wc$ grams and requires $Fc$ grams of flour and $Bc$ grams of butter per gram. One cake weighs $Wk$ grams and requires $Fk$ grams of flour and $Bk$ grams of butter per gram. 日本語訳 クッキーとケーキを作るために、小麦粉とバターを以下の量用意する: $F$グラムの小麦粉と$B$グラムの バターがある。焼き菓子の総重量を最大にするために、クッキーとケーキを何個製造できるか?
1 $Wc$グラムで、1グラムあたり$Fc$グラムの小麦粉と$Bc$グラムのバターが必 クッキー 個の重さは 要である。 1 $Wk$グラムで、1グラムあたり小麦粉$Fk$グラムとバター$Bk$グラムが必要であ ケーキ 個の重さは る。 きちんと元の文章通りの意味になっています。今回は、日本語で入力しても問題ありませんでした。 必要な パラメーターも認識されています。 Nextボタンを押して次に進みます。 Step3-1: 目的関数と制約条件 英語の問題説明から、目的関数や制約条件として文章を抜き出します。 Extract Constraints and Objectiveボタンを押します。 Step3-2: 目的関数と制約条件 目的関数と制約条件の左側に、英語の文章が抽出されました(赤枠部分)。
制約条件が多いですが、何も考えずにFormulate Allボタンを押します。 Step3-3: 目的関数と制約条件 目的関数と制約条件の右側に、定式化ができました(赤枠部分) 。
エラーも出ずに順調に進んでいます。 下にスクロールしましょう。 Step3-3: 目的関数と制約条件 一番下に変数も抽出されています。変数は、目的関数と制約条件から、パラメーター以外が抽出されている ようです。
何も考えずにTo Codingを押して先に進みます。 Step4-1: コード作成 Pythonのコードを作成します。 定式化から
Code Allを押します。 Step4-2: コード作成 プログラムが生成されました!
下にスクロールします。 Step4-3: コード作成 それなりにコードができています。確認は後回しにして先にすすみましょう。
To Testingを押します。 Step5-1: データ処理 おっと、その前にデータ処理が必要なようです。
1 Select Dataというボタンが つしかないので、押してみます。 Step5-2: データ処理 どうやら、データはファイルとして作成する必要があり、作成後にサーバーにアップロードしないといけな いようです。
ここでも何も考えずに、Download Dummy Exampleでファイルをダウンロードし、そのままファイルを選 択で同じファイルをアップロードします。 Step5-3: データ処理 OKのようです。 Validと表示されました。形式は
Nextを押して次に進みます。 Step6-1: 実行して確認 最初に問題を入力してから、ボタンしか押していませんが、どうやら完成したようです。
Run Codeを押して実行してみましょう。 Step6-2: 実行して確認 エラーになりました。未定義の変数があるようです。
コードの修正 115行ありました。このコードを確認して修正しました。 修正したコードが以下になります。 プログラムは import json import gurobipy as gp # import numpy as np with open("tmpData/data.json", "r") as f: data = json.load(f) Bk = data["Bk"] Fk = data["Fk"] Wk = data["Wk"] Fc = data["Fc"] F = data["F"] B = data["B"] Wc = data["Wc"] Bc = data["Bc"] FlourPerCookie = Wc * Fc ButterPerCookie = Wc * Bc FlourPerCake = Wk * Fk ButterPerCake = Wk * Bk # Define model model = gp.Model("model") # ====== Define variables ======
# FlourPerCookie = model.addVar(vtype=gp.GRB.CONTINUOUS,
name="FlourPerCookie")
# FlourPerCake = model.addVar(vtype=gp.GRB.CONTINUOUS,
name="FlourPerCake")
NumberOfCookies = model.addVar(vtype=gp.GRB.INTEGER,
name="NumberOfCookies")
# ButterPerCake = model.addVar(vtype=gp.GRB.CONTINUOUS,
name="ButterPerCake")
NumberOfCakes = model.addVar(vtype=gp.GRB.INTEGER, name="NumberOfCakes")
# ButterPerCookie = model.addVar(vtype=gp.GRB.CONTINUOUS,
name="ButterPerCookie")
# WeightOfCake = model.addVar(vtype=gp.GRB.CONTINUOUS,
name="WeightOfCake")
# ====== Define constraints ======
# Add constraint: total weight of cookies produced must be non-negative
# model.addConstr(NumberOfCookies * Wc >= 0, name="non_negative_weight")
# Add non-negativity constraint for the weight of cakes produced
# model.addConstr(NumberOfCakes >= 0, name="non_negative_cakes")
# Total flour usage constraint
model.addConstr(
FlourPerCookie * NumberOfCookies + FlourPerCake * NumberOfCakes <= F,
name="flour_usage",
)
# Add butter usage constraint
model.addConstr(
ButterPerCookie * NumberOfCookies + ButterPerCake * NumberOfCakes <=
B,
name="butter_usage",
)
# # Add constraint for the flour required per cookie
# Fc = 0.3 # Flour required per gram for cookies
# Wc = 110 # Weight of one cookie in grams
# model.addConstr(FlourPerCookie == Fc * Wc, name="flour_per_cookie")
# Define butter required per gram for cookies
# Bc = 0.3
# Add a constraint for butter per cookie
# WeightOfOneCookie = model.addVar(vtype=gp.GRB.CONTINUOUS,
name="WeightOfOneCookie")
# ButterPerCookie = Bc * WeightOfOneCookie
# model.addConstr(ButterPerCookie == Bc * WeightOfOneCookie,
name="butter_per_cookie")
# Add flour required for producing one cake constraint
# FlourPerCake = model.addVar(vtype=gp.GRB.CONTINUOUS,
name="FlourPerCake")
# model.addConstr(
#
FlourPerCake == FlourRequiredPerGramForCakes * WeightOfOneCake,
name="flour_per_cake_constraint" # ) # Add butter usage constraint # Bk = 0.2 # ButterPerCake = model.addVar(vtype=gp.GRB.CONTINUOUS, name="ButterPerCake") # WeightOfCake = model.addVar(vtype=gp.GRB.CONTINUOUS, name="WeightOfCake") # model.addConstr(ButterPerCake == Bk * WeightOfCake, name="butter_per_cake_constraint") # Add constraint for the total weight of the cookie # model.addConstr(FlourPerCookie + ButterPerCookie == Wc, name="cookie_weight") # # Add constraint: Total weight of one cake should be equal to the given weight Wk # model.addConstr(WeightOfCake == Wk, name="weight_of_one_cake") # ====== Define objective ====== # Set objective # model.setObjective( # NumberOfCakes * WeightOfOneCake + NumberOfCookies * WeightOfOneCookie, gp.GRB.MAXIMIZE # ) model.setObjective(NumberOfCakes * Wk + NumberOfCookies * Wc, gp.GRB.MAXIMIZE) # Optimize model model.optimize() # Get model status status = model.status # Get solver information solving_info = {} if status == gp.GRB.OPTIMAL: solving_info["status"] = model.status solving_info["objective_value"] = model.objVal solving_info["variables"] = [ { "symbol": var.VarName, "value": var.X, } for var in model.getVars() ] solving_info["runtime"] = model.Runtime solving_info["iteration_count"] = model.IterCount
# Get objective value
obj_val = model.objVal
パラメーターファイル
{"Bk": 0.2, "Fk": 0.4, "Wk": 200, "Fc": 0.3, "F": 1200, "B": 900, "Wc":
110, "Bc": 0.3}
Webサイトで、上記のコードになるように頑張れば、GUROBIで実行されて下記のように結果が表示されま
す。
Run Successful!
-----Objective Value: 3400.0000
Runtime: 0.0024s
Iteration Count: 3
-----Variables:
NumberOfCookies: 20.0000
NumberOfCakes: 6.0000
書籍と同じ結果になりました!やったね!
さて、私はどのくらいコードを修正したのでしょうか? 差分が下記になります。
9 モデルの 割ぐらい修正しています。 ほぼ作り直しですね。 悪いところとよい所
ダメだったところを箇条書きにしてみました。 定数の値が、問題文の値とまったく違う アップロードするファイルの中身は自分で正しい値にしないといけない ファイルから読み込んでいるのに、コードの途中で定数を書き換えている 2 7 不要な変数が多い( つでよいのに つもある) 定数から計算される定数を変数にしている 扱えるものが、定数、変数、目的関数、制約条件しかないため、中間定数を扱えない 2 8 不要な制約条件が多い( つでよいのに つもある) 1 2 不要でない制約条件も 次式でよいのに 次式になっている 不要でない制約条件で、未定義の定数を使っている 目的関数で、未定義の定数を使っている コードに多数の修正が必要でしたが、よかったところもたくさんあります。 ステップバイステップで構築していけるので、こまめに修正して精度を上げやすい 問題文を日本語で入力したが、きちんと正しい英語になった CookieとCakeから1文字使って定数(Fc, Fkなど)を作成しているが、CとKで被ってない 不要でない変数は、修正せずにそのまま使えた 間違っていても、ニュアンスは正しそうだった 一言でまとめると、使うのはまだまだ難しそうですが、可能性を感じました。 ローカルで実行したい人へ GUROBIを使わずにローカルで実行したい場合は、pip install pulp mypulpとし さきほどのコードを て、以下の修正をすると実行できるようになります。 インポートするライブラリを次のように変更してください # import gurobipy as gp import mypulp as gp 最後に、次のように結果出力を追加してください print(solving_info) AI 生成 で最適化問題は解けるか ChatGPT4oがあと一歩というところでした。プロンプトを工夫した 今回は、簡単な問題で試してみました。 りステップバイステップだと正解がでる可能性も感じました。 AI 生成AIで数理最適化を解かせるには、数理最適化の知識も持っていた方がよいでしょう。 生成 は間違うこともあります。よく知らないで使っていると、どこが間違っているかわかりにくいです。
最適化問題の解き方を学ぶ書籍の紹介 今回の数理モデルは、下記になります。 変数: 整数変数v:クッキーの個数 整数変数w:ケーキの個数 目的関数:110 * v + 200 * w 制約条件: → 最大化 0.3 * 110 * v + 0.4 * 200 * w <= 1200(薄力粉) 0.3 * 110 * v + 0.2 * 200 * w <= 900(バター) このような数理モデルを作成するのは練習が必要になります。 下記の書籍では、いろいろな数理モデル作成 の学習ができます。 Pythonで学ぶ数理最適化による問題解決入門 https://www.shoeisha.co.jp/book/detail/9784798180236 また、書籍と同じ内容をPyQで学習することもできます。 https://prtimes.jp/main/html/rd/p/000000018.000025386.html 自分で数理モデルを作成できるようになると、いろいろな問題を解けるようになるので、ぜひ、チャレンジ してみましょう。