蟻群算法-粒子群優(yōu)化

粒子群優(yōu)化一.導言二.基本PSO三.標準PSO四.PSO的改進與變形五.學習PSO的幾點體會2PSO的產(chǎn)生Particle

Swarm

Optimization(PSO)，粒子群優(yōu)化或者微粒群優(yōu)化PSO算法由 學者Kennedy

和Eberhart于1995年正式提出Particle

swarm

optimization.

IEEE

InternationalConference

on

Neural

Networks,

1995.A

new

optimizer

using

particle

swarm

theory.The

6th

International

Symposium

on

Micro-machine

and

Human

Science,

1995.一.導言3PSO的產(chǎn)生五年后，在國際上逐步被接受，并有大批不同領(lǐng)域的學者投入該算法相關(guān)研究，目前已經(jīng)成為智能優(yōu)化領(lǐng)域研究的熱門2003年，《控制與決策》第二期刊登國內(nèi)第一篇PSO——綜述文章一.導言4PSO的基本思想對社會行為的模擬對鳥群行為的模擬：Reynolds和Heppner，Grenander在1987年和1990年

的

中都關(guān)注了鳥群群體行動中的蘊涵的美學。他們發(fā)現(xiàn)，由數(shù)目龐大的

組成的鳥群飛行中可以改變方向，散開，或者隊形的重組等等，那么一定有某種潛在的能力或者規(guī)則保證了這些同步的行為。這些科學家都認為上述行為是基于不可預(yù)知的鳥類社會行為中的群體動態(tài)學。在這些早期的模型中他們把重點都放在了

間距的處理，也就是讓鳥群中的 之間保持最優(yōu)的距離。一.導言5PSO的基本思想對社會行為的模擬對魚群行為的研究：1975年，生物社會學家Wilson在

中闡述了對魚群的研究。他在中提出：“至少在理論上，魚群的 成員能夠受益于群體中其他

在尋找食物的過程中發(fā)現(xiàn)的和以前的經(jīng)驗，這種受益是明顯的，它超過了之間的競爭所帶來的利益消耗，不管任何時候食物資源不可預(yù)知的分散于四處?！边@說明，同種生物之間信息的社會共享能夠帶來好處。一.導言6一.導言PSO的基本思想對社會行為的模擬對魚群行為的研究：1975年，生物社會學家Wilson在

中闡述了對魚群的研究。他在中提出：“至少在理論上，魚群的 成員能夠受益于群體中其他

在尋找食物的過程中發(fā)現(xiàn)的和以前的經(jīng)驗，這種受益是明顯的，它超過了之間的競爭所帶來的利益消耗，不管任何時候食物資源不可預(yù)知的分散于四處。”這說明，同種生物之間信息的社會共享能夠帶來好處。這是PSO的基礎(chǔ)7PSO的基本思想對社會行為的模擬對人類的社會行為的模擬：與前者不同，最大區(qū)別在于抽象性！鳥類和魚類是調(diào)節(jié)他們的物理運動，來避免天敵，尋找食物，優(yōu)化環(huán)境的參數(shù)，比如溫度等。人類調(diào)節(jié)的不僅是物理運動，還包括認知和經(jīng)驗。 的是調(diào)節(jié)自己的信仰和態(tài)度，來和社會中的杰出人物或者 ，或者在某件事情上獲得最優(yōu)解的人保持一致。一.導言8PSO的基本思想對社會行為的模擬對人類的社會行為的模擬：c.這種不同導致了計算機仿真上的差別，至少有一個明顯的因素：碰撞（collision）。d.

兩個

即使不被綁在一塊，也具有相同的態(tài)度和信仰，但是兩只鳥是絕對不可能不碰撞而在空間中占據(jù)相同的位置。這是因為動物只能在三維的物理空間中運動，而人類還在抽象的心理空間運動，這里是碰撞的（collision-free）。一.導言9PSO的基本思想速度匹配和“Craziness”鳥群首先在在二 中進行位置的初始化，每個 具有X和Y兩個速度，對鄰居間速度的匹配導致鳥群的行動完全一致，方向也不變化，顯然小鳥不會這么聽話，于是加入了Craziness變量，對坐標增加一些隨機的成分。一.導言10一.導言11PSO的基本思想飛入麥田的最優(yōu)決策鳥群開始不知道麥田在哪，但知道距離麥田多遠，用與麥田的距離遠近來評價小鳥當前位置好不好。怎樣才能飛到麥田中？最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域PSO的基本思想Kennedy和Eberhart對Hepper的模仿鳥群的模型進行了修正，以使粒子能夠飛向解空間，并在最好解處降落，從而得到了PSO算法。PSO在 解空間的搜索可以理解為對人類心理空間的模仿， 在搜索時考慮自己的歷史最好點，這是 經(jīng)驗的積累，同時考慮到群體內(nèi)其他

