數(shù)學(xué)建模之智能計算

1、數(shù)學(xué)建模之智能計算（2）一、 蟻群算法 蟻群優(yōu)化算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型算法.它由意大利學(xué)者Marco Dorigo于上世紀九十年大初期最早提出的一種源于大自然的新的仿生類算法，其靈感來源于上述所描述的螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為.蟻群算法主要是借鑒螞蟻群體之間的信息傳遞方法達到尋優(yōu)的目的，最初有稱之為蟻群優(yōu)化方法，在計算機模擬仿真中由于采用了人工“螞蟻”的概念，因此，也稱螞蟻系統(tǒng)（Ant System.AS）。主要討論內(nèi)容 蟻群算法基本原理 蟻群算法模型的建立 蟻群算法研究進展 基于蟻群算法的T

2、SP求解 一個實例 蟻群算法的收斂性討論 一、基本原理1、 從真實螞蟻到人工螞蟻蟻群算法是一種受自然界生物的行為啟發(fā)而產(chǎn)生的“自然”1 / 41算法。它是從對蟻群行為的研究中產(chǎn)生的。其基本原理如下圖：圖1 蟻群覓食路線上圖表示螞蟻覓食的線路，為蟻穴 , 為食源，從到有兩條線路可走，是長路徑，是短路徑。螞蟻走過一條路線以后，在地面上會留下信息素氣味，后來螞蟻就是根據(jù)留在地面上這種氣味的強度選擇移動的方向。圖表示起始情況，假定蟻穴中有只螞蟻，分別用表示，為食源。開始時蟻穴中螞蟻向食源移動，由于路線和上均沒有螞蟻通過，在這兩條路線上都沒有信息素氣味，因此螞蟻選擇這兩條線路的機會均等。令蟻選擇線路，蟻

3、選擇線路，假定螞蟻移動的速度相同，當蟻到達食源時，蟻還在途中，如圖。蟻到達食源以后就返回，這時從返回也有兩條線路選擇，哪一條線路上信息素的氣味重就選擇哪一條。因為蟻還在途中，沒有到達終點，這時在線路上靠近端處，蟻還沒有留下信息素氣味，所以蟻返回蟻穴的線路只有一個選擇，就是由原路返回。當蟻返回時，蟻開始出發(fā)，蟻的線路選擇必定是，因為這時上氣味濃度比上重 (上已有螞蟻兩次通過 ) ，如圖所示。當蟻到達食源時 ,蟻返回線路必然選擇，如圖所示。如此繼續(xù)下去 ，沿線路上移動的螞蟻越來越多，這就是巢穴到食源的最短路線，螞蟻根據(jù)線路上留下信息素濃度的大小，確定在路線上移動的方向，蟻群向信息素濃度重的線路集聚

4、的現(xiàn)象稱為正反饋。螞蟻算法正是基于正反饋原理的啟發(fā)式算法。蟻群覓食過程中的簡單規(guī)則每只螞蟻并不是像我們想象的需要知道整個世界的信息，他們其實只關(guān)心很小范圍內(nèi)的眼前信息，而且根據(jù)這些局部信息利用幾條簡單的規(guī)則進行決策，這樣，在蟻群這個集體里，復(fù)雜性的行為就會凸現(xiàn)出來。這就是人工生命、復(fù)雜性科學(xué)解釋的規(guī)律！那么，這些簡單規(guī)則是什么呢？下面詳細說明：1、范圍：螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個方格世界，并且能移動的距離也在這個范圍之內(nèi)。2、環(huán)境：螞蟻所在的環(huán)境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種

5、是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。3、覓食規(guī)則：在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻多會以小概率犯錯誤，從而并不是往信息素最多的點移動。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應(yīng)，而對食物信息素沒反應(yīng)。4、移動規(guī)則： 每只螞蟻都朝向信息素最多的方向移，并且，當周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，并且，在運動的方向有一個

6、隨機的小的擾動。為了防止螞蟻原地轉(zhuǎn)圈，它會記住最近剛走過了哪些點，如果發(fā)現(xiàn)要走的下一點已經(jīng)在最近走過了，它就會盡量避開。5、避障規(guī)則：如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，并且有信息素指引的話，它會按照覓食的規(guī)則行為。 7、播撒信息素規(guī)則：每只螞蟻在剛找到食物或者窩的時候撒發(fā)的信息素最多，并隨著它走遠的距離，播撒的信息素越來越少。根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個紐帶，實際上把各個螞蟻之間關(guān)聯(lián)起來了。比如，當一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當其它的螞蟻經(jīng)過它附近的時候，就會

7、感覺到信息素的存在，進而根據(jù)信息素的指引找到了食物。蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來源于上述所描述的螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。其中“信息素”在蟻群算法中期到非常重要的啟示作用。 1 Colorni A, Dorigo M, Maniezzo V, etal. Distributed optimization by ant colonies . Proceedings of the 1st European Conferen

