LoginSignup
96
94

More than 5 years have passed since last update.

@simanezumi1989(恒彦 嶋津)

遺伝的アルゴリズムでナップザック問題を攻略

Last updated at Posted at 2015-04-10

はじめに

ブロック崩しを攻略する人工知能を開発しています。今回は今までの流れを無視して遺伝的アルゴリズムを実装してみました。強化学習は一個体の学習ですが，遺伝的アルゴリズムは個体群の学習といったイメージです。

※ナップザックかナップサックかの問題はここでは気にしない。
※遺伝的アルゴリズムは複数種類があるようで，何が正しいのかわからなかった。今回のコードはかなり素人レベルのものです。間違っていたり，疑問があればコメントお願いします。

ナップザック問題

ナップザック問題とは，ある容量のナップザック１つと，数種類の品物(それぞれ価値と容量)が与えられ，ナップザックの容量を超えない範囲でいくつかの品物を入れた場合，ナップザックに入れた品物の価値の和が最大となる組み合わせを求める問題。
ナップザック問題.png
画像：wikipedia ナップサック問題

問題によって設定は変わるが，今回はある種類の品物は一つしかないとする。ただし，偶然複数できる場合は除く。

遺伝的アルゴリズム(気が向けば詳しく編集する)

遺伝的アルゴリズムも複数種類あるが，以下の手順でする。
1.初期設定
2.評価
3.選択
4.交叉
5.突然変異
6.　2〜5を繰り返し，指定した世代数を経過する，あるいは評価が指定した目標値を越えれば評価して終了する

コード化

初期設定

ナップザックの容量：200
品物の数：20
品物の容量：それぞれランダム
品物の価値：それぞれランダム

個体数：9
個体の染色体数：品物の数(20)


    //ナップザックに入る容量
    const C_LIMIT = 200;

    //ITEM個の品物
    const ITEM = 20;
    var C = new Array(ITEM);//品物の容量
    var V = new Array(ITEM);//価値
    for(var i=0;i<ITEM;i++){
        C[i] = Math.floor(Math.random()*8)+1;//ランダム
        V[i] = Math.floor(Math.random()*10)+1;//ランダム
    };
    console.log("容量 :",C);
    console.log("価値 :",V);

    //個体の初期設定

    //個体数
    const X = 9;

    //E[i][j]:i番目の個体のj番目の染色体（0,1で品物を選ぶかどうか決める）
    var E = new Array(X);
    for(var i=0;i<X;i++){
        E[i] = new Array(ITEM);
        for(var j=0;j<ITEM;j++){
            E[i][j] = Math.floor(Math.random()*2);
        };
    };

評価

各個体の染色体に従って決めた総容量と総価値を求める。
染色体が1なら入れる。0なら入れない。
ナップザックに入らないなら価値は０とする。


        //個体を評価するために染色体に従って，総容量と総価値を求める
        var C_sum = new Array(X);
        var V_sum = new Array(X);

        //iはi番目の個体
        for(var i=0;i<X;i++){
            C_sum[i] = 0.0;
            V_sum[i] = 0.0; 
            for(var j=0;j<ITEM;j++){    
                //染色体が1ならナップザックに入れる
                if(E[i][j] == 1){
                    C_sum[i] += C[j];
                    V_sum[i] += V[j];
                };
                //ナップザックに入りきらないなら 価値=0
                if(C_sum[i]>C_LIMIT){
                    V_sum[i] = 0;
                };
            };
        };
        console.log("総容量 : ", C_sum);
        console.log("総価値 : ", V_sum);

選択

総価値が高い個体の上位２組を必ず時期世代に残し（エリート選択），他の個体８組は総価値の大きさに応じた確率的選択（ルーレット選択）で残す。

エリート選択

