基于并行策略的改進(jìn)混合粒子群算法及其應(yīng)用

陸鳳儀，于浩洋，徐格寧

（太原科技大學(xué)機(jī)械工程學(xué)院，山西 太原 030024）

1 引言

優(yōu)化的過(guò)程就是將一個(gè)需要解決的問(wèn)題抽象為一個(gè)數(shù)學(xué)模型，并使用優(yōu)化算法求其最大值或最小值。優(yōu)化算法可分為梯度優(yōu)化算法和非梯度優(yōu)化算法。梯度優(yōu)化算法指向最優(yōu)點(diǎn)的搜索方向明確，收斂速度快，對(duì)于復(fù)雜多峰問(wèn)題容易陷入局部最優(yōu)，前提條件是目標(biāo)函數(shù)連續(xù)且可導(dǎo)，在實(shí)際工程問(wèn)題中目標(biāo)函數(shù)往往是離散、不可導(dǎo)。非梯度優(yōu)化算法缺乏指向最優(yōu)點(diǎn)的搜索方向，搜索過(guò)程更為隨機(jī)，但收斂速度較慢，容易跳出局部最優(yōu)，不依賴(lài)目標(biāo)函數(shù)的連續(xù)、可導(dǎo)性，更符合工程要求。

粒子群算法（PSO）是當(dāng)下最流行的非梯度優(yōu)化算之一，被廣泛研究與改進(jìn)。目前對(duì)粒子群算法的改進(jìn)分為對(duì)粒子群算法自身的改進(jìn)和混合其他算法改進(jìn)粒子群算法。在粒子群算法自身的改進(jìn)方面：文獻(xiàn)[1]中提出一種自適應(yīng)的方法，根據(jù)其性能和距離，確定了每個(gè)粒子在不同維度上的慣性權(quán)重，提升了粒子群算法解決方案質(zhì)量。文獻(xiàn)[2]針對(duì)可靠性優(yōu)化問(wèn)題，提出一種沒(méi)有速度和參數(shù)的NSC-PSO 算法。文獻(xiàn)[3]提出了3 種非線性的慣性權(quán)重，來(lái)提升粒子群算法的質(zhì)量和收斂速度。上述文獻(xiàn)對(duì)粒子群算法自身的參數(shù)進(jìn)行改進(jìn)，挖掘粒子群算法的潛力，有效地提升了粒子群算法針對(duì)某些目標(biāo)函數(shù)的性能，但難以克服高維度復(fù)雜優(yōu)化易陷入局部最優(yōu)的局限性。在混合其他算法改進(jìn)粒子群算法方面：文獻(xiàn)[4]借鑒了差分進(jìn)化算法的交叉和選擇操作，生成指導(dǎo)向量提升優(yōu)化結(jié)果質(zhì)量和求解效率。文獻(xiàn)[5]提出一種粒子群算法與實(shí)數(shù)編碼遺傳算法相結(jié)合的混合算法，很好的平衡了混合算法的開(kāi)發(fā)能力與探索能力。文獻(xiàn)[6-8]使用模擬退火算法（SA）作為PSO 的本地搜索機(jī)制，幫助PSO 跳出局部最優(yōu)。借鑒其他算法可以很好地改善PSO本身的一些難以解決的缺陷，但會(huì)增加算法的復(fù)雜程度。

就工程實(shí)際應(yīng)用而言，文獻(xiàn)[9]使用3S（強(qiáng)度、剛度、穩(wěn)定性）理論及幾何約束構(gòu)建門(mén)式起重機(jī)門(mén)架優(yōu)化模型，使用零階優(yōu)化方法優(yōu)化該模型，減小了門(mén)架質(zhì)量。文獻(xiàn)[10]使用3S（強(qiáng)度、剛度、穩(wěn)定性）理論構(gòu)建通用橋式起重機(jī)主梁金屬結(jié)構(gòu)模型，提出并使用改進(jìn)果蠅算法優(yōu)化，減小了主梁體積。但并沒(méi)有針對(duì)實(shí)際情況合理劃分網(wǎng)格，圓整后會(huì)產(chǎn)生較大誤差。

