intime o'

その代償として無限に空想をすることを許された(斎藤茂太著「精神科の待合室」より) 巡回セールスマン問題、蟻コロニー最適化 - JavaScript 2011/08/27(Sat.)

ヒマを持て余して、主要なトコだけ書いた。
でもちょっと手抜き。実際には「10匹くらいアリを同時に放してフェロモン
出させる」ていうのを何回か繰り返すんだけど、面倒だから1匹ずつに
しちゃった。十行くらいのコードを9回コピペすればいいんだけど。

Wikipediaにも問題は書いてるけど、それよりちょっと改良したバージョンで
本によればかなり精度がいいやつ。つまり、次の地点に行く確率を
計算するんだけど、適当な確率で、さっきの確率が一番高いところを
自動で選ぶパターン。で今思ったんだけどその「適当な確率」の具体的な
数値が乗ってなかったので、私の想像。


var G={};
G.V=[];
G.V.push([50,50]);
G.V.push([30,50]);
G.V.push([50,30]);
G.V.push([100,100]);


init();
function step(){ ari(); evapo();}

//----------------
function evapo(){
	G.P=G.P.map(function(r){return r*=.6});
}

(function init(){
	G.E=[];
	G.P=[];
	for(var i=0;i<G.V.length;i++){
		G.P[i]=0;
		G.E[i]=[];
		for(var j=0;j<G.V.length;j++){
			var x1=G.V[i][0],y1=G.V[i][1],x2=G.V[j][0],y2=G.V[j][1];
			G.E[i][j]=Math.sqrt(Math.pow(x1-x2,2)+Math.pow(y1-y2,2));
		}
	}
})();

function ari(){
	var now=0,next,p_,P,prob=[],prob_max=0,max_i,rout=[0],nokori=[];
	for(var i=1;i<G.V.length;i++)nokori.push(i);
	//make a rout
	while(nokori.length>0){
		for(var i=0;i<nokori.length;i++){
			next=nokori[i];
			P=0;
			prob[i]=Math.pow(G.P[now][next]/G.E[now][next],2);
			P+=prob[i];
			if(prob_max<prob[i])max_i=i;
		}
		prob=prob.map(function($p){return $p/P});
		p_=Math.random();
		if(p_>.2){
			for(var i=0;i<prob.length;i++){
				if(p_<prob[i]){next=nokori[i];break;}
				else p_-=prob[i];
			}
		}else{
			next=nokori[max_i];
		}
		rout.push(next);
		for(var x;x=nokori.shift(),x!=next;nokori.push(x));
		now=next;
	}

	var len=0;
	//compute length of that rout, and phelomon.
	for(var i=1;i<rout.length;i++)len+=G.E[rout[i-1]][rout[i]];
	for(var i=1;i<rout.length;i++)G.P[rout[i-1]][rout[i]]+=1e3/len;
}

#TODO
canvasの上に最適なルートを随時描画する。
ユーザーはcanvasの上にクリックして地点を追加させてける。

コメ(0) | トラ(0)

---