morikomorou’s blog

自分が学んだことなどの備忘録的なやつ

トップ > Python > 【python】遺伝的アルゴリズム(Genetic Algorithm)を実装してみる

【python】遺伝的アルゴリズム(Genetic Algorithm)を実装してみる

Python 最適化


はじめに

遺伝的アルゴリズムとは、生命の進化過程を模したアルゴリズムです。
ランダム性を利用した非常に簡単なロジックのアルゴリズムですが、最適化問題に広く使われております。

以下のスライドが非常に詳しく説明されていたので、大変参考になりました。
https://www.slideshare.net/kzokm/genetic-algorithm-41617242

今回はこのスライドをベースに遺伝的アルゴリズムを実装してみたいと思います。




遺伝的アルゴリズム

遺伝的アルゴリズムでは最適化問題の解の候補を遺伝子として表現します。
そして異なる遺伝子を持った個体を複数用意します(世代)。
世代内で各個体の適応度(最適化問題におけるの評価値)を計算し、適応度が低いものを淘汰します。
世代内の適応度が高いものを優先して取り出し、遺伝子を混ぜ合わせたり、突然変異させたりして、次の世代を作成します。
これを繰り返してどんどん世代を進めることで遺伝子が最適解に近づいていくという手法です。

例題

今回は遺伝的アルゴリズムを使ってOneMax問題を解いてみたいと思います。
OneMax問題とは、0と1からなる n個の数列の和が最大となるような数列を探し出すことです。
すごく簡単で、すべての要素が1であればそれが理論上の最適解であることがわかります。
これを遺伝的アルゴリズムを使用して、ちゃんと最適解を求められるかやってみたいと思います。

実装

遺伝的アルゴリズムのフローは下記のとおりです。

  1. 初期世代の作成
  2. 世代の各個体の適応度の評価
  3. 選択/淘汰
  4. 交叉
  5. 突然変異
  6. 任意の世代に進むまで2から繰り返し

それでは、上記の説明を踏まえながら実装していきます

初期世代の作成

まずは個体の定義からです。
今回の問題は0と1からなる n個の数列の和を最大化する問題なので、遺伝子を0と1からなる n個の数列として定義します。
そしてこの遺伝子を持つ個体をIndividualというクラスとして定義しておきます。
クラスメソッドには、その個体の適応度を計算するためのメソッド及び、適応度を出力するためのメソッドを入れています。
適応度の計算は遺伝子の和をとるだけですね。

import numpy as np


class Individual:
    '''各個体のクラス
        args: 個体の持つ遺伝子情報(np.array)'''
    def __init__(self, genom):
        self.genom = genom
        self.fitness = 0  # 個体の適応度(set_fitness関数で設定)
        self.set_fitness()

    def set_fitness(self):
        '''個体に対する目的関数(OneMax)の値をself.fitnessに代入'''
        self.fitness = self.genom.sum()

    def get_fitness(self):
        '''self.fitnessを出力'''
        return self.fitness

このIndividualクラスオフジェクトを複数作成して、リストにしてまとめたものを初期世代とします。
初期状態では何が最適解かわからないので、初期世代の各個体の遺伝子は0と1をランダムに n個並べた数列を入れておきます。

def create_generation(POPURATIONS, GENOMS):
    '''初期世代の作成
        input:
            POPURATIONS: 1世代の個体数
            GENOMS: 遺伝子の長さ(n)
        return: 初期世代の個体クラスのリスト'''
    generation = []
    for i in range(POPURATIONS):
        individual = Individual(np.random.randint(0, 2, GENOMS)) # ランダムに0,1を並べた数列を作成
        generation.append(individual)
    return generation

np.random.seed(seed=65)
# param
POPURATIONS = 100  # 1世代の個体数
GENOMS = 50             # 遺伝子の長さ(n)

# create first genetarion
generation = create_generation(POPURATIONS, GENOMS)

