一種基于調(diào)節(jié)因子的小生境粒子群優(yōu)化算法

王 甫，鄭亞平，劉天琪

(1.綿陽師范學院數(shù)學與計算機科學學院，四川 綿陽 621000;2.四川大學電氣信息學院，成都 610065)

1 概述

通過模擬鳥群社會行為，根據(jù)群智能的演化計算技術(shù)，粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法于1995 年被提出［1］。算法中參數(shù)少、程序編制容易、具有較快的收斂速度是PSO 的明顯優(yōu)勢，在工程中的各領域得到了廣泛應用。

基于差分方程，PSO 算法的穩(wěn)定性和收斂性已經(jīng)得到初步結(jié)論，即基本的PSO 算法不能收斂到全局最優(yōu)值［2］。對于目前流行的PSO 算法，參數(shù)選擇或動態(tài)修改某個參數(shù)是改進的基本方向，但是依靠調(diào)節(jié)慣性權(quán)重和加速因子，目前仍然不能有效解決PSO 易陷入局部最優(yōu)的問題。種群后期進化中的趨同性，是陷入局部最優(yōu)的根本原因。如果利用多種群協(xié)同進化，加強全局收斂，就可以避免早熟。

混沌變異的小生境粒子群優(yōu)化算法(Niche Chaotic Mutation PSO，NCPSO)于2002 年被提出，其中圓形小生境粒子種群在進化過程中得以實現(xiàn)，低維函數(shù)測試搜索精度較高［3］，協(xié)同策略實現(xiàn)較為復雜，但是利用小生境容易實現(xiàn)，可以使得小范圍的粒子相互獨立，形成孤立的動態(tài)搜索空間。粒子小范圍有效地分布，各個粒子在自己搜索范圍內(nèi)尋找極值點，可以有效防止大規(guī)模的種群趨同現(xiàn)象。通過建立淘汰更新機制，淘汰最劣粒子，保證整個種群向全局最優(yōu)值運動。

此后，NCPSO 得到了廣泛的應用。2010 年，一種基于NCPSO 的圖像分割方法被提出。該方法利用NCPSO，通過建立小生境，保持了粒子的多樣性，一定程度上使得PSO 容易陷入局部問題得到解決［4］。通過最大類別間的方差閾值分割技術(shù)，NCPSO 得到分割圖像的最佳閾值。這種基于混沌粒子群算法(Chaos PSO，CPSO)的新方法與基于PSO 的最大類別間的方差分割法進行相比，結(jié)果證明新方法可以對圖像進行快速精確地分割。文獻［5］提出了一種新的小生境粒子群算法(MNCPSO)。基于Mamdani 利潤模型，產(chǎn)品價格與顧客需求量滿足經(jīng)濟學中線性需求關(guān)系。為了求解優(yōu)化模型的參數(shù)，MNCPSO 用混沌算法變換進行初始化，基于歐氏距離公式和閾值保持粒子的多樣性，進一步擴大了粒子搜索范圍。

盡管目前NCPSO 和相應的改進算法已經(jīng)取得了不錯的效果，但是NCPSO 和部分改進PSO 對高維函數(shù)搜索精度偏低、種群收斂速度后期較慢。本文針對上述缺點，提出一種改進的NCPSO 算法(NCPSO-FLV)。在算法中增加速度和位置調(diào)節(jié)因子，從而在后期的進化中，針對早熟的粒子加大隨機性，提高后期的收斂速度和算法的搜索精度。

2 帶有調(diào)節(jié)因子的小生境粒子群優(yōu)化算法

2.1 基本粒子群優(yōu)化算法

基本PSO 算法利用如下公式來通過速度和位置更新粒子狀態(tài):

其中，pi，j表示局部最優(yōu)值;pg表示全局最優(yōu)值;C1和C2代表學習因子;ω 代表慣性權(quán)重。

2.2 小生境粒子群優(yōu)化算法

NCPSO 基本思想是不同粒子之間不進行信息交互獨立進化，使得粒子處于分離孤立的小環(huán)境中，算法中孤立環(huán)境內(nèi)粒子減小了趨同性［6］。如果某一個微粒適應函數(shù)值在連續(xù)迭代的過程基本不變，以這個粒子為中心，和離它最近微粒的距離作為半徑，形成圓形區(qū)域的小生境，如果粒子進入圓形區(qū)域會被吸收，并且合并成新的小生境。

