蚁群算法js版 - 蓝色理想

　蚁群算法js版

作者：bjhaoyun　时间： 2006-04-17　文档类型：原创　来自：蓝色理想

人工生命—群集智能—蚁群算法js版

前言（摘自网上，代码是自己想出来的）

对于普通大众来说，“人工生命”、“群集智能”、“仿生机器人”等等可能是一些新鲜名词，他们可能会问，这些新鲜而时髦的科技的内容到底是什么？它们是否代表未来科技发展的方向？它们对人们的生活将会有什么样的影响？人类的未来将是什么样的？

对于计算机相关专业的技术人员来说，也许“细胞自动机”、“遗传算法”、“神经网络”、“蚁群算法”、“计算智能”等名词已经不陌生，然而这些技术之间究竟有什么联系？技术人员在同计算机程序中的 Bug 无休止地作斗争的同时，能不能考虑让计算机程序自发地变聪明？计算机程序可以自发地修正自己的错误吗？

对于生物专业的人士来说，他们可能更加关心自然生物 DNA 的合成、培育和生长。然而究竟什么是“活性”的本质？生命是一种物质还是信息？如何不进行昂贵而笨重的生物学实验就能验证研究人员的某个理论？

对于社会科学家和管理者来说，他们可能很关心如何让人们自发地合作，如何让一个组织更具活力。我们将会看到，自然界中的蚂蚁仅仅遵循简单的规则就能达到整体的合作从而有效、快速地搬运食物。那么，我们能否像蚂蚁那样每个人仅仅根据简单的规则完成简单的决策就有可能在人类群体中涌现出意想不到的集体效应？

这些问题表面上看，差异很大，但令人高兴的是，今天它们都可以在一门新兴科学——计算机科学和生物学交叉的人工生命中找到答案。人工生命诞生于 20 世纪末。起初，从事人工生命研究生学者主要是一些计算机科学家，他们向大自然学习，把生物的灵活适应本领移植到计算机中，让程序变得聪明起来。“遗传算法”、“神经网络”、“蚁群算法”等等正是计算机科学家向生物界学习的成果。另外，计算机也提供了天然的生物系统的模拟场所，这让生物学家们在电脑中就可以进行在平常情况下难以进行或无法进行的一些实验。

然而，人工生命不仅仅关心一些具体的技术问题，它更是一种崭新的自下而上的科学思维方法。事实上，在不经意间，科学界已经发生了一次全新的方法论变革：这就是用综合集成的方法代替还原分解的方法。我们仅掌握原子世界的规律并不能完全理解生命现象。纯粹的还原论已经走到了尽头，而通过计算机的帮助人们就可以把已经被分解还原的单个规律重新综合组织起来。我们不仅关心每个计算单元的属性，而且关心这些单元组合而成的整体动态。单个单元也许是非活性的，但单元的组合可能涌现出“活性”。这就是人工生命的方法。

人工生命学科还很年轻，在很多方面仍然不够成熟，而且很多学者对这门新学科的发展也各执看法，甚至这门学科的研究范围都不是很确定。我们所提到的人工生命在技术上主要指在数字世界中创造的虚拟版本的人工生命和在现实世界中创造的机器人版本的人工生命；在方法论上则主要强调自下而上的涌现方法和自发的适应进化方法。因此，所述的各种人工生命模型的基本思想是尽量减少人为的外在干预，让系统自发的发展、进化。

人工生命自一开始诞生就是一门理论和实际紧密结合的学科，它一方面需要人们运用抽象的理性思维看待生命，另一方面又特别强调计算机模拟实验。本着这种思路，每一个人工生命的实例都尽量写出其中的核心代码。因此熟悉计算机编程的人们可以从这些叙述中直接在自己的计算机上实现各种活灵活现的人工生命模型。

蚁群算法

还没有完成，现贴个初步的结果上来，大家帮忙一起研究下了，谢谢！
目前能实现随意控制蚂蚁的轨迹长度（Path）、数量（Unit）、速度（V）、角度（R）、加速度（dv，dr）。
Kr和Kv是常数，打算将来改成数组，作为用来控制蚂蚁活跃程度的基因。
但是总的div数量受机器速度限制，数量多了会很慢，我的机器最多只能跑得动3000只蚂蚁（当然轨迹要减小到1），已经把运动延时设成和蚂蚁数量相关，希望能有高手帮忙优化下。再次感谢！

