光傳輸陳巧媛1107400040羅琪1107400010姚正康1107400053李志恒1107400006

1、廣州大學機械與電氣工程學院課程設計報告設計題目:基于動態(tài)門限的波長分配算法 專業(yè)班級: 電信112 姓 名: 陳巧媛 羅琪 姚正康 李志恒學 號: 1107400040 1107400010 1107400053 1107400006 指導老師: 劉外喜 完成日期: 2015年1月7日 摘要 為了尋找一條適合的光通路，并合理地調(diào)配網(wǎng)絡資源，擴大現(xiàn)有的網(wǎng)絡資源的使用率，達到最大限度的增加通信通道的容量，降低完全分割策略波長分配算法導致的網(wǎng)絡擁塞。方法：引入動態(tài)門限的概念，利用基于遺傳算法的神經(jīng)網(wǎng)絡預測器求出門限值，根據(jù)實時網(wǎng)絡動態(tài)劃分各個波長子集。結(jié)果：動態(tài)門限可以對各個波長子集進行靈活劃分，解

2、決全分割策略波長路由分配的局限性，降低網(wǎng)絡擁塞的發(fā)生率。結(jié)論：該算法與分割策略波長分配算法相比，性能有了很大的改善，此算法在一定程度上降低完全分割策略波長分配算法導致的網(wǎng)絡擁塞，提高整個網(wǎng)絡的公平性。關鍵詞：遺傳算法 蟻群算法 動態(tài)門限的波長算法ABSTRACT In order to find a suitable optical path, and the rational allocation of the use ofcyber source, expanding their existing c

3、yber source rate, maximum increase communication channel capacity, reduce network congestion completelysegmentation strategy resulted in wavelength assignment algorithm. Method:introducing the concept of dynamic threshold, using the

4、60;genetic algorithmneural network predictor for out of limit value based on the network, according to the real-time dynamic dividing each wavelength subset. Results: thedynamic threshold can be flexibly divided for each wave

5、length subset, resolve the limitation of full segmentation strategy of routing and wavelength assignment, reduce the incidence of network congestion. Conclusion: compared with the algorithm of segmentation strategy wavelength assignmentalgo

6、rithm, performance has been greatly improved, this algorithm reduces thenetwork congestion completely segmentation strategy resulted in wavelength assignment algorithm in a certain extent, improve the fairness of the whole network.Keywords: wave

7、length algorithm genetic algorithm ant colony algorithmdynamic threshold目錄1、 實現(xiàn)功能.4 1.1遺傳算法.41.2蟻群算法.42、 實驗原理2.1遺傳算法.52.2蟻群算法.63、 功能及代碼及實驗結(jié)果3.1.1遺傳算法功能.73.1.2遺傳算法結(jié)果.93.1.3遺傳算法代碼.223.2.1蟻群算法功能.293.2.2蟻群算法結(jié)果.303.2.3蟻群算法代碼.31四、課程設計心得總結(jié).341、 實現(xiàn)功能 1. 1遺傳算法： 某個國家有N個城市，有一個商人希望能在每一個城市推銷他的產(chǎn)品，所以他希望能夠從某個城

8、市開始，把每個城市都走一遍，最后再回到一開始的地方?？墒沁@個國家的路費十分昂貴，所以他希望這么一趟下來走的總路程最短。接下來的實驗會用遺傳算法算出最優(yōu)的選擇方案。 1.2蟻群算法： 以求解個城市的旅行商問題為例，設蟻群中螞蟻的數(shù)量為,ij (,=1,2,)表示城市和城市之間的距離,i()表示時刻位于城市的螞蟻的個數(shù),則有 表示時刻在城市,連線上殘留的信息量.初始時刻,各條路徑上信息量相等,設(0)=(為常數(shù)).螞蟻(=1,2,)在運動過程中,根據(jù)各條路徑上的信息量決定轉(zhuǎn)移方向. 表示在時刻螞蟻由城市轉(zhuǎn)移到城市的概率.殘留信息的重要程度;啟發(fā)信息的重要程度;tabuk記錄螞蟻當前所走過的城市,稱

