羅金炎

(閩江學院數(shù)學系，福建福州 350108)

一種求解非線性約束優(yōu)化問題的粒子群優(yōu)化算法

羅金炎

(閩江學院數(shù)學系，福建福州 350108)

提出一種新的基于粒子群優(yōu)化算法求解非線性約束優(yōu)化問題的方法.通過引入自適應的退火罰因子和不可微精確罰函數(shù)來處理約束條件，可以使算法逐漸搜索到可行的極值點.數(shù)值實驗證明了算法是有效的.

約束優(yōu)化；模擬退火；精確罰函數(shù)法；粒子群優(yōu)化算法

在實際工程和科學研究中，約束優(yōu)化問題，尤其是非線性約束優(yōu)化問題是一類廣泛存在但又較難求解的問題，目前，此類問題的求解方法還不很成熟，仍在不斷發(fā)展完善中.早期對非線性約束優(yōu)化問題的求解是通過罰函數(shù)法將其轉(zhuǎn)化為無約束問題來求解的，近期提出的逐次二次規(guī)劃法（SQP）、逐次線性規(guī)劃法（SLP）以及廣義簡約梯度法（GRG），已經(jīng)脫離了對無約束優(yōu)化方法的依賴，是目前求解非線性約束最優(yōu)化問題較為有效的方法.但以上這些方法都是基于梯度尋優(yōu)的方法提出的，對目標函數(shù)和約束條件有連續(xù)、可微的要求，且這些方法僅能求得局部極值點.

粒子群算法（PSO）是Kennedy和Eberhart于1995年提出的一種進化算法①Kennedy J, Eberhart R C. Particle swarm optimization [C]// Proceedings-IEEE International Conference on Neural Networks. 1995: 1942-1948.，它源于對簡化社會模型的模擬，與其它進化算法相比，其思想簡單，采用群體的速度——位移搜索模型容易實現(xiàn)，避免了復雜的進化操作.粒子群算法無需優(yōu)化問題有連續(xù)性和可微性，只要求被優(yōu)化的問題是可計算的，同時粒子群算法是基于群體進化的算法，且能收斂到全局最優(yōu)解，因此克服了傳統(tǒng)的基于梯度優(yōu)化方法的一些缺點.目前，粒子群算法已被廣泛應用于各種優(yōu)化問題求解中，如調(diào)度問題、組合優(yōu)化等問題.本文提出一種求解非線性約束優(yōu)化問題的粒子群優(yōu)化算法，并通過數(shù)值實驗證明了算法的有效性.

1 基于粒子群算法的非線性約束優(yōu)化方法

實際工程中的許多優(yōu)化問題，最終都可化為非線性約束優(yōu)化問題的求解，通?？擅枋鰹橄铝行问剑?/p>

其中，n x∈R，f(x)是被優(yōu)化的目標函數(shù)，m是等式約束個數(shù)，n是不等式約束個數(shù).

粒子群算法與其它進化類算法相似，采用“群體”與“進化”的概念，同時依據(jù)個體（粒子）的適應值的大小進行操作，但粒子群算法不像其它進化算法那樣對于個體使用進化算子，而是將每個個體看作是在搜索空間中的一個沒有重量和體積的粒子，并在搜索空間中以一定的速度飛行，每個粒子的飛行速度根據(jù)其本身的飛行經(jīng)驗和群體的飛行經(jīng)驗調(diào)整.粒子群算法根據(jù)下列公式進行解的迭代更新：

其中，w為慣性權重，rand()為均勻分布在(0,1)之間的隨機數(shù)，c1和c2為學習因子.粒子的速度vi被最大速度Vmax限制，即若vi>Vmax，則令vi=Vmax，若vi

