粒子群算法介紹及深入

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

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

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

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

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

2

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

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

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

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

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

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

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

N

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

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

error('輸入的參數(shù)錯(cuò)誤');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第四個(gè)函數(shù)：Ackley函數(shù)，函數(shù)圖形如下：函數(shù)的代碼如下，因?yàn)樵摵瘮?shù)在（0,...,0處有最小值0因此需要取相反數(shù)[c-sharp]1.functionresult=Ackley(x)可編輯-------------精選文檔-----------------%Ackley函數(shù)%輸入給出相應(yīng)的,在x=(0,0,…,0)處有全局極小點(diǎn)0,得到最大值，返回值取相反數(shù)4.%編制人：