淺談幾種智能優(yōu)化算法

1、淺談幾種智能優(yōu)化算法摘要：該文首先介紹介紹了幾種典型的群體智能算法，具體包括遺傳算法、蟻群算法和粒子群算法，并對它們進行 了詳細的分析。關(guān)鍵詞：智能算法；蟻群算法；遺傳算法；粒子群算法中圖分類號：TP301 文獻標識碼：A 文章編號：1009-3044(2011)19-4628-03Empirical Study on Several Typical Intelligence AlgorithmsHalqam?Ablat(Sub Institute of Mathematics and Information Technology, Xinjiang Education Institute,

2、Urumqi 830043, China)Abstract: In this essay, the author introduce several typical swarm intelligence algorithms includes genetic algorithm, ant colony optimization algorithm and particle swarm optimization algorithm.Key words: intelligence algorithm; genetic algorithm; ant colony algorithm; particl

3、e swarm algorithm1 概述為了使系統(tǒng)達到最優(yōu)的目標所提出的各種求解方法稱為最優(yōu)化方法。最優(yōu)化在運籌學和管理科學中起著核心作用。最優(yōu)化通常是極大或極小某個多變量的函數(shù)并滿足一些等式或不等式約束。最優(yōu)化技術(shù)對社會的影響日益增加，應用的種類和數(shù)量快速增加，絲毫沒有減緩的趨勢。近幾年來，隨著計算機的發(fā)展，一些過去無法解決的復雜優(yōu)化問題已經(jīng)能夠通過計算機來求得近似解，所以，計算機求解優(yōu)化問題的方法研究也就顯得越來越重要了。對于簡單的函數(shù)優(yōu)化問題，經(jīng)典算法比較有效，且能獲得函數(shù)的精確最優(yōu)解。但是對于具有非線性、多極值等特點的復雜函數(shù)及組合優(yōu)化問題而言，經(jīng)典算法往往無能為力?；谙到y(tǒng)動態(tài)演化

4、的算法及基于此類算法而構(gòu)成的混合型算法又可稱為智能優(yōu)化算法。近年來 ，隨著優(yōu)化理論的發(fā)展，一些新的智能算法得到了迅速發(fā)展和廣泛應用，成為解決傳統(tǒng)優(yōu)化問題的新方法，如遺傳算法、蟻群算法、粒子群算法等。2 蟻群算法蟻群算法是受到對真實蟻群行為的研究的啟發(fā)而提出的。生物學研究表明一群互相協(xié)作的螞蟻能夠找到食物源和巢穴之間的最短路徑，而單只螞蟻卻不能。因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。螞蟻個體之間就是通過這種間接的通信機制達到協(xié)同搜索食物最短路徑的目的。螞蟻覓食協(xié)作方式的本質(zhì)是：1 )路徑概率選擇機制：信息素蹤跡越

5、濃的路徑，被選中的概率越大；2)信息素更新機制：路徑越短，在上面的信息素蹤跡濃度增長越快；3)協(xié)同工作機制：螞蟻之間通過信息素進行通信。在蟻群優(yōu)化算法中，作為分布智能體(Distributed gent)的人工蟻(Artificial Ants) 的行為可以如下描述：一群人工蟻相互協(xié)作在問題的解空間中搜索好的解，這些人工蟻按照人工信息素蹤跡和基于問題的啟發(fā)式信息的指引在問題空間移動以構(gòu)造問題的解。在此， 信息素 (Pheromone)類似于一種分布式的長期記憶，這種記憶不是局部地存在于單個的人工蟻，而是全局地分布在整個問題空間。當人工蟻在問題空間中移動時，它們在其經(jīng)過的路徑上留下信息素蹤跡，這

6、些蹤跡反映了人工蟻在問題空間覓食(即構(gòu)造好的解)過程中的經(jīng)歷。換句話說，信息素在蟻群的協(xié)作和通信中起到一種間接媒介的作用。人工蟻在解空間中一步一步地移動從而構(gòu)造問題的解，同時，它們根據(jù)解的質(zhì)量在其路徑上留下相應濃度的信息素，蟻群中其他螞蟻傾向于沿著信息素濃的路徑前進，同樣這些螞蟻也將在這段路徑上留下自己的信息素，這就形成了一種自催化強化學習機制，也就是正反饋。這種正反饋機制將指引蟻群找到高質(zhì)量的問題解。3 遺傳算法遺傳算法(Genetic Agorithm) 是模擬生物在自然環(huán)境中 優(yōu)勝劣汰、適者生存的遺傳和進化過程而形成的一種具有自適應能力的、全局性的概率搜索算法。遺傳算法是從代表待優(yōu)化問題