粒子群算法求解約束優(yōu)化問題的難點是約束條件的處理.文獻[1]采用分離目標函數(shù)與約束條件的方法，將約束條件轉(zhuǎn)化為調(diào)節(jié)函數(shù)和目標函數(shù)一起作為粒子的適應函數(shù)，每個粒子的優(yōu)劣由這兩個函數(shù)值按一定比較準則共同決定，但其中比較準則的確定有一定的難度.Parsopoulos等人在文獻[2]中將約束優(yōu)化問題轉(zhuǎn)化為minmax問題，并采用粒子群算法進行求解，取得了滿意的結(jié)果，但存在系數(shù)的選擇問題.文獻[3]引入半可行域的概念，提出了競爭選擇的新規(guī)則，并對適應度函數(shù)進行改進，結(jié)合粒子群算法本身的特點，設計了選擇算子，從而得到一個求解約束優(yōu)化問題的新的進化算法.文獻[4]將原約束函數(shù)作為以歐拉數(shù)為底的指數(shù)函數(shù)的指數(shù)變量重新構(gòu)造一個輔助函數(shù)作為約束函數(shù)，采取約束函數(shù)的滿足優(yōu)先于目標函數(shù)的尋優(yōu)，該方法雖然對約束優(yōu)化問題的約束條件滿足取得一定效果，但目標函數(shù)的優(yōu)化效果并不明顯.以上方法或多或少都與所要解決的問題有關，罰函數(shù)法則可以克服這種缺陷，它通過對不可行解施加某種懲罰，經(jīng)過不斷迭代后，使解群逐漸收斂于可行的極值點.采用一般的罰函數(shù)法[5]或動態(tài)罰函數(shù)法[6]來處理約束問題，計算過程需要求解一系列無約束極小問題，工作量較大，并且罰因子的選取也有一定難度，取得很大時可能陷入病態(tài)，取得過小又可能使算法的收斂性能很差.本文采用不可微精確罰函數(shù)法，不需要求解一系列無約束極小問題，采用自適應的退火罰因子可以防止罰因子取得過大或過小.通過調(diào)整自適應的退火罰因子，結(jié)合不可微精確罰函數(shù)來處理約束條件，最終可使算法逐漸收斂于有可行域的極值點，從而實現(xiàn)非線性約束優(yōu)化問題的求解.

2 基于粒子群算法的退火罰函數(shù)優(yōu)化算法

2.1 懲罰函數(shù)法

懲罰函數(shù)法最早是在最優(yōu)化問題中用來處理非線性約束優(yōu)化的一種方法，它通過對約束條件施加懲罰函數(shù)而使有約束問題變?yōu)闊o約束優(yōu)化問題，從而利用成熟的無約束優(yōu)化方法求解.對于式（1）的求解可以化為下列無約束問題的求解：

其中，P(σk,x)是懲罰函數(shù)，σk是懲罰因子.針對不同的懲罰函數(shù)，形成了不同的方法，主要有外罰函數(shù)法、內(nèi)罰函數(shù)法、乘子法和精確罰函數(shù)法.外罰函數(shù)法和內(nèi)罰函數(shù)法容易引起求解問題的病態(tài)問題，這是由它們需要罰因子無限增大而引起的.乘子法通過在罰函數(shù)中引入拉格朗日乘子λ，使得罰因子kσ可取某個有限值，因而解決了早期外罰函數(shù)和內(nèi)罰函數(shù)法中出現(xiàn)的病態(tài)問題，但它需要解決一系列無約束極小值問題來逼近最優(yōu)乘子和最優(yōu)解.精確罰函數(shù)法有不可微精確罰函數(shù)和可微精確罰函數(shù)兩種形式.不可微精確罰函數(shù)法的主要缺點是它在約束邊界不可微，因此不能采用無約束優(yōu)化中有效的梯度法.可微精確罰函數(shù)法雖可以利用梯度型算法來求解，但要利用這些函數(shù)的二階導數(shù)，從而大大增加了無約束極小化過程的工作量.

2.2 基于粒子群算法的退火精確罰函數(shù)法

用粒子群優(yōu)化算法求解約束優(yōu)化問題，基本上采用罰函數(shù)的二次型形式，即：

但是，這種處理方法在某些非線性優(yōu)化問題中的求解性能并不好.

為了改變上述方法的缺陷，本文采用一種模擬退火不可微精確罰函數(shù)法[7]，即罰函數(shù)的選取為如下形式：

罰因子kσ吸取了模擬退火的思想，使T逐漸下降，即kσ逐漸增大，其增加速度由溫度冷卻參數(shù)α來控制.隨著進化的不斷進行，kσ逐漸增大，使得解群趨于可行解.罰函數(shù)的形式采用了不可微精確罰函數(shù).由于粒子群算法對問題的可微性沒有限制，因此克服了基于梯度型算法不能處理不可微函數(shù)的缺陷，從而能夠有效地求得可行的極值點.

