高 鴿，孫超利，曾建潮(太原科技大學電子信息工程學院，太原 030024)

隨著科學技術(shù)的不斷發(fā)展，許多實際工程領域的最優(yōu)化問題呈現(xiàn)出越來越復雜的特性，如目標函數(shù)、約束函數(shù)不能用解析式表達，而是通過復雜的仿真進行計算，需要花費大量的計算機時間。近年來，利用隨機搜索算法求解約束優(yōu)化問題得到了更多的重視。隨機搜索算法對函數(shù)的性質(zhì)要求非常低，可以用于一般的復雜工程優(yōu)化問題。微粒群算法是隨機搜索算法的一種，由于它不要求優(yōu)化函數(shù)連續(xù)或可微，采用簡單的速度位移進化模型，需調(diào)整的參數(shù)數(shù)量少，求得解的質(zhì)量高、時間短，因此近年來得到了廣泛的應用[1-4]，并取得了一定的成果。然而，作為群體算法，微粒群算法在獲得最優(yōu)解之前需要進行大量的適應值計算，而對于約束優(yōu)化問題，若約束函數(shù)計算費時，則還需要耗費大量的約束函數(shù)計算時間，因此，微粒群算法不適合于求解計算費時的約束優(yōu)化問題。

據(jù)了解已有較多的學者對適應值計算費時問題展開研究，如崔方舒等[5]將廣義回歸神經(jīng)網(wǎng)絡(GRNN)與PSO算法相結(jié)合，提出了適合求解隨機優(yōu)化問題的智能算法， 通過對預測策略及模型更新策略的分析決定個體的適應值是否用實際的適應值函數(shù)計算，節(jié)省了大量適應值計算時間；針對帶約束的多目標優(yōu)化問題，Hemant Kumar Singh等[6]人將代理模型應用到模擬退火算法中，提出了SASA算法，節(jié)省了實際函數(shù)的計算次數(shù)。Yao等[7]以支持向量機作為代理模型，提出分類輔助微分進化算法，用來判斷哪一個后代個體的適應值需要用實際的適應值函數(shù)計算；Sun等[8]人根據(jù)同一代粒子之間的距離關(guān)系，提出了一種新的適應值預測模型，即某代任意粒子適應值已知，則該進化代中任意其他粒子的適應值就可以通過預測得到；Z.Cui等[9]提出了一種快速PSO算法，不需要計算所有粒子的適應值，只有當可信度低于某個閾值時，才需要實際計算該粒子的適應值；為了避免局部收斂，該作者又采用了一種新的策略，即被估計個體的適應值通過加權(quán)組合來確定，而每一個父代個體的權(quán)重是與周圍被估計的粒子與它本身之間的距離成比例的[10]。

然而，對于約束函數(shù)計算費時問題研究的人并不多。大部分學者針對約束函數(shù)計算費時問題，都是通過罰函數(shù)法將其轉(zhuǎn)換為無約束優(yōu)化問題，然后進行求解。然而，罰因子的選取本身就是一個優(yōu)化問題。Sasena等[11]意識到了上述問題，在有效的全局優(yōu)化算法(EGO)背景下研究了約束處理問題，避免了在不可行域中采樣，間接地減少了約束函數(shù)的計算次數(shù)，在本文中，我們稱這種方法為保持約束可行法。C.K.Goh等[12]人提出了元模型協(xié)同進化算法來處理目標函數(shù)和約束函數(shù)計算費時問題，提高代理模型進化技術(shù)的效率。文獻[13]首先使用罰函數(shù)來處理約束沖突，然后對罰函數(shù)應用代理模型，以解決罰函數(shù)選取難的問題，該方法使用一種連續(xù)的技術(shù)來更新模型，但是模型的質(zhì)量缺理論準確性。文獻[14]針對非線性約束優(yōu)化問題為每個約束函數(shù)建立一個可以提高精度的模型，隨著迭代搜索的進行，模型準確性逐漸提高，可行域會從一個簡單的線性模型逐漸向原真實模型逼近，確保求得的最優(yōu)解時原問題的最優(yōu)解。