的共享作用和的歷史最好點，這是社會信息本身具有學習能力的表現(xiàn)。一.導言12名稱的由來：Swarm和ParticleSwarm：在 傳統(tǒng)字典中有三個意思一大群尤指正在行進中的一大群昆蟲或其它細小生物蜂群由蜂王帶領(lǐng)遷移到別處建立一新?lián)c的一群蜜蜂一大群尤指處于

中或成群出動的一大批喧鬧的人或動物一.導言13名稱的由來：Swarm和Particle作者 此詞是借用了Millonas在1994年的中的 的一個應(yīng)用模型中的提法Millonas明確提出群體智能（swarm

in

ligence）的五點原則——在算法的研究中當深思the

proximity

principle：群體能夠執(zhí)行簡單的時間和空間的計算thequalityprinciple：群體能夠響應(yīng)環(huán)境的特征要素一.導言14ligence）名稱的由來：Swarm和ParticleMillonas明確提出群體智能（swarm

in的五點原則the

principleof

diverse

response：群體能夠使自己的行動不被限制在一個狹小的范圍內(nèi)theprincipleofstability：群體不要每次環(huán)境變化都跟著改變自己的行為模式theprincipleofadaptability：群體的行為模式要能夠在值得計算代價的時候發(fā)生改變一.導言15名稱的由來：Swarm和ParticleParticle:算法中有速度和加速度的字眼，這比較適合于粒子。Reeves在1983年的中了粒子系統(tǒng)包括基本粒子團和云、火、煙霧等彌漫性物體作者的想法是讓粒子盡量具有一種普遍性的意義用粒子在超空間（Hyperspace）的飛行來模擬人類的社會性行為一.導言16算法描述及簡要分析一個由m個粒子（Particle）組成的群體（Swarm）在D維搜索空間中以一定的速度飛行，每個粒子在搜索時，考慮到了自己搜索到的歷史最好點和群體內(nèi)（或鄰域內(nèi)）其他粒子的歷史最好點，在此基礎(chǔ)上進行位置（狀態(tài)，也就是解）的變化17二.基本PSO算法描述及簡要分析與GA相類似的問題種群的規(guī)定與初始化：Swarm具有大小，隨機初始化點的好壞如何判斷：通過適值函數(shù)停止準則18二.基本PSO1.

算法描述及簡要分析?還要解決的問題本身所找到的歷史最好點如何進行考慮，也就是讓這個點如何影響下一次迭代？對群體內(nèi)或者鄰域內(nèi)成員所找到的歷史最好點如何進行考慮？粒子的位置如何進行變化？二.基本PSO192.

基本PSO的公式二.基本PSO,

pgDxivi

