胡秀云,齊泓深，劉道華

(1.信陽學(xué)院 數(shù)學(xué)與信息學(xué)院,河南 信陽464000；2. 鄭州大學(xué) 管理工程學(xué)院,河南 鄭州 450001；3.信陽師范學(xué)院 計(jì)算機(jī)與信息技術(shù)學(xué)院,河南 信陽464000)

0 引言

“無免費(fèi)午餐定理”告誡人們，沒有哪一種智能優(yōu)化算法能適合求解所有的優(yōu)化模型，故人們總是設(shè)計(jì)或改進(jìn)各種智能算法，對所求優(yōu)化問題獲得較高的優(yōu)化解質(zhì)量[1].傳統(tǒng)的PSO算法因具有參數(shù)設(shè)置少、算法設(shè)計(jì)簡單、獲得全局解的能力強(qiáng)等優(yōu)點(diǎn)，現(xiàn)已廣泛地應(yīng)用于各種優(yōu)化問題求解[2].但傳統(tǒng)的PSO算法的慣性權(quán)重大都采用線性調(diào)整方式，而不能充分利用粒子在整個搜索過程中尋優(yōu)信息來自適應(yīng)地更改該參數(shù).同時，對于各種復(fù)雜帶約束的優(yōu)化類問題，因設(shè)計(jì)變量多導(dǎo)致所賦予的粒子自身維數(shù)增加，粒子在尋優(yōu)過程中對粒子位置及速度信息的計(jì)算量增大，優(yōu)化過程中適應(yīng)度.評價(jià)函數(shù)的計(jì)算量也隨之增大.

因此，采用不同的方式在不影響優(yōu)化結(jié)果的前提下，降低設(shè)計(jì)變量個數(shù)將大大降低計(jì)算量.文獻(xiàn)[3]采用變量的灰關(guān)聯(lián)分析方法對優(yōu)化變量進(jìn)行排序，從而刪減部分設(shè)計(jì)變量.文獻(xiàn)[4]采用靈敏度分析方法，分析變量的微小變化對因變量的影響程度，從而刪減部分對因變量影響較小的設(shè)計(jì)變量.但這些方法均在提高優(yōu)化求解效率之時，而降低了優(yōu)化解的精度.

在復(fù)雜不等式約束處理中，許多文獻(xiàn)采用包絡(luò)函數(shù)法，將不等式約束包絡(luò)在一個不等式約束函數(shù)內(nèi)，然后采用罰函數(shù)法，將不等式約束問題轉(zhuǎn)化成無約束優(yōu)化問題[5].也有文獻(xiàn)采用可行規(guī)則法、多目標(biāo)概念處理法以及隨機(jī)排序法等，并且都取得了很好的應(yīng)用效果[6].但這些方法大都是算法尋優(yōu)操作后來判斷所求解是否在解的可行空間內(nèi)，從而降低了解的求解效率.

基于此，本文將揭示等式約束中所包含的隱含變量關(guān)系，從而將那些被其他變量表達(dá)的變量約簡掉，降低了優(yōu)化變量數(shù)的同時，并沒有降低優(yōu)化解的精度.其次將所有不等式約束(包括將等式約束轉(zhuǎn)化成不等式約束)均放在一種子程序內(nèi)，在算法計(jì)算適應(yīng)度評價(jià)函數(shù)值之前，進(jìn)行子程序調(diào)用，以排除尋優(yōu)之中不在解空間內(nèi)的變量值，從而大大提高了優(yōu)化求解效率.最后，通過典型函數(shù)測試驗(yàn)證可知，這種帶權(quán)PSO算法對約束條件同時處理的方法既能提高解的精度，又能提高優(yōu)化的求解效率.

1 約束優(yōu)化類問題

1.1 等式約束及優(yōu)化變量約簡策略

對于一般的優(yōu)化問題，其常規(guī)的表達(dá)形式為

minf(x),

(1)

s.t.

gi(x)≤0,i=1,2,…,p；

(2)

hj(x)=0,j=1,2,…,m；

(3)

lk≤xk≤uk.

(4)

式中：x=(x1,x2,…,xn);p表示不等式約束的個數(shù);m是等式約束的個數(shù).

