遺伝的アルゴリズム (Genetic Algorithm, GA) を勉強したので Rust で実装しました.

セットアップ

遺伝的アルゴリズム (以下 GA と呼ぶ) とは最適化アルゴリズムの一種で, 生物の進化プロセスを人工的に模倣するものです.

問題設定

$G$ を有限集合 (例えば $G = \{ 0, 1 \}$), $L$ を正の整数とし, 空間 $G^L$ で定義された関数 $f: G^L \to \mathbb{R}$ が与えられたとします. 問題はこの $f$ の最大値を与える元 $x_* \in G^L$ を数値的に求めることです. なお空間 $G^L$ の元を GA では遺伝子 (gene) または個体 (individual), 長さ $L$ を遺伝子長と呼びます.

個体

個々の個体 Individual は遺伝子型 G の配列 Vec<G> という情報を持っています. 評価関数 f が与えられたとき, その適応度を計算するメソッドが付随しています.

/// 個体を表す型. 型引数 `G` は遺伝子型 (例えば `u8`).
#[derive(Debug, Clone)]
pub struct Individual<G> {
    vec: Vec<G>,
}
impl<G> Individual<G> {
    // 適応度を計算する.
    pub fn fitness<F, T>(&self, f: F) -> T where
        F: Fn(&[G]) -> T
    {
        f(&self.vec)
    }
}

さらに FromIterator, Display, Deref, DerefMut を実装しておくと便利です.

impl<G> std::iter::FromIterator<G> for Individual<G> {
    fn from_iter<T>(iter: T) -> Self where T: IntoIterator<Item = G> {
        let vec = iter.into_iter().collect();
        Individual { vec }
    }
}
impl<G> std::fmt::Display for Individual<G> where G: Copy + ToString {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", 
            self.vec.iter().fold(String::new(), |acc, g| acc + &g.to_string())
        )
    }
}
impl<G> std::ops::Deref for Individual<G> {
    type Target = [G];
    fn deref(&self) -> &[G] { &self.vec }
}
impl<G> std::ops::DerefMut for Individual<G> {
    fn deref_mut(&mut self) -> &mut [G] { &mut self.vec }
}

進化

親世代から次世代を生成する過程は, 選択, 交叉, 突然変異という三段階のプロセスによって実現されます. これを十分最適化が進むまで繰り返します.

選択

最初に, 親世代から各々の適応度に基づいて次世代に子孫を残すことのできる個体を選択します. ルーレット選択, ランキング選択, トーナメント選択などいくつかの方式がありますが, ここではトーナメント選択を実装しました. これは親世代から tournament_size 個の個体をランダムに選び, その中で最も適応度が高かった個体を選ぶ, という処理を n 回繰り返すものです. 従って適応度が高めの個体は複数回選ばれる可能性がある一方で, 適応度が低めの個体は子を残すことができません.

use rand::seq::SliceRandom;

/// トーナメント選択
pub fn tournament_selection<'a, G, F, T, R>(
    population: &'a [Individual<G>], f: F, rng: &mut R, tournament_size: usize
) -> (Vec<&'a Individual<G>>, Vec<&'a Individual<G>>) 
where
    R: Rng, F: Fn(&[G]) -> T, T: Ord
{
    let n = population.len();
    let mut a = (0..n).map(|_| {
        population
            .choose_multiple(rng, tournament_size)
            .max_by_key(|ind| ind.fitness(&f))
            .unwrap()
    }).collect::<Vec<_>>();
    let b = a.split_off(n/2);
    (a, b)
}

なお次の交叉で用いるために, 選ばれた個体群を半分に分けています.

交叉

ふたりの親の遺伝子を適当なところで分割し, くっつけるのが交叉 (crossover) です. ただしある確率で親の遺伝子をそのまま受け継ぎます. 交叉の際に切れ込みを入れる箇所の個数に応じて一点交叉, 二点交叉, ... と呼ばれますが, 通常は二点交叉が用いられるようです.

use rand::Rng;