9、為記憶列表,=1,2,集合tabuk隨著進化過程作動態(tài)調(diào)整.經(jīng)過個時刻,所有螞蟻都完成了一次遍歷.此時,計算每一只螞蟻所走過的路徑,并保存最短路徑=1,2,.在螞蟻完成一次循環(huán)以后,各路徑上的信息量進行如下調(diào)整(+1)=(1-)()+   式中(0,1),表示信息素()隨時間的推移而衰減的程度.所以1-為信息素殘留因子，開始時（0）=0，         式中為螞蟻在本次循環(huán)中在城市和之間留下的信息量,它的計算公式根據(jù)具體問題而定.Dorigo曾給出3種不同的模型,分別稱為Ant-Cy

10、cle模型、Ant-Quantity模型、Ant-Density模型，它們的區(qū)別就在于信息素的更新機制,即其差別在于在Ant-Cycle模型中：    式中，Q表示信息素強度，它在一定程度上影響算法的收斂速度；Lk表示第K只螞蟻4）在本次循環(huán)中所奏路徑的總長度。在Ant-Quantity模型中： 式中，Q表示信息素強度，它在一定程度上影響算法的收斂速度；dij表示第K只螞蟻在t和t+1之間經(jīng)過的（ i, j ）在Ant-Density模型中：區(qū)別:式(5)式(6)中利用的是局部信息，即螞蟻完成一步后更新路徑上的信息素；而式(4)中利用的是整體信息，即螞蟻完成一個循

11、環(huán)后所有路徑上的信息素。經(jīng)過大量試驗總結(jié)研究，采用式(4)性能較好，所以 Ant-Cycle模型是最優(yōu)的。以上說明了信息素殘留因子1-、信息啟發(fā)式因子、期望啟發(fā)式因子、信息素強度Q、螞蟻數(shù)目M等都是非常重要的參數(shù)，其選區(qū)方式和選區(qū)原則直接影響到蟻群算法的全局收斂性和求解效率。我們學習到這種“三步走”2選擇蟻群算法最優(yōu)組合參數(shù)的有效方法：（1） 確定螞蟻數(shù)目M，根據(jù) 城市規(guī)模 / 螞蟻數(shù)目 1.5的選擇策略來確定螞蟻的總數(shù)目。（2） 參數(shù)粗調(diào)，即調(diào)整數(shù)值范圍較大的信息啟發(fā)式因子、期望啟發(fā)式因子、信息素強度Q等參數(shù)，已得到較理想的解。（3） 參數(shù)微調(diào)，即調(diào)整數(shù)值范圍較小的信息素殘留因子1-。2、

12、實驗原理 2.1遺傳算法： 遺傳算法是一個仿生學的算法。進化論認為地球上千奇百怪的生物都是進化而來的，如今能生存在地球上的生物是更適應于這個環(huán)境的，我們也可以說它們是被“優(yōu)化過”的。他們是怎么優(yōu)化的呢？在一個種群中，生物的差異主要來自于兩點，不同染色體之間的交叉結(jié)合以及染色體自發(fā)的隨機變異。這些差異實際上是隨機發(fā)生的，但是生物的外部生存環(huán)境會通過生存與死亡讓更能適應的個體存活下去。因此隨著時間的推移，生物種群對環(huán)境的適應能力會越來越高。受到這個現(xiàn)象的啟發(fā)，有人發(fā)明了遺傳算法，通過模擬遺傳的過程來解決一些優(yōu)化問題。 我們假設需要解決的問題空間類似于地球生物圈，問題的一個可能解也就被類比成一條有多

