深層学習とメタヒューリスティクス(1) 遺伝的アルゴリズムでOneMax問題を解く


# はじめに

深層学習とメタヒューリスティクス ディープ・ニューラルエボリューション

![](https://www.ohmsha.co.jp/Portals/0/book/small/978-4-274-22446-1.jpg)

この本で群知能とメタヒューリスティクスを勉強していきます。
かなり網羅的な本のため、学んだことを一個一個実装していこうと思います。
リポジトリは[deep_learning_meta_heuristic](https://github.com/Ganariya/deep_learning_meta_heuristic)です。

今回は、1.2.1の遺伝的アルゴリズムを用いて、OneMax問題を解いていきます。

# 遺伝的アルゴリズムとは？

遺伝的アルゴリズムは、生物の進化に着目を得たシミュレーションの最適化アルゴリズムです。

たくさんの個体を作成して

- 選択
- 交叉
- 突然変異

を用いて、より強い世代の個体群を作成します。
これによって、より適した個体が残ることを目指します。

選択は、「より強い個体を優先的に残す」操作です。
交叉は、「選ばれた２体の個体を交叉して、新しい個体を生み出す」操作です。
突然変異は、「ある確率で新しい個体を生み出すことで、多様性を見出す」操作です。

これらをうまく用いることで、最適化問題を解くことができます。

## リンク

分かりやすい参考にさせていただいたリンクです。

- [遺伝的アルゴリズム（Genetic Algorithm）を始めよう！](https://www.slideshare.net/kzokm/genetic-algorithm-41617242?from_action=save)
    - とても分かりやすいです！
    - これがインターネット上のデファクトスタンダードな感じがあります
- [Pythonで遺伝的アルゴリズム](https://qiita.com/KeisukeToyota/items/0f527a72270430017d8d)

## 用語

### 遺伝子(gene)

遺伝子は、各個体の染色体の一個一個のパーツです。

ナップザック問題なら、あるアイテム$i$をリュックに詰めるか詰めないか？を表します。

バイナリだったり実数値だったり様々です。

### 染色体(chromesome)

遺伝子の集合体・配列です。
次のIndividualとほぼ同じため、扱わない実装をしています。

染色体は、各個体（解）を示すのが、複数の定義があるときに使うのかもしれません。

例えば、ナップザック問題なら染色体は$N$個のアイテムをうまく詰めるなら$N$の遺伝子の配列を用意しますが
多目的ナップザック問題なら、$3\times N$のような多次元配列になるので、$3$つの染色体を使うのでしょうか･･･

### 個体(Individual)

個体は、一個の解を表します。

例えば、TSPなら$(1, 4, 3, 2, 5)$や
ナップザック問題なら$(1, 0, 1, 0, 1)$のように

複数の遺伝子で構成された配列で、個体一体一体が一個の解を表します。

これらの個体を選択・交叉・突然変異させていくことで、より良い個体（解）を探します。

### 世代(Population)

世代は、１世代あたりの個体群を表します。
$K$体の個体群でなる世代なら、$K$個の候補解があるのと同義です。

この１世代あたりの個体群からうまいこと強い解を新しく作り出して
次の世代を作成していきます。

### GTYPE(Genome Type)

GTYPEは遺伝子型という意味です。
これは、染色体や個体と同じで、配列を表します。
つまり、各遺伝子の存在でみた表現です。

### PTYPE(Pheno Type)

PTYPEは表現型という意味です。

先程のGTYPEは遺伝子単位で見た配列でした。
例えば、ナップザック問題なら$(1, 0, 1, 0, 0)$のようなアイテムを入れる？入れない？の配列でした。

しかし、現実的な問題からこのGTYPEをみると

「アイテム１を入れるか？入れないか？
アイテム２を入れるか？...」のように、実際の問題に照らし合わせた見方をすることができます。

このように、実際の問題の人間的な視点から見た表現をPTYPEといいます。
（自然言語処理とソースコードのバイナリみたいな違いという感じです）

### 適応度関数

適応度関数$f$は、表現型を引数にとる関数です。

たとえば、$f(x)$, $x$はナップザック問題の配列・解とすると
この一個の個体解がどれくらい良いか？を求める関数です。

$f([1, 0, 1, 0, 0]) = 324$のようになります。

このPTYPEに対してより良いスコアを出す個体を多く世代内に集めて、適応度関数の高い個体を次の世代に引き継いでいきます。

### OneMax問題

OneMax問題は、$N$個の配列に含まれる$1$の個数を最大化する問題です。

つまり、$N=5$なら$(1, 1, 1, 1, 1)$が最適です。

とてもシンプルな設定なので、実装しやすく、遺伝的アルゴリズムを体験するときによく用いられるようです。

## 操作の流れ

$N = 1世代の個体の数$
$R = 1個体の遺伝子の数$(OneMax問題なら$R$個の0, 1を最大化)
$T = 世代交代の回数$

1. 世代を初期化する
2. $T$回世代交代させる
    3. 世代に含まれる$N$体を適応度関数で評価する
    4. 次の世代の配列を用意する
    4. 選択する
        5. エリート選択する
    6. 交叉する
        7. トーナメント選択かルーレット選択で$2$体いま世代から選び、次の世代の配列に$N$体揃うまで、個体を交叉して追加する
    8. 突然変異させる
    9. 次の世代の配列を今の世代とする

## 選択

選択では、より良い個体が多く次の世代に含まれるように選びます。

しかし、強い個体ばかり残すと多様性が失われて局所解に陥るためバランスを取る必要があります。

### エリート選択

ソートしたときの上位$Elite$体だけ、強制的に次の世代へ個体を引き継ぎます。

上位の個体は必ずある決まった数だけ引き継ぐことで、最低限この世代での強い個体を次の世代にも引き継ぐことができます。

### ルーレット選択

エリート選択したあとは、残りの個体は交叉を用いて作成します。
このとき、交叉を用いるためには今の世代から$2$体選ぶ必要があるため
ある程度ランダム性のある選択を行う必要があります。

ルーレット選択は、文字通りルーレットで選択をします。


$$Prob(i) = \frac{f(i)}{\sum_{j\in P_t}f(j)}$$

上記のような式です。

これは今$t$の世代$P_t$のうちの$i$体目の個体がどれくらいの確率$Prob(i)$で選択されるか？を表します。

分子は$i$体目の適応度で、分母は合計$N$体の適応度の総和です。

よって、適応度が大きい個体ほどより選択されることになります。

実装をする際は、二分探索と累積和を用いると楽です。
ソースコードを参照してみてください。

### トーナメント選択

トーナメント選択は、$N$体の個体からランダムに$K$体選び
そのうちの最も良い個体のみを選ぶものです。

ディープラーニングだとバッチなどに値します。

トーナメント選択で使用する$K$が大きすぎると、選ばれやすい個体ができてしまうため、多様性が消えてしまいます。

## 交叉

交叉は２体の選択された個体の遺伝子を交配・交換して
より新しい個体を生み出す操作です。

### ２点交叉

２体の染色体を交配します。

$x1< x2$の入れ替える位置を決めて

```
a1[x1:x2] = a2[x1:x2]
```

のようにすることで、a2の遺伝子を一部引き継ぐことができます。

ただ、今のソースコードだと中央がより多く含まれるようになってしまっているため、修正が必要です。（どうすればいいんでしょうか･･･）

## 突然変異

突然変異は多様性を持たせるために、各個体をある一定の確率で変化させる操作です。

遺伝子の値を反転させたり、染色体（配列）のある区間を反転・交換などを行います。

$0.01$ぐらいの小さい値のほうが良いようです。あまり大きいと収束せず、悪い結果になることもあるようです。

# ソースコード

```python
import random
import copy
import functools
import itertools
import bisect

import click
import numpy as np

# 個体の遺伝子の長さ
GENOME_LENGTH = 50

# 世代の個体数
POPULATION_SIZE = 30

# 最大実行回数
MAX_GENERATION = 100

# エリート戦略
ELITE_SELECT = 5

# トーナメント戦略
TOURNAMENT_SELECT = 6

# 個体の突然変異確率
INDIVIDUAL_MUTATION = 0.1

# 個体の突然変異確率
GENOME_MUTATION = 0.1


class Genome:
    def __init__(self, value):
        self.value = value

    def mutate(self):
        q = random.random()
        if q < GENOME_MUTATION:
            self.value = 1 - self.value

    def __repr__(self):
        return str(self.value)


@functools.total_ordering
class Individual:

    def __init__(self):
        self.genomes = [Genome(random.randint(0, 1)) for _ in range(GENOME_LENGTH)]

    def fitness(self):
        return sum(x.value for x in self.genomes)

    def mutate(self):
        q = random.random()
        if q < INDIVIDUAL_MUTATION:
            for g in self.genomes:
                g.mutate()

    def two_point_crossover(self, other):
        other = copy.deepcopy(other)
        r1 = random.randint(0, GENOME_LENGTH - 1)
        r2 = random.randint(0, GENOME_LENGTH - 1)
        if r1 > r2:
            r1, r2 = r2, r1
        self.genomes[r1:r2] = other.genomes[r1:r2]

    def __eq__(self, other):
        return self.fitness() == other.fitness()

    def __lt__(self, other):
        return self.fitness() < other.fitness()

    def __repr__(self):
        return f"{self.fitness()} {self.genomes}"


class Population:

    def __init__(self):
        self.individuals = [Individual() for i in range(POPULATION_SIZE)]

    def evolution(self):
        # elite
        self.individuals.sort(reverse=True)
        next_individuals = self.individuals[:ELITE_SELECT]

        # select
        while len(next_individuals) < POPULATION_SIZE:
            x1 = copy.deepcopy(self.select_individual())
            x2 = copy.deepcopy(self.select_individual())
            x1.two_point_crossover(x2)
            next_individuals.append(x1)
        # 突然変異
        for x in next_individuals:
            x.mutate()

        self.individuals = next_individuals

    def get_scores(self):
        avg_v = sum([x.fitness() for x in self.individuals]) / POPULATION_SIZE
        min_v = min([x.fitness() for x in self.individuals])
        max_v = max([x.fitness() for x in self.individuals])
        return {
            "avg": avg_v,
            "min": min_v,
            "max": max_v
        }

    def select_individual(self):
        x = self._tournament_selection()
        # x = self._roulette_selection()
        return x

    def _roulette_selection(self):
        total = sum([x.fitness() for x in self.individuals])
        cumdist = list(itertools.accumulate([x.fitness() for x in self.individuals]))
        index = bisect.bisect(cumdist, total * random.random())
        return self.individuals[min(index, POPULATION_SIZE - 1)]

    def _tournament_selection(self):
        candidates = [self.individuals[random.randint(0, POPULATION_SIZE - 1)] for i in range(TOURNAMENT_SELECT)]
        candidates.sort(reverse=True)
        return candidates[0]


#
# @click.command()
# @click.option('--genome_length', '-gl', type=int, default=30)
# @click.option('--population_size', '-ps', type=int, default=30)
# @click.option('--max_generation', '-mg', type=int, default=100)
# @click.option('--select_genome', '-sg', type=int, default=20)
# @click.option('--genome_mutation', '-gm', type=float, default=0.01)
# @click.option('--individual_mutation', '-im', type=float, default=0.01)
# def init(genome_length, population_size, max_generation, select_genome, genome_mutation, individual_mutation):
#     global GENOME_LENGTH, POPULATION_SIZE, MAX_GENERATION, SELECT_GENOME, GENOME_MUTATION, INDIVIDUAL_MUTATION
#     GENOME_LENGTH = genome_length
#     POPULATION_SIZE = population_size
#     MAX_GENERATION = max_generation
#     SELECT_GENOME = select_genome
#     GENOME_MUTATION = genome_mutation
#     INDIVIDUAL_MUTATION = individual_mutation


if __name__ == '__main__':

    population = Population()

    for i in range(MAX_GENERATION):
        print("---------------------")
        print(i, " :generation")

        # i世代目
        population.evolution()
        scores = population.get_scores()

        print(f"avg:{scores['avg']}  min:{scores['min']}  max:{scores['max']}")
```

## Genome

遺伝子クラスです。

One-Max問題のため、ある確率で突然変異として反転します。

## Individual

個体クラスです。
染色体を持っていて、この中に遺伝子が入ります。

適応度関数fitnessやmutate, two_point_crossoverなどを持っています。

## Population

世代クラスです。
個体群をlistとして持っています。

evolutionで世代交代を行い、次の世代へと更新します。

まずElete選択で強制的に強い個体を取り出します。
そして、規定数の個体数になるまで、今の世代から$2$体選択して交叉することを繰り返します。
最後に突然変異させます。

こうして次の世代を作ります。

## click

```python
#
# @click.command()
# @click.option('--genome_length', '-gl', type=int, default=30)
# @click.option('--population_size', '-ps', type=int, default=30)
# @click.option('--max_generation', '-mg', type=int, default=100)
# @click.option('--select_genome', '-sg', type=int, default=20)
# @click.option('--genome_mutation', '-gm', type=float, default=0.01)
# @click.option('--individual_mutation', '-im', type=float, default=0.01)
# def init(genome_length, population_size, max_generation, select_genome, genome_mutation, individual_mutation):
#     global GENOME_LENGTH, POPULATION_SIZE, MAX_GENERATION, SELECT_GENOME, GENOME_MUTATION, INDIVIDUAL_MUTATION
#     GENOME_LENGTH = genome_length
#     POPULATION_SIZE = population_size
#     MAX_GENERATION = max_generation
#     SELECT_GENOME = select_genome
#     GENOME_MUTATION = genome_mutation
#     INDIVIDUAL_MUTATION = individual_mutation

```

コマンドラインに対応させようとした残骸です。

## 結果

```
# 個体の遺伝子の長さ
GENOME_LENGTH = 50

# 世代の個体数
POPULATION_SIZE = 30

# 最大実行回数
MAX_GENERATION = 100

# エリート戦略
ELITE_SELECT = 5

# トーナメント戦略
TOURNAMENT_SELECT = 6

# 個体の突然変異確率
INDIVIDUAL_MUTATION = 0.1

# 個体の突然変異確率
GENOME_MUTATION = 0.1

---------------------
98  :generation
avg:46.233333333333334  min:38  max:47
---------------------
99  :generation
avg:46.833333333333336  min:42  max:47
```

上記の設定でトーナメント戦略で個体を選択して世代を交代させることを繰り返すと

$100$回更新した時、$47$個まで$1$を揃えることができました。
やはりなかなか最適解にはたどり着くことは現在は難しいですが、現実的な時間で近似解を求めることができました。

# 最後に

遺伝的アルゴリズムを軽くですが勉強してみました。
普段は群知能を勉強していますが、遺伝的アルゴリズムも面白いなぁと思いました。

ただ、順列などの問題は交叉が面倒だったりするため、問題によって表現の仕方の難しさが変わり、うまいことパラメータを合わせないといけないのは大変だなと感じました。

なにか間違いなどがあればアドバイスいただければと思います！