仿生算法小結(jié)

1、PSO粒子群優(yōu)化算法引言粒子群優(yōu)化算法(PSO)是一種進(jìn)化計(jì)算技術(shù)(evolutionarycomputation),由Eberhart博士和kennedy博士發(fā)明。源于對(duì)鳥(niǎo)群捕食的行為研究PSO同遺傳算法類似，是一種基于迭代的優(yōu)化工具。系統(tǒng)初始化為一組隨機(jī)解，通過(guò)迭代搜尋最優(yōu)值。但是并沒(méi)有遺傳算法用的交叉(crossover)以及變異(mutation)。而是粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索。詳細(xì)的步驟以后的章節(jié)介紹同遺傳算法比較，PSO的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)并且沒(méi)有許多參數(shù)需要調(diào)整。目前已廣泛應(yīng)用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域2.背景:人工生命人工生命是

2、來(lái)研究具有某些生命基本特征的人工系統(tǒng).人工生命包括兩方面的內(nèi)容研究如何利用計(jì)算技術(shù)研究生物現(xiàn)象研究如何利用生物技術(shù)研究計(jì)算問(wèn)題我們現(xiàn)在關(guān)注的是第二部分的內(nèi)容.現(xiàn)在已經(jīng)有很多源于生物現(xiàn)象的計(jì)算技巧.例如,人工神經(jīng)網(wǎng)絡(luò)是簡(jiǎn)化的大腦模型.遺傳算法是模擬基因進(jìn)化過(guò)程的.現(xiàn)在我們討論另一種生物系統(tǒng)-社會(huì)系統(tǒng).更確切的是,在由簡(jiǎn)單個(gè)體組成的群落與環(huán)境以及個(gè)體之間的互動(dòng)行為.也可稱做群智能(swarmintelligence).這些模擬系統(tǒng)利用局部信息從而可能產(chǎn)生不可預(yù)測(cè)的群體行為例如floys和boids,他們都用來(lái)模擬魚(yú)群和鳥(niǎo)群的運(yùn)動(dòng)規(guī)律,主要用于計(jì)算機(jī)視覺(jué)和計(jì)算機(jī)輔助設(shè)計(jì).在計(jì)算智能(computat

3、ionalintelligence)領(lǐng)域有兩種基于群智能的算法.蟻群算法(antcolonyoptimization)和粒子群算法(particleswarmoptimization).前者是對(duì)螞蟻群落食物采集過(guò)程的模擬.已經(jīng)成功運(yùn)用在很多離散優(yōu)化問(wèn)題上.粒子群優(yōu)化算法(PSO)也是起源對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬最初設(shè)想是模擬鳥(niǎo)群覓食的過(guò)程但后來(lái)發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具.算法介紹如前所述，PSO模擬鳥(niǎo)群的捕食行為。設(shè)想這樣一個(gè)場(chǎng)景：一群鳥(niǎo)在隨機(jī)搜索食物。在這個(gè)區(qū)域里只有一塊食物。所有的鳥(niǎo)都不知道食物在那里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢。最簡(jiǎn)單有效的就是搜

4、尋目前離食物最近的鳥(niǎo)的周圍區(qū)域。PSO從這種模型中得到啟示并用于解決優(yōu)化問(wèn)題。PSO中，每個(gè)優(yōu)化問(wèn)題的解都是搜索空間中的一只鳥(niǎo)。我們稱之為“粒子”所有的例子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值(fitnessvalue)，每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索PSO初始化為一群隨機(jī)粒子(隨機(jī)解)。然后通過(guò)疊代找到最優(yōu)解。在每一次疊代中，粒子通過(guò)跟蹤兩個(gè)極值來(lái)更新自己。第一個(gè)就是粒子本身所找到的最優(yōu)解。這個(gè)解叫做個(gè)體極值pBest.另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解。這個(gè)極值是全局極值gBest。另外也可以不用整個(gè)種群而只是用其中一部分最為粒子

5、的鄰居，那么在所有鄰居中的極值就是局部極值程序的偽代碼如下ForeachparticleInitializeparticleENDDoForeachparticleCalculatefitnessvalueIfthefitnessvalueisbetterthanthebestfitnessvalue(pBest)inhistorysetcurrentvalueasthenewpBestEndChoosetheparticlewiththebestfitnessvalueofalltheparticlesasthegBestForeachparticleCalculateparticlevel

6、ocityaccordingequation(a)Updateparticlepositionaccordingequation(b)EndWhilemaximumiterationsorminimumerrorcriteriaisnotattained在每一維粒子的速度都會(huì)被限制在一個(gè)最大速度Vmax，如果某一維更新后的速度超過(guò)用戶設(shè)定的Vmax，那么這一維的速度就被限定為Vmax4.遺傳算法和PSO的比較大多數(shù)演化計(jì)算技術(shù)都是用同樣的過(guò)程種群隨機(jī)初始化對(duì)種群內(nèi)的每一個(gè)個(gè)體計(jì)算適應(yīng)值(fitnessvalue).適應(yīng)值與最優(yōu)解的距離直接有關(guān)種群根據(jù)適應(yīng)值進(jìn)行復(fù)制如果終止條件滿足的話，就停止，

7、否則轉(zhuǎn)步驟2從以上步驟，我們可以看到PSO和GA有很多共同之處。兩者都隨機(jī)初始化種群，而且都使用適應(yīng)值來(lái)評(píng)價(jià)系統(tǒng)，而且都根據(jù)適應(yīng)值來(lái)進(jìn)行一定的隨機(jī)搜索。兩個(gè)系統(tǒng)都不是保證一定找到最優(yōu)解但是，PSO沒(méi)有遺傳操作如交叉(crossover閑變異(mutation).而是根據(jù)自己的速度來(lái)決定搜索。粒子還有一個(gè)重要的特點(diǎn)，就是有記憶。與遺傳算法比較，PSO的信息共享機(jī)制是很不同的.在遺傳算法中，染色體(chromosomes)互相共享信息，所以整個(gè)種群的移動(dòng)是比較均勻的向最優(yōu)區(qū)域移動(dòng).在PSO中,只有g(shù)Best(orlBest)給出信息給其他的粒子，這是單向的信息流動(dòng).整個(gè)搜索更新過(guò)程是跟隨當(dāng)前最優(yōu)解

8、的過(guò)程.與遺傳算法比較,在大多數(shù)的情況下，所有的粒子可能更快的收斂于最優(yōu)解5.人工神經(jīng)網(wǎng)絡(luò)和PSO人工神經(jīng)網(wǎng)絡(luò)(ANN)是模擬大腦分析過(guò)程的簡(jiǎn)單數(shù)學(xué)模型，反向轉(zhuǎn)播算法是最流行的神經(jīng)網(wǎng)絡(luò)訓(xùn)練算法。進(jìn)來(lái)也有很多研究開(kāi)始利用演化計(jì)算(evolutionarycomputation)技術(shù)來(lái)研究人工神經(jīng)網(wǎng)絡(luò)的各個(gè)方面。演化計(jì)算可以用來(lái)研究神經(jīng)網(wǎng)絡(luò)的三個(gè)方面：網(wǎng)絡(luò)連接權(quán)重，網(wǎng)絡(luò)結(jié)構(gòu)(網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，傳遞函數(shù))，網(wǎng)絡(luò)學(xué)習(xí)算法。不過(guò)大多數(shù)這方面的工作都集中在網(wǎng)絡(luò)連接權(quán)重，和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上。在GA中，網(wǎng)絡(luò)權(quán)重和/或拓?fù)浣Y(jié)構(gòu)一般編碼為染色體(Chromosome)，適應(yīng)函數(shù)(fitnessfunction)的選擇一

