行動を遺伝子とする遺伝的アルゴリズムのブロック崩し攻略

#はじめに
ブロック崩しを攻略する人工知能を開発しています。前回宣言した通り，各時間の行動を遺伝子とする遺伝的アルゴリズムを実装しました。


#遺伝的アルゴリズム
大まかな流れは[前回の記事](http://qiita.com/simanezumi1989/items/8e81b0125e7b98708b46)と同じです。大きく違うところは遺伝子です。前回は，行動を決定するニューラルネットワークの重みを遺伝子としていましたが，今回は直接遺伝子が行動を決定します。

##初期設定
個体を100個体用意する。
このとき，個体の行動は（-1,0,1）=（左,停止,右）の３つであり，遺伝子数は10000とする。

例えば遺伝子が[0,0,1,0,-1,....]であれば，バーは，停止，停止，右，停止，左，...という動きをする。

```js

var N = 100;//個体数
var individual = new Array(N);
var chrom = 10000;//遺伝子数
//初期の遺伝子決定(ランダム)
for(var n=0;n<N;n++){
	individual[n] = new Array(chrom);
	for(var c=0;c<chrom;c++){
		individual[n][c] = Math.floor(Math.random()*3) - 1;//-1か0か1
	};
};
```

##世代交代モデル
MGGとする。
個体群からランダムに１組の親を選び，n個体の子供を作る。そして，親と子供を含めたn+2個体のうち，もっとも評価の高い個体と，ルーレット選択によって選ばれた１個体を親と入れ替える。

##交叉
２点交叉を行う。２点交叉は下の図をみればわかるように，８個体の子供を作る。

[![２点交叉.png](https://qiita-image-store.s3.amazonaws.com/0/67439/cae47ec4-ca8b-2fa7-76da-e1bf2b64a351.png)](http://www.sist.ac.jp/~kanakubo/research/evolutionary_computing/ga_operators.html)

```js

//親選択
var r1 = Math.floor(Math.random()*N);
var r2 = Math.floor(Math.random()*N);

//二点交叉
//交叉する点を選択
var rand1 = Math.floor(Math.random()*chrom);
var rand2 = rand1 + Math.floor(Math.random()*(chrom-rand1));//0<=r1<r2<遺伝子数
//親+子=2+8　の子供個体をつくる
const CHILDLEN = 10;
var child = new Array(CHILDLEN);
for(var n=0;n<CHILDLEN;n++){
	child[n] = new Array(chrom);
};
for(var c=0;c<chrom;c++){
	var parent=[individual[r1][c],individual[r2][c]];
	child[0][c] = parent[0];//親を代入
	child[1][c] = parent[1];//親を代入

    //上の図のように親個体を代入
	if(c<rand1){
		child[2][c] = parent[0];
		child[3][c] = parent[0];
		child[4][c] = parent[0];
		child[5][c] = parent[0];
		child[6][c] = parent[1];
		child[7][c] = parent[1];
		child[8][c] = parent[1];
		child[9][c] = parent[1];
	}else if(rand1<=c && c<rand2){
		child[2][c] = parent[0];
		child[3][c] = parent[0];
		child[4][c] = parent[1];
		child[5][c] = parent[1];
		child[6][c] = parent[0];
		child[7][c] = parent[0];
		child[8][c] = parent[1];
		child[9][c] = parent[1];				
	}else{
		child[2][c] = parent[0];
		child[3][c] = parent[1];
		child[4][c] = parent[0];
		child[5][c] = parent[1];
		child[6][c] = parent[0];
		child[7][c] = parent[1];
		child[8][c] = parent[0];
		child[9][c] = parent[1];
	};
};
```
##突然変異

```js
//各個体1%で突然変異
const mutantrate = 0.01;
for(var n=0;n<N;n++){
	if(Math.random()<mutantrate){
          //numberOfFrames=個体がゲームした時間 までの遺伝子を突然変異させる
		var m = Math.floor(Math.random()*numberOfFrames);
		individual[n][m] = Math.floor(Math.random()*3) - 1;
	};
};
```
#結果
動画：[ブロック崩し 遺伝的アルゴリズム](https://www.youtube.com/watch?v=J1L1ZuN8dhw&feature=youtu.be)
うまく動いてくれました。前回よりも実行結果が速くいろいろ試すこともできました。

#課題
動画のような個体は，多くの犠牲のもと出来上がった個体なので，もっと世代数を減らしたいです。

#次回「課題はやらずに前進だ！」
今回遺伝的アルゴリズムがうまく機能したので，次回はこの行動をニューラルネットワークに記憶させます。


#参考資料
２点交叉の図
[様々な選択・交叉・突然変異](http://www.sist.ac.jp/~kanakubo/research/evolutionary_computing/ga_operators.html)
過去の記事
[実数値遺伝的アルゴリズムによるニューラルネットワークの重み最適化とブロック崩しへの応用](http://qiita.com/simanezumi1989/items/8e81b0125e7b98708b46)
[遺伝的アルゴリズムでナップザック問題を攻略](http://qiita.com/simanezumi1989/items/10cfe1e8a23cd9d4c7b1)

#実装コード

```html

<!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">
<style type="text/css">

body{ -moz-user-select: none; -webkit-user-select: none; -ms-user-select: none; font-size: 20px;}
canvas{ border: none; position: absolute; left: 10px; top: 10px;}
#graph2{ cursor: pointer;}
#data{ position: relative; top: 410px;}
#myPercent{ width: 40px; font-size: inherit;}
#quickCalc{ font-size: inherit;}

</style>
</head>
<body>

<canvas id='graph'></canvas>
<canvas id='graph2'></canvas>
<p id='data'>
	<input type='checkbox' id='resetEverytime' checked>落ちたらリセット<br>
	<input type='text' value='100' id='myPercent'>　
	<input type='button' id='quickCalc' value='描画せずに計算'>　
	<span id='myResult'></span><br>
	<input type="text" id="times" value="100">世代
	<input type="button" id="try" value="計算">
</p>

<script>
(function(){
	//バーを動かす関数
	function moveBar(In){
		var action = In[numberOfFrames];
		if(action==0) reward += 10;
		var tempX = bar.x+action*30; //左右に30ピクセルまたは動かない
		if (tempX<p.r) tempX = p.r; //左の壁に当たったら、それ以上左へは行かない
		else if (tempX>w-p.r) tempX = w-p.r; //右の壁に当たったらそれ以上右へは行かない
		bar.x = tempX;
	};

	function d(ID){ return document.getElementById(ID);}
	var timer;
	var paused = false, gameOver = false, gameEnded = true;
	var numberOfBalls = 0; //使用したボールの数
	var numberOfFrames = 0; //かかったフレーム数（÷33＝時間（秒））
	var graph = d('graph'), graph2 = d('graph2');
	var g = graph.getContext('2d'), g2 = graph2.getContext('2d');
	var w = 600, h = 400;
	graph.width = graph2.width = w; graph.height = graph2.height = h;
	g.fillStyle = '#000';
	g.fillRect(0,0,w,h);
	g.save();
	g.font = '30px Arial';
	g.fillStyle = 'white';
	g.fillText('Click to Start',210,220);
	g.restore();

	// pはボール。順にx座標、y座標、半径、速度x成分、速度y成分,色
	var p = {x: 300, y: 20, r: 10, vx: 0, vy: 0, color: '#fff'};

	//barは棒。x座標、yは厚み、Lは長さの半分、edgeは角度が付き始める点の端からの距離
	var bar = {x: 300, y: 10, L: 50, edge: 45, color: '#ff0'};

	//bはブロック。b.xとb.yがともに配列で、xy座標を示す。wはwidthで幅、hはheightで高さ。全て同じ大きさの長方形
	var b = {x: [], y: [], w: 20, h: 10, color: '#88f'};

	var score = 0;

	d('graph2').addEventListener('click',function(){
		if (gameEnded){
			gameEnded = false;
			reset();
			drawBG();
			mainLoop();
		}
		else if (paused){
			paused = false;
			drawBG();
			mainLoop();
		}
		else{
			paused = true;
			clearTimeout(timer);
			g2.font = '30px Arial';
			g2.fillStyle = 'white';
			g2.fillText('paused',250,220);
		}
	},false);

	function reset(){
		bar.x = 300;
		p.x = bar.x; p.y = bar.y+p.r;
		var angle = Math.PI*(10)/180;//Math.PI*(Math.random()*60-30)/180; //-30～30
		p.vx = Math.sin(angle)*12; p.vy = Math.cos(angle)*12; //cosとsinの反転に注意
		b.x = []; b.y = [];
		for (var i=0; i<3; i++) for (var j=0; j<11; j++){
			b.x.push(w/2-10*b.w+j*b.w*2);
			b.y.push(340-i*b.h*2);
		}
		score = numberOfBalls = numberOfFrames = 0;
	}

	function mainLoop(){
		g.fillStyle = '#000';
		g.fillRect(0,0,w,h);
		g.setTransform(1,0,0,-1,0,h);

		//ボールの描画
		g.beginPath();
		g.arc(p.x,p.y,p.r,0,2*Math.PI);
		g.fillStyle = p.color;
		g.fill();
		//ボールの描画

		//バーの描画
		g.fillStyle = bar.color;
		g.fillRect(bar.x-bar.L+p.r+3,0,(bar.L-p.r-3)*2,bar.y); //±3は"遊び"

		//ボールを現在の速度をもとに移動させる
		p.x += p.vx;
		p.y += p.vy;

		//バーを動かす
		moveBar(individual[best[1]]);


		//ここから衝突判定。まずはブロック
		if (p.y>=280){
			for (var i=0,I=b.x.length,hit=false; i<I; i++){
				if ((p.y-b.y[i])*p.vy<0 && Math.abs(p.x-b.x[i])<=b.w && Math.abs(p.y-b.y[i])<=b.h+p.r){
					p.vy *= -1;
					hit = true;
					break;
				}
				else if ((p.x-b.x[i])*p.vx<0 &&Math.abs(p.y-b.y[i])<=b.h && Math.abs(p.x-b.x[i])<=b.w+p.r){
					p.vx *= -1;
					hit = true;
					break;
				}
			}
			if (hit){
				score += 10;
				b.x.splice(i,1); b.y.splice(i,1);
				drawBG();
				if (b.x.length<=0){
					gameEnded = true;
					d('graph2').style.cursor = 'pointer';
					g2.font = '40px Arial';
					g2.fillStyle = 'white';
					g2.fillText('SUCCESS !',200,200);
					var timeLapse = Math.floor(100*numberOfFrames/33)/100;
					g2.fillText(timeLapse+' sec',220,250);
					return;
				}
			}
		}
		//↓衝突判定。ここから壁
		if (p.x>w-p.r){ p.x = w-p.r; p.vx *= -1;} //right
		if (p.x<p.r){	p.x = p.r; p.vx *= -1;} //left
		if (p.y>h-p.r){	p.y = h-p.r; p.vy *= -1;} //up
		if (p.y<p.r+bar.y){
			var p_bar = Math.abs(p.x-bar.x);
			if (!gameOver && p_bar<=bar.L){
				var X = (p.x>bar.x) ? 1 : -1;　//衝突点のバーの法線ベクトル(X,1);
				if (p_bar<=bar.L-bar.edge) X = 0; //バーの中央
				else if (p_bar<=bar.L-bar.edge/3) X *= (p_bar-bar.L+bar.edge)/100; //0～0.3（バーの端は約73°）
				else X *= 0.3;
				var L = Math.sqrt(X*X+1); //法線ベクトルの長さ
				var vec = {x: X/L, y: 1/L}; //法線ベクトルの正規化
				var dot = vec.x*p.vx+vec.y*p.vy;
				p.y = p.r+bar.y;
				p.vx -= 2*dot*vec.x;
				p.vy -= 2*dot*vec.y;
				if (Math.abs(p.vx)/p.vy>1.5){ //角度が付き過ぎないよう調整
					var v2 = p.vx*p.vx+p.vy*p.vy;
					p.vy = Math.sqrt(v2/3.25);
					p.vx = (p.vx<0) ? -p.vy*1.5 : p.vy*1.5;
				}
			}
			else if (!gameOver && p.y<p.r) gameOver = true;
			else if (gameOver && p.y<-p.r){
				gameOver = false;
				reset();
				numberOfFrames = -1;;
				drawBG();
			}
		}
		numberOfFrames++;
		timer = setTimeout(mainLoop,30); //30ミリ秒後にmainloop実行 (-> 1秒に約30回繰り返す)
	}

	//↓ブロックの描画。動きがないのに毎回描くのは無駄なので、別にして処理を節約。
	function drawBG(){
		g2.clearRect(0,0,w,h);
		g2.font = '20px Arial';
		g2.fillStyle = '#fff';
		g2.fillText('Balls:　'+numberOfBalls,15,25);
		g2.fillText('Score:　'+score,480,25);
		g2.save();
		g2.setTransform(1,0,0,-1,0,h);
		g2.fillStyle = '#ccf';
		for (var i=0,I=b.x.length; i<I; i++) g2.fillRect(b.x[i]-b.w,b.y[i]-b.h,2*b.w,2*b.h);
		g2.fillStyle = b.color;
		for (var i=0; i<I; i++) g2.fillRect(b.x[i]-b.w+1,b.y[i]-b.h+1,2*b.w-2,2*b.h-2);
		g2.restore();
	};

	console.log("start");
	var reward;


	//↓ここから計算用
	function calculate(In){
		while (numberOfFrames<10000){
			p.x += p.vx;
			p.y += p.vy;
			moveBar(In);
			if (p.y>=280){
				for (var i=0,I=b.x.length,hit=false; i<I; i++){
					if ((p.y-b.y[i])*p.vy<0 && Math.abs(p.x-b.x[i])<=b.w && Math.abs(p.y-b.y[i])<=b.h+p.r){
						p.vy *= -1;	hit = true;	break;}
					else if ((p.x-b.x[i])*p.vx<0 && Math.abs(p.y-b.y[i])<=b.h && Math.abs(p.x-b.x[i])<=b.w+p.r){
						p.vx *= -1;	hit = true;	break;}
				}
				if (hit){
					score += 10;
					reward += 10;

					b.x.splice(i,1); b.y.splice(i,1);
					if (b.x.length==0) break;
				}
			}
			if (p.x>w-p.r){ p.x = w-p.r; p.vx *= -1;} //right
			if (p.x<p.r){	p.x = p.r; p.vx *= -1;} //left
			if (p.y>h-p.r){	p.y = h-p.r; p.vy *= -1;} //up
			if (p.y<p.r+bar.y){
				var p_bar = Math.abs(p.x-bar.x);
				if (p_bar<=bar.L){
					var X = (p.x>bar.x) ? 1 : -1;　//衝突点のバーの法線ベクトル(X,1);
					if (p_bar<=bar.L-bar.edge) X = 0; //バーの中央
					else if (p_bar<=bar.L-bar.edge/3) X *= (p_bar-bar.L+bar.edge)/100; //0～0.3（バーの端は約73°）
					else X *= 0.3;
					var L = Math.sqrt(X*X+1); //法線ベクトルの長さ
					var vec = {x: X/L, y: 1/L}; //法線ベクトルの正規化
					var dot = vec.x*p.vx+vec.y*p.vy;
					p.y = p.r+bar.y;
					p.vx -= 2*dot*vec.x;
					p.vy -= 2*dot*vec.y;
					if (Math.abs(p.vx)/p.vy>1.5){ //角度が付き過ぎないよう調整
						var v2 = p.vx*p.vx+p.vy*p.vy;
						p.vy = Math.sqrt(v2/3.25);
						p.vx = (p.vx<0) ? -p.vy*1.5 : p.vy*1.5;
					}
				}else if (p.y<p.r){
					break;
				};
			};
			numberOfFrames++;
		};
	};

	//遺伝的アルゴリズム

	//初期設定

	//各時間ごとの行動を遺伝子とする個体を作る
	
	var N = 100;//個体数
	var individual = new Array(N);
	var chrom = 1000;//遺伝子数

	//初期の遺伝子決定(ランダム)
	for(var n=0;n<N;n++){
		individual[n] = new Array(chrom);
		for(var c=0;c<chrom;c++){
			individual[n][c] = Math.floor(Math.random()*3) - 1;
		};
	};

	//最も良い個体とその番号を入れる配列
	var best = new Array(2);

	document.getElementById("try").addEventListener("click", function(){
		//操作をGENERATION回繰り返す
		var GENERATION = document.getElementById("times").value;
		for(var ge=0;ge<GENERATION;ge++){

			if (ge == GENERATION-1){
				//結果の出力
				var copy_eval = new Array(N);
				for(var n=0;n<N;n++){
					copy_eval[n] = evaluation(individual[n]);
				}
				best = [copy_eval[0],0];//evaluation(個体)=ゲームスコア
				for(var n=0;n<N;n++){
					if(copy_eval[n]>best[0]){
						best[0] = copy_eval[n];
						best[1] = n;
					};
				};
				console.log("best : ", best[0], best[1]);
				if(best[0]>1500){
					console.log("break");
					break;
				}else{
					console.log("not break");
					ge = 0;
				};
			};
	
			//選択と交叉
			//MGG選択
			const crossrate = 0.8;
			if(crossrate>Math.random()){
				//親選択
				var r1 = Math.floor(Math.random()*N);
				var r2 = Math.floor(Math.random()*N);
				var rand1 = Math.floor(Math.random()*chrom);
				var rand2 = rand1 + Math.floor(Math.random()*(chrom-rand1));//0<=r1<r2<1000
				var crossposition = Math.floor(Math.random()*3);
				//二点交叉
				const CHILDLEN = 10;//2+2^3
				var child = new Array(CHILDLEN);
				for(var n=0;n<CHILDLEN;n++){
					child[n] = new Array(chrom);
				};
				for(var c=0;c<chrom;c++){
					var parent=[individual[r1][c],individual[r2][c]];
					child[0][c] = parent[0];
					child[1][c] = parent[1];
					if(c<rand1){
						child[2][c] = parent[0];
						child[3][c] = parent[0];
						child[4][c] = parent[0];
						child[5][c] = parent[0];
						child[6][c] = parent[1];
						child[7][c] = parent[1];
						child[8][c] = parent[1];
						child[9][c] = parent[1];
					}else if(rand1<=c && c<rand2){
						child[2][c] = parent[0];
						child[3][c] = parent[0];
						child[4][c] = parent[1];
						child[5][c] = parent[1];
						child[6][c] = parent[0];
						child[7][c] = parent[0];
						child[8][c] = parent[1];
						child[9][c] = parent[1];				
					}else{
						child[2][c] = parent[0];
						child[3][c] = parent[1];
						child[4][c] = parent[0];
						child[5][c] = parent[1];
						child[6][c] = parent[0];
						child[7][c] = parent[1];
						child[8][c] = parent[0];
						child[9][c] = parent[1];
					};
				};

				var	child_eval = new Array(CHILDLEN);
				for(var n=0;n<CHILDLEN;n++){
					child_eval[n] = evaluation(child[n])
				};

	
				//最も評価の高い個体の番号を取得
				var top = [child_eval[0],0];
				for(var n=1;n<CHILDLEN;n++){
					if(child_eval[n]>top[0]){
						top[0] = child_eval[n];
						top[1] = n;
					};
				};
			
				//ルーレット選択で決定した個体番号の取得
				var total = 0;
				for(var n=0;n<CHILDLEN;n++){
					total += child_eval[n];
				};
				var arrow = Math.floor(Math.random()*total);
				var select = 0;
				for(var n=0,sum=0.0;n<CHILDLEN;n++){
					sum += child_eval[n];
					if(sum>arrow){
						select = n;
						break;
					};
				};

				for(var c=0;c<chrom;c++){
					individual[r1][c] = child[top[1]][c];
					individual[r2][c] = child[select][c];
				};		
			};
			//突然変異
			const mutantrate = 0.01;
			for(var n=0;n<N;n++){
				if(Math.random()<mutantrate){
					var m = Math.floor(Math.random()*numberOfFrames);
					individual[n][m] = (individual[n][m]+2)%3 - 1;
				};
			};
		};
	},false);

	//誤差関数evaluation(個体[個体番号]) = ゲームスコア
	function evaluation(In){
		reward = 0;
		reset();
		calculate(In);//個体がゲームをする
		return reward//ブロック崩しのスコアを与える
	};
})();
</script>
</body>
</html>
```
※ コメントアウトは前のコードに依存しているかもしれません。
※ 結果は上にあります。