Rustで遺伝的アルゴリズムを書く - じゃあ、おうちで学べる

8ビットの候補を組み合わせて変化させながら、最良個体をそのまま残すイメージ

最も得点の高い候補を残しながら、別の候補も試します。各図の個体数やビット列は説明用の例で、コードの実行結果ではありません。

はじめに

遺伝的アルゴリズムは、複数の答えの候補を用意し、それらを組み合わせたり一部を変えたりしながら、より良い答えを探す計算方法です。まず、何を「良い」とするかを得点で表せるようにし、各候補を採点します。その得点をもとに材料となる候補を選び、新しい候補を作ります。新しい候補も採点し、同じ操作を繰り返します。

「遺伝的」という名前は、生物の遺伝や自然選択をヒントにしていることに由来します。候補を「個体」、新しい候補の材料にする個体を「親」、そこから作った候補を「子」と呼びます。親の一部を組み合わせる操作が「交叉」、ランダムに一部を変える操作が「突然変異」です。こうした操作を使い、候補の集まりを世代ごとに更新していきます。

たとえば、翌日の作業を複数の設備へ割り当てる場面を考えます。すべての組み合わせを比べ終わる前に、計画を渡す時刻が来てしまうとします。そこで複数の割り当て案を採点し、良い案ほど次の案の材料に選ばれやすくして、別の割り当ても試します。遺伝的アルゴリズムは、試す回数を限りながら候補を改善したい時に検討できます。ただし、必ず最も良い答えが見つかるわけではなく、期限や設備の上限を守れているかも別に確かめる必要があります。

今回は仕組みを復習するために、Rustで8個のビットをすべて1にする処理を書きます。ビットは0か1の値で、たとえば00001111なら1が4個あるので4点です。目指す答えは11111111で、最初から分かっています。それでも探索を書くのは、候補を選び、組み合わせ、変化させる処理を自分で説明できるようにするためです。さらに、その時点で最も得点の高い候補を残し、探索を続けても失わないことを確かめます。

AIへ実装を頼む時も、手法そのものを学びたいのか、仕事で使う答えが欲しいのかで依頼は変わります。この例で交叉や突然変異を書くのは、答えを得るためというより、その手法を理解するためです。

候補と評価値を決める

候補1個を個体、候補をまとめたものを集団、集団を1回更新する単位を世代と呼びます。00001111の評価値は4、11111111は8です。この評価値を計算する関数を目的関数と呼び、値が大きい候補ほど良い候補とします。8ビットなら評価値の上限は8なので、最適値もあらかじめ分かります。

答えだけが必要なら、最初から11111111を返せます。この例ではその分かっている答えを24個体、150世代の探索で求めます。答えが分かっているからこそ、候補の作り方、評価、最良個体の保存が期待どおりに働くかを確かめられます。

最良個体を残しながら世代交代する

候補をu8で表し、評価にはcount_onesを使います。親は2個体のトーナメントで選び、1点交叉で子を作ります。最良個体をそのまま残すため、世代を進めても最良値は悪化しません。

トーナメントはランダムに選んだ2個体を比べ、1の多い方を親にする操作です。

トーナメント選択。ランダムに選んだ2個体のうち、1の数が多い候補を親にする

1点交叉ではビット列を1か所で分け、一方の親から下位側、もう一方から上位側を受け継ぎます。コードのmaskがその境界を表します。さらに確率1/8で1ビットを反転する突然変異を加え、親の組み合わせだけでは作れない候補も試します。

1点交叉と突然変異の例。親Bの上位4ビットと親Aの下位4ビットを合わせ、突然変異では1ビットを反転する

集団の大きさは24です。次の集団の先頭に最良個体をコピーし、残り23個を子で埋めます。乱数の初期状態を表すseedを同じ値にすると、同じ順序で候補を作れます。この乱数生成器は初期状態が0だと値が変化しないため、seedに0を渡すと入力の検査で拒否します。

