#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&&!Har dtoFindPath)
{
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,®s0,®s0);
}
void ResetCur(void)
{
union REGS regs0;
regs0.h.ah=1;
regs0.h.ch=0x06;
regs0.h.cl=0x07;
int86(0x10,®s0,®s0);
}
/* ------------ main ANT programe ------------- */
void WorldInitial(void)
{
int k,i,j;
randomize();
clrscr();
HomeFoodInitial();
for(AntNow=0;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.yy y>=y1&&food.yyy<=y2) return; if(home.xxx>=x1&&home.xxx<=x2&&hom e.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 for(AntNow=0;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 /* 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_FO OD] = 0; ant[AntNow].SmellAmount[SMELL_TYPE_H OME] = MAX_SMELL; ant[AntNow].IQ = 1; for(i=0;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||sme lldisp<0) smelldisp = 30000; if(SmellDispFlag) { gotoxy(i,j); if((i==food.xxx&&j==fo od.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 { ant[AntNow].SpeedTimer+=timer10ms; if(ant[AntNow].SpeedTimer>=ant[AntNo w].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].Trac ePtr] = ant[AntNow].xxx; ant[AntNow].tracey[ant[AntNow].Trac ePtr] = ant[AntNow].yyy; if(++(ant[AntNow].TracePtr)>=TRAC E_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[SMEL L_TYPE_FOOD]) { smellnow = Smell[SMELL_TYPE_FOOD][antx][anty]; smelltodrop = ant[AntNow].SmellAmount[SMELL_TYPE_FOO D]*SMELL_DROP_RATE; if(smelltodrop>smellnow) Smell[SMELL_TYPE_FOOD][antx][anty] = smelltodrop; /* else Smell[...] = smellnow */ ant[AntNow].SmellAmount[SME LL_TYPE_FOOD]-= smelltodrop; if(ant[AntNow].SmellAmount[SM ELL_TYPE_FOOD]<0) ant[AntNow].SmellAmount[SMELL_TYPE_FOO D] = 0; } /* of have smell to drop */ } /* of have food */ else /* no food, looking for food */ { if(ant[AntNow].SmellAmount[SMEL L_TYPE_HOME]) { smellnow = Smell[SMELL_TYPE_HOME][antx][anty]; smelltodrop = ant[AntNow].SmellAmount[SMELL_TYPE_HOM E]*SMELL_DROP_RATE; if(smelltodrop>smellnow) Smell[SMELL_TYPE_HOME][antx][anty] = smelltodrop; /* else Smell[...] = smellnow */ ant[AntNow].SmellAmount[SMEL L_TYPE_HOME]-= smelltodrop; if(ant[AntNow].SmellAmount[SM ELL_TYPE_HOME]<0) ant[AntNow].SmellAmount[SMELL_TYPE_HOM E] = 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_TY PE_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 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_TY PE_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 */ } void DispSmell(int type) /* input: 0 -- Only display food smell 1 -- Only display home smell 2 -- Display both food and home smell */ { int k,i,j; int fromk,tok; int smelldisp; switch(type) { case 0: fromk = 0; tok = 0; break; case 1: fromk = 1; tok = 1; break; case 2: fromk = 0; tok = 1; break; default:fromk = 0; tok = 1; break; } SmellGoneTimer = 0; for(k=fromk;k<=tok;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_D ROP_RATE)); if(smelldisp>=30000||smelldi sp<0) smelldisp = 30000; gotoxy(i,j); if(i!=food.xxx||j!=food.yyy) { 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'); } } } } /* of one location */ } int AntNextDir(int xxx,int yyy,int ddir) { int randnum; int testdir; int CanGoState; int cangof,cangol,cangor; int msf,msl,msr,maxms; int type; CanGoState = CanGo(xxx,yyy,ddir); if(CanGoState==0||CanGoState==2||CanG oState==3||CanGoState==6) cangof = 1; else cangof = 0; if(CanGoState==0||CanGoState==1||CanG oState==3||CanGoState==5) cangol = 1; else cangol = 0; if(CanGoState==0||CanGoState==1||CanG oState==2||CanGoState==4) cangor = 1; else cangor = 0; if(ant[AntNow].food) type = SMELL_TYPE_HOME; else type = SMELL_TYPE_FOOD; msf = GetMaxSmell(type,xxx,yyy,ddir); msl = GetMaxSmell(type,xxx,yyy,TurnLeft(ddir)); msr= GetMaxSmell(type,xxx,yyy,TurnRight(ddir)); maxms = MaxLocation(msf,msl,msr); /* maxms - 1 - msf is MAX 2 - msl is MAX 3 - msr is MAX 0 - all 3 number is 0 */ testdir = NULL; switch(maxms) { case 0: /* all is 0, keep testdir = NULL, random select dir */ break; case 1: if(cangof) testdir = ddir; else if(msl>msr) if(cangol) testdir = TurnLeft(ddir); else if(cangor) testdir = TurnRight(ddir); break; case 2: if(cangol) testdir = TurnLeft(ddir); else if(msf>msr) if(cangof) testdir = ddir; else if(cangor) testdir = TurnRight(ddir); break; case 3: if(cangor) testdir = TurnRight(ddir); else if(msf>msl) if(cangof) testdir =ddir; else if(cangol) testdir = TurnLeft(ddir); break; default:break; } /* of maxms */ randnum = random(1000); if(randnum /* 1. if testdir = NULL, means can not find the max smell or the dir to max smell can not go then random select dir 2. if ant error, don't follow the smell, random select dir */ { randnum = random(100); switch(CanGoState) { case 0: if(randnum<90) testdir = ddir; else if (randnum>=90&&randnum<95) testdir = TurnLeft(ddir); else testdir = TurnRight(ddir); break; case 1: if(randnum<50) testdir = TurnLeft(ddir); else testdir = TurnRight(ddir); break; case 2: if(randnum<90) testdir = ddir; else testdir = TurnRight(ddir); break; case 3: if(randnum<90) testdir = ddir; else testdir = TurnLeft(ddir); break; case 4: testdir = TurnRight(ddir); break; case 5: testdir = TurnLeft(ddir); break; case 6: testdir = ddir; break; case 7: testdir = TurnBack(ddir); break; default:testdir = TurnBack(ddir); } /* of can go state */ } return(testdir); } int GetMaxSmell(int type,int xxx,int yyy,int ddir) { int i,j; int ms; /* MAX smell */ ms = 0; switch(ddir) { case UP: for(i=xxx-ANT_EYESHOT;i<=xxx+ANT_ EYESHOT;i++) for(j=yyy-ANT_EYESHOT;j { if(!JudgeCanGo(i,j)) continue; if((i==food.xxx&&j==food .yyy&&type==SMELL_TYPE_FOOD)|| (i==home.xxx&&j==ho me.yyy&&type==SMELL_TYPE_HOME)) { ms = MAX_SMELL; break; } if(IsTrace(i,j)) continue; if(Smell[type][i][j]>ms) ms = Smell[type][i][j]; } break; case DOWN: for(i=xxx-ANT_EYESHOT;i<=xxx+AN T_EYESHOT;i++) for(j=yyy+1;j<=yyy+ANT_EY ESHOT;j++) { if(!JudgeCanGo(i,j)) continue; if((i==food.xxx&&j==food. yyy&&type==SMELL_TYPE_FOOD)|| (i==home.xxx&&j==ho me.yyy&&type==SMELL_TYPE_HOME)) { ms = MAX_SMELL; break; } if(IsTrace(i,j)) continue; if(Smell[type][i][j]>ms) ms = Smell[type][i][j]; } break; case LEFT: for(i=xxx-ANT_EYESHOT;i for(j=yyy-ANT_EYESHOT;j<= yyy+ANT_EYESHOT;j++) { if(!JudgeCanGo(i,j)) continue; if((i==food.xxx&&j==food. yyy&&type==SMELL_TYPE_FOOD)|| (i==home.xxx&&j==ho me.yyy&&type==SMELL_TYPE_HOME)) { ms = MAX_SMELL; break; } if(IsTrace(i,j)) continue; if(Smell[type][i][j]>ms) ms = Smell[type][i][j]; } break; case RIGHT: for(i=xxx+1;i<=xxx+ANT_EYESHOT;i++) for(j=yyy-ANT_EYESHOT;j<= yyy+ANT_EYESHOT;j++) { if(!JudgeCanGo(i,j)) continue; if((i==food.xxx&&j==food .yyy&&type==SMELL_TYPE_FOOD)|| (i==home.xxx&&j==ho me.yyy&&type==SMELL_TYPE_HOME)) { ms = MAX_SMELL; break; } if(IsTrace(i,j)) continue; if(Smell[type][i][j]>ms) ms = Smell[type][i][j]; } break; default: break; } return(ms); } int IsTrace(int xxx,int yyy) { int i; for(i=0;i if(ant[AntNow].tracex[i]==xxx&&ant[An tNow].tracey[i]==yyy) return(1); return(0); } int MaxLocation(int num1,int num2,int num3) { int maxnum; if(num1==0&&num2==0&&num3==0) return(0); maxnum = num1; if(num2>maxnum) maxnum = num2; if(num3>maxnum) maxnum = num3; if(maxnum==num1) return(1); if(maxnum==num2) return(2); if(maxnum==num3) return(3); } int CanGo(int xxx,int yyy,int ddir) /* input: xxx,yyy - location of ant ddir - now dir output: 0 - forward and left and right can go 1 - forward can not go 2 - left can not go 3 - right can not go 4 - forward and left can not go 5 - forward and right can not go 6 - left and right can not go 7 - forward and left and right all can not go */ { int tx,ty,tdir; int okf,okl,okr; /* forward can go ? */ tdir = ddir; tx = xxx; ty = yyy; switch(tdir) { case UP: ty--; break; case DOWN: ty++; break; case LEFT: tx--; break; case RIGHT: tx++; break; default: break; } /* of switch dir */ if(JudgeCanGo(tx,ty)) okf = 1; else okf = 0; /* turn left can go ? */ tdir = TurnLeft(ddir); tx = xxx; ty = yyy; switch(tdir) { case UP: ty--; break; case DOWN: ty++; break; case LEFT: tx--; break; case RIGHT: tx++; break; default: break; } /* of switch dir */ if(JudgeCanGo(tx,ty)) okl = 1; else okl = 0; /* turn right can go ? */ tdir = TurnRight(ddir); tx = xxx; ty = yyy; switch(tdir) { case UP: ty--; break; case DOWN: ty++; break; case LEFT: tx--; break; case RIGHT: tx++; break; default: break; } /* of switch dir */ if(JudgeCanGo(tx,ty)) okr = 1; else okr = 0; if(okf&&okl&&okr) return(0); if(!okf&&okl&&okr) return(1); if(okf&&!okl&&okr) return(2); if(okf&&okl&&!okr) return(3); if(!okf&&!okl&&okr) return(4); if(!okf&&okl&&!okr) return(5); if(okf&&!okl&&!okr) return(6); if(!okf&&!okl&&!okr) return(7); return(7); } int JudgeCanGo(int xxx,int yyy) /* input: location to judeg output: 0 -- can not go 1 -- can go */ { int i,j; if(xxx<=0||xxx>MAXX) return(0); if(yyy<=0||yyy>MAXY) return(0); if(block[xxx][yyy]) return(0); return(1); } int TurnLeft(int ddir) { switch(ddir) { case UP: return(LEFT); case DOWN: return(RIGHT); case LEFT: return(DOWN); case RIGHT: return(UP); default: break; } /* of switch dir */ } int TurnRight(int ddir) { switch(ddir) { case UP: return(RIGHT); case DOWN: return(LEFT); case LEFT: return(UP); case RIGHT: return(DOWN); default: break; } /* of switch dir */ } int TurnBack(int ddir) { switch(ddir) { case UP: return(DOWN); case DOWN: return(UP); case LEFT: return(RIGHT); case RIGHT: return(LEFT); default: break; } /* of switch dir */ } // AO.cpp : 定义控制台应用程序的入口点。 #pragma once #include 62,42,16,8,7,27,30,43,58,58, 37,38,46,61,62,63,32,45,59,5, 10,21,5,30,39,32,25,25,48,56, 30 }; double y_Ary[N_CITY_COUNT]= { 52,49,64,26,30,47,63,62,33,21, 41,32,25,42,16,41,23,33,13,58, 42,57,57,52,38,68,48,67,48,27, 69,46,10,33,63,69,22,35,15,6, 17,10,64,15,10,39,32,55,28,37, 40 }; //返回指定范围内的随机整数 int rnd(int nLow,int nUpper) { return nLow+(nUpper-nLow)*rand()/(RAND_MAX+1); } //返回指定范围内的随机浮点数 double rnd(double dbLow,double dbUpper) { double dbTemp=rand()/((double)RAND_MAX+1.0); return dbLow+dbTemp*(dbUpper-dbLow); } 蚁群算法简述及实现 1 蚁群算法的原理分析 蚁群算法是受自然界中真实蚁群算法的集体觅食行为的启发而发展起来的一种基于群体的模拟进化算法,属于随机搜索算法,所以它更恰当的名字应该叫“人工蚁群算法”,我们一般简称为蚁群算法。M.Dorigo等人充分的利用了蚁群搜索食物的过程与著名的TSP问题的相似性,通过人工模拟蚁群搜索食物的行为来求解TSP问题。 蚂蚁这种社会性动物,虽然个体行为及其简单,但是由这些简单个体所组成的群体却表现出及其复杂的行为特征。这是因为蚂蚁在寻找食物时,能在其经过的路径上释放一种叫做信息素的物质,使得一定范围内的其他蚂蚁能够感觉到这种物质,且倾向于朝着该物质强度高的方向移动。蚁群的集体行为表现为一种正反馈现象,蚁群这种选择路径的行为过程称之为自催化行为。由于其原理是一种正反馈机制,因此也可以把蚁群的行为理解成所谓的增强型学习系统(Reinforcement Learning System)。 引用M.Dorigo所举的例子来说明蚁群发现最短路径的原理和机制,见图1所示。假设D 和H之间、B和H之间以及B和D之间(通过C)的距离为1,C位于D和B的中央(见图1(a))。现在我们考虑在等间隔等离散世界时间点(t=0,1,2……)的蚁群系统情况。假设每单位时间有30只蚂蚁从A到B,另三十只蚂蚁从E到D,其行走速度都为1(一个单位时间所走距离为1),在行走时,一只蚂蚁可在时刻t留下浓度为1的信息素。为简单起见,设信息素在时间区间(t+1，t+2)的中点(t+1.5)时刻瞬时完全挥发。在t=0时刻无任何信息素,但分别有30只蚂蚁在B、30只蚂蚁在D等待出发。它们选择走哪一条路径是完全随机的,因此在两个节点上蚁群可各自一分为二,走两个方向。但在t=1时刻,从A到B的30只蚂蚁在通向H的路径上(见图1(b))发现一条浓度为15的信息素,这是由15只从B走向H的先行蚂蚁留下来的;而在通向C的路径上它们可以发现一条浓度为30的信息素路径,这是由15只走向BC的路径的蚂蚁所留下的气息与15只从D经C到达B留下的气息之和(图1(c))。这时,选择路径的概率就有了偏差,向C走的蚂蚁数将是向H走的蚂蚁数的2倍。对于从E到D来的蚂蚁也是如此。 （a）（b）（c） 图1 蚁群路径搜索实例 这个过程一直会持续到所有的蚂蚁最终都选择了最短的路径为止。 这样,我们就可以理解蚁群算法的基本思想:如果在给定点,一只蚂蚁要在不同的路径中选择,那么,那些被先行蚂蚁大量选择的路径(也就是信息素留存较浓的路径)被选中的概率就更大,较多的信息素意味着较短的路径,也就意味着较好的问题回答。 function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta ,Rho,Q) %%===================================================== ==================== %% ACATSP.m %% Ant Colony Algorithm for Traveling Salesman Problem %% ChengAihua,PLA Information Engineering University,ZhengZhou,China %% Email:aihuacheng@https://www.doczj.com/doc/5f2981659.html, %% All rights reserved %%------------------------------------------------------------------------- %% 主要符号说明 %% C n个城市的坐标，n×4的矩阵 %% NC_max 最大迭代次数 %% m 蚂蚁个数 %% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 信息素增加强度系数 %% R_best 各代最佳路线 %% L_best 各代最佳路线的长度 %%===================================================== ==================== %%第一步：变量初始化 n=size(C,1);%n表示问题的规模（城市个数） D=zeros(n,n);%D表示完全图的赋权邻接矩阵 for i=1:n for j=1:n if i~=j D(i,j)=max( ((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5,min(abs(C(i,3)-C(j,3)),144- abs(C(i,3)-C(j,3))) );%计算城市间距离 else D(i,j)=eps; end D(j,i)=D(i,j); end end Eta=1./D;%Eta为启发因子，这里设为距离的倒数 Tau=ones(n,n);%Tau为信息素矩阵 Tabu=zeros(m,n);%存储并记录路径的生成 NC=1;%迭代计数器 R_best=zeros(NC_max,n);%各代最佳路线 先新建一个主程序M文件ACATSP.m 代码如下: function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q) %%================================================== ======================= %% 主要符号说明 %% C n个城市的坐标，n×2的矩阵 %% NC_max 蚁群算法MATLAB程序最大迭代次数 %% m 蚂蚁个数 %% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 表示蚁群算法MATLAB程序信息素增加强度系数 %% R_best 各代最佳路线 %% L_best 各代最佳路线的长度 %%================================================== ======================= %% 蚁群算法MATLAB程序第一步：变量初始化 n=size(C,1);%n表示问题的规模（城市个数） D=zeros(n,n);%D表示完全图的赋权邻接矩阵 for i=1:n for j=1:n if i~=j D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5; else D(i,j)=eps; % i = j 时不计算，应该为0，但后面的启发因子要取倒数，用eps（浮点相对精度）表示 end D(j,i)=D(i,j); %对称矩阵 end end Eta=1./D; %Eta为启发因子，这里设为距离的倒数 Tau=ones(n,n); %Tau为信息素矩阵 Tabu=zeros(m,n); %存储并记录路径的生成 蚁群算法的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; 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; end; end; for k=1:32; for k=1:32; deltao(i,j)=0; end; end; best_cost=10000; for n_gen=1:50; print_head(n_gen); for i=1:m; %best_solution=[]; print_head2(i); 基于蚁群算法的多目标优化 池元成;蔡国飙 【期刊名称】《计算机工程》 【年(卷),期】2009(035)015 【摘要】Aiming at multi-objective optimization problem, this paper proposes an Ant Colony Algorithm(ACA) for solving Multi-objective Optimization Problem(MOPACA). An improved pheromone updating process based on continuous space is described. Two moving strategies are used in the searching process to ensure better solutions. Convergence property of the algorithm is analyzed. Preliminary simulation results of two benchmark functions show the feasibility of the algorithm.%针对多目标优化问题,提出一种用于求解多目标优化问题的蚁群算法.该算法定义连续空间内求解多目标优化问题的蚁群算法的信息素更新方式,根据信息素的概率转移和随机选择转移策略指导蚂蚁进行搜索,保证获得的Pareto前沿的均匀性以及Pareto解集的多样性.对算法的收敛性进行分析,利用2个测试函数验证算法的有效性. 【总页数】3页(168-169,172) 【关键词】蚁群算法;多目标优化;收敛性分析 【作者】池元成;蔡国飙 【作者单位】北京航空航天大学宇航学院,北京100083;北京航空航天大学宇航学院,北京100083 【正文语种】中文 //Basic Ant Colony Algorithm for TSP #include （多目标优化模型） 蚁群算法在旅行商问题中的应用 摘要 本文将对蚁群算法的仿真学原理进行概要介绍和对蚁群算法产生、发展、优化进行介绍以及阐述蚁群算法的几点重要基本规则，并对蚁群算法的优缺点进行讨论。蚁群算法是受自然界中蚁群搜索食物行为启发而提出的一种智能多目标优化算法，通过介绍蚁群觅食过程中基于信息素的最短路径的搜索策略，给出基于MATLAB的蚁群算法在旅行商问题中的应用。 关键字：蚁群算法；旅行商问题；仿真；多目标优化 一、问题重述 旅行商问题(TSP)是一个经典的组合优化问题。TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton 回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个N P完全问题。随着问题规模的增大，人们对复杂事物和复杂系统建立数学模型并进行求解的能力是有限的，目标函数和约束条件往往不能以明确的函数关系表达，或因函数带有随机参、变量，导致基于数学模型的优化方法在应用于实际生产时，有其局限性甚至不适用。基于仿真的优化(Simulation Based Optimization，SBO)方法正是在这样的背景下发展起来的。本文将使用一种近似算法或启发式算法—蚁族算法。 1、蚁群算法的提出 蚁群算法(Ant Colony Optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 2、蚁群算法的仿生学原理 蚁群算法最初是通过对蚂蚁群落的观察，受蚁群行为特征启发而得出的。蚂蚁是一种群居昆虫，在觅食、清理巢穴征启发而得出的。蚂蚁是一种群居昆虫，在觅食、等活动中，彼此依赖、相互协作共同完成特定的任务。等活动中，彼此依赖、相互协作共同完成特定的任务。就个体来讲，单个蚂蚁的智力和体力是极其有限的，体来讲，单个蚂蚁的智力和体力是极其有限的，服务于整个群落的生存与发展；就群体来讲，蚁群在行为上的分工协作、群落的生存与发展；就群体来讲，蚁群在行为上的分工协作、在完成任务过程中所体现的自组织特征等反应出蚁群具有较高的智能和自我管理能力，具有很高层次组织性，高的智能和自我管理能力，具有很高层次组织性，这使得蚁群能够完成一些复杂的任务。群能够完成一些复杂的任务。 蚁群的行为是整体协作，相互分工，蚁群的行为是整体协作，相互分工，以一个整体去解决一些对单个蚂蚁看上去是不可能完成的任务。些对单个蚂蚁看上去是不可能完成的任务。就目前来讲，蚁群至少有三个方面的行为特征对算法研究有很好的启发意义，分别是觅食行为、任务分配、死蚁堆积阁。蚁群的觅食行为指蚂蚁从巢穴出发寻找食物并且将食物搬回巢穴的行为.当蚂蚁出外寻找食物时，会在自己走过的路径上释放一种称为信息家的物质，径上释放一种称为信息家的物质，后续的蚂蚁一般更愿意走那些信息素强度更高的路径。这样，那些信息素强度更高的路径。这样，较短路径上单位时间内通过的蚂蚁数目较多，留下的信息素也较多(浓度更高) 通过的蚂蚁数目较多，留下的信息素也较多(浓度更高)，对蚂蚁产生了更强的吸引，使得更多的蚂蚁走较短的路径。妈蚁产生了更强的吸引，使得更多的蚂蚁走较短的路径。这就形成了一个正反馈机制，就形成了一个正反馈机制，使得最终所有的蚂蚁都走蚁穴到食物源的最短路径. 食物源的最短路径. 3、蚁群算法实现的重要规则 （1）范围 蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范 function [y,val]=QACStic load att48 att48; MAXIT=300; % 最大循环次数 NC=48; % 城市个数 tao=ones(48,48);% 初始时刻各边上的信息最为1 rho=0.2; % 挥发系数 alpha=1; beta=2; Q=100; mant=20; % 蚂蚁数量 iter=0; % 记录迭代次数 for i=1:NC % 计算各城市间的距离 for j=1:NC distance(i,j)=sqrt((att48(i,2)-att48(j,2))^2+(att48(i,3)-att48(j,3))^2); end end bestroute=zeros(1,48); % 用来记录最优路径 routelength=inf; % 用来记录当前找到的最优路径长度 % for i=1:mant % 确定各蚂蚁初始的位置 % end for ite=1:MAXIT for ka=1:mant %考查第K只蚂蚁 deltatao=zeros(48,48); % 第K只蚂蚁移动前各边上的信息增量为零 [routek,lengthk]=travel(distance,tao,alpha,beta); if lengthk 多目标蚁群算法及其实现 李首帅（2012101020019） 指导老师：张勇 【摘要】多目标优化问题对于现阶段来说，是十分热门的。本文将对多目标规划当中的旅行商问题，通过基于MATLAB的蚁群算法来解决，对多目标问题进行局部优化。 【关键词】旅行商问题；蚁群算法；MATLAB 一、背景介绍 旅行商问题是物流领域当中的典型问题，它的求解十分重要。蚁群算法是受自然界中真实蚁群的集体行为的启发而提出的一种基于群体的模拟进化算法,属于随机搜索算法。M. Dorigo等人充分利用了蚁群搜索食物的过程与旅行商问题(TSP)之间的相似性,通过人工模拟蚁群搜索食物的行为(即蚂蚁个体之间通过间接通讯与相互协作最终找到从蚁穴到食物源的最短路径)来求解TSP问题。为区别于真实蚁群,称算法中的蚂蚁为“人工蚂蚁”。人们经过大量研究发现,蚂蚁个体之间是通过一种称之为信息素(pheromone)的物质进行信息传递,从而能相互协作,完成复杂的任务。蚁群之所以表现出复杂有序的行为,个体之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质,而且能够感知这种物质的存在及其强度,并以此指导自己的运动方向。蚂蚁倾向于朝着该物质强度高的方向移动。因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。 二、蚁群算法原理介绍 1.蚁群在路径上释放信息素； 2.碰到还没走过的路口，就随机挑选一条路走。同时释放与路径长度有关的信息素； 3.信息素浓度与路长成反比； 4.最优路径上的信息浓度越来越大； 5.最终蚁群找到最优路径。 其实自然界中，蚁群这种寻找路径的过程表现是一种正反馈的过程，与人工蚁群的优化算法很相近。所以我们简单功能的工作单元视为蚂蚁，则上述的搜寻路径过程可以用来解释人工蚁群搜寻过程。 人工蚁群和自然界蚁群各具特点。人工蚁群具有一定的记忆能力。它能够记忆已经访问过的节点;另外,人工蚁群在选择下一条路径的时候并不是完全盲目的,而是按一定的算法规律有意识地寻找最短路径。而自然界蚁群不具有记忆的能力，它们的选路凭借外激素，或者 蚁群算法matlab精讲及仿真 4.1基本蚁群算法 4.1.1基本蚁群算法的原理 蚁群算法是上世纪90年代意大利学者M.Dorigo,v.Maneizz。等人提出来的,在越来越多的领域里得到广泛应用。蚁群算法，是一种模拟生物活动的智能算法，蚁群算法的运作机理来源于现实世界中蚂蚁的真实行为，该算法是由Marco Dorigo 首先提出并进行相关研究的，蚂蚁这种小生物，个体能力非常有限，但实际的活动中却可以搬动自己大几十倍的物体，其有序的合作能力可以与人类的集体完成浩大的工程非常相似，它们之前可以进行信息的交流，各自负责自己的任务，整个运作过程统一有序，在一只蚂蚁找食物的过程中，在自己走过的足迹上洒下某种物质，以传达信息给伙伴，吸引同伴向自己走过的路径上靠拢，当有一只蚂蚁找到食物后，它还可以沿着自己走过的路径返回，这样一来找到食物的蚂蚁走过的路径上信息传递物质的量就比较大，更多的蚂蚁就可能以更大的机率来选择这条路径，越来越多的蚂蚁都集中在这条路径上，蚂蚁就会成群结队在蚁窝与食物间的路径上工作。当然，信息传递物质会随着时间的推移而消失掉一部分，留下一部分，其含量是处于动态变化之中，起初，在没有蚂蚁找到食物的时候，其实所有从蚁窝出发的蚂蚁是保持一种随机的运动状态而进行食物搜索的，因此，这时，各蚂蚁间信息传递物质的参考其实是没有价值的，当有一只蚂蚁找到食物后，该蚂蚁一般就会向着出发地返回，这样，该蚂蚁来回一趟在自己的路径上留下的信息传递物质就相对较多，蚂蚁向着信息传递物质比较高的路径上运动，更多的蚂蚁就会选择找到食物的路径，而蚂蚁有时不一定向着信 息传递物质量高的路径走，可能搜索其它的路径。这样如果搜索到更短的路径后，蚂蚁又会往更短的路径上靠拢，最终多数蚂蚁在最短路径上工作。【基于蚁群算法和遗传算法的机器人路径规划研究】 该算法的特点： (1)自我组织能力，蚂蚁不需要知道整体环境信息，只需要得到自己周围的信息，并且通过信息传递物质来作用于周围的环境，根据其他蚂蚁的信息素来判断自己的路径。 (2)正反馈机制，蚂蚁在运动的过程中，收到其他蚂蚁的信息素影响，对于某路径上信息素越强的路径，其转向该路径的概率就越大，从而更容易使得蚁群寻找到最短的避障路径。 (3)易于与其他算法结合，现实中蚂蚁的工作过程简单，单位蚂蚁的任务也比较单一，因而蚁群算法的规则也比较简单，稳定性好，易于和其他算法结合使得避障路径规划效果更好。 (4)具有并行搜索能力探索过程彼此独立又相互影响，具备并行搜索能力，这样既可以保持解的多样性，又能够加速最优解的发现。 4.1.2 基本蚁群算法的生物仿真模型 a为蚂蚁所在洞穴,food为食物所在区,假设abde为一条路径,eadf为另外一条路径,蚂蚁走过后会留下信息素,5分钟后蚂蚁在两条路径上留下的信息素的量都为3,概率可以认为相同,而30分钟后baed路径上的信息素的量为60,明显大于eadf路径上的信息素的量。最终蚂蚁会完全选择abed这条最短路径,由此可见, 目录 1 绪论 (1) 1.1研究背景 (1) 1.2国内外研究综述 (2) 1.3主要研究内容 (4) 1.4论文组织结构 (5) 2 相关技术综述 (6) 2.1基本蚁群算法 (6) 2.2Pareto最优解 (8) 2.3多目标优化问题的数学求解 (10) 2.4多目标优化问题的智能算法 (12) 3 岸桥-泊位调度问题的形式化描述 (13) 3.1港口调度 (13) 3.2问题描述 (15) 3.3数学模型 (16) 4 基于蚁群算法的多目标岸桥-泊位调度优化 (24) 4.1岸桥-泊位调度的多目标优化 (24) 4.2多目标蚁群算法的参数改进优化 (25) 4.3基于多目标蚁群算法的搜索方式优化 (32) 4.4约束条件的处理 (35) 5 实验与分析 (39) 5.1Flexterm平台简介 (39) 5.2Flexterm架构及环境配置 (40) 5.3仿真实验 (41) 6 总结与展望 (53) 6.1总结 (53) 6.2展望 (54) 参考文献 (55) 致谢 (59) I 万方数据 攻读硕士期间参加的科研项目 (60) II 万方数据 Contents 1 Introduction (1) 1.1 Research Background (1) 1.2Research Status at Home and Abroad (2) 1.3 Researce Contents (4) 1.4 Organization of Thesis (5) 2 Basic Theory Research and Analysis (6) 2.1 Basic Ant Colony Algorithm (6) 2.2 Pareto Optimum Solution (8) 2.3 Mathematical Solution of Multiobjective Problems (10) 2.4 Intelligent Algorithm for Multiobjective Problems (12) 3 Formal Description of Quay Berth Scheduling Problem (13) 3.1 Port Scheduling (13) 3.2 Problem Description (15) 3.3 Mathematical Model (16) 4 Optimization of Multi Objective Crane Scheduling Based on Ant Colony Algorithm (24) 4.1 Multi Objective Optimization of Quay Berth Scheduling (24) 4.2 Parameter Optimization of Ant Colony Algorithm (25) 4.3 Search Optimization Based on Ant Colony Algorithm (32) 4.4 Constraint Handling (35) 5 The Simulation and Analysis of Experiments (39) 5.1 Flexterm Platform Profile (39) 5.2 Flexterm Architecture and Environment Configuration (40) 5.3 Simulation Experiment (41) 6 Conclusions and Prospects (53) 6.1 Conclusions (53) 6.2 Further Work (54) Reference (554) Thanks (58) The Projects During Master Candidate (59) III 万方数据 基于蚁群算法的机器人路径规划MATLAB源代码 基本思路是，使用离散化网格对带有障碍物的地图环境建模，将地图环境转化为邻接矩阵，最后使用蚁群算法寻找最短路径。 function [ROUTES,PL,Tau]=ACASPS(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q) %% --------------------------------------------------------------- % ACASP.m % 基于蚁群算法的机器人路径规划 % GreenSim团队——专业级算法设计&代写程序 % 欢迎访问GreenSim团队主页→https://www.doczj.com/doc/5f2981659.html,/greensim %% --------------------------------------------------------------- % 输入参数列表 % G 地形图为01矩阵，如果为1表示障碍物 % Tau 初始信息素矩阵（认为前面的觅食活动中有残留的信息素） % K 迭代次数（指蚂蚁出动多少波） % M 蚂蚁个数（每一波蚂蚁有多少个） % S 起始点（最短路径的起始点） % E 终止点（最短路径的目的点） % Alpha 表征信息素重要程度的参数 % Beta 表征启发式因子重要程度的参数 % Rho 信息素蒸发系数 % Q 信息素增加强度系数 % % 输出参数列表 % ROUTES 每一代的每一只蚂蚁的爬行路线 % PL 每一代的每一只蚂蚁的爬行路线长度 % Tau 输出动态修正过的信息素 %% --------------------变量初始化---------------------------------- %load D=G2D(G); N=size(D,1);%N表示问题的规模（象素个数） MM=size(G,1); a=1;%小方格象素的边长 Ex=a*(mod(E,MM)-0.5);%终止点横坐标 if Ex==-0.5 Ex=MM-0.5; end Ey=a*(MM+0.5-ceil(E/MM));%终止点纵坐标 Eta=zeros(1,N);%启发式信息，取为至目标点的直线距离的倒数 %下面构造启发式信息矩阵 for i=1:N 多目标优化的求解方法 多目标优化(MOP)就是数学规划的一个重要分支,就是多于一个的数值目标函数在给定区域上的最优化问题。 多目标优化问题的数学形式可以描述为如下: 多目标优化方法本质就是将多目标优化中的各分目标函数,经处理或数学变换,转变成一个单目标函数,然后采用单目标优化技术求解。目前主要有以下方法: （1）评价函数法。常用的方法有:线性加权与法、极大极小法、理想点法。评价函数法的实质就是通过构造评价函数式把多目标转化为单目标。 (2)交互规划法。不直接使用评价函数的表达式,而就是使决策者参与到求解过程,控制优化的进行过程,使分析与决策交替进行,这种方法称为交互规划法。常用的方法有:逐步宽容法、权衡比替代法,逐次线性加权与法等。 (3)分层求解法。按目标函数的重要程度进行排序,然后按这个排序依次进行单目标的优化求解,以最终得到的解作为多目标优化的最优解。 而这些主要就是通过算法来实现的, 一直以来很多专家学者采用不同算法解决多目标优化问题, 如多目标进化算法、多目标粒子群算法与蚁群算法、模拟退火算法及人工免疫系统等。 在工程应用、生产管理以及国防建设等实际问题中很多优化问题都就是多目标优化问题, 它的应用很广泛。 1)物资调运车辆路径问题 某部门要将几个仓库里的物资调拨到其她若干个销售点去, 在制定调拨计划时一般就要考虑两个目标, 即在运输过程中所要走的公里数最少与总的运输费用最低, 这就是含有两个目标的优化问题。利用首次适配递减算法与标准蚁群算法对救灾物资运输问题求解, 求得完成运输任务的最少时间, 将所得结果进行了比较。 2)设计 如工厂在设计某种新产品的生产工艺过程时, 通常都要求产量高、质量好、成本低、消耗少及利润高等, 这就就是一个含有五个目标的最优化问题; 国防部门在设计导弹时, 要考虑导弹的射程要远、精度要最高、重量要最轻以及消耗燃料要最省等,这就就是一个含有四个目标的最优化问题。Jo等人将遗传算法与有限元模拟软件结合 function [y,val]=QACS tic load att48 att48; MAXIT=300; % 最大循环次数 NC=48; % 城市个数 tao=ones(48,48);% 初始时刻各边上的信息最为1 rho=0.2; % 挥发系数 alpha=1; beta=2; Q=100; mant=20; % 蚂蚁数量 iter=0; % 记录迭代次数 for i=1:NC % 计算各城市间的距离 for j=1:NC distance(i,j)=sqrt((att48(i,2)-att48(j,2))^2+(att48(i,3)-att48(j,3))^2); end end bestroute=zeros(1,48); % 用来记录最优路径 routelength=inf; % 用来记录当前找到的最优路径长度 % for i=1:mant % 确定各蚂蚁初始的位置 % end for ite=1:MAXIT for ka=1:mant %考查第K只蚂蚁 deltatao=zeros(48,48); % 第K只蚂蚁移动前各边上的信息增量为零 [routek,lengthk]=travel(distance,tao,alpha,beta); if lengthk 蚁群算法最短路径通用Matlab程序（附图） function [ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q) %% --------------------------------------------------------------- % ACASP.m % 蚁群算法动态寻路算法 % ChengAihua,PLA Information Engineering University,ZhengZhou,China % Email:aihuacheng@https://www.doczj.com/doc/5f2981659.html, % All rights reserved %% --------------------------------------------------------------- % 输入参数列表 % G 地形图为01矩阵，如果为1表示障碍物 % Tau 初始信息素矩阵（认为前面的觅食活动中有残留的信息素） % K 迭代次数（指蚂蚁出动多少波） % M 蚂蚁个数（每一波蚂蚁有多少个） % S 起始点（最短路径的起始点） % E 终止点（最短路径的目的点） % Alpha 表征信息素重要程度的参数 % Beta 表征启发式因子重要程度的参数 % Rho 信息素蒸发系数 % Q 信息素增加强度系数 % % 输出参数列表 % ROUTES 每一代的每一只蚂蚁的爬行路线 % PL 每一代的每一只蚂蚁的爬行路线长度 % Tau 输出动态修正过的信息素 %% --------------------变量初始化---------------------------------- %load D=G2D(G); N=size(D,1);%N表示问题的规模（象素个数） MM=size(G,1); a=1;%小方格象素的边长 Ex=a*(mod(E,MM)-0.5);%终止点横坐标 if Ex==-0.5 Ex=MM-0.5; end Ey=a*(MM+0.5-ceil(E/MM));%终止点纵坐标 Eta=zeros(1,N);%启发式信息，取为至目标点的直线距离的倒数 %下面构造启发式信息矩阵 for i=1:N if ix==-0.5 龙源期刊网 https://www.doczj.com/doc/5f2981659.html, 动态环境下机器人多目标路径规划蚂蚁算法作者：徐守江 来源：《电脑知识与技术·学术交流》2008年第32期 摘要：研究了一种新颖的动态复杂不确定环境下的机器人多目标路径规划蚂蚁算法。该方法首先根据蚂蚁觅食行为对多个目标点的组合进行优化，规划出一条最优的全局导航路径。在此基础上，机器人按照规划好的目标点访问顺序根据多蚂蚁协作局部路径算法完成局部路径的搜索。机器人每前进一步都实时地进行动态障碍物运动轨迹预测以及碰撞预测，并重新进行避碰局部路径规划。仿真结果表明，即使在障碍物非常复杂的地理环境，用该算法也能使机器人沿一条全局优化的路径安全避碰的遍历各个目标点，效果十分令人满意。 关键词：机器人；多蚂蚁协作；全局导航路径；局部路径 中图分类号：TP24文献标识码：A文章编号：1009-3044(2008)32-1185-03 Ant Algorithm for Mobile Robot Path Plan with Multi-objects in an Unfamiliar Environment XU Shou-jiang (Jiangsu Food Science College, Huai'an 223003, China) Abstract: Based on Ant Colony Optimization (ACO), this thesis presents a novel algorithm underlying the robot multi-objects path planning and dynamic obstacle avoidance in a complex and unfamiliar environment, and the algorithm optimizes the combination of all objects and can get a globally optimal navigation path. The locally optimal path between the position of robot and the present object which is gotten from the globally optimal navigation path is accomplished by local path planning with multi-ants in cooperation. Collision prediction proceeds timely after ever step of robot and local dynamic planning for obstacle avoidance is executed. Our computer experiments demonstrate that the algorithms are robust and stable. Key words: robot; multi-ants cooperation; global navigation path; local path 1 引言 移动机器人运动导航或路径规划属于研究机器人控制系统的重要应用基础问题，也是机器人研究领域中的一个重要分支。它是指在有障碍物的工作环境中，如何寻找一条从给定起始点到终止点的较优的运动路径，使机器人在运动过程中能安全无碰撞地绕过障碍物，且所走路线最短。对这一问题，各国学者已经做了大量的研究，其中包括Dijkstra算法及其改进[1]、启发蚁群算法(C++版)
蚁群算法简述及实现
蚁群算法TSP问题matlab源代码
蚁群算法matlab程序代码
蚁群算法matlab
基于蚁群算法的多目标优化
蚁群算法代码
仿真的多目标优化(蚁群算法在旅行商问题中的应用)
蚁群算法MATLAB代码
多目标蚁群算法及其实现
matlab蚁群算法精讲及仿真图
基于蚁群算法的多目标岸桥-泊位调度优化研究
基于蚁群算法的MATLAB实现
多目标优化的求解方法
(完整版)蚁群算法matlab程序实例整理
蚁群算法最短路径通用Matlab程序(附图)
动态环境下机器人多目标路径规划蚂蚁算法
相关主题
文本预览