GAでOneMax問題を解いてみる

はじめに

OneMax問題とは、[1, 0, 0, 0, 1, 0, 1, 0, 1, 1]のように0と1からなる数列の要素の和が最大となるような数列を探す問題です。人間からすると、すべての要素が1となるような数列[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]が最大になり、最適解であるということがすぐに理解できます。この問題の最適解をGA(遺伝的アルゴリズム)の手法を使用して求めてみたいと思います。

OneMax問題の処理の流れ

1　初期集団を生成：乱数で0 or 1からなるリストを個体数分作成する
2　選択：適応度の高い個体を残し、残りの個体を淘汰する
3　交叉：2で残った個体から2個体(親)をランダムに選択し、(淘汰した数だけ)子を作成する
4　突然変異：3で作成された子を一定の確率で突然変異させる
※2-4を指定の世代数繰り返す

今回GAでの各要素は以下のように設定し、OneMax問題を求めたいと思います。
世代：上記の処理2-4処理を1世代として、それを指定した世代数分行う。
遺伝子：数列の各要素(0 or 1)
個体：[1, 0, 0, 0, 1, 0, 1, 0, 1, 1]のような数列
集団：複数の個体が集まった集団
適応度：数列の要素の和([1, 0, 0, 0, 1, 0, 1, 0, 1, 1]であれば5)
選択：適応度が高い個体を残す。低いものは淘汰される。
交叉：2つの個体(親)から遺伝子を引き継いだ新たな個体(子)を生成する。
　　　※今回は一点交叉で行う。他にも2点交叉や一様交叉などがある。
突然変異：数列の各要素を一定の確率で変化させる。

以下実装手順です。

main.py

# coding: utf-8

from . import ga_onemax

# Parameter
SELECT_RATE = 0.5  # 選択割合
MUTATE_RATE = 0.1  # 突然変異の確立
GENE_SIZE = 10  # 個体がもつ0/1のリスト長さ
POPULATION_SIZE = 10  # 集団の個体数
GENERATION = 25  # 世代数

# インスタンスを生成
ga_one_max = ga_onemax.GA_OneMax(GENE_SIZE, POPULATION_SIZE, SELECT_RATE, MUTATE_RATE)

# 1. 初期集団を生成
ga_one_max.generate_initial_population()

for i in range(GENERATION):
    print("{0}世代".format(i + 1))

    # 2. 選択
    ga_one_max.selection()

    # 3. 交叉
    ga_one_max.crossover()

    # 4. 突然変異
    ga_one_max.mutate()

    # 集合に属する個体の情報を描画する
    ga_one_max.draw_population_info()

ga_onemax.py

# coding: utf-8

import random
import copy

# 個体の適応度を計算する
def calc_fitness(individual):
    return sum(individual)

class GA_OneMax:
    # 初期化
    def __init__(self, gene_size, population_size, select_rate, mutate_rate):
        self.gene_size = gene_size
        self.population_size = population_size
        self.select_rate = select_rate
        self.mutate_rate = mutate_rate

        self.population = []             # 集団
        self.individuals_fitness = []    # 集合に属する各個体の適応度
        self.selected_individuals = []   # 選択で残った適応度の高い個体群
        self.child_individuals = []      # 交叉、突然変異を経て新たに生成された個体群

    # 1. 初期集団を生成する
    def generate_initial_population(self):

        for _ in range(self.population_size):
            # 個体(の遺伝子情報を格納するリスト)
            individual = []

            # ランダムに0か1を選択し、個体の情報(遺伝子)を設定する
            for _ in range(self.gene_size):
                individual.append(random.randint(0, 1))

            # 集団に個体を追加する
            self.population.append(individual)

        # 集合の各個体の適応度を計算し、適応度が高い順にsortする
    def sort_fitness(self):
        # 各個体の適応度を計算する
        for individual in self.population:
            fitness = calc_fitness(individual)
            self.individuals_fitness.append([individual, fitness])

        # 適応度が高い順にソートする
        self.individuals_fitness.sort(key=lambda x: x[1], reverse=True)

    # 2. 指定した選択割合に基づき、適応度の高い個体を残す
    def selection(self):
        # 適応度が高い順に集団をソートする
        self.sort_fitness()

        # 残す個体の数を指定
        n = int(self.select_rate * self.population_size)

        for i in range(n):
            self.selected_individuals.append(copy.deepcopy(self.individuals_fitness[i][0]))

    # 3. 選択された適応度の高い個体群(集合)から任意に２個体を選択し、交叉させ、子を生成する
    def crossover(self):

        # 新しく生成する子(個体)の数
        num_crossover = self.population_size - len(self.selected_individuals)

        # 交叉を行う数だけ、子を生成する
        for i in range(num_crossover):
            parent = random.sample(self.selected_individuals, 2)   # 残った個体群から2つの個体を選択する(重複なし)
            intersection = random.randint(1, self.gene_size - 2)   # 交叉点

            parent1_gene = copy.deepcopy(parent[0][0:intersection])
            parent2_gene = copy.deepcopy(parent[1][intersection:])

            # 子を生成
            parent1_gene.extend(parent2_gene)

            # 子をリストに格納
            self.child_individuals.append(parent1_gene)

    # 4. 一定の確率で突然変異させる
    def mutate(self):
        for individual in self.child_individuals:
            for i in range(len(individual)):
                n = random.random()
                if n < self.mutate_rate:
                    individual[i] = random.randint(0, 1)

        # 新しい集団 = 選択された個体群(親) + 新しく生成された個体群(子)
        self.selected_individuals.extend(self.child_individuals)
        self.population = copy.deepcopy(self.selected_individuals)

        # 変数を初期化
        self.reset()

    # 変数の初期化
    def reset(self):
        self.individuals_fitness = []
        self.selected_individuals = []
        self.child_individuals = []

    # 集団に属する各個体の遺伝子情報を表示する
    def draw_population_info(self):
        for individual in self.population:
            print(individual)

実行結果

1世代
[1, 1, 1, 1, 0, 1, 1, 0, 1, 0]
[1, 1, 1, 1, 1, 1, 0, 0, 1, 0]
[1, 1, 0, 0, 0, 1, 1, 0, 1, 1]
[0, 1, 1, 0, 1, 1, 1, 1, 0, 0]
[1, 1, 1, 1, 1, 0, 0, 1, 0, 0]
[0, 1, 1, 0, 1, 1, 0, 1, 0, 0]
[0, 1, 1, 0, 1, 1, 1, 0, 1, 1]
[1, 1, 1, 0, 1, 1, 1, 1, 0, 0]
[1, 1, 0, 1, 1, 1, 0, 0, 1, 0]
[1, 1, 0, 0, 0, 1, 1, 1, 0, 0]

・
・
・

25世代
[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]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

25世代目では、確かに数列の要素の和が最大になる最適解が求められていることがわかります。

今回はGAのアルゴリズムを理解するために、比較的実装しやすいOneMax問題をGAで解いてみるということを行ってみました。次は巡回セールスマン問題をGAを用いて解いてみたいと思います。

参考

遺伝的アルゴリズムによるOneMax問題の最適化