読者です 読者をやめる 読者になる 読者になる

損失関数がNaNになる問題

TensorFlowでDeep Learningを実行している途中で、損失関数がNaNになる問題が発生した。

Epoch:  10,  Train Loss: 85.6908,   Train Accuracy: 0.996,      Test Error: 90.7068,  Test Accuracy: 0.985238
Epoch:  20,  Train Loss: 42.9642,   Train Accuracy: 0.998286,   Test Error: 121.561,  Test Accuracy: 0.98619
Epoch:  30,  Train Loss: 0.945895,  Train Accuracy: 1.0,        Test Error: 102.041,  Test Accuracy: 0.990476
Epoch:  40,  Train Loss: nan,       Train Accuracy: 0.101429,   Test Error: nan,      Test Accuracy: 0.1
Epoch:  50,  Train Loss: nan,       Train Accuracy: 0.0941429,  Test Error: nan,      Test Accuracy: 0.1
Epoch:  60,  Train Loss: nan,       Train Accuracy: 0.0968571,  Test Error: nan,      Test Accuracy: 0.1
Epoch:  70,  Train Loss: nan,       Train Accuracy: 0.0881429,  Test Error: nan,      Test Accuracy: 0.1
Epoch:  80,  Train Loss: nan,       Train Accuracy: 0.0931429,  Test Error: nan,      Test Accuracy: 0.1
Epoch:  90,  Train Loss: nan,       Train Accuracy: 0.0997143,  Test Error: nan,      Test Accuracy: 0.1
Epoch: 100,  Train Loss: nan,       Train Accuracy: 0.0997143,  Test Error: nan,      Test Accuracy: 0.1

原因は、損失関数に指定している交差エントロピーtf.log(Y)にあった。

cross_entropy = -tf.reduce_sum(Y_*tf.log(Y))

tf.log(Y)はln(x)(自然対数のlog)であり、xが0になるとき-∞になるため、NaNとなっていた。

f:id:Shoto:20170507182523p:plain

ゼロから作るDeep Learning ―Pythonで学ぶディープラーニングの理論と実装では、4章の「ニューラルネットワークの学習」で、 極少の数値を加算することで、この問題に対処する方法を提示している。

def cross_entropy_error(y, t):
    delta = 1e-7
    return -np.sum(t * np.log(y + delta))

しかし、TensorFlowを利用したいので、上記の問題を解決しているsoftmax_cross_entropy_with_logits()を用いて、 cross_entropyを書き換える。

#cross_entropy = -tf.reduce_sum(Y_*tf.log(Y))
cross_entropy = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(Y, Y_))

これにより、NaNになる問題が解決できた。 しかし、学習が進み、cross_entropyが低くなるに連れて、Yは1に近づき、tf.log(Y)は0に近づくため、 cross_entropyがNaNになる確率は低くなるはずなのだが、NaNになる点は謎のままである。

Epoch:  10,  Train Error: 1.46717,  Train Accuracy: 0.995,     Test Error: 1.47448,   Test Accuracy: 0.987619
Epoch:  20,  Train Error: 1.46428,  Train Accuracy: 0.997286,  Test Error: 1.47456,   Test Accuracy: 0.985714
Epoch:  30,  Train Error: 1.46262,  Train Accuracy: 0.998715,  Test Error: 1.47142,   Test Accuracy: 0.990476
Epoch:  40,  Train Error: 1.46272,  Train Accuracy: 0.998429,  Test Error: 1.47249,   Test Accuracy: 0.989047
Epoch:  50,  Train Error: 1.46235,  Train Accuracy: 0.998857,  Test Error: 1.47399,   Test Accuracy: 0.987619
Epoch:  60,  Train Error: 1.46462,  Train Accuracy: 0.996715,  Test Error: 1.47435,   Test Accuracy: 0.987619
Epoch:  70,  Train Error: 1.46261,  Train Accuracy: 0.998572,  Test Error: 1.47196,   Test Accuracy: 0.989524
Epoch:  80,  Train Error: 1.46215,  Train Accuracy: 0.999,     Test Error: 1.47119,   Test Accuracy: 0.99
Epoch:  90,  Train Error: 1.46547,  Train Accuracy: 0.995715,  Test Error: 1.4784,    Test Accuracy: 0.982857
Epoch: 100,  Train Error: 1.46201,  Train Accuracy: 0.999143,  Test Error: 1.47057,   Test Accuracy: 0.990476

参考文献

ResourceExhaustedErrorの原因

TensorFlowで学習していると、訓練データ数が大きい場合、たまにResourceExhaustedErrorが出る。 Windows 10では、以下の内容が表示される。

ResourceExhaustedError (see above for traceback): OOM when allocating tensor with shape[37800,32,28,28] 
[[Node: Conv2D = Conv2D[T=DT_FLOAT, data_format="NHWC", padding="SAME", strides=[1, 1, 1, 1], 
use_cudnn_on_gpu=true, _device="/job:localhost/replica:0/task:0/gpu:0"](Reshape, Variable/read)]]

注目すべきは[37800,32,28,28]の部分。 順にバッチ数、チャンネル数、画像の縦のピクセル数、画像の横のピクセル数を表している。 これらの積(37800x32x28x28=948326400、単位はbyteではない)がメモリーの許容サイズを超えたためエラーが起きてるのだが、 今回はバッチ数(37800)が大き過ぎることにより、ResourceExhaustedErrorが発生している。

