読者です 読者をやめる 読者になる 読者になる

golangでDifferential Evolutionの実装

Golang プログラミング 遺伝的アルゴリズム Go

まとめ

golangでDifferential Evolution(差分進化法)の実装をおこなった

interfaceを使うことでうまく切り離した実装を行いたかったが、包丁ではなく手でちぎったような切り離しになり、よくない

アロケーションなどは特に考えなかったので、小さなテストデータでも解を求めるのに非常に時間がかかってしまっている(要改善)

追記

1

ランダムで3つの値を生成するときに毎回配列を生成していた箇所を配列を再利用することでアロケーションはかなり減らせたが、実行速度としてはほとんど変化なし

各個体のinterfaceは特に用意せず、個体の配列を操作するinterfaceのみに変更

2

rand.Seedでシードを設定している箇所がループの中で呼ばれているというミスを修正

目的

golangでinterfaceを使うことになれるためのプログラム開発

差分進化はパラメータの評価が比較可能で、パラメータ同士の演算ができれば計算可能なので、なんとなくinterfaceが想像しやすかったので試しに

実装

golangのversionは1.5.1

アルゴリズム

まずはこの記事のアルゴリズムで何をしたいのかを説明する

目的関数が以下のように定義されているとする

{
Z = x^{2} + y^{2}
}

上記の関数を最小化するようなxとyのパラメータを求めたいとすると、(x, y) = (0, 0)になる

このように簡単な目的関数であれば、すぐに解を求めることができるが複雑な関数になると計算が大変で最適解を求めるのが難しい

また、最適解であるのかどうかを判断することが難しい

そこで解の候補をランダムに生成して、その中で評価の高いパラメータを利用していくことで準最適解を求める

遺伝的アルゴリズムを簡単に言うとだいたいこんなところ

この記事で実装するのはDifferential Evolutionというアルゴリズムである

解の候補から重複しない3つを選び、2つの差分を残り1つに足したパラメータを新たな解の候補とする

新たに生成した解の候補のほうが評価が高ければ、次の世代のパラメータとする

また、局所解に陥ることが無いように一定の確率で評価の低いパラメータも遺伝する

かなりざっくりですが、おおよそこんなところです

プログラム

N世代目の個体とN+1世代目の個体のリストを持っているとして、次の世代を生成するためのinterfaceを実装する

package diffev

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

func init() {
    rand.Seed(time.Now().UnixNano())
}

/*
 * N 番目の世代の個体と N + 1番目の世代の個体の2つの配列を持つと想定している
 */
type EvolverData interface {
    SetSubValue(int, int, int) // n 番目の個体に i と j の個体の差分を設定する
    ScaleValue(int, float64)   // n 番目の個体を f 倍する
    AddValue(int, int)         // n 番目の個体に i の個体の値を足す
    Compare(int) bool          // n 番目の個体を前の世代と比較する(新しい個体の方が評価が高い場合は真)
    InheritParent(int)         // n 番目の個体に親の個体を引き継ぐ
    Swap()                     // N 番目と N + 1 番目の値を入れ替える
    Len() int                  // 個体数を取得する
}

type DiffEv struct {
    data    EvolverData
    indvN   int
    crossP  int
    repeatN int
    scaleF  float64
    cr      float64
}

func containsNum(ary []int, num int) bool {
    for _, v := range ary {
        if v == num {
            return true
        }
    }

    return false
}

func setRandNums(initN, max int, ary []int) {
    for i := 0; i < len(ary); {
        rNum := rand.Intn(max)

        if initN == rNum || containsNum(ary, rNum) {
            continue
        }

        ary[i] = rNum
        i += 1
    }
}

func (d *DiffEv) EvolveByDiff() {
    rAry := make([]int, 3)
    for i := 0; i < d.repeatN; i += 1 {
        for n := 0; n < d.indvN; n += 1 {
            setRandNums(n, d.indvN, rAry)
            d.data.SetSubValue(n, rAry[1], rAry[2])
            d.data.ScaleValue(n, d.scaleF)
            d.data.AddValue(n, rAry[0])

            if !(n == d.crossP || d.cr < rand.Float64() || d.data.Compare(n)) {
                d.data.InheritParent(n)
            }
        }

        d.data.Swap()
    }
}

func NewDiffEv(crossP, repeatN int, scaleF, cr float64, data EvolverData) (*DiffEv, error) {
    if data.Len() < 3 {
        return nil, fmt.Errorf("invalid number of individual")
    }

    if crossP < 0 || data.Len() < crossP {
        return nil, fmt.Errorf("invalid cross probability")
    }

    if repeatN < 1 {
        return nil, fmt.Errorf("invalid repeat number")
    }

    if scaleF < 0 {
        return nil, fmt.Errorf("invalid scale value")
    }

    if cr < 0 || 1 < cr {
        return nil, fmt.Errorf("invalid cr value")
    }

    return &DiffEv{
        data:    data,
        indvN:   data.Len(),
        crossP:  crossP,
        repeatN: repeatN,
        scaleF:  scaleF,
        cr:      cr,
    }, nil
}

Differential Evolutionでは、ある候補crossPとある確率crで評価が低いパラメータでも次の世代に引き継ぐことで局所解に陥ることがないようになっている

repeatNでは何世代まで計算を行うのかを設定している

scaleFは計算した差分の影響の重みを設定しており、小さいとパラメータの値があまり大きくは変化しない

テスト

テストでは目的関数を以下のように設定し、100個体2000世代を計算した

Zは値が大きいほど評価が高いものとする(最適解は(0,0))

{
Z = -x^{2} - y^{2}
}

parameter: &{-1.655360682766549 6.005544599539681} ===> &{2.0119567949243818e-162 8.485657984289152e-163}
score:  -38.806785  ===>  -0.000000
PASS
ok      github.com/mizkei/diffev    10.161s

一応ほぼ最適解に近いパラメータにはなっている

ただ、異様に遅いので、ベンチマークを取ると

10091344240 ns/op     6408616 B/op     200226 allocs/op
ok      github.com/mizkei/diffev    10.093s

ご覧のとおりですね

流石にこれはないので、改善していきます

追記

10360028271 ns/op        6568 B/op        220 allocs/op
ok      github.com/mizkei/diffev    10.365s

アロケーションは減りましたが、実行時間は特に変化なしです

追記 2

rand.Seedの設定をループの中に記述してしまっていたので、これを修正

2000000000            0.03 ns/op        0 B/op          0 allocs/op
ok      github.com/mizkei/diffev    0.466s

おおよそ問題無い速度になったと思います github

問題

  • おそらくinterfaceの定義がよくない
  • interfaceがよくないので、結局使用者は自身で色々とかく必要がある -> すこし改善
  • アロケーションが多すぎて計算時間がかかりすぎている -> アロケーションの問題ではなかった -> 単純に乱数設定の問題でした

参考