羅金炎

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

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

羅金炎

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

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

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

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

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

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

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

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

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

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

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

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

2.1 懲罰函數(shù)法

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

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

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

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

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

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

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

3 算 例

選取如下測(cè)試函數(shù)測(cè)試本文提出的算法，根據(jù)它們的目標(biāo)函數(shù)值和滿(mǎn)足的約束條件來(lái)進(jìn)行綜合評(píng)價(jià).

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

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

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

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

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

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

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

4 結(jié) 論

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

[1]劉華鎣, 林玉娥, 王淑云, 等. 粒子群算法的改進(jìn)及其在求解約束優(yōu)化問(wèn)題中的應(yīng)用[J]. 吉林大學(xué)學(xué)報(bào): 理學(xué)版, 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)化問(wèn)題的一種新的進(jìn)化算法[J]. 吉林大學(xué)學(xué)報(bào): 理學(xué)版, 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)化中的應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2004, 21(8): 114-118.

[6]張寶菊, 單國(guó)全, 齊名軍, 等. 求解非線性約束優(yōu)化問(wèn)題改進(jìn)的粒子群算法[J]. 天津師范大學(xué)學(xué)報(bào): 自然科學(xué)版, 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

福建省自然科學(xué)基金項(xiàng)目(2009J05011)；閩江學(xué)院科技啟動(dòng)項(xiàng)目(YKQ09001)

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