蚁群算法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 Fireworks 设计比赛网页制作 web标准用户体验 UE photoshop Dreamweaver Studio8 Flash 手绘 CG

站点最新

站点最新列表

周大福“敬•自然”设计大赛开启

国际体验设计大会7月将在京举行

中国国防科技信息中心标志征集

云计算如何让安全问题可控

云计算是多数企业唯一拥抱互联网的机会

阿里行云

云手机年终巨献，送礼标配299起

阿里巴巴CTO王坚的"云和互联网观"

1499元买真八核云OS双蛋大促

首届COCO桌面手机主题设计大赛

栏目最新

栏目最新列表

浅谈JavaScript编程语言的编码规范

如何在illustrator中绘制台历

Ps简单绘制一个可爱的铅笔图标

数据同步算法研究

用ps作简单的作品展示页面

CSS定位机制之一:普通流

25个最佳最闪亮的Eclipse开发项目

Illustrator中制作针线缝制文字效果

Photoshop制作印刷凹凸字体

VS2010中创建自定义SQL Rule