蚁群算法原理和源码

现在的位置: 首页＞科研＞正文

蚁群算法原理和源码

发表于848 天前 ⁄ 科研 ⁄ 暂无评论 ⁄ 被围观 616 次+

蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
　　蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。

　　蚁群算法是一种求解组合最优化问题的新型通用启发式方法，该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点。通过建立适当的数学模型，基于故障过电流的配电网故障定位变为一种非线性全局寻优问题。
　　预期的结果：
　　各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物！有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果令开辟的道路比原来的其他道路更短，那么，渐渐，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。
　　原理：
　　为什么小小的蚂蚁能够找到食物？他们具有智能么？设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼的编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序。
　　然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码不过100多行！为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？下面详细说明：
　　1、范围：
　　蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。
　　2、环境：
　　蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。
　　3、觅食规则：
　　在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。
　　4、移动规则：
　　每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。
　　5、避障规则：
　　如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。
　　7、播撒信息素规则：
　　每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。
　　根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。
　　问题：
　　说了这么多，蚂蚁究竟是怎么找到食物的呢？
　　在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁的某个方向正确，而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食物。
　　当然，在有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。
　　蚂蚁如何找到最短路径的？这一是要归功于信息素，另外要归功于环境，具体说是计算机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。也许有人会问局部最短路径和全局最短路的问题，实际上蚂蚁逐渐接近全局最短路的，为什么呢？这源于蚂蚁会犯错误，也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径，这可以理解为一种创新，这种创新如果能缩短路途，那么根据刚才叙述的原理，更多的蚂蚁会被吸引过来。
　　引申
　　跟着蚂蚁的踪迹，你找到了什么？通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的特点：
　　1、多样性
　　2、正反馈
　　多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。
　　引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。如果多样性过剩，也就是系统过于活跃，这相当于蚂蚁会过多的随机运动，它就会陷入混沌状态；而相反，多样性不够，正反馈机制过强，那么系统就好比一潭死水。这在蚁群中来讲就表现为，蚂蚁的行为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。
　　既然复杂性、智能行为是根据底层规则涌现的，既然底层规则具有多样性和正反馈特点，那么也许你会问这些规则是哪里来的？多样性和正反馈又是哪里来的？我本人的意见：规则来源于大自然的进化。而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合。而这样的巧妙结合又是为什么呢？为什么在你眼前呈现的世界是如此栩栩如生呢？答案在于环境造就了这一切，之所以你看到栩栩如生的世界，是因为那些不能够适应环境的多样性与正反馈的结合都已经死掉了，被环境淘汰了！
　　蚁群算法的实现
　　下面的程序开始运行之后，蚂蚁们开始从窝里出动了，寻找食物；他们会顺着屏幕爬满整个画面，直到找到食物再返回窝。
　　其中，‘F’点表示食物，‘H’表示窝，白色块表示障碍物，‘+’就是蚂蚁了。
　　参数说明：
　　最大信息素：蚂蚁在一开始拥有的信息素总量，越大表示程序在较长一段时间能够存在信息素。信息素消减的速度：随着时间的流逝，已经存在于世界上的信息素会消减，这个数值越大，那么消减的越快。
　　错误概率表示这个蚂蚁不往信息素最大的区域走的概率，越大则表示这个蚂蚁越有创新性。
　　速度半径表示蚂蚁一次能走的最大长度，也表示这个蚂蚁的感知范围。
　　记忆能力表示蚂蚁能记住多少个刚刚走过点的坐标，这个值避免了蚂蚁在本地打转，停滞不前。而这个值越大那么整个系统运行速度就慢，越小则蚂蚁越容易原地转圈。
　　/*ant.c*/
　　#define SPACE 0×20
　　#define ESC 0×1b
　　#define ANT_CHAR_EMPTY ‘+’
　　#define ANT_CHAR_FOOD 153
　　#define HOME_CHAR ‘H’
　　#define FOOD_CHAR ‘F’
　　#define FOOD_CHAR2 ‘f’
　　#define FOOD_HOME_COLOR 12
　　#define BLOCK_CHAR 177
　　#define MAX_ANT 50
　　#define INI_SPEED 3
　　#define MAXX 80
　　#define MAXY 23
　　#define MAX_FOOD 10000
　　#define TARGET_FOOD 200
　　#define MAX_SMELL 5000
　　#define SMELL_DROP_RATE 0.05
　　#define ANT_ERROR_RATE 0.02
　　#define ANT_EYESHOT 3
　　#define SMELL_GONE_SPEED 50
　　#define SMELL_GONE_RATE 0.05
　　#define TRACE_REMEMBER 50
　　#define MAX_BLOCK 100
　　#define NULL 0
　　#define UP 1
　　#define DOWN 2
　　#define LEFT 3
　　#define RIGHT 4
　　#define SMELL_TYPE_FOOD 0
　　#define SMELL_TYPE_HOME 1
　　#include “stdio.h”
　　#include “conio.h”
　　#include “dos.h”
　　#include “stdlib.h”
　　#include “dos.h”
　　#include “process.h”
　　#include “ctype.h”
　　#include “math.h”
　　void WorldInitial(void);
　　void BlockInitial(void);
　　void CreatBlock(void);
　　void SaveBlock(void);
　　void LoadBlock(void);
　　void HomeFoodInitial(void);
　　void AntInitial(void);
　　void WorldChange(void);
　　void AntMove(void);
　　void AntOneStep(void);
　　void DealKey(char key);
　　void ClearSmellDisp(void);
　　void DispSmell(int type);
　　int AntNextDir(int xxx,int yyy,int ddir);
　　int GetMaxSmell(int type,int xxx,int yyy,int ddir);
　　int IsTrace(int xxx,int yyy);
　　int MaxLocation(int num1,int num2,int num3);
　　int CanGo(int xxx,int yyy,int ddir);
　　int JudgeCanGo(int xxx,int yyy);
　　int TurnLeft(int ddir);
　　int TurnRight(int ddir);
　　int TurnBack(int ddir);
　　int MainTimer(void);
　　char WaitForKey(int secnum);
　　void DispPlayTime(void);
　　int TimeUse(void);
　　void HideCur(void);
　　void ResetCur(void);
　　/* ————— */
　　struct HomeStruct
　　{
　　int xxx,yyy;
　　int amount;
　　int TargetFood;
　　}home;
　　struct FoodStruct
　　{
　　int xxx,yyy;
　　int amount;
　　}food;
　　struct AntStruct
　　{
　　int xxx,yyy;
　　int dir;
　　int speed;
　　int SpeedTimer;
　　int food;
　　int SmellAmount[2];
　　int tracex[TRACE_REMEMBER];
　　int tracey[TRACE_REMEMBER];
　　int TracePtr;
　　int IQ;
　　}ant[MAX_ANT];
　　int AntNow;
　　int timer10ms;
　　struct time starttime,endtime;
　　int Smell[2][MAXX+1][MAXY+1];
　　int block[MAXX+1][MAXY+1];
　　int SmellGoneTimer;
　　int SmellDispFlag;
　　int CanFindFood;
　　int HardtoFindPath;
　　/* —– Main ——– */
　　void main(void)
　　{
　　char KeyPress;
　　int tu;
　　clrscr();
　　HideCur();
　　WorldInitial();
　　do
　　{
　　timer10ms = MainTimer();
　　if(timer10ms) AntMove();
　　if(timer10ms) WorldChange();
　　tu = TimeUse();
　　if(tu>=60&&!CanFindFood)
　　{
　　gotoxy(1,MAXY+1);
　　printf(“Can not find food, maybe a block world.”);
　　WaitForKey(10);
　　WorldInitial();
　　}
　　if(tu>=180&&home.amount<100&&!HardtoFindPath)
　　{
　　gotoxy(1,MAXY+1);
　　printf(“God! it is so difficult to find a path.”);
　　if(WaitForKey(10)==0×0d) WorldInitial();
　　else
　　{
　　HardtoFindPath = 1;
　　gotoxy(1,MAXY+1);
　　printf(” “);
　　}
　　}
　　if(home.amount>=home.TargetFood)
　　{
　　gettime(&endtime);
　　KeyPress = WaitForKey(60);
　　DispPlayTime();
　　WaitForKey(10);
　　WorldInitial();
　　}
　　else if(kbhit())
　　{
　　KeyPress = getch();
　　DealKey(KeyPress);
　　}
　　else KeyPress = NULL;
　　}
　　while(KeyPress!=ESC);
　　gettime(&endtime);
　　DispPlayTime();
　　WaitForKey(10);
　　clrscr();
　　ResetCur();
　　}
　　/* —— general sub process ———– */
　　int MainTimer(void)
　　/* output: how much 10ms have pass from last time call this process */
　　{
　　static int oldhund,oldsec;
　　struct time t;
　　int timeuse;
　　gettime(&t);
　　timeuse = 0;
　　if(t.ti_hund!=oldhund)
　　{
　　if(t.ti_sec!=oldsec)
　　{
　　timeuse+=100;
　　oldsec = t.ti_sec;
　　}
　　timeuse+=t.ti_hund-oldhund;
　　oldhund = t.ti_hund;
　　}
　　else timeuse = 0;
　　return (timeuse);
　　}
　　char WaitForKey(int secnum)
　　/* funtion: if have key in, exit immediately, else wait ’secnum’ senconds then exit
　　input: secnum — wait this senconds, must < 3600 (1 hour)
　　output: key char, if no key in(exit when timeout), return NULL */
　　{
　　int secin,secnow;
　　int minin,minnow;
　　int hourin,hournow;
　　int secuse;
　　struct time t;
　　gettime(&t);
　　secin = t.ti_sec;
　　minin = t.ti_min;
　　hourin = t.ti_hour;
　　do
　　{
　　if(kbhit()) return(getch());
　　gettime(&t);
　　secnow = t.ti_sec;
　　minnow = t.ti_min;
　　hournow = t.ti_hour;
　　if(hournow!=hourin) minnow+=60;
　　if(minnow>minin) secuse = (minnow-1-minin) + (secnow+60-secin);
　　else secuse = secnow - secin;
　　/* counting error check */
　　if(secuse<0)
　　{
　　gotoxy(1,MAXY+1);
　　printf(“Time conuting error, any keyto exit…”);
　　getch();
　　exit(3);
　　}
　　}
　　while(secuse<=secnum);
　　return (NULL);
　　}
　　void DispPlayTime(void)
　　{
　　int ph,pm,ps;
　　ph = endtime.ti_hour - starttime.ti_hour;
　　pm = endtime.ti_min - starttime.ti_min;
　　ps = endtime.ti_sec - starttime.ti_sec;
　　if(ph<0) ph+=24;
　　if(pm<0) { ph–; pm+=60; }
　　if(ps<0) { pm–; ps+=60; }
　　gotoxy(1,MAXY+1);
　　printf(“Time use: %d hour- %d min- %d sec “,ph,pm,ps);
　　}
　　int TimeUse(void)
　　{
　　int ph,pm,ps;
　　gettime(&endtime);
　　ph = endtime.ti_hour - starttime.ti_hour;
　　pm = endtime.ti_min - starttime.ti_min;
　　ps = endtime.ti_sec - starttime.ti_sec;
　　if(ph<0) ph+=24;
　　if(pm<0) { ph–; pm+=60; }
　　if(ps<0) { pm–; ps+=60; }
　　return(ps+(60*(pm+60*ph)));
　　}
　　void HideCur(void)
　　{
　　union REGS regs0;
　　regs0.h.ah=1;
　　regs0.h.ch=0×30;
　　regs0.h.cl=0×31;
　　int86(0×10,&regs0,&regs0);
　　}
　　void ResetCur(void)
　　{
　　union REGS regs0;
　　regs0.h.ah=1;
　　regs0.h.ch=0×06;
　　regs0.h.cl=0×07;
　　int86(0×10,&regs0,&regs0);
　　}
　　/* ———— main ANT programe ————- */
　　void WorldInitial(void)
　　{
　　int k,i,j;
　　randomize();
　　clrscr();
　　HomeFoodInitial();
　　for(AntNow=0;AntNow<MAX_ANT;AntNow++)
　　{
　　AntInitial();
　　} /* of for AntNow */;
　　BlockInitial();
　　for(k=0;k<=1;k++)
　　/* SMELL TYPE FOOD and HOME */
　　for(i=0;i<=MAXX;i++)
　　for(j=0;j<=MAXY;j++)
　　Smell[k][j] = 0;
　　SmellGoneTimer = 0;
　　gettime(&starttime);
　　SmellDispFlag = 0;
　　CanFindFood = 0;
　　HardtoFindPath = 0;
　　}
　　void BlockInitial(void)
　　{
　　int i,j;
　　int bn;
　　for(i=0;i<=MAXX;i++)
　　for(j=0;j<=MAXY;j++)
　　block[j] = 0;
　　bn = 1+ MAX_BLOCK/2 + random(MAX_BLOCK/2);
　　for(i=0;i<=bn;i++) CreatBlock();
　　}
　　void CreatBlock(void)
　　{
　　int x1,y1,x2,y2;
　　int dx,dy;
　　int i,j;
　　x1 = random(MAXX)+1;
　　y1 = random(MAXY)+1;
　　dx = random(MAXX/10)+1;
　　dy = random(MAXY/10)+1;
　　x2 = x1+dx;
　　y2 = y1+dy;
　　if(x2>MAXX) x2 = MAXX;
　　if(y2>MAXY) y2 = MAXY;
　　if(food.xxx>=x1&&food.xxx<=x2&&food.yyy>=y1&&food.yyy<=y2) return;
　　if(home.xxx>=x1&&home.xxx<=x2&&home.yyy>=y1&&home.yyy<=y2) return;
　　for(i=x1;i<=x2;i++)
　　for(j=y1;j<=y2;j++)
　　{
　　block[j] = 1;
　　gotoxy(i,j);
　　putch(BLOCK_CHAR);
　　}
　　}
　　void SaveBlock(void)
　　{
　　FILE *fp_block;
　　char FileNameBlock[20];
　　int i,j;
　　gotoxy(1,MAXY+1);
　　printf(” “);
　　gotoxy(1,MAXY+1);
　　printf(“Save to [font href="http://www.phpcup.cn/tag.php?name=file" onclick="tagshow(event)"]file[/font]…”,FileNameBlock);
　　gets(FileNameBlock);
　　if(FileNameBlock[0]==0) strcpy(FileNameBlock,“Ant.ant”);
　　else strcat(FileNameBlock,“.ant”);
　　if ((fp_block = fopen(FileNameBlock, “wb”)) == NULL)
　　{ gotoxy(1,MAXY+1);
　　printf(“Creat file %s fail…”,FileNameBlock);
　　getch();
　　exit(2);
　　}
　　gotoxy(1,MAXY+1);
　　printf(” “);
　　fputc(home.xxx,fp_block);
　　fputc(home.yyy,fp_block);
　　fputc(food.xxx,fp_block);
　　fputc(food.yyy,fp_block);
　　for(i=0;i<=MAXX;i++)
　　for(j=0;j<=MAXY;j++)
　　fputc(block[j],fp_block);
　　fclose(fp_block);
　　}
　　void LoadBlock(void)
　　{
　　FILE *fp_block;
　　char FileNameBlock[20];
　　int i,j,k;
　　gotoxy(1,MAXY+1);
　　printf(” “);
　　gotoxy(1,MAXY+1);
　　printf(“Load file…”,FileNameBlock);
　　gets(FileNameBlock);
　　if(FileNameBlock[0]==0) strcpy(FileNameBlock,“Ant.ant”);
　　else strcat(FileNameBlock,“.ant”);
　　if ((fp_block = fopen(FileNameBlock, “rb”)) == NULL)
　　{ gotoxy(1,MAXY+1);
　　printf(“Open file %s fail…”,FileNameBlock);
　　getch();
　　exit(2);
　　}
　　clrscr();
　　home.xxx = fgetc(fp_block);
　　home.yyy = fgetc(fp_block);
　　food.xxx = fgetc(fp_block);
　　food.yyy = fgetc(fp_block);
　　gotoxy(home.xxx,home.yyy); putch(HOME_CHAR);
　　gotoxy(food.xxx,food.yyy); putch(FOOD_CHAR);
　　food.amount = random(MAX_FOOD/3)+2*MAX_FOOD/3+1;
　　/* food.amount = MAX_FOOD; */
　　home.amount = 0;
　　home.TargetFood =
　　(food.amount<TARGET_FOOD)?food.amount:TARGET_FOOD;
　　for(AntNow=0;AntNow<MAX_ANT;AntNow++)
　　{
　　AntInitial();
　　} /* of for AntNow */;
　　for(i=0;i<=MAXX;i++)
　　for(j=0;j<=MAXY;j++)
　　{
　　block[j] = fgetc(fp_block);
　　if(block[j])
　　{
　　gotoxy(i,j);
　　putch(BLOCK_CHAR);
　　}
　　}
　　for(k=0;k<=1;k++)
　　/* SMELL TYPE FOOD and HOME */
　　for(i=0;i<=MAXX;i++)
　　for(j=0;j<=MAXY;j++)
　　Smell[k]<i id="bks_6wp7flgp">[j] = 0;
　　SmellGoneTimer = 0;
　　gettime(&starttime);
　　SmellDispFlag = 0;
　　CanFindFood = 0;
　　HardtoFindPath = 0;
　　fclose(fp_block);
　　}
　　void HomeFoodInitial(void)
　　{
　　int randnum;
　　int homeplace;
　　/* 1 — home at left-up, food at right-down
　　2 — home at left-down, food at right-up
　　3 — home at right-up, food at left-down
　　4 — home at right-down, food at left-up */
　　randnum = random(100);
　　if(randnum<25) homeplace = 1;
　　else if (randnum>=25&&randnum<50) homeplace = 2;
　　else if (randnum>=50&&randnum<75) homeplace = 3;
　　else homeplace = 4;
　　switch(homeplace)
　　{
　　case 1: home.xxx = random(MAXX/3)+1;
　　home.yyy = random(MAXY/3)+1;
　　food.xxx = random(MAXX/3)+2*MAXX/3+1;
　　food.yyy = random(MAXY/3)+2*MAXY/3+1;
　　break;
　　case 2: home.xxx = random(MAXX/3)+1;
　　home.yyy = random(MAXY/3)+2*MAXY/3+1;
　　food.xxx = random(MAXX/3)+2*MAXX/3+1;
　　food.yyy = random(MAXY/3)+1;
　　break;
　　case 3: home.xxx = random(MAXX/3)+2*MAXX/3+1;
　　home.yyy = random(MAXY/3)+1;
　　food.xxx = random(MAXX/3)+1;
　　food.yyy = random(MAXY/3)+2*MAXY/3+1;
　　break;
　　case 4: home.xxx = random(MAXX/3)+2*MAXX/3+1;
　　home.yyy = random(MAXY/3)+2*MAXY/3+1;
　　food.xxx = random(MAXX/3)+1;
　　food.yyy = random(MAXY/3)+1;
　　break;
　　}
　　food.amount = random(MAX_FOOD/3)+2*MAX_FOOD/3+1;
　　/* food.amount = MAX_FOOD; */
　　home.amount = 0;
　　home.TargetFood = (food.amount<TARGET_FOOD)?food.amount:TARGET_FOOD;
　　/* data correctness check */
　　if(home.xxx<=0||home.xxx>MAXX||home.yyy<=0||home.yyy>MAXY||
　　food.xxx<=0||food.xxx>MAXX||food.yyy<=0||food.yyy>MAXY||
　　food.amount<=0)
　　{
　　gotoxy(1,MAXY+1);
　　printf(“World initial fail, any key to exit…”);
　　getch();
　　exit(2);
　　}
　　gotoxy(home.xxx,home.yyy); putch(HOME_CHAR);
　　gotoxy(food.xxx,food.yyy); putch(FOOD_CHAR);
　　}
　　void AntInitial(void)
　　/* initial ant[AntNow] */
　　{
　　int randnum;
　　int i;
　　ant[AntNow].xxx = home.xxx;
　　ant[AntNow].yyy = home.yyy;
　　randnum = random(100);
　　if(randnum<25) ant[AntNow].dir = UP;
　　else if (randnum>=25&&randnum<50) ant[AntNow].dir = DOWN;
　　else if (randnum>=50&&randnum<75) ant[AntNow].dir = LEFT;
　　else ant[AntNow].dir = RIGHT;
　　ant[AntNow].speed = 2*(random(INI_SPEED/2)+1);
　　ant[AntNow].SpeedTimer = 0;
　　ant[AntNow].food = 0;
　　ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] = 0;
　　ant[AntNow].SmellAmount[SMELL_TYPE_HOME] = MAX_SMELL;
　　ant[AntNow].IQ = 1;