(vi11

i

m,

1

pi

(

pi1,

pi

2

,

,pg

(

pg1,

pg

2

,202.

基本PSO的公式21二.基本PSO(7.1)(7.2)kkkid

id

1

idid

2gdidid

id

idvk

1

vk

c

(

p

x

)

c

(

p

xk

)xk

1

xk

vk

1

,

U[0,1]基本PSO的公式c1和c2：學習因子（learningfactor）或加速系數(shù)（acceleration

coefficient），一般為正常數(shù)。學習因子使粒子具有自我總結(jié)和向群體中優(yōu)秀學習的能力，從而向自己的歷史最優(yōu)點以及群體內(nèi)或鄰域內(nèi)的歷史最優(yōu)點靠近。通常等于2。二.基本PSO22基本PSO的公式

粒子的速度被限制在一個最大速度Vmax的范圍內(nèi)。引入Vmax的原因：防止計算機溢出對人類學習和觀念轉(zhuǎn)變的模擬它還決定了空間搜索的粒子性23二.基本PSO基本PSO的公式當把群體內(nèi)所有粒子都作為鄰域成員時，得到粒子群優(yōu)化算法的全局版本；當群體 分成員組成鄰域時得到粒子群優(yōu)化算法的局部版本。局部版本中，一般有兩種方式組成鄰域，一種是索引號相臨的粒子組成鄰域，另一種是位置相臨的粒子組成鄰域。粒子群優(yōu)化算法的鄰域定義策略又可以稱為粒子群的鄰域拓撲結(jié)構(gòu)。二.基本PSO24二.基本PSO3.

基本PSO步驟步1：在初始化范圍內(nèi)，對粒子群進行隨機初始化，包括隨機位置和速度。步2：計算每個粒子的適應(yīng)值。步3：對于每個粒子，將其適應(yīng)值與所經(jīng)歷過的最好位置的適應(yīng)值進行比較，如果更好，則將其作為粒子的歷史最優(yōu)值，用當前位置更新

歷史最好位置25二.基本PSO263.

基本PSO步驟步4：對每個粒子，將其歷史最優(yōu)適應(yīng)值與群體內(nèi)或鄰域內(nèi)所經(jīng)歷的最好位置的適應(yīng)值進行比較，若更好，則將其作為當前的全局最好位置。步5：根據(jù)式（7.1）和（7.2）對粒子的速度和位置進行更新步6：若未達到終止條件，則轉(zhuǎn)步2。標準PSO的公式為改善算法收斂性能，Shi和Eberhart在1998年的

中引入了慣性權(quán)重的概念，將速度更新方程修改為（7.3）所示：三.標準PSO1(7.3)k

k

kkidididid

2gdidvk

1

v

c

(

p

x

)

c

(

p

xk

)27標準PSO的公式這里，w稱為慣性權(quán)重，其大小決定了對粒子當前速度繼承的多少，合適的選擇可以使粒子具有均衡的探索和開發(fā)能力?？梢姡綪SO算法是慣性權(quán)重w=1的特殊情況。分析和實驗表明，設(shè)定Vmax的作用可以通過慣性權(quán)重的調(diào)整來實現(xiàn)。現(xiàn)在的PSO基本上使用

Vmax進行初始化，將Vmax設(shè)定為每維變量的變化范圍，而不必進行細致的選擇與調(diào)節(jié)。28三.標準PSO標準PSO的公式目前，對于PSO算法的研究大多以帶有慣性權(quán)重的PSO為對象進行分析、擴展和修正，因此大多數(shù)文獻中將帶有慣性權(quán)重的PSO算法稱為PSO算法的標準版本，或者稱為標準PSO算法；而將前述PSO算法稱為初始PSO算法/基本PSO算法，或者稱為PSO算法的初始版本。29三.標準PSO算法構(gòu)成要素群體大?。簃m是個整型參數(shù)。當m很小的時候，陷入局優(yōu)的可能性很大。然而，群體過大將導致計算時間的大幅增加。并且當群體數(shù)目增長至一定水平時，再增長將不再有顯著的作用。當m

=1的時候，PSO算法變?yōu)榛?/p>

搜索的技術(shù)，一旦陷入局優(yōu)，將不可能跳出。當m很大時，PSO的優(yōu)化能力很好，

收斂的速度將非常慢。三.標準PSO30算法構(gòu)成要素學習因子：c1和c2學習因子使粒子具有自我總結(jié)和向群體中優(yōu)秀個體學習的能力，從而向群體內(nèi)或鄰域內(nèi)最優(yōu)點靠近。c1和c2通常等于2，不過在文獻中也有其他的取值。但是一般c1等于c2，并且范圍在0和4之間。31三.標準PSO算法構(gòu)成要素最大速度：Vmax慣性權(quán)重智能優(yōu)化方法的運行是否成功，探索能力和開發(fā)

能力的平衡是非常關(guān)鍵的。對于粒子群優(yōu)化算法

來說，這兩種能力的平衡就是靠慣性權(quán)重來實現(xiàn)。32三.標準PSO算法構(gòu)成要素鄰域拓撲結(jié)構(gòu)全局版本粒子群優(yōu)化算法將整個群體作為粒子的鄰域，速度快，不過有時會陷入局部最優(yōu)；局部版本粒子群優(yōu)化算法將索引號相近或者位置相近的作為粒子的鄰域，收斂速度慢一點，不過很難陷入局部最優(yōu)。顯然，全局版本的粒子群優(yōu)化算法可以看作局部版本粒子群優(yōu)化算法的一個特例，即將整個群體都作為鄰域。停止準則三.標準PSO33算法構(gòu)成要素粒子的初始化較好地選擇粒子的初始化空間，將大大縮短收斂時間。這是問題依賴的。34三.標準PSO重要的參數(shù)：慣性權(quán)重和鄰域定義計算舉例求解無約束優(yōu)化問題：5維的Rosenbrock函數(shù)35三.標準PSOn1i1

x2

)2

(x

1)2

)i

ii1x[30,30]nmin

f

(x)