7、潛在解集的一個種群開始，而種群則由經(jīng)過基因編碼的一定數(shù)目的個體組成?；蚓幋a成染色體，每個個體由染色體構(gòu)成，每個個體實際上是帶有染色體特征的實體。染色體作為遺傳物質(zhì)的主要載體，是多個基因的集合，其內(nèi)部表現(xiàn)（即基因型）是多個基因的某種組合，它決定了個體的形狀的外部表現(xiàn)。因此，在一開始需要實現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出活應冷越來越好的個體。在每一代中，根據(jù)問題域中個體的適應度的優(yōu)劣，選擇一些適應度高的個體，基于這些選出的適應度高的個體，并借助于自然遺傳學的交叉、變異算子，產(chǎn)生出代表新解集的下一代種群。這個過程將導致種群像自然進化

8、一樣，使后生代種群比前代種群具有更高的適應度，更加適應于環(huán)境。在優(yōu)化過程結(jié)束后，末代種群中的最優(yōu)個體經(jīng)過解碼，即可以作為問題的近似最優(yōu)解。遺傳算法是將問題的每一個可能性解看作是群體中的一個個體（染色體），并將每一個染色體編碼成串的形式，再根據(jù)預定的目標函數(shù)對每個個體進行評價，給出一個適應值。算法將根據(jù)適應度值進行它的尋優(yōu)過程，遺傳算法的尋優(yōu)過程是通過選擇、雜交和變異三個遺傳算子來具體實現(xiàn)的。4 PSO算法及其改進4.1 PSO簡介粒子群優(yōu)化算法(PSO)是一種進化算法，經(jīng)典粒子群算法的基本思想是模擬鳥類群體行為，并利用了生物學家的生物群體模型，因為鳥類的生活使用了簡單的規(guī)則：1 )飛離最近的個

9、體；2)飛向目標；3)飛向群體的中心；來確定自己的飛行方向和飛行速度，并且成功的尋找到棲息地。PSO算法就從這種生物種群行為特性中得到啟發(fā)并用于求解優(yōu)化問題。如果我們把一個優(yōu)化問題看作是在空中覓食的鳥群，那么在空中飛行的一只覓食的“鳥”就是 PSO算法中在解空間中進行搜索的一個“粒子”( Particle) ，也是優(yōu)化問題的一個解。 “食物”就是優(yōu)化問題的最優(yōu)解。粒子的概念是一個折衷的選擇，它只有速度和加速度用于本身狀態(tài)的調(diào)整，沒有質(zhì)量和體積。PSO算法中每個粒子即解空間中的一個解，它根據(jù)自己的飛行經(jīng)驗和同伴的飛行經(jīng)驗來調(diào)整自己的飛行。每個粒子在飛行過程所經(jīng)歷過的最好位置，就是粒子本身找到的最

10、優(yōu)解。整個群體所經(jīng)歷過的的最好位置，就是整個群體目前找到的最優(yōu)解。前者叫做個體極值(pbest)，后者叫做全局極值(gbest)。每個粒子都通過上述兩個極值小斷更新自己，從而產(chǎn)生新一代群體。實際操作中通過由優(yōu)化問題所決定的適應度函數(shù)值(fitnessvalue)來評價粒子的 “好壞” 程度。顯然，每 個粒子的行為就是追隨著當前的最優(yōu)粒子在解空間中搜索。在PSO算法中每個粒子可以看作是解空間中的一個點。如果粒子的群體規(guī)模為N，則第i( i=1,2, ,N)個粒子的位置可表示為Xi,并在搜索空間中以一定的速度飛行，第i 個粒子的飛行速度可表示為Vi。該飛行速度是根據(jù)個體的飛行經(jīng)驗和群體的飛行經(jīng)驗來

11、進行動態(tài)地調(diào)整。假設(shè)矢量：Xi=(xi1,xi2, ,xim)表示微粒i 的當前位置；Vi=(vi1,vi2, ,vim)表示微粒i 的當前飛行速度；Pi=(pi1,pi2, ,pim)表示微粒i 所經(jīng)歷過的具有最好適應度值的位置，稱為個體i 所經(jīng)歷的最佳位置(又稱局部最優(yōu)點) 。設(shè)f(X)為需要最大化的目標函數(shù)，則微粒i 目前的個體最好位置由下式確定：( 1)群體中的微粒數(shù)為N，群體中所有微粒所經(jīng)歷過的最佳位置Pg(t),稱為全局最佳位置。則：( 2)Kennedy和 Eberhart 最早提出的PSO算法的進化方程如下：( 3)( 4)其中：下標“i”表示第i 個微粒，下標“j”表示的是微

12、粒 i 的第 j 維分量，t 表示第 t 代，學習因子c1,c2為非負常數(shù)， c1 用來調(diào)節(jié)微粒向本身最好位置飛行的步長，c2 用來調(diào)節(jié)微粒向群體最好位置飛行的步長，通常c1,c2在 0,2 間取值。 r1j(t),r2j(t) 是兩個介于0,1之間的服從均勻分布的隨機數(shù)，即： r1j(t)U(0,1)， r2j(t)U(0,1)。為了減少在優(yōu)化過程中，微粒飛出搜索空間的可能性，vij(t)通常限定在一定的范圍內(nèi)，即 vij vmin,vmax 。 vmin、 vmax是根據(jù)具體問題而人為設(shè)定的，同時人們也會根據(jù)具體問題，限定搜索空間xijxmin,xmax。迭代終止條件根據(jù)具體問題一般選為最

