この記事はtomowarkar ひとりAdvent Calendar 2019の16日目の記事です。

遺伝的アルゴリズムとは

遺伝的アルゴリズム（いでんてきアルゴリズム、英語：genetic algorithm、略称：GA）とは、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。人工生命同様、偶然の要素でコンピューターの制御を左右する。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。wikipedia 遺伝的アルゴリズム

ルール

ビット列の遺伝子配列を持つ個体の操作を行う
個体の集まりを集団とする
ビット配列内の1の数を評価する
遺伝子配列が全て1の個体が現れるまで集団内での世代交代を行う
世代交代は一定確率に基づき淘汰、交差、選択、突然変異が行われる

$$
\left[
\begin{array}
0 &1 &0& 0 &1&\ldots &0 &1 &0 &1\
\end{array}
\right]
$$
これを
$$
\left[
\begin{array}
1 &1 &1& 1 &1&\ldots &1 &1 &1 &1\
\end{array}
\right]
$$
こうなるまで世代交代するのだ

コード

main()

遺伝子配列が全て1の個体が現れるまでループさせる。

package main

import (
    "fmt"
    "math/rand"
    "sort"
)

const (
    // 淘汰率, 交差率, 突然変異率
    selectionRate, crossRate, mutateRate = 0.2, 0.2, 0.05
)

func main() {
    // 遺伝子長, 集団の大きさ
    nGene, nIndividual := 50, 100
    population := createPopulation(nGene, nIndividual)
    for i := 0; ; i++ {
        population = changeGeneration(population)
        sortGenes(population)
        fmt.Println(population[0].gene, population[0].nOnes)
        if population[0].nOnes == nGene {
            fmt.Println(i+1, "世代")
            break
        }
    }
}

Gene

遺伝子配列を保持する構造体
処理をしやすくするために評価値を一緒に格納

// Gene : 遺伝子情報
type Gene struct {
    gene  []int // 遺伝子配列
    nOnes int   // ターゲットの数
}

changeGeneration(gs []Gene) []Gene

世代以降の関数
一定確率で突然変異、交差、コピーを行い次世代配列を作成
自己分裂で自分と異なる遺伝子をもつ個体を生成する可能性を持っているが気にしない

func changeGeneration(gs []Gene) []Gene {
    var nextGeneration []Gene
    sortGenes(gs)

    // 選択, 淘汰
    elites := gs[:int((1-selectionRate)*float64(len(gs)))]
    for {
        pos := rand.Intn(len(elites))
        switch n := rand.Float64(); {
        case n < mutateRate:
            // 突然変異
            nextGeneration = append(nextGeneration, mutate(elites[pos]))
        case n > 1-crossRate:
            // 交差
            nextGeneration = append(nextGeneration, crossing(elites[pos], elites[rand.Intn(len(elites))]))
        default:
            // コピー
            nextGeneration = append(nextGeneration, elites[pos])
        }
        if len(nextGeneration) == len(gs) {
            break
        }
    }
    return nextGeneration
}

createPopulation(nGene, nIndividual int) []Gene

第0世代を作成するための関数
ランダムな遺伝子を持つ個体を生成する

func createPopulation(nGene, nIndividual int) []Gene {
    var population []Gene
    for i := 0; i < nIndividual; i++ {
        gene := make([]int, nGene)
        for j := 0; j < nGene; j++ {
            gene[j] = rand.Intn(2)
        }
        population = append(population, Gene{gene: gene, nOnes: countOnes(gene)})
    }
    return population
}

countOnes(gene []int) int

遺伝子の評価関数
遺伝子配列の中の1の数をカウントして返す

func countOnes(gene []int) int {
    var ans int
    for i := 0; i < len(gene); i++ {
        ans += gene[i]
    }
    return ans
}

sortGenes(gs []Gene)

遺伝子集団を評価値に基づきソートする関数
破壊的ソートだが今回は集団の順番は特段意味を持たないのでOK

func sortGenes(gs []Gene) {
    sort.SliceStable(gs, func(i, j int) bool {
        return gs[i].nOnes > gs[j].nOnes
    })
}

mutate(g Gene) Gene

突然変異の関数
遺伝子配列の一部の値を反転させる

func mutate(g Gene) Gene {
    position := rand.Intn(len(g.gene))
    if g.gene[position] == 0 {
        g.gene[position] = 1
    } else {
        g.gene[position] = 0
    }
    g.nOnes = countOnes(g.gene)
    return g
}

crossing(parent1, parent2 Gene) Gene

交差の関数
二つの遺伝子を交差させ、子供を作る
二点交差を使用

func crossing(parent1, parent2 Gene) Gene {
    var child1 []int
    // 二点交差
    splitR := rand.Intn(len(parent1.gene)-1) + 1
    splitL := rand.Intn(splitR)

    child1 = append(child1, parent1.gene[:splitL]...)
    child1 = append(child1, parent2.gene[splitL:splitR]...)
    child1 = append(child1, parent1.gene[splitR:]...)

    return Gene{gene: child1, nOnes: countOnes(child1)}
}

結果

[0 1 0 0 1 0 1 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 0 1 0 1] 30
[1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 0 0] 30
[1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 0 0] 32
[1 1 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 0 0] 32
[0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 1 0 1 0 0 0 1 1 0] 33
・
・
・
[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 0 1 1 1 1 1] 49
[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 0 1 1 1 1 1 1 1 1 1 1 1 1 1] 49
[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] 50
158 世代

考察

30回平均

以下淘汰率,交差率,突然変異率の値をかえ、30回平均をとった値

	世代数	淘汰率	交差率	突然変異率
1	181	0.2	0.2	0.05
2	627	0.25	0.2	0.05
3	100	0.2	0.25	0.05
4	90	0.25	0.25	0.05
5	268	0.2	0.2	0.1
6	554	0.25	0.2	0.1
7	129	0.2	0.25	0.1
8	111	0.25	0.25	0.1

この結果のみでは断定できないが、ざっと以下のことが読み取れそう

突然変異率を上げると目的の個体が現れるまでに時間がかかる
淘汰率>交差率において目的の個体が現れるまでに時間がかかる
淘汰率, 交差率をあげると目的の個体が現れるのが早くなる

これらは体感的にも納得ですね
1. は評価値が高いものまで突然変異で値が変わってしまい、収束までに時間がかかる。2. は同じような個体ばかりになり収束しない(これは適度に枝狩りされて早めに収束することもある)。3. は結果的に世代交代のスパンが早まってるのと同意だから。

淘汰率(または突然変異率)が交差率に対して大きいと収束しないことがある。
といのもあり、これも体感と一致。

まとめ

以上明日も頑張ります！！
tomowarkar ひとりAdvent Calendar Advent Calendar 2019

参考

https://algoful.com/Archive/Algorithm/ga
https://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

Goで遺伝アルゴリズムらしきものを実装する