9、般根據(jù)研究目的確定。例如在分類問(wèn)題中，錯(cuò)誤分類的比率可以用來(lái)作為適應(yīng)值演化計(jì)算的優(yōu)勢(shì)在于可以處理一些傳統(tǒng)方法不能處理的例子例如不可導(dǎo)的節(jié)點(diǎn)傳遞函數(shù)或者沒(méi)有梯度信息存在。但是缺點(diǎn)在于：在某些問(wèn)題上性能并不是特別好。2.網(wǎng)絡(luò)權(quán)重的編碼而且遺傳算子的選擇有時(shí)比較麻煩最近已經(jīng)有一些利用PSO來(lái)代替反向傳播算法來(lái)訓(xùn)練神經(jīng)網(wǎng)絡(luò)的論文。研究表明PSO是一種很有潛力的神經(jīng)網(wǎng)絡(luò)算法。PSO速度比較快而且可以得到比較好的結(jié)果。而且還沒(méi)有遺傳算法碰到的問(wèn)題這里用一個(gè)簡(jiǎn)單的例子說(shuō)明PSO訓(xùn)練神經(jīng)網(wǎng)絡(luò)的過(guò)程。這個(gè)例子使用分類問(wèn)題的基準(zhǔn)函數(shù)(Benchmarkfunction)IRIS數(shù)據(jù)集。(Iris是一種鳶尾屬植物)

10、在數(shù)據(jù)記錄中，每組數(shù)據(jù)包含Iris花的四種屬性：萼片長(zhǎng)度，萼片寬度，花瓣長(zhǎng)度，和花瓣寬度，三種不同的花各有50組數(shù)據(jù).這樣總共有150組數(shù)據(jù)或模式。我們用3層的神經(jīng)網(wǎng)絡(luò)來(lái)做分類?，F(xiàn)在有四個(gè)輸入和三個(gè)輸出。所以神經(jīng)網(wǎng)絡(luò)的輸入層有4個(gè)節(jié)點(diǎn)，輸出層有3個(gè)節(jié)點(diǎn)我們也可以動(dòng)態(tài)調(diào)節(jié)隱含層節(jié)點(diǎn)的數(shù)目，不過(guò)這里我們假定隱含層有6個(gè)節(jié)點(diǎn)。我們也可以訓(xùn)練神經(jīng)網(wǎng)絡(luò)中其他的參數(shù)。不過(guò)這里我們只是來(lái)確定網(wǎng)絡(luò)權(quán)重。粒子就表示神經(jīng)網(wǎng)絡(luò)的一組權(quán)重，應(yīng)該是4*6+6*3=42個(gè)參數(shù)。權(quán)重的范圍設(shè)定為-100，100(這只是一個(gè)例子，在實(shí)際情況中可能需要試驗(yàn)調(diào)整).在完成編碼以后，我們需要確定適應(yīng)函數(shù)。對(duì)于分類問(wèn)題，我們把所有的

