蚁群算法的原理以及实现源代码

1、蚁群算法ACO(ant colony optimization)的原理以及实现源代码 By Minidxer | February 1, 2008 之前说的算法基本上都比较枯燥的（废话，算法都很枯燥），这次要介绍的蚁群算法(Ant Colony Algorithm)却是一种源于自然现象的算法，也是一种 meta heuristic，即与具体问题关系不大的优化算法，也就是它是一种用来在图中寻找优化路径的机率型技术。Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。小小的蚂蚁总是能够找到食物，他们具有什么样的智能呢？设想，如果我们要为蚂蚁设计

2、一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼的编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序。 为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息

3、利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！下面就是实现如此复杂性的七条简单规则：1、范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。2、环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。3、觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物

4、，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。4、移动规则： 每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。5、避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向

5、，并且有信息素指引的话，它会按照觅食的规则行为。 7、播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。 下面的程序开始运行之后，蚂蚁们开始从窝里出动了，寻找食物；他们会顺着屏幕爬满整个画面，直到找到食物再返回窝。 其中，F点表示食物，H表示窝，白色块表示障碍物，+就是蚂蚁了。 参数说明：最大信息素：蚂蚁在一开始拥有的信息素总量，越大表示程序在较长一段时间能够存在信息素。信息素消减的速度：随着时间的流逝，已经存在于世界上的信息素会消减，这个数值越大，那么消减的越快。错误概率表示这个蚂蚁不往信息素最大的区域走的概率，越大则表示这个蚂蚁越有

6、创新性。速度半径表示蚂蚁一次能走的最大长度，也表示这个蚂蚁的感知范围。记忆能力表示蚂蚁能记住多少个刚刚走过点的坐标，这个值避免了蚂蚁在本地打转，停滞不前。而这个值越大那么整个系统运行速度就慢，越小则蚂蚁越容易原地转圈。 源代码如下(不同编译器可能需做一定修改)：/*ant.c*/#define SPACE 0x20#define ESC 0x1b#define ANT_CHAR_EMPTY +#define ANT_CHAR_FOOD 153#define HOME_CHAR H#define FOOD_CHAR F#define FOOD_CHAR2 f#define FOOD_HOME_C

7、OLOR 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#defin

8、e 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.hvoid WorldIniti