文獻[15]提出一種新型向量微粒群算法，該算法定義了一個收縮系數(shù)確保個體任意維上都在約束邊界內(nèi)，同時定義了一個函數(shù)來判斷粒子是否在可行域內(nèi)，整個處理過程都為向量模式。S.He等[16]利用“回飛”策略，直接用上一代個體的位置來替代當前的不可行位置；Sun等分別使用一維搜索[17]和多維搜索[18]的方法為不可行個體在其飛行軌跡或其周圍尋找一個可行位置以替代該不可行個體的位置，但是在找到一個可行位置之前可能需要很多次約束函數(shù)的計算，如果約束函數(shù)計算費時的話無疑是很消耗時間的，顯然很不適用。本文擬將尋找一種簡單有效的約束沖突判斷方法，以替換實際的、費時的約束函數(shù)計算，減少整體優(yōu)化時間，使得微粒群算法能夠適合此類優(yōu)化問題。

由于對于種群中的任何一個個體，均只有可行和不可行兩種可能，因此，針對約束函數(shù)的判斷，構(gòu)造一個基于支持向量機分類器的預測微粒群算法，并與保持約束可行法和一維搜索方法的思想相結(jié)合，用于判斷某一個體的可行性，來替換實際的約束函數(shù)計算，以解決約束函數(shù)計算費時問題的復雜優(yōu)化問題。

1 基本概念

1.1 約束優(yōu)化問題

約束優(yōu)化問題的數(shù)學模型可以表示為：

(1)

若一個變量在可行域內(nèi)，則稱該變量為該約束優(yōu)化問題的一個可行解。

在本文中，將使用一下數(shù)學模型用于約束優(yōu)化問題初始可行解的產(chǎn)生以及約束沖突的判斷：

s.t.ximin≤xi≤ximax,i=1,2,…,n

(2)

其中，δ為容忍度，用于將等式約束轉(zhuǎn)化為兩個不等式約束來處理。

1.2 微粒群算法

1995年，Kennedy和Eberhart等通過對鳥群和魚群群體捕食行為的模擬，提出了一種全局優(yōu)化算法——微粒群算法(PSO)，實現(xiàn)了對優(yōu)化問題的求解[19-22]，自微粒群算法提出以來，不斷的有專家學者對其收斂性能進行修改以適應不同的應用，文獻[23]簡要回顧了微粒群算法的歷史，并強調(diào)其飛行軌跡的隨機穩(wěn)定性的重要性。在該算法中，每一個微粒代表一個候選解，它在D維搜索空間中沒有重量沒有體積卻具有一定飛行速度，并且能根據(jù)自身以及同伴的飛行經(jīng)驗動態(tài)地調(diào)整自己的飛行速度。

對于第i個微粒第t+1代的速度和位置，微粒群算法的進化公式可用公式(3)和(4)表示。

(3)

(4)

其中，ω為慣性權(quán)重，c1和c2分別為認知系數(shù)和社會加速權(quán)重，r1和r2為在[0，1]范圍內(nèi)均勻分布且相互獨立的隨機函數(shù)。

1.3 支持向量機原理

支持向量機是在統(tǒng)計學習理論和結(jié)構(gòu)風險最小原理基礎上發(fā)展而來的新的機器學習算法，從本質(zhì)上看，它避開了從歸納到演繹的傳統(tǒng)過程，實現(xiàn)了高效的從訓練樣本到預測樣本的“轉(zhuǎn)導推理”，大大簡化了分類和回歸等問題。其原理是利用非線性映射將數(shù)據(jù)集映射到高維空間，從而使得低維線性不可分的數(shù)據(jù)在高維空間線性可分。

SVM的目標是對特征空間劃分最優(yōu)超平面，支持向量是它的訓練結(jié)果，在SVM分類決策中起決定作用的就是支持向量，而且只由少數(shù)的支持向量所決定，計算的復雜性取決于支持向量的數(shù)目，而不是樣本空間的維數(shù)。這不但可以幫助我們抓住關(guān)鍵樣本、剔除大量冗余樣本，而且注定了該方法具有較好的魯棒性。這種魯棒性主要體現(xiàn)在：增加或刪除非支持向量對模型沒有影響；支持向量樣本集具有一定的魯棒性。