8、ce on Artifical Life, 1991,134-1422 Dorigo M. Optimzation,learning and natural algorithms.Ph.D.Thesis, Department of Electronics, Politenico diMilano,Italy,1992 在蟻群算法中，需要定義人工螞蟻的概念，人工螞蟻具有雙重特性，首先，它們是真實馬一行維特征的一種抽象，通過對真實螞蟻行為的觀察，將蟻群行為中的智能化因素賦予人工螞蟻；另一方面，為了解決實際問題，人工螞蟻必須具備真實螞蟻一些所不具備的特性。歸納起來看，它與真實螞蟻之間主要存在下列異

9、同 二、人工蟻與真實蟻的共同特征比較1、 人工蟻與真實蟻一樣，都是一個需要合作的群體問題的解決需要通過人工蟻的合作來完成，人工蟻群通過相互協(xié)調(diào)與合作從而有可能找到全局最優(yōu)方案，而每只人工蟻的單獨行動只可能找到局部最優(yōu)解2、 人工蟻和真實蟻一樣，都要完成一個共同的任務(wù) 人工蟻與真實蟻一樣，都要完成一個共同的任務(wù)，即需尋找一個從源節(jié)點（巢穴）到目的節(jié)點（食物源）之間的最短路經(jīng)（或最小代價），人工螞蟻與真實螞蟻一樣都不能跳躍，必須在相鄰節(jié)點之間移動，直至遍歷所有可能路徑，為了減少計算復(fù)雜度并尋找出最短路徑，需要記錄當前路徑3、 人工蟻與真實蟻一樣都通過使用信息素進行間接通信人工蟻與真實蟻一樣都存在一

10、種改變當前所處環(huán)境的機制：真實螞蟻在經(jīng)過的路徑上留下信息素，人工蟻則不斷修改更新在其所經(jīng)過的路徑上存儲的信息，是一種模擬自然界中的信息素軌跡更新的過程4、 人工蟻利用真實蟻覓食行為中的自催化機制正反饋 當一些路徑上通過的螞蟻越來越多時，路徑上留下的信息素軌跡也越來越多，使得信息素強度變大，根據(jù)螞蟻清傾向于選擇信息強度大的特點，后來的螞蟻選擇該路經(jīng)的概率也越高，從而增加了該路經(jīng)的信息素強度，這稱之為自催化過程 自催化機制利用信息素作為反饋，通過對系統(tǒng)演化過程中較優(yōu)解的增強作用，使得問題的解向著全局最優(yōu)的方向逐步接近5、 信息素的揮發(fā)機制在蟻群算法中設(shè)置一種揮發(fā)機制，類似于真實信息素的揮發(fā)，這種機

11、制需要螞蟻忘記過去，不受過去經(jīng)驗的過分約束，有利于指引螞蟻朝著新的方向搜索，避免早熟收斂6、 利用當前信息進行路徑選擇的隨機選擇策略 人工蟻于真實蟻都是利用概率選擇策略實現(xiàn)一個節(jié)點到相鄰節(jié)點的移動，選擇策略只利用當前的信息去預(yù)測未來的情況，而不能利用未來的信息，因此，人工蟻與真實蟻所使用的選擇策略在時間和空間上都具有局部特性 人工蟻具備一些真實蟻所不具備的特征，主要體現(xiàn)在下列五個方面1、 人工蟻存在于離散空間中，它們的移動實質(zhì)上是有一個離散狀態(tài)到另一個離散狀態(tài)的轉(zhuǎn)移；2、 人工蟻具有一個記錄其過去自身行為的內(nèi)在狀態(tài)；3、 人工蟻存在于與時間無關(guān)聯(lián)的環(huán)境之中人工蟻并非完全盲從，它受到問題特征的啟

12、發(fā)，例如，有的問題中人工螞蟻產(chǎn)生一個解后改變信息量，而在有的問題中人工螞蟻每做一次選擇便改變信息量 5、為了提升人工蟻系統(tǒng)的性能，改進算法效率，人工蟻可增加一些性能，如預(yù)測未來、局部優(yōu)化、回溯等。在很多具體應(yīng)用中，人工蟻可以在局部優(yōu)化的過程中交換信息以及實行簡單預(yù)測等。三、基本蟻群算法模型的建立1、螞蟻個體的抽象 抽象出能夠為建立模型起作用的真實蟻群的機理，摒棄與建立模型算法無關(guān)的因素.2、問題空間的描述螞蟻軌跡可以看成為二維平面上的活動，其活動過程為一個狀態(tài)到另一個狀態(tài)的遷移，因此，利用蟻群算法求解的問題其數(shù)學(xué)模型采用圖論語言來描述就顯得非常自然，另一方面，在實際問題中的許多應(yīng)用問題可以通過

