基于單純形法的多目標(biāo)優(yōu)化復(fù)合算法

薛貴文， 張茂軍

(桂林電子科技大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院，廣西 桂林 541004)

多目標(biāo)優(yōu)化是多目標(biāo)決策的一個領(lǐng)域，涉及多個目標(biāo)函數(shù)的數(shù)學(xué)優(yōu)化問題，需要同時進行優(yōu)化。多目標(biāo)優(yōu)化已應(yīng)用于工程、經(jīng)濟和物流等許多科學(xué)領(lǐng)域。在2個或更多相互沖突的目標(biāo)之間出現(xiàn)權(quán)衡時，通常需要做出最佳決策。自20世紀(jì)60年代早期以來，多目標(biāo)優(yōu)化問題(multi-objective optimization problem，簡稱MOP)吸引了越來越多不同背景研究人員的注意力。在實際應(yīng)用中，各個子目標(biāo)之間并非完全統(tǒng)一，其中一個子目標(biāo)因素的改變會影響到其他子目標(biāo)的性能，無法使每個子目標(biāo)的值都達到極值。一般處理此類問題的方法是折中處理，盡量使得各個子目標(biāo)最優(yōu)化。Chinchluluun等[1]探討了多目標(biāo)優(yōu)化的發(fā)展進程，包括最優(yōu)性條件、應(yīng)用程序、全局優(yōu)化技術(shù)等。對于無約束優(yōu)化問題，已有的研究重點是最速下降法和牛頓法。Mita等[2]提出了一種新的非單調(diào)線搜索，可在迭代中增加目標(biāo)函數(shù)值，以避免初始目標(biāo)函數(shù)在迭代中減小。Fliege等[3]對牛頓法進行了擴展，Kim等[4]改進了雙目標(biāo)優(yōu)化中的Pareto前沿，可以系統(tǒng)地改變目標(biāo)函數(shù)之間的權(quán)重，從而尋找Pareto最優(yōu)解。Luc等[5]對向量優(yōu)化問題的標(biāo)量分別通過構(gòu)造線性函數(shù)和凸性函數(shù)來表示，通過求解關(guān)鍵標(biāo)量得到向量問題的最優(yōu)解。

在多目標(biāo)優(yōu)化問題中，當(dāng)采取線性加權(quán)法對目標(biāo)函數(shù)進行優(yōu)化時，所用的權(quán)重大多為主觀判斷值，當(dāng)人為干預(yù)到權(quán)重選取時，會影響到最優(yōu)解的精確性。張華軍等[6]提出一種約束優(yōu)化方法，可獲取一個目標(biāo)的最優(yōu)權(quán)重，同時利用遺傳算法和投影梯度法，可在權(quán)重的選取中滿足個人偏好。Marler等[7]通過Pareto最優(yōu)集和目標(biāo)函數(shù)值驗證了最小化加權(quán)求和的方法是否適用于個人偏好。Zitzler等[8]選取6個測試函數(shù)，對幾種常見的目標(biāo)優(yōu)化方法進行了比較，發(fā)現(xiàn)當(dāng)收斂到Pareto最優(yōu)前沿時，各個方法的復(fù)雜程度會有明顯區(qū)別，并證明了elitism是改善多目標(biāo)搜索的重要因素。以往通過線性加權(quán)方法對多目標(biāo)進行優(yōu)化，均人為選取權(quán)重，會對最優(yōu)解造成一定誤差。

單純形法在數(shù)學(xué)優(yōu)化領(lǐng)域常被用于線性規(guī)劃問題的數(shù)值求解,同樣單純形法的創(chuàng)建也推動了線性規(guī)劃問題研究理論的發(fā)展。線性規(guī)劃問題是探究在一定約束下求極值的方法，單純形法能夠有效地解決此類問題。

鄧勃等[9]對幾類常用的單純形優(yōu)化方法的優(yōu)化性能進行了比較，并分析了其效果的優(yōu)劣性。韓煒等[10]提出了一種將遺傳算法和單純形法組合的全局優(yōu)化算法。吳承禎等[11]運用單純形法優(yōu)化擬合了Logistic曲線，結(jié)果表明改進后的單純形法具有較強的擬合非線性方程的能力，對于各學(xué)科中的非線性曲線的參數(shù)估計具有普遍意義。申卯興等[12]通過對單純形求解法的實質(zhì)進行分析，提出了一種基于矩陣初等變換初始可行基的獲得方法。鑒于此，為避免主觀因素對權(quán)重選取的影響，提出了一種基于單純形法的多目標(biāo)優(yōu)化復(fù)合算法。

1 最優(yōu)化模型

一般來說，一個最優(yōu)化問題具有以下形式：

minf(x) or maxf(x)，

(1)