在樣本線性可分的情況下，將N個樣本的訓練集正確分類的判別函數(shù)形式為：y(x)=ωx+b.不僅能將兩類樣本正確分開，而且使得分類間隔最大的分類面就是最優(yōu)分類面，最優(yōu)分類面上的樣本即為支持向量。

最優(yōu)化問題最初的數(shù)學提法中目標函數(shù)實際上是一個嚴格的凸規(guī)劃。按照最優(yōu)化理論中凸二次規(guī)劃的解法，通常把它轉(zhuǎn)化為Wolfe對偶問題來求解。原最優(yōu)化問題的Wolfe對偶問題，如式(5)所示。

(5)

式(5)的解即為原最優(yōu)化問題的整體最優(yōu)解。解出α后，即能確定最優(yōu)超平面，得到其判別函數(shù)。

利用Wolfe對偶問題，不但能更好地處理問題，而且能使樣本在新問題中僅以向量點積的形式出現(xiàn)看，正是這樣一個重要特點，使支持向量機方法能推廣到非線性情況。

對非線性問題，可以通過非線性變換轉(zhuǎn)化為某個高維空間中的線性問題，在高維特征空間中求最優(yōu)分類面。支持向量機采用的是滿足Mercer條件的核函數(shù)k(xi,xj)=φ(xi)φ(xj)，將樣本變換到高維空間。這時的目標函數(shù)和相應的分類函數(shù)分別為式(6)和式(7)所示。

(6)

(7)

最常用的核函數(shù)[24-25]有線性內(nèi)積函數(shù)、多項式內(nèi)積函數(shù)、 徑向基內(nèi)積函數(shù)[26]和Sigmoid核函數(shù)。

2 基于支持向量機分類方法的微粒群算法(SVMPSO)求解約束計算費時優(yōu)化問題

文獻[27]提出的基于一維搜索約束保持法的微粒群算法(ODCPVPSO)方法，對于每個個體位置都實際計算它的約束沖突值，如果滿足約束條件則計算它的適應值，否則，使用一維搜索的方法尋找滿足約束函數(shù)的新位置，尋找最佳步長因子β，最終使得H(xi(t)+β(xi(t+1)-xi(t)))=0，這樣就為每個逃逸粒子產(chǎn)生了一個新的可行位置。

基于文獻[27]的約束處理機制，利用樣本構(gòu)建一個支持向量機作為判斷約束滿足與否的分類器。加入SVM分類之后，先用SVM對每個粒子進行約束函數(shù)值分類，再對分類在可行域的粒子進行實際計算其約束沖突值，若實際也滿足約束條件，再計算其適應值；否則，若用SVM估計個體不在可行域內(nèi)，則對該逃逸個體使用一維搜索的方法優(yōu)化約束沖突函數(shù)的時候，也采用同樣的過程，具體的流程圖如圖1所示。

從圖1中我們需要注意一點，構(gòu)造支持向量機時為脫機訓練，因此如何選擇樣本集，使得訓練支持向量機時產(chǎn)生的最優(yōu)超平面能更精確地將兩類解分開是關(guān)鍵。

假設支持向量機訓練樣本個數(shù)為N，種群大小為n.

方案一：初始化產(chǎn)生N/2個粒子，將這N/2個粒子約束在不可行域內(nèi)，作為不可行解部分，再產(chǎn)生N/2個粒子，將其約束在可行域內(nèi)，作為可行解部分，二者共同構(gòu)成支持向量機的訓練樣本。再從這N/2個可行解中選取n個作為種群初始化的粒子，進行后續(xù)進化過程。

由此看來，在將粒子約束在不可行域和可行域的過程中，至少要計算N次約束函數(shù)值，浪費了不少時間。于是本文采用另一種樣本產(chǎn)生方法，方案如下。

圖1 SVMPSO算法解決約束優(yōu)化問題流程圖 Fig.1 The training strategy of SVM-assisted PSO

