張永強(qiáng)，徐　宗昌，呼凱凱，胡春陽(yáng)

（1.裝甲兵工程學(xué)院技術(shù)保障工程系，北京 100072；2.海軍航空兵學(xué)院，遼寧　葫蘆島 125000）

基于私有云和改進(jìn)粒子群算法的約束優(yōu)化求解

張永強(qiáng)1，2，徐宗昌1，呼凱凱1，胡春陽(yáng)1

（1.裝甲兵工程學(xué)院技術(shù)保障工程系，北京 100072；2.海軍航空兵學(xué)院，遼寧葫蘆島 125000）

為提高約束優(yōu)化模型的求解準(zhǔn)確度和運(yùn)算速度，針對(duì)粒子群算法及其計(jì)算方法進(jìn)行了改進(jìn)。引入多樣化機(jī)制避免算法陷入局部最優(yōu)的危險(xiǎn)：創(chuàng)建多個(gè)子群將決策空間劃分為多個(gè)搜索子空間，多子群獨(dú)立搜索以保證群間解的多樣化；用量子粒子代替普通粒子，為其添加服從球狀分布的伴隨粒子來(lái)提高群內(nèi)解的多樣化。多樣化的引入增加了計(jì)算量和計(jì)算復(fù)雜度，利用并行計(jì)算提高算法運(yùn)行速度：分析了改進(jìn)粒子群算法并行計(jì)算的方法，在私有云計(jì)算平臺(tái)上編寫(xiě)了基于Map Reduce的并行求解流程。實(shí)驗(yàn)結(jié)果表明，本文方法具有較高準(zhǔn)確度，算法的穩(wěn)定性也較好，運(yùn)算速度可成倍提高。

約束優(yōu)化；粒子群算法；私有云計(jì)算平臺(tái)；并行求解；多樣化

網(wǎng)址：www.sys-ele.com

0　引　言

在實(shí)際工程中，許多問(wèn)題都可用式（1）所示的約束優(yōu)化模型描述［1］：

式中，X 為決策向量，且滿足k≤xi≤l，i=1，2，…，n，其中k和l為常數(shù)；f（X）、g（X）與h（X）均為空間Rn上的n元函數(shù)，且f（X）為目標(biāo)函數(shù)，g（X）為不等式約束函數(shù)，h（X）為等式約束函數(shù)；模型共包含s個(gè)等式約束函數(shù)和s′-s個(gè)不等式約束函數(shù)。

模型的求解要求在滿足函數(shù)約束與變量邊界的前提下，通過(guò)優(yōu)化目標(biāo)函數(shù)來(lái)確定出問(wèn)題的決策變量值。然而，約束優(yōu)化模型的數(shù)學(xué)特征使得模型的求解非常困難。約束優(yōu)化模型中的變量可以是離散值或連續(xù)值，約束條件可以是等式也可以是不等式，目標(biāo)函數(shù)與約束函數(shù)可能是線性或非線性的，解變量空間可能是單峰或多峰的，搜索空間的可行域可能是單個(gè)連通區(qū)域也可能是多個(gè)非連通區(qū)域，模型的最優(yōu)解可能在可行域的邊緣也可能在可行域的內(nèi)部，另外變量多而導(dǎo)致的高維問(wèn)題也增加了求解的復(fù)雜度與計(jì)算量［2］。

當(dāng)前，通用的求解約束優(yōu)化問(wèn)題的方法由兩部分組成：優(yōu)化算法與約束處理技術(shù)?？蛇x的優(yōu)化算法有粒子群優(yōu)化（particle swarm optimization，PSO）算法、遺傳算法、模擬退火算法等；而常用的約束處理技術(shù)有懲罰函數(shù)法與多目標(biāo)法等［3］。本文的目標(biāo)是研究如何改進(jìn)PSO以提高解的準(zhǔn)確度，為了研究方便，對(duì)于約束處理技術(shù)采用了一種傳統(tǒng)的懲罰函數(shù)法。

PSO是由Kennedy博士等提出的一種智能優(yōu)化算法［4］。PSO算法的計(jì)算參數(shù)少、收斂速度快、易于編程實(shí)現(xiàn)，是解決約束優(yōu)化問(wèn)題的常用算法。然而PSO同時(shí)也存在求解的準(zhǔn)確度不高、易陷入局部最優(yōu)化的危險(xiǎn)，因此在應(yīng)用時(shí)需要進(jìn)行改進(jìn)，這也是本文的主要工作。

本文章節(jié)安排如下：第1章介紹了PSO算法如何求解約束優(yōu)化模型，并針對(duì)約束優(yōu)化問(wèn)題列舉了當(dāng)前常見(jiàn)的幾種改進(jìn)PSO算法；第2章從多樣化與擴(kuò)展搜索空間兩方面對(duì)PSO算法進(jìn)行了改進(jìn)；第3章針對(duì)改進(jìn)PSO計(jì)算量大的問(wèn)題，在私有云的基礎(chǔ)上設(shè)計(jì)了并行處理PSO的流程，以提高處理速度；第4章通過(guò)一系列試驗(yàn)對(duì)改進(jìn)PSO的性能進(jìn)行了比較驗(yàn)證。

