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

王 甫，鄭亞平，劉天琪

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

1 概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step 7評(píng)估目標(biāo)函數(shù)與全局最優(yōu)值。

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

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

Step 10結(jié)束。

3 算法對(duì)比實(shí)驗(yàn)

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

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

表1 測(cè)試函數(shù)

算法測(cè)試環(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 個(gè)不同函數(shù)的搜索區(qū)間均為［-100，100］。搜索區(qū)間也是PSO 粒子初始化的區(qū)間，首次循環(huán)開(kāi)始，粒子在上述對(duì)應(yīng)的區(qū)間內(nèi)隨機(jī)產(chǎn)生［10］。

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

3.2 測(cè)試結(jié)果

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

表2 3 種算法的搜索精度對(duì)比

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

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

重復(fù)實(shí)驗(yàn)50 次，得到3 種算法的達(dá)到可接受精度的平均時(shí)間，結(jié)果如表5 所示。因?yàn)镹CPSO-FLV引入速度限制和位置限制，進(jìn)化過(guò)程比較復(fù)雜，在前4 個(gè)函數(shù)的運(yùn)行時(shí)間比其他2 種算法長(zhǎng)，在第5 個(gè)函數(shù)上的運(yùn)行時(shí)間最短，也說(shuō)明了NCPSO-FLV 具有對(duì)三角函數(shù)的良好搜索能力。

表3 3 種算法達(dá)到可接受精度的進(jìn)化代數(shù)對(duì)比

表4 3 種算法的成功概率對(duì)比

表5 3 種算法的運(yùn)行時(shí)間對(duì)比

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

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

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

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

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

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

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

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

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

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

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

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

3.3 實(shí)例計(jì)算

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

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

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

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

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

限制條件如下:

標(biāo)準(zhǔn)結(jié)果為:

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

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

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

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

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

圖6 收斂曲線比較

4 結(jié)束語(yǔ)

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

［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］陳國(guó)強(qiáng)，王宇平.采用離散粒子群算法的復(fù)雜網(wǎng)絡(luò)重疊社團(tuán)檢測(cè)［J］.西安交通大學(xué)學(xué)報(bào)，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］史哲文，白雪石，郭 禾.基于改進(jìn)小生境粒子群算法的多模函數(shù)優(yōu)化［J］.計(jì)算機(jī)應(yīng)用研究，2012，29(3):465-468.

［5］宮艷雪，黃 道，孫少超.基于Mamdani 模糊推理系統(tǒng)的制造/再制造混合系統(tǒng)的最優(yōu)定價(jià)［J］.華東理工大學(xué)學(xué)報(bào)，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］韓錦東，李英俊，陳志祥.帶能力約束的多目標(biāo)OEM協(xié)作生產(chǎn)訂單分配決策與混合蟻群算法應(yīng)用研究［J］.中國(guó)機(jī)械工程，2012，23(22):2714-2719.

［8］賈東立，張家樹(shù).基于混沌變異的小生境粒子群算法［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］謝 康，肖靜華，周先波，等.中國(guó)工業(yè)化與信息化融合質(zhì)量:理論與實(shí)證［J］.經(jīng)濟(jì)研究，2012，(1):1-16.

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