Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
4
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

posted at

updated at

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

前書き

ここではいきなり実践から入るので、先に、「遺伝的アルゴリズム~理論編~」を参照してください。

やってみよう

 さあ、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}
というすべて1の配列をどのように作り出すか、というものを考えたものである。

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

まずは全体のコードを示す。

コード

GA.py
import random
from decimal import Decimal


GENOM_LENGTH = 20          # 遺伝子情報の長さ
MAX_GENOM_LIST = 200        #遺伝子集団の大きさ
SELECT_GENOM = 10           #エリート遺伝子選択数
INDIVIDUAL_MUTATION = 0.01  #個体突然変異確率
GENOM_MUTATION = 0.01       #遺伝子突然変異確率
MAX_GENERATION = 20        #繰り返す世代数


def genom(length):

    """
    遺伝子をランダムに生成する。
    戻り値は、一個体の遺伝子配列
    """
    genom_list = []
    for i in range(length):
        a = random.randint(0,1)
        genom_list.append(a)
    return genom_list


def evaluation(ga):
    """
    個体の評価関数。
    引数で得られた遺伝子配列から、その合計値を評価値として返している。
    """
    genom_total = sum(ga)
    genom_num = len(ga)
    return Decimal(genom_total) / Decimal(genom_num)


def select_elite(ga,elite_length):
    """
    優秀な個体を取り出す関数。
    """
    sort_result = sorted(ga, reverse=True, key=evaluation)
    result = [sort_result.pop(0) for i in range(elite_length)]
    return result


def crossover(ga_one,ga_second):
    """
    交叉関数。
    引数で与えられた2個体の親から、2個体の子を返している。
    ここでは、二点交叉で遺伝させている。
    """
    genom_list = []
    cross_one = random.randint(0,GENOM_LENGTH)
    cross_second = random.randint(cross_one,GENOM_LENGTH)

    one = ga_one
    second = ga_second

    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:]

    genom_list.append(progeny_one)
    genom_list.append(progeny_second)

    return genom_list


def create_next_generation(ga,ga_elite,ga_progeny):
    """
    次の世代の集団を生成する。
    第一引数で前世代の集団を取得し、
    第2、3引数のエリートと子供を加えて、その分優秀でない個体を取り除いている。
    """
    next_generation_geno = sorted(ga, reverse = False, key = evaluation)

    for i in range(0, len(ga_elite) + len(ga_progeny)):
        next_generation_geno.pop(0)

    next_generation_geno.extend(ga_elite)
    next_generation_geno.extend(ga_progeny)
    return next_generation_geno

def mutation(ga, individual_mutation, genom_mutation):
    """
    突然変異を行う。
    一定確率で個体が突然変異するか選別し、
    引っかかった個体の遺伝子配列要素をまた確率で選別し、
    引っかかった要素を1か0に改変する。
    """
    ga_list = []
    for i in ga:
        if individual_mutation > (random.randint(0,100) / Decimal(100)):
            genom_list = []
            for i_ in i:
                if genom_mutation > (random.randint(0,100)/Decimal(100)):
                    genom_list.append(random.randint(0,1))
                else:
                    genom_list.append(i_)
            ga_list.append(genom_list)
        else:
            ga_list.append(i)

    return ga_list


if __name__ == '__main__':

    current_generation = []    
    for i in range(MAX_GENOM_LIST):
        current_generation.append(genom(GENOM_LENGTH))


    for count_ in range(1,MAX_GENERATION + 1):
        current_evaluation = []

        for i in range(MAX_GENOM_LIST):
            evaluation_result = evaluation(current_generation[i])
            current_evaluation.append(evaluation_result)

        elite_genes = select_elite(current_generation,SELECT_GENOM)

        progeny_gene = []

        for i in range(0,SELECT_GENOM):
            progeny_gene.extend(crossover(elite_genes[i-1],elite_genes[i]))

        next_generation = create_next_generation(current_generation,elite_genes,progeny_gene)
        next_generation = mutation(next_generation,INDIVIDUAL_MUTATION,GENOM_MUTATION)

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

        print ("-----------第{}世代----------".format(count_))
        print ("        Min:{}".format(min_))
        print ("        Max:{}".format(max_))
        print ("        avg:{}".format(avg_))
        print("\n")

        current_generation = next_generation


    print ("最も優れた個体は、{}".format(elite_genes[0]))

概略

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

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

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

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

-----------第20世代----------
        Min:0.9
        Max:1
        avg:0.96875


最も優れた個体は、[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というものはものすごく難解でとっかかりにくいといったイメージがあるそうだ。しかし意外にも、その基礎はおもしろくかつイメージしやすい。この記事で、AIの片鱗を見ることができただろう。あとは君たちのアイデアを導入するだけだ。
 また次で会おう。
 読んでくれてありがとう。

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
4
Help us understand the problem. What are the problem?