🦀

Rustで遺伝的アルゴリズムをやってみる

に公開
Rust
遺伝的アルゴリズム
tech

概要

Rustの学習を進めていくなかで、何か作ってみようということで
遺伝的アルゴリズムを使ってナップサック問題に挑戦しました。

Rustにて完成させることが目的なので、GAとしては少し端折っている部分はあります。

https://ja.wikipedia.org/wiki/ナップサック問題

準備

今回は、容量200のナップサックに商品を詰めることにします。
商品は、10個用意しそれぞれ価値を設定します。
容量を超えず、価値が最大になる商品の組み合わせを求めます。

商品

struct Goods {
    id: i32,
    capacity: i32,
    value: i32,
}

初期値は、容量、価値ともに乱数で1～100の値とします。

fn init_goods(goods_vec: &mut Vec<Goods>, size: i32) {
    let mut rng = rand::rng();

    for i in 0..size {
        goods_vec.push(
            Goods {
                id: i + 1,
                capacity: rng.random_range(1..100),
                value: rng.random_range(1..100)
            }
        );
    }
}

個体

struct Individual {
    dna: i128,
    goods: Goods,
}

個体は、遺伝子と評価に使うための商品合計値を格納する変数を持たせます。
遺伝子は、右から10ビット使用し、ビットが1の位置の商品をナップサックに入れることを表します。

0000000000　商品は何も入れない。
0000000101　商品１と３を入れる。

評価

各個体の評価は、遺伝子のビットを右から見ていき、1が立っている位置の商品の容量と価値を合計していきます。

世代交代

エリートの選択

今回は、個体数100として上位5体をエリートとして、次の世代にそのまま残します。

突然変異

エリート以外の全個体に対して、それぞれ5%の確率で、突然変異を起こします。
10ビットのうちどこか1箇所のビットを反転します。

交叉

今回は、トップの個体と最下位の個体の遺伝子を交叉します。
トップの個体の上位5ビットと最下位の個体の下位5ビットを取り出し、新しく10ビットの遺伝子として新たな個体を作成します。

増えた分、最下位の個体は削除します。

感想

100000世代ほど繰り返すと解が収束しました。
なんとか解が求められたように思えます。

今までJavaでいろいろと書いていましたが、なんとかRustで実行できるようになりました。

今後もいろいろと書いてみて学習をしていこうと思います。

Discussion