これで初期世代generationが完成しました。




世代の各個体の適応度の評価

ここから世代の更新のループに入るので、今後のフローの部分までまとめて雛形を書いてしまいます。
各個体の適応度は個体クラスを作成した際に自動で計算されるようにしているので、特に何もする必要はありません。
ここでは各世代における最高の適応度と最低の適応度をとりあえずプリントするようにしてます。

def ga_solve(generation):
    '''遺伝的アルゴリズムのソルバー
        return: 各世代の最高適応度をまとめたリスト、最低適応度をまとめたリスト'''
    best = []
    worst = []
    # --- Generation loop
    print('Generation loop start.')
    for i in range(GENERATIONS):
        # --- Step1. Print fitness in the generation
        best_ind = max(generation, key=Individual.get_fitness)
        best.append(best_ind.fitness)
        worst_ind = min(generation, key=Individual.get_fitness)
        worst.append(worst_ind.fitness)
        print("Generation: " + str(i) \
                + ": Best fitness: " + str(best_ind.fitness) \
                + ". Worst fitness: " + str(worst_ind.fitness))

        # --- Step2. Selection

        # --- Step3. Crossover

        # --- Step4. Mutation

    print("Generation loop ended. The best individual: ")
    print(best_ind.genom)
    return best, worst


# param
GENERATIONS = 20  # 繰り返す世代数

# solve
best, worst = ga_solve(generation)

まだ何も世代を更新できてないので結果は省きます。

選択

先ほど作成したga_solve関数をいじっていきます。
選択では適応度の高いものを'ランダム性を交えつつ'抽出するという操作を行います。
手法は下記3つがよく使われるようです。

  • ルーレット選択: 適応度に応じて重みをつけて、ランダムに選ぶ(適応度が高いほど選ばれやすい)
  • トーナメント選択: ランダムに数個選び、その中で適応度が一番高いものを選ぶ
  • エリート選択: 世代の中で適応度上位~個をそのまま選ぶ

ルーレット選択、トーナメント選択をそれぞれ実装したものが以下になります。
選択により、適応度の高いものを重複ありで POPURATIONS 個選択します。

def select_roulette(generation):
    '''選択の関数(ルーレット方式)'''
    selected = []
    weights = [ind.get_fitness() for ind in generation]
    norm_weights = [ind.get_fitness() / sum(weights) for ind in generation]
    selected = np.random.choice(generation, size=len(generation), p=norm_weights)
    return selected


def select_tournament(generation):
    '''選択の関数(トーナメント方式)'''
    selected = []
    for i in range(len(generation)):
        tournament = np.random.choice(generation, 3, replace=False)
        max_genom = max(tournament, key=Individual.get_fitness).genom.copy()
        selected.append(Individual(max_genom))
    return selected

まずはルーレット方式を選んでおきましょう。

def ga_solve(generation):
    '''遺伝的アルゴリズムのソルバー
        return: 最終世代の最高適応値の個体、最低適応値の個体'''
    ...略...
        # --- Step2. Selection (Roulette)
        selected = select_roulette(generation)
    ...略...

交叉

ここでも先ほど作成したga_solve関数をいじっていきます。
交叉では選択によって抽出された個体の遺伝子の掛け合わせを行います。
手法は下記がよく使われるようです。

  • 1点交叉
  • 2点交叉

1点交叉はなんかあんまりよくないようなので2点交叉を実装しておきます。
交叉の手法の説明は冒頭で引用しているスライドがすごく詳しいのでそちらでチェックお願いします。

