(Python) 遺伝的アルゴリズムの解説&実装してみた！

こんにちは

初めまして！tarokuと申します！
今回がQiita初投稿で、記事書く時に使うMarkDown記法とかもよー分からんのですが、フィーリングで頑張ります！

記念すべき初回は、遺伝的アルゴリズム(GA)を実装してみようと思います！
よろしくお願いします～

目次

解説パート

遺伝的アルゴリズム(GA)って何？
遺伝的アルゴリズムの流れ

実装パート

いろいろ設定
適応度関数
選択
交叉
突然変異
GAを動かしてみよう！
コード全容

～解説パート～

遺伝的アルゴリズム(GA)って何？

遺伝的アルゴリズムは最適化アルゴリズムです。
なんかの設計みたいなことがしたい時に、GAを使えばうまーくいくかもしれませんってやつです。

じゃあ遺伝的って何や、生物が関係するんか？って思った方は鋭いです！
GAは生物が子孫を作って進化していく（最適化していく）様子をマネした計算方法なんです。

生物はRPGみたいに「進化するぜ！」といって進化するのではなく、
ある親から遺伝や突然変異で偶然強い子供が生まれた時、その子供が強いから生き残って、大人になって、さらに生まれる子供も強くて・・・ってな感じで進化していきます。
そんな感じで強いやつが生き残り、弱いやつがやられる「自然淘汰」を何世代もすることで、その過程が進化という現象として観測されるんですね。

それをマネしたのが、遺伝的アルゴリズムです！
強いやつ同士選んで子供を作ったり、突然変異させたりを繰り返すことで最終的に最適な設計を目指します。

それを踏まえて、次に、どういう計算の流れになっているのか説明します！

遺伝的アルゴリズムの流れ

まずは用語の説明をします。
・世代数
→繰り返しの回数

・個体
→生物みたいなやつ。一世代に100体とか1000体とか。遺伝子と適応度を持つ。

・遺伝子
→最適化したいやつ。今回の実装では英単語当てゲームをするので、アルファベットを使いました。

・適応度関数
→個体の強さ（適応度）を測るやつ。スカウター。

遺伝的アルゴリズムで重要な操作は以下の3つです。
・選択　　：強いやつを優先的に選ぶ
・交叉　　：二個体間で子孫を作る
・突然変異：遺伝子が偶然変わる
選択・交叉・突然変異の仕様は実装パートでもう少し説明します。

それを踏まえて、遺伝的アルゴリズムはこんな感じです。
①個体生成(N体)
②適応度関数で適応度を測る
③2体選択＋交叉 or 一体選択+突然変異 or 一体選択
④③をN体になるまで繰り返し、個体集団をアップデートする
⑤②～④を最大世代数まで繰り返す
⑥一番適応度が高いやつが最適解！

アルゴリズムの詳細はWikipediaを見るのをおススメします笑

https://ja.wikipedia.org/wiki/遺伝的アルゴリズム

～実装パート～

遺伝的アルゴリズムについての理解が済んだところで、実装に入っていきたいと思います！

今回実装するのは、文字当てゲームです。
用意したアルファベットの文字列に、できるだけ近い文字列を出力するように最適化していきます。

例えば、"super"という文字列を用意します。
"super"と"abcde"は全然ちがいますよね？
"super"と"abcdf"も全然ちがいます。
"super"と"abcdr"は"r"が一致したので少し近づきました。
じゃあ"abcer"は...

みたいな感じでだんだん"super"という単語に近づけていけるのかやっていきます。
当然、全く同じ文字列（上の例では"super"）が最適解ですが、GAは最適解を出力できるのでしょうか？

まずは必要なライブラリをimportしたり、定数を設定したりします。

いろいろ設定

GA.py

import random
import Levenshtein as lev
import bisect
import matplotlib.pyplot as plt

alphabets = ("a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z")
answer = "supercalifragilisticexpialidocious"

alphabetsが今回の遺伝子です。
answerが今回当てる文字列です。
"supercalifragilisticexpialidocious"
ちなみにこれで一単語みたいです。どうやって読むんだろ。