13、圖的語言來描述，這就使得蟻群算法的廣泛應(yīng)用成為可能.3、尋找路徑的抽象把真實螞蟻的覓食過程抽象成算法中解的構(gòu)造過程，將信息素抽象成存在于圖邊上的軌跡，信息素的大小可以通過設(shè)置權(quán)重來體現(xiàn)，并根據(jù)權(quán)重的值決定走向下一個節(jié)點的概率.用任何兩個節(jié)點分別表示螞蟻的巢穴（初始節(jié)點）和食物源（終止節(jié)點），人工螞蟻按照一定的狀態(tài)轉(zhuǎn)移概率從初始節(jié)點移動到鄰近的節(jié)點，以此類推，最終選擇行走到目標節(jié)點，從而得到問題的一個可行解.4、信息素揮發(fā)的抽象自然界中真實螞蟻在所經(jīng)過的路徑上會連續(xù)不斷的留下信息素，而信息素也會隨著時間的推移連續(xù)不斷的揮發(fā)，在人工蟻群算法中，螞蟻完成從某一節(jié)點到相鄰節(jié)點的一次移動后（相應(yīng)于經(jīng)過一

14、個時間單位），進行一次信息素揮發(fā)，這有利于避免陷入局部最優(yōu)的陷阱.5、啟發(fā)因子的引入為了設(shè)計有效的蟻群算法，在決定螞蟻行走方向的狀態(tài)轉(zhuǎn)移概率時，引入一個隨機搜索的過程，即引入一個啟發(fā)因子，根據(jù)所求問題空間的具體特征，給蟻群算法一個初始的引導(dǎo)，從而極大的增加算法的有效性，從而使蟻群算法的有效應(yīng)用成為可能.為了說明螞蟻系統(tǒng)模型，下面討論基于蟻群算法的旅行商問題的解.在模型建立與求解過程中，我們需要首先引入下列符號：用表示時刻位于城市的螞蟻數(shù)目，為蟻群中螞蟻的總數(shù)目，為TSP問題的規(guī)模，即城市的個數(shù).顯然， ，表示t時刻路徑上的信息量，是t時刻集合中元素（城市）兩兩連接上殘留信息量的集合，在初始時刻

15、各路經(jīng)上的信息量都相等，即設(shè)（常數(shù)），基本蟻群算法的尋優(yōu)是通過有向圖來實現(xiàn)的.螞蟻在運動過程中，根據(jù)各條路經(jīng)上留下的信息量決定其轉(zhuǎn)移方向.此處采用禁忌表來記錄螞蟻k當前所走過的城市.集合隨著進化過程作動態(tài)調(diào)整，而用來表示螞蟻k下一步允許訪問的城市位置，顯然.若用表示城市和城市之間的距離，則t時刻，圖中邊反映由城市轉(zhuǎn)移到城市的啟發(fā)程度，即能見度，可以取為，是一個與時間無關(guān)的常數(shù).在搜索過程中，螞蟻根據(jù)各條路經(jīng)上的信息量以及路徑的啟發(fā)信息（主要是路徑長度）來計算狀態(tài)轉(zhuǎn)移概率，如用表示螞蟻k在 t時刻由城市轉(zhuǎn)移到城市的狀態(tài)轉(zhuǎn)移概率，則可以定義 (1)在上式中，與分別反映了路徑軌跡與路徑能見度的相對重

16、要性. 作為信息啟發(fā)式因子，反映了螞蟻在運動過程中所積累的信息在螞蟻運動時所起的作用，其值越大，則該螞蟻越傾向于選擇其他螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性越強，作為啟發(fā)式因子，反映了螞蟻在運動過程中啟發(fā)因素在選擇路徑時的受重視程度，其值越大，則該狀態(tài)轉(zhuǎn)移越接近貪心規(guī)則.在兩種極端情形：與下，則分別退化為傳統(tǒng)的貪心算法與純粹的正反饋啟發(fā)式方法.上述狀態(tài)轉(zhuǎn)移概率的計算用到t時刻各條路經(jīng)上信息量的計算，下面我們討論的計算方法.在初始時刻，可以選擇（常數(shù)），螞蟻完成一次循環(huán)后各路經(jīng)上的信息量更新方程設(shè)為 (2)其中，表示信息素的持久系數(shù)（即信息的揮發(fā)度），而則表示信息素的衰減系數(shù)，因此一般選擇比較合適.

17、從上式可以看出，在已知的情況下，為了計算，需要計算出全體螞蟻在時刻t到時刻內(nèi)留在路徑上信息素量的增量，因此，需要計算出每只螞蟻k 在時刻t到時刻內(nèi)留在路徑上信息素量的增量.根據(jù)更新策略的不同，Dorigo M提出了三種計算不同的方法，從而得到三種不同的蟻群算法模型，分別稱之為Ant-Quantity（蟻量）模型、Ant-Density（蟻密）模型以及Ant-Cycle（蟻周）模型.在蟻量模型中 (3)其中，Q 表示信息素強度，為螞蟻循環(huán)一周釋放的總信息量.在蟻密模型中 (4)從上面的定義不難看到，在蟻密模型中，一只螞蟻從城市轉(zhuǎn)移到城市的過程中路徑上信息素的增量與邊的長度無關(guān)，而在蟻量模型中，它

