Population-based incremental learning

計算機科学や機械学習において、Population-Based Incremental Learning (PBIL) とは、最適化アルゴリズムの一つであり、分布推定アルゴリズムの一つ。遺伝的アルゴリズムの一種であり、個々の個体ではなく、全個体群の遺伝子型（確率ベクトル）が進化する^[1]。アルゴリズムはShumeet Balujaが1994年に提案した。このアルゴリズムは標準的な遺伝的アルゴリズムよりもシンプルであり、多くのケースで、標準的な遺伝的アルゴリズムよりも良い結果を示す^[2]^[3]^[4]。

アルゴリズム

PBIL において、遺伝子は0以上1以下の実数で表現され、その遺伝子において、特定の対立遺伝子が現れる確率を表している。

PBIL のアルゴリズムは以下の通り。

個体群が確率ベクトルから生成される。
個々の個体の適応度が計算され、順位付けされる。
個体群の遺伝子型（確率ベクトル）を個体の適応度に基づいて更新する。
突然変異する。
ステップ1-4を繰り返す。

ソースコード

これは、Javaで実装された、ソースコードの一部である。論文では、learnRate = 0.1、negLearnRate = 0.075、mutProb = 0.02、mutShift = 0.05 が使われている。小さな問題の場合、N = 100、ITER_COUNT = 1000 で十分である。

public void optimize() {
    final int totalBits = getTotalBits(domains);
    final double[] probVec = new double[totalBits];
    Arrays.fill(probVec, 0.5);
    bestCost = POSITIVE_INFINITY;
 
    for (int i = 0; i < ITER_COUNT; i++) {
        // N個の遺伝子を作成する
        final boolean[][] genes = new boolean[N][totalBits];
        for (boolean[] gene : genes) {
            for (int k = 0; k < gene.length; k++) {
                if (rand.nextDouble() < probVec[k])
                    gene[k] = true;
            }
        }

        // コストを計算する
        final double[] costs = new double[N];
        for (int j = 0; j < N; j++) {
            costs[j] = costFunc.cost(toRealVec(genes[j], domains));
        }

        // 最小・最大コストの遺伝子を探す
        boolean[] minGene = null, maxGene = null;
        double minCost = POSITIVE_INFINITY, maxCost = NEGATIVE_INFINITY;
        for (int j = 0; j < N; j++) {
            double cost = costs[j];
            if (minCost > cost) {
                minCost = cost;
                minGene = genes[j];
            }
            if (maxCost < cost) {
                maxCost = cost;
                maxGene = genes[j];
            }
        }

        // 最良コストの遺伝子と比較する
        if (bestCost > minCost) {
            bestCost = minCost;
            bestGene = minGene;
        }

        // 最小・最大コストの遺伝子で確率ベクトルを更新する
        for (int j = 0; j < totalBits; j++) {
            if (minGene[j] == maxGene[j]) {
                probVec[j] = probVec[j] * (1d - learnRate) +
                        (minGene[j] ? 1d : 0d) * learnRate;
            } else {
                final double learnRate2 = learnRate + negLearnRate;
                probVec[j] = probVec[j] * (1d - learnRate2) +
                        (minGene[j] ? 1d : 0d) * learnRate2;
            }
        }

        // 突然変異
        for (int j = 0; j < totalBits; j++) {
            if (rand.nextDouble() < mutProb) {
                probVec[j] = probVec[j] * (1d - mutShift) +
                        (rand.nextBoolean() ? 1d : 0d) * mutShift;
            }
        }
    }
}