基于優(yōu)先度函數(shù)的概率不確定語言術(shù)語集雙邊匹配方法

白曉莉,陳巖,2,鄧珍美

(1.沈陽工業(yè)大學(xué) 理學(xué)院,遼寧 沈陽 110870;2.沈陽工業(yè)大學(xué) 管理學(xué)院,遼寧 沈陽 110870)

雙邊匹配研究可以追溯于Gale和Shapley[1]在關(guān)于婚姻匹配問題中的研究,研究中論證了雙邊穩(wěn)定匹配的存在性以及最優(yōu)性,并提出了著名的Gale-Shapley算法.自此之后,雙邊匹配問題的研究不斷涌現(xiàn)于各個領(lǐng)域.例如,崗位與求職者匹配問題[2]、風(fēng)險投資企業(yè)匹配問題[3]、醫(yī)生與患者匹配問題[4]、物流服務(wù)供應(yīng)方與需求方匹配問題[5]等.隨著社會的發(fā)展,匹配問題背景愈加復(fù)雜,由于評價主體受專業(yè)知識限制,評價信息通常具有不確定性.不確定信息下的雙邊匹配問題是目前研究的熱點,在不確定形式下,主體無法使用比較精確的數(shù)值進(jìn)行評價,為了這一問題得到解決,學(xué)者們將直覺模糊、猶豫模糊[6]、區(qū)間猶豫模糊[8]、區(qū)間直覺模糊[9]、三角模糊[10]等方法引入雙邊匹配問題中,并應(yīng)用于各個領(lǐng)域.但在模糊環(huán)境下進(jìn)行評價,就意味著主體所提供的語言術(shù)語集的重要程度是一致的.實際并非如此,主體給出的語言術(shù)語集中的語言術(shù)語不一定是等概率的.在2016年,Pang[11]等學(xué)者們對猶豫模糊語言術(shù)語集中的每一個語言項都賦予了概率,定義了概率語言術(shù)語集(PLTS).因此,學(xué)者們開始對概率語言環(huán)境下雙邊匹配問題進(jìn)行研究.Li等提出了一種在概率語言環(huán)境下,基于前景理論的屬性權(quán)重未知的雙邊匹配方法.Li等[13]提出了基于概率語言偏好關(guān)系的雙邊匹配方法,其中給出了時間滿意度的定義,并構(gòu)建模型來處理概率語言偏好關(guān)系.Li等[14]學(xué)者提出了一種在概率語言術(shù)語集下,考慮最低可接受值的基于后悔理論雙邊匹配決策方法.汪新凡等針對概率猶豫模糊信息下準(zhǔn)則具有期望水平的雙邊匹配問題,提出了一種考慮匹配主體心理行為的雙邊匹配方法.之后就有一些學(xué)者提出匹配主體可能更傾向用類似于[好,非常好]這種語言評價區(qū)間的形式來表達(dá)偏好信息,基于Xu[11]在2004年提出了不確定語言變量(ULV)的概念后,在2017年,由Lin等[17]提出了概率不確定語言術(shù)語集(PULTS)的概念.概率不確定語言術(shù)語集體現(xiàn)不確定語言術(shù)語集的概率特征,是概率語言術(shù)語集與不確定語言術(shù)語的擴(kuò)展形式.但從目前來看,將概率不確定語言術(shù)語集應(yīng)用于雙邊匹配問題中的研究鮮有涉足,并且已有研究大多以設(shè)立參照點獲得主體相對優(yōu)勢,這會導(dǎo)致匹配主體評價信息的偏差,從而影響匹配結(jié)果.其次,為獲得符合匹配主體偏好的匹配方案,匹配主體在匹配過程中的心理行為也應(yīng)當(dāng)充分考慮.

因此,本文對于概率不確定語言環(huán)境下的雙邊匹配問題進(jìn)行了研究,并且考慮了主體的心理行為.首先,給出了概率不確定語言術(shù)語集區(qū)間型得分的定義,進(jìn)而根據(jù)可能度公式計算概率不確定語言術(shù)語集間的可能度,比較概率不確定語言術(shù)語集的優(yōu)劣程度;其次構(gòu)造出優(yōu)先度函數(shù)來反映匹配主體心理行為;然后,利用新的滿意度公式構(gòu)建滿意度矩陣,建立雙邊匹配滿意度最大化模型,通過求解模型,獲得最優(yōu)匹配方案;最后,進(jìn)行算例分析,并與現(xiàn)有雙邊匹配方法進(jìn)行比較,證明了所提出方法的優(yōu)點.

1 基礎(chǔ)知識

1.1 不確定語言變量

1.2 概率不確定語言術(shù)語集(PULTS)相關(guān)概念

其中〈[Lk,Uk],pk〉表示不確定語言術(shù)語,且[Lk,Uk]的概率為pk,Lk和Uk是語言術(shù)語,滿足Lk≤Uk,#S(p)是S(p)的基數(shù).

