粒子群算法介紹及深入

-------------精選文檔-----------------粒子群算一、粒子算法的歷史粒子群算法源于復(fù)雜適應(yīng)系統(tǒng)ComplexAdaptive理論于1994年正式提出的成員稱為主體如研究鳥群系統(tǒng)個鳥在這個系統(tǒng)中就稱為主體應(yīng)性環(huán)境及其他的主體進行交流，并且根據(jù)交流的過程“學(xué)習(xí)”或“積累經(jīng)驗”改變自身結(jié)構(gòu)與行為統(tǒng)的演變或進化包括：新層次的產(chǎn)生（小鳥的出生）；分化和多樣性的出現(xiàn)（鳥群中的鳥分成許多小的群）；新的主題的出現(xiàn)（鳥尋找食物過程中，不斷發(fā)現(xiàn)新的食物）。所以CAS統(tǒng)中的主體具有4個基本特特點是粒子群算法發(fā)展變化的依據(jù)）：

首先，主體是主動的、活動的。主體與環(huán)境及其他主體是相互影響互作用的種影響是系統(tǒng)發(fā)展變化的主要動力。環(huán)境的影響是宏觀的的影響是微觀的觀要有機結(jié)合。最后，整個系統(tǒng)可能還要受一些隨機因素的影響。粒子群算法就是對一個CAS系統(tǒng)－－－鳥群社會系統(tǒng)的研究得出的。粒子群算法（ParticleSwarmOptimization,PSO）最早是由Eberhart和Kennedy1995提出，它的基本概念源于對鳥群覓食行為的研究。設(shè)想這樣一個場景:一群鳥在隨機搜尋食物，在這個區(qū)域里只有一塊食物，所有的鳥都不知道食物在哪里是它們知道當(dāng)前的位置離食物還有多遠(yuǎn)么找到食物可編輯-------------精選文檔-----------------的最優(yōu)策略是什么呢?最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。PSO法就從這種生物種群行為特性中得到啟發(fā)并用于求解優(yōu)化問題。在PSO，每個優(yōu)化問題的潛在解都可以想象成d維搜索空間上的一個點，我們稱之為“粒子”（Particle，所有的粒子都有一個被目標(biāo)函數(shù)決定的適應(yīng)值(FitnessValue，個粒子還有一個速度決定他們飛翔的方向和距離，然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索鳥群飛行的研究發(fā)現(xiàn)。鳥僅僅是追蹤它有限數(shù)量的鄰居但最終的整體結(jié)果是整個鳥群好像在一個中心的控制之下.即復(fù)雜的全局行為是由簡單規(guī)則的相互作用引起的。二、粒子群法的具體表述上面羅嗦了半天，那些都是科研工作者寫論文的語氣，不過，PSO歷史就像上面說的那樣。下面通俗的解釋PSO法。PSO算法就是模擬一群鳥尋找食物的過程鳥就是PSO中的粒子就是我們需要求解問題的可能解些鳥在尋找食物的過程中停改變自己在空中飛行的位置與速度家也可以觀察一下群在尋找食物的過程中始鳥群比較分散，逐漸這些鳥就會聚成一群，這個群忽高忽低、忽左忽右，直到最后找到食物。這個過程我們轉(zhuǎn)化為一個數(shù)學(xué)問題。尋找函數(shù)

y=1-cos(3*x)*exp(-x)

的在[0,4]最大值。該函數(shù)的圖形如下：可編輯-------------精選文檔-----------------當(dāng)x=0.9350-0.9450到最大值y=1.3706。為了得到該函數(shù)的最大值，我們在[0之間隨機的灑一些點，為了演示，我們放置兩個點，并且計算這兩個點的函數(shù)值，同時給這兩個點設(shè)置[0間的一個速度。下面這些點就會按照一定的公式更改自己的位置達(dá)新位置后計算這兩個點的值后再按照一定的公式更新自己的位置到最后在y=1.3706個點停止自己的更新個過程與粒子群算法作為對照如下：

這兩個點就是粒子群算法中的粒子。該函數(shù)的最大值就是鳥群中的食物計算兩個點函數(shù)值就是粒子群算法中的適應(yīng)值的函數(shù)就是粒子群算法中的適應(yīng)度函數(shù)。更新自己位置的一定公式就是粒子群算法中的位置速度更新公式。下面演示一下這個算法運行一次的大概過程：可編輯-------------精選文檔-----------------可編輯-------------精選文檔-----------------21次可編輯-------------精選文檔-----------------標(biāo)準(zhǔn)的粒子算法在上一節(jié)的敘述中，唯一沒有給大家介紹的就是函數(shù)的這些隨機的點（粒子如何運動的是說按照一定的公式更新個公式就是粒子群算法中的位置速度更新公式。下面就介紹這個公式是什么。在上一節(jié)中我們求取函數(shù)的在[0,4]最大值。并[0,4]之間放置了兩個隨機的點，這些點的坐標(biāo)假設(shè)為x1=1.5；x2=2.5這里的點是一個標(biāo)量，但是我們經(jīng)常遇到的問題可能是更一般的情況－－x一個矢量的情況，比如二維的情可編輯ii2i3iii2i3ii2i3i，iggg2g況z=2*x1+3*x2

2

-------------精選文檔-----------------的情況。這個時候我們的每個粒子為二維，記粒子n粒子群群體的規(guī)模，也就是這個群中粒子的個數(shù)，每個粒子的維數(shù)2。更一般的是粒子的維數(shù)為q，這樣在這個種群中有n個粒子，每個粒子為q維。由個粒子組成的群體對就是每個粒子的維數(shù)）空間進行搜索。每個粒子表示為：x（x,x,x,...,x），每個粒子對應(yīng)的速度可以表示為v,v,v,....,v)，每個粒子在搜索時要考慮兩個因素：1自己搜索到的歷史最優(yōu)值p

p,p,....,p，i=1,2,3,....,n2搜索到的最優(yōu)值pp=(p,p,....,p的p只有一個。下面給出粒子群算法的位置速度更新公式：這里有幾個重要的參數(shù)需要大家記憶后的講解中將會經(jīng)常用到：它們是：慣2?！?[0,1]區(qū)間內(nèi)做約。通常設(shè)可編輯i。ik。i。ik。-------------精選文檔-----------------粒子是同）叫群優(yōu)標(biāo)準(zhǔn)的粒子群算法(部版本)在

全局版的標(biāo)準(zhǔn)粒子群算法中個粒子的速度的更新是根據(jù)兩個因素來變化的，這兩個因素是：1.粒子自己歷史最優(yōu)值p2.粒子群體的全局最優(yōu)值p

g。如果改變粒子速度更新公式，讓每個粒子的速度的更新根據(jù)以下兩個因素更新，A.粒子自己歷史最優(yōu)值pB.粒子鄰域內(nèi)粒子的最優(yōu)值pn其余保持跟全局版的標(biāo)準(zhǔn)粒子群算法一樣，這個算法就變?yōu)榫植堪娴牧Ｗ尤核惴??？删庉?------------精選文檔-----------------一般一個粒子i的鄰域隨著迭代次數(shù)的增加而逐漸增加，開始第一次迭代，它的鄰域為0，隨著迭代次數(shù)鄰域線性變大，最后鄰域擴展到整個粒子群，這時就變成全局版本的粒子群算法了過實踐證明局版本的粒子群算法收斂速度快是容易陷入局部最優(yōu)部版本的粒子群算法收斂速度慢是很難陷入局部最優(yōu)粒子群算法大都在收斂速度與擺脫局部最優(yōu)兩個方面下功夫。其實這兩個方面是矛盾的。看如何更好的折中了。根據(jù)取鄰域的方式的不同，局部版本的粒子群算法有很多不同的實現(xiàn)方法。第一種方法：按照粒子的編號取粒子的鄰域，取法有四種1，環(huán)形取法2隨機環(huán)形取法3輪形取法4隨機輪形取法。1環(huán)形2隨機環(huán)形3輪形4隨機輪形因為后面有以環(huán)形取法實現(xiàn)的算法，對環(huán)形取法在這里做一點點說明：以粒為例，當(dāng)鄰域是0的時候，鄰域是它本身，當(dāng)鄰域是時，鄰域為2，8；當(dāng)鄰域是2時，鄰域是2，7，8；......，以此類推，一直到鄰域為4，這個時候，鄰域擴展到整個例子群體。據(jù)文獻介紹（國外的文獻，采用輪形拓?fù)浣Y(jié)構(gòu)，PSO效果很好。可編輯abaababab-------------精選文檔-----------------第二種方法：按照粒子的歐式距離取粒子的鄰域在第一種方法中，按照粒子的編號來得到粒子的鄰域，但是這些粒子其實可能在實際位置上并不相鄰，于是Suganthan提出基于空間距離的劃分方案，在迭代中計算每一個粒子與群中其他粒子的距離個粒子間的的最大距離為對每一粒子按||x-x||/dm算一個比值。其||x-x||是當(dāng)前粒子ab距離。而選擇閾值frac據(jù)迭代次數(shù)而變化。當(dāng)另一粒子滿足||x-x||/dm<frac，認(rèn)為b成為當(dāng)前粒子的鄰域。這種辦法經(jīng)過實驗得較好的應(yīng)用效果是由于要計算所有粒子之間的距離，計算量大，且需要很大的存儲空間，所以，方法一般不經(jīng)常使用。粒子群算法分類粒

子群算法主要分為4大的分支：（1標(biāo)準(zhǔn)粒子群算法的變形在這個分支中，主要是對標(biāo)準(zhǔn)粒子群算法的慣性因子、收斂因子（約束因子）、“認(rèn)知”部分c1，“社會”部分的行變化與調(diào)節(jié)，希望獲得好的效果。慣性因子的原始版本是保持不變的來有人提出隨著算法迭代的進行性因子需要逐漸減小的思想法開始階段的慣性因子可以是算法不容易陷入局部最優(yōu)算法的后期的慣性因子可以使收斂速度加快收斂更加平穩(wěn)，不至于出現(xiàn)振蕩現(xiàn)象。經(jīng)測試態(tài)的減小慣性因子，的確可以使算法更加穩(wěn)定果比較好是遞減慣性因子采用什么樣的方法呢？人們首先想到的是線型遞減種策略的確很好是是不是最優(yōu)的呢？于是有人對遞減的策略作了研究究結(jié)果指出型函數(shù)的遞減優(yōu)于凸函數(shù)的遞減策略是可編輯gg-------------精選文檔-----------------凹函數(shù)的遞減策略又優(yōu)于線型的遞減過本人測試驗結(jié)果基本符合這個結(jié)論，但是效果不是很明顯。對于收斂因子，經(jīng)過證明如果收斂因子取0.729,以確保算法的收斂，但是不能保證算法收斂到全局最優(yōu)，經(jīng)過本人測試，取收斂因子為0.729果較好。對于社會與認(rèn)知的系數(shù)c2,c1有人提出大后小小后大的思想，因為在算法運行初期，每個鳥要有大的自己的認(rèn)知部分而又比較小的社會部分，這個與我們自己一群人找東西的情形比較接近為在我們找東西的初期們基本依靠自己的知識取尋找后來們積累的經(jīng)驗越來越豐富是大家開始逐漸達(dá)成共識（社會知識），這樣我們就開始依靠社會知識來尋找東西了。2007希臘的兩位學(xué)者提出將收斂速度比較快的全局版本的粒子群算法與不容易陷入局部最優(yōu)的局部版本的粒子群算法相結(jié)合的辦法，利用的公式是局版本)＋）*v(局部版本)