以下のように、僕の環境では、バッチ数(n_batch)は、訓練データ数(n_record)とバッチ率(batch_rate)をかけて決定している。 そのため、訓練データ数が大きい場合は、バッチ率を小さくする必要があったのにしていなかったため、エラーが発生していた。 もしくはバッチ数をエラーが出ない固定値に設定する必要があった。

n_batch = int(n_record*batch_rate)
for start in range(0, n_record, n_batch):
    end = start + n_batch
    sess.run(train_step, feed_dict={X: train_data[start:end], Y_: train_label[start:end]})

TensorFlowのMNISTのチュートリアルでは、 以下のようにバッチ数を50に固定している。 ただし、訓練データ数が少ないMNISTだから50で良いが、訓練データ数が非常に大きいデータの場合は、 学習に時間がかかりすぎる場合がある。 そのため、やはりバッチ率を指定するなどにより、訓練データ数に合わせてバッチ数の調整が必要である。 また、run()だけでなくeval()に渡すバッチ数も調整する必要がある。

for i in range(20000):
    batch = mnist.train.next_batch(50)
    if i % 100 == 0:
        train_accuracy = accuracy.eval(feed_dict={x: batch[0], y_: batch[1], keep_prob: 1.0})
        print("step %d, training accuracy %g" % (i, train_accuracy))
    train_step.run(feed_dict={x: batch[0], y_: batch[1], keep_prob: 0.5})

参考文献

Python3でcPickleのエラーを回避する

CIFAR-10を読み込もうとしたら、Python2で動いてたcPickleがPython3では動かない。 import cPickleと書けばImportError: No module named 'cPickle'と吐き、 d = cPickle.load(f)と書けばUnicodeDecodeError: 'ascii' codec can't decode byte 0x8b in position 6: ordinal not in range(128)と吐く。 これらの問題を解決する。

cPicleではなく、_pickleを使う

Python3ではcPicleなど存在しない。代わりに_pickleを使えばいいのだが、 修正を最小限にするために、以下のように記述する。

#import cPickle
import _pickle as cPickle

loadできない場合はエンコードを指定する

load()のencodinglatin1を指定すると上手くいく。

    def unpickle(self, f):
        fo = open(f, 'rb')
        d = cPickle.load(fo, encoding='latin1')
        fo.close()

        return d

参考文献

CIFAR-10の取得と整理

MNISTの識別モデルをDeep Learningで上手く学習できたので、次の対象としてCIFAR-10を選んだ。 TensorFlowを使うと、学習が上手くいくように加工してくれるみたいだが、今回は一次ソースからデータを取得する。

CIFAR-10の取得

まず、CIFAR-10 and CIFAR-100 datasetsの “CIFAR-10 python version” をクリックしてデータをダウンロードする。 解凍するとcifar-10-batches-pyというフォルダーができるので適当な場所に置く。

CIFAR-10の内容

cifar-10-batches-pyの中身は以下の通り。 data_batchは10000x5レコード、test_batchは10000レコードある。 各々データとラベルに別れる。 データは1レコードあたり3072個(=1024x3, RGB)ある。 ラベルは1レコードあたり1個(0〜9のいずれか)なので、onehotにする必要がある。

cifar-10-batches-py
├── batches.meta  
├── data_batch_1  // training data 1
├── data_batch_2  // training data 2
├── data_batch_3  // training data 3
├── data_batch_4  // training data 4
├── data_batch_5  // training data 5
├── readme.html
└── test_batch    // testing data

batches.metaは以下の通り。