13、個基因的染色體。作為簡化，我們認為一條染色體就代表了一個生物，另一方面，你也可以理解為生物進化的勝利實質(zhì)上也是染色體的進化勝利。首先我們要有初始的生命種子，即一些隨機的染色體，然后我們對這些染色體定義“繁殖”、“突變”和“死亡”的概念，就能夠讓它們在這個空間里自由發(fā)展?！胺敝场敝傅氖莾蓷l染色體之間產(chǎn)生相互而變化，生成新的染色體的過程；“突變”指的是每條染色體都可能以微小的概率改變自己的基因的過程；“死亡”就是把某條染色體從種群中移除，也就是被淘汰了。那么我們怎么衡量每一條染色體是不是比它的小伙伴活得更自在呢？我們可以針對具體的環(huán)境，定義一個適應度函數(shù)，用來評估每個染色體對這個環(huán)境的適應程度，然

14、后以這個適應程度為權(quán)重決定它們是否能活到下一代。下表是生物和算法中的概念關系的總結(jié)：*問題的一個解染色體*問題的背景生物圈環(huán)境*解的適應度染色體在這個環(huán)境下的生存幾率*構(gòu)成解的基本單元基因*解和解之間的基本單元交換繁殖*單個解自己的基本單元變化突變*不再考慮某個解死亡 因為孕育了生命的地球一直以來都沒有變成火星，也沒有變成金星，是一個相對固定的環(huán)境。遺傳算法在此基礎上發(fā)展而來，它也不是什么問題都適用的，而是需要在一個相對固定的環(huán)境里面進行發(fā)展。如果我們每一步的決策會改變當前的局勢（比如下棋這樣和對手交互的游戲），那么我認為這時遺傳算法不是最合適的，頂多只能夠用在其中一個子問題當中。比如R的sk

15、means算法就有遺傳算法在每一步迭代中優(yōu)化的版本。有一些問題的大環(huán)境是不變的，我們可以在上面利用遺傳算法求解。對于某一個特定的迷宮，我們可以認為每次往哪個方向前進是構(gòu)成解的基本單元，這些基本單元連在一起就成為了一個解，借助據(jù)此行動之后離出口的曼哈頓距離還可以定義適應度。又比如在一個n維空間內(nèi)部搜索某個確切函數(shù)的最大值時，我們可以將每一維的坐標作為基本單元，某個點就是一條n個基本單元構(gòu)成的解，這個點的函數(shù)值便是適應度。除去這些比較老舊的話題，我們還有更好玩的例子，就是讓一群自行車在地圖上面跑，希望得到在這個地圖上跑得最遠的（還有多輛車同時競賽的版本）。在這個例子中，自行車的輪胎數(shù)量、大小以及其

16、中的連接結(jié)構(gòu)分別是一個解的不同基本單元，它們能夠構(gòu)成一個自行車，適應度函數(shù)則是程序模擬過后的最大行駛距離。 2.2蟻群算法： 自1991年由意大利學者 M. Dorigo，V. Maniezzo 和 A. Colorni 通過模擬蟻群覓食行為提出了一種基于種群的模擬進化算法蟻群優(yōu)化。該算法的出現(xiàn)引起了學者們的極大關注，蟻群算法的特點：    其原理是一種正反饋機制或稱增強型學習系統(tǒng); 它通過【最優(yōu)路徑上螞蟻數(shù)量的增加信息素強度增加后來螞蟻選擇概率增大最優(yōu)路徑上螞蟻數(shù)量更大增加】達到最終收斂于最優(yōu)路徑上L 它是一種通用型隨機優(yōu)化方法, 它吸收了螞蟻的行為特(內(nèi)在搜索

17、機制) , 它是使用人工螞蟻仿真(也稱螞蟻系統(tǒng)) 來求解問題L但人工螞蟻決不是對實際螞蟻的一種簡單模擬, 它融進了人類的智能L人工螞蟻有一定的記憶; 人工螞蟻不完全是瞎的; 人工螞蟻生活的時空是離散的L 它是一種分布式的優(yōu)化方法, 不僅適合目前的串行計算機, 而且適合未來的并行計算機L 它是一種全局優(yōu)化的方法, 不僅可用于求解單目標優(yōu)化問題, 而且可用于求解多目標優(yōu)化問題L 它是一種啟發(fā)式算法, 計算復雜性為o (Nc*n2*m) , 其中Nc 是迭代次數(shù), m 是螞蟻數(shù)目, n 是目的節(jié)點數(shù)目L本圖螞蟻從A點出發(fā)，速度相同，食物在D點，可能隨機選擇路線ABD或ACD。假設初始時每條分配路線一