def cross_two_point_copy(child1, child2):
    '''交叉の関数(二点交叉)
        input: 混ぜ合わせたい個体のペア
        output: 交叉後の個体のペア'''
    size = len(child1.genom)
    tmp1 = child1.genom.copy()
    tmp2 = child2.genom.copy()
    cxpoint1 = np.random.randint(1, size)
    cxpoint2 = np.random.randint(1, size - 1)
    if cxpoint2 >= cxpoint1:
        cxpoint2 += 1
    else:
        cxpoint1, cxpoint2 = cxpoint2, cxpoint1
    tmp1[cxpoint1:cxpoint2], tmp2[cxpoint1:cxpoint2] = tmp2[cxpoint1:cxpoint2].copy(), tmp1[cxpoint1:cxpoint2].copy()
    new_child1 = Individual(tmp1)
    new_child2 = Individual(tmp2)
    return new_child1, new_child2

選択で抽出した個体の遺伝子をそのまま残すか、交叉させるかという点でもランダム性を持たせたいので一定の確率で交叉させるようにします。

def crossover(selected):
    '''交叉の関数'''
    children = []
    if POPURATIONS % 2:
        selected.append(selected[0])
    for child1, child2 in zip(selected[::2], selected[1::2]):
        # 一定の確率で交叉を適用
        if np.random.rand() < CROSSOVER_PB:
            child1, child2 = cross_two_point_copy(child1, child2)
        children.append(child1)
        children.append(child2)
    children = children[:POPURATIONS]
    return children

# param
CROSSOVER_PB = 0.8   # 交叉させる確率(80%)

ga_solve関数も追記しておきます。

def ga_solve(generation):
    '''遺伝的アルゴリズムのソルバー
        return: 最終世代の最高適応値の個体、最低適応値の個体'''
    ...略...
        # --- Step3. Crossover (two_point_copy)
        children = crossover(selected)
    ...略...

突然変異

選択、交叉だけだと局所解に陥りやすくなりますので、一定の確率で遺伝子をランダムに変化させます。
今回は、遺伝子の数列内のどこか1か所の0と1を反転させるという操作とします。
個体自身の遺伝子を書き変える操作なので、Individualクラスのメソッドに追加しておきます。

class Individual:
    '''各個体のクラス
        args: 個体の持つ遺伝子情報(np.array)'''
    ...略...
    def mutate(self):
        '''遺伝子の突然変異'''
        tmp = self.genom.copy()
        i = np.random.randint(0, len(self.genom) - 1)
        tmp[i] = float(not self.genom[i])
        self.genom = tmp
        self.set_fitness()

def mutate(children):
    '''突然変異の関数'''
    for child in children:
        # 一定の確率で突然変異させる
        if np.random.rand() < MUTATION_PB:
            child.mutate()
    return children

def ga_solve(generation):
    '''遺伝的アルゴリズムのソルバー
        return: 最終世代の最高適応値の個体、最低適応値の個体'''
    ...略...
        # --- Step4. Mutation
        generation = mutate(children)
    ...略...

# param
MUTATION_PB = 0.1  # 突然変異させる確率(10%)

これで遺伝的アルゴリズムの実装は完成です。




OneMax問題を解く

実際に動かしてみましょう。
後で全コード載せますが、上記で実装したコードを実行すると下記のように出力されます。

Generation loop start.
Generation: 0: Best fitness: 34. Worst fitness: 19
Generation: 1: Best fitness: 34. Worst fitness: 18
Generation: 2: Best fitness: 35. Worst fitness: 19
Generation: 3: Best fitness: 35. Worst fitness: 19
Generation: 4: Best fitness: 34. Worst fitness: 19
Generation: 5: Best fitness: 37. Worst fitness: 20
Generation: 6: Best fitness: 39. Worst fitness: 20
Generation: 7: Best fitness: 37. Worst fitness: 19
Generation: 8: Best fitness: 36. Worst fitness: 20
Generation: 9: Best fitness: 36. Worst fitness: 23
Generation: 10: Best fitness: 38. Worst fitness: 26
Generation: 11: Best fitness: 37. Worst fitness: 25
Generation: 12: Best fitness: 38. Worst fitness: 26
Generation: 13: Best fitness: 39. Worst fitness: 23
Generation: 14: Best fitness: 40. Worst fitness: 25
Generation: 15: Best fitness: 38. Worst fitness: 27
Generation: 16: Best fitness: 39. Worst fitness: 25
Generation: 17: Best fitness: 39. Worst fitness: 25
Generation: 18: Best fitness: 41. Worst fitness: 24
Generation: 19: Best fitness: 39. Worst fitness: 25
Generation loop ended. The best individual:
[1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 0
 1 1 1 1 1 1 1 0 0 1 1 1 1]