次にGAをclassで定義して__init__(self)を作ります。

初期化

GA.py クラスGA

class GA():
    def __init__(self):
        self.mutation_rate = 0.01 #突然変異率
        self.num = 100 #一世代あたりの個体数
        self.generation = 10000 #総世代数
        self.manurate = (0.5, 0.8, 1.0) #交叉:突然変異:選択 確率の累積和表現
        self.tech = "two" # tech="two"->two-point crossover tech="bin"->binary crossover　交叉手法の選択
        self.get_data_freq = 100 #データ取得の頻度。これだと100世代に一回
        
        self.indivisuals_list = [] #ある世代の個体たちのリスト
        self.indivisuals_eval_list = [] #ある世代の個体たちの適応度のリスト
        
        self.average_eval_list = [] #データを取得した世代の個体たちの平均適応度
        
        #初期個体集団生成 ランダムだよーん
        for i in range(100):
            indivisual = ""
            for j in range(len(answer)):
                char = random.choice(alphabets)
                indivisual += char
            self.indivisuals_list.append(indivisual)

これで第1世代の100個体が誕生しました～
おめでたい

適応度関数

次に適応度関数を定義します。
二つの文字列がどれだけ似ているかを測る関数はいろいろあるみたいなんですが、
今回はよく使われていそうだったLevenshtein距離っていうのを使ってみます。
全く同じだと0,全然違うと文字列の長さを出力するみたいです。

詳しくはwikiさんに聞いてください。
Levenshtein距離について

https://ja.wikipedia.org/wiki/レーベンシュタイン距離

GA.py クラスGA

    def Eval(self):
        for i in self.indivisuals_list:
            self.indivisuals_eval_list.append(len(answer)-lev.distance(answer,i)+1)
        return

Evalはanswerに設定した文字列と個体たちがどれくらい似ているかを数値で出力し、
結果を self.indivisuals_eval_list というリストに格納します。
「選択」手法の関係上、強いやつほどでかい適応度を持つ必要があるので、文字列長からLevenshtein距離を引いた値を適応度関数に設定しました。（ここで適応度が常に正になるような関数にしましょう）

適応度関数が定義できたところで、「選択」「交叉」「突然変異」の実装に移ります。

選択

選択は強いやつを優先的に選ぶ操作です。さっきつくった適応度関数でもとめた適応度が強さってことですね。
選択手法にはルーレット選択、ランキング選択、トーナメント選択などがあるのですが、今回はルーレット選択を採用してみました。
ここはむずいんで注意しましょう！

GA.py クラスGA

    def Choose(self):
        acc = []
        accval = 0
        for i in self.indivisuals_eval_list:
            accval += i
            acc.append(accval)
        randval = accval*random.random()
        chosen = bisect.bisect(acc, randval)
        
        return chosen

ルーレット選択は、値がでかいやつにでかい当選確率を持たせたルーレットを回して選択するやり方です。
累積和という考え方を利用して実装します。

①まず、各個体の適応度の累積和をリストに格納していきます。
②次に全個体の適応度の合計に0~1の乱数を掛けます。
③最後に適応度の累積和のリストに上の値で探索をかければ完了です。

self.indivisuals_eval_list に先ほどの適応度関数によって求めた、すべての個体の適応度が格納されています。
accは累積和のリストです。

例えば、
self.indivisuals_eval_list = [1,2,3,4,5]
の時、
acc = [1,3,6,10,15]
になります。（①）
0~1のランダムな値を0.6とすると
15×0.6 = 9 （②）
accの中で6と10の間に入るので、[1,2,3,4←こいつ,5]　が選ばれました（③）
って感じです。

以上がルーレット選択でした！

交叉

交叉は二個体を組み合わせて新たな個体を作る操作です。
よく使われる交叉手法に、二点交叉と一様交叉があります。
今回はどちらも実装します！

