c語言程序課程設(shè)計--模擬螞蟻覓食

1、<p><b>　　目 錄</b></p><p><b>　　1 前言1</b></p><p><b>　　2 需求分析1</b></p><p><b>　　2.1要求1</b></p><p><b>　　2.2任務(wù)1&

2、lt;/b></p><p><b>　　2.3運行環(huán)境1</b></p><p><b>　　2.4開發(fā)工具1</b></p><p>　　3 概要設(shè)計與詳細設(shè)計1</p><p>　　3.1系統(tǒng)流程圖2</p><p>　　3.2訪問流程圖3</p&

3、gt;<p><b>　　4 編碼與實現(xiàn)4</b></p><p><b>　　4.1分析4</b></p><p>　　4.2具體代碼實現(xiàn)6</p><p>　　5 課程設(shè)計總結(jié)15</p><p>　　參考文獻...15</p><p><b

4、>　　致 謝15</b></p><p><b>　　1 前言</b></p><p>　　使用C語言編程，設(shè)計一個有效的算法，模擬螞蟻覓食的過程。</p><p><b>　　2 需求分析</b></p><p><b>　　2.1要求</b></

5、p><p>　?。?）各個螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。</p><p>　?。?）當一只找到食物以后，它會向環(huán)境釋放一種信息素，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物。</p><p>　?。?）有些螞蟻并沒有象其它螞蟻一樣總重復(fù)同樣的路，他們會另辟蹊徑，如果令開辟的道路比原來的其他道路更短，那么，漸漸，更多的螞蟻被吸引到這條較短

6、的路上來。</p><p>　　（4）最后，經(jīng)過一段時間運行，可能會出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復(fù)著。</p><p><b>　　2.2任務(wù)</b></p><p>　?。?）構(gòu)建二維數(shù)組將每條路徑的信息素量、相應(yīng)路徑的信息素增量和城市距離放入其中。</p><p>　?。?）輸入兩個城市間的坐標，并得到兩個城市間

7、的最近距離。</p><p>　?。?）畫出所有模塊的流程圖；</p><p><b>　?。?）編寫代碼；</b></p><p>　　（5）程序分析與調(diào)試。</p><p><b>　　2.3運行環(huán)境</b></p><p>　?。?）WINDOWS2000/XP系統(tǒng)&l

8、t;/p><p>　?。?）TurboC2.0編譯環(huán)境</p><p><b>　　2.4開發(fā)工具</b></p><p><b>　　C語言</b></p><p>　　3 概要設(shè)計與詳細設(shè)計</p><p><b>　　3.1系統(tǒng)流程圖</b></

9、p><p><b>　　如圖3.1所示。</b></p><p>　　圖3.1 系統(tǒng)流程圖</p><p><b>　　3.2訪問流程圖</b></p><p><b>　　如圖3.2所示。</b></p><p><b>　　圖3.2訪問流程圖

10、</b></p><p><b>　　4 編碼與實現(xiàn)</b></p><p><b>　　4.1分析</b></p><p>　　程序開始運行，螞蟻們開始從窩里出動了，尋找食物；他們會順著屏幕爬滿整個畫面，直到找到食物再返回窩。</p><p>　　其中，‘D’點表示食物，‘A’表示窩，

11、白色塊表示障礙物，‘+’就是螞蟻了。</p><p>　　預(yù)期的結(jié)果：各個螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。當一只找到食物以后，它會向環(huán)境釋放一種信息素，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物！有些螞蟻并沒有象其它螞蟻一樣總重復(fù)同樣的路，他們會另辟蹊徑，如果令開辟的道路比原來的其他道路更短，那么，漸漸，更多的螞蟻被吸引到這條較短的路上來。最后，經(jīng)過一段時間運行，可能會出現(xiàn)一條最短

12、的路徑被大多數(shù)螞蟻重復(fù)著。</p><p>　　1、范圍：螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個方格世界，并且能移動的距離也在這個范圍之內(nèi)。</p><p>　　2、環(huán)境：螞蟻所在的環(huán)境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素

13、。每個螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。</p><p>　　3、覓食規(guī)則：在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻多會以小概率犯錯誤，從而并不是往信息素最多的點移動。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應(yīng)，而對食物信息素沒反應(yīng)。</p&