9、al(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(i

10、nt 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

11、(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; i

12、nt food; int SmellAmount2; int tracexTRACE_REMEMBER; int traceyTRACE_REMEMBER; int TracePtr; int IQ;antMAX_ANT;int AntNow;int timer10ms;struct time starttime,endtime;int Smell2MAXX+1MAXY+1;int blockMAXX+1MAXY+1;int SmellGoneTimer;int SmellDispFlag;int CanFindFood;int HardtoFindPath;/* - Main - */voi

13、d 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=1

14、80&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();/*

15、- 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

16、; 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 minin) secuse = (minnow-1-minin) + (secnow+60-secin); else secuse = secnow - secin; /* count

17、ing error check */ if(secuse0) 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

18、.ti_sec; if(ph0) ph+=24; if(pm0) ph-; pm+=60; if(ps0) 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 - starttim

19、e.ti_sec; if(ph0) ph+=24; if(pm0) ph-; pm+=60; if(ps0) pm-; ps+=60; return(ps+(60*(pm+60*ph);void HideCur(void) union REGS regs0; regs0.h.ah=1; regs0.h.ch=0x30; regs0.h.cl=0x31; int86(0x10,®s0,®s0);void ResetCur(void) union REGS regs0; regs0.h.ah=1; regs0.h.ch=0x06; regs0.h.cl=0x07; int86(0x10

20、,®s0,®s0);/* - main ANT programe - */void WorldInitial(void) int k,i,j; randomize(); clrscr(); HomeFoodInitial(); for(AntNow=0;AntNowMAX_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+) Smellkij

21、 = 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+) blockij = 0; bn = 1+ MAX_BLOCK/2 + random(MAX_BLOCK/2); for(i=0;iMAXX) x2 = MAXX; if(y2MAXY) y2 = MAXY; if(food.xxx=x1&

22、food.xxx=y1&food.yyy=x1&home.xxx=y1&home.yyy=y2) return; for(i=x1;i=x2;i+) for(j=y1;j=y2;j+) blockij = 1; gotoxy(i,j); putch(BLOCK_CHAR); void SaveBlock(void) FILE *fp_block; char FileNameBlock20; int i,j; gotoxy(1,MAXY+1); printf( ); gotoxy(1,MAXY+1); printf(Save to file.,FileNameBlock); gets(FileN

23、ameBlock); if(FileNameBlock0=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_bloc

24、k); fputc(food.xxx,fp_block); fputc(food.yyy,fp_block); for(i=0;i=MAXX;i+) for(j=0;j=MAXY;j+) fputc(blockij,fp_block); fclose(fp_block);void LoadBlock(void) FILE *fp_block; char FileNameBlock20; int i,j,k; gotoxy(1,MAXY+1); printf( ); gotoxy(1,MAXY+1); printf(Load file.,FileNameBlock); gets(FileName

25、Block); if(FileNameBlock0=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 = fget

26、c(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.amountTARGET_FOOD)?food.amount:TARGET_FOOD; for(A

27、ntNow=0;AntNowMAX_ANT;AntNow+) AntInitial(); /* of for AntNow */; for(i=0;i=MAXX;i+) for(j=0;j=MAXY;j+) blockij = fgetc(fp_block); if(blockij) 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+) Smellkij = 0; SmellGoneTimer = 0; gettim

28、e(&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 le

29、ft-up */ randnum = random(100); if(randnum=25&randnum=50&randnum75) 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

30、/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

31、)+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.amountTARGET_FOOD)?food.amount:TARGET_FOOD; /* data correctness

32、 check */ if(home.xxxMAXX|home.yyyMAXY| food.xxxMAXX|food.yyyMAXY| 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 antAntNow */ in

33、t randnum; int i; antAntNow.xxx = home.xxx; antAntNow.yyy = home.yyy; randnum = random(100); if(randnum=25&randnum=50&randnum75) antAntNow.dir = LEFT; else antAntNow.dir = RIGHT; antAntNow.speed = 2*(random(INI_SPEED/2)+1); antAntNow.SpeedTimer = 0; antAntNow.food = 0; antAntNow.SmellAmountSMELL_TYP

34、E_FOOD = 0; antAntNow.SmellAmountSMELL_TYPE_HOME = MAX_SMELL; antAntNow.IQ = 1; for(i=0;i=SMELL_GONE_SPEED) SmellGoneTimer = 0; for(k=0;k=1;k+) /* SMELL TYPE FOOD and HOME */ for(i=1;i=MAXX;i+) for(j=1;j=30000|smelldisp9) putch(#); else putch(smelldisp+0); Smellkij-= 1+(Smellkij*SMELL_GONE_RATE); if

35、(Smellkij0) Smellkij = 0; if(SmellDispFlag) if(Smellkij=2) gotoxy(i,j); putch(SPACE); /* of one location */ /* of time to change the world */ /* of world change */void AntMove(void) int antx,anty; int smelltodrop,smellnow; for(AntNow=0;AntNow=antAntNow.speed) antAntNow.SpeedTimer = 0; gotoxy(antAntN

36、ow.xxx,antAntNow.yyy); putch(SPACE); AntOneStep(); gotoxy(antAntNow.xxx,antAntNow.yyy); /* ant0 is a sepecail ant, use different color */ if(AntNow=0) textcolor(0xd); if(antAntNow.food) putch(ANT_CHAR_FOOD); else putch(ANT_CHAR_EMPTY); if(AntNow=0) textcolor(0x7); /* remember trace */ antAntNow.trac

37、exantAntNow.TracePtr = antAntNow.xxx; antAntNow.traceyantAntNow.TracePtr = antAntNow.yyy; if(+(antAntNow.TracePtr)=TRACE_REMEMBER) antAntNow.TracePtr = 0; /* drop smell */ antx = antAntNow.xxx; anty = antAntNow.yyy; if(antAntNow.food) /* have food, looking for home */ if(antAntNow.SmellAmountSMELL_T

38、YPE_FOOD) smellnow = SmellSMELL_TYPE_FOODantxanty; smelltodrop = antAntNow.SmellAmountSMELL_TYPE_FOOD*SMELL_DROP_RATE; if(smelltodropsmellnow) SmellSMELL_TYPE_FOODantxanty = smelltodrop; /* else Smell. = smellnow */ antAntNow.SmellAmountSMELL_TYPE_FOOD-= smelltodrop; if(antAntNow.SmellAmountSMELL_TY

39、PE_FOODsmellnow) SmellSMELL_TYPE_HOMEantxanty = smelltodrop; /* else Smell. = smellnow */ antAntNow.SmellAmountSMELL_TYPE_HOME-= smelltodrop; if(antAntNow.SmellAmountSMELL_TYPE_HOME0) putch(FOOD_CHAR); else putch(FOOD_CHAR2); textcolor(7); gotoxy(1,MAXY+1); printf(Food %d, Home %d ,food.amount,home.

40、amount);void AntOneStep(void) int ddir,tttx,ttty; int i; ddir = antAntNow.dir; tttx = antAntNow.xxx; ttty = antAntNow.yyy; ddir = AntNextDir(tttx,ttty,ddir); switch(ddir) case UP: ttty-; break; case DOWN: ttty+; break; case LEFT: tttx-; break; case RIGHT: tttx+; break; default: break; /* of switch dir */ antAntNow.dir = ddir; antAntNow.xxx = tttx; antAntNow.yyy = ttty; if(antAntNow.food) /* this ant carry with food,