---------------------------------------------Matlab 源码-----------------------

% the procedure of ant colony algorithm for VRP

% % % % % % % % % % %

%initialize the parameters of ant colony algorithms

load data.txt;

d=data(:,2:3);

g=data(:,4);

m=31; % 蚂蚁数

alpha=1;

belta=4;% 决定tao和miu重要性的参数

lmda=0;

rou=0.9; %衰减系数

q0=0.95;

% 概率

tao0=1/(31*841.04);%初始信息素

Q=1;% 蚂蚁循环一周所释放的信息素

defined_phrm=15.0; % initial pheromone level value

QV=100; % 车辆容量

vehicle_best=round(sum(g)/QV)+1; %所完成任务所需的最少车数

V=40;

% 计算两点的距离

for i=1:32;

for j=1:32;

dist(i,j)=sqrt((d(i,1)-d(j,1))^2+(d(i,2)-d(j,2))^2);

end;

%给tao miu赋初值

for i=1:32;

for j=1:32;

if i~=j;

%s(i,j)=dist(i,1)+dist(1,j)-dist(i,j);

tao(i,j)=defined_phrm;

miu(i,j)=1/dist(i,j);

end;

for k=1:32;

deltao(i,j)=0;

end;

best_cost=10000;

for n_gen=1:50;