18、與成反比，就是說，在蟻量模型終端路徑對螞蟻更具有吸引力，因此，更一步加強了狀態(tài)轉(zhuǎn)移概率方程中能見度因子的值.在上述兩種基本蟻群算法模型中，螞蟻完成一步后即更新路徑上的信息素，即在建立方案的同時釋放信息素，采用的是局部信息，為了充分利用整體信息從而得到全局最優(yōu)算法，下面介紹一種蟻周模型.蟻周模型與上述兩種模型的主要區(qū)別在于的不同，在蟻周模型中，表示螞蟻經(jīng)過n步完成一次循環(huán)后后更新螞蟻k所走過的路徑，具體更新值滿足 （5）其中，表示螞蟻k在本次循環(huán)中所走路徑的長度.由于蟻周系統(tǒng)中，要求螞蟻已經(jīng)建立了完整的軌跡后再釋放信息，信息素軌跡根據(jù)如下公式進行更新 （6）四、 基本蟻群算法的實現(xiàn)以TSP為例，

19、基本蟻群算法的具體實現(xiàn)步驟描述如下：（1）參數(shù)初始化 令時間，循環(huán)次數(shù)計數(shù)器初值，軌跡強度增量的初值設(shè)為0，即，初始階段禁忌表設(shè)為空集，即，由某種啟發(fā)式算法規(guī)則確定，在TSP中一般取為，將m只螞蟻隨機置于n個元素（城市）上，并令有向圖上每條邊的初始信息量為常數(shù)，即；（2） 循環(huán)次數(shù)螞蟻禁忌表索引號，螞蟻數(shù)目；（3） 螞蟻個體根據(jù)狀態(tài)轉(zhuǎn)移概率公式(1)計算的概率原則元素（城市）j并前進，；（4）修改禁忌指針表，即將選擇好之后的螞蟻移動到新的元素（城市），并將該元素（城市）移到該螞蟻個體的禁忌表中；（5）信息素更新的計算在蟻密模型中， ；在蟻量模型中，；對于每一個路徑，設(shè)置持久因子，并按照（2）計

20、算.在蟻周模型中，對于，根據(jù)禁忌表的記錄計算，對于，設(shè)，即為螞蟻k的禁忌表中連接城市的路徑，計算，對于每一條路經(jīng)，按照（6）計算.（6）紀錄到目前為止的最短路經(jīng)，如果，則計算終止，循環(huán)結(jié)束并輸出計算結(jié)果，否則，清空禁忌表并返回步驟（2）.一系列仿真試驗表明，在求解TSP 問題時，蟻周算法的性能優(yōu)于其它兩種算法，因此，人們更多地關(guān)注于一周算法的研究.下面我們討論基本蟻群算法的計算復(fù)雜度問題.算法計算復(fù)雜度由時間復(fù)雜度和空間復(fù)雜度構(gòu)成.根據(jù)蟻群算法所列參數(shù)，以及每一步算法描述，其算法每一步運算量主要包括：初始化參數(shù)，含賦值運算量為，設(shè)置禁忌表賦值運算量為，每只螞蟻單獨求解需要算術(shù)元算量為，而信息素

21、軌跡濃度的更新需要次算術(shù)運算，因此，算法總的運算量為.基本蟻群算法的求解通過有向圖來描述，因此需要一個n階二維距離矩陣來描述問題本身的特征；為了表示有向圖上的信息量，需要用另外一個n階二維距離來表示圖上的信息素濃度；同時，在求解TSP問題的過程中，為了保證TSP城市不出現(xiàn)重復(fù)的現(xiàn)象，需要為每只螞蟻設(shè)置一個n階一維數(shù)組的禁忌表；為了保存螞蟻尋找到的解，還需為每只螞蟻設(shè)置一個數(shù)組；為了便于更新軌跡，需要利用二維數(shù)組保存每條邊上的信息素更新量，等等.整個計算過程所耗的空間復(fù)雜度為.由于蟻群算法是一種比較新的模擬進化智能算法，目前還沒有形成非常嚴格的系統(tǒng)理論，包括算法中的許多參數(shù)設(shè)置、信息素量的更新策

22、略等都仍然有許多值得研究的地方.另外，蟻群算法可以用來有效求解較小規(guī)模的TSP問題，但是，對較大規(guī)模的TSP問題，蟻群算法存在需要循環(huán)次數(shù)偏大等問題.針對這些問題，近年來研究者進行了大量深入的研究，提出了許多改進的蟻群優(yōu)化算法，這些改進算法主要集中在性能的改進等方面.例如，精英策略，其思想是在算法開始后便對到目前為止所發(fā)現(xiàn)的最佳路徑給以記錄，并將隨之得到的行程標記為全局最優(yōu)行程，一旦對信息進行搜索更新，則對所得到的行程加權(quán)處理，而經(jīng)過上述行程的螞蟻記為“精英”，這樣做的目的可以增加選擇較好行程的機會，從而可能以更快的速度收斂到更好的解.在精英策略中，需要注意的是：若選擇的精英過多，則算法可能因