Lin[17]等學(xué)者給出了概率不確定語言術(shù)語集標(biāo)準(zhǔn)化的方法:

(1)S(p)為任一概率不確定語言術(shù)語集,則已標(biāo)準(zhǔn)化的概率不確定語言術(shù)語集Sn(p)為

(2)如果#S1(p)<#S2(p),則給S1(p)增加具有概率為0的最小不確定語言變量#S2(p)-#S1(p)個,這樣使得兩個概率不確定語言術(shù)語集的基數(shù)相等.

定義3 設(shè)兩個標(biāo)準(zhǔn)化概率不確定語言術(shù)語集為

那么它們的運(yùn)算法則為

(3)λS(p)=∪〈[Lk,Uk],pk〉∈S(p){λpk[Lk,Uk]};

(4)(S(p))λ=∪〈[Lk,Uk],pk〉∈S(p){[Lk,Uk]λpk}.

其中λ≥0.

=

為概率不確定語言術(shù)語集平均算子(PULA).

1.3 雙邊匹配

設(shè)雙邊匹配主體集合分別為A={A1,A2,…,Am},B={B1,B2,…,Bn},其中,Ai表示A中的第i個主體,i∈M,M={1,2,…,m}.Bj表示B中的第j個主體j∈N,N={1,2,…,n}.一般地,m≥n.

定義5 設(shè)一一映射μ:A∪B→A∪B,若?Ai∈A,?Bj∈B,滿足:

(1)μ(Ai)∈B;

(2)μ(Bj)∈A∪{Bj};

(3)μ(Ai)=Bj當(dāng)且僅當(dāng)μ(Bj)=Ai.

則稱μ為雙邊匹配.其中μ(Ai)=Bj或μ(Bj)=Ai,表示Ai與Bj在μ中匹配,記為(Ai,Bj);μ(Bj)=Bj表示Bj在μ中未匹配,記為(Bj,Bj).

2 優(yōu)先度函數(shù)

2.1 可能度