思路1：用div做点

运行代码框
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"><HEAD> <meta http-equiv="Content-Type" content="text/html; charset=gb2312" /> <title>蚁群算法js版</title> <style> .ant{ position:absolute; background-color:#000000; overflow:hidden; width:2px; height:2px; } .food{ position:absolute; background-color:#0000ff; overflow:hidden; width:2px; height:2px; } .nest{ position:absolute; background-color:#ff0000; overflow:hidden; width:2px; height:2px; } </style> <script type="text/JavaScript"> //============================ //系统参数初始化 //---------------------------- //生命体数量与轨迹长度 Unit=10;Path=30; //生命体速度上下限 v0=2;vM=10; //生命体加速度变化范围 Kr=0.1;Kv=0.1*(vM-v0); //生命体运动范围 x0=0;xM=document.documentElement.clientWidth; y0=0;yM=document.documentElement.clientHeight; //生命体出生地(巢穴) xi0=x0+(xM-x0)*Math.random(); yi0=y0+(yM-y0)*Math.random(); str0='<div class="ant" style="left:'+xi0+';top:'+yi0+';"></div>'; //食物所在地 xf=x0+(xM-x0)*Math.random(); yf=y0+(yM-y0)*Math.random(); //气味感知范围 R_2=5*5; //============================ var r=new Array(); var v=new Array(); var dr=new Array(); var dv=new Array(); var x=new Array(); var y=new Array(); var life=new Array(); //单击暂停 var xi0,yi0,xf,yf; var Time0,str0; window.status='pause'; function document.onclick(){ if(window.status=='pause'){ window.status=0; nest.style.left=xi0; nest.style.top=yi0; food.style.left=xf; food.style.top=yf; //测试初始化时间用 Time0=(new Date()).getTime(); init(0); }else{ window.status='pause'; } } //窗口大小调整后刷新页面以调整系统参数 function window.onresize(){ // window.location.href=document.location; } //初始化函数 function init(i){ if(window.status!='pause'&&i<Unit){ if(!life[i]){ document.body.appendChild(life[i]=document.createElement(str0)); x[i]=xi0; y[i]=yi0; r[i]=Math.random(); v[i]=1/Math.random(); dr[i]=Kr*Math.random(); dv[i]=Kv*Math.random(); } Move(i); window.status=i+1; setTimeout('init('+(i+1)+')',i); // }else{ // alert('生成耗时：'+((new Date()).getTime()-Time0)+'ms'); } } //运动函数 Total=Unit*Path; P2=2*Math.PI; function Move(i){ if(window.status!='pause'){ k=i%Unit; X=x[k]; Y=y[k]; R=r[k]; V=v[k]; if(!life[i]){ str='<div class="ant" style="left:'+X+';top:'+Y+';"></div>'; document.body.appendChild(life[i]=document.createElement(str)); } obj=life[i]; R+=dr[k]*(2*Math.random()-1); V+=dv[k]*(2*Math.random()-1); X+=Math.sin(P2*R)*V; Y+=Math.cos(P2*R)*V; //遇到食物原路返回并减小角度变化 distance=(X-xf)*(X-xf)+(Y-yf)*(Y-yf); if(distance<R_2){ R+=0.5; r[i]/=2; v[i]*=2; } distance=(X-xi0)*(X-xi0)+(Y-yi0)*(Y-yi0); if(distance<R_2){ R+=0.5; r[i]/=2; v[i]*=2; } /*---------------------------------- /*================================*/ //碰撞边界反弹 R=(X<x0||X>xM)?-R:R; R=(Y<y0||Y>yM)?0.5-R:R; X=x[k]+Math.sin(P2*R)*V; Y=y[k]+Math.cos(P2*R)*V; /*================================*/ //溢出边界重生(类似流星效果) if(X<x0||X>xM||Y<y0||Y>yM){ X=xi0; Y=yi0; } /*---------------------------------- /*================================*/ //边界限制 x[k]=X=(X<x0)?x0:(X>xM)?xM-2:X; y[k]=Y=(Y<y0)?y0:(Y>yM)?yM-2:Y; r[k]=R>1?R-1:R<0?R+1:R; v[k]=V=(V<v0)?v0:((V<vM)?V:vM); /*================================*/ obj.style.left=x[k]=X; obj.style.top=y[k]=Y; setTimeout('Move('+(i+Unit)%Total+')',Unit); } } //根据浏览器自动加载动画 switch(navigator.appName.toLowerCase()){ case "netscape": window.addEventListener("load",document.onclick,false); break; case "microsoft internet explorer": default: window.attachEvent("onload",document.onclick); break; } </script> </head> <body scroll="no"> <div id="food" class="food"></div> <div id="nest" class="nest"></div> </body> </html>
[Ctrl+A 全部选择提示：你可先修改部分代码，再按运行]

