約束優化的粒子群改進算法及應用

李二悶，衛良保，李 揚，張玉星，馬朝選

(太原科技大學機械工程學院，太原 030024)

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

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

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

1 基本粒子群算法

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

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

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

2 改進粒子群算法

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

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

改進粒子群算法的具體算法流程如下，其中Step6體現了APSO的核心:

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

step2，計算每個微粒的適應值;

Step3，對每個微粒，將其適應值與所經歷過的最好位置的適應值進行比較，若較好，則將其作為當前的最好位置;

step4，對每個微粒，將其適應值與全局所經歷的最好位置的適應值進行比較，若較好，則將其作為當前的全局最好位置;

step5，根據進化方程對微粒速度和位置進行優化;

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

step7，如未達到結束條件，則返回step2.

3 測試函數仿真實驗與對比分析

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

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

本文改進粒子群算法用C++語言在VC++6.0實現[5]，在Athlon 64 X2一內存2G 的DIY 計算機上運行，設定相關初始參數如表1所示，經試驗測定。

表1 初始參數表Tab.1 Initial parameters

為了更好的反映出每種優化方法的優化性能，和上面文獻一樣，引成功率指標以及平均有效迭代次數如下[5]:

式中的NV表示100次獨立試驗中能成功獲得的最優解的試驗次數;ni表示第i次成功獲得最優解的迭代次數。根據上述設定參數，對上例進行優化設計，所得結果與文獻[6-7]中提供的結果一并列于表2和表3.

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

如表3所示，在滿足約束條件情況下，采用本文APSO算法，隨機進行20次尋優，得目標函數的最優值，該結果比文獻中所列結果都好，證明了本文方法可行求解精度高，求解效果優。

表2 4種優化算法優化結果的對比Tab.2 Comparison of optimization result from 4 optimization algorithms

表3 5種優化算法獲得的最優結果對比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次迭代運行時獲得最好優化結果時的收斂情況。從圖2可以看出。采用改進PSO算法時所優化的結果精確性高，收斂時間早，而且其收斂速度非常快。

4 工程應用算例

為了能夠顯示出APSO算法在工程應用上的的優點，并研究改進后算法對問題的依賴性，本文選取一個工程有代表性的問題進行優化應用。

4.1 數學模型

單梁起重機廣泛應用廠礦企業，其主要結構件主梁截面大多采用箱形截面，截面簡圖如圖3，現對跨度L=22.5 m，額定載重為5 T的起重機主梁截面進行優化，目標是使其質量最輕，并滿足主梁的剛度，強度，整體穩定性，局部穩定性以及工藝尺寸等約束[8-11]。優化模型如下:

圖3 起重機主梁截面結構圖Fig.3 The structure figure of girder section

4.2 優化結果分析

為滿足工程需要，最優解應為絕對可行域內的解。初始參數取 c1=c2=1.005，w=0.8，最大迭代次數n=100，群粒子數nd=20.對上述實例進行相關截面尺寸參數的優化設計，計算結果與文獻[7]中提供的結果一并列于表4.

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

表4 優化結果參數對比表Tab.4 Comparison of optimal solutions

5 結論

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

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

(3)主梁結構工程優化設計實例及其工程應用進一步證明了本文方法在求解工程非線性約束優化問題的有效性，且比MATLAB有一定優越性。

[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].北京:科學出版社，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]陶元芳.機械工程軟件技術基礎[M].北京:機械工業出版社，2010.

[6]劉道華，原思聰，蘭洋.混沌映射的粒子群優化方法[J].西安電子科技大學學報，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]李揚，衛良保.基于VC和MATLAB的單梁起重機優化設計.[J].太原科技大學學報，2012，33(1);26-29.

[9]徐格寧.機械裝備金屬結構設計[M].北京:機械工業出版社，2009.

[10]孫靖民，梁迎春.機械優化設計[M].北京:機械工業出版社，2002.

[11]全國起重機械標準化委員會.GB/T3811—2008起重機設計規范[S].北京:中國標準出版社，2008.