ほとんどパラメータを設定せずに遺伝的アルゴリズムによる最適化が可能な Pythonパッケージvcoptを試用してみました． また，例題として一時期流行った「サイゼリヤで1000円あれば最大何kcal摂れるのか」 問題を今更ですが遺伝的アルゴリズムで解いてみました．
今回のコードはgithubにjupyter notebook形式で置いてあります． github.com
0. 使用環境
- Windows 10
- Python3.7.6 (Anaconda)
1. vcoptの導入
- pipでvcoptをインストールできます．
pip install vcopt - アップデートする場合は以下のコマンドだそうです．
pip install -U vcopt
2. vcoptの基本的な使い方 (連続値のパラメータの最適化)
- vcoptのチュートリアルではRastrigin関数が取り上げられていましたが，
ここではRosenbrock関数の最小値を求めてみます．
Rosenbrock function
変数の範囲はで，最適解は
です．
Rosenbrock関数は変数間の依存性があり、最急降下法などの導関数を用いるアルゴリズムでは収束が遅くなるという特徴があります．この問題を遺伝的アルゴリズムで解いてみます．
# 目的関数(Rosenbrock)の定義 def rosenbrock(x): k=0 for i in range(len(x)-1): k += 100 * (x[i+1] - x[i]**2)**2 + (1-x[i])**2 return k # 変数の範囲 n = 5 # 次元 param_range = [[-5.12, 5.12] for _ in range(n)] print(param_range) # [[-5.12, 5.12], [-5.12, 5.12], [-5.12, 5.12], [-5.12, 5.12], [-5.12, 5.12]]
# Rosenbrock関数の可視化 import matplotlib.pyplot as plt from mpl_toolkits.mplot3d import Axes3D import numpy as np # 格子データの作成 x = [i/100*10.24-5.12 for i in range(100+1)] y = np.zeros([len(x),len(x)]) for r in range(len(x)): for c in range(len(x)): y[r, c] = rosenbrock([x[r], x[c]]) X1, X2 = np.meshgrid(x, x) # 3Dプロットで表示 fig = plt.figure() ax = fig.add_subplot(111, projection='3d') surf = ax.plot_surface(X1, X2, y, cmap="plasma", facecolor="w") fig.colorbar(surf) ax.view_init(elev=45, azim=30) ax.set_title('Rosenbrock function') fig.show()
# vcoptの最適化を実行 from vcopt import vcopt param, score = vcopt().rcGA(param_range, # 変数の範囲 rosenbrock, # 目的関数 -9999, # 目標値 show_pool_func='print',# 表示オプション )
___________________ info ___________________
para_range : n=5
score_func : <class 'function'>
aim : -9999.0
show_pool_func : 'print'
seed : None
pool_num : 50
max_gen : None
core_num : 1 (*vcopt, vc-grendel)
___________________ start __________________
Scoring first gen 50/50
gen=0, best_score=36317.4971, mean_score=154287.5313, mean_gap=164286.5313, time=0.3
gen=50, best_score=15037.9459, mean_score=100169.0721, mean_gap=110168.0721, time=0.3
gen=100, best_score=7684.9472, mean_score=60821.6427, mean_gap=70820.6427, time=0.4
(中略)
gen=28450, best_score=0.2982, mean_score=0.4468, mean_gap=9999.4468, time=7.5
__________________ results _________________
para : [0.92675764 0.85854066 0.73998302 0.54789356 0.3002722 ]
score : 0.29824238001062775
____________________ end ___________________
遺伝的アルゴリズムは近似解法であるため，score=0の厳密解ではなく正解値0に近い近似解が得られています． 何度か回してみたのですが，Rosenbrock問題の場合は初期値とシードによって結果がかなりブレる傾向がありそうです．
3. 離散値最適化の例
- 離散最適化の例題として，サイゼリヤメニューの中から1000円以内で最大カロリー摂取できる組み合わせを探す、「サイゼリヤで1000円あれば最大何kcal摂れるのか」という問題を，vcoptを使って遺伝的アルゴリズムで解いてみます．
- メニューは以下から取得します．何度かメニューが更新されているようだったので，先人達と同じ結果を得られるよう2019/5/10のdbを用いました．
saizeriya.db
# SQLiteDBの読み込み import sqlite3 import pandas as pd from contextlib import closing dbname = 'saizeriya_20190510.db' with closing(sqlite3.connect(dbname)) as conn: select_sql = 'SELECT * FROM menu' menu = pd.read_sql_query(select_sql, conn) menu.head()
| id | name | category | type | price | calorie | salt | |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 彩りガーデンサラダ | sidedish | salad | 299 | 130 | 1.1 |
| 1 | 2 | 小エビのサラダ | sidedish | salad | 349 | 115 | 1.3 |
| 2 | 3 | やわらかチキンのサラダ | sidedish | salad | 299 | 134 | 1.2 |
| 3 | 4 | わかめサラダ | sidedish | salad | 299 | 92 | 2.1 |
| 4 | 5 | イタリアンサラダ | sidedish | salad | 299 | 196 | 0.7 |
* 評価関数は総カロリー最大化とし，価格が制約(\1,000)を超過した場合にペナルティを与えるようにします．
# 評価関数 def saize_cal(param): t_cal = sum(menu['calorie']*param) # 総カロリー t_price = sum(menu['price']*param) # 価格 if t_price > 1000.0: t_cal -= t_price*10 # 1000円を超過した場合は罰則をつける return t_cal # 変数の範囲 param_range = np.zeros([len(menu), 2]) param_range[:,1]+=1
# 離散最適化の実行 param, score = vcopt().dcGA(param_range, saize_cal, 999999, show_pool_func='print',# 表示オプション )
___________________ info ___________________
para_range : n=115
score_func : <class 'function'>
aim : 999999.0
show_pool_func : 'print'
seed : None
pool_num : 1150
max_gen : None
core_num : 1 (*vcopt, vc-grendel)
___________________ start __________________
Scoring first gen 1150/1150
gen=0, best_score=-148631.0, mean_score=-240810.4078, mean_gap=1240809.4078, time=1.7
gen=1150, best_score=-144563.0, mean_score=-220274.0991, mean_gap=1220273.0991, time=3.4
gen=2300, best_score=-125892.0, mean_score=-201871.5643, mean_gap=1201870.5643, time=5.3
(中略)
gen=34500, best_score=1735.0, mean_score=1185.0513, mean_gap=998813.9487, time=71.4
gen=35650, best_score=1940.0, mean_score=1246.8087, mean_gap=998752.1913, time=73.3
gen=36800, best_score=1940.0, mean_score=1308.6478, mean_gap=998690.3522, time=75.9
(中略)
gen=86250, best_score=1940.0, mean_score=1939.5061, mean_gap=998059.4939, time=166.0
__________________ results _________________
para : [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
score : 1940.0
____________________ end ___________________
# 最適化結果を表示 print("注文するメニュー:") print(menu['name'][param!=0].values) print("カロリー:") print(score)
注文するメニュー:
['ポテトのグリル' 'アーリオ・オーリオ(Wサイズ)' 'ラージライス']
カロリー:
1940.0
vcoptを用いて正解のメニューを無事探索することができました． 正解メニューを得るまでの探索時間は73秒でした．vcoptは解集合の分散の収束を探索完了条件とするため多少余分に探索を行っており，今回は探索完了まで166秒かかりました．
