Remrinのpython攻略日記

python3に入門しました。python3についてあれこれとサンプルコードとか。

遺伝的アルゴリズム

遺伝的アルゴリズムの例
 
①初期の遺伝子プール(個体群)を決める
②一定確率で遺伝子を交差させ、個体数を2倍にする
③一定確率で突然変異を起こす
④重みづけをして評価し、生き残る個体を選ぶ
⑤一定回数または目標値に達するまで②に戻る
 
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を1つだけ反転させる
        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 : 640世代 平均: 5.3 

 
print_flag=Falseとすると、各世代の平均のみ表示

0世代 平均: 8.41世代 平均: 9.252世代 平均: 10.853世代 平均: 10.954世代 平均: 11.75世代 平均: 12.2 
・・・
第37世代 平均: 15.938世代 平均: 15.9539世代 平均: 16.040世代 平均: 15.8 

 
f:id:rare_Remrin:20170528222725p:plain
 
今回の例だと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()