18、只螞蟻，每個時間單位行走一步，本圖為經(jīng)過9個時間單位時的情形：走ABD的螞蟻到達終點，而走ACD的螞蟻剛好走到C點，為一半路程本圖為從開始算起，經(jīng)過18個時間單位時的情形：走ABD的螞蟻到達終點后得到食物又返回了起點A，而走ACD的螞蟻剛好走到D點。3、 功能及代碼3.1遺傳算法（1）評分與淘汰： 通常來講，我們會給這一代種群的每個染色體賦予一個值，然后以這個值為權(quán)重作為染色體的存活概率。因為旅行商問題希望得到越小越好的連線，因此我們應該認為距離反比于每條染色體的存活率。我一開始粗糙地求出這個地圖的一個上界，然后讓存活率正比于每個染色體的距離與這個上界的差。后來發(fā)現(xiàn)以一個常數(shù)作為上界太粗糙了，

19、應該與時俱進，所以我將這個上界改了一下，定義為當前種群中最長距離加一的值。 我假設整個族群的個體數(shù)量是偶數(shù)，然后每次以存活概率進行抽樣，只留下一半的種群用以繁殖出另一半。（2） 繁殖： 繁殖的方案有很多種選擇，我這里的方案是自己隨意定下來的，沒有經(jīng)過嚴格而仔細的比較，并不能保證是最優(yōu)的。 在淘汰部分所述的假設前提下，我們有一半的族群來繁殖另一半。首先我將所有存活的染色體復制一份，然后讓它們隨機與原染色體進行繁殖。 對于兩條云雨過后的染色體a和b，我一開始是這樣定義它們的子代的：數(shù)量m代表繁殖中可能會變化的基因數(shù)量，隨機選擇a的m個位置，將這些位置上面的基因按照b中的順序排列后放回。但是實際上這

20、個問題里的相鄰基因之間有著非常密切的關系，這樣的查找實際上只是一個隨機搜索罷了，不能起到很快收斂到更優(yōu)排列的作用。于是我改進了子代的定義：數(shù)量m仍然代表繁殖中可能會變化的基因數(shù)量，不過我先隨機選擇a的一個位置，將這個位置開始之后的m個連續(xù)基因按照b中的順序排列后放回，即造成一段連續(xù)的變化。這樣這個方法就更有“目的性”，更容易對一個局部區(qū)域找到更好的連接方式。（3） 變異：對于每條染色體，我希望每次至多只有一個基因會產(chǎn)生變異，這個基因是這樣選出來的：事先設定一個概率p，然后生成長度等于染色體基因數(shù)的均勻分布隨機數(shù)列，挑出所有小于概率p的基因（如果有的話），再在它們當中選擇一個即可。選出這個基因之

21、后，我再挑出另一個基因并交換它們。這并沒有很好地照顧基因前后之間的關聯(lián)性，所以我改進了一下變異的方法：我挑出另一個基因之后，將之前選出要變異的基因插入到這個位置上，就像往鏈表中加入元素一樣。（4） 跳出局部最優(yōu)： 在實驗中發(fā)現(xiàn)，到了后期算法開始無法突破瓶頸，可能需要很多次的迭代才能得到一個微小的進步。這種情況也許是算法效率上的問題，也許是陷入了一個難以再大踏步進化的局部最優(yōu)中。為了從這樣的情況下跳出來，我嘗試了許多的算法，這里就不贅述了，直接說一下我最后改進到的算法。 為了跳出局部最優(yōu)，我選擇了“滅絕”的方法，就是在一定的條件下將最厲害的精英殺死。如果超過了一定的步驟N，當前的族群仍然固步自封

