概要

遺伝的アルゴリズムって名前は聞くけど、そういえば実装したことなかったなと思い、Pythonで実装してみました。

特に目新しい要素はないですが、自分のメモの為に書いておきます。

遺伝的アルゴリズム

遺伝的アルゴリズムは、ある問題に対する解の候補を遺伝子に見立て、それを交叉したり突然変異させたりして最適解を求めるアルゴリズムです。

既に様々な研究が行われている分野なので、詳しい説明はWikipediaの遺伝的アルゴリズムのページを見た方が参考になります。

扱う問題

今回は遺伝的アルゴリズムでOne Max問題を解くためのプログラムを実装しました。

One Max問題と書くと面倒くさそうに見えますが、実際はとても単純で、0と1で表された

[1,0,0,1,0]

といった配列があった場合、

[1,1,1,1,1]

のように配列の中身を全て1にするのがこの問題の目的です。

アルゴリズムの流れ

ランダムにN個の現世代の個体群を生成
現世代の各個体の適応度を計算して、最も適応度の高い個体をエリートとして保存
交叉 or 突然変異で次世代のN個の個体群を生成
現世代と次世代の個体群の中から適応度の高いN-1個を選択
4.で選択したN-1個と2.で選択したエリートを新たに現世代とし、2.に戻る
3.～6.の操作をG回繰り返し、最終的に最も適応度の高い個体を解として出力

それぞれのステップをコードを示しながら簡単に説明していきます。ソースコード全体はこちらに置いておくので興味がある人は見てみてください。

1. ランダムにN個の現世代の個体群を生成

population = []
for i in range(n):
    arr = [random.randint(0, 1) for j in range(dim)]
    population.append(arr)

最初にランダムに個体をN個生成して、populationに保存します。

2. 各個体の適応度を計算・エリート選択

def calc_score(x):
    return sum(x)

def find_elite(population):
    score = map(lambda x: calc_score(x), population)
    max_val = -1
    max_index = None

    for i, val in enumerate(score):
        if val > max_val:
            max_val = val
            max_index = i

    return copy.deepcopy(population[max_index])

populationの各個体のスコアをscoreに格納して、その中からスコアが最も高い個体を返します。

今回はOne Max問題なので、スコアは個体中の1の数です。他の問題を扱う場合は、calc_scoreの中身を書き換えれば大丈夫です。

3. 交叉 or 突然変異で次世代のN個の個体群を生成

def cross(parent1, parent2):
    length = len(parent1)
    r1 = int(math.floor(random.random() * length))
    r2 = r1 + int(math.floor(random.random() * (length - r1)))

    child = copy.deepcopy(parent1)
    child[r1:r2] = parent2[r1:r2]

    return child


def mutate(parent):
    r = int(math.floor(random.random() * len(parent)))
    child = copy.deepcopy(parent)
    child[r] = (parent[r] + 1) % 2

    return child

crossが交叉のための関数です。今回は2点交叉という方法を用いました。

2点交叉とは、親を2つ取り、それぞれの親の遺伝子のある区間を入れ替えるというものです。イメージとしては下図のようになります。（画像はWikipediaの遺伝的アルゴリズムのページより引用）

f:id:phoro3:20161013110620p:plain CC BY-SA 3.0, Link

プログラムでは、始点r1と終点r2をランダムに選び、その区間の値を入れ替えたものを子として返しています。

mutateは突然変異のための関数です。やっていることはシンプルで、親の遺伝子から1箇所を選択し、その箇所の値を反転させます。

4. 現世代と次世代の個体群の中から適応度の高いN-1個を選択

def select(num, population):
    selection = []
    score = map(lambda x:calc_score(x), population)
    total = sum(score)
    for i in range(n):
        threshold = math.floor(random.random() * total)
        sum_score = 0
        for index, val in enumerate(score):
            sum_score += val
            if sum_score > threshold:
                selection.append(population[index])
                break

    return selection

ここでは、ルーレット選択を用いてpopulation中からnum個だけ個体を選択します。

ルーレット選択とは重みをつけた上で、ランダムに選択を行うことです。ここでは各個体の適応度を重みとしています。

基本的には適応度が高い個体の方が選択されやすいですが、ランダム性があるので適応度が低い個体もある程度は選択されます。これによって、適応度が高い個体を保ちつつも、個体群の多様性を保つことができます。

実行結果

長さ10の配列でプログラムを実行した結果を示します。各世代で適応度が最大の個体を出力しています。

Generation: 1
[1, 1, 0, 1, 1, 1, 1, 1, 0, 1]

Generation: 2
[1, 1, 0, 1, 1, 1, 1, 1, 0, 1]

Generation: 3
[1, 1, 0, 1, 1, 1, 1, 1, 0, 1]

Generation: 4
[1, 1, 0, 1, 1, 1, 1, 1, 0, 1]

Generation: 5
[1, 1, 0, 1, 1, 1, 1, 1, 0, 1]

Generation: 6
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]

Generation: 7
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]

Generation: 8
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]

Generation: 9
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]

Generation: 10
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]

Generation: 11
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]

Generation: 12
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]

Generation: 13
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]

Generation: 14
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]

Generation: 15
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]

Generation: 16
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

一番最初は配列の3番目と9番目が0ですが、第6世代で9番目が16世代で3番目が1になってることが分かると思います。

まとめ

とても単純な問題で遺伝的アルゴリズムを実装してみました。今回は慣れるのが目的だったので、単純な実装にしました。

しかし、遺伝的アルゴリズムは様々な研究が行われている分野なので、交叉方法や次世代の個体の選択方法は今回扱った以外にもたくさんあります。時間があったらそちらも調べてみたいと思います。

SHIROBAKO大好き人間のブログ

SHIROBAKOが好きなエンジニアによる技術ブログ

遺伝的アルゴリズムの実装

概要