各世代の適応度をプロットした結果はこちらです。

最適解の理論値は50なんですが、最終結果は39と、なんかあまり最適解に近づいていないような感じがします。

トーナメント選択を試してみる

世代が進んでも最高適応度が下がってしまうことが散見されますので、
選択の際にうまく適応度上位のものが選ばれていないということが考えられます。
ですので、追加で実装していたトーナメント方式で選択を行ってみます。

コードの実行結果はこちら

Generation loop start.
Generation: 0: Best fitness: 34. Worst fitness: 19
Generation: 1: Best fitness: 35. Worst fitness: 23
Generation: 2: Best fitness: 37. Worst fitness: 25
Generation: 3: Best fitness: 38. Worst fitness: 28
Generation: 4: Best fitness: 41. Worst fitness: 29
Generation: 5: Best fitness: 43. Worst fitness: 31
Generation: 6: Best fitness: 43. Worst fitness: 34
Generation: 7: Best fitness: 43. Worst fitness: 35
Generation: 8: Best fitness: 46. Worst fitness: 37
Generation: 9: Best fitness: 46. Worst fitness: 38
Generation: 10: Best fitness: 47. Worst fitness: 40
Generation: 11: Best fitness: 47. Worst fitness: 43
Generation: 12: Best fitness: 48. Worst fitness: 44
Generation: 13: Best fitness: 49. Worst fitness: 44
Generation: 14: Best fitness: 49. Worst fitness: 45
Generation: 15: Best fitness: 50. Worst fitness: 45
Generation: 16: Best fitness: 50. Worst fitness: 46
Generation: 17: Best fitness: 50. Worst fitness: 48
Generation: 18: Best fitness: 50. Worst fitness: 48
Generation: 19: Best fitness: 50. Worst fitness: 48
Generation loop ended. The best individual:
[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1]

各世代の適応度をプロットした結果はこちらです。


最大適応度、最小適応度ともに世代が進むにつれて最適解に近づいていることがわかります。
最大適応度のほうは最適解を15世代目くらいですでに求められていますね！

全コード

先程のグラフの描画を含む全コードは以下です。




import numpy as np
import matplotlib.pyplot as plt


class Individual:
    '''各個体のクラス
        args: 個体の持つ遺伝子情報(np.array)'''
    def __init__(self, genom):
        self.genom = genom
        self.fitness = 0  # 個体の適応度(set_fitness関数で設定)
        self.set_fitness()

    def set_fitness(self):
        '''個体に対する目的関数(OneMax)の値をself.fitnessに代入'''
        self.fitness = self.genom.sum()

    def get_fitness(self):
        '''self.fitnessを出力'''
        return self.fitness

    def mutate(self):
        '''遺伝子の突然変異'''
        tmp = self.genom.copy()
        i = np.random.randint(0, len(self.genom) - 1)
        tmp[i] = float(not self.genom[i])
        self.genom = tmp
        self.set_fitness()


def select_roulette(generation):
    '''選択の関数(ルーレット方式)'''
    selected = []
    weights = [ind.get_fitness() for ind in generation]
    norm_weights = [ind.get_fitness() / sum(weights) for ind in generation]
    selected = np.random.choice(generation, size=len(generation), p=norm_weights)
    return selected


