約束函數(shù)估值策略輔助的微粒群算法

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

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

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

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

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

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

1 基本概念

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

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

(1)

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

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

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

(2)

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

1.2 微粒群算法

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

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

(3)

(4)

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

1.3 支持向量機(jī)原理

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

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

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

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

(5)

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

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

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

(6)

(7)

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

2 基于支持向量機(jī)分類方法的微粒群算法(SVMPSO)求解約束計(jì)算費(fèi)時(shí)優(yōu)化問(wèn)題

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

4 總結(jié)

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

參考文獻(xiàn)：

[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] 崔方舒，適合于隨機(jī)優(yōu)化問(wèn)題的微粒群算法的研究[D].太原：太原科技大學(xué)，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] 李海生，支持向量機(jī)回歸算法與應(yīng)用研究[D].廣州：華南理工大學(xué)，2005.

[25] 祝紅梅，支持向量機(jī)核參數(shù)選擇及其應(yīng)用[D].西安：西安科技大學(xué)，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] 孫超利，面向機(jī)械化設(shè)計(jì)的微粒群算法理論及其應(yīng)用研究[D].太原：太原科技大學(xué)，2010.

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