基于TOPSIS的改進雙層多目標優(yōu)化算法研究

葉 茂，王 魯*，馬志東

(山東農(nóng)業(yè)大學(xué)信息科學(xué)與工程學(xué)院，山東 泰安 271018)

1 引言

雙層多目標優(yōu)化問題是指在一個多目標優(yōu)化問題中存在兩個不同的決策者(DM)，兩個決策者位于不同的層級，并且獨立控制著一組決策變量和相互沖突的目標函數(shù)。在雙層多目標優(yōu)化問題中，上層決策者(ULDM)先進行決策，下層決策者(LLDM)的決策受上層決策者的影響[1]。雙層多目標優(yōu)化問題的基本概念是首先由ULDM設(shè)定目標并做出決策，然后LLDM在ULDM的決策下對目標進行最優(yōu)化計算，最后ULDM參考LLDM提出的方案綜合考慮上下層，得到雙層多目標優(yōu)化問題的滿意解。

TOPSIS(Technique for order performance by similarity to ideal solution)是解決多目標決策問題的經(jīng)典方法之一，為多目標優(yōu)化問題提供一個更廣闊的折中方案。它的基本思想是所選結(jié)果與正理想解(PIS)距離最近，與負理想解(NIS)距離最遠，將雙層多目標優(yōu)化問題中每一層中互相沖突的多個目標的轉(zhuǎn)化為兩個目標，即與PIS距離最近和與NIS距離最遠[2]。然后利用模糊集理論中的隸屬度函數(shù)來表示兩種距離的滿意度，最后利用FGP(fuzzy goals programming)方法解決兩個目標相互沖突的問題[3]，[4]。

近年來，雙層多目標優(yōu)化問題得到廣泛的研究[5]。TOPSIS是由Hwang和Yoon首先提出，Lia等人將TOPSIS方法進行擴展用于求解雙層多目標優(yōu)化問題[6]，[7]。Dey等利用線性化技術(shù)將非線性隸屬函數(shù)轉(zhuǎn)換成等價的線性隸屬函數(shù)，然后進行歸一化處理，接著建立模糊規(guī)劃模型，通過最小化負偏差變量來實現(xiàn)問題的折中解[8]。Abo-Sinna利用TOPSIS方法求解分式規(guī)劃問題，將目標函數(shù)轉(zhuǎn)化為最大化型非線性函數(shù)，避免決策過程中出現(xiàn)的決策僵局[9]。Elsisy等人將TOPSIS方法和KKT(Karush-Kuhn-Tucker)結(jié)合用于求解模糊粗糙雙層多目標線性規(guī)劃問題[10]。El sayed對模型中分數(shù)目標的系數(shù)和標量進行模糊處理，避免問題中的舍入誤差[11]。本文提出一種改進的雙層多目標優(yōu)化算法(MBLMOO)，該方法結(jié)合TOPSIS方法和FGP方法，利用FGP方法代替TOPSIS方法中的最大最小模型，實驗結(jié)果表明了該算法的有效性。

2 算法描述

2.1 問題闡述

雙層多目標優(yōu)化問題包含兩個決策者，每一層都有一組不可通約、相互矛盾的目標函數(shù)[1][7]。雙層多目標優(yōu)化問題最大化型模型如下。

上層問題求解x1

(1)

下層問題求解x2

(2)

約束條件

x∈G={x=(x1，x2)∈Rn|

gi(x1，x2)≤0，i=1，2，…，q}≠?

(3)

其中x1∈Rn1，x2∈Rn2，n=n1+n2，x1=(x11，x12，…，x1n1)，x2=(x21，x22，…，x2n1)，G為雙層多目標優(yōu)化問題的可行集，m1，i=1，2表示第i個決策者的目標函數(shù)個數(shù)，q表示約束函數(shù)個數(shù)。

2.2 基于TOPSIS的改進雙層多目標優(yōu)化算法

TOPSIS方法求解雙層多目標優(yōu)化問題的基本思想是所求的解與正理想解距離最近，與負理想解距離最遠。方法中所提到的距離函數(shù)定義如下[9]

(4)

2.2.1 MBLMOO算法求解上層問題

針對雙層多目標優(yōu)化問題的上層問題

MBLMOO算法上層模型如下

(5)

s.t.

x∈G={x=(x1，x2)∈Rn|

gi(x1，x2)≤0，i=1，2，…，q}≠?

(6)

μ1(x)=

(7)

μ2(x)=

(8)

隸屬度函數(shù)圖像如圖1所示。

圖1 隸屬度函數(shù)μ1(x)，μ2(x)