算法中的小生境可以用如下公式描述:

如果粒子滿足如下公式，將采取不同的操作:

滿足式(4 -1)，小生境粒子吸收粒子;滿足式(4 -2)，合并小生境相交。粒子的速度更新公式如下:

2.3 調(diào)節(jié)因子

調(diào)節(jié)因子主要在進化后期過程中被使用，其主要功能是:(1)阻止小生境中的部分粒子陷入早熟;(2)調(diào)節(jié)后期進化的收斂速度。調(diào)節(jié)因子分為位置調(diào)節(jié)和速度調(diào)節(jié)因子2 類。如果檢測到種群在給定循環(huán)次數(shù)內(nèi)沒有位置改變時，位置調(diào)節(jié)因子認為粒子陷入局部最優(yōu)，當前粒子全局搜索能力最差，算法利用全局最優(yōu)值位置，更改種群中其他粒子的位置，增強了搜索能力，公式即為:

其中，xd和vd分別為粒子第d 維的位置和速度;ud和ld分別為粒子第d 維空間的最大最小值。

被調(diào)節(jié)粒子位置后，如果在規(guī)定的循環(huán)次數(shù)內(nèi)最優(yōu)位置仍沒得到更新，再次以當前最佳位置作為參考，增強粒子的多樣性。

為保證收斂性，粒子速度變化的情況必須被同時評估，又引入了速度更新因子，如果粒子速度在迭代過程中越來越慢，則種群趨向成熟，根據(jù)當前粒子中最快速度，可以使其他粒子加快運動。

引入速度因子的目的是:當粒子當前位置與最優(yōu)位置之間存在較大差距，更新后期粒子運動速度會變慢，趨向成熟收斂［7］。同時過慢的速度導致粒子難以收斂。速度因子可以作為位置因子的補充，保證一定的收斂速度，使粒子速度更新之后保證收斂。

NCPSO-FLV 算法的具體步驟如下:

Step 1給定初始化空間，產(chǎn)生隨機粒子和速度。

Step 2根據(jù)目標函數(shù)和所有產(chǎn)生粒子，計算目標函數(shù)取值。

Step 3計算全局最優(yōu)值。

Step 4根據(jù)式(5 -1)和式(5 -2)更新種群中所有粒子的位置和速度。

Step 5評估粒子的當前位置和上次迭代位置的變化，根據(jù)閾值，利用式(6)更新所有粒子的位置。

Step 6評估粒子的當前速度和上次迭代速度的變化，根據(jù)閾值，利用式(7)更新當前粒子的速度。

Step 7評估目標函數(shù)與全局最優(yōu)值。

Step 8如果目標函數(shù)值較大，不改變?nèi)肿顑?yōu)值;如果全局最優(yōu)值較大，用目標函數(shù)值替換全局最優(yōu)值。

Step 9判斷是否滿足最大進化代數(shù)，不滿足轉(zhuǎn)Step4;滿足轉(zhuǎn)Step10。

Step 10結(jié)束。

3 算法對比實驗

3.1 測試函數(shù)和環(huán)境

根據(jù)文獻［6］選擇測試函數(shù)。表1 中是從Benckmark 測試集中所選擇的不同測試函數(shù)［8-9］，可以綜合評價算法的性能。通過評估，可以評價算法精度和對陷入局部最優(yōu)問題的處理能力。

表1 測試函數(shù)

算法測試環(huán)境為:硬件系統(tǒng):CPU 為Core I 7 3630QM的CPU，內(nèi)存為8 GB DDR 3;軟件系統(tǒng):操作系統(tǒng)為Win7 32 bit，使用Matlab R2010。

5 個不同函數(shù)的搜索區(qū)間均為［-100，100］。搜索區(qū)間也是PSO 粒子初始化的區(qū)間，首次循環(huán)開始，粒子在上述對應的區(qū)間內(nèi)隨機產(chǎn)生［10］。

利用小生境保持多樣性，保證粒子不會陷入早熟，比較小生境粒子群和評估收斂速度和搜索精度。

3.2 測試結(jié)果

