目次
- 「ゴチ」バトルの問題
- ナップサック問題と両替問題
- 準備
- Python で問題を解く
- ファイルを読み込んで問題を解く
- 遺伝的アルゴリズムを実装する
- 参考資料
「ゴチ」バトル
遺伝的アルゴリズムを実装する
ここでの「ゴチ」バトルの問題では，ortoolpy モジュールによって簡単かつ高速に解くことができた．しかし，定式化が異なった類似の問題が必ずしも ortoolpy モジュールで解けるとは限らないので，ここでは遺伝的アルゴリズムを実装して「ゴチ」バトルの問題を解いてみよう．
遺伝的アルゴリズムとは
遺伝的アルゴリズム (Genetic Algorithm: GA) はメタヒューリスティクスのひとつであり，生物の進化過程をシミュレーションすることで，多数の組み合わせの中から最適な解を見つけ出すことができるアルゴリズムです．遺伝的アルゴリズムでは 0 と 1 の値を持つ遺伝子 (gene) からなる染色体 (chromosome) を考えます．つまりここでは，一つひとつの料理を注文するかどうかの 0-1 変数が遺伝子になり，すべての（注文しないという情報も含まれる）注文リストが染色体になります．
遺伝的アルゴリズムでは染色体（注文リスト）の集まりを集団 (population) とよび，この集団に対して交叉 (crossover)，突然変異 (mutation)，選択 (selection) という操作を繰り返します．交叉とは集団内の2つの染色体の組において，遺伝子の一部を入れ替えることです．突然変異とは，各染色体において，ある確率で一部の遺伝子が 0 から 1 へ，あるいは 1 から 0 へ変化することを言います．さらに，選択は交叉と突然変異を経た染色体の集団および元の染色体の集団のうち，環境へのより高い適応性をもつもの（つまり，目的の予算により近い注文リスト）が次世代に選択されることを言います．
ここで「ゴチ」バトルの問題を解くための遺伝的アルゴリズムは具体的には次のようになります．
- Step 1:
- \(size\) 個の染色体からなる初期集団 \(P\) を生成する．
- Step 2:（交叉）
- 集団 \(P\) をランダムに並べ替え，順に取り出した2つの染色体ごとにそれらを組み合わせて新たな解の集団 \(Q_1\) を生成する．
- Step 3:（突然変異）
- 集団 \(P\) と \(Q_1\) を複製した集団 \(Q_2\) を作成し，集団 \(Q_2\) から遺伝子をランダムにいくつか選び，遺伝子の情報を変化させる．
- Step 4:（選択）
- 集団の集合 \(P \cup Q_1 \cup Q_2\) から目的の予算により近い順に \(size\) 個を選択し，次世代の集団 \(P\) とする．
- Step 5:
- 終了条件を満たせば目的関数最良値となる染色体を出力して終了．そうでなければ Step 2 に戻る．
上の遺伝的アルゴリズムにおいて第 \(n\) 世代の集団 \(P\) が第 \(n+1\) 世代の集団 \(P\) に進化するイメージを図にすると，次のようになります．なお，価格の配列は \(w = [50, 60, 70, 80, 90, 100]\) とし，目標金額 は \(c = 280\) としています．
遺伝的アルゴリズムの実装
以下には「ゴチ」バトルの問題を解くために遺伝的アルゴリズムを実装したコードを示します．
遺伝的アリゴリズムで問題を解くimport numpy as np
def crossover(Qx, size, length):
"""
行列 Qx に対して，奇数行と偶数行の交叉を行う．
具体的には，乱数で決めた point より右側の遺伝子配列を奇数行と偶数行で入れ替えることで交叉を行う．
size : 集団の長さ
length: 染色体の長さ
point: 交叉の場所 (1 <= point <= length-1)
"""
point = rng.integers(0, length) # 交叉の場所を乱数で
Qro = Qx[0:size:2, point:length].copy() # 奇数(odd)行で pointから右側の情報を取り出す
Qre = Qx[1:size:2, point:length].copy() # 偶数(even)行で pointから右側の情報を取り出す
# 入れ替え
Qx[0:size:2, point:length] = Qre # 偶数行の右側に奇数行の右側の値をコピー
Qx[1:size:2, point:length] = Qro # 奇数行の右側に偶数行の右側の値をコピー
return Qx
def mutation(Qx, size, length, p):
"""
行列 Qx を突然変異させる
size : 集団の長さ
length: 染色体の長さ
p: 突然変異の確率
"""
# 突然変異を起こす行列を生成（この行列要素が1の場所にある遺伝子を反転させる）
mutation_matrix = rng.choice(2, (size*2, length), p=[1-p, p])
# Qx を突然変異させる
### 条件付きのブロードキャストを使う
### もしも突然変異行列の値が 0 より大（つまり1）なら， 1-Qx で反転させる．それ以外は Qx のまま
Qx = np.where(mutation_matrix > 0, 1 - Qx, Qx)
return Qx
##### パラメータ設定
# 重量（価格）
weight = np.array([928, 598, 880, 1180, 598, 1280, 1860,
2580, 788, 2588, 898, 898, 598, 698,
698, 980, 1280, 880, 1000, 498, 698,
498, 398, 598, 680, 980, 550, 880,
1180, 880, 1180, 398, 598, 625])
# ナップサックの容量（予算）
capacity = 14800
# 染色体の長さ
length = len(weight)
# 集団の長さ（偶数にする）
size = 100
# 繰り返し回数
max_gens = 500
# 初期化の確率
prob_init = 0.1
# 突然変異の確率（あまりに小さいと，解に近いところから動かなくなる）
prob_mutation = 0.2
# 乱数列の初期化
rng = np.random.default_rng()
# rng = np.random.default_rng(1) ## 再現性を持たせたい場合
# 複合データ型を定義
tp = np.dtype([ ('total', 'i8'), ('err', 'i8'), ('x', 'i8', length)])
# 定義した複合データ型を利用して，3つの要素からなる構造化配列をゼロで初期化
X = np.zeros(size*4, dtype=tp)
###############################
# Step 1
# ただし，size*4 個を作成し，ソートした上位 size 個を初期集団 P としています
###############################
# 染色体の初期化
X_init = rng.choice(2, (size*4, length), p=[1-prob_init, prob_init])
# 構造化配列の染色体に初期値を設定
X['x'] = X_init
# 行列の積の形式で一気に求める
X['total'] = np.dot(X['x'], weight)
# 目標価格との差の絶対値を求める（これがゼロになれば解を発見したことになる）
X['err'] = np.abs(capacity - X['total'])
# 構造化配列のソート（誤差の絶対値を基準に）
X = np.sort(X, order='err')
# GAメインの始まり-----------------------
for gen in range(0, max_gens):
# P は先頭の size 個
P = X['x'][0:size].copy()
###############################
# Step 2
###############################
# Q1 は P をランダムに並べ替えてコピー
Q1 = rng.permutation(P)
# Q1 を交差させる
Q1 = crossover(Q1, size, length)
###############################
# Step 3
###############################
# Q2 を作る（P と Q1 をコピー）
Q2 = np.concatenate([P, Q1])
# Q2 の突然変異させる
Q2 = mutation(Q2, size, length, prob_mutation)
# 構造化配列 X の中身が「P, Q2, Q1」の順になるように再構築する
X['x'][size:size*3] = Q2
X['x'][size*3:] = Q1
###############################
# Step 4
###############################
# 行列の積の形式で一気に求める
X['total'] = np.dot(X['x'], weight)
# 誤差を求める
X['err'] = np.abs(capacity - X['total'])
# 構造化配列のソート
X = np.sort(X, order='err')
# 途中経過の表示
# print(gen, X[0][['total', 'err']])
###############################
# Step 5
###############################
# 終了判定
if X[0]['err'] == 0:
break
if X[0]['err'] == 0:
print('解が見つかりました')
print(X[0], ', 世代数:', gen)
print(np.where(X[0]['x'] > 0, weight, 0))
else:
print('解が見つかりませんでした．世代数:', gen)
解が見つかりました
(14800, 0, [0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0]) , 世代数: 45
[ 0 0 880 0 0 1280 0 2580 788 2588 0 0 598 0
0 0 1280 0 1000 498 698 0 0 0 0 0 550 880
1180 0 0 0 0 0]
上のコードを実行するたびに（合計金額が14800円になるという）制約を満たす異なる注文リストが得られるはずです．また，上のコードの Step 5 (124行目から129行目) の処理では，制約を満たす解が見つかった時点で計算を終了しています．この処理を行わず計算を継続すると，制約を満たす複数の解を見つけることができるようになります（133行目の X[0] を X に置き換えるとすべての染色体を表示できます）．さらに，Step 4 においてすべての遺伝子の組み合わせが同一である染色体が集団内に複数含まれ，集団内の多様性が損なわれてしまう場合があります．この問題を解決するには，Step 4 において，同一の染色体は1個体のみを次世代の集団に残すような処理を追加すると良いでしょう．
NumPy 配列を用いずに Python のリストと繰り返し処理を使って記述することも可能ですが，その処理速度は遅くなることが予想されます．上のコードは NumPy 配列と次のような NumPy の各種メソッドを活用することで動作が遅い繰り返しを徹底的に排除しています．慣れるまでは難しいかもしれませんが，一つひとつがどのような処理であるかをじっくり読み解いてください．
この結果，Python リストと繰り返しを使った場合よりも（この問題のサイズの場合では）10倍以上の速度で計算が可能になっています（この問題の実験では Python リストが平均 214ms，上のコードが 18.2msとなり11.5倍の速度でした）．特に，NumPy の構造化配列を使っていることにより遺伝的アルゴリズムの Step 4（選択）でのソートが非常に簡単かつ高速に行えるようになっています．（Python で複数のリストをあるリストを基準に全てソートすることはコーディングが面倒で，さらに処理速度の面でも不利になります．）