総価値の高い個体を上位２組（top2）を探す。
後で個体を代入するために（eliteに）保存しておく。


        //選択

        //エリート選択
        var top2 = new Array(2);//総価値の上位２組
        var N_top2 = new Array(2);//上位2個体となる個体番号

        //上位2個体を探す(準備)
        //便宜上 top2[0]>top2[1] とする
        if(V_sum[0] > V_sum[1]){
            top2[0] = V_sum[0];
            top2[1] = V_sum[1];
            N_top2[0] = 0;
            N_top2[1] = 1;
        }else{
            top2[0] = V_sum[1];
            top2[1] = V_sum[0];
            N_top2[0] = 1;
            N_top2[1] = 0;
        };
        for(var i=2;i<X;i++){
            //上位2個体を探す
            if(V_sum[i]>top2[0]){
                top2[1] = top2[0];//２番目に大きい値にする
                top2[0] = V_sum[i];//最も大きくする
                N_top2[0] = i;
                N_top2[1] = 0;
            }else if(V_sum[i]>top2[1]){
                top2[1] = V_sum[i];//二番目に大きい値にする
                N_top2[1] = i;
            };
        };
        console.log(top2);

        //エリート配列を確保する
        var elite = new Array(2)
        for(var i=0;i<2;i++){
            elite[i] = new Array(ITEM)
            for(var j=0;j<ITEM;j++){
                elite[i][j] = E[N_top2[i]][j];
            };
        };

ルーレット選択

個体群から，１０個体を確率的に選択する。このとき，１個体が複数選ばれることもあれば，先ほどのエリートが選ばれることもある。選択方法は以下の式で決定する。


個体が選択される確率=\frac{個体の総価値}{各個体の総価値の合計}

例えば　個体番号：総価値の組み合わせが{0:3, 1:4, 2:5}なら


個体0が選択される確率=\frac{3}{3+4+5}

となる。式はこんな感じだがコードでするときは以下の手順で行う。

総価値の和を求める：total
0〜(total-1)までの数字からランダムに選択する：arrow
まず，sum=0として，個体の総価値をたしていく。もしsumがarrowを越えたら，そのときたした個体番号を返し，たし合わせるのを止める。


        //ルーレット選択

        //次の世代の入れ物を作る
        var nextE = new Array(X);
        for(var i=0;i<X;i++){
            nextE[i] = new Array(ITEM)
        };

        //的
        var total = 0
        for(var i=0;i<X;i++){
            total += V_sum[i];
        };
        for(var x=0;x<X;x++){
            var arrow = Math.floor(Math.random()*total);
            var sum = 0;
            for(var i=0;i<X;i++){
                sum += V_sum[i]
                if(sum>arrow){
                    for(var j=0;j<ITEM;j++){
                        nextE[x][j] = E[i][j];
                    };
                    break;
                };
            };
        };

交叉

選択された２個体を親として，交叉率に応じて遺伝子を交叉（交換？）する。

二点交叉

交叉点をランダムで二つ選び、二つの交叉点に挟まれている部分を入れ換える方式
二点交叉.png

        //交叉(前から２組ずつ交叉する。交叉しなければそのままコピーされる)
        for(var x=0;(X%2==1 && x<X-1) || (X%2==0 && x<X);x=x+2){//２組ずつ選ぶので偶奇で場合分けする。
            //crossrate%で交叉
            var crossrate = Math.floor(Math.random()*100);
            if(crossrate<95){
                //２点交叉でcopyEからchildを作る
                //r1〜r2までの染色体を入れ替える
                var r1 = Math.floor(Math.random()*ITEM);//ITEM=15
                var r2 = r1 + Math.floor(Math.random()*(ITEM-r1));//0<=r1<r2<15
                var child = new Array(2);
                child[0] = new Array(ITEM);
                child[1] = new Array(ITEM);

                for(var i=0;i<ITEM;i++){
                    if(r1<=i && i<=r2){
                        child[0][i] = nextE[x+1][i];
                        child[1][i] = nextE[x][i];
                    }else{
                        child[0][i] = nextE[x][i];
                        child[1][i] = nextE[x+1][i];
                    };
                };

                for(var i=0;i<ITEM;i++){
                    //childを世代に入れる
                    nextE[x][i] = child[0][i];
                    nextE[x+1][i] = child[1][i];
                };
            }else{
                console.log("入れ替えなし");
            };
              };

突然変異

各個体が数％の確率で染色体の0と1を入れ替える。


            //突然変異
            for(var i=0;i<X;i++){
                var mutantrate = Math.floor(Math.random()*100);
                if(mutantrate<3){
                    m = Math.floor(Math.random()*ITEM);
                    nextE[i][m] = (nextE[i][m] + 1)%2;
                };
            };

