戴尔服务器r410:[讨论]蚁群算法js版[vml vs div](20060421更新)

来源：百度文库编辑：中财网时间：2024/04/29 07:55:13

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

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

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

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

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

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

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

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

==========
蚁群算法
==========
大家帮忙一起研究下了，谢谢！
-------------------------
思路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>/*----------------------------------v\:*{behavior:url(#default#VML);}o\:*{behavior:url(#default#VML);}/*================================*/.map{position:absolute;background-color:#000000;overflow:hidden;top:0px;left:0px;}.ant{position:absolute;background-color:#ff0000;overflow:hidden;width:1px;height:1px;}.ant2{position:absolute;background-color:#00ff00;overflow:hidden;width:1px;height:1px;}.food{position:absolute;background-color:#00ffff;overflow:hidden;width:2px;height:2px;}.nest{position:absolute;background-color:#ff00ff;overflow:hidden;width:2px;height:2px;}</style><script type="text/JavaScript">//============================//系统参数初始化//----------------------------//生命体数量与轨迹长度Unit=30;Path=10;//生命体运动范围xM=500;yM=500;//生命体速度上下限v0=2;vM=10;//生命体加速度变化范围Kr=0.1;Kv=0.1*(vM-v0);//气味感知范围R_2=5*5;//生命体出生地(巢穴)var xi0=xM*Math.random();var yi0=yM*Math.random();var str0=Math.floor(xi0)+‘,‘+Math.floor(yi0);//食物所在地xf=xM*Math.random();yf=yM*Math.random();//============================var x=new Array();var y=new Array();var r=new Array();var v=new Array();var dr=new Array();var dv=new Array();var p=new Array();var q=new Array();/*================================*///单击暂停var xi0,yi0,xf,yf;var Time0,clicked;window.status=‘pause‘;function document.onclick(){if(clicked){window.status=‘pause‘;return clicked=false;}map.style.width=xM;map.style.height=yM;nest.style.left=xi0;nest.style.top=yi0;food.style.left=xf;food.style.top=yf;clicked=true;//测试初始化时间用//Time0=(new Date()).getTime();if(!inited)init(0);else StartMove(0);}//窗口大小调整后刷新页面以调整系统参数function window.onresize(){//window.location.href=document.location;}//初始化函数var life;str0=‘<div id=ant class=ant style=\"left:‘;str1=‘;\"></div>‘;inited=false;var point=new Array();Total=Unit*Path;function init(i){if(!clicked)return false;if(i<Total){if(i<Unit){x[i]=xi0;y[i]=yi0;p[i]=i;q[i]=‘ant‘;r[i]=Math.random();v[i]=1/Math.random();dr[i]=Kr*Math.random();dv[i]=Kv*Math.random();}else{xi0=x[i%Unit];yi0=y[i%Unit];}//vml做点//point[i]=Math.floor(xi0)+‘,‘+Math.floor(yi0);//div做点point[i]=Math.floor(xi0)+‘;top:‘+Math.floor(yi0);setTimeout(‘init(‘+(window.status=++i)+‘)‘,0);}else{//vml做点//shape1.outerHTML=shape1.outerHTML.replace(/ path = \".*?\"/,‘ path = \"m‘+str0+‘l‘+point.join(‘m‘+str0+‘l‘)+‘ e\"‘);//div做点map.innerHTML=str0+point.join(str1+str0)+str1;inited=true;window.status=0;//测试初始化时间用//alert(‘生成耗时：‘+((new Date()).getTime()-Time0)+‘ms‘);//Time0=(new Date()).getTime();StartMove(0);}}function StartMove(i){if(i<Unit){Move(p[i]);setTimeout(‘StartMove(‘+(window.status=++i)+‘)‘,0);}else{//测试初始化时间用//alert(‘生成耗时：‘+((new Date()).getTime()-Time0)+‘ms‘);}}//运动函数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];obj=ant[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;//遇到食物原路返回并减小角度变化if(q[i%Unit]==‘ant‘){distance=(X-xf)*(X-xf)+(Y-yf)*(Y-yf);if(distance<R_2){R+=0.5;q[i%Unit]=‘ant2‘;}}else{distance=(X-xi0)*(X-xi0)+(Y-yi0)*(Y-yi0);if(distance<R_2){R+=0.5;q[i%Unit]=‘ant‘;}}/*----------------------------------/*================================*///碰撞边界反弹R=(X<0||X>xM)?-R:R;R=(Y<0||Y>yM)?0.5-R:R;X=x[k]+Math.sin(P2*R)*V;Y=y[k]+Math.cos(P2*R)*V;/*================================*//*----------------------------------//溢出边界重生(类似流星效果)if(X<0||X>xM||Y<0||Y>yM){X=xi0;Y=yi0;}/*================================*///边界限制x[k]=X=(X<0)?0:(X>xM)?xM-2:X;y[k]=Y=(Y<0)?0:(Y>yM)?yM-2:Y;r[k]=(R>1)?(R-1):(R<0)?(R+1):R;v[k]=(V<v0)?v0:((V<vM)?V:vM);/*================================*/obj.style.left=x[k]=X;obj.style.top=y[k]=Y;i=p[i%Unit]=(i+Unit)%Total;obj.className=q[i%Unit];setTimeout(‘Move(‘+i+‘)‘,40/*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;"><div id="map" class="map"><div id="ant"></div></div><div id="food" class="food"></div><div id="nest" class="nest"></div></body></html>

提示：您可以先修改部分代码再运行4.21更新：
--------------
请参见见14层
采用数组做地图，用面向对象方法做蚂蚁

4.19更新：
--------------
受hutia启发：
转来一篇文章，面向对象js编程，一起学习哈
http://www.cnrui.cn/blog/?id=79

join函数来连接坐标字符串数组，结果显示生成时间和点的数量已成正比，基本达到从而达到降低时间复杂度的目的

优化算法，降低生成过程时间复杂度，使其与蚂蚁数量成正比。
增加找到食物变色
一次性生成所有div，再开始演绎

4.18更新：
-----------------
增加蚁巢和食物标记并让蚂蚁遇到食物或者蚁巢原路返回，同时减小角度变化并增大速度变化，食物和蚁巢位置设为随机产生
屏蔽了调整窗口事件中的刷新代码，以防止刷新到论坛页面，要预览随窗口调整效果建议放到本地运行并取消调整事件中屏蔽的代码
有个想法，就是所有的蚂蚁会随着时间推移活性（dr、dv）逐渐减小，轨迹逐渐减少，慢慢趋向死亡，除非找到食物，最终让能够经常找到食物的蚂蚁生存下来。
---------------------------------------
To wangzijia:
呵呵，不只是为了研究而研究，且不说这本身是个挑战并实现很多特效，单说js的面向对象特性在这里展现出来，只要延时足够长可以实现很复杂的算法呢
即使用C如果要生成点的话，也有同样的问题，到底是每次先计算好所有的点，再统一生成画面，还是一边计算一边生成某些特定的点，算法本身是和语言无必然联系的。
顺便说下我之所以做这个是因为看到别人做的一个java版本的示例，很有意思，但是速度实在慢的吓人，所以想到要自己做个看看。

4.17
----------------------------------------------
目前能实现随意控制蚂蚁的轨迹长度（Path）、数量（Unit）、速度（V）、角度（R）、加速度（dv，dr），Kr和Kv是常数，用来控制蚁群的活跃程度。

-------------------------
思路2：用vml中的path指令做点
----------------------
经过学习终于搞明白了怎么用vml做点，并试着生成2000~4000个点看看，以下代码生成随机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>

提示：您可以先修改部分代码再运行个人感觉在div和vml最主要的区别在于用div生成的点是静态的不像vml中的path最小化后还原要重新生成。

讨论预科VS复读关于FLASH+JS的讨论学习讨论高达SEED-D 华硕975 VS 技嘉975 大家来讨论讨论... 赛扬D VS 闪龙赛扬D VS 速龙 Mouz vs 3D 鲁尼 VS D罗 2005年最新VS.net哪有D版下载 VML是什么了？ trojandownloader.js.psye.d是什么病毒哪个大哥能给我提供一个关于3D MAX学习讨论交流的群 CANON 350D VS SONY @100 男篮世锦赛 D组中国VS意大利男篮世锦赛 D组波多黎各VS美国男篮世锦赛D组斯洛文尼亚VS塞内加尔蚁群优化算法的使用-编码的问题！ QQ群讨论组？麦克格雷迪讨论群讨论番茄花园版XP VML画一个饼图，无法显示 3D字谜011期,大家来讨论一下吧! 微粒群算法的问题 Euclid算法实现c++版