| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛 | 
登录
注册
用户控制面板
搜索
道具
风格
短消息
论坛展区
帮助
编程论坛 → 开发语言 → 『 C语言论坛 』 → [求助]算法注释
我的收件箱(0)
欢迎加入我们，一同切磋技术
用户名：   
 
密　码：  
共有 570 人关注过本帖
标题：[求助]算法注释
只看楼主 加入收藏
xiazhi123456
Rank: 1
等　级：新手上路
帖　子：9
专家分：0
注　册：2007-6-30
楼主
收藏
 问题点数：0 回复次数：5 
[求助]算法注释

跪求高手给注释一下下面蚁群算法的代码，不甚感激！

#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_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)==0x0d) 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=0x30;
regs0.h.cl=0x31;
int86(0x10,&regs0,&regs0);
}

void ResetCur(void)
{
union REGS regs0;
regs0.h.ah=1;
regs0.h.ch=0x06;
regs0.h.cl=0x07;
int86(0x10,&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][i][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[i][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[i][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 file...",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[i][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[i][j] = fgetc(fp_block);
if(block[i][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][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;

for(i=0;i<TRACE_REMEMBER;i++)
{
ant[AntNow].tracex[i] = 0;
ant[AntNow].tracey[i] = 0;
}
ant[AntNow].TracePtr = 0;

/* a sepecail ant */
if(AntNow==0) ant[AntNow].speed = INI_SPEED;
}

void WorldChange(void)
{
int k,i,j;
int smelldisp;

SmellGoneTimer+=timer10ms;
if(SmellGoneTimer>=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<=MAXY;j++)
{
if(Smell[k][i][j])
{
smelldisp = 1+((10*Smell[k][i][j])/(MAX_SMELL*SMELL_DROP_RATE));
if(smelldisp>=30000||smelldisp<0) smelldisp = 30000;
if(SmellDispFlag)
{
gotoxy(i,j);
if((i==food.xxx&&j==food.yyy)||(i==home.xxx&&j==home.yyy))
/* don't over write Food and Home */;
else
{
if(smelldisp>9) putch('#');
else putch(smelldisp+'0');
}
}
Smell[k][i][j]-= 1+(Smell[k][i][j]*SMELL_GONE_RATE);
if(Smell[k][i][j]<0) Smell[k][i][j] = 0;
if(SmellDispFlag)
{
if(Smell[k][i][j]<=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<MAX_ANT;AntNow++)
{
ant[AntNow].SpeedTimer+=timer10ms;
if(ant[AntNow].SpeedTimer>=ant[AntNow].speed)
{
ant[AntNow].SpeedTimer = 0;
gotoxy(ant[AntNow].xxx,ant[AntNow].yyy);
putch(SPACE);
AntOneStep();
gotoxy(ant[AntNow].xxx,ant[AntNow].yyy);
/* ant0 is a sepecail ant, use different color */
if(AntNow==0) textcolor(0xd);
if(ant[AntNow].food) putch(ANT_CHAR_FOOD);
else putch(ANT_CHAR_EMPTY);
if(AntNow==0) textcolor(0x7);

/* remember trace */
ant[AntNow].tracex[ant[AntNow].TracePtr] = ant[AntNow].xxx;
ant[AntNow].tracey[ant[AntNow].TracePtr] = ant[AntNow].yyy;
if(++(ant[AntNow].TracePtr)>=TRACE_REMEMBER) ant[AntNow].TracePtr = 0;

/* drop smell */
antx = ant[AntNow].xxx;
anty = ant[AntNow].yyy;

if(ant[AntNow].food)
/* have food, looking for home */
{
if(ant[AntNow].SmellAmount[SMELL_TYPE_FOOD])
{
smellnow = Smell[SMELL_TYPE_FOOD][antx][anty];
smelltodrop = ant[AntNow].SmellAmount[SMELL_TYPE_FOOD]*SMELL_DROP_RATE;
if(smelltodrop>smellnow) Smell[SMELL_TYPE_FOOD][antx][anty] = smelltodrop;
/* else Smell[...] = smellnow */
ant[AntNow].SmellAmount[SMELL_TYPE_FOOD]-= smelltodrop;
if(ant[AntNow].SmellAmount[SMELL_TYPE_FOOD]<0) ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] = 0;
} /* of have smell to drop */
} /* of have food */
else
/* no food, looking for food */
{
if(ant[AntNow].SmellAmount[SMELL_TYPE_HOME])
{
smellnow = Smell[SMELL_TYPE_HOME][antx][anty];
smelltodrop = ant[AntNow].SmellAmount[SMELL_TYPE_HOME]*SMELL_DROP_RATE;
if(smelltodrop>smellnow) Smell[SMELL_TYPE_HOME][antx][anty] = smelltodrop;
/* else Smell[...] = smellnow */
ant[AntNow].SmellAmount[SMELL_TYPE_HOME]-= smelltodrop;
if(ant[AntNow].SmellAmount[SMELL_TYPE_HOME]<0) ant[AntNow].SmellAmount[SMELL_TYPE_HOME] = 0;
} /* of have smell to drop */
}
} /* of time to go */
/* else not go */
} /* of for AntNow */

textcolor(FOOD_HOME_COLOR);
gotoxy(home.xxx,home.yyy); putch(HOME_CHAR);
gotoxy(food.xxx,food.yyy);
if(food.amount>0) putch(FOOD_CHAR);
else putch(FOOD_CHAR2);
textcolor(7);

gotoxy(1,MAXY+1);
printf("Food %d, Home %d ",food.amount,home.amount);
}

void AntOneStep(void)
{
int ddir,tttx,ttty;
int i;

ddir = ant[AntNow].dir;
tttx = ant[AntNow].xxx;
ttty = ant[AntNow].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 */

ant[AntNow].dir = ddir;
ant[AntNow].xxx = tttx;
ant[AntNow].yyy = ttty;

if(ant[AntNow].food)
/* this ant carry with food, search for home */
{
if(tttx==home.xxx&&ttty==home.yyy)
{
home.amount++;
AntInitial();
}
if(tttx==food.xxx&&ttty==food.yyy)
ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] = MAX_SMELL;
} /* of search for home */
else
/* this ant is empty, search for food */
{
if(tttx==food.xxx&&ttty==food.yyy)
{
if(food.amount>0)
{
ant[AntNow].food = 1;
food.amount--;
ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] = MAX_SMELL;
ant[AntNow].SmellAmount[SMELL_TYPE_HOME] = 0;
ant[AntNow].dir = TurnBack(ant[AntNow].dir);
for(i=0;i<TRACE_REMEMBER;i++)
{
ant[AntNow].tracex[i] = 0;
ant[AntNow].tracey[i] = 0;
}
ant[AntNow].TracePtr = 0;
CanFindFood = 1;
} /* of still have food */
}
if(tttx==home.xxx&&ttty==home.yyy)
ant[AntNow].SmellAmount[SMELL_TYPE_HOME] = MAX_SMELL;
} /* of search for food */
}

void DealKey(char key)
{
int i;
switch(key)
{
case 'p': gettime(&endtime);
DispPlayTime();
getch();
gotoxy(1,MAXY+1);
for(i=1;i<=MAXX-1;i++) putch(SPACE);
break;
case 't': if(SmellDispFlag)
{
SmellDispFlag=0;
ClearSmellDisp();
}
else SmellDispFlag = 1;
break;
case '1': DispSmell(SMELL_TYPE_FOOD);
getch();
ClearSmellDisp();
break;
case '2': DispSmell(SMELL_TYPE_HOME);
getch();
ClearSmellDisp();
break;
case '3': DispSmell(2);
getch();
ClearSmellDisp();
break;
case 's': SaveBlock();
break;
case 'l': LoadBlock();
break;
default: gotoxy(1,MAXY+1);
for(i=1;i<=MAXX-1;i++) putch(SPACE);
} /* of switch */
}

void ClearSmellDisp(void)
{
int k,i,j;

for(k=0;k<=1;k++)
/* SMELL TYPE FOOD and HOME */
for(i=1;i<=MAXX;i++)
for(j=1;j<=MAXY;j++)
{
if(Smell[k][i][j])
{
gotoxy(i,j);
putch(SPACE);
}
} /* of one location */
}

搜索更多相关主题的帖子: define　FOOD　注释　算法　CHAR　
2007-07-01 10:19
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来　自：我爱龙龙
等　级：贵宾
威　望：104
帖　子：9786
专家分：208
注　册：2006-5-23
第 2 楼
收藏
 得分:0 

这个是算法.
太长了.头晕...

蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来寻找最优解决方案的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径。其选择一条路径的概率与该路径上分泌物的强度成正比。

因此，由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象：某一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。蚁群算法就是根据这一特点，通过模仿蚂蚁的行为，从而实现寻优。


倚天照海花无数，流水高山心自知。
2007-07-01 10:34
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来　自：我爱龙龙
等　级：贵宾
威　望：104
帖　子：9786
专家分：208
注　册：2006-5-23
第 3 楼
收藏
 得分:0 

转载:

蚁群算法的基本原理


这种算法有别于传统编程模式，其优势在于，避免了冗长的编程和筹划，程序本身是基于一定规则的随机运行来寻找最佳配置。也就是说，当程序最开始找到目标的时候，路径几乎不可能是最优的，甚至可能是包含了无数错误的选择而极度冗长的。但是，程序可以通过蚂蚁寻找食物的时候的信息素原理，不断地去修正原来的路线，使整个路线越来越短，也就是说，程序执行的时间越长，所获得的路径就越可能接近最优路径。这看起来很类似与我们所见的由无数例子进行归纳概括形成最佳路径的过程。实际上好似是程序的一个自我学习的过程。

这种优化过程的本质在于：
　　选择机制：信息素越多的路径，被选择的概率越大。
　　更新机制：路径上面的信息素会随蚂蚁的经过而增长，而且同时也随时间的推移逐渐挥发消失。
　　协调机制：蚂蚁间实际上是通过分泌物来互相通信、协同工作的。
　　蚁群算法正是充分利用了选择、更新和协调的优化机制，即通过个体之间的信息交流与相互协作最终找到最优解，使它具有很强的发现较优解的能力。

基于以上机制编写的程序的核心代码可能不过上百行，却完成了类似于学习的过程。原因就是所谓的自组织理论，简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，但是，当集群里有无数蚂蚁的时候，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？下面详细说明：

1、范围：
蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。

2、环境：
蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。

3、觅食规则：
在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。

4、移动规则：
每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。

5、避障规则：
如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。

6、播撒信息素规则：
每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。

根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。

说了这么多，蚂蚁究竟是怎么找到食物的呢？

在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁的某个方向正确，而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食物。

当然，在有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。

蚂蚁如何找到最短路径的？

这一是要归功于信息素，另外要归功于环境，具体说是计算机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。也许有人会问局部最短路径和全局最短路的问题，实际上蚂蚁逐渐接近全局最短路的，为什么呢？这源于蚂蚁会犯错误，也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径，这可以理解为一种创新，这种创新如果能缩短路途，那么根据刚才叙述的原理，更多的蚂蚁会被吸引过来。


倚天照海花无数，流水高山心自知。
2007-07-01 10:35
xiazhi123456
Rank: 1
等　级：新手上路
帖　子：9
专家分：0
注　册：2007-6-30
第 4 楼
收藏
 得分:0 

哥们能不能把这个算法的主要步骤给注释一下？？
谢谢了！！！

2007-07-01 12:02
xiazhi123456
Rank: 1
等　级：新手上路
帖　子：9
专家分：0
注　册：2007-6-30
第 5 楼
收藏
 得分:0 

请求高手帮忙，注释一下代码！！！！！

2007-07-01 13:48
xiazhi123456
Rank: 1
等　级：新手上路
帖　子：9
专家分：0
注　册：2007-6-30
第 6 楼
收藏
 得分:0 

请求大家帮忙啊

2007-07-01 15:05
快速回复：[求助]算法注释
数据加载中...
 
　　　



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有，并保留所有权利。
Powered by Discuz, Processed in 0.033788 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved