SuprSonicJetBoy's blog

いろいろです。

Pythonでライブラリを使わずにOneMax問題を遺伝的アルゴリズムで解いてみる

Pythonでライブラリを使わずに、OneMax問題をやってみました。

機械学習の技術を実用的なレベルまで持っていきたく試行錯誤を繰り返しているのですが、最適化という部分をまだあまり突き詰めていませんでした。
ハイパーパラメータの最適化には色々な手法があるみたいですが、ここに遺伝的アルゴリズムを使うことができるようです。
最近では、Bayesian Optimization(ベイズ最適化)が使われているようですが、引き出しは多い方がいいのでやってみました。
(実際にニューラルネットとか機械学習で使うとなれば、実数値遺伝的アルゴリズムを使うようになると思います。)

遺伝的アルゴリズムについて

色々なサイトや文献を読み漁りましたが、遺伝的アルゴリズムPythonで入門だけすることを前提とすれば、

qiita.com

と、ここで紹介されていた

www.slideshare.net で十分かなと思います。

実装

「個体集団」を用意し、「選択」、「交叉」、「突然変異」の3種類を順に実装していきます。

用語

上記サイトより抜粋しました。

用語
Gene 遺伝子
Chromosome 染色体
Individual 個体
Population 個体集団
Fitness 適応度
Mutation 突然変異
Phenotype 表現型
Locus 遺伝子座
Genotype 遺伝子型
Offspring 子孫
Selection 選択
Roulette wheel selection ルーレット方式
Ranking selection ランキング方式
Tournament selection トーナメント方式
Elitism エリート主義
Crossover 交叉
Single point crossover 一点交叉
Two-point crossover 二点交叉
Multi-point crossover 多点交叉
Uniform drossover 一様交叉

個体の生成

class Individual:
    def __init__(self, chromosome, fitness=None):
        self.chromosome = chromosome
        self.fitness = fitness

    def mutate(self, mutation):
        for i in self.chromosome:
            if mutation > (random.randint(0, 100) / 100):
                self.chromosome[i] = random.randint(0, 1)

    def fit(self):
        self.fitness = sum(self.chromosome) / len(self.chromosome)

def create_individual(chr_size):
    return Individual([random.randint(0, 1) for i in range(chr_size)])

1つの個体は、染色体を1つだけ持つようにしてみます。
chromosme は、適当なサイズの遺伝子のリストを持ちます。

fitness は、OneMax問題の場合は単純で、遺伝子の値が0 or 1 なので、染色体の遺伝子の合計値を、染色体の長さで割ります。
なので、答えが1の場合が最適応となります。

mutate() でランダムに遺伝子を突然変異させます。

選択

エリート主義で、適応度の高いものからいくつか選択します。

def select_individual(population, elite_size):
    population = sorted(population, reverse=True, key=lambda i: i.fitness)     
    elite = [population.pop(0) for i in range(elite_size)]
    random.shuffle(population)
    return elite, population

交叉

二点交叉を行います。

def crossover(a, b):
    # Two-point crossover
    a_chr = a.chromosome
    b_chr = b.chromosome
    
    size = len(a_chr)

    f = random.randint(0, size)
    s = random.randint(f, size)

    _a = a_chr[:f] + b_chr[f:s] + a_chr[s:]
    _b = b_chr[:f] + a_chr[f:s] + b_chr[s:]

    return [Individual(_a), Individual(_b)]

突然変異

ある個体の染色体の遺伝子を突然変異させます。

def mutate(population, individual_mutation, gene_mutation):
    for i in range(len(population)):
        if individual_mutation > (random.randint(0, 100) / 100):
            population[i].mutate(gene_mutation)
    return population

実行その1

世代数を指定する場合です。
まず、適当な個体集団をつくり、適応度を計算します。
その個体集団から、エリートをいくつか選出します。
選出したエリートは、交叉や突然変異をすることなく、次の世代に渡します。
残りの個体集団は、交叉、突然変異させて、個体の数を調整して次の世代に渡します。

import random

random.seed(64)

CHROMOSOME_SIZE = 10
GENE_MUTATION = 0.1
INDIVIDUAL_MUTATION = 0.1
POPULATION_SIZE = 100
ELITE_SIZE = 2
GENERATION_MAX = 3