最良個体をコピーする処理をエリート保存と呼びます。次の集団にも現在の最高点の個体が必ず残るので、集団内の最高点は下がりません。一方、全個体を最良個体のコピーにすると、個体間の違いが失われます。良い候補を保持することと、まだ試していない候補を作ることの両方が必要です。乱数生成器は再現用で、暗号用途には使いません。

fn random(state: &mut u64) -> u64 {
    *state ^= *state << 13;
    *state ^= *state >> 7;
    *state ^= *state << 17;
    *state
}

fn evolve(mut seed: u64, generations: usize) -> u8 {
    assert_ne!(seed, 0);
    let mut population: Vec<u8> = (0..24).map(|_| random(&mut seed) as u8).collect();
    let parent = |population: &[u8], seed: &mut u64| {
        let a = population[random(seed) as usize % population.len()];
        let b = population[random(seed) as usize % population.len()];
        if a.count_ones() >= b.count_ones() { a } else { b }
    };
    for _ in 0..generations {
        population.sort_by_key(|value| std::cmp::Reverse(value.count_ones()));
        let mut next = vec![population[0]];
        while next.len() < population.len() {
            let a = parent(&population, &mut seed);
            let b = parent(&population, &mut seed);
            let cut = 1 + random(&mut seed) % 7;
            let mask = ((1_u16 << cut) - 1) as u8;
            let mut child = (a & mask) | (b & !mask);
            if random(&mut seed) % 8 == 0 {
                child ^= 1 << (random(&mut seed) % 8);
            }
            next.push(child);
        }
        population = next;
    }
    population.into_iter().max_by_key(|v| v.count_ones()).unwrap_or(0)
}

fn main() {
    let initial = evolve(7, 0).count_ones();
    let result = evolve(7, 150);
    assert!(result.count_ones() >= initial);
    assert_eq!(result.count_ones(), 8);
    assert_eq!(evolve(7, 150), result);
}

最後の3つの検査では、初期集団より最高点が下がらないこと、このseedで最適値8へ達すること、再実行で同じ結果になることを確認します。突然変異の確率1/8は「子1個について1ビットを反転する確率」です。各ビットを個別に1/8で反転する実装とは、1回で起こる変更の数が違います。

エリート保存。現在の最良個体を次の集団へそのままコピーし、残りを新しい子で埋める。同じ評価式なら最高点は下がらない

全探索との費用比較

実際のジョブの割り当てなどへ広げる時は、全候補を調べる案と、評価回数を制限して良い候補を探す案を比べられます。後者を選ぶなら、最適性を証明できない結果でも用途を満たせることが前提です。小さな入力では全探索と比べ、全探索で求めた最良値との差と評価回数を記録できます。差が許容範囲を超える時や、問題が小さく全探索でも間に合う時は、手法を選び直す理由になります。

AIへの依頼も手法を学ぶ目的か、答えを安く求める目的かで変わります。前者なら交叉や突然変異を指定し、各操作を確かめることに意味があります。後者なら、8ビットの全256通りを調べる案も比較対象です。探索方法を比べる時は、乱数の初期値を変え、同じ候補評価回数で得られる値を見ます。手法名を先に指定すると、その手法を使わずに済む案は比較から外れます。

候補の有効性を確かめる

探索の効率とは別に、候補として有効かを確かめます。ジョブの実行順や担当の割り当てには、期限や設備の上限など、破ってはいけない条件があります。作業が1件抜けた割り当ては、所要時間だけなら短く見えてしまいます。

候補の有効性を得点の減点だけで表す時には注意が必要です。たとえば「期限を破ったら10点減点」では、他の項目で20点良くなる候補が選ばれます。高得点でも、必須条件を破った候補は採用できません。 期限を必ず守る要件なら、違反した候補を採用対象から外すなど、得点で埋め合わせられない扱いにします。AIへ計画づくりを頼む時にも、改善したい指標と必須条件を分けて伝えます。

得点と必須条件を分けて確かめる。高得点でも、期限や設備の上限、作業の抜けなどの必須条件に違反する候補は採用できない