遺伝的アルゴリズム
遺伝的アルゴリズムの例
①初期の遺伝子プール(個体群)を決める
②一定確率で遺伝子を交差させ、個体数を２倍にする
③一定確率で突然変異を起こす
④重みづけをして評価し、生き残る個体を選ぶ
⑤一定回数または目標値に達するまで②に戻る
16桁の2進数の数を正解として、遺伝的アルコリズムで正解をさがす例。
import matplotlib.pyplot as plt import numpy as np import random def mating(pool): """ランダムに選ばれる両親から交差し、個体数を2倍にする。 子のみのnewpoolを戻り値とする""" newpool = [] for i in range(len(pool)): p1, p2 = random.choice(pool), random.choice(pool) # 遺伝子が交差する地点を一か所選ぶ crosspoint = int(random.random()*16) div = pow(2, crosspoint) # 遺伝子を交差させて入れ替える f1 = (p1 // div)*div + p2 % div f2 = (p2 // div)*div + p1 % div newpool += [f1, f2] return newpool def mutation(pool): "突然変異。20％の個体に、1部位の突然変異が起きる" for i in range(len(pool)//5): p_index = int(random.random()*len(pool)) p1 = pool[p_index] mutate_point = int(random.random()*16) bit = pow(2, mutate_point) # bitを１つだけ反転させる p_bit = p1 & bit # p1 = p1 - p_bit + (bit - p_bit) p1 = p1 + bit - p_bit * 2 pool[p_index] = p1 return def selection(pool) ->list: "2倍に増えた個体数をもとに自然淘汰する。上位から40％、下位から10％を残す" evaluate = [] for i in pool: e = 16 - bin((i^d)).count("1") evaluate.append( (i, e) ) evaluate.sort(key=lambda x:x[1], reverse=True) # 上位と下位に分ける l = len(evaluate) upper, lower = evaluate[:l//2], evaluate[l//2:] # random.shuffleはin placeで戻り値はNone random.shuffle(upper) random.shuffle(lower) survived = upper[:int(l*0.4)] + lower[:data_size - int(l*0.4)] return [i for i, e in survived] def random_selection(pool): "自然淘汰をせずにランダムで個体を残す" random.shuffle(pool) return pool[:data_size] def print_evaluate(pool, generation, flag): """合致するビット数を評価 flat=True のときは、各個体の評価を表示. flag=False のときは、世代数と平均のみ表示""" evaluate = [] for i in pool: evaluate.append(16 - bin((i^d)).count("1")) if flag: for i, e in zip(pool, evaluate): print(bin(i)[2:].zfill(16),":", e) print("第{}世代".format(generation), end=" ") score = sum(evaluate)/len(evaluate) print("平均:", score, "\n"*flag) return score def main(pool, select=True, print_flag=True): "世代を重ねるメインループ" generation = 0 score = [] score.append(print_evaluate(pool, generation, print_flag)) for i in range(40): pool = mating(pool) mutation(pool) if select: pool = selection(pool) else: pool = random_selection(pool) generation += 1 score.append(print_evaluate(pool, generation, print_flag)) return score if __name__ == "__main__": d = 0b0101011000001111 data_size = 20 # initialize #pool = [int(random.random()*256) for i in range(data_size)] pool = np.random.randint(65536, size=data_size, dtype=int) pool2 = pool.copy() scores = main(pool, select=True, print_flag=False) scores2 = main(pool2, select=False, print_flag=False) x = np.arange(len(scores)) plt.plot(x, np.array(scores)/16, "-", label="selection") plt.plot(x, np.array(scores2)/16, ":", label= "without selection") plt.legend(fontsize=14) plt.ylim(0, 1)
print_flag=Trueとすると、各世代の個体を表示。
1001100010111001 : 6 1000000011110001 : 4 1001000111110001 : 4 1000100010001001 : 7 1000000011110001 : 4 1001100011110001 : 4 1001000111110001 : 4 1001000111110001 : 4 1000000010111010 : 6 1001000011010001 : 6 1001000111110001 : 4 1001100010111010 : 6 1001000010111011 : 8 1001000111110001 : 4 1001000110110001 : 5 1001100010111011 : 7 1000000010101001 : 7 1001000110110000 : 4 1001000011111010 : 6 0011000010110001 : 6 第40世代 平均: 5.3
print_flag=Falseとすると、各世代の平均のみ表示
第0世代 平均: 8.4 第1世代 平均: 9.25 第2世代 平均: 10.85 第3世代 平均: 10.95 第4世代 平均: 11.7 第5世代 平均: 12.2 ・・・ 第37世代 平均: 15.9 第38世代 平均: 15.95 第39世代 平均: 16.0 第40世代 平均: 15.8
今回の例だと20世代ほどでほぼ正解に辿りついている。
課題：
numpyの2進数の扱い方がよくわからず、あまり使えていない。
それ以前にpythonで2進数をどう扱うか勉強が必要。
特定のbitだけ演算をする方法を調べ中。
bit演算の優先順位なども頭に入れないと。
自然選択なしで、多数の試行を重ねて結果をヒストグラムなりにしても面白そう。
NumPyのboolで
無理にビット演算をするのをやめて、NumPyのdtype=boolで書き直してみた。
import matplotlib.pyplot as plt import numpy as np import random def mating(pool): """ランダムに選ばれる両親から交差し、個体数を2倍にする。 子のみのnewpoolを戻り値とする""" newpool = [] for i in range(data_size): # ランダムで親を選ぶ p1, p2 = random.choice(pool), random.choice(pool) # 遺伝子が交差する地点を一か所選ぶ crosspoint = int(random.random()*16) f1 = np.hstack((p1[:crosspoint], p2[crosspoint:])) f2 = np.hstack((p2[:crosspoint], p1[crosspoint:])) # 遺伝子を交差させて入れ替える newpool += [f1, f2] return np.array(newpool) def mutation(pool): "突然変異。20％の個体に、1部位の突然変異が起きる" for i in range(len(pool)//5): p_index = int(random.random()*len(pool)) p1 = pool[p_index] mutate_point = int(random.random()*16) p1[mutate_point] = ~p1[mutate_point] pool[p_index] = p1 return def selection(pool): "2倍に増えた個体数をもとに自然淘汰する。上位から40％、下位から10％を残す" # 正解数で降順にソート pool = sorted(pool, key=lambda x:(x==d).sum(), reverse=True) # 上位と下位に分ける l = len(pool) upper, lower = pool[:l//2], pool[l//2:] # random.shuffleはin placeで戻り値はNone random.shuffle(upper) random.shuffle(lower) # 上位から80%,下位から20％選ぶ survived = np.vstack((upper[:int(l*0.4)], lower[:data_size - int(l*0.4)])) return survived def random_selection(pool): "2倍に増えた個体数から自然淘汰をせずにランダムで個体を残す" random.shuffle(pool) return pool[:data_size] def print_evaluate(pool, generation, flag): """合致する数を評価 flat=True のときは、各個体ごとの評価を表示. flag=False のときは、世代数と平均のみ表示""" # 正解数をカウント evaluate = (pool==d).sum(axis=1) # 表示フラグがTrueなら各個体を表示 if flag: for i, e in zip(pool, evaluate): print(i, ":", e) # flagに関係なく、各世代の平均を表示 print("第{}世代".format(generation), end=" ") score = sum(evaluate)/(data_size * 16) print("平均:", score, "\n"*flag) return score def main(pool, select=True, print_flag=True): "世代を重ねるメインループ" generation = 0 score = [] score.append(print_evaluate(pool, generation, print_flag)) for i in range(20): pool = mating(pool) mutation(pool) if select: # 自然淘汰ありのとき pool = selection(pool) else: # 自然淘汰なしのとき pool = random_selection(pool) generation += 1 score.append(print_evaluate(pool, generation, print_flag)) return score if __name__ == "__main__": # initialize d = np.array([0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1], dtype=bool) data_size = 20 pool = np.random.randint(0, 2, (data_size, 16), dtype=bool) pool2 = pool.copy() # 自然淘汰あり scores = main(pool, select=True, print_flag=True) # 自然淘汰なし scores2 = main(pool2, select=False, print_flag=False) # グラフ表示 x = np.arange(len(scores)) plt.plot(x, np.array(scores), "-", label="selection") plt.plot(x, np.array(scores2), ":", label= "without selection") plt.legend(fontsize=14) plt.ylim(0, 1) plt.title("Genetic Argorithm", fontsize=14) plt.show()