1　PSO及常見(jiàn)改進(jìn)算法

1.1PSO算法求解約束優(yōu)化

經(jīng)典的PSO算法是一種模擬鳥(niǎo)群覓食行為的基于群體的隨機(jī)優(yōu)化技術(shù)。在式（1）中，X的取值并不是Rn中的任意向量，而是在一定范圍內(nèi)變化，這個(gè)范圍被稱為決策空間Sn。決策空間Sn又依照是否滿足約束條件被劃分為可行域和不可行域只有在可行域中的向量才滿足約束條件，PSO算法就是在Sn中按約束處理規(guī)則遍歷，經(jīng)過(guò)一定的迭代次數(shù)后算法將在某一可行域收斂，將收斂后算法標(biāo)記的全局最優(yōu)解即作為式（1）的解。X、、Sn和Rn的關(guān)系可以用式（2）表示為

為保證盡可能地逼近全局最優(yōu)解，PSO算法從任務(wù)的開(kāi)始起將多個(gè)粒子散落到?jīng)Q策空間Sn中，并以個(gè)體粒子歷史最優(yōu)解和全體粒子群歷史最優(yōu)解做為粒子更新的主要參數(shù)。在決策空間Sn中，分布著由N個(gè)粒子組成的粒子群，任意一個(gè)粒子的位置和速度分別用向量Xi=（xi1，xi2，…，xin）和向量Vi=（υi1，υi2，…，υin）表示，并用向量Pi=（pi1，pi2，…，pin）表示該粒子的歷史最優(yōu)解，而整個(gè)粒子群的歷史最優(yōu)解用向量Pg=（pg1，pg2，…，pgn）表示。算法初始階段隨機(jī)產(chǎn)生一個(gè)粒子群，在下一個(gè)時(shí)刻，粒子的位置和速度依據(jù)式（3）和式（4）移動(dòng)：

其中，Ai=（ai1，ai2，…，ain）為粒子移動(dòng)的加速度，其計(jì)算公式為

式中，R1和R2為n×n維的矩陣，其元素服從U［0，1］；c＞2為跳變常數(shù)；Χ為粒子移動(dòng)的收縮參數(shù)。

1.2常見(jiàn)的面向約束優(yōu)化求解的改進(jìn)PSO算法

經(jīng)典PSO算法在處理約束優(yōu)化方面存在收斂過(guò)快、易陷入局部最優(yōu)［2］。針對(duì)這一問(wèn)題，國(guó)內(nèi)外學(xué)者做了大量改進(jìn)。近年來(lái)，基于PSO求解約束優(yōu)化問(wèn)題改進(jìn)算法主要有：

文獻(xiàn)［5］提出了一種被稱為混沌PSO（chaos PSO，CPSO）的改進(jìn)算法，該算法中每個(gè)粒子都按照適應(yīng)度函數(shù)進(jìn)化，也即選擇向最接近可行域的方向運(yùn)動(dòng)。為了確定不可行度，CPSO實(shí)時(shí)比較并保存違反各約束條件最大的那個(gè)粒子。

文獻(xiàn)［6］還提出了一種HPSO（hybrid PSO），目的是為了保持解的多樣化。HPSO利用多種方法更新粒子信息，并在雙種群的基礎(chǔ)上使用了粒子重組機(jī)制。但測(cè)試結(jié)果表明該方法只對(duì)某些約束優(yōu)化問(wèn)題有效。

文獻(xiàn)［7］為了避免解的局部性，結(jié)合約束處理機(jī)制提出了一種動(dòng)態(tài)多子群PSO算法。根據(jù)違反約束條件的程度，各子群分別針對(duì)不同的約束條件搜索。該算法的局部搜索采用了序貫二次規(guī)劃法（sequential quadratic programming，SQP），且SQP的性能會(huì)直接影響到約束優(yōu)化問(wèn)題的解。

文獻(xiàn)［8］針對(duì)線性等式約束優(yōu)化問(wèn)題提出了LPSO（linear PSO）算法。LPSO將式（5）中的R1與R2替換為服從均勻分布的隨機(jī)變量e1與e2，即粒子運(yùn)動(dòng)的加速度變?yōu)锳i=Χ［ce1·（Pg-Xi）+ce2·（Pi-Xi）］-（1-Χ）·Vi。這一變動(dòng)使得算法在可行域中的搜索性能大大提高，然而LPSO因收斂過(guò)快易導(dǎo)致求出局部最優(yōu)解。為解決這一問(wèn)題，作者又在LPSO的基礎(chǔ)上提出了CLPSO（converging LPSO）算法［8］，通過(guò)改變Pg的選擇機(jī)制與粒子向Pg運(yùn)動(dòng)的速度來(lái)緩解上述問(wèn)題。實(shí)驗(yàn)顯示CLPSO的解要遠(yuǎn)優(yōu)于LPSO。另外，文獻(xiàn)［9］也在LPSO的基礎(chǔ)上提出了MLPSO（mutation linear PSO），通過(guò)引入變異操作更新了粒子更新的速度，在一定程度上也改善了LPSO存在的問(wèn)題。

