損失関数が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となっていた。
ゼロから作る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
参考文献
- Why does my TensorFlow Convnet (attempted) training result in NaN gradients?
- ゼロから作るDeep Learning ―Pythonで学ぶディープラーニングの理論と実装
ゼロから作るDeep Learning ―Pythonで学ぶディープラーニングの理論と実装
- 作者: 斎藤康毅
- 出版社/メーカー: オライリージャパン
- 発売日: 2016/09/24
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (14件) を見る
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()のencodingにlatin1を指定すると上手くいく。
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レコードある。
各々データとラベルに別れる。
データは１レコードあたり3072個(=1024x3, RGB)ある。
ラベルは１レコードあたり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とする。
dataとsrcは同じ階層にある。
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を返す。
注意！： np.empty()はランダムな数値で初期化するので、以下は間違ってるので使わないでください。暇ができたら修正します。
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バッチずつ訓練するエポックを１回繰り返す。 訓練エラー、訓練精度、テスト精度を算出する。 """ 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が、モデルの保存とモデルの復元で一致している。 同じモデルとテストデータだと、同じ精度が出ることが確認できた。
その他
もしモデルの復元で失敗するときは、モデルの保存を一回した後で、モデルの復元だけ実行したり、 以下のように１行足してみると上手く行くかも。
# 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問題を解いた。
今回は、これよりも少し複雑なナップサック問題を解く。
ナップサック問題とは
Wikipedia によると、ナップサック問題とは次のような問題である。
ナップサック問題は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、 「容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、 ナップサックの容量 Cを超えない範囲でいくつかの品物をナップサックに詰め、 ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。 同じ種類の品物を1つまでしか入れられない場合（xi ∈ {0, 1}）や、 同じ品物をいくつでも入れてよい場合（xi ∈ 0以上の整数）など、いくつかのバリエーションが存在する。
今回は容量Cは無視する。 いくらでも品物を詰め込めるが、価値を最大化しつつ、容積ではなく重さを最小化する。 また同じ品物をいくつでも入れて良いことにする。
個体生成、評価、エリート選出
品物が価値と重さという２つの変数を持つ。 まずはこれらを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'}
個体の評価では、次の３パターンに別れる。
- スコアはないけどパラメーターはある
- スコアもなくてパラメーターもない
- スコアもパラメーターもある
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}