方案二：在初始化產(chǎn)生n個可行解基礎上更新位置，對于每個粒子，計算其約束函數(shù)值，判斷其是否滿足約束沖突，若滿足，則將其放入樣本集的可行解庫中，否則將其放入樣本集的不可行解庫中，同時采用一維搜索的方法，產(chǎn)生相應的可行解放入樣本集的可行解庫中。繼續(xù)進化，進行同樣的操作，直到產(chǎn)生N/2個不可行解為止。其流程圖如圖2所示。

無論是哪一種方法，支持向量機都是針對小樣本數(shù)據(jù)處理問題的，而且問題描述的可行域所占整個搜索空間的比值[27]不同，所以在選擇樣本數(shù)N時，要視情況而定。

3 實驗分析

圖2 樣本產(chǎn)生方案二流程圖

由式(5)解出的拉格朗日乘子α中，只有一部分對確定最優(yōu)超平面起作用，本文選取這一部分的原則是：選擇一個閾值，使大于等于這個閾值的α數(shù)為原α數(shù)的1/3到1/2之間，小于這個閾值的默認為0，不起作用，由這些起作用的α確定所需的支持向量。經(jīng)過實驗驗證，設置閾值使大于等于這個閾值的α數(shù)為原α數(shù)的1/3到1/2之間相對于其它閾值所得的效果好。表1將仿真結(jié)果與ODCPVPSO算法的仿真結(jié)果進行比較。

為了評價SVMPSO算法的有效性，本文將SVM-PSO算法與ODCPVPSO算法中約束函數(shù)值的實際計算次數(shù)進行比較，比較結(jié)果見表2，其中ρ為SVMPSO算法比ODCPVPSO算法中約束函數(shù)值的實際計算次數(shù)減少的百分比。

表1 SVMPSO算法與ODCPVPSO算法的優(yōu)化結(jié)果比較

表2 SVMPSO算法與ODCPVPSO算法中約束函數(shù)值的實際計算次數(shù)比較結(jié)果

從表1整體上可以看出，SVMPSO算法所求出的最優(yōu)解與最差解比偏差不大，較為平穩(wěn)。除了g02和g10之外，SVMPSO均取得了與ODCPVPSO相同或者更好的最優(yōu)解。

從表2可以看出，SVMPSO算法大大減少了約束函數(shù)值的實際計算次數(shù)。

4 總結(jié)

本文通過構(gòu)建支持向量機分類器來判斷PSO算法中的個體是否滿足約束沖突條件，避免復雜的約束計算，縮短了整體優(yōu)化時間。通過最優(yōu)解和約數(shù)函數(shù)實際計算次數(shù)的比較結(jié)果表明SVMPSO算法既保持了算法的性能，同時又大幅度減少了約束函數(shù)的計算量，從而節(jié)省大量時間，達到預期效果。本文算法采用脫機訓練的方式構(gòu)建支持向量機，然而，這種方式會受到樣本數(shù)量、樣本選擇等的限制，由于在微粒群算法進化過程中，會產(chǎn)生大量實際計算的約束函數(shù)值信息，因此，如何利用進化過程中的這些信息，用于更好、更準確的構(gòu)建分類器，將是我們今后的研究方向。

參考文獻：

[1] MOHAMMAD SALEHI MALEH，SOODABEH SOLEYMANI，RAMTIN RASOULI NEZHAD，et al.Using Particle Swarm Optimization Algorithm Based on Multi-Objective Function in Reconfigured System for Optimal Placement of Distributed Generation[J].Journal of Bioinformatics and Intelligent Control，2013，2(2)：119-124.

[2] DERRAR H，AHMED-NACER M，BOUSSAID O.Particle swarm optimisation for data warehouse logical design[J].International Journal of Bio-inspired Computation，2012，4(4)：249-257.

[3] ALI L，SABAT S L，UDGATA S K.Particle swarm optimisation with stochastic ranking for constrained numerical and engineering benchmark problems[J].International Journal of Bio-inspired Computation，2012，4(3)：155-166.

[4] ABDELSALAM H M，MOHAMED A M.Optimal sequencing of design projects′activities using discrete particle swarm optimisation[J].International Journal of Bio-inspired Computation，2012，4(2)：100-110.

