トップ > Python > vcoptの試用&「サイゼリヤで1000円あれば最大何kcal摂れるのか」問題を遺伝的アルゴリズムで解く

vcoptの試用&「サイゼリヤで1000円あれば最大何kcal摂れるのか」問題を遺伝的アルゴリズムで解く

Python vcopt 遺伝的アルゴリズム 単目的最適化

ほとんどパラメータを設定せずに遺伝的アルゴリズムによる最適化が可能な 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の基本的な使い方 (連続値のパラメータの最適化)

f({\bf x}) = f(x_1, x_2,\cdots,x_N) = \sum_{i=1}^{N-1}[100(x_{i+1}-x_{i}^2)^2+(1-x_{i})^2 ]

変数の範囲は -5.12 \leq x_i \leq 5.12で，最適解は f_{min}(1,\cdots,1)=0です． 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()

f:id:ohtayo:20200301234416p:plain

# 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秒かかりました．

参考文献