23、為陷入舉步最優(yōu)解的陷阱而過早出現(xiàn)搜索停滯現(xiàn)象，極大極小系統(tǒng)（MAXMIN System）是另一種有代表性的改進算法，該算法要求每次迭代后授權(quán)一只螞蟻對螞蟻系統(tǒng)的信息素進行更新修改以獲取更好的解.為了增強算法初始階段的搜索能力，信息素的初始值被設(shè)置為取值上限MAX，為了避免搜索停滯，路徑上的信息素濃度被限制在區(qū)間內(nèi).另外，基于秩權(quán)限（Rankbased Version）的改進AS 算法也是一種有效算法，與精英算法相似，在該算法中總是更新更好路徑上的信息素.以求解大型TSP（最多包含132座城市）為例，研究表明，基于AS的算法性能均優(yōu)于前面兩章描述的模擬退伙算法（SA）和遺傳算法(GA)，而基于秩

24、權(quán)限的改進AS 算法可以得到比精英策略AS 算法更優(yōu)的解.蟻群算法進化計算過程，實際上是計算機通過程序不斷迭代來實現(xiàn)的，由于蟻群算法在構(gòu)造解的過程中.利用了隨機選擇策略，因此，算法是否收斂就成為人們關(guān)心的問題.1999年，Gutjahr W J最早從有向圖的角度對一種改進的蟻群算法圖搜索蟻群系統(tǒng)（GBAS）的收斂性進行了證明. 此后，改進的蟻群算法及其收斂分析的工作一直是研究的重點和難點問題.五、改進的蟻群算法蟻群算法作為一種隨機搜索算法，與其它模擬進化算法一樣，通過候選解組成的群體進化過程來尋求最優(yōu)解，該過程包含適應(yīng)階段與協(xié)作兩個階段.在適應(yīng)階段，各候選解根據(jù)積累的信息不斷的調(diào)整自身結(jié)構(gòu)；在

25、協(xié)作階段，候選解之間通過信息交流，以期望產(chǎn)生性能更好的解.但是，基本蟻群算法存在搜索時間過長的問題，雖然計算機速度的提高以及蟻群算法的本質(zhì)并行性在一定程度上可以緩解這一問題，但是，隨著問題規(guī)模變大，計算實時性會成為一大難題.為了克服基本蟻群算法的缺陷，人們提出了許多改進的蟻群算法.下面介紹三種改進方案.一、具有變異特征的蟻群算法這是1999年吳慶洪等人針對TSP問題的基本蟻群算法提出的一種改進方案.對于路徑的選擇采取逆轉(zhuǎn)變異方式，設(shè)某個體所走路徑：如果距離滿足其中表示對進行取整運算.則進行操作：inversion(),函數(shù)inversion()的功能是把個體solution的和這一段顛倒過來，

26、如：其中，變異的次數(shù)是隨機的，這一過程涉及到的運算比蟻群算法中的循環(huán)過程要簡單得多，因此只需較短的時間內(nèi)便可完成相同次數(shù)的運算.另一方面，經(jīng)過這種變異算子作用后，這一代解的性能產(chǎn)生明顯的改善，從而也能改善整個群體的性能，減少計算時間.試驗表明，上述具有變異特征的蟻群算法可以有效加快搜索速度. 2、基于蟻群算法與遺傳算法融合(GAAA)的改進方法上述GAAA算法是由丁建立等在2003年提出了的，其基本思想是吸取兩種算法的優(yōu)點，克服各自的缺陷，優(yōu)勢互補.在時間效率上優(yōu)于遺傳算法，在求解精度效率上優(yōu)于遺傳算法，是時間效率和求精解效率都比較好的啟發(fā)式算法.其基本思路是算法前過程采用遺傳算法，充分利用遺

27、傳算法的快速性、隨機性、全局收斂性，其結(jié)果是產(chǎn)生有關(guān)問題的初始信息素分布. 算法后過程采用蟻群算法，在一定初始信息素分布的情況下，充分利用蟻群算法的并行性、正反饋性、求精解效率高登特點. 下面討論GAAA算法中遺傳算法的定義與設(shè)置.在編碼與適應(yīng)值函數(shù)的涉及中，結(jié)合解決問題，采用十進制編碼，適應(yīng)值函數(shù)結(jié)合目標函數(shù)而定，如TSP問題，以遍歷城市次序作為遺傳算法的編碼，適應(yīng)值函數(shù)取為哈密頓圈的長度的倒數(shù).種群生成與染色體選擇則利用rand函數(shù)隨機生成一定數(shù)量的十進制實數(shù)編碼種群，根據(jù)適應(yīng)值函數(shù)選擇準備進行交配的一對染色體父串.交叉算子采用Davis提出的順序交叉法，先進行常規(guī)的雙點交叉，再進行維持原

28、有相對訪問順序的巡回路線修改，具體交叉如下：隨機在父串上選擇一個交配區(qū)域，如兩父串選定為 將的交配區(qū)域加到前面，將的交配區(qū)域加到的前面：依次刪除中與交配區(qū)域相同的數(shù)碼，最后得到兩字串：變異算子采用逆轉(zhuǎn)變異方法，所謂逆轉(zhuǎn)，如染色體在區(qū)間和處發(fā)生斷裂，斷裂片斷又以順序插入，于是逆轉(zhuǎn)后的染色體變?yōu)椋渲?，“進化”是指逆轉(zhuǎn)算子的單方向性，只有經(jīng)逆轉(zhuǎn)后適應(yīng)值有提高的才能接受下來，否則逆轉(zhuǎn)無效.為了實現(xiàn)遺傳算法和蟻群算法的有效結(jié)合，需要討論GAAA算法的改進與銜接問題.首先通過遺傳算法得到一定的路徑信息素，并把信息素的初值設(shè)置為，其中，是根據(jù)具體求解問題規(guī)模給定的一個信息素常數(shù)，是遺傳算法求解結(jié)果轉(zhuǎn)換得信