22、，我就將最好的一個或幾個染色體殺死，用族群內(nèi)部的次好染色體代替他們，并繼續(xù)進化下去。但是這樣單純地殺死精英有點浪費，所以我選擇將被滅絕的精英儲存起來。當我儲存夠了K個精英時，就將它們?nèi)坚尫懦鰜?，在幾匹不同意義的好馬同時出現(xiàn)時就有可能催生出一匹強力的超級小馬。經(jīng)過實驗，效率最高的應該是K=2。每次釋放精英我都稱作一個“時代”。這里“一定的步驟”N也是隨著時代增加而不斷增加的。（5） 實驗結(jié)果： 如果使用完全隨機的地圖，旅行商問題是很難通過人眼看出“這種方案離最優(yōu)解的差距還有多遠”的。所以我在單位圓上等間距地生成了100個點，以此作為地圖，這樣便能通過人眼來比較當前方案的優(yōu)劣程度。 下面的圖就是

23、在這個地圖上應用遺傳算法的全程進化過程展示，我經(jīng)過0.5秒截一次圖?？梢钥闯?，一開始的一萬代能夠很快地從一個隨機的情況進化到一個較好的結(jié)果，之后效率則會有明顯的下降了，而最后的幾次進化則花費了非常久的時間。（6）R語言代碼： #生成隨機地圖getMap = function(n,xlim=c(0,1),ylim=c(0,1)x = runif(n,xlim1,xlim2)y = runif(n,ylim1,ylim2)ans = as.matrix(dist(cbind(x,y)return(list(x=x,y=y,ans=ans)#生成單位圓地圖getRoundMap = function