13、大迭代次數(shù)或粒子群搜索到的最優(yōu)位置滿足于預先設(shè)定的精度。為了方便起見，我們將經(jīng)典微粒群算法的形式表述如下：( 5)( 6)4.2 改進的PSO算法正如先前所述，公式(5)由三部分組成：第一部分是粒子先前的速度項，即Vi(t)，第二部分和第三部分是導致粒子速度變化的兩項，即 c1× r1 × (Pi(t)-Xi(t)和c2× r2× (Pg(t)-Xi(t)。一方面，如果沒有后兩項，粒子將保持在相同的方向上以當前的速度“飛翔”至下一個點，直至達到邊界值。這樣的 PSO將不能找到一個可接受的解，除非這樣的飛行軌跡是一種合理的方案，而這在現(xiàn)實中是非常少見的。另

14、一方面，如果沒有第一項，那么“飛翔”粒子的速度僅僅取決于粒子的當前位置和它們最好的歷史位置。速度自身是沒有記憶性的。假設(shè)在開始的時候，粒子i 正好是整體最好所在的點，那么粒子i 將以速度為0“飛翔”，這將保持粒子此次的位置不變，直到出現(xiàn)新的一個最好點替代粒子i。同時，每一個粒子將向自身最好點和整體最好點的質(zhì)心方向“飛翔” 。因此可以想像在沒有第一項情況下的PSO搜索過程，其搜索空間將在迭代中逐漸衰退，這類似于局部搜索算法。只有當全局最好點包含在初始搜索空間內(nèi)的時候，才有可能找到滿意解。這樣，最終解在很大程度上要依賴于初始化種群。這也說明了在沒有第一項內(nèi)容的情況下，PSO算法更多的顯現(xiàn)的是局部搜

15、索能力。從另一層意思來說，第一項內(nèi)容使得粒子有一種擴展搜索空間的能力，即開拓能力( explore ability ) ，是一種全局搜索能力的表現(xiàn)。在各類問題的解決中，局部搜索和全局搜索都起著重要作用。對于某一類優(yōu)化問題的具體解決中，我們應該權(quán)衡局部搜索和全局搜索的貢獻。Y.Shi和 Eberhart 在 1998 年對微粒群算法引入了慣性權(quán)重w(t) ，并提出了在進化過程中線性調(diào)整慣性權(quán)重的方法，以起到權(quán)衡全局搜索和局部搜索能力。慣性權(quán)重因子W 可以是個整數(shù)，也可以是以時間為變量的線性或非線性正整數(shù)。該方程已被學者們稱為標準PSO算法，這樣公式就變?yōu)椋?)( 8)當慣性權(quán)重w(t)=1 時，

16、式(3)與式(7)相同，從而表明代慣性權(quán)重的微粒群算法是基本微粒群算法的擴展，建議w(t)的取值范圍為0,1.4，但實驗結(jié)果表明當w(t)取 0.8,1.2時， 算法收斂速度更快，而當 w(t) > 1.2時， 算法則較多的陷入局部極值。慣性權(quán)重w(t) 表明微粒的原先的速度能在多大的程度上得到保留，較大的w(t) 值有較好的全局搜索能力，而較小的w(t) 則由較強的局部搜索能力。因此，隨著迭代次數(shù)的增加，線性的減小慣性權(quán)重w(t)，就可以使得微粒群算法在初期具有較強的全局收斂能力，而在晚期具有較強的局部收斂能力。當慣性權(quán)重w(t) 滿足：( 9)即 w(t)隨著迭代線性地從m 遞減到

17、n( 通常 m=1.2,n=0.4)時，從幾個測試函數(shù)的測試結(jié)果來看，效果很好。等式(9)中的 max_circletimes 為最大截止代數(shù)，對于慣性權(quán)重w(t)來說， 由于不同的問題，其每一代所需的比例關(guān)系并不相同，這樣，線性的遞減關(guān)系并不是對所有的問題都會最佳。又有學者提出了基于模糊系統(tǒng)的慣性權(quán)重的動態(tài)調(diào)整。5 結(jié)束語本論文介紹了幾種典型的智能算法：蟻群算法、遺傳算法和粒子群算法，并進行了較深入的闡述。參考文獻：1 徐成賢,陳志平,李乃成.近代優(yōu)化方法M. 北京:科學出版社 ,2002:24-27.2 丁建立,陳增強,袁著祉.基于自適應螞蟻算法的動態(tài)最優(yōu)路由選擇J.控制與決策,2003,18(6):751-753.3 張紀會,高齊圣,徐心和.自適應蟻群算法J.控制理論與應用,2000,17(1):1-3.4 魏平 ,熊偉清.一種求解函數(shù)優(yōu)化的蟻群算法J.計算機科學,2002,29(9):227-229.5 潘峰 ,陳杰 ,甘明剛,等 .粒子群優(yōu)化算法模型分析J.自動化學報,2006(3):368-377.6 Kennedy J,Eberhart R C.Particle swarm optimizationC.Pr