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

1、淺談幾種智能優(yōu)化算法摘要：該文首先介紹介紹了幾種典型的群體智能算法，具體包括遺傳算法、蟻群算法和粒子群算法，并對(duì)它們進(jìn)行 了詳細(xì)的分析。關(guān)鍵詞：智能算法；蟻群算法；遺傳算法；粒子群算法中圖分類(lèi)號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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)達(dá)到最優(yōu)的目標(biāo)所提出的各種求解方法稱為最優(yōu)化方法。最優(yōu)化在運(yùn)籌學(xué)和管理科學(xué)中起著核心作用。最優(yōu)化通常是極大或極小某個(gè)多變量的函數(shù)并滿足一些等式或不等式約束。最優(yōu)化技術(shù)對(duì)社會(huì)的影響日益增加，應(yīng)用的種類(lèi)和數(shù)量快速增加，絲毫沒(méi)有減緩的趨勢(shì)。近幾年來(lái)，隨著計(jì)算機(jī)的發(fā)展，一些過(guò)去無(wú)法解決的復(fù)雜優(yōu)化問(wèn)題已經(jīng)能夠通過(guò)計(jì)算機(jī)來(lái)求得近似解，所以，計(jì)算機(jī)求解優(yōu)化問(wèn)題的方法研究也就顯得越來(lái)越重要了。對(duì)于簡(jiǎn)單的函數(shù)優(yōu)化問(wèn)題，經(jīng)典算法比較有效，且能獲得函數(shù)的精確最優(yōu)解。但是對(duì)于具有非線性、多極值等特點(diǎn)的復(fù)雜函數(shù)及組合優(yōu)化問(wèn)題而言，經(jīng)典算法往往無(wú)能為力?；谙到y(tǒng)動(dòng)態(tài)演化

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

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

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

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

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

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

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

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

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

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

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

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

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

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