11、數(shù)據(jù)送入神經(jīng)網(wǎng)絡(luò)，網(wǎng)絡(luò)的權(quán)重有粒子的參數(shù)決定。然后記錄所有的錯(cuò)誤分類的數(shù)目作為那個(gè)粒子的適應(yīng)值。現(xiàn)在我們就利用PSO來(lái)訓(xùn)練神經(jīng)網(wǎng)絡(luò)來(lái)獲得盡可能低的錯(cuò)誤分類數(shù)目。PSO本身并沒(méi)有很多的參數(shù)需要調(diào)整。所以在實(shí)驗(yàn)中只需要調(diào)整隱含層的節(jié)點(diǎn)數(shù)目和權(quán)重的范圍以取得較好的分類效果。6.PSO的參數(shù)設(shè)置從上面的例子我們可以看到應(yīng)用PSO解決優(yōu)化問(wèn)題的過(guò)程中有兩個(gè)重要的步驟:問(wèn)題解的編碼和適應(yīng)度函數(shù)PSO的一個(gè)優(yōu)勢(shì)就是采用實(shí)數(shù)編碼,不需要像遺傳算法一樣是二進(jìn)制編碼(或者采用針對(duì)實(shí)數(shù)的遺傳操作.例如對(duì)于問(wèn)題f(x)=x1A2+x2A2+x3A2求解，粒子可以直接編碼為(x1,x2,x3),而適應(yīng)度函數(shù)就是f(x)

12、.接著我們就可以利用前面的過(guò)程去尋優(yōu).這個(gè)尋優(yōu)過(guò)程是一個(gè)疊代過(guò)程,中止條件一般為設(shè)置為達(dá)到最大循環(huán)數(shù)或者最小錯(cuò)誤PSO中并沒(méi)有許多需要調(diào)節(jié)的參數(shù),下面列出了這些參數(shù)以及經(jīng)驗(yàn)設(shè)置粒子數(shù)：一般取20-40.其實(shí)對(duì)于大部分的問(wèn)題10個(gè)粒子已經(jīng)足夠可以取得好的結(jié)果，不過(guò)對(duì)于比較難的問(wèn)題或者特定類別的問(wèn)題,粒子數(shù)可以取到100或200粒子的長(zhǎng)度:這是由優(yōu)化問(wèn)題決定,就是問(wèn)題解的長(zhǎng)度粒子的范圍:由優(yōu)化問(wèn)題決定,每一維可是設(shè)定不同的范圍Vmax:最大速度,決定粒子在一個(gè)循環(huán)中最大的移動(dòng)距離,通常設(shè)定為粒子的范圍寬度,例如上面的例子里，粒子(x1,x2,x3)x1屬于-10,10,那么Vmax的大小就是20學(xué)

13、習(xí)因子:c1和c2通常等于2.不過(guò)在文獻(xiàn)中也有其他的取值.但是一般c1等于c2并且范圍在0和4之間中止條件:最大循環(huán)數(shù)以及最小錯(cuò)誤要求.例如,在上面的神經(jīng)網(wǎng)絡(luò)訓(xùn)練例子中,最小錯(cuò)誤可以設(shè)定為1個(gè)錯(cuò)誤分類,最大循環(huán)設(shè)定為2000,這個(gè)中止條件由具體的問(wèn)題確定.全局PSO和局部PSO:我們介紹了兩種版本的粒子群優(yōu)化算法:全局版和局部版.前者速度快不過(guò)有時(shí)會(huì)陷入局部最優(yōu).后者收斂速度慢一點(diǎn)不過(guò)很難陷入局部最優(yōu).在實(shí)際應(yīng)用中,可以先用全局PSO找到大致的結(jié)果，再有局部PSO進(jìn)行搜索.另外的一個(gè)參數(shù)是慣性權(quán)重，由Shi和Eberhart提出，有興趣的可以參考他們1998年的論文(題目:Amodifiedp

14、articleswarmoptimizer)蟻群算法簡(jiǎn)介：蟻群算法(antcolonyoptimization,ACO)，又稱螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型技術(shù)。它由MarcoDorigo于1992年在他的博士論文中引入，其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。事實(shí)上，每只螞蟻并不是像我們想象的需要知道整個(gè)世界的信息，他們其實(shí)只關(guān)心很小范圍內(nèi)的眼前信息，而且根據(jù)這些局部信息利用幾條簡(jiǎn)單的規(guī)則進(jìn)行決策，這樣，在蟻群這個(gè)集體里，復(fù)雜性的行為就會(huì)凸現(xiàn)出來(lái)。這就是人工生命、復(fù)雜性科學(xué)解釋的規(guī)律！那么，這些簡(jiǎn)單規(guī)則是什么呢？下面詳細(xì)說(shuō)明：1、范圍：螞蟻觀察到的范圍是一個(gè)方格世界，

15、螞蟻有一個(gè)參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個(gè)方格世界，并且能移動(dòng)的距離也在這個(gè)范圍之內(nèi)。2、環(huán)境：螞蟻所在的環(huán)境是一個(gè)虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個(gè)螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。3、覓食規(guī)則：在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過(guò)去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點(diǎn)的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻多會(huì)以小概率犯錯(cuò)誤，從而并不是往信息素最多的點(diǎn)移動(dòng)。螞蟻找窩的規(guī)則和上

16、面一樣，只不過(guò)它對(duì)窩的信息素做出反應(yīng)，而對(duì)食物信息素沒(méi)反應(yīng)。4、移動(dòng)規(guī)則：每只螞蟻都朝向信息素最多的方向移，并且，當(dāng)周圍沒(méi)有信息素指引的時(shí)候，螞蟻會(huì)按照自己原來(lái)運(yùn)動(dòng)的方向慣性的運(yùn)動(dòng)下去，并且，在運(yùn)動(dòng)的方向有一個(gè)隨機(jī)的小的擾動(dòng)。為了防止螞蟻原地轉(zhuǎn)圈，它會(huì)記住最近剛走過(guò)了哪些點(diǎn)，如果發(fā)現(xiàn)要走的下一點(diǎn)已經(jīng)在最近走過(guò)了，它就會(huì)盡量避開(kāi)。5、避障規(guī)則：如果螞蟻要移動(dòng)的方向有障礙物擋住，它會(huì)隨機(jī)的選擇另一個(gè)方向，并且有信息素指引的話，它會(huì)按照覓食的規(guī)則行為。7、播撒信息素規(guī)則：每只螞蟻在剛找到食物或者窩的時(shí)候撒發(fā)的信息素最多，并隨著它走遠(yuǎn)的距離，播撒的信息素越來(lái)越少。根據(jù)這幾條規(guī)則，螞蟻之間并沒(méi)有直接的關(guān)

17、系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過(guò)信息素這個(gè)紐帶，實(shí)際上把各個(gè)螞蟻之間關(guān)聯(lián)起來(lái)了。比如，當(dāng)一只螞蟻找到了食物，它并沒(méi)有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當(dāng)其它的螞蟻經(jīng)過(guò)它附近的時(shí)候，就會(huì)感覺(jué)到信息素的存在，進(jìn)而根據(jù)信息素的指引找到了食物。引申:跟著螞蟻的蹤跡，你找到了什么？通過(guò)上面的原理敘述和實(shí)際操作，我們不難發(fā)現(xiàn)螞蟻之所以具有智能行為，完全歸功于它的簡(jiǎn)單行為規(guī)則，而這些規(guī)則綜合起來(lái)具有下面兩個(gè)方面的特點(diǎn)：1、多樣性2、正反饋多樣性保證了螞蟻在覓食的時(shí)候不置走進(jìn)死胡同而無(wú)限循環(huán)，正反饋機(jī)制則保證了相對(duì)優(yōu)良的信息能夠被保存下來(lái)。我們可以把多樣性看成是一種創(chuàng)造能力，而正反饋是

18、一種學(xué)習(xí)強(qiáng)化能力。正反饋的力量也可以比喻成權(quán)威的意見(jiàn)，而多樣性是打破權(quán)威體現(xiàn)的創(chuàng)造性，正是這兩點(diǎn)小心翼翼的巧妙結(jié)合才使得智能行為涌現(xiàn)出來(lái)了。引申來(lái)講，大自然的進(jìn)化，社會(huì)的進(jìn)步、人類的創(chuàng)新實(shí)際上都離不開(kāi)這兩樣?xùn)|西，多樣性保證了系統(tǒng)的創(chuàng)新能力，正反饋保證了優(yōu)良特性能夠得到強(qiáng)化，兩者要恰到好處的結(jié)合。如果多樣性過(guò)剩，也就是系統(tǒng)過(guò)于活躍，這相當(dāng)于螞蟻會(huì)過(guò)多的隨機(jī)運(yùn)動(dòng)，它就會(huì)陷入混沌狀態(tài)；而相反，多樣性不夠，正反饋機(jī)制過(guò)強(qiáng)，那么系統(tǒng)就好比一潭死水。這在蟻群中來(lái)講就表現(xiàn)為，螞蟻的行為過(guò)于僵硬，當(dāng)環(huán)境變化了，螞蟻群仍然不能適當(dāng)?shù)恼{(diào)整。既然復(fù)雜性、智能行為是根據(jù)底層規(guī)則涌現(xiàn)的，既然底層規(guī)則具有多樣性和正反饋特

19、點(diǎn)，那么也許你會(huì)問(wèn)這些規(guī)則是哪里來(lái)的？多樣性和正反饋又是哪里來(lái)的？我本人的意見(jiàn)：規(guī)則來(lái)源于大自然的進(jìn)化。而大自然的進(jìn)化根據(jù)剛才講的也體現(xiàn)為多樣性和正反饋的巧妙結(jié)合。而這樣的巧妙結(jié)合又是為什么呢？為什么在你眼前呈現(xiàn)的世界是如此栩栩如生呢？答案在于環(huán)境造就了這一切，之所以你看到栩栩如生的世界，是因?yàn)槟切┎荒軌蜻m應(yīng)環(huán)境的多樣性與正反饋的結(jié)合都已經(jīng)死掉了，被環(huán)境淘汰了！參數(shù)說(shuō)明：最大信息素：螞蟻在一開(kāi)始擁有的信息素總量，越大表示程序在較長(zhǎng)一段時(shí)間能夠存在信息素。信息素消減的速度：隨著時(shí)間的流逝，已經(jīng)存在于世界上的信息素會(huì)消減，這個(gè)數(shù)值越大，那么消減的越快。錯(cuò)誤概率表示這個(gè)螞蟻不往信息素最大的區(qū)域走的概