def select_tournament(generation):
    '''選択の関数(トーナメント方式)'''
    selected = []
    for i in range(len(generation)):
        tournament = np.random.choice(generation, 3, replace=False)
        max_genom = max(tournament, key=Individual.get_fitness).genom.copy()
        selected.append(Individual(max_genom))
    return selected


def crossover(selected):
    '''交叉の関数'''
    children = []
    if POPURATIONS % 2:
        selected.append(selected[0])
    for child1, child2 in zip(selected[::2], selected[1::2]):
        if np.random.rand() < CROSSOVER_PB:
            child1, child2 = cross_two_point_copy(child1, child2)
        children.append(child1)
        children.append(child2)
    children = children[:POPURATIONS]
    return children


def cross_two_point_copy(child1, child2):
    '''二点交叉'''
    size = len(child1.genom)
    tmp1 = child1.genom.copy()
    tmp2 = child2.genom.copy()
    cxpoint1 = np.random.randint(1, size)
    cxpoint2 = np.random.randint(1, size - 1)
    if cxpoint2 >= cxpoint1:
        cxpoint2 += 1
    else:
        cxpoint1, cxpoint2 = cxpoint2, cxpoint1
    tmp1[cxpoint1:cxpoint2], tmp2[cxpoint1:cxpoint2] = tmp2[cxpoint1:cxpoint2].copy(), tmp1[cxpoint1:cxpoint2].copy()
    new_child1 = Individual(tmp1)
    new_child2 = Individual(tmp2)
    return new_child1, new_child2


def mutate(children):
    for child in children:
        if np.random.rand() < MUTATION_PB:
            child.mutate()
    return children


def create_generation(POPURATIONS, GENOMS):
    '''初期世代の作成
        return: 個体クラスのリスト'''
    generation = []
    for i in range(POPURATIONS):
        individual = Individual(np.random.randint(0, 2, GENOMS))
        generation.append(individual)
    return generation


def ga_solve(generation):
    '''遺伝的アルゴリズムのソルバー
        return: 最終世代の最高適応値の個体、最低適応値の個体'''
    best = []
    worst = []
    # --- Generation loop
    print('Generation loop start.')
    for i in range(GENERATIONS):
        # --- Step1. Print fitness in the generation
        best_ind = max(generation, key=Individual.get_fitness)
        best.append(best_ind.fitness)
        worst_ind = min(generation, key=Individual.get_fitness)
        worst.append(worst_ind.fitness)
        print("Generation: " + str(i) \
                + ": Best fitness: " + str(best_ind.fitness) \
                + ". Worst fitness: " + str(worst_ind.fitness))

        # --- Step2. Selection (Roulette)
        # selected = select_roulette(generation)
        selected = select_tournament(generation)

        # --- Step3. Crossover (two_point_copy)
        children = crossover(selected)

        # --- Step4. Mutation
        generation = mutate(children)

    print("Generation loop ended. The best individual: ")
    print(best_ind.genom)
    return best, worst


np.random.seed(seed=65)

# param
POPURATIONS = 100
GENOMS = 50
GENERATIONS = 20
CROSSOVER_PB = 0.8
MUTATION_PB = 0.1

# create first genetarion
generation = create_generation(POPURATIONS, GENOMS)

# solve
best, worst = ga_solve(generation)

# plot
fig, ax = plt.subplots()
ax.plot(best, label='max')
ax.plot(worst, label='min')
ax.axhline(y=GENOMS, color='black', linestyle=':', label='true')
ax.set_xlim([0, GENERATIONS - 1])
ax.set_ylim([0, GENOMS * 1.1])
ax.legend(loc='best')
ax.set_xlabel('Generations')
ax.set_ylabel('Fitness')
ax.set_title('Tournament Select')
plt.show()

おわりに

かなり簡単なアルゴリズムなのにちゃんと最適解が求まるのはなんだか不思議な感じです。
ほかの最適化問題にも応用してみたいと思います

ランキング参加中
プログラミング