print_head(n_gen);

for i=1:m;

%best_solution=[];

print_head2(i);

sumload=0;

cur_pos(i)=1;

rn=randperm(32);

n=1;

nn=1;

part_sol(nn)=1;

%cost(n_gen,i)=0.0;

n_sol=0; % 由蚂蚁产生的路径数量

M_vehicle=500;

t=0; %最佳路径数组的元素数为0

while sumload<=QV;

for k=1:length(rn);

if sumload+g(rn(k))<=QV;

gama(cur_pos(i),rn(k))=(sumload+g(rn(k)))/QV;

A(n)=rn(k);

n=n+1;

end;

fid=fopen('out_customer.txt','a+');

fprintf(fid,'%s %i\t','the current position is:',cur_pos(i));

fprintf(fid,'\n%s','the possible customer set is:')

fprintf(fid,'\t%i\n',A);

fprintf(fid,'------------------------------\n');

fclose(fid);

p=compute_prob(A,cur_pos(i),tao,miu,alpha,belta,gama,lmda,i);

maxp=1e-8;

na=length(A);

for j=1:na;

if p(j)>maxp

maxp=p(j);

index_max=j;

end;

old_pos=cur_pos(i);

if rand(1)<q0

cur_pos(i)=A(index_max);

else

krnd=randperm(na);

