日記

更新頻度はあまり高くはありませんがネタがあったら書いていこうと思います。

【だがしかし】遺伝的アルゴリズムで最高のうまい棒の組み合わせを求めた。

だがしかし第1話でうまい棒はいろいろな組み合わせで食べることができ、最高だということをほたるさんが言っていましたが、今回は遺伝的アルゴリズムの手法を用いて本当に良い組み合わせは何なのかを求めてみました。

https://pbs.twimg.com/media/CYFpTxeVAAAed9M.jpg

方法

データ収集

www.eatsmart.jp

まず上のサイトからうまい棒の成分データをスクレイピングし、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)が高い組み合わせを発見できるかを調べました。
このような問題を一般にナップザック問題といいます。

ナップサック問題 - Wikipedia

ナップザック問題とは容量に制限のあるナップザックにどれだけ別のパラメータ(例えば値段や栄養価等)の高い物をたくさん入れられるかという問題です。今回の場合は重さが脂質で別のパラメータが脂質以外の栄養価の合計になります。この問題はスケールした場合計算量が膨大になってしまいます。そこで遺伝的アルゴリズムを用いた方法が知られています。

遺伝的アルゴリズムでは、生物の進化を参考にして計算を行います。まず問題を遺伝子型で表します。遺伝子型とは例えば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とかなり大きかったので制約条件をもう少し厳しくしてもよかったのではないかと考えました。

最後にプログラムのソースコードを載せます。

github.com