使用FGP方法[12]引入具有統(tǒng)一性適應(yīng)度的成員目標如下

(9)

(10)

(11)

s.t.

(12)

x∈G={x=(x1，x2)∈Rn|gi(x1，x2)≤0，

i=1，2，…，q}≠?

求解模型可得上層問題的決策向量x1u*=(x11u*，x12u*，…，x1n1u*)，為了保證所提出的MBLMOO方法的有效性，將上層問題所得的決策向量作為下層問題的約束。

2.2.2 MBLMOO算法求解雙層問題

為了使用基于TOPSIS方法得到雙層多目標優(yōu)化問題的滿意解，構(gòu)造雙層問題的距離函數(shù)如下

(13)

(14)

構(gòu)造MBLMOO算法模型

(15)

s.t.

x∈G={x=(x1，x2)∈Rn|

gi(x1，x2)≤0，i=1，2，…，q}≠?

(16)

μ3(x)=

(17)

μ4(x)=

(18)

引入具有統(tǒng)一性適應(yīng)度的成員目標如下

(19)

(20)

(21)

s.t.

(22)

x∈G={x=(x1，x2)∈Rn|gi(x1，x2)≤0，

i=1，2，…，q}≠?

2.3 算法求解步驟

根據(jù)以上MBLMOO算法，算法步驟如下：

1)分別計算雙層多目標優(yōu)化問題各層中每個目標獨立的最大值和最小值；

7)構(gòu)造雙層多目標優(yōu)化問題的PIS和NIS收益表；

3 仿真研究

3.1 測試函數(shù)

通過求解Abo-Sinna[1]所研究的測試函數(shù)來驗證所提出的MBLMOO算法的有效性。

上層優(yōu)化問題

(23)

下層優(yōu)化問題

(24)

約束條件

x=(x1，x2)∈G={(x1，x2)|x1+x2≤4，x1，x2≥0}

(25)

對測試函數(shù)中每一個目標函數(shù)求解，其獨立最優(yōu)解的最大、最小值如表1所示。

表1 獨立最優(yōu)解的最大及最小值

3.2 MBLMOO算法求解測試函數(shù)上層問題

求解上層優(yōu)化問題：

(26)

約束條件：

x=(x1，x2)∈G={(x1，x2)|x1+x2≤4，x1，x2≥0}

(27)

構(gòu)造上層優(yōu)化問題的PIS和NIS收益表如表2和表3所示：

表2 上層問題的PIS收益表

表3 上層問題的NIS收益表

s.t.

3.3 MBLMOO算法求解測試函數(shù)雙層問題

下層優(yōu)化問題：

(28)

約束條件：

x=(x1，x2)∈G={(x1，x2)|x1+x2≤4，x1，x2≥0}

(29)

構(gòu)造下層優(yōu)化問題的PIS和NIS收益表如表4和表5所示。

表4 下層問題的PIS收益表

表5 下層問題的NIS收益表

s.t.

使用Lingo程序求解模型，得到測試函數(shù)的滿意解x*=(0，0.398)，目標函數(shù)的解為f11=15.84，f12=16.84，f21=-6.92，f22=63.68，Z=1.877。

3.4 結(jié)果分析

將本文所提出的MBLMOO算法求解Abo-Sinna所研究的測試函數(shù)所得結(jié)果與Abo-Sinna提出的模糊方法[1]及A.Baky改進的TOPSIS方法[14]所求結(jié)果進行比較，各目標函數(shù)的最優(yōu)解為f11=16，f12=17，f21=9，f22=64。比較結(jié)果如表6所示：

表6 比較基于不同方法的滿意解及最優(yōu)解

從表6中可以看出，MBLMOO算法得到的滿意解與Abo-Sinna提出的模糊方法及A.Baky提出的TOPSIS方法所得到的滿意解相比較，具有更好的表現(xiàn)。

4 總結(jié)

針對雙層多目標優(yōu)化問題的多層次多目標的特性，本文提出一種基于TOPSIS的改進雙層多目標優(yōu)化算法。利用TOPSIS方法的正理想解和負理想解的特性，將雙層多目標優(yōu)化問題中每一層中互相沖突的多個目標的轉(zhuǎn)化為兩個目標，然后利用模糊集理論中的隸屬度函數(shù)來表示兩種距離的滿意度，并利用FGP方法解決雙目標函數(shù)相互沖突的問題。最后通過一個測試函數(shù)與Abo-Sinna提出的模糊方法及A.Baky提出的TOPSIS方法相比較，結(jié)果驗證了所提的MBLMOO算法的有效性。