Co-CLPSO（cooperation comprehensive learning PSO）也被用于求解約束優(yōu)化問(wèn)題［10］。該方法中，兩個(gè)子群相互合作。每個(gè)子群中的粒子按一定的適應(yīng)性規(guī)則探索不同的區(qū)域。兩個(gè)子群定期交換信息，最后通過(guò)綜合兩個(gè)子群獲得問(wèn)題的最優(yōu)解。

當(dāng)搜索空間由多個(gè)不連通的可行域組成時(shí)，如何定位這些可行域、以及如何快速找到最優(yōu)解所在的可行域是PSO算法的主要改進(jìn)目標(biāo)。文獻(xiàn)［3］提出了一種EAPSO（epsilon adaptive mutation linear PSO）算法，按一定運(yùn)動(dòng)規(guī)則使得粒子始終保持一定的拓?fù)湫螒B(tài)，這樣可使算法在初期搜索到盡可能多的可行域、并在后期使得大部分粒子位于最可能出現(xiàn)優(yōu)化解的可行域。在EAPSO的基礎(chǔ)上，通過(guò)改善算法的局部搜索能力，在文獻(xiàn)［11］中又提出了一種EAPSO-MG（EAPSO-modified gradient）的算法。

為了擴(kuò)展PSO算法處理約束優(yōu)化問(wèn)題的范圍，文獻(xiàn)［2］提出了一種SAM-PSO（self-adaptive PSO）。該算法針對(duì)PSO的搜索空間存在多峰值的問(wèn)題，在進(jìn)化過(guò)程中根據(jù)各峰值的優(yōu)劣來(lái)決定下次進(jìn)化時(shí)該峰值附近的粒子數(shù)量。當(dāng)然還存在其他的改進(jìn)算法，這里不再一一列舉。

2　改進(jìn)的粒子群算法

經(jīng)典PSO算法的一個(gè)優(yōu)勢(shì)是收斂速度快，然而也正因此，算法易陷入局部最優(yōu)。受文獻(xiàn)［6-7］與文獻(xiàn)［12］啟發(fā)，本文針對(duì)這一問(wèn)題提出了一個(gè)由多子群劃分、量子粒子和伴隨粒子3部分組成的改進(jìn)措施，目的是通過(guò)保持解的多樣化來(lái)避免算法陷入局部最優(yōu)解的危險(xiǎn)。其中多子群劃分保證了群間多樣化，而量子粒子和伴隨粒子則保證了群內(nèi)多樣化。

2.1多子群劃分與運(yùn)行

粒子的任務(wù)是檢測(cè)峰值，同一個(gè)群中的粒子最終會(huì)收斂至相同的局部最優(yōu)。因此，為了檢測(cè)出新的峰值，最簡(jiǎn)便的方法是讓粒子分屬多個(gè)子群。多子群的搜索對(duì)計(jì)算速度有較高的要求，而且由于將粒子劃歸于各子群，單個(gè)子群內(nèi)的粒子數(shù)會(huì)變少，從而導(dǎo)致收斂速度減緩。

考慮將決策空間Sn劃為d個(gè)子空間，使得

對(duì)于Sn中的任一向量Xi=（xi1，xi2，…，xin），假設(shè)最后一個(gè)變量xin的取值范圍滿足k≤xin≤l，其中k和l為常數(shù)，且有Δ=（l-k）/d≥1。令xi1至xin-1的取值范圍保持不變，將變量xin的取值范圍按d份平均劃分為k≤xin≤k+Δ，k+Δ≤xin≤k+2Δ，…，k+（d-1）Δ≤xin≤l，則可得到d個(gè)不相交的子決策空間，且滿足關(guān)系式（6）。

在算法運(yùn)算中，各個(gè)子決策空間Sin內(nèi)單獨(dú)運(yùn)行PSO算法，各粒子只記錄Sin內(nèi)搜索到的個(gè)體最優(yōu)解Pii和子群內(nèi)最優(yōu)解Pgi。經(jīng)過(guò)一段時(shí)間后，比較d個(gè)子群最優(yōu)解，將其中最差的一個(gè)子群移除，而將該子群內(nèi)的粒子標(biāo)記為自由粒子，并向子群最優(yōu)解中的最好子群遷移。這樣經(jīng)過(guò)多次迭代后，將只剩下一個(gè)決策子空間，且所有的粒子都位于該子空間內(nèi)或其周圍搜索，并最終收斂。