29、息素值.信息素更新模型采用蟻群圈模型進行信息素更新，即一圈中只有最短路徑的蟻群才進行信息素修改增加，而所有路徑的軌跡更新方程均采用：為了驗證算法性能，采用典型的含遍歷30個城市的TSP問題進行仿真實驗，GAAA算法中迭代次數(shù)固定為30代，蟻群算法中各路徑的信息素初始值設(shè)為60，遺傳算法求解結(jié)果轉(zhuǎn)換的信息素值為經(jīng)過路徑加2，軌跡更新表1反映GAAA算法優(yōu)化求解數(shù)據(jù)逼近過程，圖8直觀地說明了GAAA算法中經(jīng)過遺傳算法求解結(jié)果在信息素初值設(shè)置的表現(xiàn)，不難看出GAAA 算法是一個逐步收斂的過程，從均值與分布的角度來看，具有非常高的求解精度，圖9 是應(yīng)用GAAA 算法得到的最優(yōu)解，與采用其他方法得到的最

30、優(yōu)解結(jié)果一致.圖10圖11找到的解與最優(yōu)解非常接近，是其它算法容易陷入舉步最優(yōu)的幾個值，由于在遺傳階段采用隨機產(chǎn)生種群，因而有效避免了陷入舉步最優(yōu). 表1 GAAA 算法優(yōu)化解數(shù)據(jù)逼近過程圖8 GAAA算法一次隨機遺傳變異后產(chǎn)生的信息素分布圖9 GAAA算法找到的最優(yōu)路徑（423.74）圖10 GAAA算法一次隨機迭代找到的最優(yōu)路徑(424.46)圖11 GAAA算法一次隨機迭代找到的最優(yōu)路徑(424.67)下面的三個表則給出了GAAA算法與基本蟻群算法以及遺傳算法與模擬退火算法結(jié)合方法的實驗結(jié)果比較.表2 GAAA算法實驗結(jié)果表3 基本蟻群算法實驗結(jié)果表4 遺傳算法與模擬退火算法結(jié)合方法實驗

31、結(jié)果通過仿真實驗可以看出，GAAA算法無論在優(yōu)化性能還是時間性能上都能夠取得好的效果，由于在遺傳算法中使用隨機生成種群，不僅加快了蟻群算法的速度還避免了求精解階段陷入局部最優(yōu)，另外，由于采用遺傳算法與蟻群算法結(jié)合，對于蟻群算法中的參數(shù)調(diào)整有較大的減少，從而減少了盲目的實驗次數(shù).在蟻群算法的設(shè)計過程中，為了避免過小導(dǎo)致收斂速度慢的缺陷，還可以通過設(shè)置自適應(yīng)變化的以提高收斂速度，例如，取初始值，當算法求得的最優(yōu)值在規(guī)定的次循環(huán)后還沒有明顯改進時，取其中為調(diào)解因子，一般取，而為的最小值.仿真結(jié)果表明，與基本蟻群算法相比，最優(yōu)解以及收斂性能等方面均有一定的提高. 二、 粒子群算法動物學(xué)家Reynold

32、sf對鳥群的飛翔和群舞行為很感興趣，而動物學(xué)家Heppner則對于大數(shù)目的鳥群為什么能如此一致的朝一個方向飛行、突然同時轉(zhuǎn)向、分散、再聚集很感興趣，這些研究者通過對每個個體的行為建立簡單的數(shù)學(xué)模型，然后在計算機上模擬和再現(xiàn)這些群體行為.基于鳥類的導(dǎo)航成為人們研究的課題。在其他動物群體中，比如畜群、魚群以至于人類群體，社會生物學(xué)家Wilson認為“至少從理論上說，群體中的單個成員在搜尋食物的過程中能夠利用其它成員曾經(jīng)勘測和發(fā)現(xiàn)的關(guān)于食物位置的信息，當事先不確定食物位于什么地方時，這種信息的利用是至關(guān)重要的，這種信息分享的機制遠遠超過了由于群體成員之間的競爭而導(dǎo)致的不利之處”以上對于動物群體的觀察

33、說明了群體成員之間的信息分享是非常重要的，這一點也是粒子群優(yōu)化算法賴以建立的基本原理之一.研究者的另一個動機是希望模擬人的社會行為，即單個的人是怎樣通過調(diào)節(jié)個人的行為以便與其它社會成員和諧一致，并取得最有利于自己的位置.單個的人為了避免與其它社會成員發(fā)生沖突，通常利用自己以前的經(jīng)驗和其它社會成員的經(jīng)驗來調(diào)整自己的行為，這是PSO設(shè)計思想的另一個源泉.若把在某個區(qū)域范圍內(nèi)尋找某個函數(shù)最優(yōu)值的問題看作鳥群覓食行為，區(qū)域中的每個點看作一只鳥，現(xiàn)把它叫粒子，每個粒子之間是協(xié)作的，相互之間是互通信息的.同時每個粒子都利用自己以前的經(jīng)驗和其它社會成員的經(jīng)驗來調(diào)整自己的行為.粒子群算法是一種演化計算技術(shù)，是