s.t.gi(x)≤0,i=1,2,…,m，
hi(x)=0,i=1,2,…,l，
x=(x1,x2,…,xn)T∈X。

S={x∈X∣gi(x)≤0,i=1,2,…,m,

hi(x)=0,i=1,2,…,l}

(2)

稱為最優(yōu)化問題的可行集。

在單目標(biāo)優(yōu)化問題(single-objective optimization problem，簡稱SOP)中，最優(yōu)解可通過較為簡單的數(shù)學(xué)方法求出，然而，多目標(biāo)優(yōu)化問題中，各個目標(biāo)之間相互制約，使得一個目標(biāo)的改善往往是以損失其他目標(biāo)的性能為代價。因此，對于多目標(biāo)優(yōu)化問題，其解大多為一個非劣解的集合，即Pareto解集，而且，只有當(dāng)一組解收斂到接近真正Pareto最優(yōu)解時，才能確保該組解近似最優(yōu)，同時，求得的解也必須均勻稀疏地分布在Pareto最優(yōu)域上。一組在多個目標(biāo)之間好的協(xié)議解是建立在一組多樣解的基礎(chǔ)之上,因為在多目標(biāo)進化算法中，決策者一般需要處理決策變量空間和目標(biāo)空間2個空間，所以解(個體)之間的多樣性可以分別在這2個空間定義。

通過種群各個體綜合適應(yīng)度方差最大化來確定目標(biāo)權(quán)重[6]，從而將目標(biāo)權(quán)重的計算轉(zhuǎn)化為如下約束優(yōu)化問題：

(3)

(4)

其中，fij為第i個可行解的第j個指標(biāo)。

對比多目標(biāo)優(yōu)化問題和單目標(biāo)優(yōu)化問題，兩者最大的區(qū)別在于前者將問題總結(jié)為一個向量優(yōu)化問題。但在向量比較中存在的影響因素較多且復(fù)雜，難以完全考慮到，且大多數(shù)實際問題嚴(yán)格來說都屬于多目標(biāo)優(yōu)化問題，所以可將多目標(biāo)優(yōu)化問題通過非負(fù)加權(quán)求和轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。在目前的算法中，研究者采用主觀賦予的方法，將權(quán)值設(shè)定為幾組固定值。雖然這些固定值確實對于一些算法來說是較好的選擇，但將這些固定值在此類問題中默認(rèn)為通用，則不夠嚴(yán)謹(jǐn)。Kanako等[2]認(rèn)為，完全最優(yōu)解在不能夠同時最小化所有目標(biāo)函數(shù)時，Pareto最優(yōu)化就變的尤為重要。

minF(x)， s.t.x∈Rn，

(5)

對于所有的x∈Rn，都有

Fi∶Rn→R,i=1，2，…，m。

同時假設(shè)分量函數(shù)Fi連續(xù)可微且有下界。

引理1若不存在x∈Rn滿足F(x)≤F(x*)和F(x)≠F(x*)，則點x*∈Rn是Pareto對于問題(4)的最優(yōu)解(最有效解)。此外，點x∈Rn是Pareto臨界點(平穩(wěn)點)。

通過引入松弛變量，可使多目標(biāo)優(yōu)化問題實現(xiàn)完全無量綱化，使得多個目標(biāo)處于同一完全標(biāo)量[13]。單目標(biāo)優(yōu)化問題

(6)

s.t.fi(x)+risi≤εi，

x∈X,si≥0,?i=1,2,…,p,

其中，fi(x)為有上界的函數(shù)，存在Ui∈R，使得fi(x)≤Ui。

2 算法構(gòu)建

將多目標(biāo)優(yōu)化問題線性加權(quán)為單目標(biāo)優(yōu)化問題，需要建立一個復(fù)合型算法來確定權(quán)重，并判斷是否在可行域范圍之內(nèi)。

先設(shè)置反射系數(shù)α、壓縮系數(shù)θ、擴張系數(shù)γ和收縮系數(shù)β，形成初始單純形，并自選一個在可行域內(nèi)的頂點，其他2個頂點由次頂點構(gòu)造產(chǎn)生。一般需要確定第一個頂點，若所確定的頂點不在可行域內(nèi)，則應(yīng)通過重新產(chǎn)生隨機數(shù)再產(chǎn)生隨機點，直到第一個頂點在可行域內(nèi)為止。最終所選擇的頂點都需要滿足可行性檢查，若不滿足，則需要調(diào)入，即先求出可行點集中心

(7)

再調(diào)入迭代：

X(q+1)=X(S)+0.5(X(q+1)-X(S))，

(8)

然后計算最好點X(L)、次差點X(H-1)和最差點X(H)，

(9)

計算出壞點外其余各頂點的中心

(10)