用div做点总觉得不是很值得，哪位大侠有更好的方法还请指点迷经!

为了方便大家比较div和move函数对蚂蚁数量的敏感程度，做了两个临时脚本供大家参考都是500只蚂蚁，轨迹为1，机器慢的朋友请适当减小参数后再运行。

这是无div的情形：初始化耗时28078ms（仅供参考）

运行代码框
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"><HEAD> <meta http-equiv="Content-Type" content="text/html; charset=gb2312" /> <title>蚁群算法js版</title> <style> .point{ position:absolute; background-color:#000000; overflow:hidden; width:2px; height:2px; } </style> <script type="text/JavaScript"> //============================ //系统参数初始化 //---------------------------- //生命体数量与轨迹长度 Unit=500;Path=1; //生命体速度上下限 v0=2;vM=10; //生命体加速度变化范围 Kr=0.1;Kv=0.1*(vM-v0); //生命体运动范围 x0=0;xM=document.documentElement.clientWidth; y0=0;yM=document.documentElement.clientHeight; //生命体出生地(蚁巢) xi0=(x0+xM)/2;yi0=(y0+yM)/2; //============================ var r=new Array(); var v=new Array(); var dr=new Array(); var dv=new Array(); var x=new Array(); var y=new Array(); var life=new Array(); //单击暂停 window.status='pause'; var Time0; function document.onclick(){ if(window.status=='pause'){ window.status=0; Time0=(new Date()).getTime(); init(0); }else{ window.status='pause'; } } //边界随窗口大小调整 function window.onresize(){ xM=document.documentElement.clientWidth; yM=document.documentElement.clientHeight; xi0=(x0+xM)/2; yi0=(y0+yM)/2; } //初始化函数 function init(i){ if(window.status!='pause'&&i<Unit){ if(!life[i]){ life[i]='<div class="point" style="left:'+xi0+';top:'+yi0+';"></div>'; // str='<div class="point" style="left:'+xi0+';top:'+yi0+';"></div>'; // document.body.appendChild(life[i]=document.createElement(str)); x[i]=xi0; y[i]=yi0; r[i]=Math.random(); v[i]=1/Math.random(); dr[i]=Kr*Math.random(); dv[i]=Kv*Math.random(); } Move(i); window.status=i+1; setTimeout('init('+(i+1)+')',0/*i*/); }else{ alert('无div生成耗时：'+((new Date()).getTime()-Time0)+'ms'); Time0=(new Date()).getTime(); } } //运动函数 Total=Unit*Path; P2=2*Math.PI; function Move(i){ if(window.status!='pause'){ k=i%Unit; X=x[k]; Y=y[k]; R=r[k]; V=v[k]; if(!life[i]){ life[i]='<div class="point" style="left:'+X+';top:'+Y+';"></div>'; // str='<div class="point" style="left:'+X+';top:'+Y+';"></div>'; // document.body.appendChild(life[i]=document.createElement(str)); } obj=life[i]; R+=dr[k]*(2*Math.random()-1); V+=dv[k]*(2*Math.random()-1); X+=Math.sin(P2*R)*V; Y+=Math.cos(P2*R)*V; //碰撞边界反弹 R=(X<x0||X>xM)?-R:R; R=(Y<y0||Y>yM)?0.5-R:R; X=x[k]+Math.sin(P2*R)*V; Y=y[k]+Math.cos(P2*R)*V; /*================================*/ //溢出边界重生(类似流星效果) if(X<x0||X>xM||Y<y0||Y>yM){ X=xi0; Y=yi0; } /*---------------------------------- /*================================*/ r[k]=R>1?R-1:R<0?R+1:R; v[k]=V=(V<v0)?v0:((V<vM)?V:vM); //obj.style.left=x[k]=X; //obj.style.top=y[k]=Y; setTimeout('Move('+(i+Unit)%Total+')',/*Unit*/45); } } //根据浏览器自动加载动画 switch(navigator.appName.toLowerCase()){ case "netscape": window.addEventListener("load",document.onclick,false); break; case "microsoft internet explorer": default: window.attachEvent("onload",document.onclick); break; } </script> </head> <body scroll="no"> </body> </html>
[Ctrl+A 全部选择提示：你可先修改部分代码，再按运行]

