How to implement Genetic Algorithm with python / 遺伝的アルゴリズムをPythonで実装する


モチベーション

以前子供たちと一緒にめんぼうで遺伝的アルゴリズムを実装しました。その内容をPythonプログラムとして実装することでより一層理解を深めたいと思い始めました。

https://loochs.org/session36-asobi-workshop/

そもそも遺伝的アルゴリズムとは?

以下の書籍が非常に参考となります。今回の実装もこちらに基づいております。

ソースコード

実際の実装は以下リンク先から参照してください。

https://github.com/kichinosukey/GA-Question

サンプルコード

3つの3択問題についての解答を試行するGAになります。

import numpy as np
from lib import crossover, evaluate, gen_population, select, mutation
if __name__ == '__main__':
    answer = [1, 2, 3]
    num_question = len(answer)
    num_survive = 3
    num_population = 5
    population = gen_population(num_population, num_question, (min(answer), max(answer)))
    score_dict = {idx:sum(evaluate(answer, result)) for idx, result in population.items()}
    score_list_sorted = sorted(score_dict.items(), reverse=True, key=lambda x: x[1])
    
    print(score_list_sorted[0])
    cnt = 0
    while score_list_sorted[0][1] != 3:
        
        score_list_selected = select(score_list_sorted, num_survive)
        idx_selected = [t[0] for t in score_list_selected]
        population_selected = [population[idx] for idx in idx_selected]
        pop01 = population[score_list_sorted[0][0]]
        pop02 = population[score_list_sorted[1][0]]
        crv_point = np.random.randint(1, num_question-1)
        new01, new02 = crossover(pop01, pop02, crv_point)
        new01 = mutation(new01, (1, 4))
        new02 = mutation(new02, (1, 4))
        population_selected.append(new01)
        population_selected.append(new02)
        population = population_selected[:]
        population = {i:pop for i, pop in enumerate(population)}
        score_dict = {idx:sum(evaluate(answer, result)) for idx, result in population.items()}
        score_list_sorted = sorted(score_dict.items(), reverse=True, key=lambda x: x[1])       
        print(score_list_sorted[0])
        cnt += 1
        if cnt > 100:
            print(population)
            break

設計コンセプト

遺伝的アルゴリズムは大まかに以下の4つの処理を繰り返していきます。

  • 解候補の生成
  • 各解候補の評価
  • 優秀な解候補の選別
  • 新規解候補の生成(交叉・変異)

以下に各処理に関連するメソッドを載せておきます。

解候補の生成

generateでは単一の候補が決められた範囲内(range_ans)からint型の解を生成します。次にgen_populationでは解候補を指定数生成して各候補ごとにgenerateで解を生成します。

def generate(number_question, range_ans):
    """Generate answer array for questions
    
    Args:
        number_question(int):
        range_ans(tuple):
    
    Returns:
        (np.array):
    """
    return np.random.randint(range_ans[0], range_ans[1], number_question)
def gen_population(num_population, num_question, range_ans):
    """Generate population
    
    Args:
        num_population(int): number of population
        num_question(int): number of question
        range_ans(tuple): range of answers, only supported int
    
    Returns:
        (dict):{index: answer_array}
    """
    return {i:list(generate(num_question, range_ans)) for i in range(num_population)}

各解候補の評価

各候補の解と生成した解を比較して候補ごとの評価を下します。

def evaluate(answer, generated):
    """Evaluate answer array
    
    Args:
        answer(list): answer array
        generated(list): generated array
    """
    result = []
    for a, b in zip(answer, generated):
        if a == b:
            match = 1
        else:
            match = 0
        result.append(match)
    return result

優秀な解候補の選別

evaluateを使って候補ごとにスコアが出たので次の世代に残したい候補数(num_survive)を上位から順に確保しておきます。

def select(score_list, num_survive):
    """Selection method
    
    Args:
        score_list(list):
        num_survive(int): number of survival candidate
    
    Returns:
        (list)
    """
    return score_list[:num_survive]

新規解候補の生成(交叉・変異)

交叉と変異の実装です。簡易的なものなのでここは工夫のしがいがあります。今後の伸び代としてとっておきます。

def mutation(arr, range_mut):
    """Mutation
    Args:
        arr(list): array for mutation
        range_mut(tuple/list): range value for mutation
    """
    idx_max_mut = len(arr)
    idx_mut = np.random.randint(0, idx_max_mut)
    arr[idx_mut] = np.random.randint(range_mut[0], range_mut[1])
    return arr
def crossover(arr_01, arr_02, crv_point):
    """Cross over
    Args:
        arr(list):
        crv_point(int): cross over point
    Returns:
        (tuple)
    
    """
    arr_01_left = arr_01[:crv_point]
    arr_01_right = arr_01[crv_point:]
    arr_02_left = arr_02[:crv_point]
    arr_02_right = arr_02[crv_point:]
    arr_01_new = arr_01_left + arr_02_right
    arr_02_new = arr_02_left + arr_01_right
    return arr_01_new, arr_02_new

最後に

実は以前にの簡単なGAの実装に試みたことがあったのですがうまくいきませんでした。前回との違いはアソビワークショップで綿棒実装したことでかなり理解が深まっていたものと思います。今後の課題としては適用可能な問題が整数型の選択問題に限ったものなのでその適用範囲を広げるといった試みは必要かと思います。

そういえば変異を実装せずに一度サンプルスクリプトを動かしてみるとなかなか解が収束しない状況に陥りました。やはり候補の多様性というのが遺伝子の生き残りにおいては重要な要素なのだと改めて実感した次第です。