34、一種基于迭代的優(yōu)化工具，系統(tǒng)初始化為一組隨機解，通過迭代搜尋最優(yōu)值，將鳥群運動模型中棲息地類比為所求問題空間中可能解的位置，利用個體間的傳遞，導(dǎo)致整個群體向可能解的方向移動，逐步發(fā)現(xiàn)較好解.一、基本粒子群算法粒子群算法，其核心思想是對生物社會性行為的模擬.最初粒子群算法是用來模擬鳥群捕食的過程，假設(shè)一群鳥在捕食，其中的一只發(fā)現(xiàn)了食物，則其他一些鳥會跟隨這只鳥飛向食物處，而另一些會去尋找更好的食物源.在捕食的整個過程中，鳥會利用自身的經(jīng)驗和群體的信息來尋找食物.粒子群算法從鳥群的這種行為得到啟示，并將其用于優(yōu)化問題的求解.若把在某個區(qū)域范圍內(nèi)尋找某個函數(shù)最優(yōu)值的問題看作鳥群覓食行為，區(qū)域中的每個

35、點看作一只鳥，現(xiàn)把它叫粒子（particle).每個粒子都有自己的位置和速度，還有一個由目標函數(shù)決定的適應(yīng)度值.但每次迭代也并不是完全隨機的，如果找到了新的更好的解，將會以此為依據(jù)來尋找下一個解.圖1 給出了粒子運動的思路圖.圖2.4.1粒子運動的路線圖下面給出粒子群算法的數(shù)學(xué)描述.假設(shè)搜索空間是D維的，群中的第i個粒子能用如下D維矢量所表示： (1)每個粒子代表一個潛在的解，這個解有D個維度.每個粒子對應(yīng)著D維搜索空間上的一個點.粒子群優(yōu)化算法的目的是按照預(yù)定目標函數(shù)找到使得目標函數(shù)達到極值的最優(yōu)點.第i個粒子的速度或位置的變化能用如下的D維向量表示： (2)為了更準確地模擬鳥群，在粒子群優(yōu)

36、化中引入了兩個重要的參量.一個是第i個粒子曾經(jīng)發(fā)現(xiàn)過的自身歷史最優(yōu)點(Personal best，pbest)，可以表示為： (3)另一個是整個種群所找到的最優(yōu)點(Global best，gbest)，可以表示為： (4)PSO初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優(yōu)解.在每一次的迭代中，粒子通過跟蹤兩個“極值”(和)來更新自己.在找到這兩個最優(yōu)值后，粒子通過下面的公式來更新自己的速度和位置：(速度更新公式) (5) (位置更新公式) (6)其中稱之為慣性因子，在一般情況下，取，代表迭代序號，G是預(yù)先給出的最大迭代數(shù)；, ，N是群的大??； 和是正的常數(shù)，分別稱為自身認知因子和社會認

37、知因子，用來調(diào)整和的影響強度.和是區(qū)間0，1內(nèi)的隨機數(shù).由(5)和(6)構(gòu)成的粒子群優(yōu)化稱為原始型粒子群優(yōu)化.從社會學(xué)的角度來看公式(5)的第一部分稱為記憶項，表示上次優(yōu)化中的速度的影響；公式第二部分稱為自身認知項，可以認為是當前位置與粒子自身最優(yōu)位置之間的偏差，表示粒子的下一次運動中來源于自己經(jīng)驗的部分；公式的第三部分稱為社會認知項，是一個從當前位置指向種群最佳位置的矢量，反映了群內(nèi)粒子的協(xié)作和知識共享.可見，粒子就是通過自己的經(jīng)驗和同伴中最好的經(jīng)驗來決定下一步的運動.隨著迭代進化的不斷進行，粒子群逐漸聚集到最優(yōu)點處，圖2 給出了某個優(yōu)化過程中粒子逐漸聚集的示意圖.圖2 粒子群在優(yōu)化過程聚集

38、示意圖綜上所述，我們得到如下基本粒子群算法流程：(1) 設(shè)定參數(shù)，初始化粒子群，包括隨機位置和速度；(2) 評價每個粒子的適應(yīng)度；(3) 對每個粒子，將其當前適應(yīng)值與其曾經(jīng)訪問過的最好位置pbest作比較，如果當前值更好，則用當前位置更新pbest；(4) 對每個粒子，將其當前適應(yīng)值與種群最佳位置gbest作比較，如果當前值更好，則用當前位置更新gbest；(5) 根據(jù)速度和位置更新公式更新粒子；(6)若未滿足結(jié)束條件則轉(zhuǎn)第二步；否則停止迭代.迭代終止條件根據(jù)具體問題一般選為迭代至最大迭代次數(shù)或粒子群搜索到的最優(yōu)位置滿足預(yù)定的精度閾值.3 粒子群算法的軌跡分析4 改進的粒子群算法作為一種模擬鳥