pub fn next_generation_with_crossover<G, R>(
    a: Vec<&Individual<G>>, b: Vec<&Individual<G>>, prob: f64, rng: &mut R
) -> Vec<Individual<G>> where 
    R: Rng, G: Clone
{
    let l = a[0].vec.len();

    let mut next: Vec<Individual<G>> = Vec::new();
    for (a, b) in a.into_iter().zip(b.into_iter()) {
        if rng.gen::<f64>() <= prob {
            let i = rng.gen_range(1, l-1);
            let j = rng.gen_range(i+1, l);
            next.push(a[..i].iter().chain(b[i..j].iter()).chain(a[j..].iter()).map(|g| g.clone()).collect());
            next.push(b[..i].iter().chain(a[i..j].iter()).chain(b[j..].iter()).map(|g| g.clone()).collect());
        } else {
            next.push(a.clone());
            next.push(b.clone());
        }
    }
    next
}

突然変異

ある確率で子世代の遺伝子の一部に突然変異を起こさせます. なお関数の最後の引数は実際にどのような変異を起こすかを表すクロージャを渡します.

pub fn mutation<G, R, M>(pop: &mut [Individual<G>], prob: f64, rng: &mut R, mutate: M) 
where
    R: Rng, M: Fn(&mut G),
{
    for ind in pop.iter_mut() {
        for g in &mut ind.iter_mut() {
            if rng.gen::<f64>() < prob {
                mutate(g);
            }
        }
    }
}

例

参考文献2に倣って, $G = \{ 0, 1 \}$, $L = 96$ とし, 遺伝子がすべて1の状態に向かって進化させてみます (若干パラメータを変更しています).

コード

use genetic::{Individual, tournament_selection, next_generation_with_crossover, mutation};
use rand::{Rng, SeedableRng};

fn main() {
    //****** 問題設定 ******//
    // 遺伝子長
    let l: usize = 96;
    // 個体数
    let n: usize = 300; 
    // 適合度関数
    let f = |gene: &[u8]| -> u8 { gene.iter().sum::<u8>() };

    //****** GA に関するパラメータ ******//
    // トーナメントサイズ
    let tournament_size: usize = 3;
    // 交叉確率
    let cross_prob: f64 = 0.5;
    // 突然変異確率
    let mutation_prob: f64 = 0.01;
    //****** ******//

    // PRNG の初期化
    let mut rng = rand_xoshiro::Xoshiro256StarStar::seed_from_u64(123);

    // 初期個体群を生成
    let mut generation = 0;
    let mut population = (0..n).map(|_| {
        (0..l).map(|_| rng.gen_range(0u8, 2)).collect::<Individual<u8>>()
    }).collect::<Vec<_>>();

    while {
        // 現世代の最適個体の情報を表示
        let bestfit = population.iter().max_by_key(|ind| ind.fitness(f)).unwrap();
        println!("Gen{:03}: Fitness {:3}: DNA {}", generation, bestfit.fitness(f), bestfit);

        // 目標の最適個体が得られたら計算終了 (得られなくても256世代を経た時点で終了)
        (bestfit.fitness(f) < 96) && (generation < 256)
    } {
        // 世代番号を更新
        generation += 1;

        // トーナメント選択を行いふたつのグループに分ける
        let (a, b) = tournament_selection(&population, f, &mut rng, tournament_size);
                
        // 二点交叉により次世代を生成
        let mut next = next_generation_with_crossover(a, b, cross_prob, &mut rng);

        // 突然変異: 1 との Xor を取る
        mutation(&mut next, mutation_prob, &mut rng, |g| {*g ^= 1;});

        population = next;
    }
}

結果