20、率，越大則表示這個(gè)螞蟻越有創(chuàng)新性。速度半徑表示螞蟻一次能走的最大長(zhǎng)度，也表示這個(gè)螞蟻的感知范圍。記憶能力表示螞蟻能記住多少個(gè)剛剛走過(guò)點(diǎn)的坐標(biāo)，這個(gè)值避免了螞蟻在本地打轉(zhuǎn)，停滯不前。而這個(gè)值越大那么整個(gè)系統(tǒng)運(yùn)行速度就慢，越小則螞蟻越容易原地轉(zhuǎn)圈。魚(yú)群優(yōu)化算法在一片水域中,魚(yú)往往能自行或尾隨其他魚(yú)找到營(yíng)養(yǎng)物質(zhì)多的地方,因而魚(yú)生存數(shù)目最多的地方一般就是本水域中營(yíng)養(yǎng)物質(zhì)最多的地方，人工魚(yú)群算法就是根據(jù)這一特點(diǎn),通過(guò)構(gòu)造人工魚(yú)來(lái)模仿魚(yú)群的覓食!聚群及追尾行為,從而實(shí)現(xiàn)尋優(yōu)，以下是魚(yú)的幾種典型行為:覓食行為:一般情況下魚(yú)在水中隨機(jī)地自由游動(dòng),當(dāng)發(fā)現(xiàn)食物時(shí),則會(huì)向食物逐漸增多的方向快速游去。聚群行為:魚(yú)在游

21、動(dòng)過(guò)程中為了保證自身的生存和躲避危害會(huì)自然地聚集成群，魚(yú)聚群時(shí)所遵守的規(guī)則有三條:分隔規(guī)則:盡量避免與臨近伙伴過(guò)于擁擠;對(duì)準(zhǔn)規(guī)則:盡量與臨近伙伴的平均方向一致;內(nèi)聚規(guī)則:盡量朝臨近伙伴的中心移動(dòng)。追尾行為:當(dāng)魚(yú)群中的一條或幾條魚(yú)發(fā)現(xiàn)食物時(shí),其臨近的伙伴會(huì)尾隨其快速到達(dá)食物點(diǎn)。特點(diǎn)：具有較快的收斂速度,可以用于解決有實(shí)時(shí)性要求的問(wèn)題;對(duì)于一些精度要求不高的場(chǎng)合,可以用它快速的得到一個(gè)可行解;不需要問(wèn)題的嚴(yán)格機(jī)理模型,甚至不需要問(wèn)題的精確描述,這使得它的應(yīng)用范圍得以延伸.停止條件判斷連續(xù)多次所得的均方差小于語(yǔ)允許的誤差判斷某個(gè)區(qū)域的人工魚(yú)群的數(shù)目達(dá)到某個(gè)比率聯(lián)系多次所獲取的值均不能超過(guò)已尋找的極值

22、。具體見(jiàn)原浙大博士李曉磊的博士論文-人工魚(yú)群算法。另外在nature上面2007年1一月有一篇關(guān)于人工魚(yú)行為的文章。(這兩部分的資料在附件里面)智能算法綜述什么是智能算法智能計(jì)算也有人稱之為“軟計(jì)算”，是們受自然（生物界）規(guī)律的啟迪，根據(jù)其原理，模仿求解問(wèn)題的算法。從自然界得到啟迪，模仿其結(jié)構(gòu)進(jìn)行發(fā)明創(chuàng)造，這就是仿生學(xué)。這是我們向自然界學(xué)習(xí)的一個(gè)方面。另一方面，我們還可以利用仿生原理進(jìn)行設(shè)計(jì)（包括設(shè)計(jì)算法），這就是智能計(jì)算的思想。這方面的內(nèi)容很多，如人工神經(jīng)網(wǎng)絡(luò)技術(shù)、遺傳算法、模擬退火算法、模擬退火技術(shù)和群集智能技術(shù)等。人工神經(jīng)網(wǎng)絡(luò)算法“人工神經(jīng)網(wǎng)絡(luò)”（ARTIFICIALNEURALNETW

23、ORK,簡(jiǎn)稱ANN）是在對(duì)人腦組織結(jié)構(gòu)和運(yùn)行機(jī)制的認(rèn)識(shí)理解基礎(chǔ)之上模擬其結(jié)構(gòu)和智能行為的一種工程系統(tǒng)。早在本世紀(jì)40年代初期，心理學(xué)家McCulloch、數(shù)學(xué)家Pitts就提出了人工神經(jīng)網(wǎng)絡(luò)的第一個(gè)數(shù)學(xué)模型，從此開(kāi)創(chuàng)了神經(jīng)科學(xué)理論的研究時(shí)代。其后，F(xiàn)Rosenblatt、Widrow和J.J.Hopfield等學(xué)者又先后提出了感知模型，使得人工神經(jīng)網(wǎng)絡(luò)技術(shù)得以蓬勃發(fā)展。神經(jīng)系統(tǒng)的基本構(gòu)造是神經(jīng)元（神經(jīng)細(xì)胞），它是處理人體內(nèi)各部分之間相互信息傳遞的基本單元。據(jù)神經(jīng)生物學(xué)家研究的結(jié)果表明，人的一個(gè)大腦一般有10101011個(gè)神經(jīng)元。每個(gè)神經(jīng)元都由一個(gè)細(xì)胞體，一個(gè)連接其他神經(jīng)元的軸突和一些向外伸出的