定義6 對于任意的概率不確定語言術(shù)語集S(p)={〈[Lk,Uk],pk〉|pk≥0,k=1,2,…,#S(p)},稱

為概率不確定語言術(shù)語集的區(qū)間型得分.

定義7 概率不確定語言術(shù)語集間的可能度定義為:

(1)

①若0.5<ρ(S1(p1)≥S2(p2))≤1時,則S1(p1)優(yōu)于S2(p2),記為S1(p1)?S2(p2);②若ρ(S1(p1)≥S2(p2))=0.5時,則S1(p1)和S2(p2)無差異,記為S1(p1)～S2(p2);③若0≤ρ(S1(p1)≥S2(p2))<0.5時,則S1(p1)劣于S2(p2),記為S1(p1)S2(p2).

顯然,通過此公式,不僅能夠反映出概率不確定語言術(shù)語集間“期望”的差異,還可以反映它們之間“方差”的差異;其次,此公式無需借助像 Lin等學(xué)者提出的雙層比較的方式,就可以進(jìn)行概率不確定語言術(shù)語集間的優(yōu)劣比較,并能度量出兩個概率不確定語言術(shù)語集間的優(yōu)劣程度.

(1)有界性:0≤ρ(S1(p1)≥S2(p2))≤1;

(2)互補(bǔ)性:ρ(S1(p1)≥S2(p2))+ρ(S2(p2)≥S1(p1))=1;

(3)自反性:當(dāng)S1(p1)=S2(p2)時,ρ(S1(p1)≥S2(p2))=0.5;

(4)傳遞性:ρ(S1(p1)≥S2(p2))≥0.5,ρ(S2(p2)≥S3(p3))≥0.5,則ρ(S1(p1)≥S3(p3))≥0.5.

證明

(1)由定義7可知,可能度滿足0≤ρ(S1(p1)≥S2(p2))≤1.

(2)分兩種情況討論,第一種情況,當(dāng)SL1≥SU2時,ρ(S1(p1)≥S2(p2))=1,而ρ(S2(p2)≥S1(p1))=0,滿足ρ(S1(p1)≥S2(p2))+ρ(S2(p2)≥S1(p1))=1;

(3)根據(jù)公式(1),當(dāng)S1(p1)=S2(p2)時,SL1=SL2,SU1=SU2,因此,ρ(S1(p1)≥S2(p2))=0.5.

(4)ρ(S1(p1)≥S2(p2))≥0.5,ρ(S2(p2)≥S3(p3))≥0.5時,

可以推導(dǎo)出SU1-SL2≥SU2-SL1,SU2-SL3≥SU3-SL2,接著推導(dǎo)出,SU1-SL3≥SU3-SL1,再由公式

因此,ρ(S1(p1)≥S3(p3))≥0.5.

2.2 優(yōu)先度

定義8 設(shè)任意兩個已標(biāo)準(zhǔn)化的概率不確定語言術(shù)語集為

(2)

其中0≤ρ≤1.

進(jìn)一步說明,當(dāng)ρ∈[0,0.5)時,S1(p1)S2(p2),此時ρ*<0;當(dāng)ρ=0.5時,S1(p1)和S2(p2)無差異,ρ*=0;

當(dāng)ρ∈(0.5,1]時,S1(p1)?S2(p2),此時ρ*>0.

(1)-0.5<ρ*(S1(p1)≥S2(p2))<0.5;

(2)互補(bǔ)性:ρ*(S1(p1)≥S2(p2))+ρ*(S2(p2)≥S1(p1))=0;

(3)自反性:當(dāng)S1(p1)=S2(p2)時,ρ*(S1(p1)≥S2(p2))=0;

(4)傳遞性:ρ*(S1(p1)≥S2(p2))≥0,ρ*(S2(p2)≥S3(p3))≥0,則ρ*(S1(p1)≥S3(p3))≥0.

由定理1及證明和公式(2),可證明優(yōu)先度函數(shù)具有以上性質(zhì).

2.3 距離測度

為了避免匹配主體評價信息中偏倚數(shù)據(jù)的影響,根據(jù)區(qū)間型得分,定義了兩個概率不確定語言術(shù)語集間的距離測度.

(3)

定理3 給定概率不確定語言術(shù)語集S1(p1),S2(p2),S3(p3),則式(3)滿足:

(1)d(S1(p1),S2(p2))≥0;

(2)d(S1(p1),S2(p2))=d(S2(p2),S1(p1));

(3)d(S1(p1),S2(p2))+d(S2(p2),S3(p3))≥d(S1(p1),S3(p3)).

注:d(S1(p1),S2(p2))=0當(dāng)且僅當(dāng)S1(p1)與S2(p2)相等.

3 基于優(yōu)先度函數(shù)的雙邊匹配模型與方法

3.1 雙邊匹配問題描述

3.2 滿意度計算

雙邊匹配的目標(biāo)是使得雙邊匹配主體滿意度最大,由式(2)、式(3)概率不確定語言術(shù)語集的優(yōu)先度函數(shù)以及距離測度,在此定義雙邊匹配主體的滿意度.

定義10 設(shè)SdAi→Bj是在屬性Up下,匹配主體Ai對匹配主體Bj的滿意度,其計算公式為

(4)

定義11 設(shè)SdBj→Ai是在屬性Vq下,匹配主體Bj對匹配主體Ai的滿意度,其計算公式為

(5)

那么,匹配主體Ai對于Bj的綜合滿意度以及匹配主體Bj對于Ai的綜合滿意度分別為

(6)

(7)

3.3 雙邊匹配模型

基于以上匹配雙方滿意度矩陣的計算,建立了匹配雙方滿意度最大化目標(biāo)雙邊匹配模型P1如下:

(8)

(9)

(10)

(11)

其中,xij為0-1變量,xij等于1時,說明Ai與Bj匹配,xij等于0時,說明Ai與Bj不匹配.式(8)是表示匹配主體A的最大化滿意度,式(9)是表示匹配主體B的最大化滿意度,式(10)表示任一匹配主體A只能與一主體B匹配或不匹配,式(11)表示任一匹配主體B與一匹配主體A匹配.

由于匹配雙方的目標(biāo)函數(shù)是等級的,因此,通過線性加權(quán)法可將多目標(biāo)模型P1轉(zhuǎn)化為單目標(biāo)模型P2,分別加權(quán)α和β(0≤α,β≤1,α+β=1).則P2為:

3.4 雙邊匹配方法步驟

基于概率不確定語言術(shù)語集下考慮心理行為的雙邊匹配問題,提出了優(yōu)先度函數(shù)和距離測度,用于構(gòu)造滿意度矩陣,進(jìn)而建立雙邊匹配模型,具體步驟如下:

Step 2 對評價信息進(jìn)行標(biāo)準(zhǔn)化處理,并集結(jié)屬性準(zhǔn)則下的評價信息.

Step 3 將已標(biāo)準(zhǔn)化的評價信息,根據(jù)定義6和式(1)-(5)求得SdAi→Bj和SdBj→Ai.

Step 4 利用式(6)、(7)得到滿意度aij和bij,進(jìn)而構(gòu)造滿意度矩陣A=[aij]m×n和B=[bij]m×n.

Step 5 構(gòu)建多目標(biāo)模型P1,并將其轉(zhuǎn)化為單目標(biāo)模型P2.

Step 6 用Kuhn-Munkras算法求解模型P2,得到最優(yōu)匹配方案.

4 算例分析

4.1 問題描述

某工業(yè)園有3家新進(jìn)企業(yè)需要實施倉儲管理系統(tǒng)(WMS),通過服務(wù)中介機(jī)構(gòu)投放廣告等相關(guān)信息,有4家軟件供應(yīng)商有合作意向,記為Ai(i=1,2,3,4),這3家軟件需求企業(yè)記為Bj(j=1,2,3),軟件供應(yīng)商Ai對軟件需求企業(yè)Bj評價的參考屬性為U1(系統(tǒng)實現(xiàn)的收益)、U2(企業(yè)規(guī)模)、U3(發(fā)展前景),加權(quán)向量為

S={s-3:非常差,s-2:較差,s-1:差,s0:中等,s1:好,s2:很好,s3:非常好}.

4.2 求解過程

Step 1獲得評價信息.

表1 在屬性U1下的評價信息矩陣

表2 在屬性U2下的評價信息矩陣

表3 在屬性U3下的評價信息矩陣

表4 在屬性V1下的評價信息矩陣

表5 在屬性V2下的評價信息矩陣

表6 在屬性V3下的評價信息矩陣

Step 2根據(jù)式(1)-(5)分別求得滿意度SdAi→Bj和SdBj→Ai,如下表7、8所示:

表7 Ai對Bj滿意度矩陣

表8 Bj對Ai滿意度矩陣

Step 3 利用式(6)、(7)獲得滿意度aij和bij,進(jìn)而構(gòu)造滿意度矩陣A=[aij]4×3和B=[bij]4×3.

Step 4 構(gòu)建多目標(biāo)模型P1,令α=β=0.5,將多目標(biāo)模型P1轉(zhuǎn)化為模型P2.

Step 5 將綜合滿意度作為二分圖匹配中的權(quán)值,用Kuhn-Munkras算法求解模型P2,獲得雙邊匹配矩陣為

所以最優(yōu)匹配方案為{(B1,A2),(B2,A3),(B3,A4)}.

4.3 比較分析

表9 不同匹配方法的對比

表9顯示,這4種不同的匹配方法所對應(yīng)的匹配方案存在差異,進(jìn)一步分析存在差異的原因:

文獻(xiàn)[12]、文獻(xiàn)[19]中均應(yīng)用前景理論來考慮匹配主體心理行為,但前景理論需要考慮雙邊匹配主體的損失規(guī)避系數(shù)、風(fēng)險厭惡系數(shù)和風(fēng)險偏好系數(shù),參數(shù)較多,計算較冗雜,本文的優(yōu)先度不需要考慮參數(shù)的設(shè)置,計算較簡潔;文獻(xiàn)[14]中通過概率語言術(shù)語集期望值與匹配主體評價值的方式來獲得滿意度會導(dǎo)致綜合滿意度偏高或偏低,從而影響匹配結(jié)果.

文獻(xiàn)[14]的雙邊匹配方案與本文的方案不完全一致,造成這種差異的主要原因:一方面在于文獻(xiàn)[14]構(gòu)建基于期望值的滿意度函數(shù),建立了基于后悔理論的雙邊匹配模型,這樣應(yīng)用期望值會導(dǎo)致評價信息的失真,后悔理論也僅反映了匹配主體的后悔心理;另一方面在于文獻(xiàn)[14]考慮了最低可接受度,但最低可接受度是假設(shè)的虛擬值,選取不同可能會對匹配結(jié)果有影響.本文應(yīng)用優(yōu)先度與距離測量來獲得滿意度,可以避免信息的失真,從而確保匹配結(jié)果更合理,更準(zhǔn)確.并且參照點設(shè)置為評價信息的綜合平均值而不是虛擬值,這樣不但可以集中于原始評價信息,而且使計算更簡化,本文中提出的優(yōu)先度函數(shù)不同于后悔理論,它能更靈活的反映匹配主體的趨優(yōu)性、規(guī)避劣性的心理行為.

5 結(jié) 論

針對概率不確定語言環(huán)境下的雙邊匹配問題,考慮雙邊主體趨優(yōu)性的心理行為特征,提出了一種基于優(yōu)先度函數(shù)的雙邊匹配方法.(1)定義概率不確定語言術(shù)語集區(qū)間型得分,給出可能度公式,以此把定性信息轉(zhuǎn)化為定量分析,使得匹配結(jié)果更符合匹配雙方主體的預(yù)期.(2)定義的優(yōu)先度函數(shù)和距離測度為處理概率不確定語言環(huán)境下的雙邊匹配問題提供了一種有力工具,有效避免了目前研究中直接應(yīng)用期望值或評分值的方式來獲得滿意度所導(dǎo)致的信息失真.(3)定義的優(yōu)先度函數(shù)可以反映主體趨優(yōu)性和規(guī)避劣性的心理行為且不需要考慮參數(shù)的設(shè)置,計算較簡潔.