鑒于此，以并行策略為基礎(chǔ)，不改變種群規(guī)模，獨(dú)立運(yùn)行3種算法，每隔n次比較3 種算法，獲得當(dāng)前最優(yōu)點(diǎn)，并用其替換粒子群算法的種群最優(yōu)點(diǎn)，利用PSO 算法個(gè)體向種群最優(yōu)靠近的特點(diǎn)，使被替換后的PSO 算法跳出局部最優(yōu)，提升優(yōu)化結(jié)果的質(zhì)量。同時(shí)，為驗(yàn)證算法的實(shí)用性，將其應(yīng)用在10t～32t/31.5m 系列化的橋式起重機(jī)主梁金屬結(jié)構(gòu)輕量化設(shè)計(jì)中。

2 算法原理

2.1 粒子群算法（PSO）

粒子群算法（Particle Swarm Optimization）由Kennedy 和Eberhart 于1995 年提出，是一種模擬鳥(niǎo)群覓食行為的智能算法[11]。鳥(niǎo)群在整個(gè)搜索食物過(guò)程中，鳥(niǎo)群相互溝通，信息共享，讓所有鳥(niǎo)知道種群最優(yōu)位置，每只鳥(niǎo)通過(guò)種群最佳位置和個(gè)體最佳位置修正飛行的方向向量，最終鳥(niǎo)群聚集到食物附近。粒子群算法中有NP個(gè)粒子，粒子有速度向量V和位置X兩個(gè)屬性，在搜索空間中隨機(jī)生成NP個(gè)初始位置X和速度向量V。

在迭代過(guò)程中，每個(gè)粒子按式（1）生成下一代粒子的速度向量和位置：

式中：ω—慣性因子；

c1、c2—加速因子，為正常數(shù)；

R1、R2—［0，1］之間的隨機(jī)數(shù)；

Pb、Pg—粒子當(dāng)前最優(yōu)位置和種群最優(yōu)位置；

G—已完成迭代次數(shù)。

為了防止粒子飛出搜索空間，對(duì)粒子的速度和位置進(jìn)行約束，如式（2）、式（3）所示，算法流程，如圖 1 所示。

式中：Vmax、Xmax—粒子速度和位置的上限；Vmin、Vmin—粒子速度和位置的下限。

圖1 粒子群算法流程圖Fig.1 PSO Flow Diagram

粒子群算法魯棒性好，易于實(shí)現(xiàn)，收斂速度快，但在解高維度的多峰問(wèn)題時(shí)容易陷入局部最優(yōu)，廣泛應(yīng)用于非線性規(guī)劃、路徑規(guī)劃、汽車(chē)生產(chǎn)[12]等領(lǐng)域。如何在粒子群算法尋優(yōu)過(guò)程中平衡探索能力和開(kāi)發(fā)能力對(duì)算法的全局收斂尤為重要。

2.2 差分進(jìn)化算法（DE）

差分進(jìn)化算法（Differential Evolution），由Rainer Storn 和 Kenneth Price 于1997 年提出[13]。差分進(jìn)化算法源于遺傳算法，其基本思想是利用當(dāng)前種群個(gè)體間的差異重組得到中間種群，然后子代個(gè)體與父代個(gè)體競(jìng)爭(zhēng)獲得新一代種群。差分進(jìn)化算法中個(gè)體數(shù)量為NP，在搜索空間隨機(jī)生成NP個(gè)位置向量，種群個(gè)體位置向量為其中，D—優(yōu)化目標(biāo)函數(shù)的維度；G—種群經(jīng)過(guò)G次迭代；i—種群中的第i個(gè)個(gè)體，1≤i≤NP。

首先，種群位置向量根據(jù)式（4）進(jìn)行突變操作，得到個(gè)體變異位置向量Tij。

式中：r1、r2、r3—［1，NP］內(nèi)互不相等的隨機(jī)整數(shù)。

然后對(duì)種群位置向量和變異位置向量進(jìn)行交叉操作，得到個(gè)體交叉位置向量Cij，交叉操作，如式（5）所示。

式中：cr—變異算子。