(100(x計算舉例簡單分析：Rosenbrock是一個著名的測試函數(shù)，也叫香蕉函數(shù)，其特點是該函數(shù)雖然是單峰函數(shù)，在[100，100]n上只有一個全局極小點，但它在全局極小點的狹長區(qū)域內(nèi)取值變化極為緩慢，常用于評價算法的搜索性能。這種實優(yōu)化問題非常適合于使用粒子群優(yōu)化算法來求解。三.標準PSO36計算舉例算法設(shè)計編碼：因為問題的維數(shù)為5，所以每個粒子為5維的實數(shù)向量。初始化范圍：根據(jù)問題要求，設(shè)定為[-30，30]。根據(jù)前面的參數(shù)分析，知道，可以將最大速度設(shè)定為Vmax=60。種群大?。簽榱苏f明方便，這里采用一個較小的種群規(guī)模，m=5。停止準則：設(shè)定為最大迭代次數(shù)100次。三.標準PSO37計算舉例算法設(shè)計慣性權(quán)重：采用固定權(quán)重0.5。鄰域拓撲結(jié)構(gòu)：使用星形拓撲結(jié)構(gòu)，即全局版本的粒子群優(yōu)化算法。38三.標準PSO計算舉例一次迭代后的結(jié)果三.標準PSO

11121304x

2.4265985,

29.665405,

18.387815,

29.660393,

-39.97371x

22.56745,

-3.999012,

-19.23571,

-16.373426,

-45.417023x

30.34029,

-4.6773186,

5.7844753,

5.4156475,

-43.92349

05x

2.7943296,

19.942759,

-24.861498,

16.060974,

-57.757202x

27.509708,

28.379063,

13.016331,

11.539068,

-53.67677739計算舉例一次迭代后的結(jié)果從上面的數(shù)據(jù)可以看到，粒子有的分量跑出了初始化范圍。需要說明的是，在這種情況下，一般不強行將粒子重新拉回到初始化空間，即使初始化空間也是粒子的約束空間。因為，即使粒子跑出初始化空間，隨著迭代的進行，如果在初始化空間內(nèi)有更好的解存在，那么粒子也可以自行返回到初始化空間。有研究表明，即使將初始化空間不設(shè)定為問題的約束空間，即問題的最優(yōu)解不在初始化空間內(nèi)，粒子也可能找到最優(yōu)解。三.標準PSO403.

計算舉例三.標準PSO41慣性權(quán)重固定權(quán)重即賦予慣性權(quán)重以一個常數(shù)值，一般來說，該值

在0和1之間。固定的慣性權(quán)重使粒子在飛行中始

終具有相同的探索和開發(fā)能力。顯然，對于不同

的問題，獲得最好優(yōu)化效果的這個常數(shù)是不同的，要找到這個值需要大量的實驗。通過實驗

發(fā)現(xiàn)：種群規(guī)模越小，需要的慣性權(quán)重越大，因為

此時種群需要更好的探索能力來彌補粒子數(shù)量的

不足，否則粒子極易收斂；種群規(guī)模越大，需要

的慣性權(quán)重越小，因為每個粒子可以更專注于搜

索自己附近的區(qū)域。四.PSO的改進與變形42四.PSO的改進與變形慣性權(quán)重時變權(quán)重一般來說，希望粒子群在飛行開始的時候具有較好的探索能力，而隨著迭代次數(shù)的增加，特別是在飛行的后期，希望具有較好的開發(fā)能力。所以希望動態(tài)調(diào)節(jié)慣性權(quán)重?？梢酝ㄟ^時變權(quán)重的設(shè)置來實現(xiàn)。設(shè)慣性權(quán)重的取值范圍為：min

,max

最大迭代次數(shù)為Iter_max，則第i次迭代時的慣性權(quán)重可以取為：max43iIter

_

max

max

min

i慣性權(quán)重模糊權(quán)重模糊權(quán)重是使用模糊系統(tǒng)來動態(tài)調(diào)節(jié)慣性權(quán)重。下面的文獻給出了一種模糊權(quán)重的設(shè)置方式Shi

Y,

Eberhart

R.

Fuzzy

adaptive

particleswarm

optimization:

IEEE

Int.

Congress

onEvolutionary

Computation

[C].

Piscataway,

NJ:IEEE

Service

Center,

2001:

101-106.44四.PSO的改進與變形1.

慣性權(quán)重隨機權(quán)重隨機權(quán)重是在一定范圍內(nèi)隨機取值。例如可以取值如下：其中，Random為0到1之間的隨機數(shù)。這樣，慣性權(quán)重將在0.5到1之間隨

化，均值為0.75。四.PSO的改進與變形2

0.5

Random45鄰域拓撲結(jié)構(gòu)基于索引號的拓撲結(jié)構(gòu)環(huán)形結(jié)構(gòu)四.PSO的改進與變形46鄰域拓撲結(jié)構(gòu)基于索引號的拓撲結(jié)構(gòu)帶有捷徑的環(huán)形結(jié)構(gòu)四.PSO的改進與變形47鄰域拓撲結(jié)構(gòu)基于索引號的拓撲結(jié)構(gòu)輪形結(jié)構(gòu)四.PSO的改進與變形48鄰域拓撲結(jié)構(gòu)基于索引號的拓撲結(jié)構(gòu)帶有捷徑的輪形結(jié)構(gòu)四.PSO的改進與變形49鄰域拓撲結(jié)構(gòu)基于索引號的拓撲結(jié)構(gòu)星形結(jié)構(gòu)：每個粒子都與種群中的其他所有粒子相連，即將整個種群作為自己的鄰域。也就是粒子群算法的全局版本。這種結(jié)構(gòu)下，所有粒子共享的信息是種群中表現(xiàn)最好的粒子的信息。50四.PSO的改進與變形鄰域拓撲結(jié)構(gòu)基于索引號的拓撲結(jié)構(gòu)隨機結(jié)構(gòu)：隨機結(jié)構(gòu)是在N個粒子的種群中間，隨機地建立N個對稱的兩兩連接。51四.PSO的改進與變形鄰域拓撲結(jié)構(gòu)基于距離的拓撲結(jié)構(gòu)基于距離的拓撲結(jié)構(gòu)是在每次迭代時，計算一個粒子與種群中其他粒子之間的距離，然后根據(jù)這些距離來確定該粒子的鄰域構(gòu)成。一種動態(tài)鄰域拓撲結(jié)構(gòu)：在搜索開始的時候，粒

子的鄰域只有其自己，即將 最優(yōu)解作為鄰域最優(yōu)解，然后隨著迭代次數(shù)的增加，逐漸增大鄰

域，直至最后將群體中所有粒子作為自己的鄰域

成員。這樣使初始迭代時可以有較好的探索性能，而在迭代后期可以有較好的開發(fā)性能。四.PSO的改進與變形52四.PSO的改進與變形53對將要計算鄰域的粒子i，計算其與種群中其他所有粒子的距離。該粒子與粒子l（

l

i

）的距離記為：dist[l]。最大的距離記為：max_dist。定義一個關(guān)于當前迭代次數(shù)的函數(shù)fraction（取值為純小數(shù)）：frac

3.0

ITER

0.6

MAXITERMAXITER當frac

0.9

時，滿足的下列條件的粒子構(gòu)成當前粒子i

的鄰域：

dist[l]

frac

；max-

dist當frac

0.9

，將種群中所有粒子作為當前粒子i

的鄰域。四.PSO的改進與變形學習因子c1和c2同步時變參照時變慣性權(quán)重的設(shè)置方法，將學習因子設(shè)置如下：設(shè)學習因子c1

和c2

的取值范圍為：cmin

,cmax

，最大迭代次數(shù)為

Iter_max，則第

i次迭代時的學習因子取為：1

2i

maxIter

_

max

cmax

cminc

c

c

c

i(7.12)這是一種兩個學習因子同步線性減小的變化方式，所以

這里稱之為同步時變。特別地，Suganthan

在實驗中將參數(shù)設(shè)置為：cmax=3，cmin=0.25但是發(fā)現(xiàn)，這種設(shè)置下，解的質(zhì)量反而下降。54學習因子c1和c2異步時變使兩個學習因子在優(yōu)化過程中隨時間進行不同的變化，所以這里稱之為異步時變。這種設(shè)置的目的是在優(yōu)化初期加強全局搜索，而在搜索后期促使粒子收斂于全局最優(yōu)解。這種想法可以通過隨著時間不斷減小自我學習因子c1，和不斷增大社會學習因子c2來實現(xiàn)。四.PSO的改進與變形55學習因子c1和c2異步時變在優(yōu)化的初始階段，粒子具有較大的自我學習能力和較小的社會學習能力，這樣粒子可以傾向于在整個搜索空間飛行，而不是很快就飛向群體最優(yōu)解；在優(yōu)化的后期，粒子具有較大的社會學習能力和較小的自我學習能力，使粒子傾向于飛向全局最優(yōu)解。56四.PSO的改進與變形四.PSO的改進與變形具體實現(xiàn)方式如下：11i1i1

fIter

_

maxc

c

c

iter

c(7.13)2iIter

_

m