24、其它較短分支樹(shù)突組成。軸突的功能是將本神經(jīng)元的輸出信號(hào)（興奮）傳遞給別的神經(jīng)元。其末端的許多神經(jīng)末梢使得興奮可以同時(shí)傳送給多個(gè)神經(jīng)元。樹(shù)突的功能是接受來(lái)自其它神經(jīng)元的興奮。神經(jīng)元細(xì)胞體將接受到的所有信號(hào)進(jìn)行簡(jiǎn)單處理（如：加權(quán)求和，即對(duì)所有的輸入信號(hào)都加以考慮且對(duì)每個(gè)信號(hào)的重視程度體現(xiàn)在權(quán)值上有所不同）后由軸突輸出。神經(jīng)元的樹(shù)突與另外的神經(jīng)元的神經(jīng)末梢相連的部分稱為突觸。人工神經(jīng)網(wǎng)絡(luò)的特點(diǎn)人工神經(jīng)網(wǎng)絡(luò)是由大量的神經(jīng)元廣泛互連而成的系統(tǒng)，它的這一結(jié)構(gòu)特點(diǎn)決定著人工神經(jīng)網(wǎng)絡(luò)具有高速信息處理的能力。人腦的每個(gè)神經(jīng)元大約有103104個(gè)樹(shù)突及相應(yīng)的突觸，一個(gè)人的大腦總計(jì)約形成10141015個(gè)突觸。用神

25、經(jīng)網(wǎng)絡(luò)的術(shù)語(yǔ)來(lái)說(shuō)，即是人腦具有10141015個(gè)互相連接的存儲(chǔ)潛力。雖然每個(gè)神經(jīng)元的運(yùn)算功能十分簡(jiǎn)單，且信號(hào)傳輸速率也較低（大約100次/秒），但由于各神經(jīng)元之間的極度并行互連功能，最終使得一個(gè)普通人的大腦在約1秒內(nèi)就能完成現(xiàn)行計(jì)算機(jī)至少需要數(shù)10億次處理步驟才能完成的任務(wù)。人工神經(jīng)網(wǎng)絡(luò)的知識(shí)存儲(chǔ)容量很大。在神經(jīng)網(wǎng)絡(luò)中，知識(shí)與信息的存儲(chǔ)表現(xiàn)為神經(jīng)元之間分布式的物理聯(lián)系。它分散地表示和存儲(chǔ)于整個(gè)網(wǎng)絡(luò)內(nèi)的各神經(jīng)元及其連線上。每個(gè)神經(jīng)元及其連線只表示一部分信息，而不是一個(gè)完整具體概念。只有通過(guò)各神經(jīng)元的分布式綜合效果才能表達(dá)出特定的概念和知識(shí)。由于人工神經(jīng)網(wǎng)絡(luò)中神經(jīng)元個(gè)數(shù)眾多以及整個(gè)網(wǎng)絡(luò)存儲(chǔ)信息容量

26、的巨大，使得它具有很強(qiáng)的不確定性信息處理能力。即使輸入信息不完全、不準(zhǔn)確或模糊不清，神經(jīng)網(wǎng)絡(luò)仍然能夠聯(lián)想思維存在于記憶中的事物的完整圖象。只要輸入的模式接近于訓(xùn)練樣本，系統(tǒng)就能給出正確的推理結(jié)論。正是因?yàn)槿斯ど窠?jīng)網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn)和其信息存儲(chǔ)的分布式特點(diǎn)，使得它相對(duì)于其它的判斷識(shí)別系統(tǒng)，如：專家系統(tǒng)等，具有另一個(gè)顯著的優(yōu)點(diǎn)：健壯性。生物神經(jīng)網(wǎng)絡(luò)不會(huì)因?yàn)閭€(gè)別神經(jīng)元的損失而失去對(duì)原有模式的記憶。最有力的證明是，當(dāng)一個(gè)人的大腦因意外事故受輕微損傷之后，并不會(huì)失去原有事物的全部記憶。人工神經(jīng)網(wǎng)絡(luò)也有類似的情況。因某些原因，無(wú)論是網(wǎng)絡(luò)的硬件實(shí)現(xiàn)還是軟件實(shí)現(xiàn)中的某個(gè)或某些神經(jīng)元失效，整個(gè)網(wǎng)絡(luò)仍然能繼續(xù)工作。人

27、工神經(jīng)網(wǎng)絡(luò)是一種非線性的處理單元。只有當(dāng)神經(jīng)元對(duì)所有的輸入信號(hào)的綜合處理結(jié)果超過(guò)某一門限值后才輸出一個(gè)信號(hào)。因此神經(jīng)網(wǎng)絡(luò)是一種具有高度非線性的超大規(guī)模連續(xù)時(shí)間動(dòng)力學(xué)系統(tǒng)。它突破了傳統(tǒng)的以線性處理為基礎(chǔ)的數(shù)字電子計(jì)算機(jī)的局限，標(biāo)志著人們智能信息處理能力和模擬人腦智能行為能力的一大飛躍。幾種典型神經(jīng)網(wǎng)絡(luò)簡(jiǎn)介2.2.1多層感知網(wǎng)絡(luò)（誤差逆?zhèn)鞑ド窠?jīng)網(wǎng)絡(luò)）在1986年以Rumelhart和McCelland為首的科學(xué)家出版的ParallelDistributedProcessing一書(shū)中，完整地提出了誤差逆?zhèn)鞑W(xué)習(xí)算法，并被廣泛接受。多層感知網(wǎng)絡(luò)是一種具有三層或三層以上的階層型神經(jīng)網(wǎng)絡(luò)。典型的多層感知網(wǎng)

28、絡(luò)是三層、前饋的階層網(wǎng)絡(luò)，即：輸入層I、隱含層（也稱中間層）J和輸出層K。相鄰層之間的各神經(jīng)元實(shí)現(xiàn)全連接，即下一層的每一個(gè)神經(jīng)元與上一層的每個(gè)神經(jīng)元都實(shí)現(xiàn)全連接，而且每層各神經(jīng)元之間無(wú)連接。但BP網(wǎng)并不是十分的完善，它存在以下一些主要缺陷：學(xué)習(xí)收斂速度太慢、網(wǎng)絡(luò)的學(xué)習(xí)記憶具有不穩(wěn)定性，即：當(dāng)給一個(gè)訓(xùn)練好的網(wǎng)提供新的學(xué)習(xí)記憶模式時(shí)，將使已有的連接權(quán)值被打亂，導(dǎo)致已記憶的學(xué)習(xí)模式的信息的消失。2.2.2競(jìng)爭(zhēng)型（KOHONEN）神經(jīng)網(wǎng)絡(luò)它是基于人的視網(wǎng)膜及大腦皮層對(duì)剌激的反應(yīng)而引出的。神經(jīng)生物學(xué)的研究結(jié)果表明：生物視網(wǎng)膜中，有許多特定的細(xì)胞，對(duì)特定的圖形（輸入模式）比較敏感，并使得大腦皮層中的特定細(xì)

