進化的計算フレームワークDEAP (4) One Max Problem

# 最初に
deapを使用したOne Max Problemについて見ていきます。参考にしたサイトは[こちら](http://deap.readthedocs.io/en/master/examples/ga_onemax.html)になります。また、元のコードも[公式のgit](https://github.com/DEAP/deap/blob/master/examples/ga/onemax.py)からいただいています。ワンマックス問題以外にも色々例が乗っているので参考になると思います。今回は直訳という形ではなく、コードを読んでく形です。

## One Max Problem
最初にランダムにint型の0または1で埋められた個体で作られる集団を作成します。最終的に、要素が全て1になるように進化させていきます。とりあえず、最終的なコードはこちら。

```python
import random

from deap import base
from deap import creator
from deap import tools

creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)

toolbox = base.Toolbox()

toolbox.register("attr_bool", random.randint, 0, 1)
toolbox.register("individual", tools.initRepeat, creator.Individual, 
    toolbox.attr_bool, 100)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)


def evalOneMax(individual):
    return sum(individual),


toolbox.register("evaluate", evalOneMax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)



def main():
    random.seed(64)

    pop = toolbox.population(n=300)

    CXPB, MUTPB = 0.5, 0.2
    
    print("Start of evolution")
    

    fitnesses = list(map(toolbox.evaluate, pop))
    for ind, fit in zip(pop, fitnesses):
        ind.fitness.values = fit
    
    print("  Evaluated %i individuals" % len(pop))

    fits = [ind.fitness.values[0] for ind in pop]

    g = 0
    
    while max(fits) < 100 and g < 1000:
        g = g + 1
        print("-- Generation %i --" % g)
        
        offspring = toolbox.select(pop, len(pop))
        offspring = list(map(toolbox.clone, offspring))
    
        for child1, child2 in zip(offspring[::2], offspring[1::2]):

            if random.random() < CXPB:
                toolbox.mate(child1, child2)

                del child1.fitness.values
                del child2.fitness.values

        for mutant in offspring:

            if random.random() < MUTPB:
                toolbox.mutate(mutant)
                del mutant.fitness.values
    
        invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
        fitnesses = map(toolbox.evaluate, invalid_ind)
        for ind, fit in zip(invalid_ind, fitnesses):
            ind.fitness.values = fit
        
        print("  Evaluated %i individuals" % len(invalid_ind))
        
        pop[:] = offspring
        
        fits = [ind.fitness.values[0] for ind in pop]
        
        length = len(pop)
        mean = sum(fits) / length
        sum2 = sum(x*x for x in fits)
        std = abs(sum2 / length - mean**2)**0.5
        
        print("  Min %s" % min(fits))
        print("  Max %s" % max(fits))
        print("  Avg %s" % mean)
        print("  Std %s" % std)
    
    print("-- End of (successful) evolution --")
    
    best_ind = tools.selBest(pop, 1)[0]
    print("Best individual is %s, %s" % (best_ind, best_ind.fitness.values))

if __name__ == "__main__":
    main()
```
実行してみると、
> ...
> ...
> ...
> -- Generation 35 --
  Evaluated 177 individuals
  Min 86.0
  Max 100.0
  Avg 97.04333333333334
  Std 2.325536975028139
-- End of (successful) evolution --
Best individual is [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, 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], (100.0,)

と、確かに最後に全ての要素が1になっていることがわかります。　　

とりあえず、少しずつコードを見ていきたいと思います。

## 設定する
とりあえず、最初に必要なモジュールをインポートします。

 ```python
import random

from deap import base
from deap import creator
from deap import tools
```
## Creator
deap.creatorを使用することで簡単に個体を作成することができる。

```python
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)
```
最初に*FitnessMax*というクラスを定義している。これはdeap.baseモジュールの*Fitness*クラスを継承している。また、*weights*という属性を持っており、これは必ずタプルでないといけないので注意する必要がある。また、1.0というのは目的関数の値を最大化させることを表しており、負の値の場合は最小化させることを表す。また、必ずしも1.0である必要でなく、この値を変更することによって目的関数の重みを変更することができる。  
二行目で*Individual*クラスを作成している。これはlistを継承したものであり、先ほど定義した*FitnessMax*をfitness属性として持つ。

## Toolbox
*Toolbox*に関数を登録していく。

```python
toolbox = base.Toolbox()
toolbox.register("attr_bool", random.randint, 0, 1)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_bool, 100)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
```
ここでは、世代を作成する関数*toolbox.attr_bool()*と2つの初期化関数、*individual()*と*population()*を作成している。*toolbox.attr_bool()*が呼ばれると、int型の0か1をランダムで返す。これはramdom.randint(0, 1)と同等である。　　

*individual()*と*population()*はそれぞれ個体と集団を初期化する関数である。これらは*initRepeat()*という関数を使用している。この関数の最初の引数はコンテナクラスとなる。3行目の例では、*indivisual()*が*tools.initRepeat(creator.Individual, toolbox.attr_bool, 100)*と同等になる。1つ目の引数として先ほど作成した*Individual*が使用されており、これは*creator.Individual*というListを継承しているクラスが*attr_bool()*メソッドを使用して要素が埋めらることになる。また、3つ目の引数に100が入っていることから100個のint型の0か1を持つことになる。  
*population()*についても同様で、Listが*toolbox.individual()*を使用して埋められる事となる。だが、集団を構成する個体の数は固定されていない。また後で指定していく。

# 評価関数
この例で評価関数は非常に簡単である。なぜなら、含まれる1の個数を数えれば良いだけだからだ。

```python
def evalOneMax(individual):
    return sum(individual),
```
ただ、必ず目的の数と同じだけの値をイテレート可能な形で返さないといけない事に注意する。今回は目的関数が１つなので１つの値を返すだけで良い。

# 遺伝子操作
4つの関数を登録する。

```python
toolbox.register("evaluate", evalOneMax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
```
評価は*evaluate*とエイリアスされた関数が実行される。ここで、引数を固定しないのが大事になってくる。なぜなら、集団中の各個体に対して評価を行っていく必要があるからだ。  

これまでで、下準備はだいたい終了。

# 進化のサイクル
## 集団を作成する
先ほど作成した*population()*を使用して集団を作成する。

```python
def main():
    pop = toolbox.population(n=300)
```
先ほど、個体の数を固定しなかったのでここで指定している。つまり、この集団は個体300個から作成されるものとなる。また、先ほど引数を固定した通り*pop*はList型となる。   

また、ここで交叉をする確率(CXPB)、突然変異(MUTPB)をする確率を定義しておく。

```python
    CXPB, MUTPB = 0.5, 0.2
```
次にそれぞれの個体を評価していく。 

```python
    fitnesses = list(map(toolbox.evaluate, pop))
    for ind, fit in zip(pop, fitnesses):
        ind.fitness.values = fit
```
1行目で*map()*を使用し、各個体にtoolbox.evaluate()を適用して評価していく。*fitnesses*と*pop*の並び順は同じになるので次のfor文で適応度を個体にセットしていく。

## 進化させる
集団は準備できたので、進化させていく。今、各個体はint型の0か1を100個持っていて最終的に全て1にしたいというのが今回の目的であった。つまり、最終的に評価関数の値が100になれば良いという事である。まず、各個体の評価関数の値を得る必要がある。

```python
fits = [ind.fitness.values[0] for ind in pop]
```
そして、どれかの個体の評価関数の値が100になるか、1000回世代交代するまで繰り返していく。

```python
    # 世代回数を覚えておくために変数を用意する。
    g = 0
    
    # 進化開始
    while max(fits) < 100 and g < 1000:
        # 新しい世代
        g = g + 1
        print("-- Generation %i --" % g)
```
進化は、選択、交叉、突然変異と進んでいく。  
まず最初に次の世代のために選択をしていく。

```python
        offspring = toolbox.select(pop, len(pop))
        offspring = list(map(toolbox.clone, offspring))
```
2行目でクローンを作成している。1行目では参照だったため、2行目で深いコピーをして独立した個体を作成している。

次に交叉と突然変異をしていく。先ほど定義したCXPBとMUTPBでそれぞれの確率を決めている。

```python
        # 交叉。それぞれ偶数のもの、奇数のものを交叉させようとしている。
        for child1, child2 in zip(offspring[::2], offspring[1::2]):
            if random.random() < CXPB:
                toolbox.mate(child1, child2)
                del child1.fitness.values
                del child2.fitness.values

        # 突然変異
        for mutant in offspring:
            if random.random() < MUTPB:
                toolbox.mutate(mutant)
                del mutant.fitness.values
```
また、それぞれ適応した後に適応度を無効化している。

先ほどの段階で適応度が変化した個体があるので、無効化されているものを再度計算してく。

```python
        invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
        fitnesses = map(toolbox.evaluate, invalid_ind)
        for ind, fit in zip(invalid_ind, fitnesses):
            ind.fitness.values = fit
```
これで新たな世代が作成されたので、置き換える。

```python
        pop[:] = offspring
```

進化がどんな感じで進んでいるか確かめるためにプリントしていく。

```python
        fits = [ind.fitness.values[0] for ind in pop]
        
        length = len(pop)
        mean = sum(fits) / length
        sum2 = sum(x*x for x in fits)
        std = abs(sum2 / length - mean**2)**0.5
        
        print("  Min %s" % min(fits))
        print("  Max %s" % max(fits))
        print("  Avg %s" % mean)
        print("  Std %s" % std)
```

# 値を取り出す
進化が十分行われたら、解を取り出す。

```python
    best_ind = tools.selBest(pop, 1)[0]
```
この関数は*pop*の中からよかったものを1つとりだすという物である。ちなみに1を2にすればよかったものを2つ取り出せる。返り値はリストになっているので[0]でさらに取り出している。

# 終わりに
なんか、途中から口調が変わりましたね。とりあえず、わたし的に、簡単な例までは理解することができるようになったと思いますー！色々できそうなのでいじってみたいと思います。個人的にNSGA-IIを実装したいので、もうちょい勉強しないといけないなとは思いますが。ドキュメントがしっかりしているって素敵ですね。基本的な使い方まではわかったのでこれにて終わりたいと思います。　　
 
---
[進化的計算フレームワークDEAP (1) Overview](https://qiita.com/emi-cd/items/44104a8fab60799cf524)
[進化的計算フレームワークDEAP (2) Creating Types](https://qiita.com/emi-cd/items/ef42cc632467a62079ae)
[進化的計算フレームワークDEAP (3) Operators and Algorithms](https://qiita.com/emi-cd/items/bd7d68ea6f9d9aace9e0)