エリートの代入

選択で確保していたエリートを次世代に入れる。

        //仮個体を次の世代個体に代入
        for(var i=0;i<X;i++){
            for(var j=0;j<ITEM;j++){
                if(i==0 || i==1){
                    E[i][j] = elite[i][j];//エリート
                }else{
                    E[i][j] = nextE[i][j];//交叉 or コピーを入れる
                }
            };
        };

実装コードまとめ


<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8">
<title>遺伝的アルゴリズム - ルーレット選択 - ナップザック問題</title>
<meta http-equiv="Content-Style-Type" content="text/css">
<meta http-equiv="Content-Script-Type" content="text/javascript">
<meta name="robots" content="noindex,nofollow">
</head>
<body>

<script>
(function(){

    //ナップザックに入る容量
    const C_LIMIT = 200;

    //ITEM個の品物
    const ITEM = 20;
    var C = new Array(ITEM);//品物の容量
    var V = new Array(ITEM);//価値
    for(var i=0;i<ITEM;i++){
        C[i] = Math.floor(Math.random()*8)+1;//ランダム
        V[i] = Math.floor(Math.random()*10)+1;
    };
    console.log("容量 :",C);
    console.log("価値 :",V);

    //個体の初期設定

    //個体数
    const X = 9;

    //E[i][j]:i番目の個体のj番目の染色体（0,1で品物を選ぶかどうか決める）
    var E = new Array(X);
    for(var i=0;i<X;i++){
        E[i] = new Array(ITEM);
        for(var j=0;j<ITEM;j++){
            E[i][j] = Math.floor(Math.random()*2);
        };
    };

    //操作をGENERATION回繰り返す
    const GENERATION = 20;
    for(var g=0;g<GENERATION;g++){

        //個体を評価するために染色体に従って，総容量と総価値を求める
        var C_sum = new Array(X);
        var V_sum = new Array(X);

        //iはi番目の個体
        for(var i=0;i<X;i++){
            C_sum[i] = 0.0;
            V_sum[i] = 0.0; 
            for(var j=0;j<ITEM;j++){    
                //染色体が1ならナップザックに入れる
                if(E[i][j] == 1){
                    C_sum[i] += C[j];
                    V_sum[i] += V[j];
                };
                //ナップザックに入りきらないなら 価値=0
                if(C_sum[i]>C_LIMIT){
                    V_sum[i] = 0;
                };
            };
        };
        console.log("総容量 : ", C_sum);
        console.log("総価値 : ", V_sum);

        //選択

        //エリート選択
        var top2 = new Array(2);
        var N_top2 = new Array(2);//上位2個体となる個体番号

        //ここでのtop2は総価値の最大値
        //上位2個体を探す(準備)
        //便宜上 top2[0]>top2[1] とする
        if(V_sum[0] > V_sum[1]){
            top2[0] = V_sum[0];
            top2[1] = V_sum[1];
            N_top2[0] = 0;
            N_top2[1] = 1;
        }else{
            top2[0] = V_sum[1];
            top2[1] = V_sum[0];
            N_top2[0] = 1;
            N_top2[1] = 0;
        };
        for(var i=2;i<X;i++){
            //上位2個体を探す
            if(V_sum[i]>top2[0]){
                top2[1] = top2[0];//２番目に大きい値にする
                top2[0] = V_sum[i];//最も大きくする
                N_top2[0] = i;
                N_top2[1] = 0;
            }else if(V_sum[i]>top2[1]){
                top2[1] = V_sum[i];//二番目に大きい値にする
                N_top2[1] = i;
            };
        };
        console.log(top2);

        //エリート配列を確保する
        var elite = new Array(2)
        for(var i=0;i<2;i++){
            elite[i] = new Array(ITEM)
            for(var j=0;j<ITEM;j++){
                elite[i][j] = E[N_top2[i]][j];
            };
        };


        if (g == GENERATION-1){
            break;
        };

        //ルーレット選択

        //次の世代の入れ物を作る
        var nextE = new Array(X);
        for(var i=0;i<X;i++){
            nextE[i] = new Array(ITEM)
        };

        //的
        var total = 0
        for(var i=0;i<X;i++){
            total += V_sum[i];
        };
        for(var x=0;x<X;x++){
            var arrow = Math.floor(Math.random()*total);
            var sum = 0;
            for(var i=0;i<X;i++){
                sum += V_sum[i]
                if(sum>arrow){
                    for(var j=0;j<ITEM;j++){
                        nextE[x][j] = E[i][j];
                    };
                    break;
                };
            };
        };
        //交叉(前から２組ずつ交叉する。交叉しなければそのままコピーされる)
        for(var x=0;(X%2==1 && x<X-1) || (X%2==0 && x<X);x=x+2){
            //crossrate%で交叉
            var crossrate = Math.floor(Math.random()*100);
            if(crossrate<95){
                //２点交叉でcopyEからchildを作る
                //r1〜r2までの染色体を入れ替える
                var r1 = Math.floor(Math.random()*ITEM);//ITEM=15
                var r2 = r1 + Math.floor(Math.random()*(ITEM-r1));//0<=r1<r2<15
                var child = new Array(2);
                child[0] = new Array(ITEM);
                child[1] = new Array(ITEM);

                for(var i=0;i<ITEM;i++){
                    if(r1<=i && i<=r2){
                        child[0][i] = nextE[x+1][i];
                        child[1][i] = nextE[x][i];
                    }else{
                        child[0][i] = nextE[x][i];
                        child[1][i] = nextE[x+1][i];
                    };
                };

                for(var i=0;i<ITEM;i++){
                    //childを世代に入れる
                    nextE[x][i] = child[0][i];
                    nextE[x+1][i] = child[1][i];
                };
            }else{
                console.log("入れ替えなし");
            };

            //突然変異
            //各個体r%の確率で染色体のどこかを反転させる
            for(var i=0;i<X;i++){
                var mutantrate = Math.floor(Math.random()*100);
                if(mutantrate<3){
                    m = Math.floor(Math.random()*ITEM);
                    nextE[i][m] = (nextE[i][m] + 1)%2;
                };
            };
        };
        //仮個体を次の世代個体に代入
        for(var i=0;i<X;i++){
            for(var j=0;j<ITEM;j++){
                if(i==0 || i==1){
                    E[i][j] = elite[i][j];//エリート
                }else{
                    E[i][j] = nextE[i][j];
                }
            };
        };
    };
})();
</script>
</body>
</html>