39、類遷徙覓食過程建立起來的智能算法，與其他智能算法相比具有非常鮮明的特色，同時也存在一定的缺陷。 優(yōu)點：（1）粒子群算法沒有遺傳算法所需要的交叉和變異運算，僅依靠通過確定粒子的方向和速度完成搜索，并且在迭代進化過程中只有最優(yōu)的粒子將信息傳遞給其它粒子，因此，搜索速度快；（2）粒子群算法具有記憶特性，可以記憶粒子群的歷史最佳位置并傳遞給其它粒子；（3）結(jié)構(gòu)簡單，需要調(diào)整的參數(shù)少，從而易于工程實現(xiàn)；（4）采用實數(shù)編碼，問題解的變量數(shù)直接作為粒子維數(shù)，求解過程直觀。缺陷：（1）容易陷入局部最優(yōu)，收斂早熟以及求解精度低；（2）不能有效解決離散與組合問題以及很難求解非直角坐標系下表示的實際問題等。針對上述

40、基本粒子群算法的缺陷，人們提出了許多改進方案。（1）將各種先進的理論引入到粒子群算法中，得到改進的粒子群算法；（2）將粒子群算法和其它智能優(yōu)化算法相結(jié)合，研究各種混合優(yōu)化算法，達到取長補短、改善算法某方面性能的效果；（3）另外，基本粒子群算法主要針對連續(xù)函數(shù)進行搜索運算，但許多的實際問題都呈現(xiàn)為離散的組合優(yōu)化形式，因此，粒子群算法的離散化就成為第三類改進方法，粒子群算法的離散化又存在兩條不同的途徑：第一種途徑是以標準的連續(xù)粒子群算法為基礎(chǔ)，將所研究的離散問題映射到連續(xù)的粒子運動空間，仍然采用標準的粒子群算法速度以及位置更新策略，適當修改標準PSO算法從而得到問題的解；另一種途徑是針對離散優(yōu)化問

41、題，在保持標準粒子群算法基本思想、算法框架以及信息更新本質(zhì)機理不變的前提下，重新定義合適的粒子群離散表示方式與操作算子以求得問題的解。這兩種方法存在一定的區(qū)別，首先，第一種途徑將實際離散問題映射到粒子連續(xù)運動空間后，在連續(xù)空間中計算求解；第二種途徑則將PSO算法映射到離散空間，在離散空間中求解，因此上述兩種方法經(jīng)常被稱之為基于連續(xù)空間的DPSO與基于離散空間的DPSO。下面分別有代表性的集中算法對上述三類改進粒子群算法作簡單描述。一、加速粒子群算法為了提高粒子群算法的效能并擴展其應(yīng)用范圍，第一種改進措施就是將先進的理論溶入到粒子群算法中，例如：1、帶慣性權(quán)重(inertia weight)粒子

42、群算法及其改進探測是指粒子在較大程度上離開原先的尋優(yōu)軌程，偏到新的方向進行搜索；開發(fā)則指粒子在較大程度上繼續(xù)原先的尋優(yōu)軌程進行細部搜索.為了更好的控制算法的探測和開發(fā)能力，引入慣性權(quán)重w，使得 (5)式改變?yōu)椋?（18）大量的實驗表明，慣性權(quán)重的方法求解優(yōu)化問題時具有下列特點：第一，較大慣性權(quán)重可以加強PSO算法的全局搜索能力，即探索較大的區(qū)域，較快地定位最優(yōu)解的大致位置；較小的慣性權(quán)重能加強PSO算法局部搜索能力，即粒子速度減慢，開始精細的局部搜索；第二，慣性權(quán)重都是由大到小地變化.算法流程圖：(1) 算法參數(shù)設(shè)定其中有一組s參數(shù)，共h個；(2) 對粒子群的隨機位置與速度進行初始化設(shè)置：(3

43、) 將整個粒子群均分為h個子群；(4)對所有子群分別按典型粒子群算法開始運行，其中第一個子群按s1 參數(shù)的慣性權(quán)重曲線運行，第i子群按si參數(shù)的慣性權(quán)重曲線運行；(5)判斷算法收斂準則是否滿足，如果滿足轉(zhuǎn)向第八步；否則執(zhí)行第六步；(6)每間隔一定的迭代步數(shù)測出每個子群獨立的全局極值比較，把有最差全局極值的子群用有最好全局極值的子群替代，整個粒子群變?yōu)閔-1個子群，h-1個子群繼續(xù)按h-1個參數(shù)的慣性權(quán)重曲線運行；(7)判斷算法收斂準則是否滿足，如果滿足執(zhí)行第八步；否則轉(zhuǎn)向第六步；(8)輸出si及相應(yīng)的全局極值，算法運行結(jié)束.其中，初始化粒子群中的位置與速度用均勻分布隨機數(shù)在函數(shù)的定義域范圍產(chǎn)生.根據(jù)上述算法步驟