GA.py クラスGA

    def Cross(self):
    # tech="two"->two-point crossover 
    # tech="bin"->binary crossover
        a = self.Choose()
        b = self.Choose()
        
        A = self.indivisuals_list[a]
        B = self.indivisuals_list[b]
        
        if self.tech == "two":
            p1 = random.randint(0,len(A))
            p2 = random.randint(0,len(A))
            if p2<p1:
                p1,p2 = p2,p1
                
            C = A[:p1]
            D = B[:p1]
            C += B[p1:p2]
            D += A[p1:p2]
            C += A[p2:]
            D += B[p2:]
        
        if self.tech == "bin":
            C = ""
            D = ""
            for i in range(len(A)):
                if random.random()<=0.5:
                    C += A[i]
                    D += B[i]
                else:
                    C += B[i]
                    D += A[i]
        
        return C,D

二個体をさっきの方法で選択して交叉を行い、二つの子個体を出力する関数です。
initのところで設定した self.tech で交叉手法を選択します。
twoだと二点交叉、binだと一様交叉になります。

より詳細が気になる方はWikipediaをチェックするのが良いと思います！

https://ja.wikipedia.org/wiki/遺伝的アルゴリズム

以上、交叉でした！

突然変異

突然変異はある低確率で遺伝子が変わって受け継がれるやつです。
これのおかげでGAは広い解空間を探索することができるようになります。

GA.py クラスGA

    def Mutate(self):
        a = self.Choose()
        A = self.indivisuals_list[a]
        B = ""
        
        for i in A:
            if random.random() <= self.mutation_rate:
                x = random.choice(alphabets)
                B += x
            else:
                B += i
                
        return B

こんなもんかな。突然変異でしたー

GAを動かしてみよう！

すべての部品が完成したのでこれらを組み合わせてGAを動かしていこうと思います。
コードどん

GA.py クラスGA

    def GA_exe(self):
        for i in range(self.generation):
            self.Eval()
            
            if (i+1)%self.get_data_freq == 0: 
                print("genarion = "+str(i+1))
                print("max_eval = "+ str(max(self.indivisuals_eval_list)))
                print("str = "+ self.indivisuals_list[self.indivisuals_eval_list.index(max(self.indivisuals_eval_list))])
                print("\n")
                self.average_eval_list.append(sum(self.indivisuals_eval_list)/self.num)
                
            n = 0
            next_indivisuals_list = []
            
            while n<100:
                rand = random.random()
                #cross
                if rand <= self.manurate[0]:
                    (A,B) = self.Cross()
                    next_indivisuals_list.append(A)
                    n+=1
                    if n!=100:
                        next_indivisuals_list.append(B)
                        n+=1
                        
                #mutate
                if (rand > self.manurate[0]) and (rand <= self.manurate[1]):
                    A = self.Mutate()
                    next_indivisuals_list.append(A)
                    n+=1
                    
                #choose
                if rand > self.manurate[1]:
                    a = self.Choose()
                    next_indivisuals_list.append(self.indivisuals_list[a])
                    n+=1
            
            self.indivisuals_list = next_indivisuals_list
            self.indivisuals_eval_list = []

上で定義した評価、そして、選択、交叉、突然変異を繰り返して世代交代していくかんじです！
選択交叉突然変異のところで、どの操作をするのかは確率的に決定します。
その確率はself.manurate で設定しています。

最後に実行と適応度をプロットする用のコードを書いて

GA.py

ga = GA()
ga.GA_exe()

x = [i*ga.get_data_freq for i in range(len(ga.average_eval_list))]
y = ga.average_eval_list
plt.plot(x, y)
plt.show()

実行！

こんな感じで適応度が上がっていく様子が確認できました。

世代数は10000, 個体数は100, 交叉は一様交叉で実験してます。

最終世代で出力した最適解はこちらです。
"suzpercblifragilisticepialiiocious"←GAが出した解
"supercalifragilisticexpialidocious"←正解

薄眼で見たら同じです！

コード全容

GA.py

import random
import Levenshtein as lev
import bisect
import matplotlib.pyplot as plt