2.2量子粒子

使普通粒子具有量子的行為特性是實(shí)現(xiàn)解的多樣化的重要手段。利用量子的疊加態(tài)和概率特性，可使單個(gè)粒子按一定的概率表達(dá)出多個(gè)狀態(tài)，從而增加了粒子群的多樣性。文獻(xiàn)［13］給出了量子粒子的表達(dá)方式為

xα和xβ分別為普通粒子變量x 對(duì)應(yīng)量子態(tài)|0〉和|1〉的概率幅，有|x〉=α|0〉+β|1〉，其中α和β是一對(duì)復(fù)數(shù)，滿足關(guān)系式|α|2+|β|2=1。按此變量定義而成的量子粒子向量X在決策空間Sn中可映射到兩個(gè)位置，即對(duì)應(yīng)于量子態(tài)|0〉和|1〉的概率幅為：

由于每個(gè)量子粒子對(duì)應(yīng)于Sn中的兩個(gè)解，因此能夠擴(kuò)展算法解的多樣性，使得找到最優(yōu)解的幾率加大。

2.3量子粒子的伴隨粒子

粒子在從初始位置收斂至最優(yōu)解的路徑上，并不會(huì)考慮粒子的周邊情況。如果增加群內(nèi)量子粒子的數(shù)量，則會(huì)大大增加算法的計(jì)算量。為了在計(jì)算量少增加的情況下成倍擴(kuò)展搜索空間，一種可行的辦法是增加粒子的視野。文獻(xiàn)［14］提出了一種模擬物理學(xué)中量子原子運(yùn)動(dòng)形態(tài)的思路。一個(gè)量子原子是由一個(gè)原子核和一定數(shù)量的電子組成，量子原子中的電子沒(méi)有既定軌道，而是以一定的概率分布于量子原子核周圍。

運(yùn)用這一思路，本文將量子粒子作為量子原子核，并生成服從球狀分布的伴隨粒子作為量子電子。令量子粒子按正常的規(guī)則運(yùn)動(dòng)并最終收斂，而其周圍的伴隨粒子并不收斂，而僅僅參與單個(gè)粒子Pi值和子群Pg值的評(píng)比。與經(jīng)典PSO算法相較，由于伴隨粒子不執(zhí)行更新策略，算法的計(jì)算量增幅要比增加粒子數(shù)量小，而搜索空間卻能成倍增加。量子粒子的服從球狀分布的伴隨粒子生成步驟為：

步驟1生成一個(gè)服從標(biāo)準(zhǔn)正態(tài)分布的n維隨機(jī)向量Y，使得Y=（y1，y2，…，yn）～N（0，Σ），其中0為n維零向量，Σ為對(duì)角線元素等于1的正定矩陣；

步驟2計(jì)算向量Y與量子原子核X之間的距離dist，公式為

步驟5重復(fù)上面的步驟1～步驟4，便可得到圍繞某一粒子的一組球狀伴隨粒子，算法結(jié)束。

上述的步驟1中，生成隨機(jī)向量Y的方法是通過(guò)降維來(lái)處理的。Y的概率密度為

式中，N（ci）為一維標(biāo)準(zhǔn)正態(tài)分布函數(shù)，且有

式中，Λ=diag（λ1，λ2，…，λn），且λi＞0是Σ的特征值；Q是n階正交矩陣，滿足QTΣQ=Λ。

圖1以二維空間為例示出了以原點(diǎn)為中心、以半徑r= 1的伴隨粒子群。

圖1　服從球狀分布的伴隨粒子群示意圖

3　基于私有云的子群并行優(yōu)化

3.1并行優(yōu)化性能分析

假設(shè)有p個(gè)量子粒子，每個(gè)量子粒子的伴隨粒子個(gè)數(shù)為q個(gè)，則串行工作模式下的改進(jìn)PSO算法的執(zhí)行時(shí)間為

式中，Tq為量子粒子產(chǎn)生伴隨粒子的時(shí)間及其迭代計(jì)算時(shí)間；TI為單個(gè)伴隨粒子的進(jìn)化計(jì)算時(shí)間。根據(jù)伴隨粒子的工作機(jī)制，有TI≈Tq，因此改進(jìn)PSO算法中單個(gè)粒子的執(zhí)行時(shí)間是普通粒子的q+1倍，計(jì)算量大大增加。

若將搜索空間劃分為d個(gè)子空間并分配至私有云節(jié)點(diǎn)，則改進(jìn)PSO算法的并行執(zhí)行時(shí)間為

式中，Tw為私有云從節(jié)點(diǎn)與主節(jié)點(diǎn)的通信延遲時(shí)間。

若Tserial≤Tw，根據(jù)式（17），無(wú)論整數(shù)d取何值，總有式（18）成立

