【だがしかし】遺伝的アルゴリズムで最高のうまい棒の組み合わせを求めた。
だがしかし第1話でうまい棒はいろいろな組み合わせで食べることができ、最高だということをほたるさんが言っていましたが、今回は遺伝的アルゴリズムの手法を用いて本当に良い組み合わせは何なのかを求めてみました。
方法
データ収集
まず上のサイトからうまい棒の成分データをスクレイピングし、JSON形式で保存しました。下記のようなデータを得られました。
[ { "name": "チーズ味", "energy": 34, "protein": 0.4, "fat": 2, "carbon": 3.1, "natrium": 35 }, { "name": "ポタージュ", "energy": 34, "protein": 0.4, "fat": 2.1, "carbon": 3.3, "natrium": 35 } }
得られた味の数は17種類でした。
チーズ味 ポタージュ めんたい味 サラミ味 ヤサイサラダ味 テリヤキバーガー味 エビマヨネーズ味 シュガーラスク味 たこやき味 ピザ味 なっとう味 オニオンサラダ味 モッツァレラチーズ&カマンベールチーズ味 チョコレート味 とんかつソース味 牛タン塩味 明太子味(プレミアム)
これらの味に関して上記のような成分データを得られました。
遺伝的アルゴリズムについて
今回の実験では合計脂質(fat)25以下でどれだけその他の栄養価(energy, protein, carbon, natrium)が高い組み合わせを発見できるかを調べました。
このような問題を一般にナップザック問題といいます。
ナップザック問題とは容量に制限のあるナップザックにどれだけ別のパラメータ(例えば値段や栄養価等)の高い物をたくさん入れられるかという問題です。今回の場合は重さが脂質で別のパラメータが脂質以外の栄養価の合計になります。この問題はスケールした場合計算量が膨大になってしまいます。そこで遺伝的アルゴリズムを用いた方法が知られています。
遺伝的アルゴリズムでは、生物の進化を参考にして計算を行います。まず問題を遺伝子型で表します。遺伝子型とは例えば01の配列等です。実数でも表す方法が存在しています。今回は組み合わせに含むうまい棒を1、組み合わせに含まないうまい棒を0とした17列の配列で表しました。
まず、母集団として、上記の配列を20種類生成します。次にこの母集団に選択、交叉、突然変異の処理を繰り返します。
選択とは、母集団の中から次の世代の親となる個体を選択します。この選択は重要で様々なアルゴリズムが存在します。今回はルーレット戦略+ランキング法を用いました。ルーレット選択は適合度(今回の場合は脂質以外の栄養価の合計)で当たる確立を決めてルーレットを回し親を決める手法です。実際にはルーレットが存在しないので乱数とかを使ってやります。しかし、この方法だと適合度の差が大きい場合、その個体しか選ばれなくなり進化が止まってしまいますのでランキング法を導入します。
ランキング法はそれぞれの個体の適合度の差を1にします。具体的には適合度の小さい順に1からランク付けしていき、ランクを使ってルーレットで選択します。こうすることで適合度に大きな差があっても進化が止まってしまうことを防げます。
交叉は選択した親の遺伝子を入れ替え子を作成します。今回は一様交叉を用いました。一様交叉は親たちの遺伝子をランダムに組み合わせ子を生成します。生成した子は現世代の1番劣っている個体と入れ替えます。
突然変異は無条件に遺伝子を変更します。こうすることで、進化の停止を抑止することができます。
このサイクルを1000回実行し、最適解を求めます。この遺伝的アルゴリズムを用いた方法は必ず最適解が求まるわけではないので、80回並列に実行し最もよい結果を最適解とするプログラムを作成しました。言語はPythonを使いました。
#coding:utf-8 import json import random import copy import math import numpy as np import threading import copy import multiprocessing class Ga: def __init__(self, fname, mutRate=3.0, numGen=1000, numGenes = 20, numParent = 2): f = open(fname) # 生のデータ self.data = json.load(f) f.close() # 染色体数 self.numElem = len(self.data) # 突然変異率 self.mutRate = mutRate # 世代制限 self.numGen = numGen # 個体数 self.numGenes = numGenes # 染色体表現 self.genes = np.random.randint(2, size=(self.numGenes, self.numElem)) # ランキングの合計 self.fit_sum = sum(range(1, self.numGenes)) # 交叉時の親の数 self.numParent = numParent def __calc_fit(self, umaibou): # うまい棒の適合度を計算する sum = 0 sum += umaibou[u'energy'] sum += umaibou[u'protein'] sum += umaibou[u'carbon'] sum += umaibou[u'natrium'] return sum def __calc_comb_fat(self, comb): fat = 0 for i, c in enumerate(comb): if c == 1: fat+= self.data[i][u'fat'] return fat def __calc_comb_fit(self): # 組み合わせの適合度計算 fitness = np.zeros(self.numGenes) for i, comb in enumerate(self.genes): fats = 0 for j, isExs in enumerate(comb): if isExs == 1: fitness[i] += self.__calc_fit(self.data[j]) fats+= self.data[j][u'fat'] # 脂質25以下という制約条件を超えると適合度は0になる if fats > 25: fitness[i] = 0 break return fitness def __ranking(self, fitness): # 適合度を昇順に並べ替え indice = np.argsort(fitness) # 適合度が小さいほうからランク付けしていく1- rank = 1 ranking = np.zeros(len(indice)) for i in indice: ranking[i] = rank rank+=1 return ranking def __show_umaibou(self, umaibou): print('Name: %s' % umaibou[u'name']) print('energy: %f' % umaibou[u'energy']) print('protein: %f' % umaibou[u'protein']) print('carbon: %f' % umaibou[u'carbon']) print('natrium: %f' % umaibou[u'natrium']) print('fat: %f' % umaibou[u'fat']) def __show_comb(self, genes): for i, v in enumerate(genes): if v == 1: self.__show_umaibou(self.data[i]) def __choice_parents(self, rank): parents = [] for i in xrange(self.numParent): index = random.randint(0, self.fit_sum) sumFit = 0 # ランキングを降順にソートしインデックスを取得 indice = np.argsort(rank)[-1::-1] for i in indice: sumFit += rank[i] if sumFit > index and not i in parents: parents.append(i) break return parents def __crossover(self, parents): child = np.zeros(self.numElem) for i in xrange(self.numElem): r = random.randint(0, self.numParent-1) child[i] = self.genes[parents[r]][i] return child def __mutation(self): for i, v in enumerate(self.genes): r = random.randint(0, 100) if r < self.mutRate: pos = random.randint(0, self.numElem-1) if v[pos] == 0: self.genes[i][pos] = 1 else: self.genes[i][pos] = 0 def ga(self): for i in xrange(0, self.numGen): #適合度行列を計算 fitness = self.__calc_comb_fit() ranking = self.__ranking(fitness) parents = self.__choice_parents(ranking) child = self.__crossover(parents) indice = np.argsort(fitness) self.genes[indice[0]] = child self.__mutation() #print(fitness) #print(fitness[indice[self.numElem-1]]) fitness = self.__calc_comb_fit() indice = np.argsort(fitness)[-1::-1] return fitness[indice[0]], self def show_result(self): fitness = self.__calc_comb_fit() indice = np.argsort(fitness)[-1::-1] print('適合度: %f' % fitness[indice[0]]) print('脂質: %f' % self.__calc_comb_fat(self.genes[indice[0]])) self.__show_comb(self.genes[indice[0]]) max_fitness = 0.0 ga = None lock = threading.Lock() def conc(): global max_fitness global ga global lock g = Ga("../data/umaibou.json", numGen=1000, mutRate=5.0) fitness, ga_tmp = g.ga() lock.acquire() try: print("finished calcurate") if max_fitness < fitness: max_fitness = fitness ga = copy.copy(ga_tmp) finally: lock.release() for i in range(multiprocessing.cpu_count()): t = threading.Thread(target=conc) t.start() main_thread = threading.currentThread() for t in threading.enumerate(): if t is not main_thread: t.join() ga.show_result()
PythonではGoみたいに簡単にCPUの個数を指定できないようで、上記プログラムは1つのCPUでしか動きませんでした。
結果
下記結果を得ました。
適合度: 930.700000 脂質: 25.000000 Name: チーズ味 energy: 34.000000 protein: 0.400000 carbon: 3.100000 natrium: 35.000000 fat: 2.000000 Name: ポタージュ energy: 34.000000 protein: 0.400000 carbon: 3.300000 natrium: 35.000000 fat: 2.100000 Name: めんたい味 energy: 35.000000 protein: 0.400000 carbon: 3.100000 natrium: 37.000000 fat: 2.300000 Name: サラミ味 energy: 34.000000 protein: 0.400000 carbon: 3.200000 natrium: 33.000000 fat: 2.100000 Name: ヤサイサラダ味 energy: 35.000000 protein: 0.400000 carbon: 3.000000 natrium: 33.000000 fat: 2.300000 Name: テリヤキバーガー味 energy: 35.000000 protein: 0.400000 carbon: 3.000000 natrium: 33.000000 fat: 2.300000 Name: シュガーラスク味 energy: 34.000000 protein: 0.300000 carbon: 3.500000 natrium: 22.000000 fat: 2.000000 Name: なっとう味 energy: 32.000000 protein: 0.600000 carbon: 3.300000 natrium: 50.000000 fat: 1.900000 Name: モッツァレラチーズ&カマンベールチーズ味 energy: 50.000000 protein: 0.700000 carbon: 4.700000 natrium: 86.000000 fat: 3.100000 Name: とんかつソース味 energy: 29.000000 protein: 0.300000 carbon: 2.500000 natrium: 24.000000 fat: 2.000000 Name: 明太子味 energy: 49.000000 protein: 0.700000 carbon: 5.000000 natrium: 99.000000 fat: 2.900000
適合度(脂質以外の栄養価の合計) | 制約条件(脂質合計) |
---|---|
930.7 | 25 |
最高のうまい棒の組み合わせは、、、
チーズ味
ポタージュ
めんたい味
サラミ味
ヤサイサラダ味
テリヤキバーガー味
シュガーラスク味
なっとう味
モッツァレラチーズ&カマンベールチーズ味
とんかつソース味
明太子味(プレミアム)
となりました。
終わりに
適合度も十分高く、制約条件も最大で満たすことができたのでこれが最適解だと考えられました。組み合わせの要素数が11とかなり大きかったので制約条件をもう少し厳しくしてもよかったのではないかと考えました。
最後にプログラムのソースコードを載せます。