cur_pos(i)=A(krnd(1));

bbb=[old_pos cur_pos(i)];

ccc=[1 1];

if bbb==ccc;

cur_pos(i)=A(krnd(2));

end;

tao(old_pos,cur_pos(i))=taolocalupdate(tao(old_pos,cur_pos(i)),rou,tao0);%对所经弧进行局部更新

sumload=sumload+g(cur_pos(i));

nn=nn+1;

part_sol(nn)=cur_pos(i);

temp_load=sumload;

if cur_pos(i)~=1;

rn=setdiff(rn,cur_pos(i));

n=1;

A=[];

end;

if cur_pos(i)==1; % 如果当前点为车场,将当前路径中的已访问用户去掉后,开始产生新路径

if setdiff(part_sol,1)~=[];

n_sol=n_sol+1; % 表示产生的路径数,n_sol=1,2,3,..5,6...,超过5条对其费用加上车辆的派遣费用

fid=fopen('out_solution.txt','a+');

fprintf(fid,'%s%i%s','NO.',n_sol,'条路径是:');

fprintf(fid,'%i ',part_sol);

fprintf(fid,'\n');

fprintf(fid,'%s','当前的用户需求量是:');

fprintf(fid,'%i\n',temp_load);

fprintf(fid,'------------------------------\n');