若Tserial＞Tw，則當(dāng)d取最小值2（只有兩個(gè)從節(jié)點(diǎn)的私有云 ）時(shí)，要使得Tserial＞Tparallel成立 ，至少應(yīng)滿足（可通過(guò)求解不等式Tserial-Tparallel＞0獲得-）

式（19）的物理意義是，只有當(dāng)串行工作模型下改進(jìn)PSO算法的執(zhí)行時(shí)間大于私有云平臺(tái)主從節(jié)點(diǎn)通信延遲時(shí)間的4倍以上，利用私有云并行求解才會(huì)節(jié)省時(shí)間，否則主從節(jié)點(diǎn)的通信延遲將會(huì)超過(guò)優(yōu)化算法的執(zhí)行時(shí)間?？疾槭剑?6）可知，量子粒子及其伴隨粒子的個(gè)數(shù)越多，利用私有云并行求解才會(huì)越有利。

當(dāng)Tserial?Tw時(shí)，主從節(jié)點(diǎn)的通信延遲可忽略不計(jì)，根據(jù)式（17）有

此時(shí)利用私有云并行求解的時(shí)間僅為串行求解模式的1/d，可節(jié)省大量計(jì)算時(shí)間。

3.2私有云計(jì)算平臺(tái)

私有云是云計(jì)算的一種應(yīng)用模式，它與公有云計(jì)算平臺(tái)的區(qū)別在于其專用性。私有云不對(duì)外提供服務(wù)，而只供單位內(nèi)部使用。隨著云計(jì)算技術(shù)的發(fā)展，特別是一些云計(jì)算操作系統(tǒng)的開(kāi)源，搭建一個(gè)私有云平臺(tái)變得較為容易。由于云計(jì)算本身就是一種分布式的且并行的計(jì)算模式，適用于并行求解PSO算法。

一個(gè)私有云平臺(tái)包括一個(gè)主節(jié)點(diǎn)和多個(gè)從節(jié)點(diǎn)。將改進(jìn)PSO算法的任務(wù)分配給主節(jié)點(diǎn)，按從節(jié)點(diǎn)的數(shù)量劃分粒子群的子群數(shù)量，對(duì)每個(gè)從節(jié)點(diǎn)規(guī)定其決策子空間，多個(gè)從節(jié)點(diǎn)之間的決策子空間互不相交。在每個(gè)從節(jié)點(diǎn)上獨(dú)立運(yùn)行算法，在迭代一定次數(shù)后各從節(jié)點(diǎn)暫停算法，將各自的子群全局最優(yōu)解送入主節(jié)點(diǎn)比較，主節(jié)點(diǎn)將最差解的子群解散，子群內(nèi)的粒子仍作為一個(gè)群體保留，并令其向最優(yōu)解子群遷移。經(jīng)過(guò)一段時(shí)間后，從節(jié)點(diǎn)上的子群逐漸解散，并最終收斂至僅存子群，而所有的粒子也將收斂于該子群內(nèi)的某個(gè)峰值。

3.3基于Map Reduce的算法求解

Map Reduce是Google公司開(kāi)發(fā)的大型分布式并行編程模型，目前廣泛應(yīng)用于云計(jì)算平臺(tái)。Map Reduce用逐步分解的原則，通過(guò)把大規(guī)模數(shù)據(jù)集分發(fā)給主節(jié)點(diǎn)下的各從節(jié)點(diǎn)，共同完成計(jì)算任務(wù)，最后通過(guò)整合各從節(jié)點(diǎn)的結(jié)果，而得到任務(wù)的最終解。本文通過(guò)私有云平臺(tái)上的Map Reduce解算改進(jìn)PSO算法，可解決單機(jī)運(yùn)算資源不足的問(wèn)題。按照這一思路，設(shè)計(jì)了基于Map Reduce的解算流程，如圖2所示。

設(shè)計(jì)了3個(gè)子程序?qū)?yīng)于圖2中的流程，分別為：

（1）并行任務(wù)管理子程序。改進(jìn)PSO算法的管理程序，不會(huì)運(yùn)行具體算法，而是對(duì)任務(wù)進(jìn)行集中管理，主要負(fù)責(zé)將任務(wù)區(qū)域分解為與私有云節(jié)點(diǎn)數(shù)目相同的子區(qū)域，將各個(gè)搜索子區(qū)域分配給對(duì)應(yīng)的計(jì)算節(jié)點(diǎn)，記錄任務(wù)是如何分解的，以及分配到了哪個(gè)計(jì)算節(jié)點(diǎn)上，并負(fù)責(zé)各分節(jié)點(diǎn)與主節(jié)點(diǎn)之間的信息交換，獲取從節(jié)點(diǎn)的局部最優(yōu)解，并評(píng)判出算法當(dāng)前的全局最優(yōu)解。