若X0不在可行域內(nèi)，則以最好點為起點。計算出除最差點外其他頂點的形心，判斷各頂點與形心是否在可行域內(nèi)，若符合條件，則測試

max‖Xi-X1‖<ε，

(11)

滿足條件(11)，則完成單純形的構(gòu)造；若頂點及形心不在可行域內(nèi)，便縮小初始單純形構(gòu)造因子系數(shù)，并重新構(gòu)造單純形，當(dāng)不滿足式(11)時，利用最差點求出反射點

X(R)=X0+α(X0-X(H))，

(12)

通常取α=1,3。檢查X(R)是否在可行域內(nèi)，若X(R)為非可行點，將反射系數(shù)減半后，再按式(12)更改反射點，直到X(R)進入可行域內(nèi)為止；若反射點在可行域內(nèi)，則繼續(xù)比較反射點是否優(yōu)于最優(yōu)值。當(dāng)反射點優(yōu)于壞點，即f(X(R))f(X(H))，這種情況往往是由于反射點過遠引起的，α→0.5α將反射點拉近。

計算擴張點，在符合邊界條件的情況下將擴張點代替最差點，再利用式(7)進行測試，若滿足式(11)，則完成了模型構(gòu)造。

算法1多目標(biāo)優(yōu)化

輸入：x1，x2，x;

1)設(shè)置α=1，γ=2，β=0.5，h=4，hi=1，esp=5;

2)建立初始單純形;

f(X(L))=min{f(X(j)),i=1,2,…,K},

f(X(H))=max{f(X(j)),i=1,2,…,K};

4)計算除壞點以外其余各頂點的中心

5)判斷各頂點在不在可行域內(nèi);

6)ifai>20 do;

7)無法收斂, 重新構(gòu)造單純形;

8)if f_reflect_n2

9)X_reflect進行擴張，并作為單純形新頂點;

10)m=abs(double(subs(f,symvar(f),X(:,F_index(end))′))-f_Xc_n1)，計算精度;

11)結(jié)束循環(huán)，輸出最優(yōu)解。

算法流程如圖1所示。

3 數(shù)值算例

采用Mita等[2]的2個算例來驗證算法的功能性。

1)Das and Dennis(DD1)：n=5,m=2，

L= (-20,-20,…,-20)T,U= (20,20,…,20)T。

將算例1導(dǎo)入算法1，可得如表1所示的最好點、最壞點、次壞點和一系列反射點的具體數(shù)值。圖2為各點在目標(biāo)函數(shù)上的數(shù)值。

圖1 算法流程圖

表1 DD1模型的計算結(jié)果

圖2 各點在目標(biāo)函數(shù)上的數(shù)值

由表1可知，通過多次迭代后目標(biāo)函數(shù)的最優(yōu)值(Xc_n1)為1.049 3。因為初始點的選取未摻入主觀因素的影響，所以此最優(yōu)值的誤差更小。

n=10,m=3，

L= (-2,-2,…,-2)T,U= (2,2,…,2)T。

同樣地，將算例2代入算法1后，能夠得到如表2所示的各點在目標(biāo)函數(shù)中體現(xiàn)的具體數(shù)值。

表2 FDS的計算結(jié)果

從表2可看出，經(jīng)過多次反射點迭代，最終得到線性加權(quán)函數(shù)的最優(yōu)解為0.564 1，并得到初始點中的最壞點、次壞點和最好點及多次反射點，排除人為主觀因素影響后，也將誤差影響降到最低。

4 結(jié)束語

通過運用以單純形法為基礎(chǔ)的復(fù)合型算法，在多目標(biāo)優(yōu)化問題中，無需對目標(biāo)函數(shù)求導(dǎo)即可找到最優(yōu)值。該算法運用在多目標(biāo)優(yōu)化問題中可大大減少計算工作量，相較于最速下降法、牛頓法、共軛梯度法等復(fù)合型算法，求解的極值精度更高，且可避免因目標(biāo)函數(shù)求導(dǎo)值精確度的誤差對最后結(jié)果的影響。該算法是根據(jù)目標(biāo)各數(shù)點的函數(shù)值大小關(guān)系，判斷目標(biāo)函數(shù)的變化趨勢，為尋找目標(biāo)函數(shù)的極值方向提供依據(jù)，經(jīng)過若干次迭代后找到極值點。通過judge函數(shù)選取目標(biāo)函數(shù)最合適的初始點，也可避免因主觀選取初始點造成的誤差，從而提高最優(yōu)解的精確性。但線性加權(quán)求和的方法只能通過逼近Pareto前沿面為凸集的情況，若多目標(biāo)優(yōu)化問題的Pareto面為非凸，此方法就不能與原多目標(biāo)優(yōu)化問題完全等價，此時直接處理原多目標(biāo)優(yōu)化問題才能夠得到最優(yōu)解。