エンジニアが正しく「I love you」と伝えるための遺伝的アルゴリズム(殺伐)

「エンジニアが正しく「好き」と伝えるための実装法」という記事が話題だったので、乗っかってみました。

内気なエンジニアのために「I love you」と言ってくれるプログラムを遺伝的アルゴリズムで作成します。

【参考】
Machine Learning: Introduction to Genetic Algorithms

遺伝的アルゴリズムとは？

この国はすっかりダメになってしまいました。
だから、偉い人達は相談して、この法律をつくりました。
「バトル・ロワイアル」
そこで今日はみなさんに、ちょっと殺し合いをしてもらいます。
最後の一人になるまでです。

↑これに”交配”と”突然変異”の仕組みが含まれれば遺伝的アルゴリズムです。
ニコニコ大百科にさらにわかりやすい例が掲載されています。

少年少女を100人ずつ用意します。
一生懸命歌っていただきます。
歌の上手い上位5人ずつを残して残りは抹殺します。
互いに交配して彼らの子供を男女100人ずつ用意します。
2〜4を何回も繰り返します。
どっかで停止し、その時一番うまかった一組を残して抹殺します。
残った2人が鏡音リン・レンです。
なんだってー！？
– 本掲示板>>3より

とりあえず、なんとなく仕組みが分かったところでやってみましょう。

「I love you」に辿りつくまでの流れ

まず、２０人の個体を用意します。

個体それぞれに文字を書かせます。
文字の内容が「I love you」に近い順に並べます。
上位２名が子作りして、子供を二人生みます。
下位２名を処分して、生まれた子供と入れ替えます。
ランダムに選んだ個体の文字を一部変化させます(突然変異)

上記１〜５を「I love you」がちゃんと書ける個体が生まれるまで続けます。

サンプル

コード

Machine Learning: Introduction to Genetic Algorithmsに掲載されているコードにコメント付け加えただけなので、詳しくは先の記事を読んでください。

var Gene = function(code) { //個体
    if (code) this.code = code;
    this.cost = 9999;
};
Gene.prototype.code = ''; // 遺伝情報

Gene.prototype.calcCost = function(compareTo) { //コスト計算
    var total = 0;
    for (i = 0; i < this.code.length; i++) {
        total += (this.code.charCodeAt(i) - compareTo.charCodeAt(i)) * (this.code.charCodeAt(i) - compareTo.charCodeAt(i)); //一文字ずつUnicodeコード値の差を計算
    }
    this.cost = total;
};

Gene.prototype.random = function(length) { //ランダムな遺伝子を作成する
    while (length--) {
        this.code += String.fromCharCode(Math.floor(Math.random() * 255));
        //fromCharCodeメソッドは0x41, 0x42, 0x43のような文字コード列を "ABC" のような文字列に変換して返します
    }
};

Gene.prototype.mate = function(gene) { //交叉
    var pivot = Math.round(this.code.length / 2) - 1; //交叉点(中心)取得
    
    //子作り（一点交叉）
    var child1 = this.code.substr(0, pivot) + gene.code.substr(pivot); 
    var child2 = gene.code.substr(0, pivot) + this.code.substr(pivot);

    return [new Gene(child1), new Gene(child2)]; //生誕
};

Gene.prototype.mutate = function(chance) { //突然変異
    if (Math.random() > chance) return; //変異できずにバイバイ

    var index = Math.floor(Math.random() * this.code.length); //変異するインデックスを決定(ランダム)
    var upOrDown = Math.random() <= 0.5 ? -1 : 1; //1 or -1  //増やすか減らすか決定
    var newChar = String.fromCharCode(this.code.charCodeAt(index) + upOrDown); //キャラクターコードを増減
    var newString = ''; //新しい遺伝情報
    for (i = 0; i < this.code.length; i++) {
        if (i == index) newString += newChar; //変異させたキャラクターコードを挿入
        else newString += this.code[i];
    }

    this.code = newString; //遺伝情報を上書き

};






var Population = function(goal, size) { //群れ　
    this.members = []; //個体を入れとく箱
    this.goal = goal; //目指すゴール
    this.generationNumber = 0; //世代数
    while (size--) {
        var gene = new Gene(); //sizeの数だけ個体を用意する
        gene.random(this.goal.length); //ゴールの長さを元に染色体をランダムに作成
        this.members.push(gene); //群れに追加
    }
};

Population.prototype.sort = function() { //コストを基準にソート
    this.members.sort(function(a, b) {
        return a.cost - b.cost;
    });
}

Population.prototype.generation = function() { //世代処理
    for (var i = 0; i < this.members.length; i++) {
        this.members[i].calcCost(this.goal); //コスト計算

    }

    this.sort(); //群れをソート
    this.display(); //画面出力
    
    var children = this.members[0].mate(this.members[1]); //上位２名で交叉
    
    //取捨選択
    this.members.splice(this.members.length - 2, 2, children[0], children[1]); //群れのなかから順位の低い２名が死亡。子供２人と入れ替え。

    
    for (var i = 0; i < this.members.length; i++) {
        this.members[i].mutate(0.5); //突然変異
        this.members[i].calcCost(this.goal); //コスト計算
        if (this.members[i].code == this.goal) { //ゴールに辿りついたら終了
            this.sort();
            this.display();
            return true;
        }
    }
    
    this.generationNumber++; //世代カウント

    var scope = this;
    
    setTimeout(function() {
        scope.generation(); //次の世代へ
    }, 20);
    
};