[5] 崔方舒，適合于隨機優(yōu)化問題的微粒群算法的研究[D].太原：太原科技大學，2009.

[6] SINGH H K，RAY T，SMITH W.Surrogate Assisted Simulated Annealing(SASA)for Constrained Multi-objective Optimization[C]∥Evolutionary Computation (CEC)，IEEE，2010：1-8.

[7] LU X，TANG K，YAO X.Classification-assisted differential evolution for computationally expensive problems[C]∥Evolutionary Computation (CEC)，IEEE，2011：1986-1993.

[8] SUN C L，ZENG J C，XUE S D，et al.A new fitness estimation strategy for particle swarm optimization[J].Information Sciences，2013，181：355-370.

[9] CUI Z H，ZENG J C，SUN G.A fast particles swarm optimization[J].International Journal of Innovative Computing，Information and Control，2006，2：1365-1380.

[10] CUI Z H，CAI X J，SHI Z Z.Using Fitness Landscape to Improve the Performance of Particle Swarm Optimization[J].Journal of Computational and Theoretical Nanoscience，2012，9(2)：258-266.

[11] SASENA M J，PAPALAMBROS P，GOOVAERTS P.Exploration of Metamodeling Sampling Criteria for Constrained Global Optimization[J].Engineering Optimization，2002，34：263-278.

[12] GOH C K，LIM D.A surrogate-assisted memetic co-evolutionary algorithm for expensive constrained optimization problems[C]∥ Evolutionary Computation (CEC)， IEEE，2011：744-749.

[13] RUNARSSON T P.Constrained evolutionary optimization by approximate ranking and surrogate models [C]∥ Parallel Problem Solving from Nature-PPSN Ⅷ，2004：401-410.

[14] JIN Y，OH S，JEON M.Incremental approximation of nonlinear constraint functions for evolutionary constrained optimization[C]∥Evolutionary Computation (CEC)，IEEE，2010：1-8.

[15] SUN C L，ZENG J C，PAN J S.A New Vector Particle Swarm Optimization for Constrained Optimization Problems[C]∥International Joint Conference on Computational Sciences and Optimization， 2009：485-488.

[16] HE S，PREMPAIN E，WU Q H.An improved particle swarm optimizer for mechanical design optimization problems[J].Engineering Optimization，2004，36：585-605.

[17] SUN C L，ZENG J C，PAN J S.A New Vector Particle Swarm Optimization for Constrained Optimization Problems[C]∥Computational Sciences and Optimization，2009：485-488.

[18] SUN C L，ZENG J C，PAN J S.An improved vector particle swarm optimization for constrained optimization problems[J].Information Sciences，2011，181：1153-1163.

[19] JIANG M S.Analysis in particle swarm optimization[C]∥swarm intelligence symposium，2007：92-99.

[20] YE G Q，SUN S Y.Particle swarm optimization based on dynamic population size [J].Information and Control，2008，37：18-27.

[21] LIU H B，WANG X K，TAN G J.Convergence analysis of particle swarm optimization and improvement of chaotic[J].Control and Decision，2006，21：636-640.

[22] GUANG Q L，ZHAO F Q.Parallel hybrid PSO-GA algorithm and its application to layout design[J].Structural and Multidisciplinary Optimization，2006，33：749-758.

[24] 李海生，支持向量機回歸算法與應用研究[D].廣州：華南理工大學，2005.

[25] 祝紅梅，支持向量機核參數(shù)選擇及其應用[D].西安：西安科技大學，2007.

[26] FATTAHI H，F(xiàn)ARSANGI M A E，SHOJAEE S，et al.Application of the hybrid harmony search with support vector machine for identification and classification of damaged zone around underground spaces[J].International journal of optimization in civil engineering，2013，3：345-358.

[27] 孫超利，面向機械化設計的微粒群算法理論及其應用研究[D].太原：太原科技大學，2010.

[28] THOMAS P R，XIN Y.Stochastic Ranking for Constrained Evolutionary Optimization[J].Evolutionary computation，2000，4：284-294.