遺伝的アルゴリズムの並列化とgoroutineによる実装

先日、「遺伝的アルゴリズムをGoで実装してみた」という記事を書きました。
この内容で2019年7月13日（土）に開催されるGo Conference'19 in Fukuokaに登壇させていただくことになったので、開発中のeagoというパッケージをもっと作り込んで行きたいと思います。
今回は、遺伝的アルゴリズム（以下、GA）の計算処理をgoroutineでサクッと並列化した話です。

概要

GAは複数の個体を用いた多点探索のアルゴリズムであるため、本質的に並列化と親和性が高い手法であると言えます。実用的な観点からも短い計算時間で良好な解を得ることが望まれているため、これまでに数多くの並列化手法が提案されています。

今回はGo言語の強みの一つであるgoroutineを使ってGAの処理の一部を並列化してみます。また、擬似問題に対してベンチマークを取り、実装した並列処理が全体の計算時間短縮に有効であることも検証しました。

代表的な並列化手法

マスタースレーブ方式

GAを並列化するための最も単純な手法は適応度計算を並列化することです。マスタースレーブ方式では下図のように、全体の制御および遺伝的操作を行うマスターと、適応度計算を行う複数のスレーブから構成されます。

f:id:hirotsuru314:20190619141143p:plain — マスタースレーブ方式

この方式は、同時に計算できる処理を並列化しただけの極めて単純かつ一般的な手法であり、GA固有の並列化処理ではありません。
今回はこちらをgoroutineを使って実装してみます。

島モデル

島モデルはGA自体を並列化するというアプローチをとっています。集団を複数の部分集団に分割することでGAを同時に実行し、並列処理を実現しています。
その概要を下図に示します。

f:id:hirotsuru314:20190619142435p:plain — 島モデル

それぞれの部分集合を初期化して、評価・選択・交叉・突然変異などをそれぞれで行います。ここで本手法の重要な特徴となるのが、ある一定の条件を元に部分集団から一部の個体を選んで交換を行う点です。このプロセスにより、島モデルは並列化手法であるという側面のほかに、個体の多様性を維持するための手法としての側面も併せもちます。

goroutineによる並列化

今回はマスタースレーブ方式を実装してみます。前述の通り、マスタースレーブ方式では適応度計算を並列化するため、適応度関数（目的関数）が非常に複雑で計算処理に時間がかかる場合に有効な並列化であると言えます。
個体群に属するそれぞれの個体の適応度計算は独立して行えるため、この適応度計算をするためのスレーブとしてgoroutineを立ち上げて、並列で計算を行うようにします。マスターについては、それぞれのスレーブの計算結果を受け取るプロセスがいるというよりは、それぞれのスレーブが以下のように定義したIndividual構造体のFitnessに計算結果を書き込むことで、以降の処理で全ての結果を参照できるようにしています。

type Individuals []Individual

type Individual struct {
    Chromosome Genome
    Fitness    float64
    Evaluated  bool
}

実装にはsync.WaitGroupを用いました。
WaitGroupを用いると、独立した複数のタスクを平行で処理して、それら全ての終了を待ち合わせる処理が非常にシンプルな記述で実装できます。

func (indis Individuals) Evaluate(parallel bool) {
    var wg sync.WaitGroup
    if !parallel {
        for i := range indis {
            indis[i].Evaluate()
        }
    } else {
        for i := range indis {
            wg.Add(1)
            go func(i int) {
                defer wg.Done()
                indis[i].Evaluate()
            }(i)
        }
        wg.Wait()
    }
}

上記の Evaluate() の部分が適応度計算の関数です。
WaitGroupはカウンターのようになっていて、Addを呼び出すと引数に渡された整数だけカウンターを増やし、Doneを呼び出すとカウンターを1つ減らします。そしてWaitを呼び出すとカウンターがゼロになるまでブロックします。

パフォーマンス検証

実行時間の測定には、testingパッケージに備わっているベンチマークの仕組みを用いました。
並列化が有効かどうかを検証するために、実用的ではないですが、適応度関数の中で1 ms sleepするようにして、擬似的に計算処理に時間がかかる適応度関数を作りました。

ベンチマークのための全体コードの以下のようになります。

package main

import (
    "github.com/tsurubee/eago"
    "log"
    "testing"
    "time"
)

type Vector []float64

func (V Vector) Initialization() eago.Genome {
    return Vector(eago.InitFloatVector(2, 32, -32))
}

func (V Vector) Fitness() float64 {
    time.Sleep(1 * time.Millisecond) // Heavy process
    var s float64
    for _, x := range V {
        s += x * x
    }
    return s
}

func (V Vector) Mutation() {
    eago.AddNormalFloat(V, 0.5)
}

func (V Vector) Crossover(X eago.Genome) eago.Genome {
    return Vector(eago.BLXalpha(V, X.(Vector), 0.3))
}

func BenchmarkParallelGA(b *testing.B) {
    for i := 0; i < b.N; i++ {
        runGA(true)
    }
}

func BenchmarkNonParallelGA(b *testing.B) {
    for i := 0; i < b.N; i++ {
        runGA(false)
    }
}

func runGA(parallel bool) {
    var v Vector
    ga := eago.NewGA(eago.GAConfig{
        PopulationSize: 30,
        NGenerations:   20,
        CrossoverRate:  0.8,
        MutationRate:   0.01,
        ParallelEval:   parallel,
    })
    ga.PrintCallBack = func() {} // Do not print messages while running
    if err := ga.Minimize(v); err != nil {
        log.Fatal(err)
    }
}

このファイルを *_test.goという形式で保存して、ファイルが存在するディレクトリで以下のようなコマンドを実行することでベンチマークが取得できます。

$ go test -bench .
goos: darwin
goarch: amd64
pkg: github.com/tsurubee/eago/examples/ga
BenchmarkParallelGA-4             50      37193820 ns/op
BenchmarkNonParallelGA-4           2     821147753 ns/op
PASS
ok      github.com/tsurubee/eago/examples/ga    4.365s

適応度関数内でのsleepの時間を1・5・10 msにして、並列化あり（parallel）並列化なし（non-parallel）における処理時間をグラフにすると以下のようになりました。

f:id:hirotsuru314:20190623114700p:plain

今回のベンチマークの条件では、個体数30、世代数20であるため、適応度計算は600回程度行われ、sleepが10 msのときに処理を並列化しない場合は、適応度計算だけでも6000 msかかることになります。
このことを考えると、適応度計算が重い場合に、今回のようなマスタースレーブ方式の並列化が、全体の処理時間の短縮に有効であることがわかります。