對上述3 種算法重復運行30 次，設定最大循環(huán)為10 000 次，對每個算法運行結(jié)果求出平均值，得到最后的精度比較。由表2 可見，NCPSO-FLV 的最終搜素精度較高，尤其是在第5 個帶有三角函數(shù)的測試函數(shù)上，均比其他2 種算法的搜索精度高。

表2 3 種算法的搜索精度對比

根據(jù)設定的可接受精度，進行50 次實驗，選取各個算法能夠達到可接受精度的最小進化代數(shù)進行對比，結(jié)果如表3 所示。可以看出，NCPSO-FLV 所需要的進化代數(shù)最小，PSO-ω 在第5 個測試函數(shù)上在10 000 次進化后，達不到接受精度。

根據(jù)可接受精度和達到可接受精度的平均循環(huán)次數(shù)，連續(xù)運行3 種算法50 次，利用其中達到可接受精度的次數(shù)與總循環(huán)次數(shù)之比為成功概率，從表4可以看出，NCPSO-FLV 的成功概率較高，第一個函數(shù)為100%，最后一個函數(shù)和NCPSO 成功概率相同。

重復實驗50 次，得到3 種算法的達到可接受精度的平均時間，結(jié)果如表5 所示。因為NCPSO-FLV引入速度限制和位置限制，進化過程比較復雜，在前4 個函數(shù)的運行時間比其他2 種算法長，在第5 個函數(shù)上的運行時間最短，也說明了NCPSO-FLV 具有對三角函數(shù)的良好搜索能力。

表3 3 種算法達到可接受精度的進化代數(shù)對比

表4 3 種算法的成功概率對比

表5 3 種算法的運行時間對比

3 種算法針對5 個測試函數(shù)的收斂曲線比較如圖1～圖5 所示。

圖1 測試函數(shù)F1的收斂曲線

圖2 測試函數(shù)F2的收斂曲線

圖3 測試函數(shù)F3的收斂曲線

圖4 測試函數(shù)F4的收斂曲線

圖5 測試函數(shù)F5的收斂曲線

由圖1～圖3 可知，NCPSO-FLV 算法加入速度調(diào)節(jié)因子之后收斂速度加快，精度提高。對函數(shù)F1和F3收斂較快，對于較難最小化的函數(shù)F2，NCPSOFLV 算法后期容易陷入局部最優(yōu)值，但是精度比小生境粒子群算法提高很多。由圖4 和圖5 可知，對于F4函數(shù)，NCPSO-FLV 算法后期收斂速度較慢，但是仍然取得了較好的精度。對于F5，NCPSO-FLV 算法精度較高，而且比小生境粒子群算法的振蕩減小很多。

根據(jù)以上測試結(jié)果，可以得出以下結(jié)論:

(1)調(diào)節(jié)因子小生境粒子群算法比小生境粒子群算法的精度高，從5 個測試函數(shù)來看，調(diào)節(jié)因子小生境粒子群算法最高能夠達到1e -100 數(shù)量級的精度，遠高于小生境粒子群算法。

(2)調(diào)節(jié)因子小生境粒子群算法在絕大多數(shù)測試函數(shù)上的后期收斂性能較好。

(3)以算法達到可接受搜索精度作為標準時，調(diào)節(jié)因子的粒子群算法具有更快的速度。

(4)針對一個固定的搜索精度而言，調(diào)節(jié)因子的粒子群算法魯棒性較好。

3.3 實例計算

最優(yōu)化技術(shù)致力于如何解決工程模型，把最優(yōu)化問題表示為數(shù)學模型和如何求最優(yōu)解。在全球經(jīng)濟一體化的進程中，企業(yè)參與全球化生產(chǎn)網(wǎng)絡與其他企業(yè)建立合作關(guān)系分工合作地進行生產(chǎn)與貿(mào)易實現(xiàn)互利共贏是經(jīng)濟發(fā)展的趨勢［11］，在大量零組件需要外部協(xié)作實現(xiàn)這種協(xié)作性生產(chǎn)的生產(chǎn)模式中，品牌企業(yè)如何合理分配訂單給不同的代工企業(yè)供應商進行生產(chǎn)，即生產(chǎn)任務分配問題就成為這種生產(chǎn)方式的主要決策。在此類任務分配問題中，一方面每個訂單的交貨期和售價各不相同，另一方面承擔這些訂單的供應商及其加工成本及加工時間也是各不相同的。針對這些情況，為找到一個最優(yōu)的訂單分配方案就需要考慮成本收益服務水平等目標因素，以最終達到整體的訂單效益最大化［12］。