設(shè)集合Ω內(nèi)含有所有約束優(yōu)化變量，即Ω={xk|k=1,2,…,n}，集合Ωj內(nèi)含有所有等式約束變量[7].故Ωj?Ω.在式(3)、式(4)中，假如找到式(5)的關(guān)系式.

xk=Rk,j({xll∈Ωj,l≠k}),

(5)

即xk的值可以被Rk,j及{xll∈Ωj,l≠k}中的相關(guān)變量計(jì)算得出.此時，式(3)中的變量xk即被約簡了，但式(3)仍成立.整個約束優(yōu)化中的等式約束式(3)將被轉(zhuǎn)化成變量間的不等式約束式(6)的形式.

lk≤Rk,j({xll∈Ωj,l≠k})≤uk.

(6)

這對整個約束優(yōu)化問題來說，既能使嚴(yán)格的等式約束變成了具有一定可行域內(nèi)的不等式約束，同時還減少了整個優(yōu)化的求解變量數(shù)，從而使各種智能優(yōu)化算法縮減了代碼長度或優(yōu)化的維度，使優(yōu)化效率大大提高.

1.2 不等式約束處理策略

2 帶權(quán)的PSO算法

2.1 權(quán)值的確定方法

在傳統(tǒng)的PSO算法中，設(shè)搜索空間的維數(shù)為D，粒子群個體規(guī)模為s，則第i個粒子的當(dāng)前位置狀態(tài)為xi=(x1,x2,…,xD)T，第i個粒子的當(dāng)前速度為vi=(v1,v2,…,vD)T，第i個粒子的當(dāng)前搜索到最優(yōu)位置為pi=(pi1,pi2,…,piD)T，i=1,2,…,s.若整個種群搜索到的最優(yōu)位置的對應(yīng)粒子下標(biāo)為g，則PSO中各粒子的速度位置更新方程為：

vi,d(t+1)=ωvi,d(t)+c1r1(pi,d(t)-xi,d(t))+

c2r2(pg,d(t)-xi,d(t)),

(7)

xi,d(t+1)=xi,d(t)+vi,d(t+1),

(8)

其中：t為當(dāng)前迭代次數(shù)，t=1,2,…,max_gen；d表示維度，d=1,2,…,D；c1、c2分別為個體認(rèn)知因子和社會認(rèn)知因子，但在一般情況下，c1=c2=2；r1、r2為隨機(jī)數(shù)，獨(dú)立服從區(qū)間(0，1)上均勻分布；ω為慣性權(quán)值[8].從式(7)、式(8)中可以看出，傳統(tǒng)的粒子群算法主要有3個參數(shù)，即慣性權(quán)重參數(shù)ω和加速因子參數(shù)c1和c2.許多學(xué)者都提出ω的值應(yīng)該在算法搜索迭代過程中線性下降.

ω=ωmax-(ωmax-ωmin)g/G，

(9)

其中:g是算法的當(dāng)前迭代次數(shù)，G是最大迭代次數(shù)，ωmax和ωmin一般設(shè)為0.9和0.4.

這種傳統(tǒng)的慣性權(quán)重參數(shù)調(diào)整方法，不能很好地利用其他粒子在搜索過程中的信息.基于此，對于式(7)中ω將采用如下操作方式獲得.

假定有n個粒子，經(jīng)過m次迭代后，每個粒子獲得的優(yōu)化解設(shè)為Aj，其中j∈{1,2,…,m}，則n個粒子經(jīng)過m次迭代后所構(gòu)建的最優(yōu)解矩陣D為：

(10)

利用下式將全局最優(yōu)解D規(guī)范化后得：

(11)

(12)

(13)

(14)

此時，PSO在優(yōu)化過程中，式(7)中ω采用式(14)代替，這樣就能實(shí)現(xiàn)任何一粒子在優(yōu)化過程中，既能利用當(dāng)前粒子所迭代每一步的解信息，還能充分利用其他粒子迭代時的歷史解信息.

2.2 帶權(quán)的PSO算法求解帶約束類問題的步驟