速度更新公式，v代速度w＋1）＋v

位置更新公式該算法在文獻中討論了系數(shù)n取各種不同情況的情況，并且運行來了20000來分析各種系數(shù)的結(jié)果。（2粒子群算法的混合這個分支主要是將粒子群算法與各種算法相混合，有人將它與模擬退火算法相混合些人將它與單純形方法相混合是最多的是將它與遺傳算法的混合。根據(jù)遺傳算法的三種不同算子可以生成3不同的混合算法。粒子群算法與選擇算子的結(jié)合，這里相混合的思想是：在原來的粒子群算法中，我們選擇粒子群群體的最優(yōu)值作為p，但是相結(jié)合的版本是根據(jù)所有粒子的適應(yīng)度的大小給每個粒子賦予一個被選中的概率據(jù)概率對這些粒子可編輯gg-------------精選文檔-----------------進行選擇，被選中的粒子作為p，其它的情況都不變。這樣的算法可以在算法運行過程中保持粒子群的多樣性，但是致命的缺點是收斂速度緩慢。粒子群算法與雜交算子的結(jié)合，結(jié)合的思想與遺傳算法的基本一樣，在算法運行過程中根據(jù)適應(yīng)度的大小子之間可以兩兩雜交如用一個很簡單的公式w（新）＝n×w1＋（1）×w2；w1與w2就是這個新粒子的父輩粒子。這種算法可以在算法的運行過程中引入新的粒子，但是算法一旦陷入局部最優(yōu)，那么粒子群算法將很難擺脫局部最優(yōu)。粒子群算法與變異算子的結(jié)合，結(jié)合的思想：測試所有粒子與當(dāng)前最優(yōu)的距離離小于一定的數(shù)值的時候拿出所有粒子的一個百分％的粒子進行隨機初始化，讓這些粒子重新尋找最優(yōu)值。二進制粒子群算法最初的PSO是從解決連續(xù)優(yōu)化問題發(fā)展起來的.Eberhart等又提出了PSO的離散二進制版.用來解決工程實際中的組合優(yōu)化問題。他們在提出的模型中將粒子的每一維及粒子本身的歷史最優(yōu)局最優(yōu)限制為或0速度不作這種限制。用速度更新位置時，設(shè)定一個閾值，當(dāng)速度高于該閾值時，粒子的位置取1否則取二進制與遺傳算法在形式上很相似，但實驗結(jié)果顯示，在大多數(shù)測試函數(shù)中，二進制PSO遺傳算法速度快，尤其在問題的維數(shù)增加時（4協(xié)同粒子群算法協(xié)同，該方法將粒子的D維分到D粒子群中，每個粒子群優(yōu)化一維向量，評價適應(yīng)度時將這些分量合并為一個完整的向量。例如第i個粒子群，除第i個分量外，其他D-1個分量都設(shè)為最優(yōu)值，不斷用第i個粒子群中的粒子替換可編輯-------------精選文檔-----------------第i個分量，直到得到第i的最優(yōu)值，其他維相同。為將有聯(lián)系的分量劃分在一個群，可將向量分配到m個粒子群優(yōu)化，則前Dmod粒子群的維數(shù)向上取整mod個粒子群的維數(shù)向下取整。協(xié)同PSO某些問題上有更快的收斂速度，但該算法容易被欺騙?；镜牧Ｗ尤核惴ǖ姆种Ь椭鴤€，大部分的粒子群算法都圍繞著這4分支在變化中粒子群算法的變形居多根本上來說乎沒有什么新的思想的提出。標(biāo)準(zhǔn)粒子群算法的實現(xiàn)標(biāo)準(zhǔn)粒子群算法的實現(xiàn)思想基本按照粒子群算法2)----準(zhǔn)的粒子群算法的講述實現(xiàn)。主要分為3函數(shù)。第一個函數(shù)為粒子群初始化函數(shù)InitSwarm(SwarmSize......AdaptFunc)主要作用是初始化粒子群的粒子，并設(shè)定粒子的速度、位置在一定的范圍內(nèi)。本函數(shù)所采用的數(shù)據(jù)結(jié)構(gòu)如下所示：表ParSwarm錄的是粒子的位置、速度與當(dāng)前的適應(yīng)度值，我們W來表示位置，用V來代表速度，用F來代表當(dāng)前的適應(yīng)度值。在這里我們假設(shè)粒子個數(shù)為，每個粒子的維數(shù)為D。