對于企業(yè)而言，使得訂單效益最大化，就是如何優(yōu)化生產(chǎn)任務分配問題，其中最重要的環(huán)節(jié)之一就是如何分配工作單位。工作單位分配，也就是將總?cè)蝿辗峙浣o若干單位，由于各個單位的生產(chǎn)能力和成本不一樣，實際上存在一個最有分配的優(yōu)化問題。

重慶一汽車零件廠共有5 個車間，每個車間的生產(chǎn)能力、單位產(chǎn)品成本、庫存原材料總量、單位產(chǎn)品消耗中的原材料如表6 所示。

優(yōu)化的目標函數(shù)自然是成本函數(shù)。

其中，xi為各個車間產(chǎn)品分配量。

限制條件如下:

標準結(jié)果為:

利用NCPSO 的計算結(jié)果為:

用NCPSO-FLV 的計算結(jié)果為:

可以看出，調(diào)節(jié)因子的小生境粒子群算法的計算結(jié)果更精確。

表6 零件廠生產(chǎn)資料信息

3 種算法針對實例的收斂曲線如圖6 所示，同樣可以看出，NCPSO-FLV 算法的收斂精度最高。

圖6 收斂曲線比較

4 結(jié)束語

本文提出了一種加入調(diào)節(jié)因子的小生境粒子群算法，利用小生境種群多樣性的概念，在搜索過程中，根據(jù)調(diào)節(jié)因子對粒子速度和位置的不斷調(diào)整，加強了各個粒子的社會性和粒子的多樣性，提高了粒子群的收斂速度和搜索進度。但該算法在個別測試函數(shù)上后期收斂速度不是很理想，對其進行改進是下一步的研究方向。

［1］Kennedy J，Eberhart R C.Particle Swarm Optimization［C］//Proc.of IEEE International Conference on Neural Network.Perth，Australia:IEEE Press，1995:1942-1948.

［2］陳國強，王宇平.采用離散粒子群算法的復雜網(wǎng)絡重疊社團檢測［J］.西安交通大學學報，2013，47(1):107-113.

［3］Brits R，Engelbrchta P，Bergh F D.A Niching Particle Swarm Optimizer［C］//Proc.of IEEE Conference on Simulated Evolutionary and Learning.Singapore:IEEE Press，2002:1037-1040.

［4］史哲文，白雪石，郭 禾.基于改進小生境粒子群算法的多模函數(shù)優(yōu)化［J］.計算機應用研究，2012，29(3):465-468.

［5］宮艷雪，黃 道，孫少超.基于Mamdani 模糊推理系統(tǒng)的制造/再制造混合系統(tǒng)的最優(yōu)定價［J］.華東理工大學學報，2011，37(6):759-764.

［6］Li Changhe，Yang Shengxiang，Nguyen T T.A Self-Learning Particle Swarm Optimizer for Global Search［J］.IEEE Transactions on System Man and Cybernetics:Part B，2012，42(3):627-645.

［7］韓錦東，李英俊，陳志祥.帶能力約束的多目標OEM協(xié)作生產(chǎn)訂單分配決策與混合蟻群算法應用研究［J］.中國機械工程，2012，23(22):2714-2719.

［8］賈東立，張家樹.基于混沌變異的小生境粒子群算法［J］.控制與與決策，2007，22(1):117-120.

［9］Yao Xin，Liu Yong，Lin Guangming.Evolutionary Programming Made Faster［J］.IEEE Transactions on Evolutionary Computation，2004，3(2):82-102.

［10］Clerc M，Kennedy J.The Particle Swarm-Explosion，Stability，and Convergence in a Multidimensional Complex Space ［J］.IEEE Transactions on Evolutionary Computation，2002，6(1):58-73.

［11］謝 康，肖靜華，周先波，等.中國工業(yè)化與信息化融合質(zhì)量:理論與實證［J］.經(jīng)濟研究，2012，(1):1-16.

［12］王永瑜，郭立平.綠色GDP 核算理論與方法研究［J］.統(tǒng)計研究，2010，27(11):77-84.