29、胞產(chǎn)生大的興奮，而其相鄰的神經(jīng)細(xì)胞的興奮程度被抑制。對(duì)于某一個(gè)輸入模式，通過(guò)競(jìng)爭(zhēng)在輸出層中只激活一個(gè)相應(yīng)的輸出神經(jīng)元。許多輸入模式，在輸出層中將激活許多個(gè)神經(jīng)元，從而形成一個(gè)反映輸入數(shù)據(jù)的“特征圖形”。競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)是一種以無(wú)教師方式進(jìn)行網(wǎng)絡(luò)訓(xùn)練的網(wǎng)絡(luò)。它通過(guò)自身訓(xùn)練，自動(dòng)對(duì)輸入模式進(jìn)行分類。競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)及其學(xué)習(xí)規(guī)則與其它類型的神經(jīng)網(wǎng)絡(luò)和學(xué)習(xí)規(guī)則相比，有其自己的鮮明特點(diǎn)。在網(wǎng)絡(luò)結(jié)構(gòu)上，它既不象階層型神經(jīng)網(wǎng)絡(luò)那樣各層神經(jīng)元之間只有單向連接，也不象全連接型網(wǎng)絡(luò)那樣在網(wǎng)絡(luò)結(jié)構(gòu)上沒(méi)有明顯的層次界限。它一般是由輸入層（模擬視網(wǎng)膜神經(jīng)元）和競(jìng)爭(zhēng)層（模擬大腦皮層神經(jīng)元，也叫輸出層）構(gòu)成的兩層網(wǎng)絡(luò)。兩層之間

30、的各神經(jīng)元實(shí)現(xiàn)雙向全連接，而且網(wǎng)絡(luò)中沒(méi)有隱含層。有時(shí)競(jìng)爭(zhēng)層各神經(jīng)元之間還存在橫向連接。競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)的基本思想是網(wǎng)絡(luò)競(jìng)爭(zhēng)層各神經(jīng)元競(jìng)爭(zhēng)對(duì)輸入模式的響應(yīng)機(jī)會(huì)，最后僅有一個(gè)神經(jīng)元成為競(jìng)爭(zhēng)的勝者，并且只將與獲勝神經(jīng)元有關(guān)的各連接權(quán)值進(jìn)行修正，使之朝著更有利于它競(jìng)爭(zhēng)的方向調(diào)整。神經(jīng)網(wǎng)絡(luò)工作時(shí)，對(duì)于某一輸入模式，網(wǎng)絡(luò)中與該模式最相近的學(xué)習(xí)輸入模式相對(duì)應(yīng)的競(jìng)爭(zhēng)層神經(jīng)元將有最大的輸出值，即以競(jìng)爭(zhēng)層獲勝神經(jīng)元來(lái)表示分類結(jié)果。這是通過(guò)競(jìng)爭(zhēng)得以實(shí)現(xiàn)的，實(shí)際上也就是網(wǎng)絡(luò)回憶聯(lián)想的過(guò)程。除了競(jìng)爭(zhēng)的方法外，還有通過(guò)抑制手段獲取勝利的方法，即網(wǎng)絡(luò)競(jìng)爭(zhēng)層各神經(jīng)元抑制所有其它神經(jīng)元對(duì)輸入模式的響應(yīng)機(jī)會(huì)，從而使自己“脫穎而出”

31、，成為獲勝神經(jīng)元。除此之外還有一種稱為側(cè)抑制的方法，即每個(gè)神經(jīng)元只抑制與自己鄰近的神經(jīng)元，而對(duì)遠(yuǎn)離自己的神經(jīng)元不抑制。這種方法常常用于圖象邊緣處理，解決圖象邊緣的缺陷問(wèn)題。競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)的缺點(diǎn)和不足：因?yàn)樗鼉H以輸出層中的單個(gè)神經(jīng)元代表某一類模式。所以一旦輸出層中的某個(gè)輸出神經(jīng)元損壞，則導(dǎo)致該神經(jīng)元所代表的該模式信息全部丟失。2.2.3Hopfield神經(jīng)網(wǎng)絡(luò)1986年美國(guó)物理學(xué)家JJ.Hopfield陸續(xù)發(fā)表幾篇論文，提出了Hopfield神經(jīng)網(wǎng)絡(luò)。他利用非線性動(dòng)力學(xué)系統(tǒng)理論中的能量函數(shù)方法研究反饋人工神經(jīng)網(wǎng)絡(luò)的穩(wěn)定性，并利用此方法建立求解優(yōu)化計(jì)算問(wèn)題的系統(tǒng)方程式?；镜腍opfield神經(jīng)網(wǎng)

32、絡(luò)是一個(gè)由非線性元件構(gòu)成的全連接型單層反饋系統(tǒng)。網(wǎng)絡(luò)中的每一個(gè)神經(jīng)元都將自己的輸出通過(guò)連接權(quán)傳送給所有其它神經(jīng)元，同時(shí)又都接收所有其它神經(jīng)元傳遞過(guò)來(lái)的信息。即：網(wǎng)絡(luò)中的神經(jīng)元t時(shí)刻的輸出狀態(tài)實(shí)際上間接地與自己的t-1時(shí)刻的輸出狀態(tài)有關(guān)。所以Hopfield神經(jīng)網(wǎng)絡(luò)是一個(gè)反饋型的網(wǎng)絡(luò)。其狀態(tài)變化可以用差分方程來(lái)表征。反饋型網(wǎng)絡(luò)的一個(gè)重要特點(diǎn)就是它具有穩(wěn)定狀態(tài)。當(dāng)網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)的時(shí)候，也就是它的能量函數(shù)達(dá)到最小的時(shí)候。這里的能量函數(shù)不是物理意義上的能量函數(shù)，而是在表達(dá)形式上與物理意義上的能量概念一致，表征網(wǎng)絡(luò)狀態(tài)的變化趨勢(shì)，并可以依據(jù)Hopfield工作運(yùn)行規(guī)則不斷進(jìn)行狀態(tài)變化，最終能夠達(dá)到的某