{
    'num_cases_per_batch': 10000,
    'label_names': ['airplane', 'automobile', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck'],
    'num_vis': 3072
}

各ファイルは、以下のメソッドで可読できるようになる。

    import cPickle
    def unpickle(self, f):
        fo = open(f, 'rb')
        d = cPickle.load(fo)
        fo.close()

        return d

CIFAR-10の整理

Deep Learningで学習させるため、訓練データ、訓練ラベル、テストデータ、テストラベルに分ける。 さらに、ラベルはonehotにする。まずは、必要なライブラリーをインポート。

# coding: utf-8

import cPickle
import numpy as np
from sklearn.preprocessing import OneHotEncoder

ダウンロードしたCIFAR-10はDIRに置くことにする。 なお、データ整理の実行ファイルをsrc/data_cifar10.pyとする。 datasrcは同じ階層にある。

DIR = '../data/cifar10/cifar-10-batches-py/'
FILE_TRAIN = 'data_batch_%s'
FILE_TEST = 'test_batch'

訓練用のdata_batchは、5分割されているので全て結合する。 ラベルについては、onehot()によりonehotに変換する。 テスト用のtest_batchの結合する以外は、data_batchと同じ処理を行う。 結果して、訓練データ、訓練ラベル、テストデータ、テストラベルを格納したdataを返す。

   def main(self):        
        # Training
        train_data = np.empty((0,3072))
        train_label = np.empty((0,10))
        for i in range(1, 6):
            print('read %s' % FILE_TRAIN%i)
            # data
            train_data_1 = self.unpickle(DIR+FILE_TRAIN%i)['data']
            train_data = np.concatenate((train_data, train_data_1), axis=0)
            # labels
            train_label_1 = self.unpickle(DIR+FILE_TRAIN%i)['labels']
            train_label_1 = self.onehot(train_label_1)
            train_label = np.concatenate((train_label, train_label_1), axis=0)

        # Testing
        print('read %s' % FILE_TEST)
        # data
        test_data = self.unpickle(DIR+FILE_TEST)['data']
        # labels
        test_label = self.unpickle(DIR+FILE_TEST)['labels']
        test_label = self.onehot(test_label)

        # Collect
        data = [train_data, train_label, test_data, test_label]

        return data

onehot()の各行の処理内容については、こちらが詳しい。

   def onehot(self, X):
        X = np.array(X).reshape(1, -1)
        X = X.transpose()
        encoder = OneHotEncoder(n_values=max(X)+1)
        X = encoder.fit_transform(X).toarray()

        return X

test()でmain()を実行して、結果を標準出力して内容を確認する。

   def test(self):
        data = self.main()
        
        print('')
        print('Training Data: %s columns, %s records' % (data[0].shape[1], data[0].shape[0]))
        print(data[0])
        print('')
        print('Training Labels: %s columns, %s records' % (data[1].shape[1], data[1].shape[0]))
        print(data[1])
        print('')

        print('Test Data: %s columns, %s records' % (data[2].shape[1], data[2].shape[0]))
        print(data[2])
        print('')
        print('Test Labels: %s columns, %s records' % (data[3].shape[1], data[3].shape[0]))
        print(data[3])      
        print('')

ファイル名を指定するだけで実行できるように以下を記述する。

if __name__ == "__main__":
    DataCifar10().test()

実行結果は以下の通り。 目的のデータが取得できていることが確認できる。

$ python data_cifar10.py
read data_batch_1
read data_batch_2
read data_batch_3
read data_batch_4
read data_batch_5
read test_batch

Training Data: 3072 columns, 50000 records
[[  59.   43.   50. ...,  140.   84.   72.]
 [ 154.  126.  105. ...,  139.  142.  144.]
 [ 255.  253.  253. ...,   83.   83.   84.]
 ...,
 [  35.   40.   42. ...,   77.   66.   50.]
 [ 189.  186.  185. ...,  169.  171.  171.]
 [ 229.  236.  234. ...,  173.  162.  161.]]

Training Labels: 10 columns, 50000 records
[[ 0.  0.  0. ...,  0.  0.  0.]
 [ 0.  0.  0. ...,  0.  0.  1.]
 [ 0.  0.  0. ...,  0.  0.  1.]
 ...,
 [ 0.  0.  0. ...,  0.  0.  1.]
 [ 0.  1.  0. ...,  0.  0.  0.]
 [ 0.  1.  0. ...,  0.  0.  0.]]

Test Data: 3072 columns, 10000 records
[[158 159 165 ..., 124 129 110]
 [235 231 232 ..., 178 191 199]
 [158 158 139 ...,   8   3   7]
 ...,
 [ 20  19  15 ...,  50  53  47]
 [ 25  15  23 ...,  80  81  80]
 [ 73  98  99 ...,  94  58  26]]

Test Labels: 10 columns, 10000 records
[[ 0.  0.  0. ...,  0.  0.  0.]
 [ 0.  0.  0. ...,  0.  1.  0.]
 [ 0.  0.  0. ...,  0.  1.  0.]
 ...,
 [ 0.  0.  0. ...,  0.  0.  0.]
 [ 0.  1.  0. ...,  0.  0.  0.]
 [ 0.  0.  0. ...,  1.  0.  0.]]

最後に全ソースを載せておく。

# coding: utf-8

import cPickle
import numpy as np
from sklearn.preprocessing import OneHotEncoder

DIR = '../data/cifar10/cifar-10-batches-py/'
FILE_TRAIN = 'data_batch_%s'
FILE_TEST = 'test_batch'

class DataCifar10:
    def __init__(self):
        pass


    def main(self):        
        # Training
        train_data = np.empty((0,3072))
        train_label = np.empty((0,10))
        for i in range(1, 6):
            print('read %s' % FILE_TRAIN%i)
            # data
            train_data_1 = self.unpickle(DIR+FILE_TRAIN%i)['data']
            train_data = np.concatenate((train_data, train_data_1), axis=0)
            # labels
            train_label_1 = self.unpickle(DIR+FILE_TRAIN%i)['labels']
            train_label_1 = self.onehot(train_label_1)
            train_label = np.concatenate((train_label, train_label_1), axis=0)

        # Testing
        print('read %s' % FILE_TEST)
        # data
        test_data = self.unpickle(DIR+FILE_TEST)['data']
        # labels
        test_label = self.unpickle(DIR+FILE_TEST)['labels']
        test_label = self.onehot(test_label)
        
        # Collect
        data = [train_data, train_label, test_data, test_label]

        return data


    def unpickle(self, f):
        fo = open(f, 'rb')
        d = cPickle.load(fo)
        fo.close()

        return d


    def onehot(self, X):
        X = np.array(X).reshape(1, -1)
        X = X.transpose()
        encoder = OneHotEncoder(n_values=max(X)+1)
        X = encoder.fit_transform(X).toarray()

        return X


    def test(self):
        data = self.main()
        
        print('')
        print('Training Data: %s columns, %s records' % (data[0].shape[1], data[0].shape[0]))
        print(data[0])
        print('')
        print('Training Labels: %s columns, %s records' % (data[1].shape[1], data[1].shape[0]))
        print(data[1])
        print('')

        print('Test Data: %s columns, %s records' % (data[2].shape[1], data[2].shape[0]))
        print(data[2])
        print('')
        print('Test Labels: %s columns, %s records' % (data[3].shape[1], data[3].shape[0]))
        print(data[3])      
        print('')


if __name__ == "__main__":
    DataCifar10().test()

参考文献

TensorFlowでmodelを保存して復元する

modelの保存と復元は、それぞれ以下のようにシンプルな設計で行える。

  • Save a model
saver = tf.train.Saver()
saver.save(sess, '../model/test_model')
  • Restore a model
saver = tf.train.Saver()
saver.restore(sess, '../model/test_model')

本記事では、実際にmodelを訓練して保存し、そのmodelを復元して、各々のテスト精度が一致していることを確認する。

処理の流れ

# coding: utf-8

import tensorflow as tf
import random
import os

from data_fizzbuzz import DataFizzBuzz

class Test:
    def __init__(self):
        pass

    def main(self):
        data = DataFizzBuzz().main()
        model = self.design_model(data)
        self.save_model(data, model)
        self.restore_model(data, model)

データを取得して、モデルをデザインして、モデルを訓練して保存して、モデルを復元する。

データ

例によってFizzBuzz問題のためのデータを利用する。 ここ にあるので、以下で解説するソースと同じ場所に置く。

モデル

def design_model(self, data):
    X  = tf.placeholder(tf.float32, [None, data[0].shape[1]])
    W1 = tf.Variable(tf.truncated_normal([data[0].shape[1], 100], stddev=0.01), name='W1')
    B1 = tf.Variable(tf.zeros([100]), name='B1')
    H1 = tf.nn.tanh(tf.matmul(X, W1) + B1)
    W2 = tf.Variable(tf.random_normal([100, data[1].shape[1]], stddev=0.01), name='W2')
    B2 = tf.Variable(tf.zeros([data[1].shape[1]]), name='B2')
    Y = tf.matmul(H1, W2) + B2
    Y_ = tf.placeholder(tf.float32, [None, data[1].shape[1]])

    tf.add_to_collection('vars', W1)
    tf.add_to_collection('vars', B1)
    tf.add_to_collection('vars', W2)
    tf.add_to_collection('vars', B2)

    model = {'X': X, 'Y': Y, 'Y_': Y_}

    return model

1層のFFNNを訓練する。 重み(W)とバイアス(B)についてはnameを付ける。 add_to_collection()で変数として登録する。

モデルの保存

def save_model(self, data, model):
    """
    # Data
    dataは、訓練データ、訓練ラベル、テストデータ、
    テストラベルの順に格納されているので、順に取り出す。
    """
    train_data  = data[0]
    train_label = data[1]
    test_data  = data[2]
    test_label = data[3]

    """
    # Model
    設計したモデルのうち、訓練で使うのは、X, Y, Y_のみなので、それらを取り出す。
    """
    X, Y, Y_ = model['X'], model['Y'], model['Y_']

    """
    # Functions
    訓練で利用する関数をそれぞれ定義する。
    """
    loss = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(Y, Y_))
    step = tf.train.AdamOptimizer(0.05).minimize(loss)
    accuracy = tf.reduce_mean(tf.cast(tf.equal(tf.argmax(Y, 1), tf.argmax(Y_, 1)), tf.float32))

    """
    # Setting
    初期化。saverは、モデルを保存するためのインスタンス。
    """
    saver = tf.train.Saver()
    sess = tf.Session()
    sess.run(tf.global_variables_initializer())

    """
    # Randamize data
    101〜1023のデータをランダマイズする。
    """
    p = np.random.permutation(range(len(train_data)))
    train_data, train_label = train_data[p], train_label[p]

    """
    # Training
    100バッチずつ訓練するエポックを1回繰り返す。
    訓練エラー、訓練精度、テスト精度を算出する。
    """
    for start in range(0, train_label.shape[0], 1):
        end = start + 100
        sess.run(step, feed_dict={X: train_data[start:end], Y_: train_label[start:end]})

        # Testing
        train_loss = sess.run(loss, feed_dict={X: train_data, Y_: train_label})
        train_accuracy = sess.run(accuracy, feed_dict={X: train_data, Y_: train_label})
        test_accuracy = sess.run(accuracy, feed_dict={X: test_data, Y_: test_label})

    """
    # Accuracy
    学習後、訓練エラー、訓練精度、テスト精度を標準出力する。
    """
    std_output = 'Train Loss: %s, \t Train Accuracy: %s, \t Test Accuracy: %s'
    print(std_output % (train_loss, train_accuracy, test_accuracy))

    """
    # Save a model
    既存の訓練モデルを削除して、今回訓練したモデルを保存する。
    """
    for f in os.listdir('../model/'):
        os.remove('../model/'+f)
    saver.save(sess, '../model/test_model')
    print('Saved a model.')

    sess.close()