fclose(fid);

% 对所得路径进行路径内3-opt优化

final_sol=exchange(part_sol);

for nt=1:length(final_sol); % 将所有产生的路径传给一个数组

temp(t+nt)=final_sol(nt);

end;

t=t+length(final_sol)-1;

sumload=0;

final_sol=setdiff(final_sol,1);

rn=setdiff(rn,final_sol);

part_sol=[];

final_sol=[];

nn=1;

part_sol(nn)=cur_pos(i);

A=[];

n=1;

end;

if setdiff(rn,1)==[];% 产生最后一条终点不为1的路径

n_sol=n_sol+1;

nl=length(part_sol);

part_sol(nl+1)=1;%将路径的最后1位补1

% 对所得路径进行路径内3-opt优化

final_sol=exchange(part_sol);

for nt=1:length(final_sol); % 将所有产生的路径传给一个数组

temp(t+nt)=final_sol(nt);

end;

cost(n_gen,i)=cost_sol(temp,dist)+M_vehicle*(n_sol-vehicle_best); %计算由蚂蚁i产生的路径总长度

for ki=1:length(temp)-1;

deltao(temp(ki),temp(ki+1))=deltao(temp(ki),temp(ki+1))+Q/cost(n_gen,i);

end;

if cost(n_gen,i)<best_cost;