这是无move函数的情形，初始化耗时12437ms（仅供参考）

运行代码框
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"><HEAD> <meta http-equiv="Content-Type" content="text/html; charset=gb2312" /> <title>蚁群算法js版</title> <style> .point{ position:absolute; background-color:#000000; overflow:hidden; width:2px; height:2px; } </style> <script type="text/JavaScript"> //============================ //系统参数初始化 //---------------------------- //生命体数量与轨迹长度 Unit=500;Path=1; //生命体速度上下限 v0=2;vM=10; //生命体加速度变化范围 Kr=0.1;Kv=0.1*(vM-v0); //生命体运动范围 x0=0;xM=document.documentElement.clientWidth; y0=0;yM=document.documentElement.clientHeight; //生命体出生地(蚁巢) xi0=(x0+xM)/2;yi0=(y0+yM)/2; //============================ var r=new Array(); var v=new Array(); var dr=new Array(); var dv=new Array(); var x=new Array(); var y=new Array(); var life=new Array(); //单击暂停 window.status='pause'; var Time0; function document.onclick(){ if(window.status=='pause'){ window.status=0; Time0=(new Date()).getTime(); init(0); }else{ window.status='pause'; } } //边界随窗口大小调整 function window.onresize(){ xM=document.documentElement.clientWidth; yM=document.documentElement.clientHeight; xi0=(x0+xM)/2; yi0=(y0+yM)/2; } //初始化函数 function init(i){ if(window.status!='pause'&&i<Unit){ if(!life[i]){ str='<div class="point" style="left:'+xi0+';top:'+yi0+';"></div>'; document.body.appendChild(life[i]=document.createElement(str)); x[i]=xi0; y[i]=yi0; r[i]=Math.random(); v[i]=1/Math.random(); dr[i]=Kr*Math.random(); dv[i]=Kv*Math.random(); } //Move(i); window.status=i+1; setTimeout('init('+(i+1)+')',0/*i*/); }else{ alert('无move函数生成耗时：'+((new Date()).getTime()-Time0)+'ms'); } } //运动函数 Total=Unit*Path; P2=2*Math.PI; function Move(i){ if(window.status!='pause'){ k=i%Unit; X=x[k]; Y=y[k]; R=r[k]; V=v[k]; if(!life[i]){ str='<div class="point" style="left:'+X+';top:'+Y+';"></div>'; document.body.appendChild(life[i]=document.createElement(str)); } obj=life[i]; R+=dr[k]*(2*Math.random()-1); V+=dv[k]*(2*Math.random()-1); X+=Math.sin(P2*R)*V; Y+=Math.cos(P2*R)*V; //碰撞边界反弹 R=(X<x0||X>xM)?-R:R; R=(Y<y0||Y>yM)?0.5-R:R; X=x[k]+Math.sin(P2*R)*V; Y=y[k]+Math.cos(P2*R)*V; /*================================*/ //溢出边界重生(类似流星效果) if(X<x0||X>xM||Y<y0||Y>yM){ X=xi0; Y=yi0; } /*---------------------------------- /*================================*/ r[k]=R>1?R-1:R<0?R+1:R; v[k]=V=(V<v0)?v0:((V<vM)?V:vM); obj.style.left=x[k]=X; obj.style.top=y[k]=Y; setTimeout('Move('+(i+Unit)%Total+')',/*Unit*/45); } } //根据浏览器自动加载动画 switch(navigator.appName.toLowerCase()){ case "netscape": window.addEventListener("load",document.onclick,false); break; case "microsoft internet explorer": default: window.attachEvent("onload",document.onclick); break; } </script> </head> <body scroll="no"> </body> </html>
[Ctrl+A 全部选择提示：你可先修改部分代码，再按运行]