modelディレクトリーには、以下が保存される。

  • checkpoint
  • test_model.data-00000-of-00001
  • test_model.index
  • test_model.meta

モデルの復元

def restore_model(self, data, model):
    # Data
    train_data  = data[0]
    train_label = data[1]
    test_data  = data[2]
    test_label = data[3]

    # Model
    X, Y, Y_ = model['X'], model['Y'], model['Y_']

    # Function
    accuracy = tf.reduce_mean(tf.cast(tf.equal(tf.argmax(Y, 1), tf.argmax(Y_, 1)), tf.float32))

    """
    # Setting
    SaverとSessionのインスタンスを生成し、モデルを復元する。
    """
    saver = tf.train.Saver()
    sess = tf.Session()
    saver.restore(sess, '../model/test_model')
    print('Restored a model')

    test_accuracy = sess.run(accuracy, feed_dict={X: test_data, Y_: test_label})
    print('Test Accuracy: %s' % test_accuracy)

復元は非常に簡単。 モデルの保存で使用したデータとモデルを渡している。 データは何でもいいが、モデルは同じものが必要。 初期化は不要。

実行結果

$ python test.py
Train Loss: 1.88192,     Train Accuracy: 0.781148,   Test Accuracy: 0.762376
Saved a model.
Restored a model
Test Accuracy: 0.762376