（2）計(jì)算節(jié)點(diǎn)監(jiān)控子程序。類似“看門狗”程序，避免因宕機(jī)而導(dǎo)致計(jì)算任務(wù)失敗。首先負(fù)責(zé)備份并行任務(wù)管理子程序中的關(guān)鍵參數(shù)，如區(qū)域劃分和節(jié)點(diǎn)分配等信息，一旦主節(jié)點(diǎn)宕機(jī)可在重啟后盡快恢復(fù)事務(wù)；同時(shí)監(jiān)控各個(gè)從節(jié)點(diǎn)的執(zhí)行狀態(tài)，若不能獲取從節(jié)點(diǎn)的提交信息，則判斷其失效。

（3）算法執(zhí)行子程序。接受并行任務(wù)管理子程序分配的搜索子域，在決策子空間S in內(nèi)執(zhí)行改進(jìn)的PSO算法，迭代一定次數(shù)后將子群內(nèi)最優(yōu)解提交給并行任務(wù)管理子程序，由后者確定出當(dāng)前的全局最優(yōu)解；按時(shí)響應(yīng)計(jì)算節(jié)點(diǎn)監(jiān)控子程序，避免其誤判。

圖2　基于MapReduce的改進(jìn)PSO算法并行求解流程

4　實(shí)驗(yàn)與分析

為了評(píng)估本文改進(jìn)PSO算法的有效性，進(jìn)行了3組試驗(yàn)。實(shí)驗(yàn)對(duì)象為約束優(yōu)化標(biāo)準(zhǔn)測(cè)試函數(shù)（g01～g13）［15］中的g09與g13，分別對(duì)應(yīng)約束條件為不等式與等式兩種約束特征。

實(shí)驗(yàn)平臺(tái)為具有1個(gè)主節(jié)點(diǎn)與8個(gè)從節(jié)點(diǎn)的私有云，各節(jié)點(diǎn)的硬件配置為雙核CPU，主頻2.6GHz，內(nèi)存4GB，采用Matlab軟件編寫(xiě)并運(yùn)行測(cè)試代碼。

為保證比較的公平性，對(duì)于通用的參數(shù)各算法采用相同的參數(shù)值，其中粒子群數(shù)量400個(gè)，迭代次數(shù)1 000次，跳變常數(shù)c與粒子收縮量Χ均采用文獻(xiàn)［16］提供的推薦值，即c=2.05，Χ=0.729 8。

4.1與其他算法的比較

為驗(yàn)證改進(jìn)后PSO算法的全局優(yōu)化性能，將本文算法與CPSO［5］、HPSO［6］與CLPSO［8］進(jìn)行了比較。其中運(yùn)行CPSO、HPSO與CLPSO的計(jì)算平臺(tái)與私有云中單個(gè)從節(jié)點(diǎn)的硬件配置相同，而對(duì)于本文算法，將總數(shù)為400的粒子群均分至8個(gè)從節(jié)點(diǎn)，這樣每個(gè)子群的粒子數(shù)量為50，伴隨粒子數(shù)量為100。

以函數(shù)g 13為例，介紹本文算法的執(zhí)行過(guò)程。根據(jù)文獻(xiàn)［15］中函數(shù)g13的定義，該函數(shù)包括5個(gè)約束變量，其中變量x3的搜索范圍為-3.2≤x3≤3.2。保持其余4個(gè)變量的搜索范圍不變，將x3的搜索范圍按私有云的從節(jié)點(diǎn)數(shù)量平均分為8份，分別為-3.2≤x31≤-2.4，-2.4≤x32≤-1.6，-1.6≤x33≤-0.8，-0.8≤x34≤0，0≤x35≤0.8，0.8≤x36≤1.6，1.6≤x37≤2.4，2.4≤x38≤3.2。然后啟動(dòng)私有云平臺(tái)，將這8個(gè)搜索區(qū)間分配至平臺(tái)的8個(gè)從節(jié)點(diǎn)，并啟動(dòng)算法。每次迭代完成，各從節(jié)點(diǎn)都向主節(jié)點(diǎn)報(bào)告本次迭代的子群最優(yōu)解，由主節(jié)點(diǎn)比較出本次迭代的全局最優(yōu)解與最差解。在經(jīng)過(guò)一定的迭代次數(shù)后，將當(dāng)前全局最差解的子群標(biāo)記為刪除態(tài)，即僅恢復(fù)變量x3搜索范圍的原始定義-3.2≤x3≤3.2，并使該子群向全局最優(yōu)解方向運(yùn)動(dòng)。經(jīng)過(guò)一定次數(shù)的迭代后，所有子群的所有粒子均指向x3的某一搜索范圍，算法的收斂區(qū)間越來(lái)越集中，并將最后一次迭代所標(biāo)記的全局最優(yōu)解作為算法的解。4種算法分別運(yùn)行100次后統(tǒng)計(jì)得到g09與g13函數(shù)的優(yōu)化解分布如表1所示。

表1　本文算法與CPSO、HPSO、CLPSO的比較