33、個(gè)極小值的目標(biāo)函數(shù)。網(wǎng)絡(luò)收斂就是指能量函數(shù)達(dá)到極小值。如果把一個(gè)最優(yōu)化問(wèn)題的目標(biāo)函數(shù)轉(zhuǎn)換成網(wǎng)絡(luò)的能量函數(shù)，把問(wèn)題的變量對(duì)應(yīng)于網(wǎng)絡(luò)的狀態(tài)，那么Hopfield神經(jīng)網(wǎng)絡(luò)就能夠用于解決優(yōu)化組合問(wèn)題。對(duì)于同樣結(jié)構(gòu)的網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)參數(shù)（指連接權(quán)值和閥值）有所變化時(shí)，網(wǎng)絡(luò)能量函數(shù)的極小點(diǎn)（稱為網(wǎng)絡(luò)的穩(wěn)定平衡點(diǎn)）的個(gè)數(shù)和極小值的大小也將變化。因此，可以把所需記憶的模式設(shè)計(jì)成某個(gè)確定網(wǎng)絡(luò)狀態(tài)的一個(gè)穩(wěn)定平衡點(diǎn)。若網(wǎng)絡(luò)有M個(gè)平衡點(diǎn)，則可以記憶M個(gè)記憶模式。當(dāng)網(wǎng)絡(luò)從與記憶模式較靠近的某個(gè)初始狀態(tài)（相當(dāng)于發(fā)生了某些變形或含有某些噪聲的記憶模式，也即：只提供了某個(gè)模式的部分信息）出發(fā)后，網(wǎng)絡(luò)按Hopfield工作運(yùn)行規(guī)則

34、進(jìn)行狀態(tài)更新，最后網(wǎng)絡(luò)的狀態(tài)將穩(wěn)定在能量函數(shù)的極小點(diǎn)。這樣就完成了由部分信息的聯(lián)想過(guò)程。Hopfield神經(jīng)網(wǎng)絡(luò)的能量函數(shù)是朝著梯度減小的方向變化，但它仍然存在一個(gè)問(wèn)題，那就是一旦能量函數(shù)陷入到局部極小值，它將不能自動(dòng)跳出局部極小點(diǎn)，到達(dá)全局最小點(diǎn)，因而無(wú)法求得網(wǎng)絡(luò)最優(yōu)解。遺傳算法遺傳算法（GeneticAlgorithms）是基于生物進(jìn)化理論的原理發(fā)展起來(lái)的一種廣為應(yīng)用的、高效的隨機(jī)搜索與優(yōu)化的方法。其主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換，搜索不依賴于梯度信息。它是在70年代初期由美國(guó)密執(zhí)根（Michigan）大學(xué)的霍蘭（Holland）教授發(fā)展起來(lái)的。1975年霍蘭教授發(fā)表了第

35、一本比較系統(tǒng)論述遺傳算法的專著自然系統(tǒng)與人工系統(tǒng)中的適應(yīng)性(AdaptationinNaturalandArtificialSystems)。遺傳算法最初被研究的出發(fā)點(diǎn)不是為專門解決最優(yōu)化問(wèn)題而設(shè)計(jì)的，它與進(jìn)化策略、進(jìn)化規(guī)劃共同構(gòu)成了進(jìn)化算法的主要框架，都是為當(dāng)時(shí)人工智能的發(fā)展服務(wù)的。迄今為止，遺傳算法是進(jìn)化算法中最廣為人知的算法。近幾年來(lái)，遺傳算法主要在復(fù)雜優(yōu)化問(wèn)題求解和工業(yè)工程領(lǐng)域應(yīng)用方面，取得了一些令人信服的結(jié)果，所以引起了很多人的關(guān)注。在發(fā)展過(guò)程中，進(jìn)化策略、進(jìn)化規(guī)劃和遺傳算法之間差異越來(lái)越小。遺傳算法成功的應(yīng)用包括：作業(yè)調(diào)度與排序、可靠性設(shè)計(jì)、車輛路徑選擇與調(diào)度、成組技術(shù)、設(shè)備布置與

36、分配、交通問(wèn)題等等。3.1特點(diǎn)遺傳算法是解決搜索問(wèn)題的一種通用算法，對(duì)于各種通用問(wèn)題都可以使用。搜索算法的共同特征為：首先組成一組候選解；依據(jù)某些適應(yīng)性條件測(cè)算這些候選解的適應(yīng)度；根據(jù)適應(yīng)度保留某些候選解，放棄其他候選解；對(duì)保留的候選解進(jìn)行某些操作，生成新的候選解。在遺傳算法中，上述幾個(gè)特征以一種特殊的方式組合在一起：基于染色體群的并行搜索，帶有猜測(cè)性質(zhì)的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳算法與其它搜索算法區(qū)別開(kāi)來(lái)。遺傳算法還具有以下幾方面的特點(diǎn)：遺傳算法從問(wèn)題解的串集開(kāi)始嫂索，而不是從單個(gè)解開(kāi)始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解

37、的；容易誤入局部最優(yōu)解。遺傳算法從串集開(kāi)始搜索，覆蓋面大，利于全局擇優(yōu)。許多傳統(tǒng)搜索算法都是單點(diǎn)搜索算法，容易陷入局部的最優(yōu)解。遺傳算法同時(shí)處理群體中的多個(gè)個(gè)體，即對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估，減少了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，同時(shí)算法本身易于實(shí)現(xiàn)并行化。遺傳算法基本上不用搜索空間的知識(shí)或其它輔助信息，而僅用適應(yīng)度函數(shù)值來(lái)評(píng)估個(gè)體在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點(diǎn)使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來(lái)指導(dǎo)他的搜索方向。具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過(guò)程獲得的信息自行組織搜索時(shí)，硬度

38、大的個(gè)體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。運(yùn)用領(lǐng)域前面描述是簡(jiǎn)單的遺傳算法模型，可以在這一基本型上加以改進(jìn)，使其在科學(xué)和工程領(lǐng)域得到廣泛應(yīng)用。下面列舉了一些遺傳算法的應(yīng)用領(lǐng)域：優(yōu)化：遺傳算法可用于各種優(yōu)化問(wèn)題。既包括數(shù)量?jī)?yōu)化問(wèn)題，也包括組合優(yōu)化問(wèn)題。程序設(shè)計(jì)：遺傳算法可以用于某些特殊任務(wù)的計(jì)算機(jī)程序設(shè)計(jì)。機(jī)器學(xué)習(xí)：遺傳算法可用于許多機(jī)器學(xué)習(xí)的應(yīng)用，包括分類問(wèn)題和預(yù)測(cè)問(wèn)題等。經(jīng)濟(jì)學(xué)：應(yīng)用遺傳算法對(duì)經(jīng)濟(jì)創(chuàng)新的過(guò)程建立模型，可以研究投標(biāo)的策略，還可以建立市場(chǎng)競(jìng)爭(zhēng)的模型。免疫系統(tǒng)：應(yīng)用遺傳算法可以對(duì)自然界中免疫系統(tǒng)的多個(gè)方面建立模型，研究個(gè)體的生命過(guò)程中的突變現(xiàn)象以及發(fā)掘進(jìn)化過(guò)程中的基因