Test Accuracyが、モデルの保存とモデルの復元で一致している。 同じモデルとテストデータだと、同じ精度が出ることが確認できた。

その他

もしモデルの復元で失敗するときは、モデルの保存を一回した後で、モデルの復元だけ実行したり、 以下のように1行足してみると上手く行くかも。

# Setting
saver = tf.train.Saver()
sess = tf.Session()
saver = tf.train.import_meta_graph('../model/test_model.meta')  ## <- add
saver.restore(sess, '../model/test_model')

遺伝的アルゴリズムによるナップサック問題の最適化

以前遺伝的アルゴリズムの入門的なOneMax問題を解いた。

testpy.hatenablog.com

今回は、これよりも少し複雑なナップサック問題を解く。

ナップサック問題とは

Wikipedia によると、ナップサック問題とは次のような問題である。

ナップサック問題は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、 「容量 C のナップサックが一つと、n 種類の品物(各々、価値 pi, 容積 ci)が与えられたとき、 ナップサックの容量 Cを超えない範囲でいくつかの品物をナップサックに詰め、 ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。 同じ種類の品物を1つまでしか入れられない場合(xi ∈ {0, 1})や、 同じ品物をいくつでも入れてよい場合(xi ∈ 0以上の整数)など、いくつかのバリエーションが存在する。

今回は容量Cは無視する。 いくらでも品物を詰め込めるが、価値を最大化しつつ、容積ではなく重さを最小化する。 また同じ品物をいくつでも入れて良いことにする。

個体生成、評価、エリート選出

品物が価値と重さという2つの変数を持つ。 まずはこれらを20個生成する。

# input
for i in xrange(N_ITEMS):
    self.items[i] = (random.randint(0, 100), random.randint(1, 10))  # value, weight
# output
{0: (90, 5), 1: (18, 5), 2: (25, 7), 3: (12, 7), 4: (52, 2), 5: (77, 10), 6: (72, 3), 7: (2, 10), 8: (89, 6), 9: (36, 10), 10: (22, 9), 11: (47, 6), 12: (45, 3), 13: (65, 6), 14: (25, 6), 15: (71, 5), 16: (81, 9), 17: (11, 6), 18: (90, 10), 19: (32, 5)}

20個の品物の中から5つずつランダムに選んだセットを20個用意する。

# input
pop = []
for i in range(N_POP):
    ind = [self.items[k] for k in random.sample(range(N_ITEMS), 5)]
    pop.append(ind)
# output
[(25, 7), (11, 6), (2, 10), (18, 5), (77, 10)]
[(22, 9), (65, 6), (77, 10), (89, 6), (81, 9)]
[(72, 3), (81, 9), (52, 2), (25, 6), (18, 5)]
[(36, 10), (45, 3), (81, 9), (90, 5), (90, 10)]
[(25, 6), (81, 9), (36, 10), (89, 6), (77, 10)]
[(65, 6), (72, 3), (90, 5), (25, 6), (12, 7)]
[(18, 5), (2, 10), (71, 5), (11, 6), (36, 10)]
[(77, 10), (12, 7), (25, 6), (47, 6), (71, 5)]
[(89, 6), (47, 6), (25, 7), (65, 6), (25, 6)]
[(52, 2), (25, 6), (18, 5), (36, 10), (89, 6)]
[(71, 5), (65, 6), (36, 10), (25, 6), (32, 5)]
[(2, 10), (32, 5), (25, 6), (81, 9), (71, 5)]
[(12, 7), (36, 10), (71, 5), (22, 9), (81, 9)]
[(36, 10), (18, 5), (12, 7), (90, 10), (72, 3)]
[(77, 10), (22, 9), (90, 5), (25, 6), (11, 6)]
[(22, 9), (89, 6), (71, 5), (72, 3), (65, 6)]
[(77, 10), (32, 5), (52, 2), (89, 6), (45, 3)]
[(47, 6), (2, 10), (18, 5), (25, 6), (89, 6)]
[(65, 6), (2, 10), (89, 6), (52, 2), (45, 3)]
[(36, 10), (11, 6), (2, 10), (89, 6), (65, 6)]

これらの個体として、各々評価を行う。 と言っても、価格と重さを各々足し合わせるだけ。

# input
def clac_score(self, indivisual):
    dic = {}
    dic['score0'] = 0  # value
    dic['score1'] = 0  # weight
    for ind in indivisual:
        dic['score0'] += ind[0]
        dic['score1'] += ind[1]