実装結果

こんな感じになります。
スクリーンショット 2015-04-11 05.50.18.png

感想やら，まとめやら，課題やら，，，

イメージでしかなかった遺伝的アルゴリズムを定式化できてよかった。ただし，見るサイトによって遺伝的アルゴリズムの書き方が違うので，理解している自信はない。そして一番困ったのはナップザック問題の答えがわからないので，実装があっているのかわからない。
また遺伝的アルゴリズムの欠点が何かがわからなかった。
ブロック崩しに適応するには，ニューラルネットワークの重みを染色体で決定すればいけるかもしれない。そのとき，染色体を実数にする方法を勉強する必要がありそう。

参考資料

Library of Algorithms：視覚的にアルゴリズムを理解するサイト
move2.gif

wikipedia ナップサック問題
遺伝的アルゴリズム：静岡理工科大学
遺伝的アルゴリズム:海外？サイト
遺伝的アルゴリズムのslideshare
遺伝的アルゴリズムを体験できるサイト

その他

※AIを構築して対戦するゲームを作った。遺伝的アルゴリズムでAIを作成する実験もしている。
マリオネットAI：AI構築型対戦ゲーム
※遺伝的アルゴリズムなどを使ってマリオネットAIのメタAIを開発中
Projectパペッティア
最新の成果動画
遺伝的アルゴリズムで自作ゲームを攻略してみた。(Toutube)
遺伝的アルゴリズムで自作ゲームを攻略してみた。(ニコニコ)

最後に

なんども書くが，今回のコードはあまり自信がない。疑問や修正点があればコメントください。
また，ブロック崩しを遺伝的アルゴリズムで攻略する方法についてアイデアがある方もアドバイス等のコメントお願いします。

96
94
7

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
96
94