Zenn
🌱

Juliaで遺伝的アルゴリズムの例を動かした (ウェブ最適化ではじめる機械学習§4.6)

2021/01/05に公開
Julia
tech

タイトルの通りですが，ウェブ最適化ではじめる機械学習 (オライリー) (こちらはAmazonのリンクですが，執筆時☆5という評判の本です)という本にメタヒューリスティクスの章があります (4章)．その中の§4.6で遺伝的アルゴリズムをgithubなどのデフォルトアイコンっぽいアイコン生成に適用するという例題があったので，これをJuliaで書いてみました．

実装ですが，こちらにJupyter notebookで置きました．

https://github.com/cocomoff/JuliaIdentIcon

出力されるアイコンの例

乱数で生成されるアイコンです．

交叉の例です．

変異の例です．

実装について

アイコンの表現について

もともとの実装はPythonのnumpyを利用されていますが，ほとんどそのままJuliaで真似して実装することができます．元の実装では8x8のアイコンに対して，左半分の8x4を一次元配列として保持し，交叉や変異を実装しています．描画する際は左右折り返して実装します．Juliaでは次のように書きました．

# 1つのアイコン(S×S/2)の作成
generate_solution(;S=SIZE) = rand(0:1, S * div(S, 2))

# 描画できる形式(S×S)に直す
function represent(s; S=SIZE)
    smat = reshape(s, (S, div(S, 2)))
    [smat reverse(smat, dims=2)]
end

アイコンの描画について

PyPlotを使っても良かったですが，Plots.jl (+ GR)で描画しました．Layoutの指定のところが非常に雑でダメです (他にいいやり方が分からなかったです)．こちらで作成した手法が上の例になります．

# 描画用の大きさ
const PX = 120
const PY = 120
ST = (PX, PY)

# 解の個数と初期解
N = 10
solutions = zeros(Int, N, SIZE * div(SIZE, 2))
for n in 1:N
    solutions[n, 1:end] = generate_solution()
end

# heatmapをN個作ってまとめて描画する
h = []
for n in 1:N
    rs = represent(solutions[n, 1:end])
    hn = heatmap(rs, aspect_ratio=1, colorbar=false, title="$n", size=ST, ticks=false, xaxis=false, yaxis=false, c=:thermal)
    push!(h, hn)
end

# plot all
fig = plot(h[1], h[2], h[3], h[4], h[5], h[6], h[7], h[8], h[9], h[10], layout=(2, 5),
aspect_ratio=1, colorbar=false, size=(PX * 5, PY * 2), ticks=false, c=:thermal)
savefig(fig, "icons.png")
fig

交叉について

もともとのデータが8×4=32次元の1次元ベクトルになっているため，2つの個体を交叉するためにある乱数を選択し，その前後で個体のデータをコピーしてきます．もう少しスマートに書ける気がしていたのですが，よく分からなかったのでベタ書きしました．

function crossover(s1, s2; size=SIZE)
    t = rand(1:(size * div(size, 2)))
    s12 = zeros(Int, size * div(size, 2))
    s12[begin:t] = s1[begin:t]
    s12[t:end] = s2[t:end]
    s12
end

変異について

交叉と同じですが，データをcopyしておきます (これをしないと変異できません)．

function mutation(s; size=SIZE)
    t = rand(1:(size * div(size, 2)))
    new_s = copy(s)
    new_s[t] = (new_s[t] + 1) % 2
    new_s
end

次世代の作成について

親世代から2つ選択して交叉させますが，標準ライブラリでreplace=falseのサンプリングをやる方法が分からなかったので，StatsBaseを使っています．親世代の解を選び，その個数(size(parents)[1]))に対して，2つ選ぶ部分です．

using StatsBase

function generate_next_generation(parents; MUT_N=3, S=SIZE)
    solutions = zeros(Int, length(parents), S * div(S, 2))
    for n in 1:N
        i, j = sample(1:size(parents)[1], 2, replace=false)
        solutions[n, 1:end] = crossover(parents[i, :], parents[j, :])
    end
    # ...
end

まとめ

面白かったです．著者によるPythonのサンプルコードはオライリーのサイトからリンクされています．

Discussion