Pythonで遺伝的アルゴリズム

遺伝的アルゴリズムとは

進化的アルゴリズムの１つで、データ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索するアルゴリズム。

今回のアルゴリズムの流れ

OneMax問題の最適化やります。

1. 第1世代の個体群を生成
2. 適応度の高い個体（エリート）を選択
3. エリートの交叉、突然変異により次世代の個体群を生成
4. 2と3を繰り返し、最後に最も適応度の高い個体を解として出力

第1世代の個体群を生成

今回は[4, [0,1,0,0,1,0,1,1,0,0]]のような[適応度, [遺伝子]]のデータ構造で個体を生成していきます。

import random
import copy

# パラメータ
gene_length = 10 # 遺伝子長
individual_length = 10 # 個体数
generation = 20 # 世代数
mutate_rate = 0.1 # 突然変異の確率
elite_rate = 0.2 # エリート選択の割合

def get_population():
    population = []
    for i in range(individual_lenght):
        population.append([random.randint(0,1) for j in range(gene_length)])
    return population

適応度と評価

適応度は配列の総和としているのでsum関数で総和を出します。
評価については適応度が高い順に並べ替えるだけの操作をしています。

def fitness(pop):
    return sum(pop)


def evaluate(pop):
    pop.sort(reverse=True)
    return pop

交叉と突然変異

二点交叉法を使って交叉を実装します。

def two_point_crossover(parent1, parent2):
    r1 = random.randint(0, gene_length-1)
    r2 = random.randint(r1, gene_length-1)
    child = copy.deepcopy(parent1)
    child[r1:r2] = parent2[r1:r2]
    return child


def mutate(parent):
    r = random.randint(0, gene_length-1)
    child = copy.deepcopy(parent)
    child[r] = 1 if child[r]==0 else 0
    return child

コード全体

ga.py

import random
import copy

# パラメータ
gene_length = 10 # 遺伝子長
individual_length = 10 # 個体数
generation = 20 # 世代数
mutate_rate = 0.1 # 突然変異の確率
elite_rate = 0.2 # エリート選択の割合

def get_population():
    population = []
    for i in range(individual_length):
        population.append([random.randint(0,1) for j in range(gene_length)])
    return population


def fitness(pop):
    return sum(pop)


def evaluate(pop):
    pop.sort(reverse=True)
    return pop


def two_point_crossover(parent1, parent2):
    r1 = random.randint(0, gene_length-1)
    r2 = random.randint(r1, gene_length-1)
    child = copy.deepcopy(parent1)
    child[r1:r2] = parent2[r1:r2]
    return child


def mutate(parent):
    r = random.randint(0, gene_length-1)
    child = copy.deepcopy(parent)
    child[r] = 1 if child[r]==0 else 0
    return child


def main():
    # 初期個体生成
    pop = evaluate([(fitness(p), p) for p in get_population()])
    print('Generation: 0')
    print('Min : {}'.format(pop[-1][0]))
    print('Max : {}'.format(pop[0][0]))
    print('--------------------------')

    for g in range(generation):
        print('Generation: ' + str(g+1))

        # エリートを選択
        eva = evaluate(pop)
        elites = eva[:int(len(pop)*elite_rate)]

        # 突然変異、交叉
        pop = elites
        while len(pop) < individual_length:
            if random.random() < mutate_rate:
                m = random.randint(0, len(elites)-1)
                child = mutate(elites[m][1])
            else:
                m1 = random.randint(0, len(elites)-1)
                m2 = random.randint(0, len(elites)-1)
                child = two_point_crossover(elites[m1][1], elites[m2][1])
            pop.append((fitness(child), child))

        # 評価
        eva = evaluate(pop)
        pop = eva

        print('Min : {}'.format(pop[-1][0]))
        print('Max : {}'.format(pop[0][0]))
        print('--------------------------')
    print('Result : {}'.format(pop[0]))


if __name__ == '__main__':
    main()

実行結果

$ python ga.py
Generation: 0
Min : 3
Max : 7
--------------------------
Generation: 1
Min : 6
Max : 9
--------------------------
Generation: 2
Min : 8
Max : 10
.
.
.
Generation: 18
Min : 9
Max : 10
--------------------------
Generation: 19
Min : 10
Max : 10
--------------------------
Generation: 20
Min : 10
Max : 10
--------------------------
Result : (10, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1])