読者です 読者をやめる 読者になる 読者になる

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

OneMax問題とは、[1,0,0,1,0,1,1,1,1,0]のように0/1からなる数列の和を最大化する問題のこと。 答えはすべて1の数列と自明だが、これを最適化アルゴリズムの1つである遺伝的アルゴリズムで解く。 遺伝的アルゴリズムとは、このような数列を遺伝子と見立て複数生成し、 数世代に渡り交叉と突然変異を繰り返すことにより、優秀な遺伝子を生み出すアルゴリズムのこと。 ここでの優秀の定義は「数列の和が大きい」となる。

PythonではDEAPという 遺伝的アルゴリズムのライブラリーがあるが、個人的に拡張性が低くて使いにくかったのと、 実装がそれほど難しくはないので、Pythonでスクラッチから書くことにした。

アルゴリズムの流れ

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

簡単な流れは上記の通り。 各世代の個体群の数は固定で、現世代のエリートと、彼らの子供の和となる。

1. 第1世代の個体群の生成

第2世代以降の個体群の生成は、基本的に交叉か突然変異になる。 そのため、この操作は第1世代だけ必要になる。 ランダム選択した0/1がN_PARAM個並ぶ数列を、 N_POP個生成する。

        
    def get_population(self):
        population = []
        for i in range(N_POP):
            arr = [random.randint(0,1) for j in range(N_PARAM)]
            population.append(arr)
        
        return population

各個体は後ほど適応度を計算するが、まず-1で初期化しておく。

>>> pop = [(-1, p) for p in self.get_population()]
>>> pop
[
    (-1, [0, 0, 0, 0, 1, 1, 1, 1, 0, 0]), 
    (-1, [1, 0, 1, 0, 1, 0, 0, 1, 0, 0]),
    (-1, [1, 0, 0, 0, 1, 0, 0, 0, 0, 1]),
    ...
]

2. エリートの選択

evaluateメソッドで、個体の適応度(fitness)を計算している。 OneMaxにおける適応度はリストの和とシンプルだが、今後の拡張を考えてメソッド化(clac_score)しておく。

    def clac_score(self, x):
        return sum(x)


    def evaluate(self, pop):
        fitness = []
        for p in pop:
            if p[0] == -1:
                fitness.append((self.clac_score(p[1]), p[1]))
            else:
                fitness.append(p)
        fitness.sort()
        fitness.reverse()

        return fitness

全個体の適応度を計算してソートしたら、ELITE_RATEの割合でエリートとして選択する。

>>> fitness = self.evaluate(pop)
>>> elites = fitness[:int(len(pop)*ELITE_RATE)]

3. エリートの交叉/突然変異

突然変異mutate()では、個体の数列からパラメーターを1つだけ反転させる。 交叉crossover()では、片親の遺伝子の一部を切り取り、もう片親の同じ位置にペーストする。 これを2点交叉というが、場合によっては1点交叉にもなり得る。

    def mutate(self, parent):
        r = int(math.floor(random.random()*len(parent)))
        child = copy.deepcopy(parent)
        child[r] = (parent[r]+1) % 2

        return child


    def crossover(self, parent1, parent2):
        length = len(parent1)
        r1 = int(math.floor(random.random()*length))
        r2 = r1 + int(math.floor(random.random()*(length-r1)))
        
        child = copy.deepcopy(parent1)
        child[r1:r2] = parent2[r1:r2]

        return child

突然変異はMUTATE_BROPの確率で起こり、それ以外は交叉となる。 これを全ての個体に対して行う。個体の組合せはランダムである。

pop = elites[:]
while len(pop) < N_POP:
    if random.random() < MUTATE_PROB:
        m = random.randint(0, len(elites)-1)
        child = self.mutate(elites[m][1])
    else:
        c1 = random.randint(0, len(elites)-1)
        c2 = random.randint(0, len(elites)-1)
        child = self.crossover(elites[c1][1], elites[c2][1])
    pop.append((-1, child))

4. 次世代の個体群の生成

現世代のエリートを選択し、彼らを交叉/突然変異させた個体群を生成した。 これらの適応度を計算することで、次世代の個体群が生成される。

fitness = self.evaluate(pop)
pop = fitness[:]

結果

10個の0/1の数列のOneMax問題を解かせたところ、第4世代で最適解が得られた。

Generation: 0
(8, [1, 1, 1, 1, 1, 1, 1, 0, 0, 1])

Generation: 1
(9, [1, 1, 1, 1, 1, 1, 1, 1, 0, 1])

Generation: 2
(9, [1, 1, 1, 1, 1, 1, 1, 1, 0, 1])

Generation: 3
(10, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

...

Generation: 24
(10, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

ソースコード

ソースコードを以下に載せておく。1ファイルにまとまっている。$ python ga.pyで実行可能。

# coding: utf-8

import random
import math
import copy

N_PARAM = 10
N_POP = 20
N_GEN = 25
MUTATE_PROB = 0.1
ELITE_RATE = 0.2

class GA:
    def __init__(self):
        pass


    def main(self): 
        pop = [(-1, p) for p in self.get_population()]

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

            # Get elites
            fitness = self.evaluate(pop)
            elites = fitness[:int(len(pop)*ELITE_RATE)]
            
            # Cross and mutate
            pop = elites[:]
            while len(pop) < N_POP:
                if random.random() < MUTATE_PROB:
                    m = random.randint(0, len(elites)-1)
                    child = self.mutate(elites[m][1])
                else:
                    c1 = random.randint(0, len(elites)-1)
                    c2 = random.randint(0, len(elites)-1)
                    child = self.crossover(elites[c1][1], elites[c2][1])
                pop.append((-1, child))
            
            # Evaluate indivisual
            fitness = self.evaluate(pop)
            pop = fitness[:]

            print pop[0]
            print


    def get_population(self):
        population = []
        for i in range(N_POP):
            arr = [random.randint(0,1) for j in range(N_PARAM)]
            population.append(arr)
        
        return population


    def clac_score(self, x):
        return sum(x)


    def evaluate(self, pop):
        fitness = []
        for p in pop:
            if p[0] == -1:
                fitness.append((self.clac_score(p[1]), p[1]))
            else:
                fitness.append(p)
        fitness.sort()
        fitness.reverse()

        return fitness


    def mutate(self, parent):
        r = int(math.floor(random.random()*len(parent)))
        child = copy.deepcopy(parent)
        child[r] = (parent[r]+1) % 2

        return child


    def crossover(self, parent1, parent2):
        length = len(parent1)
        r1 = int(math.floor(random.random()*length))
        r2 = r1 + int(math.floor(random.random()*(length-r1)))
        
        child = copy.deepcopy(parent1)
        child[r1:r2] = parent2[r1:r2]

        return child


if __name__ == "__main__":
    GA().main()

参考文献