蚁群算法的原理以及实现源代码.docx
- 文档编号:6354261
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:42
- 大小:25.45KB
蚁群算法的原理以及实现源代码.docx
《蚁群算法的原理以及实现源代码.docx》由会员分享,可在线阅读,更多相关《蚁群算法的原理以及实现源代码.docx(42页珍藏版)》请在冰点文库上搜索。
蚁群算法的原理以及实现源代码
蚁群算法ACO(antcolonyoptimization)的原理以及实现源代码
ByMinidxer|February1,2008
之前说的算法基本上都比较枯燥的(废话,算法都很枯燥……),这次要介绍的蚁群算法(AntColonyAlgorithm)却是一种源于自然现象的算法,也是一种metaheuristic,即与具体问题关系不大的优化算法,也就是它是一种用来在图中寻找优化路径的机率型技术。
MarcoDorigo于1992年在他的博士论文中引入,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
小小的蚂蚁总是能够找到食物,他们具有什么样的智能呢?
设想,如果我们要为蚂蚁设计一个人工智能的程序,那么这个程序要多么复杂呢?
首先,你要让蚂蚁能够避开障碍物,就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物,其次,要让蚂蚁找到食物,就需要让他们遍历空间上的所有点;再次,如果要让蚂蚁找到最短的路径,那么需要计算所有可能的路径并且比较它们的大小,而且更重要的是,你要小心翼翼的编程,因为程序的错误也许会让你前功尽弃。
这是多么不可思议的程序!
太复杂了,恐怕没人能够完成这样繁琐冗余的程序。
为什么这么简单的程序会让蚂蚁干这样复杂的事情?
答案是:
简单规则的涌现。
事实上,每只蚂蚁并不是像我们想象的需要知道整个世界的信息,他们其实只关心很小范围内的眼前信息,而且根据这些局部信息利用几条简单的规则进行决策,这样,在蚁群这个集体里,复杂性的行为就会凸现出来。
这就是人工生命、复杂性科学解释的规律!
下面就是实现如此复杂性的七条简单规则:
1、范围:
蚂蚁观察到的范围是一个方格世界,蚂蚁有一个参数为速度半径(一般是3),那么它能观察到的范围就是3*3个方格世界,并且能移动的距离也在这个范围之内。
2、环境:
蚂蚁所在的环境是一个虚拟的世界,其中有障碍物,有别的蚂蚁,还有信息素,信息素有两种,一种是找到食物的蚂蚁洒下的食物信息素,一种是找到窝的蚂蚁洒下的窝的信息素。
每个蚂蚁都仅仅能感知它范围内的环境信息。
环境以一定的速率让信息素消失。
3、觅食规则:
在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接过去。
否则看是否有信息素,并且比较在能感知的范围内哪一点的信息素最多,这样,它就朝信息素多的地方走,并且每只蚂蚁多会以小概率犯错误,从而并不是往信息素最多的点移动。
蚂蚁找窝的规则和上面一样,只不过它对窝的信息素做出反应,而对食物信息素没反应。
4、移动规则:
每只蚂蚁都朝向信息素最多的方向移,并且,当周围没有信息素指引的时候,蚂蚁会按照自己原来运动的方向惯性的运动下去,并且,在运动的方向有一个随机的小的扰动。
为了防止蚂蚁原地转圈,它会记住最近刚走过了哪些点,如果发现要走的下一点已经在最近走过了,它就会尽量避开。
5、避障规则:
如果蚂蚁要移动的方向有障碍物挡住,它会随机的选择另一个方向,并且有信息素指引的话,它会按照觅食的规则行为。
7、播撒信息素规则:
每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多,并随着它走远的距离,播撒的信息素越来越少。
下面的程序开始运行之后,蚂蚁们开始从窝里出动了,寻找食物;他们会顺着屏幕爬满整个画面,直到找到食物再返回窝。
其中,‘F’点表示食物,‘H’表示窝,白色块表示障碍物,‘+’就是蚂蚁了。
参数说明:
最大信息素:
蚂蚁在一开始拥有的信息素总量,越大表示程序在较长一段时间能够存在信息素。
信息素消减的速度:
随着时间的流逝,已经存在于世界上的信息素会消减,这个数值越大,那么消减的越快。
错误概率表示这个蚂蚁不往信息素最大的区域走的概率,越大则表示这个蚂蚁越有创新性。
速度半径表示蚂蚁一次能走的最大长度,也表示这个蚂蚁的感知范围。
记忆能力表示蚂蚁能记住多少个刚刚走过点的坐标,这个值避免了蚂蚁在本地打转,停滞不前。
而这个值越大那么整个系统运行速度就慢,越小则蚂蚁越容易原地转圈。
源代码如下(不同编译器可能需做一定修改):
/*ant.c*/
#defineSPACE0x20
#defineESC0x1b
#defineANT_CHAR_EMPTY'+'
#defineANT_CHAR_FOOD153
#defineHOME_CHAR'H'
#defineFOOD_CHAR'F'
#defineFOOD_CHAR2'f'
#defineFOOD_HOME_COLOR12
#defineBLOCK_CHAR177
#defineMAX_ANT50
#defineINI_SPEED3
#defineMAXX80
#defineMAXY23
#defineMAX_FOOD10000
#defineTARGET_FOOD200
#defineMAX_SMELL5000
#defineSMELL_DROP_RATE0.05
#defineANT_ERROR_RATE0.02
#defineANT_EYESHOT3
#defineSMELL_GONE_SPEED50
#defineSMELL_GONE_RATE0.05
#defineTRACE_REMEMBER50
#defineMAX_BLOCK100
#defineNULL0
#defineUP1
#defineDOWN2
#defineLEFT3
#defineRIGHT4
#defineSMELL_TYPE_FOOD0
#defineSMELL_TYPE_HOME1
#include"stdio.h"
#include"conio.h"
#include"dos.h"
#include"stdlib.h"
#include"dos.h"
#include"process.h"
#include"ctype.h"
#include"math.h"
voidWorldInitial(void);
voidBlockInitial(void);
voidCreatBlock(void);
voidSaveBlock(void);
voidLoadBlock(void);
voidHomeFoodInitial(void);
voidAntInitial(void);
voidWorldChange(void);
voidAntMove(void);
voidAntOneStep(void);
voidDealKey(charkey);
voidClearSmellDisp(void);
voidDispSmell(inttype);
intAntNextDir(intxxx,intyyy,intddir);
intGetMaxSmell(inttype,intxxx,intyyy,intddir);
intIsTrace(intxxx,intyyy);
intMaxLocation(intnum1,intnum2,intnum3);
intCanGo(intxxx,intyyy,intddir);
intJudgeCanGo(intxxx,intyyy);
intTurnLeft(intddir);
intTurnRight(intddir);
intTurnBack(intddir);
intMainTimer(void);
charWaitForKey(intsecnum);
voidDispPlayTime(void);
intTimeUse(void);
voidHideCur(void);
voidResetCur(void);
/*---------------*/
structHomeStruct
{
intxxx,yyy;
intamount;
intTargetFood;
}home;
structFoodStruct
{
intxxx,yyy;
intamount;
}food;
structAntStruct
{
intxxx,yyy;
intdir;
intspeed;
intSpeedTimer;
intfood;
intSmellAmount[2];
inttracex[TRACE_REMEMBER];
inttracey[TRACE_REMEMBER];
intTracePtr;
intIQ;
}ant[MAX_ANT];
intAntNow;
inttimer10ms;
structtimestarttime,endtime;
intSmell[2][MAXX+1][MAXY+1];
intblock[MAXX+1][MAXY+1];
intSmellGoneTimer;
intSmellDispFlag;
intCanFindFood;
intHardtoFindPath;
/*-----Main--------*/
voidmain(void)
{
charKeyPress;
inttu;
clrscr();
HideCur();
WorldInitial();
do
{
timer10ms=MainTimer();
if(timer10ms)AntMove();
if(timer10ms)WorldChange();
tu=TimeUse();
if(tu>=60&&!
CanFindFood)
{
gotoxy(1,MAXY+1);
printf("Cannotfindfood,maybeablockworld.");
WaitForKey(10);
WorldInitial();
}
if(tu>=180&&home.amount<100&&!
HardtoFindPath)
{
gotoxy(1,MAXY+1);
printf("God!
itissodifficulttofindapath.");
if(WaitForKey(10)==0x0d)WorldInitial();
else
{
HardtoFindPath=1;
gotoxy(1,MAXY+1);
printf("");
}
}
if(home.amount>=home.TargetFood)
{
gettime(&endtime);
KeyPress=WaitForKey(60);
DispPlayTime();
WaitForKey(10);
WorldInitial();
}
elseif(kbhit())
{
KeyPress=getch();
DealKey(KeyPress);
}
elseKeyPress=NULL;
}
while(KeyPress!
=ESC);
gettime(&endtime);
DispPlayTime();
WaitForKey(10);
clrscr();
ResetCur();
}
/*------generalsubprocess-----------*/
intMainTimer(void)
/*output:
howmuch10mshavepassfromlasttimecallthisprocess*/
{
staticintoldhund,oldsec;
structtimet;
inttimeuse;
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;
}
elsetimeuse=0;
return(timeuse);
}
charWaitForKey(intsecnum)
/*funtion:
ifhavekeyin,exitimmediately,elsewait'secnum'sencondsthenexit
input:
secnum--waitthissenconds,must<3600(1hour)
output:
keychar,ifnokeyin(exitwhentimeout),returnNULL*/
{
intsecin,secnow;
intminin,minnow;
inthourin,hournow;
intsecuse;
structtimet;
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);
elsesecuse=secnow-secin;
/*countingerrorcheck*/
if(secuse<0)
{
gotoxy(1,MAXY+1);
printf("Timeconutingerror,anykeytoexit...");
getch();
exit(3);
}
}
while(secuse<=secnum);
return(NULL);
}
voidDispPlayTime(void)
{
intph,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("Timeuse:
%dhour-%dmin-%dsec",ph,pm,ps);
}
intTimeUse(void)
{
intph,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)));
}
voidHideCur(void)
{
unionREGSregs0;
regs0.h.ah=1;
regs0.h.ch=0x30;
regs0.h.cl=0x31;
int86(0x10,®s0,®s0);
}
voidResetCur(void)
{
unionREGSregs0;
regs0.h.ah=1;
regs0.h.ch=0x06;
regs0.h.cl=0x07;
int86(0x10,®s0,®s0);
}
/*------------mainANTprograme-------------*/
voidWorldInitial(void)
{
intk,i,j;
randomize();
clrscr();
HomeFoodInitial();
for(AntNow=0;AntNow { AntInitial(); }/*offorAntNow*/; BlockInitial(); for(k=0;k<=1;k++) /*SMELLTYPEFOODandHOME*/ for(i=0;i<=MAXX;i++) for(j=0;j<=MAXY;j++) Smell[k][i][j]=0; SmellGoneTimer=0; gettime(&starttime); SmellDispFlag=0; CanFindFood=0; HardtoFindPath=0; } voidBlockInitial(void) { inti,j; intbn; for(i=0;i<=MAXX;i++) for(j=0;j<=MAXY;j++) block[i][j]=0; bn=1+MAX_BLOCK/2+random(MAX_BLOCK/2); for(i=0;i<=bn;i++)CreatBlock(); } voidCreatBlock(void) { intx1,y1,x2,y2; intdx,dy; inti,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[i][j]=1; gotoxy(i,j); putch(BLOCK_CHAR); } } voidSaveBlock(void) { FILE*fp_block; charFileNameBlock[20]; inti,j; gotoxy(1,MAXY+1); printf(""); gotoxy(1,MAXY+1); printf("Savetofile...",FileNameBlock); gets(FileNameBlock); if(FileNameBlock[0]==0)strcpy(FileNameBlock,"Ant.ant"); elsestrcat(FileNameBlock,".ant"); if((fp_block=fopen(FileNameBlock,"wb"))==NULL) {gotoxy(1,MAXY+1); printf("Creatfile%sfail...",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[i][j],fp_block); fclose(fp_block); } voidLoadBlock(void) { FILE*fp_block; charFileNameBlock[20]; inti,j,k; gotoxy(1,MAXY+1); printf(""); gotoxy(1,MAXY+1); printf("Loadfile...",FileNameBlock); gets(FileNameBlock); if(FileNameBlock[0]==0)strcpy(FileNameBlock,"Ant.ant"); elsestrcat(FileNameBlock,".ant"); if((fp_block=fopen(FileNameBlock,"rb"))==NULL) {gotoxy(1,MAXY+1); printf("Openfile%sfail...",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 food.amount: TARGET_FOOD; for(AntNow=0;AntNow { AntInitial(); }/*offorAntNow*/; for(i=0;i<=MAXX;i++) for(j=0;j<=MAXY;j++) { block[i][j]=fgetc(fp_block); if(block[i][j]) { gotoxy(i,j); putch(BLOCK
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 原理 以及 实现 源代码
![提示](https://static.bingdoc.com/images/bang_tan.gif)