Population.prototype.display = function() { //画面出力
    document.body.innerHTML = '';
    document.body.innerHTML += ("<h2>Generation: " + this.generationNumber + "</h2>");
    document.body.innerHTML += ("<ul>");
    for (var i = 0; i < this.members.length; i++) {
        document.body.innerHTML += ("<li>" + this.members[i].code + " (" + this.members[i].cost + ")");
    }
    document.body.innerHTML += ("</ul>");
};

var population = new Population("I love you", 20);
population.generation();

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

var Gene = function(code) { //個体

if (code) this.code = code;

this.cost = 9999;

};

Gene.prototype.code = ''; // 遺伝情報

Gene.prototype.calcCost = function(compareTo) { //コスト計算

var total = 0;

for (i = 0; i < this.code.length; i++) {

total += (this.code.charCodeAt(i) - compareTo.charCodeAt(i)) * (this.code.charCodeAt(i) - compareTo.charCodeAt(i)); //一文字ずつUnicodeコード値の差を計算

}

this.cost = total;

};

Gene.prototype.random = function(length) { //ランダムな遺伝子を作成する

while (length--) {

this.code += String.fromCharCode(Math.floor(Math.random() * 255));

//fromCharCodeメソッドは0x41, 0x42, 0x43のような文字コード列を "ABC" のような文字列に変換して返します

}

};

Gene.prototype.mate = function(gene) { //交叉

var pivot = Math.round(this.code.length / 2) - 1; //交叉点(中心)取得

//子作り（一点交叉）

var child1 = this.code.substr(0, pivot) + gene.code.substr(pivot);

var child2 = gene.code.substr(0, pivot) + this.code.substr(pivot);

return [new Gene(child1), new Gene(child2)]; //生誕

};

Gene.prototype.mutate = function(chance) { //突然変異

if (Math.random() > chance) return; //変異できずにバイバイ

var index = Math.floor(Math.random() * this.code.length); //変異するインデックスを決定(ランダム)

var upOrDown = Math.random() <= 0.5 ? -1 : 1; //1 or -1 //増やすか減らすか決定

var newChar = String.fromCharCode(this.code.charCodeAt(index) + upOrDown); //キャラクターコードを増減

var newString = ''; //新しい遺伝情報

for (i = 0; i < this.code.length; i++) {

if (i == index) newString += newChar; //変異させたキャラクターコードを挿入

else newString += this.code[i];

}

this.code = newString; //遺伝情報を上書き

};

var Population = function(goal, size) { //群れ　

this.members = []; //個体を入れとく箱

this.goal = goal; //目指すゴール

this.generationNumber = 0; //世代数

while (size--) {

var gene = new Gene(); //sizeの数だけ個体を用意する

gene.random(this.goal.length); //ゴールの長さを元に染色体をランダムに作成

this.members.push(gene); //群れに追加

}

};

Population.prototype.sort = function() { //コストを基準にソート

this.members.sort(function(a, b) {

return a.cost - b.cost;

});

}

Population.prototype.generation = function() { //世代処理

for (var i = 0; i < this.members.length; i++) {

this.members[i].calcCost(this.goal); //コスト計算

}

this.sort(); //群れをソート

this.display(); //画面出力

var children = this.members[0].mate(this.members[1]); //上位２名で交叉

//取捨選択

this.members.splice(this.members.length - 2, 2, children[0], children[1]); //群れのなかから順位の低い２名が死亡。子供２人と入れ替え。

for (var i = 0; i < this.members.length; i++) {

this.members[i].mutate(0.5); //突然変異

this.members[i].calcCost(this.goal); //コスト計算

if (this.members[i].code == this.goal) { //ゴールに辿りついたら終了

this.sort();

this.display();

return true;

}

this.generationNumber++; //世代カウント

var scope = this;

setTimeout(function() {

scope.generation(); //次の世代へ

}, 20);

};

Population.prototype.display = function() { //画面出力

document.body.innerHTML = '';

document.body.innerHTML += ("<h2>Generation: " + this.generationNumber + "</h2>");

document.body.innerHTML += ("<ul>");

for (var i = 0; i < this.members.length; i++) {

document.body.innerHTML += ("<li>" + this.members[i].code + " (" + this.members[i].cost + ")");

}

document.body.innerHTML += ("</ul>");

};

var population = new Population("I love you", 20);

population.generation();

多大な犠牲を払って作成した「I love you」なら、きっと思いも伝わるはず！

遺伝的アルゴリズムとは？

「I love you」に辿りつくまでの流れ

サンプル

コード

投稿者: shimizu