最后進(jìn)行選擇操作，如式（6）所示，得到下一代個(gè)體位置向量LG+1，選擇操作采用的是貪婪選擇策略，差分進(jìn)化算法流程圖如圖2 所示。

DE 算法能有效的處理復(fù)雜多峰問(wèn)題，與PSO 算法形成互補(bǔ)。變異算子cr對(duì)DE 算法的性能影響很大，合理的設(shè)置cr，可以很好的平衡DE 算法的開(kāi)發(fā)能力與探索能力。DE 算法已被廣泛的應(yīng)用于許多實(shí)際問(wèn)題如模式識(shí)別、電力優(yōu)化、特征選擇等[14]。

圖2 差分進(jìn)化算法流程圖Fig.2 DE Flow Diagram

2.3 人工蜂群算法（ABC）

人工蜂群算法（ABC）是由Karaboga 在2005 年提出[15]。人工蜂群算法來(lái)源于蜂群采蜜行為是一種基于群智能的優(yōu)化算法。人工蜂群算法將蜂群的采蜜行為分為初始化蜜源、放出雇傭蜂、放出觀察蜂、放出偵查蜂四部分。在算法迭代開(kāi)始之前，在搜索空間中隨機(jī)生成NP/2 個(gè)點(diǎn)作為初始化蜜源的位置Si，D｝，其中，NP為種群規(guī)模，i代表第i個(gè)蜜源，1≤i≤NP/2，D為蜜源位置的維度，G為當(dāng)前迭代次數(shù)，記錄當(dāng)前蜜源被使用次數(shù)的Trail（i）=0；迭代開(kāi)始后，放出NP/2 個(gè)雇傭蜂在蜜源附近尋找新蜜源，觀察蜂位置Li由式（7）得出。

式中：d—隨機(jī)選取的一個(gè)維度；

k—隨機(jī)選取的一個(gè)蜜源。

按貪心策略更新蜜源位置，若蜜源位置更新，則Trail（i）=0，若蜜源位置沒(méi)有改變，則Trail（i）=Trail（i）+1。

然后放出觀察蜂，每個(gè)蜜源都有一定的概率被觀察蜂跟隨，每個(gè)蜜源被跟隨的概率Pi按式（8）計(jì)算。

式中：fit（Li）—第i個(gè)蜜源的適應(yīng)度。

使用式（7）在被跟隨蜜源附近搜索新蜜源，直至NP/2 個(gè)跟隨蜂全部放出，并用貪心策略更新蜜源，若蜜源位置更新，則Trail（i）=0，若蜜源位置沒(méi)有改變，則Trail（i）=Trail（i）+1。

若蜜源滿足Trail（i）＞limit，其中l(wèi)imit為放出觀察蜂的界限，則進(jìn)行放出偵查蜂操作，在搜索空間中隨機(jī)生成一個(gè)蜜源替代掉蜜源i。limit的值影響算法的開(kāi)發(fā)能力，需設(shè)置為一個(gè)合適的值，人工蜂群算法流程圖，如圖3 所示。ABC 算法每次迭代都進(jìn)行全局搜索和局部搜索，具有很強(qiáng)的全局收斂能力，對(duì)目標(biāo)函數(shù)及初值無(wú)特殊要求，適應(yīng)性強(qiáng)。ABC 被廣泛應(yīng)用于結(jié)構(gòu)工程、網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)、圖像處理等領(lǐng)域[16]。

2.4 混合算法（DA_PSO）

DA_PSO 算法以粒子群算法為基礎(chǔ)，采用并行混合策略，將DE 算法和ABC 算法嵌入 PSO 算法中，DE 算法和 ABC 算法在求解高維度、復(fù)雜問(wèn)題，性能出眾，使用上述2 種算法的最優(yōu)點(diǎn)幫助PSO 算法跳出局部最優(yōu)，并加以探索，可提高優(yōu)化結(jié)果的質(zhì)量。DA_PSO 算法在每次并行3 種算法迭代結(jié)束后設(shè)置一個(gè)交流區(qū)，通過(guò)交流區(qū)將DE 算法和ABC 算法的求解精度和穩(wěn)定性傳遞給PSO 算法，進(jìn)而得到一種功能強(qiáng)大的算法。交流區(qū)分為判斷、擇優(yōu)、傳值三個(gè)部分。DA_PSO 算法的流程，如圖4所示。