24、(n)theta = seq(0,2*pi,length.out=n+1)1:nx = cos(theta)y = sin(theta)ans = as.matrix(dist(cbind(x,y)return(list(x=x,y=y,ans=ans)#粗糙地計算總路程上界UpperBound = function(disM)mx = apply(disM,1,max)return( sum(mx) )#生成隨機染色體rndDNA = function(n)return( sample(1:n,n) )#對一個解計算總路程的距離calcScores = function(dna,disM)n

25、 = length(dna)tmp = cbind(dna1:n,c(dna2:n,dna1)len = apply(tmp,1,function(x) disMx1,x2)len = sum(len)return(len)#根據(jù)每條染色體的分數(shù)計算權(quán)重，并以此抽樣roller = function(scores,k)scores = max(scores)-scores+1props = scores/sum(scores)N = length(scores)mxind = which.max(scores)#保留最優(yōu)染色體ans = sample(1:N)-mxind,k-1,replac

26、e = F,prob = props-mxind)return(c(mxind,ans)#種群中的繁殖過程crossEvolve = function(i,nGroup,crossGroup,prop)a = nGroupi,b = crossGroupi,n = length(a)m = max(1,trunc(n*prop)tmpa = ast = sample(1:n,1)ind = st:(st+m)if (st+m>n)bind = which(ind>n)indbind = indbind % n + 1cross = intersect(b,aind)tmpaind

27、= crossreturn(tmpa)#染色體的自我變異selfVariation = function(dna,prop)n = length(dna)pos = which(runif(n)<prop)if (length(pos)=0)return(dna)pos = sample(pos,1)newind = sample(1:n)-pos,1)if (pos>newind)tmp = dnanewind:ntmp = tmp-(pos-newind+1)dnanewind = dnaposdna(newind+1):n = tmpelsetmp = dna1:newind

28、tmp = tmp-posdnanewind = dnaposdna1:(newind-1) = tmpreturn(dna)#以某條染色體代表的解做圖drawIt = function(dots,dna,xlab=NULL,ylab=NULL,main=NULL,sub=NULL)x = dots1y = dots2if (is.null(main)scores = calcScores(dna,dots3)plot(x,y,main=as.character(scores)elseplot(x,y,main=main,xlab=xlab,ylab=ylab,sub=sub)n = leng

29、th(dna)for (i in 1:(n-1) lines(xdnai:(i+1),ydnai:(i+1)lines(xdnac(n,1),ydnac(n,1)#結(jié)尾部分的動畫函數(shù)，其中的具體參數(shù)需要變動saveAnimation = function(species,dots,sleep=0.1)require(animation)scores = apply(species1,1,calcScores,dots3)n = length(scores)oopt = ani.options(interval = sleep, nmax = 10000, ani.width = 560, an

30、i.height = 600)saveGIF(for (i in 1:5)drawIt(dots,species11,xlab='',ylab='',main=scores1,sub=paste('Generation:',species21)for (i in 1:9)drawIt(dots,species1i*20,xlab='',ylab='',main=scoresi*20,sub=paste('Generation:',species2i*20)for (i in 19:28)drawIt

31、(dots,species1i*10,xlab='',ylab='',main=scoresi*10,sub=paste('Generation:',species2i*10)for (i in 290:410)if (i % 3 = 0 )drawIt(dots,species1i,xlab='',ylab='',main=scoresi,sub=paste('Generation:',species2i)for (i in 411:443)if (i % 2 = 0 )for (j in 1:2

32、)drawIt(dots,species1i,xlab='',ylab='',main=scoresi,sub=paste('Generation:',species2i)for (i in 444:453)for (j in 1:5)drawIt(dots,species1i,xlab='',ylab='',main=scoresi,sub=paste('Generation:',species2i)for (i in 1:20)drawIt(dots,species1n,xlab='&#

33、39;,ylab='',main=scoresn,sub=paste('Generation:',species2n)#Genetic Algorithm for Traveller Salesman ProblemGA4TSP = function(dots,initDNA=NULL,N,cp,vp,maxIter,maxStay,maxElite,drawing)disM = dots3n = nrow(disM)if (N %2 >0)N = N+1Group = t(sapply(rep(n,N),rndDNA)if (!is.null(initD

34、NA)if (is.null(initDNA)Group1,=initDNAelseif (nrow(initDNA)>N)initDNA = initDNA1:N,Group1:nrow(initDNA),=initDNAmaxL = UpperBound(disM)stopFlag = FALSEiterCount = 1stayCount = 0allBest = maxLeliteBest = maxLelite = mat.or.vec(maxElite,n)elitecount = 0eracount = 0LastEra = maxLoutputRecorder = NUL

35、LGenerationRecorder = NULLshowScore=FALSEeliteInto=FALSE#初始化結(jié)束while (!stopFlag)cat('Generation:',iterCount,'Era:',eracount,'Elite:',elitecount)scores = apply(Group,1,calcScores,disM)bestScore = min(scores)mind = which.min(scores)bestDNA = Groupmind,#記錄最佳染色體#更新時代、精英的信息if (best

36、Score<eliteBest)stayCount = 0eliteBest = bestScoreeliteDNA = bestDNAif (eliteBest<allBest)allBest = eliteBestallDNA = eliteDNAoutputRecorder = rbind(outputRecorder,allDNA)GenerationRecorder = c(GenerationRecorder,iterCount)if (drawing)drawIt(dots,allDNA,main=as.character(allBest)elsestayCount

37、= stayCount+1if (stayCount = maxStay)stayCount = 0eliteBest = maxLelitecount = elitecount+1eliteelitecount, = eliteDNAscores = apply(Group,1,calcScores,disM)a = which(scores = min(scores)nind = sample(1:N)-a,length(a)Groupa, = Groupnind,eliteInto =TRUEscores = apply(Group,1,calcScores,disM)bestScore

38、 = min(scores)mind = which.min(scores)bestDNA = Groupmind,if (elitecount=maxElite)Group1:elitecount,=eliteelite = mat.or.vec(maxElite,n)elitecount = 0stayCount = 0eliteBest = maxLeracount = eracount+1maxStay = maxStay + 50showScore=TRUEscores = apply(Group,1,calcScores,disM)bestScore = min(scores)mi

39、nd = which.min(scores)bestDNA = Groupmind,#對種群計算分數(shù)，產(chǎn)生繁殖與變異succind = roller(scores,N/2)nGroup = Groupsuccind,crossind = sample(succind,N/2)crossGroup = Groupcrossind,crossans = t(sapply(1:(N/2),crossEvolve,nGroup,crossGroup,cp)crossGroup = rbind(nGroup,crossans)Group = t(apply(crossGroup,1,selfVariat

40、ion,vp)if (eliteInto)eliteInto = FALSEelseGroup1, = bestDNA stopFlag = (iterCount>=maxIter)iterCount = iterCount+1cat(' Best:',bestScore,'All:',allBest,'Stay:',paste(stayCount,'/',maxStay,sep=''),'n')if (showScore)scores = apply(Group,1,calcScores,d

41、isM)show(scores1:(N/2)show(scores(N/2+1):(N)Sys.sleep(5)showScore=FALSEif (drawing)drawIt(dots,allDNA)return(list(DNA = outputRecorder,Generation=GenerationRecorder)roundots = getRoundMap(100)system.time( species = GA4TSP(dots=roundots,initDNA=NULL,N=50,cp=0.1,vp=0.01,maxIter=50000,maxStay=50,maxEli

42、te=2,drawing=TRUE) )#require(TSP)#data("USCA50")#tsp <- USCA50#system.time( species = GA4TSP(dots=list(a=NULL,b=NULL,disM=as.matrix(tsp),initDNA=NULL,N=50,cp=0.1,vp=0.01,maxIter=50000,maxStay=50,maxElite=2,drawing=FALSE) ) 3.2蟻群算法：目前蟻群算法的應用：雖然對蟻群算法的研究時間不長, 但是初步研究已顯示出它在求解復雜優(yōu)化問題方面具有很大的優(yōu)勢,

43、 特別是1998 年在比利時布魯塞爾專門召開了第一屆螞蟻優(yōu)化國際研討會后, 現(xiàn)在每兩年召開一次這樣的螞蟻優(yōu)化國際研討會。這標志著蟻群算法的研究已經(jīng)得到了國際上的廣泛支持，使得這種新興的智能進化仿生算法展現(xiàn)出了勃勃生機3。以蟻群算法為代表的群體智能已成為當今分布式人工智能研究的一個熱點,許多源于蜂群和蟻群模型設計的算法已越來越多地被用于企業(yè)的運轉(zhuǎn)模式的研究。美國五角大樓正在資助關于群體智能系統(tǒng)的研究工作-群體戰(zhàn)略(SWARM STRATEGY),它的一個實戰(zhàn)用途是通過運用成群的空中無人駕駛飛行器和地面車輛來轉(zhuǎn)移敵人的注意力,讓自己的軍隊在敵人后方不被察覺地安全行進。英國電信公司和美國世界通信公司

44、以電子螞蟻為基礎,對新的電信網(wǎng)絡管理方法進行了試驗。群體智能還被應用于工廠生產(chǎn)計劃的制定和運輸部門的后勤管理。美國太平洋西南航空公司采用了一種直接源于螞蟻行為研究成果的運輸管理軟件,結(jié)果每年至少節(jié)約了1000萬美元費用開支。英國聯(lián)合利華公司已率先利用群體智能技術改善其一家牙膏廠的運轉(zhuǎn)狀況。美國通用汽車公司,法國液氣公司,荷蘭公路交通部和美國一些移民事務機構(gòu)也都采用這種技術來改善其運轉(zhuǎn)的機能。又如美國MCIW公司一直研究人工螞蟻，并用于管理公司的電話網(wǎng)，對用戶記賬收費等工作。另外，還設計“人工螞蟻”打算用于因特網(wǎng)的路由管理。鑒于群體智能廣闊的應用前景,美國和歐洲聯(lián)盟均于近幾年開始出資資助基于群體

45、智能模擬的相關研究項目, 關在一些院校開設群體智能的相關課程.牛津大學出版社1999年版的E.Bonabeau和M.Dorigo等人編寫的專著群體智能:從自然到人工系統(tǒng)(Swarm Intelligence:From Natural to Artificial System),以及2001年出版的J.Kennedy和R.Eberhart編著的群體智能(Swarm Intelligence)進一步擴大了群體智能的影響.IEEE進化計算會刊也于2002年8月出版了蟻群優(yōu)化算特刊。國內(nèi)也有研究者用螞蟻算法求解全國144個城市的最短回路問題，求得的解同其它方法求到得解一樣精確，這說明螞蟻算法不但是求解

46、組合優(yōu)化問題的可行方法，而且是一種很有競爭力的算法。國家自然科學基金"十五"期間學科交叉類優(yōu)先資助領域中的認知科學及其信息處理的研究內(nèi)容中也明確列出了群體智能領域的進化,自適應與現(xiàn)場認知主題4。而且從1999年開始，幾乎每年都會有幾項相關項目獲得資助。蟻群算法是一種新型的模擬進化算法，其在數(shù)據(jù)挖掘中的應用正逐步引起人們的關注。目前，人工蟻群在知識發(fā)現(xiàn)的過程中主要用于發(fā)掘聚類模型和分類模型。代碼：（1） 算法代碼：function R_best,L_best,L_ave,Shortest_Route,Shortest_Length=ACATSP(C,NC_max,m,Alph

47、a,Beta,Rho,Q)%-% 主要符號說明% C n個城市的坐標，n×2的矩陣% NC_max 最大迭代次數(shù)% m 螞蟻個數(shù)% Alpha 表征信息素重要程度的參數(shù)% Beta 表征啟發(fā)式因子重要程度的參數(shù)% Rho 信息素蒸發(fā)系數(shù)% Q 信息素增加強度系數(shù)% R_best 各代最佳路線% L_best 各代最佳路線的長度%=%第一步：變量初始化n=size(C,1);%n表示問題的規(guī)模（城市個數(shù)）D=zeros(n,n);%D表示完全圖的賦權(quán)鄰接矩陣for i=1:nfor j=1:nif i=jD(i,j)=(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)2)0.

48、5;elseD(i,j)=eps;%i=j時不計算，應該為0，但后面的啟發(fā)因子要取倒數(shù)，用eps（浮點相對精度）表示endD(j,i)=D(i,j);%對稱矩陣endendEta=1./D;%Eta為啟發(fā)因子，這里設為距離的倒數(shù)Tau=ones(n,n);%Tau為信息素矩陣Tabu=zeros(m,n);%存儲并記錄路徑的生成NC=1;%迭代計數(shù)器，記錄迭代次數(shù)R_best=zeros(NC_max,n);%各代最佳路線L_best=inf.*ones(NC_max,1);%各代最佳路線的長度L_ave=zeros(NC_max,1);%各代路線的平均長度while NC<=NC_ma

49、x%停止條件之一：達到最大迭代次數(shù)，停止%第二步：將m只螞蟻放到n個城市上Randpos=;%隨即存取for i=1:(ceil(m/n)Randpos=Randpos,randperm(n);endTabu(:,1)=(Randpos(1,1:m)'%此句不太理解？%第三步：m只螞蟻按概率函數(shù)選擇下一座城市，完成各自的周游for j=2:n%所在城市不計算for i=1:mvisited=Tabu(i,1:(j-1); %記錄已訪問的城市，避免重復訪問J=zeros(1,(n-j+1);%待訪問的城市P=J;%待訪問城市的選擇概率分布Jc=1;for k=1:nif length(find(visited=k)=0%開始時置0J(Jc)=k;J