CGA（Compact GA）〜遺伝子の分布を推定する遺伝的アルゴリズム

目次

はじめに

　CGA（Compact GA）とは，確率ベクトルから個体を生成・評価し確率ベクトルを修正していくことで最適化を行う遺伝的アルゴリズム（GA）の1つです．

　CGA の特徴は，同時に存在する個体は2つのみであるという点です．そのため，他の GA と比べてメモリ消費量が非常に少なくなります．

　この記事では CGA のアルゴリズムを紹介し，実際に簡単な最適化問題に適用してみたいと思います．

アルゴリズム

　CGAでは交叉や突然変異といった遺伝的操作は行わず，確率ベクトルを元に2つの個体を生成し，それらの適応度を確率ベクトルにフィードバックしていくことで最適化を進めていきます．以下ににその手順を示します．

1. 確率ベクトル p に対し， i 番目の要素 p[i] = 0.5 （ i = 1, 2, ..., L ) として初期化する
2. 確率 p[i] より，2つの固体 a, b を生成する
3. 個体 a, b を評価し，評価値の高い方を winner， 低い方を loserとする
4. winner, loser の i 番目の遺伝子 winner[i], loser[i] について， winner[i] ≠ loser[i] の場合，次のようにして確率ベクトルを更新する
   1. winner[i] = 1 の場合， p[i] = p[i] + 1/n
   2. winner[i] = 0 の場合， p[i] = p[i] - 1/n
5. p の全ての要素に対し， p[i] = 1 または p[i] = 0 となれば終了．そうでなければ2へ戻る

　L は個体の長さ，n は GA における集団のサイズを想定した定数です．CGA は集団サイズ n のGAをシミュレートしていることになります．

実装

　ここでは100ビットの OneMax 問題を解きます．100ビットなので個体の長さ L = 100 とし，集団サイズは n = 100 としました．

　Julia (1.1.0) で実装しました．上記のアルゴリズムを素直に書いただけのプログラムです．

mutable struct Individual
    chrom::Array{Int64,1}
    fitness::Float64
end

function fitnessFunc(chrom::Array{Int64,1})
    sum(chrom)
end

function isConverged(prob::Array{Float64,1})
    for i = 1:length(prob)
        if 0 < prob[i] < 1 
            return false
        end
    end
    return true
end

const CHROM_LENGTH = 100
const POPULATION_SIZE = 100

function main()
    prob = Array{Float64, 1}(undef, CHROM_LENGTH)

    fill!(prob, 0.5)

    ind_a = Individual(Array{Int64,1}(undef, CHROM_LENGTH), 0.0)
    ind_b = Individual(Array{Int64,1}(undef, CHROM_LENGTH), 0.0)

    gen = 0
    while !isConverged(prob)
        gen += 1
        println(gen)

        for i = 1:CHROM_LENGTH
            if prob[i] > rand()
                ind_a.chrom[i] = 1
            else
                ind_a.chrom[i] = 0
            end

            if prob[i] > rand()
                ind_b.chrom[i] = 1
            else
                ind_b.chrom[i] = 0
            end
        end

        ind_a.fitness = fitnessFunc(ind_a.chrom)
        ind_b.fitness = fitnessFunc(ind_b.chrom)

        if ind_a.fitness >= ind_b.fitness
            winner = ind_a
            loser = ind_b
        else
            winner = ind_b
            loser = ind_a
        end

        for i = 1:CHROM_LENGTH
            if winner.chrom[i] != loser.chrom[i]
                if winner.chrom[i] == 1
                    prob[i] += 1/POPULATION_SIZE
                else
                    prob[i] -= 1/POPULATION_SIZE
                end
            end
        end
    end

    println("gen: $(gen), prob: $(round.(prob))")
end

main()

　以下が実行結果です．

gen: 1560, prob: [1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0]

　1560世代で全てのビットが1になりました．数回実行してみましたが，だいたい1500世代前後で収束します．

　集団サイズをより小さくすると，ある程度のサイズまではより早く収束しました（だいたい40くらいまで）． 集団サイズ大きくすると世代数も大きくなりますが，一応収束しました．（集団サイズ1000000で試してみると19425050世代で収束しました）

　評価関数を書き換えればいろんな問題に適用できるので，パラメータと合わせていろいろ変えて試してみると面白いと思います．

参考

[1] 棟朝雅晴『遺伝的アルゴリズムーその理論と先端的手法ー』[POD版] , 森北出版

[2] G.R. Harik , F.G. Lobo , D.E. Goldberg. The compact genetic algorithm. IEEE Transactions on Evolutionary Computation ( Volume: 3 , Issue: 4 , Nov 1999 ) p.287-297. 1999