標(biāo)準(zhǔn)測(cè)試函數(shù)g09與g13的最優(yōu)解分別為680.630 057 3與0.053 949 8，對(duì)照表1的測(cè)試結(jié)果可見(jiàn)，本文算法對(duì)兩組函數(shù)尋找到最優(yōu)解的概率均優(yōu)于其他3種算法。

4.2多樣化性能測(cè)試

多樣化是本文算法的核心，多樣化機(jī)制的實(shí)現(xiàn)由多子群劃分、量子粒子和伴隨粒子3部分構(gòu)成。本小節(jié)對(duì)量子粒子與伴隨粒子對(duì)算法的貢獻(xiàn)進(jìn)行實(shí)驗(yàn)分析，而將多子群劃分的測(cè)試與私有云的加速比實(shí)驗(yàn)結(jié)合進(jìn)行。

仍然采用g09與g13作為測(cè)試函數(shù)，算法的各項(xiàng)參數(shù)與第4.1節(jié)一致。分別將以下改動(dòng)應(yīng)用到測(cè)試中：①量子粒子還原為普通粒子；②去掉量子粒子；③伴隨粒子數(shù)量增加10%；④伴隨粒子數(shù)量減少10%。將改動(dòng)后的算法分別運(yùn)行100次，得到的優(yōu)化解統(tǒng)計(jì)分布如表2所示。結(jié)合表1與表2中可見(jiàn)，對(duì)于g09與g13在最優(yōu)解區(qū)間（分別為680. 6～680.8與0.05～0.07）尋找概率而言：①不采用量子粒子導(dǎo)致算法的尋優(yōu)概率分別下降了14.2%與8.4%；②不采用伴隨粒子的尋優(yōu)概率分別下降了26.9%與35.2%；③伴隨粒子的數(shù)量提升10%可使得尋優(yōu)概率分別提高1.6%與2.8%；④伴隨粒子數(shù)量減少10%，尋優(yōu)概率分別下降3.1%與5.6%。

表2　多樣化機(jī)制性能測(cè)試

4.3加速實(shí)驗(yàn)

將整個(gè)粒子群劃分為多個(gè)子群后分配至私有云平臺(tái)各節(jié)點(diǎn)運(yùn)算是本文提高算法速度的主要方法。分配方法有多種，這里將x1（也可按其他變量的范圍劃分）的范圍按私有云的從節(jié)點(diǎn)數(shù)量劃分為8份，其他變量保持不變。然后每個(gè)子域上建立一個(gè)子群，再將子群分配至私有云的各節(jié)點(diǎn)運(yùn)行。

為驗(yàn)證子群數(shù)量對(duì)算法執(zhí)行速度的影響，進(jìn)行了不同子群數(shù)量d下的加速比實(shí)驗(yàn)，如圖3所示。

圖3　加速試驗(yàn)結(jié)果匯總

圖3中，d=1為不進(jìn)行子群劃分下的算法執(zhí)行速度。隨著d的增加，執(zhí)行時(shí)間大幅縮短，然而當(dāng)d≥8之后，由于節(jié)點(diǎn)數(shù)量的增加，從節(jié)點(diǎn)之間的網(wǎng)絡(luò)通信延遲得到了累加，算法執(zhí)行的增速放緩并趨于平穩(wěn)。

5　結(jié)　論

本文主要做了兩項(xiàng)工作：一是針對(duì)經(jīng)典PSO算法易陷入局部最優(yōu)的缺點(diǎn)，從解的多樣化原則出發(fā)，分別利用多子群機(jī)制和量子粒子+伴隨粒子機(jī)制保證了求解的群間多樣化和子群內(nèi)多樣化；二是針對(duì)改進(jìn)后PSO算法計(jì)算量大、計(jì)算復(fù)雜的特點(diǎn)，利用私有云計(jì)算平臺(tái)進(jìn)行并行計(jì)算，在MapReduce編程框架的基礎(chǔ)上，編寫(xiě)了改進(jìn)PSO算法的并行求解流程。最后通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的正確性。本文方法特別適合于涉及大計(jì)算量的約束優(yōu)化問(wèn)題，通過(guò)私有云計(jì)算平臺(tái)并行計(jì)算可成倍提高此類問(wèn)題的計(jì)算速度。

［1］Wang Y，Cai Z X，Zhou Y R，et al.Constrained optimization evolutionary algorithms［J］.Journal of Software，2009，20（1）：11 29.（王勇，蔡自興，周育人，等.約束優(yōu)化進(jìn)化算法［J］.軟件學(xué)報(bào)，2009，20（1）：11-29.）

［2］Saber ME，Ruhul A S，Efren M.Self-adaptive mix of particle swarm methodologies for constrained optimi zation［J］.Information Sciences，2014，277（9）：216-233.

［3］Bonyadi M R，Michalewicz Z.Locating potentially disjoint feasible regionsof a search space with a particle swarm optimizer［M］. Berlin：Springer Press，2014：205-230.