if __name__ == '__main__':

    # Population of the first generation
    population = [create_individual(CHROMOSOME_SIZE) for i in range(POPULATION_SIZE)]
    
    # Start
    print("START\n", population[0].chromosome, "\n")
    
    for generation in range(GENERATION_MAX):

        # Fit
        [population[i].fit() for i in range(POPULATION_SIZE)]
        
        # Result
        result = [p.fitness for p in population]
        print("{0} Generation ---".format(generation + 1))
        print("\tMIN: {0}".format(min(result)))
        print("\tMAX: {0}".format(max(result)))
        print("\tAVG: {0}".format(round(sum(result) / len(result), 3)), "\n")

        # Select
        selected_individual, population = select_individual(population, ELITE_SIZE)
        
        # Crossover
        crossover_individual = []
        for i in range(len(population)-1):
            crossover_individual.extend(crossover(population[i], population[i+1]))
        random.shuffle(crossover_individual)

        # Mutate, Generate offspring
        offspring = mutate(crossover_individual[:POPULATION_SIZE-ELITE_SIZE], INDIVIDUAL_MUTATION, GENE_MUTATION)
        offspring.extend(selected_individual)

        # Update population
        population = offspring

    print("-"*30, "\nResult:")
    print(selected_individual[0].chromosome)

とりあえず。3世代で回してみます。

START
 [1, 0, 1, 0, 0, 1, 0, 0, 0, 1] 

1 Generation ---
    MIN: 0.0
    MAX: 1.0
    AVG: 0.498 

2 Generation ---
    MIN: 0.2
    MAX: 0.8
    AVG: 0.508 

3 Generation ---
    MIN: 0.2
    MAX: 0.9
    AVG: 0.507 

------------------------------ 
Result:
[1, 1, 1, 1, 0, 1, 1, 1, 1, 1]

実行その2

今度は、エリート以外の子孫をだんだん減らしていき、最終的にエリートのみを残してみます。

import random

random.seed(64)

CHROMOSOME_SIZE = 10
GENE_MUTATION = 0.1
INDIVIDUAL_MUTATION = 0.1
POPULATION_SIZE = 100
ELITE_SIZE = 2


if __name__ == '__main__':

    # Population of the first generation
    population = [create_individual(CHROMOSOME_SIZE) for i in range(POPULATION_SIZE)]
    
    # Start
    print("START\n", population[0].chromosome, "\n")
    
    generation = 0
    while 1:
        generation += 1
             
        # Fit
        [population[i].fit() for i in range(POPULATION_SIZE)]
        
        # Result
        result = [p.fitness for p in population]
        print("{0} Generation ---".format(generation))
        print("\tMIN: {0}".format(min(result)))
        print("\tMAX: {0}".format(max(result)))
        print("\tAVG: {0}".format(round(sum(result) / len(result), 3)), "\n")
        
        # Select
        selected_individual, population = select_individual(population, ELITE_SIZE)
        
        # Crossover
        crossover_individual = []
        for i in range(len(population)-1):
            crossover_individual.extend(crossover(population[i], population[i+1]))
        random.shuffle(crossover_individual)
        
        POPULATION_SIZE -= ELITE_SIZE
        
        # Mutate, Generate offspring
        offspring = mutate(crossover_individual[:POPULATION_SIZE], INDIVIDUAL_MUTATION, GENE_MUTATION)
        offspring.extend(selected_individual)

        # Update population
        population = offspring
        
        if len(population) <= ELITE_SIZE:
            break

    print("-"*30, "\nResult:")
    print(population[0].chromosome)

こちらは、毎回エリートの数分減らしていき、最終的にエリートのみになるまでに50世代回ります。

START
 [1, 0, 1, 0, 0, 1, 0, 0, 0, 1] 

1 Generation ---
    MIN: 0.2
    MAX: 0.9
    AVG: 0.515 

...

50 Generation ---
    MIN: 0.6
    MAX: 1.0
    AVG: 0.825 

------------------------------ 
Result:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

最後に

一通り遺伝的アルゴリズムを書いてみましたが、これが果たして正しいやり方なのかどうか、正直不安です。
一応、最適解を導き出してはいますが…。
この記事を参考になさるときは他の文献も合わせて読んで頂き、間違いがあればご指摘頂ければ嬉しいです。

github.com