遺伝的アルゴリズムでOneMax問題を解く

遺伝的アルゴリズム

今日は、遺伝的アルゴリズムについて学んだ。

アルゴリズムそのものについては、このスライドが極めてわかりやすかった。
遺伝的アルゴリズム（Genetic Algorithm）を始めよう！

Hello World 的な Python コード例としては、
Pythonで遺伝的アルゴリズム
が理解しやすかった。

上記２つ記事の著者に多謝。

Pythonで遺伝的アルゴリズムのコードは十分理解しやすかったのだが、さらに自分好みにリファクタリングを加えてみた。

リファクタリング後のコード

import random
import copy


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


def fitness(gene):
    return sum(gene)


# individual は (適応度, 遺伝子）のタプルで表現される
def individual_tuple(gene):
    return (fitness(gene), gene)


def create_individual():
    gene = [random.randint(0,1) for j in range(gene_length)]
    return individual_tuple(gene)


def create_population():
    return [create_individual() for i in range(population_size)]


def evaluate(population):
    population.sort(reverse=True)


def two_point_crossover(parent1, parent2):
    r1, r2 = sorted(random.sample(range(gene_length), 2))
    parent1_gene = parent1[1]
    parent2_gene = parent2[1]
    child_gene = copy.copy(parent1_gene)
    child_gene[r1:r2] = parent2_gene[r1:r2]
    return individual_tuple(child_gene)


def mutate(parent):
    r = random.choice(range(gene_length))
    parent_gene = parent[1]
    child_gene = copy.copy(parent_gene)
    child_gene[r] = 1 if child_gene[r] == 0 else 0
    return individual_tuple(child_gene)


def main():
    # 初期個体生成
    population = create_population()

    for g in range(n_generations):
        # 適応度の降順にソート
        evaluate(population)

        print('Generation: ' + str(g + 1))
        print('Min : {}'.format(population[-1][0]))
        print('Max : {}'.format(population[0][0]))
        print('--------------------------')

        # エリートを選択
        elites = population[:int(population_size * elite_rate)]

        next_population = elites
        while len(next_population) < population_size:
            if random.random() < mutate_rate:
                # 突然変異
                parent = random.choice(elites)
                child = mutate(parent)
            else:
                # 交叉
                parent1, parent2 = random.sample(elites, 2)
                child = two_point_crossover(parent1, parent2)
            next_population.append(child)
        population = next_population

    evaluate(population)
    print('Result : {}'.format(population[0]))


if __name__ == '__main__':
    main()

感想

遺伝的アルゴリズムは、名前のとおり、生物界の自然選択を模したものなので、原理は理解しやすかった。
ただ、上のコードはあくまでも骨格。
現実の問題（ナップサック問題、巡回セールスマン問題等）を解くためには、遺伝子をどう符号化し、どのように適応度を評価するか、という点が肝だろう。
これについて考えるのが次の課題である。