14、gt;<p>　　4、移動規(guī)則：每只螞蟻都朝向信息素最多的方向移，并且，當周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，并且，在運動的方向有一個隨機的小的擾動。為了防止螞蟻原地轉(zhuǎn)圈，它會記住最近剛走過了哪些點，如果發(fā)現(xiàn)要走的下一點已經(jīng)在最近走過了，它就會盡量避開。</p><p>　　5、避障規(guī)則：如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，并且有信息素指引的

15、話，它會按照覓食的規(guī)則行為。</p><p>　　6、播撒信息素規(guī)則：每只螞蟻在剛找到食物或者窩的時候撒發(fā)的信息素最多，并隨著它走遠的距離，播撒的信息素越來越少。</p><p><b>　　圖1</b></p><p><b>　　圖2</b></p><p>　　假設(shè)螞蟻每經(jīng)過一處所留下的信息單

16、位為1，則經(jīng)過36個時間單位后，所有</p><p>　　開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點得到了食物，此時ABD的路線往返了2趟，每一處的信息素為4個單位，而從ACD的路線往返了一趟，每一處的信息素為2個單位。其比值為2:1。尋找食物的過程繼續(xù)進行，則按信息素的指導(dǎo)，蟻群在ABD的路線上增只螞蟻（2只），而ACD路線上仍然只有一只螞蟻，再經(jīng)過36個時間兩條路線上的信息素單位積累為12和4，比值為3:1。&l

17、t;/p><p>　　若繼續(xù)進行，則按信息素指導(dǎo)，最終選擇ABD路線的螞蟻會越來越多，選擇ACD路線上的螞蟻也就越來越少。同理可以得出整個大環(huán)境也是按照這種方式進行路線的選擇的。這也就解釋了（3）有些螞蟻并沒有象其它螞蟻一樣總重復(fù)同樣的路，他們會另辟蹊徑，如果令開辟的道路比原來的其他道路更短，那么，漸漸，更多的螞蟻被吸引到這條較短的路上來。</p><p>　　最后，經(jīng)過一段時間運行，可能會出

18、現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復(fù)著。</p><p><b>　　4.2具體代碼實現(xiàn)</b></p><p>　　寫上源程序，并加上必要的注釋。</p><p>　　#include <math.h> </p><p>　　#include <time.h> </p><p&

19、gt;　　#include <stdlib.h> </p><p>　　#include <stdio.h> </p><p>　　#define N 6 /*城市的數(shù)目*/</p><p>　　#define M 48 /*螞蟻的數(shù)目*/</p><

20、;p>　　double inittao=1; /*初始信息素量*/</p><p>　　double tao[N][N]; /*每條路徑的信息素量*/</p><p>　　double detatao[N][N]; /*相應(yīng)路徑的信息素增量*/</p><p>　　double distan

21、ce[N][N]; /*保存城市距離的數(shù)組*/</p><p>　　double yita[N][N]; /*啟發(fā)函數(shù)，一般初始其值為*/</p><p>　　int tabu[M][N]; /*禁忌表，tabu[i][j]=1表示螞蟻i已經(jīng)走過了j城市*/</p><p>　　int route[M][N

22、]; /*保存螞蟻k的路徑的數(shù)組為route[k][N] */</p><p>　　int i,j,k; /*循環(huán)變量*/</p><p>　　double solution[M]; /*螞蟻k訪問的路徑的長度為solution[k]*/</p><p>　　int BestR

23、oute[N]; /*當前最優(yōu)的訪問路徑序列*/</p><p>　　double BestSolution=10000000; /*當前最優(yōu)的訪問路的長度*/</p><p><b>　　int aa=1;</b></p><p>　　int NcMax;</p><p>　　double

