こんにちは。
分析官の望月です。
前回の記事の続きになります。今回は数理最適化ライブラリPuLPを用いてポケモンリーグを最適化していきます。
数理モデルの定義
まずはPuLPライブラリをインポートし、数理モデルを定義します。第2引数をpulp.LpMaximizeとしていますが、今回は目的関数を定める必要はないのであくまでも仮置きしている感じです。
# ライブラリのインポート
import pulp
# 数理モデルの定義
prob = pulp.LpProblem('PokemonLeague',pulp.LpMaximize)
リストの作成
次にポケモンとトレーナーおよびその組み合わせリストを作成します。
# ポケモンのリスト
P = df_unpivot['name'].tolist()
# トレーナーのリスト
T = ['イツキ', 'キョウ', 'シバ', 'カリン', 'ワタル']
# ポケモンとトレーナーの組み合わせリスト
PT = [(p,t) for p in P for t in T]
変数の定義
次に変数を定義します。
ポケモン×トレーナーの組み合わせの数(30×5=150)だけ用意するため、pulp.LpVariableを利用して変数を1つずつ定義するのではなく、pulp.LpVariable.dictsを利用してまとめて変数を定義します。第1引数は任意の名前、第2引数はまとめて用意する変数のリスト、第3引数は変数の種別を指定します。ここでは0or1のバイナリ値”Binary”としています。
※$x_{p,t}=1$の場合はポケモン$p$をトレーナー$t$に割りあてる、$x_{p,t}=0$の場合は割りあてないということになります。
# 変数の定義
x = pulp.LpVariable.dicts('x', PT, cat='Binary')
制約式の定義
次に制約式を順に定義していきます。
①各ポケモンを1人のトレーナーに割り当てる
例えばポケモン”ドータクン”をいずれかのトレーナーに割りあてる際には
$x_{ドータクン,イツキ}, x_{ドータクン,キョウ}, …, x_{ドータクン,ワタル}$の内いずれかは1、それ以外は0となります。つまり
\begin{align}
x_{ドータクン,イツキ} + x_{ドータクン,キョウ} + … + x_{ドータクン,ワタル} = \sum_{t \in T}x_{ドータクン,t} = 1
\end{align}
が成立することになります。
ドータクン以外のポケモンにも上記の条件をあてはめたいので
\begin{align}
\sum_{t \in T}x_{p,t} = 1 \ \ \ (p \in P)
\end{align}
を制約として追加します。
# 制約①：各ポケモンを1人のトレーナーに割り当てる
for p in P:
prob += pulp.lpSum([x[p,t] for t in T]) == 1
②各トレーナーの手持ちは6匹とする
例えばトレーナー”イツキ”に6匹のポケモンを割りあてる際には
$x_{ドータクン,イツキ}, x_{ブーピッグ,イツキ}, …, x_{カイリュー,イツキ}$の内6個が1, それ以外は0となります。つまり
\begin{align}
x_{ドータクン,イツキ} + x_{ブーピッグ,イツキ} + … + x_{カイリュー,イツキ} = \sum_{p \in P}x_{p,イツキ} = 6
\end{align}
が成立することになります。
イツキ以外のトレーナーにも上記の条件をあてはめたいので、
\begin{align}
\sum_{p \in P}x_{p,t} = 6 \ \ \ (t \in T)
\end{align}
を制約として追加します。
# 制約②：各トレーナーの手持ちは6匹とする
for t in T:
prob += pulp.lpSum([x[p,t] for p in P]) == 6
③各トレーナーの同一タイプのポケモン所持は最大2匹までとする
タイプ別にポケモンをユニークカウントしてみた結果、”エスパー”, “どく”, “かくとう”, “あく”, “ドラゴン”, “ひこう”の6タイプが3匹以上いることが分かりました。そこでタイプ偏りを解決するために各トレーナーの同一タイプのポケモン所持は最大2匹までという制約を加えていきます。
エスパータイプを保持しているポケモンは”ドータクン”, “ブーピッグ”, “ヤドラン”, “ルージュラ”, “サーナイト”, “ネイティオ”の全6匹です。各トレーナー、これらのポケモンの所持は最大2匹までとしたいので、
\begin{align}
\sum_{p \in P_{psychic}}x_{p,t} \leq 2 \ \ \ (t \in T)
\end{align}
を制約として追加します。また、これらの条件は残りの5つのタイプでも当てはまるので、その分制約を追加します。
# 制約③：各トレーナーの同一タイプのポケモン所持は最大2匹までとする
#エスパータイプ保持
P_psychic = {row.name for row in df_unpivot.itertuples() if row.エスパー == 1}
for t in T:
prob += pulp.lpSum([x[p,t] for p in P_psychic]) <= 2
#どくタイプ保持
P_poison = {row.name for row in df_unpivot.itertuples() if row.どく == 1}
for t in T:
prob += pulp.lpSum([x[p,t] for p in P_poison]) <= 2
#かくとうタイプ保持
P_fighting = {row.name for row in df_unpivot.itertuples() if row.かくとう == 1}
for t in T:
prob += pulp.lpSum([x[p,t] for p in P_fighting]) <= 2
#あくタイプ保持
P_dark = {row.name for row in df_unpivot.itertuples() if row.あく == 1}
for t in T:
prob += pulp.lpSum([x[p,t] for p in P_dark]) <= 2
#ドラゴンタイプ保持
P_dragon = {row.name for row in df_unpivot.itertuples() if row.ドラゴン == 1}
for t in T:
prob += pulp.lpSum([x[p,t] for p in P_dragon]) <= 2
#ひこうタイプ保持
P_flying = {row.name for row in df_unpivot.itertuples() if row.ひこう == 1}
for t in T:
prob += pulp.lpSum([x[p,t] for p in P_flying]) <= 2
④各トレーナーにもとから持っているポケモンを少なくとも1匹付与する
前回の記事であらかじめ下記の組み合わせは崩さないことを決めていましたのでそれを定式化していきます。
| イツキ | ネイティオ |
| キョウ | クロバット |
| シバ | カイリキー |
| カリン | ブラッキー |
| ワタル | カイリュー |
例えばイツキの場合ネイティオは入れ替えたくないので
\begin{align}
x_{ネイティオ,イツキ} = 1
\end{align}
を制約として追加します。残りの4人のトレーナー分の制約も同様に追加します。
# 制約④：各トレーナーにもとから持っているポケモンを少なくとも1匹付与する
prob += pulp.lpSum(x[("ネイティオ", "イツキ")]) == 1
prob += pulp.lpSum(x[("クロバット", "キョウ")]) == 1
prob += pulp.lpSum(x[("カイリキー", "シバ")]) == 1
prob += pulp.lpSum(x[("ブラッキー", "カリン")]) == 1
prob += pulp.lpSum(x[("カイリュー", "ワタル")]) == 1
ここまでで制約式の定義は完了です。
最適化の結果
prob.solve()で定義した問題を解いて結果を確認します。
statusが”optimal”となり、新パーティーが無事構築されました。
# 定義した問題を解く
status = prob.solve()
# 最適化計算の結果
print(pulp.LpStatus[status])
result = {}
for t in T:
result[t] = [p for p in P if x[p,t].value()==1]
正しく最適化できているかTableauで確認してみます。
https://public.tableau.com/app/profile/griinc6648/viz/_16403612218530/sheet0
画面左側が最適化前のパーティー、右側が最適化後のパーティーです。入れ替えないように指定したポケモンはちゃんとそのままの状態でいつつ、同タイプは最大2匹までになっていることが確認できました。
まとめ
はじめに設定した下記2条件を満たすように各トレーナーのパーティーを再編することでポケモンリーグに対して応急処置を施すことができました。
1. 各トレーナーでタイプを満遍なく散らしたい
2. やっぱり1匹はもとから持っているポケモンを持っておきたい
気が向いたらタイプの相性や各ポケモンがもとから持っているポテンシャル（特性値）も考慮してよりポケモンリーグを強固な存在にしたいと思います。
参考書籍
Pythonではじめる数理最適化 ケーススタディでモデリングのスキルを身につけよう（オーム社）
