Pythonによる人工知能入門２ 「遺伝的アルゴリズム～実践編～」

前書き

　初めまして、機械学習好きの学生です。前回に引き続き、遺伝的アルゴリズムの紹介になります。
ここではいきなり実践から入りますので、先に、「遺伝的アルゴリズム～理論編～」を参照してくだされば理解につながるかと思います。

追記：使用言語　python (内包表記含む)

やってみよう

　さあ、Pythonを使って実際にGAというものを動かしてみましょう。ここでは、Pythonの基礎知識はすでにあるものとして進めていきます。関数は使用しますが、説明が混沌となるのでクラスは使わないでおきます。

ONEMAX問題

　具体的に何をするのか。

　よくある例として、ONEMAX問題が取り上げられますね。これは、
　　　　　　　　　　　　｛1，0，0，1，0，1，1，1，0，0｝
のように、ランダムに「1」か「0」で構成された配列から、
　　　　　　　　　　　　｛1，1，1，1，1，1，1，1，1，1｝
というすべて１の配列をどのように作り出すか、というものを考えたものです。

　
　これをGAで解決します。流れとしては「1」か「0」を要素に持った配列をたくさんランダムに生成して、その一つ一つを個体の遺伝子情報とし、配列の合計値を評価基準として、GAアルゴリズムを組みます。

以下に実装コードを示します。

コード

GA.py

import random
from decimal import Decimal


LENGTH = 20                 # length of one genome
GENOME_NUMBER = 200         # number of genomes
ELITE_NUMBER = 10           # number of elites
INDIVIDUAL_MUTATION = 0.01  # properbility of mutation(each component)
GENOME_MUTATAION = 0.01     # properbility of mutation(each genome)
MAX_GENERATION = 30         # number of loop


## creating a new genome.
def GetGenom(length):
    
    GetGenom_list = [random.randint(0,1) for _ in range(length)]
    return GetGenom_list



## to evaluate ability of genome via evaluate function.
def Evaluate(ga):
    
    ## In this time, the evaluate function is average of components.
    ## You should change the function according to your porpose.

    GetGenom_total = sum(ga)
    GetGenom_num = len(ga)
    return Decimal(GetGenom_total) / Decimal(GetGenom_num)



## to get some elites of genome from group.
def GetElite(ga,GetElite_length):
    
    sort_result = sorted(ga, reverse=True, key=Evaluate)
    result = [sort_result.pop(0) for i in range(GetElite_length)]
    return result


## to get child or children from elites.
def Crossover(one,second):
    
    ## In this time, this function can get two genomes from two elites as parents.
    ## There are many ways to crossover and get new genome from elites, so you shuold choose proper one according to your porpose.
    
    GetGenom_list = []
    cross_one = random.randint(0,LENGTH)
    cross_second = random.randint(cross_one,LENGTH)

    progeny_one = one[:cross_one] + second[cross_one:cross_second] + one[cross_second:]
    progeny_second = second[:cross_one] + one[cross_one:cross_second] + second[cross_second:]

    GetGenom_list.append(progeny_one)
    GetGenom_list.append(progeny_second)

    return GetGenom_list



## Creating next generation group of genomes.
## The first argument is last group, second argument is eiltes, and third argument is group of children. 
def CrateGeneration(ga,ga_GetElite,ga_progeny):
    

    next_generation_geno = sorted(ga, reverse = False, key = Evaluate)

    for i in range(0, len(ga_GetElite) + len(ga_progeny)*2):
        next_generation_geno.pop(0)

    next_generation_geno.extend(ga_GetElite)
    for i in range(len(ga_progeny)):
        
        next_generation_geno.extend(ga_progeny[i])
    return next_generation_geno



# to mutate genome compornent along to mutation probability (In this code, all probability are 0.01)
def Mutation(ga, individual_mutation, GENOME_MUTATAION):

    ga_list = []
    for i in ga:
        if individual_mutation > (random.randint(0,100) / Decimal(100)):
            GetGenom_list = []
            for i_ in i:
                if GENOME_MUTATAION > (random.randint(0,100)/Decimal(100)):
                    GetGenom_list.append(random.randint(0,1))
                else:
                    GetGenom_list.append(i_)
            ga_list.append(GetGenom_list)
        else:
            ga_list.append(i)

    return ga_list





if __name__ == '__main__':

    ## Creating first generatino.
    current_generation = [GetGenom(LENGTH) for _ in range(GENOME_NUMBER)]
    
    

    ## GA loop
    for count_ in range(1,MAX_GENERATION + 1):
        
        current_Evaluate = [Evaluate(current_generation[i]) for i in range(GENOME_NUMBER)]
        GetElite_genes = GetElite(current_generation,ELITE_NUMBER)
        progeny_gene = [Crossover(GetElite_genes[i-1],GetElite_genes[i]) for i in range(ELITE_NUMBER)]

        next_generation = CrateGeneration(current_generation,GetElite_genes,progeny_gene)
        next_generation = Mutation(next_generation,INDIVIDUAL_MUTATION,GENOME_MUTATAION)

        fits = []
        j = 0
        for i in current_generation:
            fits.append(current_Evaluate[j])
            j = j + 1
        min_ = min(fits)
        max_ = max(fits)
        avg_ = sum(fits) / Decimal(len(fits))

        print ("-----------Generation {}----------".format(count_))
        print ("        Min:{}".format(min_))
        print ("        Max:{}".format(max_))
        print ("        Avg:{}".format(avg_))
        print("\n")

        current_generation = next_generation
        
        


    print ("Result : {}".format(GetElite_genes[0]))

概略

　前回の記事、理論編で示した通りの手順で行っています。
　このプログラムでは、

　　　　　　　　　　１世代あたりの個体数は 200、
　　　　　　　　　　一個体あたりの遺伝子配列の長さは 20、
　　　　　　　　　　繰り返す世代数は 30、
　　　　　　　　　　突然変異確率は、二種とも 1%、
　　　　　　　　　　エリートの選択数は 10、

という値で動かしていますね。もちろんこの値は結果が収束するように自由に決めます。
　基本的に、世代数を多くすればするほど良い個体が出てくるし、遺伝子配列の長さが大きいほど準最適解への収束速度は遅くなる特徴があります。

　そしてこれを実行すると、、、

-----------Generation 30----------
        Min:0.95
        Max:1
        Avg:0.951


Result : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

のように出力され、見事ONEMAX問題を解いた！！
（最後の数行のみ記載。）

これがGAの力です！！

課題

　さて、これでGAがどういったものか、そしてその力を理解できたことかと思います。そこで、この記事を用いて学習してくださってる方々に少しでも理解を深めてもらおうという思いで僭越ながら練習問題を提示させて頂きます。

⑴上のコードから突然変異の処理を除いたものを作成し実行せよ。またその結果を考察せよ。
⑵最適解を、
　　　　　　　　　　　　　　　｛1,0,1,0,1,0,1,0,..........0,1｝
　のように、「1」と「0」が交互に並ぶような個体であるとしてGAを組め。

以上になります。

まとめ

この記事を最後まで読んでくださってありがとうございます。機械学習、ないしはAIの片鱗を見ることができたと思います。

参考
[https://qiita.com/ksk001100/items/0f527a72270430017d8d]