#はじめに
ブロック崩しを攻略する人工知能の開発をしている。私たちの人工知能は画面データを入力とし,行動の価値を出力とするニューラルネットワークである。ここで問題となるのがニューラルネットワークの構造である。ニューラルネットワークの構造はニューロンの数と重みに依存する。これまでは強化学習のデータを教師データとしてニューラルネットワークの重みを逆伝播法で学習させていた。その結果はこちらを見ればわかるようにイマイチである。**今回は実数値遺伝的アルゴリズムを使ってニューラルネットワークの重みを最適化する。**つまり,何体かの個体にゲームをさせてスコアが高い個体の遺伝子をもった個体を作る。。。予定だったが,実行結果が遅いのでそのアイデアと今後の予定を書く。
#遺伝的アルゴリズムの流れ
世代交代モデルはMGG,交叉はBLX-α,評価はスコアの高いものを高くする。
1.重みとなる遺伝子をもった個体の個体群を作る
2.ランダムに1組の親を個体群から選び,子供をn個体作る(BLX-α)
3.親と子供のn+2個体にブロック崩しをさせ,最も評価の高い個体とルーレット選択で選んだ1個体を親個体と入れ替える
4. 2,3を繰り返す
以下コードを書く
##1.重みとなる遺伝子をもった個体の個体群を作る
//初期設定
// バイアスありの(6,33,3)ニューラルネットワーク
const INLEN = 6;
const HIDLEN = 33;
const OUTLEN = 3;
var N = 10;//個体数
var individual = new Array(N);
var chrom = INLEN*(HIDLEN - 1) + HIDLEN*OUTLEN;//遺伝子数=重みの数
//初期の遺伝子決定(ランダム)
for(var n=0;n<N;n++){
individual[n] = new Array(chrom);
for(var c=0;c<chrom;c++){
individual[n][c] = Math.random()-0.5;//-0.5〜0.5
};
};
##2.ランダムに1組の親を個体群から選び,子供をn個体作る(BLX-α)
コードでは1,2人目の子供に親を代入して,n+2人の子供を作っている。BLX-αについては前回のメモを参照。
//親選択
var r1 = Math.floor(Math.random()*N);
var r2 = Math.floor(Math.random()*N);
//1,2人目の子供に親を代入して,n+2人の子供をつくる
const CHILDLEN = 20;
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]];
if(n==0){
child[0][c] = parent[0];//親を代入
}else if(n==1){
child[1][c] = parent[1];//親を代入
}else{
//BLX-αで子供を作る
const ALPHA = 0.5;
var minP = Math.min(parent[0],parent[1])-ALPHA*Math.abs(parent[0]-parent[1]);
var maxP = Math.max(parent[0],parent[1])+ALPHA*Math.abs(parent[0]-parent[1]);
child[n][c] = minP + Math.random()*(maxP - minP);
};
};
};
##3.親と子供のn+2個体にブロック崩しをさせ,最も評価の高い個体とルーレット選択で選んだ1個体を親個体と入れ替える
//評価関数evaluationが最小の個体番号の取得
//evaluation(個体)=ゲームスコア
var top = [evaluation(child[0]),0];
for(var n=1;n<CHILDLEN;n++){
if(evaluation(child[n])>top[0]){
top[0] = evaluation(child[n]);
top[1] = n;
};
};
//ルーレット選択で決定した個体番号の取得
var total = 0;
for(var n=0;n<CHILDLEN;n++){
total += evaluation(child[n]);
};
var arrow = Math.random()*total;
var select = 0;
for(var n=0,sum=0.0;n<CHILDLEN;n++){
sum += evaluation(child[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];
};
##重要な関数
###評価関数 evaluation( )
function evaluation(In){
reward = 0;//スコアを0にセット
var copyi = new Array(chrom);
for(var c=0;c<chrom;c++){
copyi[c] = In[c];//とりあえずコピー
};
for(var count=0;count<10;count++){
reset();
calculate(copyi);//個体がゲームをする
};
return reward//ブロック崩しのスコアを返す
};
###ニューラルネットワーク net( )
net(個体,個体番号,,,行動) = 行動の価値
//シグモイド関数
function sigmoid(x){
const A = 1.0;
return 1.0/(1.0 + Math.exp(-A*x));
};
function net(In,x,y,z,vx,vy,a){
var copyi = new Array(chrom);
for(var c=0;c<chrom;c++){
copyi[c] = In[c];//とりあえずコピー
};
var c = 0;
//個体の遺伝子を重みに対応付ける(input)
var input_W = new Array(INLEN);
for(var i=0;i<INLEN;i++){
input_W[i] = new Array(HIDLEN-1);
for(var j=0;j<HIDLEN-1;j++){
input_W[i][j] = copyi[c];
c++;
};
};
//(hidden)
var hidden_W = new Array(HIDLEN);
for(var i=0;i<HIDLEN;i++){
hidden_W[i] = new Array(OUTLEN);
for(var j=0;j<OUTLEN;j++){
hidden_W[i][j] = copyi[c];
c++;
};
};
//ニューロンの決定
var input_N = [x/600,y/400,z/600,vx,vy,-1];
var hidden_N = new Array(HIDLEN-1);
hidden_N.push(-1);
var output_N = new Array(OUTLEN);
for(i=0;i<HIDLEN-1;i++){
var input_SUM = 0.0;
for(var j=0;j<INLEN;j++){
input_SUM += input_W[j][i]*input_N[j];
};
hidden_N[i] = sigmoid(input_SUM);
};
for(var i=0;i<OUTLEN;i++){
var hidden_SUM = 0.0;
for(var j=0;j<HIDLEN;j++){
hidden_SUM += hidden_W[j][i]*hidden_N[j];
};
output_N[i] = sigmoid(hidden_SUM);
};
return output_N[a];
};
#結果
世代数やニューロンを増やせば実行結果が遅くなり,調節できないので結果もでない。
#課題
調整しないといけないパラメータが多い。具体的にはニューロンの数,世代数の数,子供の数,ゲームの回数。。。
また実行速度が遅い。
#ちょっと思ったこと
この動画をみて,時間ごとの行動を遺伝子とする遺伝的アルゴリズムをやってみようと思った。
成功例があるのは大きな励みになる。ただし,この遺伝的アルゴリズムは決められた時間に決められた行動をするだけなので応用が利かない。そこで意味づけとして強化学習を加えればいいのではないかと思った。
#今後の方針
実数値遺伝的アルゴリズムのみでブロック崩し攻略するのはひとまず置いておく。次は遺伝的アルゴリズム,ニューラルネットワーク,Q-learningを組み合わせた人工知能を作る。具体的には以下の流れで行う。
1.時間ごとの行動を遺伝子とする遺伝的アルゴリズムで理想的な個体を作る(スコアが高い,ボールを落とさないなど)
2.遺伝的アルゴリズムの行動をニューラルネットワークに学習させる
3.ニューラルネットワークに強化学習をさせる
つまり,遺伝的アルゴリズムで答えを作り,ニューラルネットワークで答えを丸暗記して,強化学習で意味を理解する。
とりあえず時間ごとの行動を遺伝子とする遺伝的アルゴリズムの実装をしてみる。
#参考文献
前回の記事
実数値遺伝的アルゴリズムによるニューラルネットワークの学習
#実装コード
<!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>
</p>
<script>
(function(){
//バーを動かす関数
function moveBar(In,T){
var action = Boltzmann(In,p.x,p.y,bar.x,p.vx,p.vy,T);
var tempX = bar.x+(action-1)*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]],1.0/Math.log(Time+1.001));
Time += 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;
if (d('resetEverytime').checked) reset();
else{
p.x = bar.x; p.y = bar.y+p.r;
var angle = Math.PI*(30)/180;//Math.PI*(Math.random()*60-30)/180; //-30~30
p.vx = Math.sin(angle)*12; p.vy = Math.cos(angle)*12; //cosとsinの反転に注意
numberOfBalls++;
}
drawBG();
}
}
numberOfFrames++;
timer = setTimeout(mainLoop,10); //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();
};
//ボルツマン選択
function Boltzmann(In,x,y,z,vx,vy,T){
var myNet = [net(In,x,y,z,vx,vy,0),net(In,x,y,z,vx,vy,1),net(In,x,y,z,vx,vy,2)];//net(個体,,,0)=行動0の価値
var prob = new Array(3);
for(var i=0;i<3;i++){
prob[i] = Math.exp(myNet[i]/T)/(Math.exp(myNet[0]/T) + Math.exp(myNet[1]/T) + Math.exp(myNet[2]/T));
};
var select = Math.random();
for(var i=0,sum=0.0;i<3;i++){
sum +=prob[i]
if (select<sum) {
return i;
};
};
};
console.log("start");
var Time = 0;
//↓ここから計算用
function calculate(In){
while (numberOfFrames<1000){
p.x += p.vx;
p.y += p.vy;
moveBar(In,1.0/Math.log(Time + 1.000010));
Time += 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;
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;
}
reward = +10;
}else if (p.y<p.r){
break;
};
};
numberOfFrames++;
};
};
//遺伝的アルゴリズム
//初期設定
// バイアスありの(6,33,3)ニューラルネットワーク
const INLEN = 6;
const HIDLEN = 30;
const OUTLEN = 3;
//遺伝子がニューラルネットワークの重みとなる個体を作る
var N = 10;//個体数
var individual = new Array(N);
var chrom = INLEN*(HIDLEN - 1) + HIDLEN*OUTLEN;//遺伝子数=重みの数
//初期の遺伝子決定(ランダム)
for(var n=0;n<N;n++){
individual[n] = new Array(chrom);
for(var c=0;c<chrom;c++){
individual[n][c] = Math.random()-0.5;//-0.5〜0.5
};
};
//最も良い個体とその番号を入れる配列
var best = new Array(2);
//操作をGENERATION回繰り返す
const GENERATION = 50;
for(var ge=0;ge<GENERATION;ge++){
if (ge == GENERATION-1){
//結果の出力
best = [evaluation(individual[0]),0];//evaluation(個体)=ゲームスコア
for(var n=0;n<N;n++){
if(evaluation(individual[n])>best[0]){
best[0] = evaluation(individual[n]);
best[1] = n;
};
};
console.log("best : ", best[0]);
break;
};
//選択と交叉
//MGG選択
const crossrate = 0.8;
if(crossrate>Math.random()){
//親選択
var r1 = Math.floor(Math.random()*N);
var r2 = Math.floor(Math.random()*N);
//親と子供を含めて,エリート+ルーレットで二個体を生成
const CHILDLEN = 2;
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]];
if(n==0){
child[0][c] = parent[0];
}else if(n==1){
child[1][c] = parent[1];
}else{
//BLX-α
const ALPHA = 0.5;
var minP = Math.min(parent[0],parent[1])-ALPHA*Math.abs(parent[0]-parent[1]);
var maxP = Math.max(parent[0],parent[1])+ALPHA*Math.abs(parent[0]-parent[1]);
child[n][c] = minP + Math.random()*(maxP - minP);
};
};
};
//誤差関数Eが最小の個体番号の取得
var top = [evaluation(child[0]),0];
for(var n=1;n<CHILDLEN;n++){
if(evaluation(child[n])>top[0]){
top[0] = evaluation(child[n]);
top[1] = n;
};
};
//ルーレット選択で決定した個体番号の取得
var total = 0;
for(var n=0;n<CHILDLEN;n++){
total += evaluation(child[n]);
};
var arrow = Math.random()*total;
var select = 0;
for(var n=0,sum=0.0;n<CHILDLEN;n++){
sum += evaluation(child[n]);
if(sum>arrow){
select = n;
break;
};
};
//疑問:individualが変更されればchildも変更されるのか?
for(var c=0;c<chrom;c++){
individual[r1][c] = child[top[1]][c];
individual[r2][c] = child[select][c];
};
};
//突然変異は行わない
};
//誤差関数evaluation(個体[個体番号]) = ゲームスコア
var reward;
function evaluation(In){
reward = 0;
var copyi = new Array(chrom);
for(var c=0;c<chrom;c++){
copyi[c] = In[c];
};
for(var count=0;count<10;count++){
reset();
calculate(copyi);//個体がゲームをする
};
return reward//ブロック崩しのスコアを与える
};
//シグモイド関数
function sigmoid(x){
const A = 1.0;
return 1.0/(1.0 + Math.exp(-A*x));
};
//ニューラルネットワーク(個体,個体番号,入力0,入力1) = 行動aの価値
function net(In,x,y,z,vx,vy,a){
var copyi = new Array(chrom);
for(var c=0;c<chrom;c++){
copyi[c] = In[c];
};
var c = 0;
//重み
var input_W = new Array(INLEN);
for(var i=0;i<INLEN;i++){
input_W[i] = new Array(HIDLEN-1);
for(var j=0;j<HIDLEN-1;j++){
input_W[i][j] = copyi[c];
c++;
};
};
var hidden_W = new Array(HIDLEN);
for(var i=0;i<HIDLEN;i++){
hidden_W[i] = new Array(OUTLEN);
for(var j=0;j<OUTLEN;j++){
hidden_W[i][j] = copyi[c];
c++;
};
};
//ニューロンの決定
var input_N = [x/600,y/400,z/600,vx,vy,-1];
var hidden_N = new Array(HIDLEN-1);
hidden_N.push(-1);
var output_N = new Array(OUTLEN);
for(i=0;i<HIDLEN-1;i++){
var input_SUM = 0.0;
for(var j=0;j<INLEN;j++){
input_SUM += input_W[j][i]*input_N[j];
};
hidden_N[i] = sigmoid(input_SUM);
};
for(var i=0;i<OUTLEN;i++){
var hidden_SUM = 0.0;
for(var j=0;j<HIDLEN;j++){
hidden_SUM += hidden_W[j][i]*hidden_N[j];
};
output_N[i] = sigmoid(hidden_SUM);
};
return output_N[a];
};
})();
</script>
</body>
</html>
※ 結果は上に書いてあります