alphabets = ("a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z")
answer = "supercalifragilisticexpialidocious"

class GA():
    def __init__(self):
        self.mutation_rate = 0.01 #突然変異率
        self.num = 100 #一世代あたりの個体数
        self.generation = 10000 #総世代数
        self.manurate = (0.5, 0.8, 1.0) #交叉:突然変異:選択 確率の累積和表現
        self.tech = "bin" # tech="two"->two-point crossover tech="bin"->binary crossover　交叉手法の選択
        self.get_data_freq = 100 #データ取得の頻度。これだと100世代に一回
        
        self.indivisuals_list = [] #ある世代の個体たちのリスト
        self.indivisuals_eval_list = [] #ある世代の個体たちの適応度のリスト
        
        self.average_eval_list = [] #データを取得した世代の個体たちの平均適応度
        
        #初期個体集団生成
        for i in range(100):
            indivisual = ""
            for j in range(len(answer)):
                char = random.choice(alphabets)
                indivisual += char
            self.indivisuals_list.append(indivisual)
            
    def Eval(self):
        for i in self.indivisuals_list:
            self.indivisuals_eval_list.append(len(answer)-lev.distance(answer,i)+1)
        return
        
    def Choose(self):
        acc = []
        accval = 0
        for i in self.indivisuals_eval_list:
            accval += i
            acc.append(accval)
        randval = accval*random.random()
        chosen = bisect.bisect(acc, randval)
        return chosen
    
    def Cross(self):
    # tech="two"->two-point crossover 
    # tech="bin"->binary crossover
        a = self.Choose()
        b = self.Choose()
        
        A = self.indivisuals_list[a]
        B = self.indivisuals_list[b]
        
        if self.tech == "two":
            p1 = random.randint(0,len(A))
            p2 = random.randint(0,len(A))
            if p2<p1:
                p1,p2 = p2,p1
                
            C = A[:p1]
            D = B[:p1]
            C += B[p1:p2]
            D += A[p1:p2]
            C += A[p2:]
            D += B[p2:]
        
        if self.tech == "bin":
            C = ""
            D = ""
            for i in range(len(A)):
                if random.random()<=0.5:
                    C += A[i]
                    D += B[i]
                else:
                    C += B[i]
                    D += A[i]
        
        return C,D
    
    def Mutate(self):
        a = self.Choose()
        A = self.indivisuals_list[a]
        B = ""
        
        for i in A:
            if random.random() <= self.mutation_rate:
                x = random.choice(alphabets)
                B += x
            else:
                B += i
                
        return B
    
    def GA_exe(self):
        for i in range(self.generation):
            self.Eval()
            
            if (i+1)%self.get_data_freq == 0: 
                print("genarion = "+str(i+1))
                print("max_eval = "+ str(max(self.indivisuals_eval_list)))
                print("str = "+ self.indivisuals_list[self.indivisuals_eval_list.index(max(self.indivisuals_eval_list))])
                print("\n")
                self.average_eval_list.append(sum(self.indivisuals_eval_list)/self.num)
                
            n = 0
            next_indivisuals_list = []
            
            while n<100:
                rand = random.random()
                #cross
                if rand <= self.manurate[0]:
                    (A,B) = self.Cross()
                    next_indivisuals_list.append(A)
                    n+=1
                    if n!=100:
                        next_indivisuals_list.append(B)
                        n+=1
                        
                #mutate
                if (rand > self.manurate[0]) and (rand <= self.manurate[1]):
                    A = self.Mutate()
                    next_indivisuals_list.append(A)
                    n+=1
                    
                #choose
                if rand > self.manurate[1]:
                    a = self.Choose()
                    next_indivisuals_list.append(self.indivisuals_list[a])
                    n+=1
            
            self.indivisuals_list = next_indivisuals_list
            self.indivisuals_eval_list = []


ga = GA()
ga.GA_exe()

x = [i*ga.get_data_freq for i in range(len(ga.average_eval_list))]
y = ga.average_eval_list
plt.plot(x, y)
plt.show()