步驟1 依據(jù)式(5)將優(yōu)化問題的等式約束條件變成式(6)的不等式約束形式，構(gòu)建出新的所有不等式約束，同時找出簡約變量.

步驟2 初始化，依據(jù)被優(yōu)化問題的難易程度選擇初始群體的規(guī)模s、最大迭代次數(shù)max_gen、迭代次數(shù)計(jì)數(shù)器t、ωmax、ωmin，依據(jù)約束后變量的個數(shù)，確定初始粒子的維數(shù).初始化粒子群，即隨機(jī)設(shè)定各粒子的初始位置x和初始速度v.

步驟3 處理不等式約束，構(gòu)建不等式約束子程序，確定子程序的形式參數(shù)及子程序的返回變量.

步驟4 判斷當(dāng)前粒子所代表的解信息是否在整個優(yōu)化解可行域空間內(nèi)，將當(dāng)前所有粒子所代表的解信息代入步驟3所確定的不等式約束子程序內(nèi).如條件為真，則轉(zhuǎn)步驟5.否則,將以前一次優(yōu)化步中獲得的解作為當(dāng)前粒子的最優(yōu)解.對于初始的隨機(jī)賦值，如不滿足條件，則對不滿足條件的粒子重新賦值，轉(zhuǎn)步驟5.

步驟5 計(jì)算所有粒子的適應(yīng)度評價(jià)函數(shù)值.

步驟6 對所有粒子，比較它的適應(yīng)度值和它自身經(jīng)歷過的最好位置pi,d的適應(yīng)度值，如果優(yōu)于先前最優(yōu)值，則用此時計(jì)算值替換原pi,d值.

步驟7 對所有粒子，比較它的適應(yīng)度值和該群體經(jīng)歷過的最好位置pg,d的適應(yīng)度值，如果優(yōu)于先前最優(yōu)值，則用此時計(jì)算值替換原pg,d值.

步驟8 計(jì)算公式(10)—(14)，然后計(jì)算式(7)及式(8)，以調(diào)整各粒子的位置及速度信息.

步驟9 判斷是否達(dá)到最大迭代次數(shù)，如滿足，退出循環(huán);否則轉(zhuǎn)步驟4.

3 實(shí)例及實(shí)例分析

為了驗(yàn)證帶權(quán)PSO算法求解約束優(yōu)化問題求解方法的有效性，尤其是驗(yàn)證這種將等式約束變成不等式約束，既降低了優(yōu)化求解變量數(shù)，還提高了優(yōu)化效率.采用兩個典型的優(yōu)化實(shí)例加以驗(yàn)證.

實(shí)例1 優(yōu)化函數(shù)形式為

(15)

依據(jù)1.1節(jié)的內(nèi)容，將式(15)中的等式約束變成如下等式關(guān)系：

16x1/35,

x3=(56-8x1-14x2)/7,

從而將式(15)中等式約束變成不等式約束的形式：

16x1/35≤10,

0≤(56-8x1-14x2)/7≤10.

同時使整個優(yōu)化的目標(biāo)函數(shù)有3變量轉(zhuǎn)化成單變量優(yōu)化求解.

實(shí)例2 優(yōu)化的函數(shù)形式為

minf(x)=-9x5-15x8+6x1+

16x2+10(x6+x7),

s.t.

x9x3+0.02x6-0.025x5≤0,

x9x4+0.02x7-0.015x8≤0,

x1+x2-x3-x4=0,

0.03x1+0.01x2-x9(x3+x4)=0,

x3+x6-x5=0;x4+x7-x8=0,

0≤x1,x2,x6≤300 ;0≤x3,x5,x7≤1000;

0≤x4,x8≤200;0.01≤x9≤0.09.

(16)

由式(16)中的等式關(guān)系，轉(zhuǎn)化成不等式關(guān)系：

0≤x5-x6≤1000；

0≤x8-x7≤200；

0≤0.5(3-100x9)(x3+x4)≤300.

同時使原約束優(yōu)化問題中的變量x1、x2、x3以及x4被約減.