3 算 例

選取如下測試函數(shù)測試本文提出的算法，根據(jù)它們的目標函數(shù)值和滿足的約束條件來進行綜合評價.

算法的參數(shù)：慣性權重ω從0.9線性遞減到0.4，學習因子參數(shù)為C1 =C2 = 1.48，溫度冷卻參數(shù)為α= 0.928.

算例1 測試函數(shù)為：

群體規(guī)模為100，個體最大速率vmax= 9.12，對該問題進行10次獨立實驗取平均值，并同其它算法的結(jié)果進行比較.求解結(jié)果如表1所示.由表1可知，用本文提出的方法（退火精確罰函數(shù)法）求解的結(jié)果，無論是所求得的目標函數(shù)值還是最終所滿足的約束精度效果都是比較好的，雖然所求的目標函數(shù)值不如退火二次型罰函數(shù)法，但是它滿足的約束精度比退火二次型罰函數(shù)法要好得多，在許多實際的優(yōu)化問題中，對可行解的要求（即對約束的滿足）是極為關鍵的.

表1 算例1的數(shù)值結(jié)果比較

算例2 測試函數(shù)為：

群體規(guī)模為100，個體最大速率vmax= 16.0，求解結(jié)果如表2所示.由表2可知，本文算法在約束條件的滿足和目標的尋優(yōu)方面，比一般的粒子群算法的效率都好，在目標的尋優(yōu)上比文獻[6]中改進的粒子群算法的效率要好.

表2 算例2的數(shù)值結(jié)果比較

4 結(jié) 論

粒子群算法不要求所求解問題的連續(xù)可微性，因此可以利用基于梯度法不能求解的不可微精確罰函數(shù)法來解決非線性約束優(yōu)化問題.仿真結(jié)果表明，該算法對約束條件的滿足和目標尋優(yōu)的效果都是比較好的.

[1]劉華鎣, 林玉娥, 王淑云, 等. 粒子群算法的改進及其在求解約束優(yōu)化問題中的應用[J]. 吉林大學學報: 理學版, 2005, 43(4): 472-476.

[2]Parsopoulos K E, Vrahatis M N. Recent Approaches to Global Optimization Problems through Particle Swarm Optimization [J]. Natural Computing, 2002, (1): 235-306.

[3]張利彪, 周春光, 劉小華, 等. 求解約束優(yōu)化問題的一種新的進化算法[J]. 吉林大學學報: 理學版, 2004, 42(4): 534-560.

[4]Vaz A I F. Optimization of Nonlinear Constrained Particle Swarm [J]. Technological and Economic Development of Economy, 2006, 12(1): 30-36.

[5]張喆, 李燕. 混合微粒群算法在非線性約束優(yōu)化中的應用[J]. 計算機應用與軟件, 2004, 21(8): 114-118.

[6]張寶菊, 單國全, 齊名軍, 等. 求解非線性約束優(yōu)化問題改進的粒子群算法[J]. 天津師范大學學報: 自然科學版, 2006, 26(2): 73-76.

Particle Swarm Optimization to Nonlinear Constrained Optimization Problem

LUO Jinyan
(Department of Mathematics, Minjiang University, Fuzhou, China 350108)

A new optimal method based on particle swarm optimization (PSO) to nonlinear constrained optimization problem was presented in this paper. By adopting adaptive annealing penalty factors and non-differentiable accuracy penalty function to deal with the constraints, the method could help the PSO to gradually achieve optimal extreme point. Numerical experiments demonstrated the effectiveness of the PSO.

Constrained Optimization; Simulated Annealing; Accuracy Penalty Function; Particle Swarm Optimization

(編輯：王一芳)

O224

A

1674-3563(2012)01-0001-05

10.3875/j.issn.1674-3563.2012.01.001 本文的PDF文件可以從xuebao.wzu.edu.cn獲得

2011-05-18

福建省自然科學基金項目(2009J05011)；閩江學院科技啟動項目(YKQ09001)

羅金炎(1975- )，男，福建上杭人，副教授，碩士，研究方向：計算數(shù)學，智能優(yōu)化算法