遺伝子アルゴリズム

まだ、ぼんやりとしか理解できていませんが

URL:https://xaro.hatenablog.jp/entry/2013/12/28/011236

に記載されていた遺伝子アルゴリズムを紹介します。

import random

def eval_func(solution_list):
    """
    遺伝子リストから何かを評価する
    enumeate:列挙する、
    """
    return sum([value * pow(-1,ind) for (ind,value) in enumerate(solution_list)])

def geneticoptimize(domain,costf,maximize=False,popsize=50,step=1, mutprob=0.2,elite=0.2,maxiter=100):
    """
    domain : 変数の領域
例えば [(0,100)]*10 とすると0から100の10変数のリストで行う
    costf : 評価函数 ここが肝
    maximize : Trueにすると最大化 デフォルトは最小化
    popsize : 遺伝子の個数 デフォルトは50
    step : 突然変異の変化量 デフォルトは1
    mutprob : 突然変異の確率 デフォルトは0.2
    elite : 生き残る遺伝子の割合 デフォルトは0.2
    maxiter : 繰り返し回数 デフォルトは100
    """
    # 突然変異
    def mutate(vec):
        i = random.SystemRandom().randint(0,len(domain)-1)
        mut = random.SystemRandom().choice(range(1,step + 1))
        if random.SystemRandom().random() < 0.5 and (vec[i] - mut) > domain[i][0]:
            return vec[0:i] + [vec[i] - mut] + vec[i+1:]
        elif (vec[i] + mut) < domain[i][1]:
            return vec[0:i] + [vec[i] + mut] + vec[i+1:]
        else:
            return vec

    # 1点交叉 非推奨
    """
    １つの交叉点が選ばれます、染色体の先頭から交叉点までのバイナリー文字列が１つめの親からコピーされます。
    残りの部分は２つ目の親からコピーされます。下は親1と２を入れ替えた対の形です。
    11001011+11011111 ⇒ 11001111
    """
    def one_point_crossover(r1,r2):
        i = random.SystemRandom().randint(1,len(domain)-2)
       
        return random.SystemRandom().choice((r1[0:i] + r2[i:], r2[0:i] + r1[i:]))

    # 2点交叉
    """
    ２つの交叉点が選ばれ、染色体の先頭からはじめの交叉点までが、１つ目の親からコピーされます。
    はじめの交叉点から２つめの交叉点までが２つめの親からコピーされます。残りは１つめの親からコピーされます。
    11001011 + 11011111 ⇒ 11011111
    """
    def two_point_crossover(r1,r2):
        i, j = sorted(random.SystemRandom().sample(range(len(domain)),2))
        return random.SystemRandom().choice((r1[0:i] + r2[i:j] + r1[j:] , r2[0:i] + r1[i:j] + r2[j:]))

    # 一様交叉
    """
    両方の親からランダムにビットがコピーされます。
    11001011 + 11011101 ⇒ 11011111
    """
    def uniform_crossover(r1, r2):
        q1 = r1.copy()
        q2 = r2.copy()
        for i in range(len(r1)):
            if random.SystemRandom().random() < 0.5:   # 0.5より小さい時だけコピーが入れ替わる。
                q1[i], q2[i] = q2[i], q1[i]
       
        return random.SystemRandom().choice([q1,q2])

    # 初期遺伝子プールの作成
    pop=[]
    for i in range(popsize):
        vec = [random.SystemRandom().randint(domain[i][0],domain[i][1]) for i in range(len(domain))]   # それぞれが0～100のランダムな整数10個
        pop.append(vec)

    # 生き残る遺伝子の個数（生き残る率ｘ遺伝子の数⇒小数点以下は切り捨て）
    topelite = int(elite * popsize)

    # 交叉アルゴリズムの選択（一様交差を選択）
    #crossover = two_point_crossover
    crossover = uniform_crossover

    # Main loop
    for i in range(maxiter):
        scores=[(costf(v),v) for v in pop]
        scores.sort()
        if maximize:
            scores.reverse()
        ranked = [v for (s,v) in scores]

        # 弱い遺伝子は淘汰される
        pop = ranked[0:topelite]

        # 生き残った遺伝子同士で交叉したり突然変異したり
        while len(pop) < popsize:
            if random.SystemRandom().random() < mutprob:
                # 突然変異
                c = random.SystemRandom().randint(0,topelite)
                pop.append(mutate(ranked[c]))

            else:
                # 交叉
                c1 = random.SystemRandom().randint(0,topelite)
                c2 = random.SystemRandom().randint(0,topelite)
                pop.append(crossover(ranked[c1],ranked[c2]))
        # 暫定の値を出力
        #print(scores[0][0])
        print(scores[0])

    return scores[0]

# 実行
domain = [(0,100)]*10
ans = geneticoptimize(domain, eval_func, maximize=True,
                    popsize=50,step=1, mutprob=0.2,elite=0.3,maxiter=100)
print("Ans:",ans)      

================================================================

207, [75, 71, 68, 39, 70, 35, 71, 20, 98, 10])
(248, [83, 15, 38, 0, 88, 60, 71, 5, 48, 0])
(293, [83, 5, 68, 39, 85, 35, 66, 16, 92, 6])
(347, [83, 5, 75, 39, 85, 12, 94, 16, 92, 10])
(349, [75, 2, 75, 0, 88, 12, 94, 6, 47, 10])
(364, [83, 2, 75, 39, 85, 12, 94, 6, 92, 6])
(396, [100, 5, 68, 0, 85, 12, 94, 16, 92, 10])
(408, [83, 2, 75, 0, 88, 12, 90, 6, 92, 0])
(428, [100, 2, 75, 0, 88, 12, 94, 6, 97, 6])
(429, [100, 2, 75, 0, 88, 12, 94, 6, 97, 5])
(429, [100, 2, 75, 0, 88, 12, 94, 6, 97, 5])
(431, [100, 5, 75, 0, 88, 12, 94, 6, 97, 0])
(434, [100, 2, 75, 0, 88, 12, 94, 6, 97, 0])
(434, [100, 2, 75, 0, 88, 12, 94, 6, 97, 0])
(436, [100, 2, 75, 0, 88, 12, 95, 6, 98, 0])
(436, [100, 2, 75, 0, 88, 12, 95, 6, 98, 0])
(437, [100, 2, 75, 0, 88, 12, 95, 5, 98, 0])
(438, [100, 1, 75, 0, 88, 12, 94, 5, 99, 0])

・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

480, [100, 1, 89, 0, 99, 4, 99, 1, 99, 0])
(481, [100, 1, 88, 0, 99, 2, 99, 1, 99, 0])
(481, [100, 1, 88, 0, 99, 2, 99, 1, 99, 0])
(482, [100, 1, 89, 0, 99, 2, 99, 1, 99, 0])
(483, [100, 1, 90, 0, 99, 2, 99, 1, 99, 0])
(483, [100, 1, 90, 0, 99, 2, 99, 1, 99, 0])
(483, [100, 1, 90, 0, 99, 2, 99, 1, 99, 0])
Ans: (483, [100, 1, 90, 0, 99, 2, 99, 1, 99, 0])