# output
{'score0': 133, 'score1': 38, 'param': [(25, 7), (11, 6), (2, 10), (18, 5), (77, 10)]}
{'score0': 334, 'score1': 40, 'param': [(22, 9), (65, 6), (77, 10), (89, 6), (81, 9)]}
{'score0': 248, 'score1': 25, 'param': [(72, 3), (81, 9), (52, 2), (25, 6), (18, 5)]}
{'score0': 342, 'score1': 37, 'param': [(36, 10), (45, 3), (81, 9), (90, 5), (90, 10)]}
{'score0': 308, 'score1': 41, 'param': [(25, 6), (81, 9), (36, 10), (89, 6), (77, 10)]}
{'score0': 264, 'score1': 27, 'param': [(65, 6), (72, 3), (90, 5), (25, 6), (12, 7)]}
{'score0': 138, 'score1': 36, 'param': [(18, 5), (2, 10), (71, 5), (11, 6), (36, 10)]}
{'score0': 232, 'score1': 34, 'param': [(77, 10), (12, 7), (25, 6), (47, 6), (71, 5)]}
{'score0': 251, 'score1': 31, 'param': [(89, 6), (47, 6), (25, 7), (65, 6), (25, 6)]}
{'score0': 220, 'score1': 29, 'param': [(52, 2), (25, 6), (18, 5), (36, 10), (89, 6)]}
{'score0': 229, 'score1': 32, 'param': [(71, 5), (65, 6), (36, 10), (25, 6), (32, 5)]}
{'score0': 211, 'score1': 35, 'param': [(2, 10), (32, 5), (25, 6), (81, 9), (71, 5)]}
{'score0': 222, 'score1': 40, 'param': [(12, 7), (36, 10), (71, 5), (22, 9), (81, 9)]}
{'score0': 228, 'score1': 35, 'param': [(36, 10), (18, 5), (12, 7), (90, 10), (72, 3)]}
{'score0': 225, 'score1': 36, 'param': [(77, 10), (22, 9), (90, 5), (25, 6), (11, 6)]}
{'score0': 319, 'score1': 29, 'param': [(22, 9), (89, 6), (71, 5), (72, 3), (65, 6)]}
{'score0': 295, 'score1': 26, 'param': [(77, 10), (32, 5), (52, 2), (89, 6), (45, 3)]}
{'score0': 181, 'score1': 33, 'param': [(47, 6), (2, 10), (18, 5), (25, 6), (89, 6)]}
{'score0': 253, 'score1': 27, 'param': [(65, 6), (2, 10), (89, 6), (52, 2), (45, 3)]}
{'score0': 203, 'score1': 38, 'param': [(36, 10), (11, 6), (2, 10), (89, 6), (65, 6)]}

価格を最大化して、重さを最小化するには、 価格を降順、重さを昇順にソートする。 pure pythonだとソートコードが複雑になりそうだったので、Pandasを利用した。

# input
df = pd.DataFrame(fitness)
df = df.sort(['score0', 'score1'], ascending=[False, True])
# output
                                              param  score0  score1
3   [(36, 10), (45, 3), (81, 9), (90, 5), (90, 10)]     342      37
1    [(22, 9), (65, 6), (77, 10), (89, 6), (81, 9)]     334      40
15    [(22, 9), (89, 6), (71, 5), (72, 3), (65, 6)]     319      29
4   [(25, 6), (81, 9), (36, 10), (89, 6), (77, 10)]     308      41
16   [(77, 10), (32, 5), (52, 2), (89, 6), (45, 3)]     295      26
5     [(65, 6), (72, 3), (90, 5), (25, 6), (12, 7)]     264      27
18    [(65, 6), (2, 10), (89, 6), (52, 2), (45, 3)]     253      27
8     [(89, 6), (47, 6), (25, 7), (65, 6), (25, 6)]     251      31
2     [(72, 3), (81, 9), (52, 2), (25, 6), (18, 5)]     248      25
7    [(77, 10), (12, 7), (25, 6), (47, 6), (71, 5)]     232      34
10   [(71, 5), (65, 6), (36, 10), (25, 6), (32, 5)]     229      32
13  [(36, 10), (18, 5), (12, 7), (90, 10), (72, 3)]     228      35
14   [(77, 10), (22, 9), (90, 5), (25, 6), (11, 6)]     225      36
12   [(12, 7), (36, 10), (71, 5), (22, 9), (81, 9)]     222      40
9    [(52, 2), (25, 6), (18, 5), (36, 10), (89, 6)]     220      29
11    [(2, 10), (32, 5), (25, 6), (81, 9), (71, 5)]     211      35
19   [(36, 10), (11, 6), (2, 10), (89, 6), (65, 6)]     203      38
17    [(47, 6), (2, 10), (18, 5), (25, 6), (89, 6)]     181      33
6    [(18, 5), (2, 10), (71, 5), (11, 6), (36, 10)]     138      36
0    [(25, 7), (11, 6), (2, 10), (18, 5), (77, 10)]     133      38

ただし、populationはdict in listで扱いたいので、 DataFrameから再びdict in listに変換している。

