Juliaで遺伝的アルゴリズムを書く

• 今アツいJuliaで遺伝的アルゴリズムを書きたい
• 拡張性が高くなるよう、パッケージ化したい

遺伝的アルゴリズムとは

省略。

Juliaとは

同じく。

モジュールを定義

module GeneticAlgorithm
    using Base,Random
    export GeneList,run!

    mutable struct GeneList
        children::Vector        # 遺伝子geneのリスト
        initfun                 # 初期化関数
        evalfun                 # 評価関数
        mutatefun!              # 突然変異関数
        crossoverfun            # 交叉関数
        endfun                  # 終了条件
        tostringfun             # printする関数
        population::Int64       # 遺伝子数
        elite_rate::Float64
        mutation_rate::Float64
        elites_num::Int64
        N::Int64
    end

    # constructor
    function GeneList(
        initfun, 
        evalfun, 
        mutatefun!, 
        crossoverfun, 
        endfun, 
        tostringfun
        ; 
        population=100, 
        elite_rate=0.1, 
        mutation_rate=0.02, 
        N=100
    )

        gl = GeneList(
            [],
            initfun,
            evalfun,
            mutatefun!,
            crossoverfun,
            endfun,
            tostringfun,
            population,
            elite_rate,
            mutation_rate,
            Int(floor(population * elite_rate)),
            N
        )
        return gl
    end

    # 初期化
    function init!(gl::GeneList)
        gl.children = []
        for _ in 1:gl.population
            push!(gl.children, gl.initfun())
        end
    end

    # 達成条件
    function achieved(gl::GeneList)
        return gl.endfun(gl.children[1])
    end

    # evalの値ごとに並び替え
    function sort!(gl::GeneList)
        comp(a,b) = gl.evalfun(a) < gl.evalfun(b)
        Base.sort!(gl.children, lt=comp, rev=true)
    end

    # 突然変異
    function mutate!(gl::GeneList)
        for g in gl.children
            if rand(Float64) < gl.mutation_rate
                gl.mutatefun!(g)
            end
        end
    end

    # 交叉
    function crossover!(gl::GeneList)
        news = []
        for i in 1:gl.population
            m = rand(1:gl.elites_num)
            n = rand(1:gl.elites_num)
            push!(news, gl.crossoverfun(gl.children[m], gl.children[n]))
        end
        gl.children = news
    end

    # 文字列に変換
    function tostring(gl::GeneList)
        return gl.tostringfun(gl.children[1]) * " => " * string(gl.evalfun(gl.children[1]))
    end

    # 実行
    function run!(gl::GeneList)
        init!(gl)

        for cnt in 1:gl.N
            sort!(gl)
            println("【第"*string(cnt)*"世代】\t" * tostring(gl))
            if (achieved(gl))
                return gl.children[1]
            end
            mutate!(gl)
            crossover!(gl)
        end

        sort!(gl)
        println(string(gl.children[1]))
        return gl.children[1]
    end
end

モジュールを使用してOneMax問題を実装

using .GeneticAlgorithm

initfun() = rand((0,1),50)

function evalfun(g)
    len = length(g)
    ones = fill(1,(1,len))
    return (ones * g)[1] / len
end

function mutatefun!(g)
    p = rand(1:length(g))
    g[p] = (g[p] + 1) % 2
end

function crossoverfun(g1, g2)
    p = rand(1:(length(g1)-1))
    return cat(g1[1:p],g2[p+1:length(g2)],dims=1)
end

function endfun(g)
    return evalfun(g) == 1
end

function tostringfun(g)
    return join(g, "")
end

実行結果

N=100 （愚直に100回実行）

julia> gene = GeneList(initfun, evalfun, mutatefun!, crossoverfun, endfun, tostringfun, N=100)
run!(gene)

【第1世代】	00111101111111101100111111110001010001010010111111 => 0.66
【第2世代】	00111111111001111011011101001111111001110111111011 => 0.74
【第3世代】	00111111111001111110111011111111110101010010111111 => 0.76
【第4世代】	00111101111111101100111111111111110111111111011110 => 0.82
【第5世代】	00111101111111101100111111111111110111111111011111 => 0.84
【第6世代】	00111111111111111110111011111111110111111111111011 => 0.88
【第7世代】	00111111111111111110111011111111110111111111111111 => 0.9
【第8世代】	00111111111111111110111111111111110111111111111111 => 0.92
...
【第55世代】	10111111111111111110111111111111110111111111111111 => 0.94
【第56世代】	10111111111111111110111111111111111111111111111111 => 0.96
...
【第100世代】	10111111111111111110111111111111111111111111111111 => 0.96
[1, 0, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

5%で突然変異させる

julia> gene = GeneList(initfun, evalfun, mutatefun!, crossoverfun, endfun, tostringfun, N=100, mutation_rate=0.05)
run!(gene)

【第1世代】	10001111100010011110111111111010101110011100111101 => 0.66
【第2世代】	01111111111001101100111011011110111011011111011110 => 0.74
【第3世代】	11111111101001011111010111111110111011011111011110 => 0.78
【第4世代】	11111111101001011111011011011110111011011111111111 => 0.8
【第5世代】	11111111101001011111011111111110111011011111111111 => 0.84
【第6世代】	11111111101001011110111111111011111011011111111111 => 0.84
【第7世代】	11111111111001110110111111111110111011011111111111 => 0.86
【第8世代】	11111111111001111110111111111011111011011111111111 => 0.88
【第9世代】	11111111111001111110111111111011111011011111111111 => 0.88
【第10世代】	11111111111001111110111111111111111011011111111111 => 0.9
【第11世代】	11111111111001111110111111111111111011011111111111 => 0.9
【第12世代】	11111111111001111110111111111111111011011111111111 => 0.9
【第13世代】	11111111111001111111011111111111111011011111111111 => 0.9
【第14世代】	11111111111001111111011111111111111011011111111111 => 0.9
【第15世代】	11111111111001111111111111111111111011011111111111 => 0.92
...
【第48世代】	11111111111001111111111111111111111011011111111111 => 0.92
【第49世代】	11111111111001111111111111111111111111011111111111 => 0.94
..
【第63世代】	11111111111001111111111111111111111111011111111111 => 0.94
【第64世代】	11111111111101111111111111111111111111011111111111 => 0.96
...
【第84世代】	11111111111101111111111111111111111111011111111111 => 0.96
【第85世代】	11111111111101111111111111111111111111111111111111 => 0.98
...
【第100世代】	11111111111101111111111111111111111111111111111111 => 0.98
[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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

結論

精度としては微妙だが、割と転用しやすいライブラリっぽくできた気がする。