$ cargo run --release
Gen000: Fitness 60: DNA 111000011111110100100111110011010011001111101100100001111010100101101011011110101011111101111101
Gen001: Fitness 62: DNA 000111111110101111011010100110100011111101011101011111011101011110010101110111000110101011011110
Gen002: Fitness 64: DNA 000111011110001011111011101101111110111010101110001110011110100011111111111101011100111100101011
Gen003: Fitness 67: DNA 011011111000111001001110111110111110110111110111111010011111011011101011011111011100111101100110
Gen004: Fitness 67: DNA 101101001111101111001111110111110111000011111110001110011110100011111111111101111000111110111001
Gen005: Fitness 71: DNA 111000011111111111111101111110100011111101011111011111011101011110101011011110101001111101111101
Gen006: Fitness 73: DNA 111111101001111101111110111110111110110111110111111011011111011011101011011111010110111101100110
Gen007: Fitness 75: DNA 111001011011110101011011110111111110101111110111111010011111101101111111111101011111111101111101
Gen008: Fitness 75: DNA 111000011011111101011011110111111110111111110111001111101110111111111001111101111101111101111101
Gen009: Fitness 75: DNA 111111101001111101111110111110110110110111110111111011011111011011101011011111011110111101111110
Gen010: Fitness 77: DNA 111111101001111101111111110111110110110111110111111111010111011110111011110111111010101111111110
Gen011: Fitness 79: DNA 111111101001111101011110111110110110110111110111111111101110111011110111111111111011111101111111
Gen012: Fitness 80: DNA 010110001111101111011011110111111110111111110111111111101110111111111111111101011111011111111111
Gen013: Fitness 82: DNA 111110111011111111111101110111111110101111111111111110011110111111111111111101011111111101101101
Gen014: Fitness 83: DNA 111110111011111111111101111111100011111111111110011111011111111011111111111101111111011111111101
Gen015: Fitness 83: DNA 111001011011111111011011110111111110111111110111111111101110111111111111111111111011111111111101
Gen016: Fitness 86: DNA 111111111111111101011011110111111110111111110111111111101110111111111111111111011111011111111111
Gen017: Fitness 86: DNA 111111111111111101011011110111111110111111110111111111101110111111111111111111011111011111111111
Gen018: Fitness 87: DNA 111111111111111111011011110111111110111111110111111111101110111111111111111111011111011111111111
Gen019: Fitness 90: DNA 111111111101111111111111110111111110101111111111111111111110111111111111111110111111111111111111
Gen020: Fitness 90: DNA 111111111101111111111111110111111110101111111111111111111110111111110111111111111111111111111111
Gen021: Fitness 89: DNA 111111111101111111111111110111111110101111111111111111111100111111111111111110111111111111111111
Gen022: Fitness 90: DNA 111111111101111111111111110111111110101111111111111111011110111111111111111111111111111111111111
Gen023: Fitness 90: DNA 111111111101111111111111111110111110111111111111111111111110111111110111111111011111111111111111
Gen024: Fitness 93: DNA 111111111101111111111111111111101111111111011111111111111111111111111111111111111111111111111111
Gen025: Fitness 91: DNA 111111111101111111111111111110111110111111111011111111111110111111111111111111111111111111111111
Gen026: Fitness 92: DNA 111111111101111111111111111111111110101111111111111111111110111111111111111111111111111111111111
Gen027: Fitness 92: DNA 111111111101111111111111111111111110111111110111111111111110111111111111111111111111111111111111
Gen028: Fitness 93: DNA 111111111111111111111111110111111110101111111111111111111111111111111111111111111111111111111111
Gen029: Fitness 94: DNA 111111111111111111111111111110111110111111111111111111111111111111111111111111111111111111111111
Gen030: Fitness 94: DNA 111111111111111111111111111110111110111111111111111111111111111111111111111111111111111111111111
Gen031: Fitness 94: DNA 111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111
Gen032: Fitness 94: DNA 111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111
Gen033: Fitness 94: DNA 111111111111111111111111111110111110111111111111111111111111111111111111111111111111111111111111
Gen034: Fitness 94: DNA 111111111111111111111111111110111110111111111111111111111111111111111111111111111111111111111111
Gen035: Fitness 94: DNA 111111111111111111111111111110111111111111111111111111111111110111111111111111111111111111111111
Gen036: Fitness 94: DNA 111111111111111111111111111110111110111111111111111111111111111111111111111111111111111111111111
Gen037: Fitness 95: DNA 111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111
Gen038: Fitness 95: DNA 111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111
Gen039: Fitness 95: DNA 111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111
Gen040: Fitness 95: DNA 111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111
Gen041: Fitness 95: DNA 111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111
Gen042: Fitness 95: DNA 111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111
Gen043: Fitness 95: DNA 111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111
Gen044: Fitness 96: DNA 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

見ての通り, 44世代を経て遺伝子がすべて1の個体が誕生しました. めでたしめでたし.

参考文献