圖4 DA_PSO 流程圖Fig.4 DA_PSO Flow Diagram

判斷部分在每次3 種算法迭代結(jié)束后，判斷DA_PSO 算法是否進(jìn)入交流區(qū)。判斷操作使3 種算法每隔n次交流一次（n的值根據(jù)實(shí)際情況設(shè)置）。

判斷進(jìn)入交流區(qū)后，進(jìn)入擇優(yōu)部分，選出3 種算法運(yùn)行結(jié)果中的最優(yōu)值和最優(yōu)點(diǎn)。如式（9）所示。

式中：fit—3 種算法運(yùn)行產(chǎn)生的最佳適應(yīng)度；PSO_fit、DE_fit、ABC_fit—PSO 算法、DE 算法、ABC 算法的最佳適應(yīng)度；fit_position—3 種算法的最佳位置（fit對(duì)應(yīng)的位置）；position—擇優(yōu)結(jié)果。

傳值部分的功能是將擇優(yōu)部分產(chǎn)生的最優(yōu)值，最優(yōu)點(diǎn)傳給PSO 算法，如式（10）所示。

式中：Pg—PSO 算法的種群最優(yōu)位置。

這個(gè)操作會(huì)幫助粒子群算法擺脫自身局限，有效提升優(yōu)化結(jié)果的質(zhì)量。

3 算法測(cè)試評(píng)價(jià)

3.1 測(cè)試函數(shù)

為測(cè)試DA_PSO 算法的性能，使用如表1 所示的5 個(gè)函數(shù)對(duì)混合算法進(jìn)行算法測(cè)試。測(cè)試函數(shù)f1、f2為單峰函數(shù)，f2函數(shù)的全局最優(yōu)點(diǎn)位于一個(gè)平滑、狹長(zhǎng)的拋物線形山谷內(nèi)，算法很難辨別搜索方向，f3是二維復(fù)雜函數(shù)，具有很強(qiáng)的震蕩性，很難找到全局最優(yōu)，f4、f5是典型的非線性多模態(tài)函數(shù)，具有廣闊的搜索空間，是優(yōu)化算法很難處理的多模態(tài)問(wèn)題。

表1 測(cè)試函數(shù)Tab.1 Test Function

3.2 測(cè)試結(jié)果與評(píng)價(jià)

將上述5 個(gè)測(cè)試函數(shù)分別用PSO 算法、ABC 算法、DE 算法、DA_PSO 算法取合適參數(shù)運(yùn)行30 次，提取均值、最優(yōu)值、最差值、標(biāo)準(zhǔn)差作為評(píng)價(jià)參數(shù)，其中均值體現(xiàn)算法的精度，標(biāo)準(zhǔn)差體現(xiàn)算法的穩(wěn)定性。結(jié)果如表2 所示，DA_PSO 算法的測(cè)試函數(shù)迭代次數(shù)的均值，如圖5 所示。

由表2 和圖5 可以看出，PSO 算法在善于解決小范圍、低維度優(yōu)化問(wèn)題（f2、f3），在大范圍、高維度的函數(shù)（f1、f4、f5）的測(cè)試中得到的結(jié)果精度和穩(wěn)定性都很差；與PSO 算法相反，DE 算法在大范圍、高維度的函數(shù)（f1、f4、f5）測(cè)試中收斂速度快，得到的結(jié)果精度高；ABC 算法在各類(lèi)函數(shù)測(cè)試中取得優(yōu)化結(jié)果質(zhì)量較好，穩(wěn)定性優(yōu)于DE 算法和PSO 算法。DA_PSO 算法能很好的解決上述所有測(cè)試函數(shù)，是一種高精度、高穩(wěn)定性、適應(yīng)性強(qiáng)的優(yōu)化算法。

表2 測(cè)試結(jié)果與評(píng)價(jià)Tab.2 Test Result

圖5 迭代次數(shù)的均值Fig.5 Average Value of Iterating Times

DE 算法與PSO 算法擅長(zhǎng)領(lǐng)域恰好相反，具有很強(qiáng)的互補(bǔ)性，ABC 算法在解決各類(lèi)測(cè)試函數(shù)所表現(xiàn)出的穩(wěn)定性是PSO 算法和ABC 算法所不具備的。PSO 算法具有很好的魯棒性，易與其他算法相結(jié)合，所有粒子向種群最優(yōu)位置聚集的功能，可以整合3 種優(yōu)化算法的信息，并加以探索，在精度方面會(huì)表現(xiàn)會(huì)優(yōu)于3種算法單獨(dú)運(yùn)行。在穩(wěn)定性方面，ABC 算法為DA_PSO 算法提供了很好的穩(wěn)定性，DA_PSO 算法采用并行策略進(jìn)一步提高算法的穩(wěn)定性。由于 DA_PSO 算法吸收了 PSO 算法、DE 算法、ABC 算法的特點(diǎn)，DE_PSO 算法的適用范圍更廣。

結(jié)合策略的通用性也很強(qiáng)，不局限于上述3 種算法。這種并行策略只需要其他算法提供給PSO 算法一個(gè)當(dāng)前最優(yōu)點(diǎn)即可，針對(duì)不同的問(wèn)題可以將DE 算法和ABC 算法換成任意一種合適的算法；而且并行算法的個(gè)數(shù)也不是固定的。

4 工程實(shí)例

4.1 優(yōu)化模型構(gòu)建

為進(jìn)一步驗(yàn)證DA_PSO 算法的實(shí)際使用價(jià)值，以10t～32t/31.5m 系列化橋式起重機(jī)主梁結(jié)構(gòu)為研究對(duì)象，使用DA_PSO 算法對(duì)其進(jìn)行輕量化設(shè)計(jì)。橋式起重機(jī)主梁耗費(fèi)的鋼材占成本的30%以上，橋式起重機(jī)進(jìn)行輕量化設(shè)計(jì)對(duì)降低成本具有重要意義。橋式起重機(jī)主梁由上、下蓋板和主腹板、副腹板焊接而成的箱型梁。橋式起重機(jī)結(jié)構(gòu)復(fù)雜，工況多變，承受載荷多樣，對(duì)主梁結(jié)構(gòu)進(jìn)行合理簡(jiǎn)化，得出的橋式起重機(jī)力學(xué)模型，如圖6 所示。

圖6 橋式起重機(jī)力學(xué)模型Fig.6 Bridge Crane Mechanical Model

設(shè)計(jì)方法采用極限狀態(tài)法。橋式起重機(jī)輕量化設(shè)計(jì)就是橋式起重機(jī)主梁在滿足3S（強(qiáng)度、剛度、穩(wěn)定性）設(shè)計(jì)要求的情況下，減輕主梁自重（減小箱型梁截面面積）。主梁優(yōu)化設(shè)計(jì)模型，如式（11）所示。強(qiáng)度約束條件，如式（12）所示。剛度約束條件，如式（13）所示。穩(wěn)定性約束條件，如式（14）所示。

式中：f（X）—優(yōu)化的目標(biāo)函數(shù)（箱型梁截面積）；

g1—強(qiáng)度約束條件；

g2—?jiǎng)偠燃s束條件；

g3—穩(wěn)定性約束條件；

X1—上蓋板寬；

X2—腹板高；

X3—上蓋板厚；

X4—下蓋板厚；

X5—主腹板厚；

X6—副腹板厚；

X7—軌道側(cè)翼緣外伸；

X8—翼緣外伸。

式中：M—危險(xiǎn)截面彎矩；

y—危險(xiǎn)點(diǎn)到形心距離；

Ix—主梁截面慣性矩。

式中：Yc—主梁最大變形；

［y］—許用應(yīng)力［y］=S/1000；

S—主梁跨度。

考慮到主梁的實(shí)際制造情況及主梁各參數(shù)的幾何關(guān)系，主梁的幾何約束定義，如式（15）所示。

在實(shí)際生產(chǎn)中，鋼板的厚度（X3、X4、X5、X6）都為整數(shù)，為方便劃線及備料切割，腹板高（X2）和上蓋板寬（X1）以及兩側(cè)翼緣外伸（X7、X8）都為10 的整數(shù)倍，將整個(gè)尋優(yōu)空間按上述要求劃分網(wǎng)格，DA_PSO 算法在網(wǎng)格的節(jié)點(diǎn)中尋找最優(yōu)解。

將尋優(yōu)空間劃分成整數(shù)網(wǎng)格，更貼近實(shí)際情況，優(yōu)化生成的結(jié)果（箱型梁截面參數(shù)）更符合生產(chǎn)制造要求，若迭代完成后再將結(jié)果圓整，則會(huì)產(chǎn)生較大誤差，要么得出非最優(yōu)解，要么違反約束條件。因此，文本將連續(xù)多維的搜索空間離散成整數(shù)點(diǎn)，有效的降低了求解問(wèn)題的規(guī)模，保證算法得到最優(yōu)解。

4.2 優(yōu)化結(jié)果及分析

將起重機(jī)箱型梁的跨度S 設(shè)置為31.5m，起重量分別為10t，20t，32t?；贒A_PSO 算法的200 次迭代的結(jié)果記錄在表3 中，目標(biāo)函數(shù)的優(yōu)化迭代曲線，如圖7 所示。DA_PSO 算法任意個(gè)體目標(biāo)函數(shù)的優(yōu)化迭代曲線，如圖8 所示。

圖7 目標(biāo)函數(shù)的優(yōu)化迭代曲線Fig.7 Optimal Iteration Curve of the Objective Function

通過(guò)對(duì)圖7、圖8 的分析發(fā)現(xiàn)，DA_PSO 算法在迭代80 次左右達(dá)到收斂，能夠快速的向最優(yōu)解收斂，表3 中的數(shù)據(jù)貼近實(shí)際生產(chǎn)情況，易于加工制造。將表3 中起重量為32t 的數(shù)據(jù)與文獻(xiàn)[17]中仿真算例優(yōu)化后的數(shù)據(jù)（截面面積為33700mm2）進(jìn)行對(duì)比，主梁截面面積減少6.38%。鑒于以上分析，DA_PSO 算法在幾何約束和結(jié)構(gòu)約束的共同作用下，能快速的得到最小截面積且易于生產(chǎn)的箱型梁結(jié)構(gòu)參數(shù)，很好的完成了主梁輕量化設(shè)計(jì)，具有廣闊的工程應(yīng)用前景。

圖8 任意個(gè)體目標(biāo)函數(shù)的優(yōu)化迭代曲線Fig.8 Optimal Iteration Curve of Any Individual Objective Function

表3 優(yōu)化結(jié)果Tab.3 Optimization Results

5 結(jié)論

對(duì)PSO 算法進(jìn)行研究，發(fā)現(xiàn)PSO 算法在解決復(fù)雜，多維度問(wèn)題時(shí)，易早熟，陷入局部最優(yōu)，引入善于解決高維度問(wèn)題DE 算法和ABC 算法與PSO 算法并行、交流得到DA_PSO 算法，并采用測(cè)試函數(shù)和工程算例驗(yàn)證DA_PSO 算法性能，得出結(jié)論如下：

（1）DA_PSO 算法，吸收了并行的3 種算法的優(yōu)點(diǎn)，精度高，穩(wěn)定性好，通用性強(qiáng)，可解決多種問(wèn)題；由于DA_PSO 算法是并行算法，算法的運(yùn)算量比單一優(yōu)化算法的運(yùn)算量大。

（2）提出了一種混合策略，利用粒子群算法的魯棒性好，以及向種群最優(yōu)聚集的特性，針對(duì)要解決的問(wèn)題，將DE 算法和ABC 算法替換成任何其他算法，并吸取其特性，可更改并行算法數(shù)量。

（3）針對(duì)工程實(shí)例合理劃分網(wǎng)格，能降低問(wèn)題規(guī)模，得到適合生產(chǎn)制造的優(yōu)化結(jié)果。