進化的アルゴリズム・遺伝的アルゴリズム

Image from Gyazo

ノートブックの作成

Jupyter Notebook を起動し,新規にノートブックを作成してください. ノートブックのタイトルは AI-10 とします. ノートブックの作成方法は第1回の資料を参照してください.

フロイド問題

今回は フロイド問題(Floyd Problem) を取り上げましょう.

フロイド問題

1から10までの整数を$A$と$B$の2つのグループに分ける. このとき,各グループの整数の平方根の和を求め,その差の絶対値を目的関数$g(A,B)$とする. この目的関数が最小となるグループ$A$,$B$を求めよ. 例えば,グループ$A$を奇数,グループ$B$を偶数とするとき, 目的関数の値は$1.24$となる. $$ A=\{1, 3, 5, 7, 9\} $$ $$ B=\{2, 4, 6, 8, 10\} $$ $$ f(A) = \sqrt{1} + \sqrt{3} + \sqrt{5} + \sqrt{7} + \sqrt{9} \simeq 10.61 $$ $$ f(B) = \sqrt{2} + \sqrt{4} + \sqrt{6} + \sqrt{8} + \sqrt{10} \simeq 11.85 $$ $$ g(A, B) = |f(A) - f(B)| \simeq 1.24 $$

遺伝的アルゴリズム

フロイド問題を 遺伝的アルゴリズム(Genetic Algorithm) で解きます. 遺伝的アルゴリズムは,進化的アルゴリズムの一つに分類され, 進化の仕組みを参考に開発されたアルゴリズムです. ネーミングがとてもキャッチーなこともあり,とても人気のあるアルゴリズムです. 問題の解は,数値の列で構成される 個体 として表現され,この個体を複数生成し 世代 と呼びます. この世代で,突然変異交叉 と呼ばれるオペレータ(操作)を適用して, 新しい個体を生成し,次の世代とすることを繰り返します.

フロイド問題では,整数がグループAに属するとき$0$, グループBに属するとき$1$とする数値列を個体とします. 例えば,グループ$A$を奇数,グループ$B$を偶数とするとき, 個体$I_1$は下記のように表現されます.

$$ I_1 = (0, 1, 0, 1, 0, 1, 0, 1, 0, 1) $$

この他にも,グループ$A$を1〜5,グループ$B$を6〜10とするとき, 個体$I_2$は下記のように表現されます.

$$ I_2 = (0, 0, 0, 0, 0, 1, 1, 1, 1, 1) $$

突然変異 は個体に含まれる$n$番目の数値をランダムに変化させ, 新しい個体を生成する操作のことです. 例えば,個体$I_1$の5番目の数値を$0$から$1$に変化させます.

$$ (0, 1, 0, 1, 0, 1, 0, 1, 0, 1) \rightarrow (0, 1, 0, 1, 1, 1, 0, 1, 0, 1) $$

交叉 は複数の個体を繋ぎ合わせて,新しい個体を生成する操作のことです. 例えば,個体$I_1$の前半と,個体$I_2$の後半の数値を繋ぎ合わせます.

$$ (0, 1, 0, 1, 0, 1, 0, 1, 0, 1) \times (0, 0, 0, 0, 0, 1, 1, 1, 1, 1) \rightarrow (0, 1, 0, 1, 0, 1, 1, 1, 1, 1) $$

実装

クラスの定義

最初にライブラリをインポートします. 探索問題の型 を表すSearchPrblem遺伝的アルゴリズム を表す genetic をインポートします. この他にも,数値計算のための Numpy と, オブジェクトのコピーのための copy もインポートします.

import numpy as np
import copy
from simpleai.search import SearchProblem
from simpleai.search.local import genetic

次に 対象とする整数 と,初期状態 を定義します. 初期状態は,全ての整数がグループ$A$に属することとします.

NUMBERS = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
START = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

インポートしたSearchProblemクラスをオーバライドして, フロイド問題を表す FloydProblem を定義します. オーバライドするメソッドは,valuegenerate_random_statecrossovermutate の4種類です.

class FloydProblem(SearchProblem):

    def value(self, state):
        ...

    def generate_random_state(self):
        ...     

    def crossover(self, state1, state2):
        ...

    def mutate(self, state):
        ...

value(self, state)

状態state の目的関数を実装します. フロイド問題は目的関数を最小化する必要がありますが, ここでは目的関数を負の値で表し,最大化を目的とした問題として扱います.

def value(self, state):

    value0 = 0
    value1 = 0

    for n, s in zip(NUMBERS, state):
        if s == 0:
            value0 += np.sqrt(n)
        else:
            value1 += np.sqrt(n)

    value = -1 * np.abs(value0 - value1) # 負の値

    return value

generate_random_state(self)

ランダムに状態を生成します. 生成した乱数が0.5未満であればグループA, 0.5以上であればグループBとします.

def generate_random_state(self):

    state = []

    for n in NUMBERS:
        if np.random.rand() < 0.5:
            state.append(0)
        else:
            state.append(1)        

    return state

crossover(self, state1, state2)

状態state1と状態state2を交叉し,新しい状態を生成します. 交差する位置は乱数で決定します.

def crossover(self, state1, state2):

    child = []

    index = np.random.randint(0, len(state1))

    for i in range(0, index):
        child.append(state1[i])

    for i in range(index, len(state2)):
        child.append(state2[i])                

    return child

mutate(self, state)

状態stateを突然変異させ,新しい状態を生成します, 突然変異する位置は乱数で決定します.

def mutate(self, state):

    mutated = copy.deepcopy(state)                                

    index = np.random.randint(0, len(mutated))

    if mutated[index] == 0:
        mutated[index] = 1
    else:
        mutated[index] = 0                                     

    return mutated

解の探索

上記の実装だと最良解の推移がわからないため,下記のコードをvalue関数に追加します. 目的関数が最大の状態と値を記録し,更新があったときに表示します,

def value(self, state):

    ...

    # ここから
    global max_state
    global max_value

    if max_value < value:
        max_state = state
        max_value = value            
        print("max state: {}({:.3f})".format(max_state, max_value))
    # ここまで追加

    return value

遺伝的アルゴリズムgeneticを用いて解を探索します ここで,population_sizeは1世代の個体の数,mutation_chanceは突然変異の確率,iterations_limitは世代交代の数です.

max_state = START
max_value = 0
for n in NUMBERS:
    max_value += -1 * np.sqrt(n)
print("max state: {}({:.3f})".format(max_state, max_value))

problem = FloydProblem(initial_state=START)
result = genetic(problem, population_size=100, mutation_chance=0.5, iterations_limit=100)

この結果,目的関数が$-0.015$に収束します. これは,下記のグループに分けられたことを意味しています(AとBが逆の場合も同じ).

$$ A = \{ 1, 2, 3, 4, 6, 7 \} $$

$$ B = \{ 5, 8, 9, 10 \} $$

max state: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0](-22.468)
max state: [1, 1, 1, 1, 0, 1, 0, 0, 0, 0](-5.277)
max state: [0, 1, 0, 0, 0, 0, 1, 1, 1, 1](-3.633)
max state: [1, 1, 1, 0, 1, 0, 0, 0, 0, 1](-3.379)
max state: [1, 0, 0, 1, 1, 0, 1, 1, 0, 0](-1.048)
max state: [1, 1, 0, 0, 0, 0, 1, 0, 1, 1](-0.024)
max state: [1, 0, 0, 1, 1, 0, 0, 1, 0, 1](-0.015)
max state: [0, 0, 0, 0, 1, 0, 0, 1, 1, 1](-0.015)

参考書籍