39、資源進(jìn)化現(xiàn)象和學(xué)習(xí)現(xiàn)象：遺傳算法可以用來(lái)研究個(gè)體是如何學(xué)習(xí)生存技巧的，一個(gè)物種的進(jìn)化對(duì)其他物種會(huì)產(chǎn)生何種影響等等。社會(huì)經(jīng)濟(jì)問(wèn)題：遺傳算法可以用來(lái)研究社會(huì)系統(tǒng)中的各種演化現(xiàn)象，例如在一個(gè)多主體系統(tǒng)中，協(xié)作與交流是如何演化出來(lái)的。模擬退火算法模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為e-AE/(kT),其中E為溫度T時(shí)的內(nèi)能,E為其改變量，k為Boltzmann常數(shù)。用固體退火模擬

40、組合優(yōu)化問(wèn)題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問(wèn)題的模擬退火算法：由初始解i和控制參數(shù)初值t開(kāi)始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解一計(jì)算目標(biāo)函數(shù)差一接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程。退火過(guò)程由冷卻進(jìn)度表(CoolingSchedule)控制，包括控制參數(shù)的初值t及其衰減因子At、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件So5群體(群集)智能(SwarmIntelligence)受社會(huì)性昆蟲(chóng)行為的啟發(fā)，計(jì)算機(jī)工作者通過(guò)對(duì)社會(huì)性昆蟲(chóng)的模擬產(chǎn)生了一系列對(duì)于傳統(tǒng)問(wèn)題的新的解決方法，這些研究就是

41、群集智能的研究。群集智飽SwarmIntelligence)中的群體(Swarm)指的是“一組相互之間可以進(jìn)行直接通信或者間接通信(通過(guò)改變局部環(huán)境)的主體，這組主體能夠合作進(jìn)行分布問(wèn)題求解”。而所謂群集智能指的是“無(wú)智能的主體通過(guò)合作表現(xiàn)出智能行為的特性”。群集智能在沒(méi)有集中控制并且不提供全局模型的前提下，為尋找復(fù)雜的分布式問(wèn)題的解決方案提供了基礎(chǔ)。群集智能的特點(diǎn)和優(yōu)點(diǎn)：群體中相互合作的個(gè)體是分布式的(Distributed)，這樣更能夠適應(yīng)當(dāng)前網(wǎng)絡(luò)環(huán)境下的工作狀態(tài)；沒(méi)有中心的控制與數(shù)據(jù)，這樣的系統(tǒng)更具有魯棒性(Robust)，不會(huì)由于某一個(gè)或者某幾個(gè)個(gè)體的故障而影響整個(gè)問(wèn)題的求解?？梢圆煌?/p>

42、過(guò)個(gè)體之間直接通信而是通過(guò)非直接通信(Stimergy)進(jìn)行合作，這樣的系統(tǒng)具有更好的可擴(kuò)充性(Scalability)。由于系統(tǒng)中個(gè)體的增加而增加的系統(tǒng)的通信開(kāi)銷在這里十分小。系統(tǒng)中每個(gè)個(gè)體的能力十分簡(jiǎn)單，這樣每個(gè)個(gè)體的執(zhí)行時(shí)間比較短，并且實(shí)現(xiàn)也比較簡(jiǎn)單，具有簡(jiǎn)單性(Simplicity)o因?yàn)榫哂羞@些優(yōu)點(diǎn)，雖說(shuō)群集智能的研究還處于初級(jí)階段，并且存在許多困難，但是可以預(yù)言群集智能的研究代表了以后計(jì)算機(jī)研究發(fā)展的一個(gè)重要方向。在計(jì)算智能(Computationallntelligence領(lǐng)域有兩種基于群智能的算法，蟻群算法(AntColonyOptimization)和粒子群算法(Partic

43、leSwarmOptimization)，前者是對(duì)螞蟻群落食物采集過(guò)程的模擬，已經(jīng)成功運(yùn)用在很多離散優(yōu)化問(wèn)題上。5.1蟻群優(yōu)化算法受螞蟻覓食時(shí)的通信機(jī)制的啟發(fā)，90年代Dorigo提出了蟻群優(yōu)化算法(AntColonyOptimization,ACO)來(lái)解決計(jì)算機(jī)算法學(xué)中經(jīng)典的“貨郎擔(dān)問(wèn)題”如果有n個(gè)城市，需要對(duì)所有n個(gè)城市進(jìn)行訪問(wèn)且只訪問(wèn)一次的最短距離。在解決貨郎擔(dān)問(wèn)題時(shí)，蟻群優(yōu)化算法設(shè)計(jì)虛擬的“螞蟻”將摸索不同路線，并留下會(huì)隨時(shí)間逐漸消失的虛擬“信息素”。虛擬的“信息素”也會(huì)揮發(fā)，每只螞蟻每次隨機(jī)選擇要走的路徑，它們傾向于選擇路徑比較短的、信息素比較濃的路徑。根據(jù)“信息素較濃的路線更近的原

44、則，即可選擇出最佳路線。由于這個(gè)算法利用了正反饋機(jī)制，使得較短的路徑能夠有較大的機(jī)會(huì)得到選擇，并且由于采用了概率算法，所以它能夠不局限于局部最優(yōu)解。蟻群優(yōu)化算法對(duì)于解決貨郎擔(dān)問(wèn)題并不是目前最好的方法，但首先，它提出了一種解決貨郎擔(dān)問(wèn)題的新思路；其次由于這種算法特有的解決方法，它已經(jīng)被成功用于解決其他組合優(yōu)化問(wèn)題，例如圖的著色(Graphcoloring)以及最短超串(ShortestCommonSupersequence)等問(wèn)題。5.2粒子群優(yōu)化算法粒子群優(yōu)化算法(PSO)是一種進(jìn)化計(jì)算技術(shù)(EvolutionaryComputation),有Eberhart博士和Kennedy博士發(fā)明。源于

45、對(duì)鳥(niǎo)群捕食的行為研究。PSO同遺傳算法類似，是一種基于疊代的優(yōu)化工具。系統(tǒng)初始化為一組隨機(jī)解，通過(guò)疊代搜尋最優(yōu)值。但是并沒(méi)有遺傳算法用的交叉(crossover)以及變異(mutation)。而是粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索。同遺傳算法比較，PSO的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)并且沒(méi)有許多參數(shù)需要調(diào)整。目前已廣泛應(yīng)用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域。粒子群優(yōu)化算法(PSO)也是起源對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬，最初設(shè)想是模擬鳥(niǎo)群覓食的過(guò)程，但后來(lái)發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具。與遺傳算法比較，PSO的信息共享機(jī)制是很不同的。在遺傳算法中，染色體(chromosomes)互相共享信息，所以整個(gè)種群的移動(dòng)是比較均勻的向最優(yōu)區(qū)域移動(dòng)。在P