N

可編輯-------------精選文檔-----------------.

可編輯-------------精選文檔-----------------粒[可編輯-------------精選文檔-----------------')););');可編輯-------------精選文檔-----------------)可編輯-------------精選文檔-----------------:可編輯-------------精選文檔-----------------可編輯-------------精選文檔-----------------更可編輯-------------精選文檔-----------------更更更可編輯-------------精選文檔-----------------);更可編輯-------------精選文檔-----------------更可編輯-------------精選文檔-----------------可編輯-------------精選文檔-----------------:::：可編輯-------------精選文檔-----------------[可編輯-------------精選文檔-----------------可編輯-------------精選文檔-----------------2可編輯-------------精選文檔-----------------可編輯-------------精選文檔-----------------2可編輯-------------精選文檔-----------------'可編輯-------------精選文檔-----------------'''可編輯-------------精選文檔-----------------''這里給出一個使用的例子代碼，并分別解釋各參數(shù)的含義：可編輯-------------精選文檔-----------------,在上面的代碼中函數(shù)PsoProcess的20表粒子群的規(guī)模為20，10表每個粒子的維數(shù)為10，Scope粒子的每一維的范圍，同時也是速度的范圍，@initswarm是初始化函數(shù)的句柄，@BasestepPSO單步更新的函數(shù)句柄，@Griewank適應(yīng)度評價函數(shù)的句柄表真?zhèn)€算法循環(huán)終止，其他參數(shù)參見說明文檔。幾個適應(yīng)度評價函數(shù)下面給出幾個適應(yīng)度評價函數(shù)，并給出圖形表示第一個函數(shù)：Griewank函數(shù)，圖形如下所示：可編輯-------------精選文檔-----------------適應(yīng)度函數(shù)如下：（為了求最大值，我去了所有函數(shù)值的相反數(shù)）,可編輯-------------精選文檔-----------------繪制函數(shù)圖像的代碼如下：l第二個函數(shù)：Rastrigin數(shù)，圖形如下所示：可編輯-------------精選文檔-----------------適應(yīng)度函數(shù)如下：（為了求最大值，我去了所有函數(shù)值的相反數(shù)）,繪制函數(shù)圖像的代碼如下：可編輯-------------精選文檔-----------------l第三個函數(shù)Schaffer函數(shù)，圖形如下所示：可編輯-------------精選文檔-----------------函數(shù)的代碼如下為該函數(shù)有最大值此不需要取相反數(shù)。[c-sharp]functionresult=Schaffer(x1)%Schaffer函數(shù)%輸入給出相應(yīng)的,在x=(0,0,…,0)處有全局極大點1.%編制人：%編制日期：[row,col]=size(x1);ifrow>18.

error('輸入的參數(shù)錯誤');endx=x1(1,1);y=x1(1,2);temp=x^2+y^2;result=0.5-(sin(sqrt(temp))^2-0.5)/(1+0.001*temp)^2;繪制函數(shù)代碼圖形的代碼如下：[c-sharp]可編輯-------------精選文檔-----------------functionDrawSchaffer()x=[-5:0.05:5];y=x;[X,Y]=meshgrid(x,y);[row,col]=size(X);forl=1:colforh=1:rowz(h,l)=Schaffer([X(h,l),Y(h,l)]);endendsurf(X,Y,z);shadinginterp第四個函數(shù)：Ackley函數(shù)，函數(shù)圖形如下：函數(shù)的代碼如下，因為該函數(shù)在（0,...,0處有最小值0因此需要取相反數(shù)[c-sharp]1.functionresult=Ackley(x)可編輯-------------精選文檔-----------------%Ackley函數(shù)%輸入給出相應(yīng)的,在x=(0,0,…,0)處有全局極小點0,得到最大值，返回值取相反數(shù)4.%編制人：