# input
fitness = df.to_dict('records')
# output
{'score0': 342, 'score1': 37, 'param': [(36, 10), (45, 3), (81, 9), (90, 5), (90, 10)]}
{'score0': 334, 'score1': 40, 'param': [(22, 9), (65, 6), (77, 10), (89, 6), (81, 9)]}
{'score0': 319, 'score1': 29, 'param': [(22, 9), (89, 6), (71, 5), (72, 3), (65, 6)]}
{'score0': 308, 'score1': 41, 'param': [(25, 6), (81, 9), (36, 10), (89, 6), (77, 10)]}
{'score0': 295, 'score1': 26, 'param': [(77, 10), (32, 5), (52, 2), (89, 6), (45, 3)]}
{'score0': 264, 'score1': 27, 'param': [(65, 6), (72, 3), (90, 5), (25, 6), (12, 7)]}
{'score0': 253, 'score1': 27, 'param': [(65, 6), (2, 10), (89, 6), (52, 2), (45, 3)]}
{'score0': 251, 'score1': 31, 'param': [(89, 6), (47, 6), (25, 7), (65, 6), (25, 6)]}
{'score0': 248, 'score1': 25, 'param': [(72, 3), (81, 9), (52, 2), (25, 6), (18, 5)]}
{'score0': 232, 'score1': 34, 'param': [(77, 10), (12, 7), (25, 6), (47, 6), (71, 5)]}
{'score0': 229, 'score1': 32, 'param': [(71, 5), (65, 6), (36, 10), (25, 6), (32, 5)]}
{'score0': 228, 'score1': 35, 'param': [(36, 10), (18, 5), (12, 7), (90, 10), (72, 3)]}
{'score0': 225, 'score1': 36, 'param': [(77, 10), (22, 9), (90, 5), (25, 6), (11, 6)]}
{'score0': 222, 'score1': 40, 'param': [(12, 7), (36, 10), (71, 5), (22, 9), (81, 9)]}
{'score0': 220, 'score1': 29, 'param': [(52, 2), (25, 6), (18, 5), (36, 10), (89, 6)]}
{'score0': 211, 'score1': 35, 'param': [(2, 10), (32, 5), (25, 6), (81, 9), (71, 5)]}
{'score0': 203, 'score1': 38, 'param': [(36, 10), (11, 6), (2, 10), (89, 6), (65, 6)]}
{'score0': 181, 'score1': 33, 'param': [(47, 6), (2, 10), (18, 5), (25, 6), (89, 6)]}
{'score0': 138, 'score1': 36, 'param': [(18, 5), (2, 10), (71, 5), (11, 6), (36, 10)]}
{'score0': 133, 'score1': 38, 'param': [(25, 7), (11, 6), (2, 10), (18, 5), (77, 10)]}

個体と評価を保存する

ナップサック問題の個体の評価は、各品物の価格と重さを各々足し合わせるだけなので高速だが、 遺伝的アルゴリズムが扱う問題によっては評価に時間がかかることがある。 世代を重ねるごとに各個体は評価が上がり類似した遺伝子になっていく。 そのため、交叉や突然変異により生成された個体と同じ遺伝子を持つ個体が過去に存在することも珍しくない。 今後の遺伝的アルゴリズムの拡張を考えて、過去の個体とその評価を保存し、各個体を評価する前に参照するようにしておく。

保存する形式もdict in listにするが、パラメーターがlistだと一致評価できないので、Stringに変換してから保存。

self.fitness_master = {}
for fit in fitness:
    param = fit['param']
    self.fitness_master[str(param)] = {k:v for k,v in fit.items() if k!='param'}

個体の評価では、次の3パターンに別れる。

  1. スコアはないけどパラメーターはある
  2. スコアもなくてパラメーターもない
  3. スコアもパラメーターもある

1がまさに今回のパターン。2は新たな個体が生まれたとき。 3は交叉または突然変異の前の評価のとき。 このアルゴリズム特有で無駄な処理だが、個体の評価を参照することで高速処理できる。

fitness = []
for p in pop:
    if not p.has_key('score0'):
        # The indivisual made by crossover or mutation existed before
        if self.fitness_master.has_key(str(p['param'])):
            p.update(self.fitness_master[str(p['param'])])
        # The indivisual is the first
        else:
            p.update(self.clac_score(p['param']))
        fitness.append(p)
    else:
        fitness.append(p)

まとめ

実行結果は、以下の通り。 世代数が少ない、突然変異率が低いなどが原因で、 必ずしも一番価値のある商品だけで構成するとはなっていない。

               V   W  P                                    
Generation  0: 323 25 [(25, 1), (82, 3), (89, 6), (45, 10), (82, 5)]
Generation  1: 323 25 [(25, 1), (82, 3), (89, 6), (45, 10), (82, 5)]
Generation  2: 323 25 [(25, 1), (82, 3), (89, 6), (45, 10), (82, 5)]
Generation  3: 365 22 [(89, 6), (65, 2), (65, 2), (82, 5), (64, 7)]
Generation  4: 365 22 [(89, 6), (65, 2), (65, 2), (82, 5), (64, 7)]
Generation  5: 365 22 [(89, 6), (65, 2), (65, 2), (82, 5), (64, 7)]
Generation  6: 365 22 [(89, 6), (65, 2), (65, 2), (82, 5), (64, 7)]
Generation  7: 389 26 [(89, 6), (65, 2), (89, 6), (82, 5), (64, 7)]
Generation  8: 389 26 [(89, 6), (65, 2), (89, 6), (82, 5), (64, 7)]
Generation  9: 389 26 [(89, 6), (65, 2), (89, 6), (82, 5), (64, 7)]
Generation 10: 396 27 [(89, 6), (89, 6), (89, 6), (65, 2), (64, 7)]
Generation 11: 396 27 [(89, 6), (89, 6), (89, 6), (65, 2), (64, 7)]
Generation 12: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)]
Generation 13: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)]
Generation 14: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)]
Generation 15: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)]
Generation 16: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)]
Generation 17: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)]
Generation 18: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)]
Generation 19: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)]
Generation 20: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)]
Generation 21: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)]
Generation 22: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)]
Generation 23: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)]
Generation 24: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)]

全コードも載せておく。

# coding: utf-8

import random
import math
import copy
import operator
import pandas as pd

N_ITEMS = 20
N_POP = 20
N_GEN = 25
MUTATE_PROB = 0.1
ELITE_RATE = 0.5