［4］Kennedy J，Eberhart R.Particle swarm optimization［C］//Proc. of the IEEE International Conference on Neural Networks，1995：1942-1948.

［5］Cagnina L C，Esquivel S C，Coello C A.A particle swarm optimizer for constrained numerical optimization［M］.Berlin：Springer Press，2006：910-919.

［6］Cagnina L C，Esquivel S C，Coello C A.Solving constrained optimization problems with a hybrid particle swarm optimization algorithm［J］.Engineering Optimization，2011，43（8）：843-866.

［7］Liang JJ，Suganthan P N.Dynamic multi-swarm particle swarm optimizer with a novel constraint handling mechanism［C］//Proc.of the IEEE Congress on Eυolutionary Computation，2006：9-16.

［8］Paquet U，Engelbrecht A P.Particle swarms for linearly constrained optimisation［J］.Fundamenta Informaticae，2007，76（2）：147-179.

［9］Bonyadi M R，Li X，Michalewicz Z.A hybrid particle swarm with velocity mutation for constraint optimization problems［C］//Proc.of the Genetic and Eυolutionary Computation Conference，2013：1-8.

［10］Liang J J，Shang Z G，Li Z H.Coevolutionary comprehensive learning particle swarm optimizer［C］//Proc.of the IEEE Congress on Eυolutionary Computation，2010：1-8.

［11］Mohammad R B，Xiang L，Zbigniew M.A hybrid particle swarm with a time-adaptive topology for constrained optimization［J］. Swarm and Eυolution-ary Computation，2014，18（10）：22-37.

［12］Christian B，Daniel M.Swarm intelligence introduction and applications［M］.Long F，trans.Beijing：National Defense Indus-try Press，2011：195-218.（Christian B，Daniel M.群智能簡(jiǎn)介與應(yīng)用［M］.龍飛，譯.北京：國(guó)防工業(yè)出版社，2011：195-218.）

［13］Sun J，F(xiàn)eng B，Xu W B.Particle swarm optimization with particles having quantum behavior［C］//Proc.of the Congress on Eυolutionary Computation，2004：326-331.

［14］Blackwell B.Multi-swarms，exclusion and anti-convergence in dynamic environments［J］.IEEE Trans.on Eυolutionary Computation，2006，10（4）：459-472.

［15］Thomas P R，Yao X.Stochastic ranking for constrained evolutionary optimization［J］.IEEE Trans.on Eυolutionary Computation，2000，4（3）：284-294.

［16］Clerc M，Kennedy J.The particle swarm-explosion，stability，and convergence in a multidimensional complex space［J］.IEEE Trans.on Eυolutionary Computation，2002，6（1）：58-73.

Constrained optimization problems solving based on private cloud and improved particle swarm optimization

ZHANG Yong-qiang1，2，XU Zong-chang1，HU Kai-kai1，HU Chun-yang1
（1.Department of Technical Support Engineering，Academy of Armored Force Engineering，Beijing 100072，China；2.Naυal Air Force Institute，Huludao 125000，China）

In order to solve constrained optimization problems with higher accuracy and faster computing speed，several improvements are raised on particle swarm optimization（PSO）and its computing method.Solutions'diversification mechanism is applied in PSO to improve its global optimization ability：decision space is divided into multiple searching subspaces，while multi-subswarms are created according to those searching subspaces，and multi-subswarms are searched independently to get solutions'diversification among subswarms；ordinary particles is replaced by quantum particles in PSO，while associated particles that follow globular distribution is vested in each quantum particle，which could improve solutions'diversification in subswarms.Running speed of the improved PSO is increased via parallel computing：Parallel computing flow of the improved PSO is analyzed based on the private cloud platform and the algorithm for the flow is programmed based on MapReduce.The experimental results show that the proposed method has higher accuracy solutions and stability，and the performance and computing speed is exponentially improved.

constrained optimization；particle swarm optimization（PSO）；private cloud platform；parallel solving；diversification

TP 301.6；E 911

A

10.3969/j.issn.1001-506X.2016.05.18

1001-506X（2016）05-1086-07

2015-04-07；

2015-11-10；網(wǎng)絡(luò)優(yōu)先出版日期：2015-12-23。

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20151223.1114.030.html

張永強(qiáng)（1983-），男，博士研究生，主要研究方向?yàn)榕灤瑪y行備件優(yōu)化、裝備保障特性與綜合保障。

E-mail：wying40852@163.com

徐宗昌（1941-），男，教授，主要研究方向?yàn)檠b備保障特性與綜合保障。

E-mail：xuzca@yeah.net

呼凱凱（1987-），男，博士研究生，主要研究方向?yàn)檠b備保障特性與綜合保障。

E-mail：hkk1987@163.com

胡春陽(yáng)（1991-），男，碩士研究生，主要研究方向?yàn)檠b備保障特性與綜合保障。

E-mail：hcy1992@163.com