测试结果显示div并不是速度的瓶颈，最影响速度的是move函数本身，所以优化它才是解决问题的关键所在！
更新了下，原先测的时间还偏长了些，因为不是严格在调用init前起获取时间

思路2：用vml中的path指令做点

经过学习终于搞明白了怎么用vml做点，并试着生成2000~4000个点看看，结果显示生成时间和点的数量已成正比，基本达到优化的目的，接下来的工作就是用vml实现了。

以下代码生成随机4000个由蚁巢出发的线段，大家放心了，生成中基本速度不减慢（看状态栏），当然机器较慢的朋友还是请适当减小参数再浏览。

运行代码框
<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office"> <meta http-equiv="Content-Type" content="text/html; charset=gb2312" /> <title>蚁群算法js版</title> <style> v\:*{behavior:url(#default#VML);}o\:*{behavior:url(#default#VML);} .ant{ position:absolute; background-color:#000000; overflow:hidden; width:2px; height:2px; } .food{ position:absolute; background-color:#0000ff; overflow:hidden; width:2px; height:2px; } .nest{ position:absolute; background-color:#ff0000; overflow:hidden; width:2px; height:2px; } </style> <script type="text/JavaScript"> //============================ //系统参数初始化 //---------------------------- //生命体数量与轨迹长度 Unit=4000;Path=1; //生命体运动范围 x0=0;xM=500; y0=0;yM=500; //生命体出生地(巢穴) var xi0=x0+(xM-x0)*Math.random(); var yi0=y0+(yM-y0)*Math.random(); //var str0='<div class="ant" style="left:'+xi0+';top:'+yi0+';"></div>'; var str0=Math.floor(xi0)+','+Math.floor(yi0); //食物所在地 xf=x0+(xM-x0)*Math.random(); yf=y0+(yM-y0)*Math.random(); /*---------------------------------- //生命体速度上下限 v0=2;vM=10; //生命体加速度变化范围 Kr=0.1;Kv=0.1*(vM-v0); //气味感知范围 R_2=5*5; //============================ var r=new Array(); var v=new Array(); var dr=new Array(); var dv=new Array(); var life=new Array(); /*================================*/ //单击暂停 var xi0,yi0,xf,yf; var Time0,clicked; window.status='pause'; function document.onclick(){ if(clicked){ window.status='pause'; return clicked=false; } window.status=0; nest.style.left=xi0; nest.style.top=yi0; food.style.left=xf; food.style.top=yf; clicked=true; //测试初始化时间用 Time0=(new Date()).getTime(); init(0); } //窗口大小调整后刷新页面以调整系统参数 function window.onresize(){ // window.location.href=document.location; } //初始化函数 var point=new Array(); function init(i){ if(!clicked) return false; if(i<Unit){ xi0=x0+(xM-x0)*Math.random(); yi0=y0+(yM-y0)*Math.random(); point[i]=Math.floor(xi0)+','+Math.floor(yi0); /*---------------------------------- r[i]=Math.random(); v[i]=1/Math.random(); dr[i]=Kr*Math.random(); dv[i]=Kv*Math.random(); /*================================*/ //Move(i); setTimeout('init('+(window.status=++i)+')',0); }else{ shape1.outerHTML=shape1.outerHTML.replace(/ path = \".*?\"/,' path = \"m'+str0+'l'+point.join('m'+str0+'l')+' e\"'); alert('生成耗时：'+((new Date()).getTime()-Time0)+'ms'); } } //运动函数 Total=Unit*Path; P2=2*Math.PI; function Move(i){ if(!clicked) return false; k=i%Unit; X=x[k]; Y=y[k]; R=r[k]; V=v[k]; if(!life[i]){ str='<div class="ant" style="left:'+X+';top:'+Y+';"></div>'; document.body.appendChild(life[i]=document.createElement(str)); } obj=life[i]; R+=dr[k]*(2*Math.random()-1); V+=dv[k]*(2*Math.random()-1); X+=Math.sin(P2*R)*V; Y+=Math.cos(P2*R)*V; //遇到食物原路返回并减小角度变化 distance=(X-xf)*(X-xf)+(Y-yf)*(Y-yf); if(distance<R_2){ R+=0.5; r[i]/=2; v[i]*=2; } distance=(X-xi0)*(X-xi0)+(Y-yi0)*(Y-yi0); if(distance<R_2){ R+=0.5; r[i]/=2; v[i]*=2; } /*---------------------------------- /*================================*/ //碰撞边界反弹 R=(X<x0||X>xM)?-R:R; R=(Y<y0||Y>yM)?0.5-R:R; X=x[k]+Math.sin(P2*R)*V; Y=y[k]+Math.cos(P2*R)*V; /*================================*/ //溢出边界重生(类似流星效果) if(X<x0||X>xM||Y<y0||Y>yM){ X=xi0; Y=yi0; } /*---------------------------------- /*================================*/ //边界限制 x[k]=X=(X<x0)?x0:(X>xM)?xM-2:X; y[k]=Y=(Y<y0)?y0:(Y>yM)?yM-2:Y; r[k]=R>1?R-1:R<0?R+1:R; v[k]=V=(V<v0)?v0:((V<vM)?V:vM); /*================================*/ obj.style.left=x[k]=X; obj.style.top=y[k]=Y; setTimeout('Move('+(i+Unit)%Total+')',Unit); } //根据浏览器自动加载动画 switch(navigator.appName.toLowerCase()){ case "netscape": window.addEventListener("load",document.onclick,false); break; case "microsoft internet explorer": default: window.attachEvent("onload",document.onclick); break; } </script> </head> <body style="margin:0px;"> <v:group ID="group1" style="position:relative; left:0px; top:0px;WIDTH:500px;HEIGHT:500px;" coordsize = "500,500"> <v:rect filled="f" style="width:100%;height:100%" /> <v:PolyLine filled="f" Points="0 0" /> <v:shape id=shape1 name=shape1 filled="f" style="width:100%;height:100%" path="m 0,0 e" /> </v:group> <div id="food" class="food"></div> <div id="nest" class="nest"></div> </body> </html>
[Ctrl+A 全部选择提示：你可先修改部分代码，再按运行]

顺便说下这里用到了join函数来连接坐标字符串数组从而达到降低时间复杂度的目的。

经典论坛讨论帖：
http://www.blueidea.com/bbs/NewsDetail.asp?id=2539054

出处：蓝色理想
责任编辑：moby

◎进入论坛网页制作、网站综合版块参加讨论

相关文章

常用JS网页广告代码

站点最新

站点最新列表

全兼容的纯CSS级联菜单要点浅析

CSS Sprites 图片整合技术

雅安,一场中式旅行

热烈祝贺"醒狮杯"圆满结束

菊花宝典大赏大奖教程《阳台》

交互设计师怎样和产品团队合作

Photoshop打造个性潮流音乐海报

简单解读面包屑

CSS盒模型

Apple与Microsoft网站可用性研究

栏目最新

栏目最新列表

safari 4 新特性

Photoshop制作精美高光流线字

IE下img多余5像素空白解决方法

XHTML1.0与HTML兼容指引16条

JavaScript优化细节

全兼容的纯CSS级联菜单要点浅析

CSS Sprites 图片整合技术

Photoshop打造个性潮流音乐海报

CSS盒模型

45度地图编辑器及游戏开发心得