利用HTML5 Canvas和Javascript实现的蚁群算法求解TSP问题演示

HTML5提供了Canvas对象,为画图应用提供了便利.

Javascript可执行于浏览器中, 而不须要安装特定的编译器；

基于HTML5和Javascript语言, 可随时编写应用, 为算法測试带来便利.

针对TSP问题, 编写了Ant colony algorithm, 用于演示该算法, tsp_ant_colony_algorithm.html代码例如以下:

<html>
<head><meta charset = "utf-8" / > 
<title>TSP_demo</title>
</head>
<body>
<div id="outText">
</div>
<canvas id="canvas" height="550px" width="1024px">
</canvas>
<script type="text/javascript">
//计时開始
t1 = new Date();			//创建"then"这个日期/时间对像
t1.setTime(t1.getTime());	//为这个对象赋值var canvas = document.getElementById("canvas");
var canvasWidth = canvas.width;
var canvasHeight = canvas.height;
var context = canvas.getContext("2d");var N = 30;   //城市数量
var M = 120;   //蚂蚁数量var inittao = 1;   //初始路径激素量 
var tao;   //[N][N];     //N*N矩阵——表示i和j间残留的激素信息量, 初始化为常熟C（各路径相等），以表示激素的挥发
var yita; //[N][N];      //N*N矩阵——表示i和j间由举例所决定的选择概率矩阵
var delta_tao; //[N][N]; //一轮循环后添加的信息素
var distant; //[N][N];   //全部城市间的距离
var tabu; //[M][N];         //禁忌表
var route; //[M][N];        //M仅仅蚂蚁所走过的路径
var solution; //[M];     //对M仅仅蚂蚁所走过路径的适应度评价值
var BestRoute; //[N];       //最忌路径
var BestSolution = 10000000000;   //设置的极限最大路径
var alfa, beta, rou, Q;        //路径激素更新数量
var NcMax;                        //蚁群最大迭代次数function initMat(M, N, val) {var x = new Array();for(var i = 0; i < M; i++) {x[i] = new Array();for(var j = 0; j < N; j++)x[i].push(val);}return x;
}function initAllMats() {tao = initMat(N, N, 0);yita = initMat(N, N, 0);delta_tao = initMat(N, N, 0);distant = initMat(N, N, 0);tabu = initMat(M, N, 0);route = initMat(M, N, -1);solution = new Array();for(var i = 0; i < M; i++)solution[i] = 0;BestRoute = new Array();for(var i = 0; i < N; i++)BestRoute[i] = -1;
}//初始化城市的位置
function InCityXY(x, y)
{ for(var i = 0; i < N; i++) {x[i] = (Math.random() * 32767) % 980 + 20;y[i] = (Math.random() * 32767) % 420 + 20;}
}//初始化算法參数
function initparameter() 
{ alfa = 1;   //积累的激素调节因子作用系数beta = 5;   //启示性调节因子作用系数rou = 0.9;  Q = 100;    //常量NcMax = 200; //群蚂蚁进化代数
} //取得某个路径的长度
function EvalueSolution(a) 
{ var dist = 0; for(var i = 0; i < N-1; i++)dist += distant[a[i]][a[i+1]]; dist += distant[a[N-1]][a[0]]; return dist; 
} function drawCities(x, y) {for(var i = 0; i < N; i++) {context.beginPath();context.fillStyle = "blue";context.strokeStyle = "blue";context.lineWidth = 1;context.font = "normal 16px Arial";context.arc(x[i], y[i], 3, (Math.PI / 180) * 0, (Math.PI / 180) * 360, false);context.fill();context.stroke();context.closePath();
/*context.fillStyle = "white";context.textAlign = "center";context.textBaseline = "middle";context.fillText(String(i), x[i], y[i]);
*/}
}function drawPath(x1, y1, x2, y2, color, width) {context.beginPath();context.fillStyle = color;context.strokeStyle = color;context.lineWidth = width;context.moveTo(x1, y1);context.lineTo(x2, y2);context.stroke();
}//主函数
function ACA_TSP() {var NC = 0; //初始化算法參数initparameter(); //初始化城市的位置var x = new Array();var y = new Array();for(var i = 0; i < N; i++) {x.push(0);y.push(0);}//初始化城市位置InCityXY( x, y ); //计算随意两城市间的距离for(var i=0;i<N;i++) for(var j=i+1;j<N;j++) { distant[j][i] = Math.sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); distant[i][j] = distant[j][i]; } // calculate the heuristic parameters var i, j, k;//初始化随意两点间的选择可能性程度=1-p//若i==j。则p=1//否则。p=100/distant[i][j]for(i=0;i<N;i++) for(j=0;j<N;j++) { tao[i][j] = inittao; if(j != i) yita[i][j] = 100/distant[i][j];    //值越大，i到j被选择的路径概率越大; 或者说，i和j距离越近，被选择的概率越大} //初始化M个蚂蚁走全然部城市(N)的路径//-1表示第k仅仅蚂蚁尚没有从当前位置走向i城市/*for(k=0;k<M;k++) for(i=0;i<N;i++) route[k][i] =- 1; *///初始化全部蚂蚁的禁忌表for(k=0;k<M;k++) { route[k][0] = k % N;     //随机置放蚂蚁的第一站城市点---此代码实际上没有随机摆放tabu[k][route[k][0]] = 1;  //设置禁忌表的已訪问过的城市为1} //全部蚂蚁行走NcMax趟do { var s = 1; var partsum; var pper; var drand; //s循环N次，让每仅仅蚂蚁走N步，走全然程while( s < N) { for(k=0;k<M;k++) { var jrand= (Math.random() * 32767) % 3000; drand= jrand / 3001.0; partsum = 0; pper = 0; for(j=0;j<N;j++) { if(tabu[k][j]==0) partsum += Math.pow(tao[route[k][s-1]][j],alfa) * Math.pow(yita[route[k][s-1]][j],beta); } for(j=0;j<N;j++) { if(tabu[k][j]==0) pper += Math.pow(tao[route[k][s-1]][j],alfa) * Math.pow(yita[route[k][s-1]][j],beta)/partsum; if(pper > drand) break; } tabu[k][j]=1; route[k][s]=j; } s++; } // the pheromone is updated for(i=0;i<N;i++) for(var j=0;j<N;j++) delta_tao[i][j]=0; //记录最短路径及其长度for(k=0;k<M;k++) { solution[k] = EvalueSolution(route[k]); if(solution[k] < BestSolution) { BestSolution = solution[k]; for(s=0; s<N; s++) BestRoute[s]=route[k][s]; } } //依据上一批次（M个蚂蚁）所求路径的长度信息，更新从i到j的选择概率for(k=0;k<M;k++) { for(s=0;s<N-1;s++) delta_tao[route[k][s]][route[k][s+1]] += Q/solution[k]; delta_tao[route[k][N-1]][route[k][0]] += Q/solution[k]; } //计算NxN个节点间的转移概率。并设置最大与最小值for(i=0;i<N;i++) for(var j=0;j<N;j++) { tao[i][j]=rou*tao[i][j]+delta_tao[i][j]; if(tao[i][j] < 0.00001) tao[i][j] = 0.00001; if(tao[i][j] > 20) tao[i][j] = 20; } //又一次设置全部蚂蚁的禁忌表和路径信息for(k=0;k<M;k++) for(var j=1;j<N;j++) { tabu[k][route[k][j]]=0; route[k][j]=-1; } NC++; } while(NC < NcMax); //output the calculating outs /*print("*针对旅行商问题的蚂蚁克隆算法*"); print("初始參数："); print("alfa=" + alfa + ", beta=" + beta + ", rou=" + rou + ", Q=" + Q); print("蚁群探索循环次数:" + NcMax);print("最短路径是:" + BestSolution);print("最佳路径是:"); */for(i = 0; i < N; i++) {if (i == N - 1)j = 0;elsej = i + 1;var nodeA = BestRoute[i];var nodeB = BestRoute[j];var x1 = x[nodeA];var y1 = y[nodeA];var x2 = x[nodeB];var y2 = y[nodeB];drawPath(x1, y1, x2, y2, "black", 2);}drawCities(x, y);var out = document.getElementById("outText");out.innerHTML = "<h1>蚂蚁克隆算法求解旅行商问题: </h1>最佳路径:<br/>";for(i=0;i<N;i++) out.innerHTML = out.innerHTML + String(BestRoute[i]) + " ";out.innerHTML = out.innerHTML + "<br/>最短路径长度:<br/>" + BestSolution;
}//调用上述函数
initAllMats();
ACA_TSP();//结束后,取得如今时间, 并计算时间差
t2 = new Date();			//创建"then"这个日期/时间对像
var ms = t2.getTime() - t1.getTime();
var out = document.getElementById("outText");
out.innerHTML = out.innerHTML + "<br/>用时(毫秒):<br/>" + ms;
</script>
</body>
</html>

刷新该页面, 可随机产生不同的城市点, 并计算最短路径.

实例效果例如以下: