約束優(yōu)化的粒子群改進(jìn)算法及應(yīng)用

李二悶，衛(wèi)良保，李 揚(yáng)，張玉星，馬朝選

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

在科學(xué)計(jì)算與實(shí)際工程優(yōu)化領(lǐng)域，許多優(yōu)化問題都可以歸結(jié)為約束優(yōu)化問題，而且約束優(yōu)化問題的求解要比無約束優(yōu)化優(yōu)化問題的復(fù)雜困難，因此，研究如何處理約束優(yōu)化問題并能得到最優(yōu)解具有很重要的實(shí)際意義。1995年，Eberhart和Kennedy提出的粒子群優(yōu)化算法(PSO)是一種基于種群搜索策略的現(xiàn)代智能優(yōu)化算法[1]。由于其具有易理解、易實(shí)現(xiàn)、不要求目標(biāo)函數(shù)和約束條件可微，并能以較大概率求得全局最優(yōu)解的特點(diǎn)，目前已成功應(yīng)用于神經(jīng)網(wǎng)絡(luò)權(quán)值的訓(xùn)練、連續(xù)和離散系統(tǒng)的參數(shù)優(yōu)化及求解組合優(yōu)化問題等許多優(yōu)化問題[2]。但粒子群算法也表現(xiàn)出了求解成功率不高，易于墜入局部最優(yōu)解，早熟等不足。

近些年來，國內(nèi)外相關(guān)學(xué)者針對粒子群的不足，對粒子群進(jìn)行改進(jìn)，改進(jìn)措施大致分為兩類，一是從對算法本身改進(jìn)，提高PSO單一方面的優(yōu)化性能，例如慣性權(quán)重法、壓縮因子法、混合法等，任子暉、王堅(jiān)于2009年提出了基于聚集距離變化率的自適應(yīng)慣性權(quán)重PSO算法;二是與其它算法思想的組合，使得算法的優(yōu)化效果在一定程度上得到提高，Angeline和Lovbjerg提出了基于遺傳思想改進(jìn)的粒子群算法，2004年高鷹等提出了基于模擬退火的粒子群算法，2008年，ShengLi Song和Li Kong等人，提出了結(jié)合模擬退火和單純形法混合粒子群算法。

結(jié)合PSO算法及約束優(yōu)化問題的特點(diǎn)，并針對PSO算法本身的局限性，為了減少判斷約束條件所需的時(shí)間，提高優(yōu)化精確度、成功率，引入回退算法思想，并用直接解法，提出了一種新的求解約束優(yōu)化問題的改進(jìn)(advanced)的PSO算法——APSO.計(jì)算實(shí)例表明APSO算法具有更強(qiáng)的尋優(yōu)能力和效率。

1 基本粒子群算法

在標(biāo)準(zhǔn)PSO算法中，優(yōu)化問題被抽象成為一群粒子相互支持學(xué)習(xí)去尋找空間中的最優(yōu)位置，而粒子都有一個(gè)被目標(biāo)函數(shù)所決定的適應(yīng)度值(Fitness Value)，一個(gè)決定它們位置和飛行方向的速度，然后粒子們就以該速度追隨當(dāng)前的最優(yōu)粒子在解空間中進(jìn)行搜索，其中，粒子的飛行速度根據(jù)個(gè)體的飛行經(jīng)驗(yàn)和群體的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)的調(diào)整。假設(shè) Xi=(xi1，xi2，…，xin) 是微粒 i的當(dāng)前位置，Vi=(vi，1，vi，2，…，vi，n) 是微粒 i的當(dāng)前飛行速度，那么，基本粒子群算法的進(jìn)化方程如下:

基本微粒群算法的流程如圖1[3]:

圖1 粒子群算法流程圖Fig.1 The flowchart of PSO

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

在處理約束條件時(shí)，參考直接法，若不滿足約束的粒子被直接丟棄刪除，就不能保持好粒子群的完整性和粒子的多樣性，而且若拋棄的粒子過多，空間搜索區(qū)域的粒子密度就會(huì)降低，在后繼的搜索中，平均單個(gè)粒子的探索區(qū)域就擴(kuò)大，由于每一次搜索的步長沒有變化，那么迭代次數(shù)就會(huì)增加，搜索時(shí)間就相應(yīng)的變長，造成求解速度過慢;由于粒子數(shù)目過少，那么只能從僅有的幾個(gè)粒子中尋找最優(yōu)，備選方案就大大減少，易于陷入局部最優(yōu)，更有甚者，若所有的粒子不合工程約束，就得全部丟棄，那么本次優(yōu)化只能以失敗而告終。

引入回退的思想，對于進(jìn)化過程中不滿足約束條件的粒子實(shí)行改造。改造時(shí)，不合格粒子回退到的該粒子歷史最優(yōu)位置再參與到下一輪的進(jìn)化，不僅能較好地保持多樣性、完整性，而且收斂速度快，優(yōu)化成功率也升至100%.表達(dá)式表示為:

改進(jìn)粒子群算法的具體算法流程如下，其中Step6體現(xiàn)了APSO的核心:

step1，依照初始化過程，對微粒群的隨機(jī)位置和速度進(jìn)行初始化并對每個(gè)粒子進(jìn)行約束函數(shù)判斷，若不滿足，則重新初始化該粒子;

step2，計(jì)算每個(gè)微粒的適應(yīng)值;

Step3，對每個(gè)微粒，將其適應(yīng)值與所經(jīng)歷過的最好位置的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前的最好位置;

step4，對每個(gè)微粒，將其適應(yīng)值與全局所經(jīng)歷的最好位置的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前的全局最好位置;

step5，根據(jù)進(jìn)化方程對微粒速度和位置進(jìn)行優(yōu)化;

step6，判斷新的位置是否滿足實(shí)際工程約束函數(shù)，若不滿足，用粒子歷史最優(yōu)位置替代當(dāng)前位置，以方便下一次搜索時(shí)的搜索路徑的改變;

step7，如未達(dá)到結(jié)束條件，則返回step2.

3 測試函數(shù)仿真實(shí)驗(yàn)與對比分析

為了驗(yàn)證改進(jìn)的粒子群算法具有運(yùn)行速度快，不易陷入局部最優(yōu)，成功率高等優(yōu)點(diǎn)，選取由Himmelblau提出的作為benchmark測試算法的權(quán)威優(yōu)化問題做為實(shí)例，并通過改進(jìn)PSO算法及其他文獻(xiàn)對該實(shí)例的優(yōu)化作對比。該優(yōu)化實(shí)例模型具體形式如下[4]:

式中，X=(x1，x2，x3，x4，x5)T

本文改進(jìn)粒子群算法用C++語言在VC++6.0實(shí)現(xiàn)[5]，在Athlon 64 X2一內(nèi)存2G 的DIY 計(jì)算機(jī)上運(yùn)行，設(shè)定相關(guān)初始參數(shù)如表1所示，經(jīng)試驗(yàn)測定。

表1 初始參數(shù)表Tab.1 Initial parameters

為了更好的反映出每種優(yōu)化方法的優(yōu)化性能，和上面文獻(xiàn)一樣，引成功率指標(biāo)以及平均有效迭代次數(shù)如下[5]:

式中的NV表示100次獨(dú)立試驗(yàn)中能成功獲得的最優(yōu)解的試驗(yàn)次數(shù);ni表示第i次成功獲得最優(yōu)解的迭代次數(shù)。根據(jù)上述設(shè)定參數(shù)，對上例進(jìn)行優(yōu)化設(shè)計(jì)，所得結(jié)果與文獻(xiàn)[6-7]中提供的結(jié)果一并列于表2和表3.

從表2中可以明顯看出采用APSO算法獲得的最優(yōu)解優(yōu)于其它方法獲得最優(yōu)解，即精度高;而從成功率來說改進(jìn)PSO算法成功率為100%，從而驗(yàn)證了理論說明;且平均有效迭代次數(shù)也較前面方法降低了數(shù)十倍，說明運(yùn)算收斂速度也最好，即該方法優(yōu)化效果是很不錯(cuò)的，理想的;運(yùn)行時(shí)間也有特別大的減少，分析原因有兩個(gè)方面(1):本計(jì)算機(jī)配置高于文獻(xiàn)中配置，(2)APSO算法快速收斂優(yōu)化也使優(yōu)化時(shí)間降低。

如表3所示，在滿足約束條件情況下，采用本文APSO算法，隨機(jī)進(jìn)行20次尋優(yōu)，得目標(biāo)函數(shù)的最優(yōu)值，該結(jié)果比文獻(xiàn)中所列結(jié)果都好，證明了本文方法可行求解精度高，求解效果優(yōu)。

表2 4種優(yōu)化算法優(yōu)化結(jié)果的對比Tab.2 Comparison of optimization result from 4 optimization algorithms

表3 5種優(yōu)化算法獲得的最優(yōu)結(jié)果對比Tab.3 Comparison of optimal solutions from 5 optimization algorithms

圖2 APSO算法的收斂曲線圖Fig.2 The convergence graph of PSO and APSO

圖2給出了PSO和APSO算法在20次迭代運(yùn)行時(shí)獲得最好優(yōu)化結(jié)果時(shí)的收斂情況。從圖2可以看出。采用改進(jìn)PSO算法時(shí)所優(yōu)化的結(jié)果精確性高，收斂時(shí)間早，而且其收斂速度非常快。

4 工程應(yīng)用算例

為了能夠顯示出APSO算法在工程應(yīng)用上的的優(yōu)點(diǎn)，并研究改進(jìn)后算法對問題的依賴性，本文選取一個(gè)工程有代表性的問題進(jìn)行優(yōu)化應(yīng)用。

4.1 數(shù)學(xué)模型

單梁起重機(jī)廣泛應(yīng)用廠礦企業(yè)，其主要結(jié)構(gòu)件主梁截面大多采用箱形截面，截面簡圖如圖3，現(xiàn)對跨度L=22.5 m，額定載重為5 T的起重機(jī)主梁截面進(jìn)行優(yōu)化，目標(biāo)是使其質(zhì)量最輕，并滿足主梁的剛度，強(qiáng)度，整體穩(wěn)定性，局部穩(wěn)定性以及工藝尺寸等約束[8-11]。優(yōu)化模型如下:

圖3 起重機(jī)主梁截面結(jié)構(gòu)圖Fig.3 The structure figure of girder section

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

為滿足工程需要，最優(yōu)解應(yīng)為絕對可行域內(nèi)的解。初始參數(shù)取 c1=c2=1.005，w=0.8，最大迭代次數(shù)n=100，群粒子數(shù)nd=20.對上述實(shí)例進(jìn)行相關(guān)截面尺寸參數(shù)的優(yōu)化設(shè)計(jì)，計(jì)算結(jié)果與文獻(xiàn)[7]中提供的結(jié)果一并列于表4.

根據(jù)實(shí)際生產(chǎn)，對以上優(yōu)化結(jié)果圓整如下:x1=321，x2=11，x3=832.5，x4=5.5，x5=278.5，x6=397.5，x7=21，f(x)=3682.9 ，主梁的質(zhì)量減輕了近10%，取得比較好的經(jīng)濟(jì)效益，特別是梁的高度降低了近40 mm，可以很大的降低廠房的建設(shè)成本，并且APSO算法一些方面比MATLAB優(yōu)化有一定優(yōu)越性。

表4 優(yōu)化結(jié)果參數(shù)對比表Tab.4 Comparison of optimal solutions

5 結(jié)論

(1)通過改進(jìn)粒子群算法，可以發(fā)揮改進(jìn)后算法的優(yōu)點(diǎn)，求解工程上非線性約束優(yōu)化設(shè)計(jì)問題，其為該類問題的解決提供了新思路。

(2)benchmark測試算法優(yōu)化設(shè)計(jì)算例優(yōu)化結(jié)果顯示本文方法優(yōu)于文獻(xiàn)中粒子群法、LZM-PSO，LGM-PSO等算法，從而體現(xiàn)出此方法的有效性，用該算法可得到滿意的最優(yōu)解。

(3)主梁結(jié)構(gòu)工程優(yōu)化設(shè)計(jì)實(shí)例及其工程應(yīng)用進(jìn)一步證明了本文方法在求解工程非線性約束優(yōu)化問題的有效性，且比MATLAB有一定優(yōu)越性。

[1]KENNEDY J，EBERTHART R C.Particle Swarm Optimization[C]//Proc.IEEE Int’l.Conf.on Neural Networks，1995:l942-1948.

[2]謝曉鋒，張文俊，楊之廉.微粒群算法綜述[J].控制與決策，2003，18(2):129-133.

[3]曾建潮，介婧，崔志華.微粒群算法[M].北京:科學(xué)出版社，2004.

[4]CARLOS A，COELLO C.Use of a Self-adaptive Penalty Approach for Engineering Optimization Problems[J].Computers in Industry，2000，41(2):113-127.

[5]陶元芳.機(jī)械工程軟件技術(shù)基礎(chǔ)[M].北京:機(jī)械工業(yè)出版社，2010.

[6]劉道華，原思聰，蘭洋.混沌映射的粒子群優(yōu)化方法[J].西安電子科技大學(xué)學(xué)報(bào)，2010，3(4);764-769.

[7]HOMAIFAR A，LAI S H Y，QI X.Constrained Optimization via Genetic Algorithms[J].Computers in Industry，1994，35(4):242-254.

[8]李揚(yáng)，衛(wèi)良保.基于VC和MATLAB的單梁起重機(jī)優(yōu)化設(shè)計(jì).[J].太原科技大學(xué)學(xué)報(bào)，2012，33(1);26-29.

[9]徐格寧.機(jī)械裝備金屬結(jié)構(gòu)設(shè)計(jì)[M].北京:機(jī)械工業(yè)出版社，2009.

[10]孫靖民，梁迎春.機(jī)械優(yōu)化設(shè)計(jì)[M].北京:機(jī)械工業(yè)出版社，2002.

[11]全國起重機(jī)械標(biāo)準(zhǔn)化委員會(huì).GB/T3811—2008起重機(jī)設(shè)計(jì)規(guī)范[S].北京:中國標(biāo)準(zhǔn)出版社，2008.