上述2個代表性的有約束優(yōu)化的測試函數(shù)，用本文改進(jìn)的帶權(quán)PSO方法分別對所優(yōu)化問題的等式約束轉(zhuǎn)化成不等式約束(EC-IPSO)、不等式約束處理策略(IC-IPSO)以及兩者都處理的策略(ECIC-IPSO)，以及采用傳統(tǒng)的PSO方法分別對所優(yōu)化問題的等式約束轉(zhuǎn)化成不等式約束(EC-PSO)、不等式約束處理策略(IC-PSO)以及兩者都處理的策略(ECIC-PSO)作求解性能對比.

在實(shí)驗(yàn)過程中，采用Intel(R) Core(TM) i3-2120 CPU,@3.30 GHz，并在MATLAB R2008a編程環(huán)境下進(jìn)行求解驗(yàn)證.每個函數(shù)采用每種方法獨(dú)立運(yùn)行50次，統(tǒng)計(jì)每個函數(shù)的最優(yōu)值(Best)、平均值(Mean)、標(biāo)準(zhǔn)差(Std)、平均優(yōu)化時間(Time(s)).對于傳統(tǒng)的PSO方法，其算法參數(shù)設(shè)置為：個體規(guī)模為s=100，最大迭代數(shù)G=3000，個體認(rèn)知因子和社會認(rèn)知因子c1=c2=2，慣性權(quán)重ω依據(jù)式(9)計(jì)算，ωmax和ωmin分別為0.9和0.4.對于本文方法，其參數(shù)設(shè)置為：個體規(guī)模為s=100，最大迭代數(shù)max_gen=3000，個體認(rèn)知因子和社會認(rèn)知因子c1=c2=2，實(shí)驗(yàn)結(jié)果如表1所示.

從表1中對比數(shù)據(jù)可以看出，采用EC-IPSO方法、ECIC-IPSO、IC-IPSO、EC-PSO、IC-PSO以及ECIC-PSO方法對于實(shí)例1獲得的最好解、均值以及方差均相同，只是在優(yōu)化時間上IC-IPSO以及ECIC-IPSO遠(yuǎn)少于EC-IPSO，對于IC-PSO以及ECIC-PSO優(yōu)化時間也遠(yuǎn)少于EC-PSO.由于該實(shí)例采用等式約束轉(zhuǎn)化成不等式約束，約減了3個優(yōu)化變量，最終使得目標(biāo)函數(shù)成為單變量優(yōu)化求解，故求解精度一致，但采用不同的優(yōu)化方法，其優(yōu)化時間差別比較大.從實(shí)例2的求解指標(biāo)對比來看，在解的精度上，采用EC-PSO、IC-PSO、ECIC-PSO、EC-IPSO、IC-IPSO以及ECIC-IPSO所獲得的解的精度依次提高，優(yōu)化時所需優(yōu)化時間的對比上，采用ECIC-IPSO是最少的，且基本上少于其他方法所用時間在一個數(shù)量級以上.

圖1及圖2分別給出了兩個實(shí)例分別采用上述6種方法的優(yōu)化求解過程.從圖1及圖2中也可清楚地看出，采用ECIC-IPSO方法所需迭代次數(shù)最小，所獲解的精度也最高.

表1 優(yōu)化結(jié)果對比表Tab. 1 Comparison of optimization results

圖1 實(shí)例1的優(yōu)化求解過程圖 圖2 實(shí)例2的優(yōu)化求解過程圖 Fig. 1 Optimization solution process for example 1 Fig. 2 Optimization solution process for example 2

4 結(jié)語

(1)本文方法能夠充分利用PSO優(yōu)化過程中其他粒子信息自適應(yīng)改變慣性權(quán)重，從而能提高PSO算法的求解性能；(2)能夠?qū)?yōu)化問題中對解要求非?？量痰牡仁郊s束轉(zhuǎn)化成不等式約束，降低了優(yōu)化變量的個數(shù)，簡化了優(yōu)化的目標(biāo)函數(shù)，從而提高了優(yōu)化求解效率；(3)將優(yōu)化問題的不等式約束事先放于子程序內(nèi)，在計(jì)算每一粒子的適應(yīng)度評價(jià)函數(shù)值之前進(jìn)行不可行解的排除，從而能提高優(yōu)化求解效率.