class GA:
    def __init__(self):
        self.items = {}
        self.fitness_master = {}


    def main(self): 
        pop = [{'param': p} for p in self.get_population()]
        
        for g in range(N_GEN):
            print 'Generation%3s:' % str(g), 

            # Get elites
            fitness = self.evaluate(pop)
            elites = fitness[:int(len(pop)*ELITE_RATE)]

            # Cross and mutate
            pop = elites[:]
            while len(pop) < N_POP:
                if random.random() < MUTATE_PROB:
                    m = random.randint(0, len(elites)-1)
                    child = self.mutate(elites[m]['param'])
                else:
                    c1 = random.randint(0, len(elites)-1)
                    c2 = random.randint(0, len(elites)-1)
                    child = self.crossover(elites[c1]['param'], elites[c2]['param'])
                pop.append({'param': child})
            
            # Evaluate indivisual
            fitness = self.evaluate(pop)
            pop = fitness[:]

            print pop[0]['score0'], pop[0]['score1'], pop[0]['param']

            
    def get_population(self):
        # Make items
        for i in xrange(N_ITEMS):
            self.items[i] = (random.randint(0, 100), random.randint(1, 10))  # value, weight

        # Make population
        pop = []
        for i in range(N_POP):
            ind = [self.items[k] for k in random.sample(range(N_ITEMS), 5)]
            pop.append(ind)

        return pop


    def clac_score(self, indivisual):
        dic = {}
        dic['score0'] = 0  # value
        dic['score1'] = 0  # weight
        for ind in indivisual:
            dic['score0'] += ind[0]
            dic['score1'] += ind[1]
            
        return dic


    def evaluate(self, pop):
        fitness = []
        for p in pop:
            if not p.has_key('score0'):
                # The indivisual made by crossover or mutation existed before
                if self.fitness_master.has_key(str(p['param'])):
                    p.update(self.fitness_master[str(p['param'])])
                # The indivisual is the first
                else:
                    p.update(self.clac_score(p['param']))
                fitness.append(p)
            else:
                fitness.append(p)

        # Save fitness to all genaration dictinary
        for fit in fitness:
            param = fit['param']
            self.fitness_master[str(param)] = {k:v for k,v in fit.items() if k!='param'}

        # This generation fitness
        df = pd.DataFrame(fitness)
        df = df.sort(['score0', 'score1'], ascending=[False, True])

        fitness = df.to_dict('records')
        
        return fitness


    def mutate(self, parent):
        ind_idx = int(math.floor(random.random()*len(parent)))
        item_idx = random.choice(range(N_ITEMS))
        child = copy.deepcopy(parent)
        child[ind_idx] = self.items[item_idx]

        return child


    def crossover(self, parent1, parent2):
        length = len(parent1)
        r1 = int(math.floor(random.random()*length))
        r2 = r1 + int(math.floor(random.random()*(length-r1)))
        
        child = copy.deepcopy(parent1)
        child[r1:r2] = parent2[r1:r2]

        return child


if __name__ == "__main__":
    GA().main()

追記: 第一世代の扱いについて

上記だと、for文の中にevaluate()が無駄に2つ入ってるが、 1つ目は第一世代の評価にしか使わないので、for文の外に出す方が適切。 for文の中では、交叉と突然変異で生まれた世代の評価を行う。

    def main(self): 
        print('Generation  1:'), 
        pop = [{'param': p} for p in self.get_population()]
        fitness = self.evaluate(pop)
        print(fitness[0]['score0'], fitness[0]['score1'], fitness[0]['param'])

        for g in range(N_GEN-1):
            print('Generation %2s:' % str(g+2)),
            
            # Get elites
            elites = fitness[:int(len(pop)*ELITE_RATE)]

            # Cross and mutate
            pop = elites[:]
            while len(pop) < N_POP:
                if random.random() < MUTATE_PROB:
                    m = random.randint(0, len(elites)-1)
                    child = self.mutate(elites[m]['param'])
                else:
                    c1 = random.randint(0, len(elites)-1)
                    c2 = random.randint(0, len(elites)-1)
                    child = self.crossover(elites[c1]['param'], elites[c2]['param'])
                pop.append({'param': child})
            
            # Evaluate indivisual
            fitness = self.evaluate(pop)
            print(fitness[0]['score0'], fitness[0]['score1'], fitness[0]['param'])

Pandas.DataFrameをdicts in listに変換する

dicts in listからDataFrameを作成することはよくあるが、 DataFrameをdicts in listにしたい時がたまにある。 df.to_dict('records')を実行するだけで良いのだが、 このシンプルなコードを良く忘れるのに記事にした。

入出力がまったく同じdicts in listで実施。

dicts_in_list = [{'x': random.randint(0, 10), 'y': random.randint(1, 5)} for i in range(10)]
for dil in dicts_in_list:
    print dil

df = pd.DataFrame(dicts_in_list)
print df

dicts_in_list = df.to_dict('records')
for dil in dicts_in_list:
    print dil

結果は以下の通り。

{'y': 1, 'x': 9}
{'y': 2, 'x': 7}
{'y': 3, 'x': 7}
{'y': 1, 'x': 10}
{'y': 5, 'x': 8}
{'y': 2, 'x': 1}
{'y': 5, 'x': 0}
{'y': 5, 'x': 6}
{'y': 5, 'x': 3}
{'y': 5, 'x': 7}

    x  y
0   9  1
1   7  2
2   7  3
3  10  1
4   8  5
5   1  2
6   0  5
7   6  5
8   3  5
9   7  5

{'y': 1, 'x': 9}
{'y': 2, 'x': 7}
{'y': 3, 'x': 7}
{'y': 1, 'x': 10}
{'y': 5, 'x': 8}
{'y': 2, 'x': 1}
{'y': 5, 'x': 0}
{'y': 5, 'x': 6}
{'y': 5, 'x': 3}
{'y': 5, 'x': 7}

参考文献