この記事は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