best_cost=cost(n_gen,i);

old_cost=best_cost;

best_gen=n_gen; % 产生最小费用的代数

best_ant=i; %产生最小费用的蚂蚁

best_solution=temp;

end;

if i==m; %如果所有蚂蚁均完成一次循环，，则用最佳费用所对应的路径对弧进行整体更新

for ii=1:32;

for jj=1:32;

tao(ii,jj)=(1-rou)*tao(ii,jj);

end;

for kk=1:length(best_solution)-1;

tao(best_solution(kk),best_solution(kk+1))=tao(best_solution(kk),best_solution(kk+1))+deltao(best_solution(kk),best_solution(kk+1));

end;

fid=fopen('out_solution.txt','a+');

fprintf(fid,'%s%i%s','NO.',n_sol,'路径是:');

fprintf(fid,'%i ',part_sol);

fprintf(fid,'\n');

fprintf(fid,'%s %i\n','当前的用户需求量是:',temp_load);

fprintf(fid,'%s %f\n','总费用是:',cost(n_gen,i));

fprintf(fid,'------------------------------\n');

fprintf(fid,'%s\n','最终路径是:');

fprintf(fid,'%i-',temp);

fprintf(fid,'\n');

fclose(fid);

temp=[];

break;

end;

----------------------------------------------Js 源码--------------------------------------

人工生命—群集智能—蚁群算法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 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 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"></div> <div id="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 style="left:'+xi0+';top:'+yi0+';"></div>'; // str='<div 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 style="left:'+X+';top:'+Y+';"></div>'; // str='<div 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 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 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 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 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"></div> <div id="nest"></div> </body> </html>
[Ctrl+A 全部选择提示：你可先修改部分代码，再按运行]

顺便说下这里用到了join函数来连接坐标字符串数组从而达到降低时间复杂度的目的。http://hi.baidu.com/aqaq82/blog/item/7d755d1685b40159f3de32a2.html

固定链接: 蚁群算法原理和源码 | 丕子 +复制链接