粒子群算法優(yōu)化研究

　　[提要] 粒子群算法控制參數較少、使用簡單，受到很多專家學者的關注。但是，傳統粒子群算法在求解非線性規(guī)劃問題時，比較容易陷入局部最優(yōu)而找不到全局最優(yōu)解。本文在算法設計過程中，對傳統的粒子群算法進行改進，以提高求解效果。
　　關鍵詞：非線性規(guī)劃；粒子群算法；回收網絡
　　中圖分類號：F27 文獻標識碼：A
　　收錄日期：2017年11月28日

一、引言

　　粒子群算法（Particle Swarm Optimization，PSO）為常見優(yōu)化算法，是一種模擬鳥類覓食過程來尋求最優(yōu)解的算法，很多問題的優(yōu)化都可以使用，如核動力、車輛調度、巡回旅行等。因控制參數少、使用簡單、易實現，粒子群算法受到很多專家學者的關注。但是傳統粒子群算法在求解非線性規(guī)劃問題時，比較容易陷入局部最優(yōu)而找不到全局最優(yōu)解，本文在傳統的粒子群算法上進行了改進，以提高求解效果。

二、粒子群算法介紹

　　粒子群算法（PSO）是一種基于群體的隨機優(yōu)化方法。傳統的粒子群算法思路如下：
　　設S在維目標搜索空間中，有m個微粒組成一個群體，那么其中粒子i可以表示為一個S維的向量xi=（xi1，xi2，…，xis），i=1，2，…，m。同理，群體中的每個粒子都可以以同樣的方式表示，每個粒子的位置就是一個可行解。將其預先設定的目標函數來計算每一個粒子的適應值，并根據適應值大小來衡量粒子所在位置的優(yōu)劣程度。在搜索空間中第i個粒子的飛翔速度也是一個S維向量，記為V=（v1，v2，…，vs）。除了粒子的飛行位置和飛行速度以外，還需要記錄兩個重要的信息：第i個粒子迄今為止搜索到的最優(yōu)位置為PbestiS=（Pbesti1，Pbesti2，…，Pbesti3）；整個粒子群迄今為止搜索到的最優(yōu)位置為GbestS=（Gbest1，Gbest2，…，Gbest3）。設f（x）為目標函數，則微粒當前最好位置由下式確定：
　　p（t+1）=pi（t） 若f（xi（t+1））≥f（pi（t））xi（t+1） 若f（xi（t+1））≤f（pi（t））
　　在基礎上進行微粒飛行迭代為兩步操作：位置移動和速度變化，基本迭代公式分別為：
　　v（t+1）=v（t）+c1·（Gbest[]-present[]）+c2·（Pbest-p（t）） （1）
　　x（t+1）=x（t）+v（t+1） （2）
　　其中，學習因子c1、c2為非負常數，c1調節(jié)粒子飛向自身最好位置方向的步長，c2調節(jié)粒子飛向全局最好位置方向的步長。r1、r2為相互獨立的偽隨機數，服從[0，1]上的均勻分布。
　　經典的PSO算法步驟如下：
　　Step1：初始化一個規(guī)模為m的粒子群，并設定各個微粒的初始位置和速度。
　　Step2：設置適應度函數并計算每個微粒的適應值。
　　Step3：把每個微粒的適應值與其經歷過的最好位置時的適應值作比較，若當前微粒所在位置的適應值較好，則將其作為微粒當前的最好位置。
　　Step4：把每個微粒的適應值與整個粒子群經歷過的最好位置時的適應值作比較，若當前微粒所在位置的適應值較好，則將其作為當前的粒子群全局的最好位置。
　　Step5：根據方程（1）、（2）分別對粒子的速度和位置進行更新。
　　Step6：如果滿足終止條件，則輸出最優(yōu)解；否則返回Step2。

三、改進的粒子群算法設計

　　基本粒子群算法在求解非線性規(guī)劃問題時，比較容易陷入局部最優(yōu)而找不到全局最優(yōu)解，因此，本文在算法設計過程中，對傳統的粒子群算法進行了改進，以提高求解效果。改進的算法分別采用強引導型粒子群算法和自適應粒子群算法對原有位置、速度迭代公式進行優(yōu)化，對式（1）、（2）進行改進，使改進的位置迭代公式為：
　　x（t+1）=x（t）+（rand（）+k）·v（t）+10-6·rand（）
　　其中，rand（）為0～1之間的隨機數，k為調節(jié)系數，隨著迭代次數的增加，調節(jié)系數逐漸降低，可取k=kmax-·iter，其中iter表示迭代次數。速度更新采用自適應速度更新公式，在傳統的速度更新公式中隨迭代次數改變？棕，例如迭代100次，可�。�
　�。孔�=0.5 1≤gen≤400.1 40≤gen≤600.001 60≤gen≤100
　　速度更新公式可表示為：
　　v（）=？棕·v（）+c1·rand（）·（Gbest[]-present[]）+c2·rand（）（Pbest-present[]）
　　其中，學習因子c1和c2為常數，避免粒子陷入局部最優(yōu)并實現信息共享，以保證粒子的空間搜索能力，數值大小設置具體應視情況而定。
　�。ㄒ唬┝Ｗ拥木幋a形式。編碼過程是整個算法設計過程中的難點之一，高效的編碼方式能夠大大減輕模型運算的難度，提高模型求解效率，因此編碼的設計十分關鍵。再制造物流網絡中參數較多，編碼過程需要把每個變量進行合理編碼，以保證在交叉迭代過程中解得可行性，并保證迭代效率。主要的編碼設計思路為：分派過程中對粒子進行實數編碼，根據分派比例設定粒子的每一個分向量，如對I個回收點、J個倉儲點、K個分揀點的編碼可采用如下形式：
　　（x1，1…xi，j…xI，J"|y1，1…yj，k…yJ，K||z1，1…zk，s…zK，S||v1，1…vi，j…vI，J||u1，1…uj，k…uJ，K||w1，1…wk，s…wK，S）x代表從回收點到倉庫段粒子的位置，y代表從倉庫到分揀中心段粒子的位置，z代表從分揀中心到再制造中心段粒子的位置，v代表x的變化速度，u代表y的變化速度，w代表z的變化速度，分揀中心到再利用中心的費用另外計算。

相關熱詞搜索：粒子 算法 優(yōu)化 研究