遺伝的アルゴリズムでOneMax問題を解いてみる

#OneMax問題
OneMax問題とは, [0, 1, 1, 1, 0, 1, 0, 1, 1, 0]のように0/1からなる数列の和を最大化する問題です. 和が最大となるには, すべての要素が1となることを目指します.
今回は遺伝的アルゴリズムを用いて, OneMax問題を解いてみます.

#遺伝的アルゴリズム
遺伝的アルゴリズムは, 生物の進化の過程を真似て作られたアルゴリズムで確率的探索手法の1つです. 交叉や突然変異という操作を繰り返しながら, 個体を進化させていきます.
基本的な流れは以下のようになります.

##選択
次世代個体群を生成するために, 親個体を選択します.
親個体の選択方法には以下のようなものがあります.
-ルーレット方式
-ランキング方式
-エリート方式
##交叉
選択した親個体を交叉させて, 子個体を生成します.
交叉方法には以下のようなものがあります.
-一様交叉
-一点交叉
-多点交叉
##突然変異
生成した個体に突然変異を加えます.

#実践
それでは実際にGAでOneMax問題を解いてみます.
実験の設定は
遺伝子長:100
世代数:100
選択:トーナメント選択(トーナメントサイズ:2)
交叉:一様交叉
突然変異確率:1/遺伝子長
親個体数:100
子個体数:50
個体更新:親個体の優良個体50+子個体

# -*- coding: utf-8 -*-
import random
import copy

# 各種パラメータ
length = 100  # 遺伝子長
population = 100  # 親個体数
offspring_n = 50    # 子個体数
generation = 100     # 世代数
mutation_rate = 1.0/100.0    # 突然変異確率(1/遺伝子長)

# 初期個体群生成
def initialize():
    gene = [[random.randint(0,1) for i in range(length)] for j in range(population)]
    return gene

# 個体評価
def evaluate(gene):
    fitness = []
    for i in range(population):
        fitness.append(sum(gene[i])/length)
    return fitness

# minを見つける
def find_min(fitness):
    min = 10
    for i in range(population):
        if fitness[i] < min:
            min = fitness[i]
    return min

# maxを見つける
def find_max(fitness):
    max = 0
    for i in range(population):
        if fitness[i] > max:
            max = fitness[i]
    return max

# 親選択
def choice_parents(gene, fitness):
    father_index = random.randint(0,population-1)
    mother_index = random.randint(0,population-1)
    if fitness[father_index] > fitness[mother_index]:
        parents = gene[father_index]
    else:
        parents = gene[mother_index]
    return parents

# 交叉
def crossover(father, mother):
    offspring = []
    for i in range(length):
        p = random.random()
        if p < 0.5:
            offspring.append(father[i])
        else:
            offspring.append(mother[i])
    return offspring

# 突然変異
def mutation(offspring):
    for i in range(length):
        p = random.random()
        if p < mutation_rate:
            if offspring[i] == 0:
                offspring[i] = 1
            else:
                offspring[i] = 0
    return offspring

# 個体更新(親個体エリート50 + 子個体50 = 計100)
def elite(gene, fitness, next_gene):
    sort_fitness = sorted(fitness, reverse=True)
    gen_tmp = []
    for i in range(int(population/2)):
        index = fitness.index(sort_fitness[i])
        gen_tmp.append(gene[index])
    gen_tmp.extend(next_gene)
    return gen_tmp

def main():
    generation_count = 1
    next_gene = []

    # 初期個体群生成
    gene = initialize()

    while generation_count <= generation:
        next_gene.clear()
        #print(gene)
        # 個体評価
        fitness = evaluate(gene)
        min = find_min(fitness)
        max = find_max(fitness)
        print("generation:", generation_count)
        print("min", min)
        print("max", max)
        if min == 100:
            break
        # 次世代個体群生成
        for i in range(offspring_n):
            # 個体選択
            father = choice_parents(gene, fitness)
            mother = choice_parents(gene, fitness)
            # 交叉
            offspring = crossover(father, mother)
            # 突然変異
            offspring = mutation(offspring)
            next_gene.append(offspring)
        # 個体更新
        gene = elite(gene, fitness, next_gene)
        generation_count += 1
        print("--------------------------------")

if __name__ == "__main__":
    main()

結果は以下のようになりました.
最初の世代ではmin, maxともに低い値となっています.
それが最終世代ではmaxは最大値に達し, minも大きな値を獲得できています.
遺伝的アルゴリズムもより, 個体が進化していることを確認できました.

generation: 1
min 0.37
max 0.62
--------------------------------
generation: 2
min 0.39
max 0.63
--------------------------------

.
.
.

generation: 99
min 0.96
max 1.0
--------------------------------
generation: 100
min 0.95
max 1.0
--------------------------------