24、alfa,beta,rou,Q;</p><p>　　/* alfa是信息啟發(fā)式因子，表示軌跡的相對重要性,其值越大，則該螞蟻越傾向于選擇其他螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性越強。beta是期望啟發(fā)式因子，表示能見度?其值越大，則該狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則。rou是信息殘留因子，Q為信息素強度，用于計算螞蟻留在路徑上的信息量*/</p><p>　　int coordinate[N][

25、2]; /*城市的坐標,由用戶輸入*/</p><p>　　int jianyan(int a[],int n) /*用于檢驗用戶輸入的路徑序列數(shù)組是否合法*/</p><p><b>　　{</b></p><p>　　for(i=0;i<n-1;i++){ /*判斷數(shù)組的元素是否有重復(fù)*

26、/</p><p>　　for(j=i+1;j<n;j++){</p><p>　　if(a[i] == a[j]){</p><p><b>　　k=0;</b></p><p><b>　　break;}</b></p><p><b>　　else<

27、;/b></p><p><b>　　k=1;</b></p><p><b>　　}</b></p><p>　　if(j<n)break;</p><p><b>　　}</b></p><p><b>　　j=1;</b

28、></p><p>　　for(i=0;i<n;i++) /*判斷數(shù)組的元素是否大于等于城市數(shù)*/</p><p>　　if(a[i]>=n){</p><p><b>　　j=0;</b></p><p><b>　　break;}</b></p

29、><p>　　return k*j;</p><p><b>　　}</b></p><p>　　int zjianyan(int a[][2],int n) /*判斷用戶輸入的城市坐標是否有相同*/</p><p><b>　　{</b></p><p>　　for(i=0;i

30、<n-1;i++){</p><p>　　for(j=i+1;j<n;j++){</p><p>　　if(a[i][0] == a[j][0]&&a[i][1] == a[j][1]){</p><p><b>　　k=0;</b></p><p><b>　　break;}<

31、;/b></p><p><b>　　else</b></p><p><b>　　k=1;</b></p><p><b>　　}</b></p><p>　　if(j<n)break;</p><p><b>　　}</b

32、></p><p><b>　　return k;</b></p><p><b>　　}</b></p><p>　　void Intial()</p><p><b>　　{</b></p><p><b>　　do{</b&g

33、t;</p><p>　　printf("please input the coordinate of cities:\n");</p><p>　　for(i = 0;i < N;i++)</p><p>　　for(j = 0;j < 2;j++)</p><p>　　scanf("%d"

34、;,&coordinate[i][j]);</p><p>　　aa=zjianyan(coordinate,N);</p><p><b>　　if(aa==0)</b></p><p>　　printf("Error!Please input again!\n");</p><p>　　}

35、while(aa==0);</p><p><b>　　}</b></p><p>　　void initparameter(void) /*初始化各參數(shù)*/</p><p><b>　　{ </b></p><p>　　alfa=1.0; beta=5.0; rou=0.9; Q=10

36、0;</p><p>　　NcMax=250;</p><p><b>　　} </b></p><p>　　double EvalueSolution(int a[])/*評估路徑，測試路徑長度*/</p><p><b>　　{ </b></p><p>　　doubl

37、e dist=0; </p><p>　　for(i=0;i<N-1;i++) </p><p>　　dist+=distance[a[i]][a[i+1]]; </p><p>　　dist+=distance[a[i]][a[0]]; /*循環(huán)到最后要返回起點，形成回路*/</p><p>　　return dist;

38、</p><p><b>　　}</b></p><p>　　void dotest(void) /*測試結(jié)果準確性*/</p><p><b>　　{</b></p><p><b>　　int rp;</b></p><p>

39、;　　int test[N];</p><p><b>　　do{</b></p><p><b>　　rp = 0;</b></p><p>　　printf("make a test: \n");</p><p><b>　　do{</b></p&

40、gt;<p>　　for(i=0;i<N;i++)</p><p>　　scanf("%d",&test[i]);</p><p>　　aa=jianyan(test,N);</p><p><b>　　if(aa==0)</b></p><p>　　printf(&quo

41、t;Error!Please input again!\n");</p><p><b>　　}</b></p><p>　　while(aa==0);</p><p>　　printf("the result of test is %4f \n",EvalueSolution(test));</p>

42、<p>　　printf("would you want to continue?(1 for yes and 0 for no):");</p><p>　　scanf("%d",&rp);</p><p>　　}while(rp==1);</p><p><b>　　}</b>&l

43、t;/p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　int NC=0;</b></p><p><b>　　Intial();</b></p><p>　　initparameter();<

44、/p><p>　　for(i=0;i<N;i++){ </p><p>　　for(j=i+1;j<N;j++) </p><p><b>　　{ </b></p><p>　　distance[j][i]=sqrt(pow(coordinate[i][0]-coordinate[j][0],2)+pow(c

45、oordinate[i][1]-coordinate[j][1],2));</p><p>　　distance[i][j]=distance[j][i];</p><p><b>　　}</b></p><p><b>　　} </b></p><p>　　for(i=0;i<N;i++){

46、 </p><p>　　for(j=0;j<N;j++) </p><p><b>　　{ </b></p><p>　　tao[i][j]=inittao; </p><p>　　if(j!=i) </p><p>　　yita[i][j]=1/distance[i][j]; &

47、lt;/p><p><b>　　}</b></p><p><b>　　} </b></p><p>　　for(k=0;k<M;k++) </p><p>　　for(i=0;i<N;i++) </p><p>　　route[k][i]=-1; </p

48、><p>　　srand(time(NULL)); </p><p>　　for(k=0;k<M;k++) </p><p><b>　　{ </b></p><p>　　route[k][0]=k%N; /*設(shè)置初始城市*/</p><p>　　tabu[k]

49、[route[k][0]]=1; /*設(shè)置初始城市被訪問標記*/</p><p><b>　　} </b></p><p><b>　　do { </b></p><p>　　int s=1; </p><p>　　double partsum; /*為方便計算轉(zhuǎn)移

50、概率而設(shè)的變量,本身沒有實際意義*/</p><p>　　double pper; /*轉(zhuǎn)移概率*/</p><p>　　double drand; </p><p>　　while(s<N) </p><p><b>　　{ </b></p><p>

51、;　　for(k=0;k<M;k++) </p><p><b>　　{ </b></p><p>　　int jrand=rand()%3000; /*jrand是隨機生成，不一定要3000，其他數(shù)字也可，另外需要保證</p><p>　　drand=jrand/3001.0; drand比

52、1要小，故這里除以3001*/</p><p>　　partsum=0; </p><p><b>　　pper=0; </b></p><p>　　for(j=0;j<N;j++) /*根據(jù)概率函數(shù)計算螞蟻的轉(zhuǎn)移概率*/</p><p><b>　　{ </b

53、></p><p>　　if(tabu[k][j]==0) </p><p>　　partsum+=pow(tao[route[k][s-1]][j],alfa)*pow(yita[route[k][s-1]][j],beta); /*route[k][s-1]表示螞蟻k第s-1步走到的城市，s==1表示螞蟻從初始城市出發(fā)</p><p>　　tao

54、[route[k][s-1]][j]表示螞蟻k經(jīng)過的前一個城市到下一個沒被訪問的城市j的信息量*/</p><p><b>　　} </b></p><p>　　for(j=0;j<N;j++) </p><p><b>　　{ </b></p><p>　　if(tabu[k][j]=

55、=0) </p><p>　　pper+=pow(tao[route[k][s-1]][j],alfa)*pow(yita[route[k][s-1]][j],beta)/partsum; </p><p>　　if(pper>drand)</p><p><b>　　break;</b></p><p>&l

56、t;b>　　} </b></p><p>　　tabu[k][j]=1; /*禁忌表置訪問標志*/</p><p>　　route[k][s]=j; /*保存螞蟻k的第s步經(jīng)過的城市*/</p><p><b>　　} </b></p><

57、;p><b>　　s++; </b></p><p><b>　　} </b></p><p>　　for(i=0;i<N;i++) </p><p>　　for(j=0;j<N;j++)</p><p>　　detatao[i][j]=0; </p><

58、p>　　for(k=0;k<M;k++) /*計算每個螞蟻經(jīng)過路徑的長度，保存到當前代最好的路徑及其長度*/</p><p><b>　　{ </b></p><p>　　solution[k]=EvalueSolution(route[k]); </p><p>　　if(solution[k]<Best

59、Solution) </p><p><b>　　{ </b></p><p>　　BestSolution=solution[k]; </p><p>　　for(s=0;s<N;s++) </p><p>　　BestRoute[s]=route[k][s]; </p><p>

60、;<b>　　} </b></p><p><b>　　} </b></p><p>　　for(k=0;k<M;k++) /*計算各個路徑上的信息素增量*/</p><p><b>　　{ </b></p><p>　　for(s=0;s

61、<N-1;s++) </p><p>　　detatao[route[k][s]][route[k][s+1]]+=Q/solution[k]; </p><p>　　detatao[route[k][N-1]][route[k][0]]+=Q/solution[k]; </p><p><b>　　} </b></p>

62、;<p>　　for(i=0;i<N;i++) /*更新路徑上的信息素*/</p><p>　　for(j=0;j<N;j++)</p><p><b>　　{ </b></p><p>　　tao[i][j]=rou*tao[i][j]+detatao[i][j]; </p>

63、;<p>　　if(tao[i][j]<0.00001) </p><p>　　tao[i][j]=0.00001; </p><p>　　if(tao[i][j]>20)</p><p>　　tao[i][j]=20; </p><p><b>　　} </b></p>&

64、lt;p>　　for(k=0;k<M;k++) /*將螞蟻的路徑再重新置空,為下一次循環(huán)做準備*/</p><p>　　for(j=1;j<N;j++) /*注意起始城市，即j=0沒有被清空*/</p><p><b>　　{ </b></p><p>　　tabu[k][rout

65、e[k][j]]=0; </p><p>　　route[k][j]=-1; </p><p><b>　　} </b></p><p><b>　　NC++; </b></p><p>　　} while(NC<NcMax); </p><p>　　print

66、f("*-------------------------------------------------------------------------*\n");</p><p>　　printf("the initialized parameters of ACA are as follows:\n");</p><p>　　printf(&q

67、uot;alfa=%.1f, beta=%.1f, rou=%.1f, Q=%.1f \n",alfa,beta,rou,Q);</p><p>　　printf("the best route is:");</p><p>　　for(i=0;i<N;i++) </p><p>　　printf("%d "

68、;,BestRoute[i]); </p><p>　　printf("\n");</p><p>　　printf("the shortest length of the path is:%2f \n",BestSolution);</p><p>　　printf("*----------------------

69、---------------------------------------------------*\n");</p><p>　　system("PAUSE");</p><p><b>　　dotest();</b></p><p><b>　　}</b></p><

70、;p><b>　　程序提示輸入信息</b></p><p><b>　　程序運行結(jié)果</b></p><p><b>　　5 課程設(shè)計總結(jié)</b></p><p>　　在此次設(shè)計中開始時覺得這個題目很新鮮，通過查閱各方資料，我了解到這個是一個比較經(jīng)典的問題，但是這設(shè)計的過程中也遇到很多問題。比如

71、：當輸入數(shù)據(jù)中有兩個是相同的，也就是說相當于把相同的那個城市坐標訪問兩次，這與算法的設(shè)定（一次遍歷中已訪問的城市不能再訪問）有矛盾，故程序不能執(zhí)行下去，提醒用戶輸入有錯誤。當發(fā)現(xiàn)這個問題時我還是比較驚訝的，因為當時認為自己已經(jīng)是比較嚴謹了，竟然也出現(xiàn)這樣的問題。通過這個小錯誤，我發(fā)現(xiàn)了自己的不足。以后在設(shè)計時要多多假設(shè)，未雨綢繆。爭取少、不出現(xiàn)錯誤。同時在此過程中我也獲得了很多的外援，來自老師的，同學的，還有網(wǎng)上論壇里面的網(wǎng)友的。通過這

72、樣的交流我真正理解了：天外有天，人外有人。這句話的深刻含義。俗話說得好：三個臭皮匠賽過諸葛亮。群眾的力量才是偉大的。以后我會盡量減少主觀上的意見，多多用客觀的眼觀看事物。</p><p><b>　　參考文獻</b></p><p>　　[1]李士勇，陳永強，李研.蟻群算法及其應(yīng)用 [M]. 哈爾濱: 哈爾濱工業(yè)大學出版社, 2004. 9–18.</p>

73、<p>　　[2]陳宏建，陳峻，徐曉華等.改進的增強型蟻群算法 [J]. 計算機工程, 2005，31(2): 176–178.</p><p>　　[3]葉志偉，鄭肇葆.蟻群算法中參數(shù)α、β、ρ設(shè)置的研究 [J]. 武漢大學學報, 2004，29(7): 577–601.</p><p><b>　　致 謝</b></p><p&