一種解釋結(jié)構(gòu)模型的優(yōu)化算法研究

彭曉易 李穎 李晶

摘要：解釋結(jié)構(gòu)模型被廣泛應(yīng)用于醫(yī)療、教育等領(lǐng)域，但相關(guān)理論發(fā)展較為緩慢。為加快解釋結(jié)構(gòu)模型的計算速度，豐富解釋結(jié)構(gòu)模型相關(guān)理論，通過對系統(tǒng)各要素所對應(yīng)有向圖的本質(zhì)關(guān)系進行分析，對該模型中的級間劃分方法作更深一步解析并給出優(yōu)化算法，發(fā)現(xiàn)有向圖中若不存在回路，則有向圖匯點對應(yīng)的是最高級要素集合中的要素，因此匯點可以從縮減可達矩陣中直接找出，從而能對復(fù)雜系統(tǒng)要素更快地進行分層。對應(yīng)的優(yōu)化算法相比傳統(tǒng)方法減少了一倍左右的計算量，并通過實證分析進行驗證。該研究結(jié)果為解釋結(jié)構(gòu)模型方法優(yōu)化提供了一種新詮釋。

關(guān)鍵詞：解釋結(jié)構(gòu)模型;縮減可達矩陣;匯點;優(yōu)化算法

DOI：10.11907/rjdk.191537 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP312文獻標(biāo)識碼：A 文章編號：1672-7800（2020）006-0057-04

0 引言

1973年，Warfield提出解釋結(jié)構(gòu)模型（InterpretiveStructural Modeling，ISM）。ISM的特點是運用人們的知識及經(jīng)驗，通過計算機的幫助，將一個復(fù)雜的社會經(jīng)濟系統(tǒng)分解為若干個較小的子系統(tǒng)，從而將復(fù)雜系統(tǒng)構(gòu)成一個結(jié)構(gòu)模型，該模型具有多級遞階的特點。解釋結(jié)構(gòu)模型隸屬于概念模型，由于該模型能將含糊不明的思想以直觀性的結(jié)構(gòu)關(guān)系進行表示，從而能更客觀地分析問題，因此被廣泛應(yīng)用于運輸、教育、醫(yī)療、自然災(zāi)害風(fēng)險控制、技術(shù)與績效評估、風(fēng)險管理與控制、標(biāo)準(zhǔn)制定、產(chǎn)品服務(wù)系統(tǒng)、供應(yīng)商開發(fā)與管理、供應(yīng)鏈管理、移動支付等領(lǐng)域。

求解可達矩陣和要素集合的級間劃分是解釋結(jié)構(gòu)模型計算中的兩個核心部分，但當(dāng)處理的系統(tǒng)要素較多時，頻繁進行交集運算使計算較為繁瑣。鑒于解釋結(jié)構(gòu)模型的應(yīng)用范圍較廣，一些國內(nèi)學(xué)者為了更好地運用該方法解決實際問題，改進了模型級間劃分方法，在減少計算量的同時提高了工作效率。目前系統(tǒng)級間劃分的改進方法主要分為4種：①無需求出可達矩陣，級間劃分能在鄰接矩陣上直接進行;②先計算出可達矩陣，然后在可達矩陣上計算可達集等，再根據(jù)計算結(jié)果進行級間劃分;③需先求出可達矩陣中行元素為1的個數(shù)，然后根據(jù)由少到多的原則對可達矩陣重新進行排列;④ISM一陣上作業(yè)法，雖然該方法比其它級間劃分改進方法更為簡便，但采用了復(fù)雜的圖論方法進行理論證明，不利于社會科學(xué)領(lǐng)域的科研工作者理解，因此在實際應(yīng)用中大多使用原級間劃分方法。

本文將深入解析原級間劃分方法基本原理，為ISM方法提供一種新詮釋，并在此基礎(chǔ)上給出對應(yīng)算法，以期減少計算步驟、提高運算效率。

1 解釋結(jié)構(gòu)模型方法步驟

建立解釋結(jié)構(gòu)模型的主要步驟為：

（1）確定系統(tǒng)構(gòu)成要素。

（2）建立鄰接矩陣。

（3）建立可達矩陣。

（4）系統(tǒng)各要素級間劃分。設(shè)系統(tǒng)要素集合N={s_i/i=1，2，…，n}，且劃分級次為k，級間劃分表示為L（n）=[L₁，L₂…，L₃]。其中L₁，L₂，…，L_k是系統(tǒng)要素自上而下的k個級次。定義第0級要素所構(gòu)成的集合為空集，即L₀=ψ，則L_p迭代算法為：

（5）建立ISM。根據(jù)各要素層級關(guān)系建立解釋結(jié)構(gòu)模型。

2 級間劃分方法基本原理解析及其算法

系統(tǒng)要素集合為：

N={s_i/i=1，2，…，n}

系統(tǒng)要素s_i與有向圖節(jié)點相互對應(yīng)。

2.1 圖論中相關(guān)概念

回路：閉鏈或回路的起點和終點為同一點。

有向圖：有向邊和節(jié)點組成的網(wǎng)絡(luò)圖可以表示為G={E，S}，G為有向圖，E為有向邊集合，S為節(jié)點集合。

鄰接矩陣：描述圖中每個節(jié)點之間兩兩關(guān)系的矩陣表示形式，其反映了系統(tǒng)各要素之間的直接對應(yīng)關(guān)系。

匯點：有且僅有有向邊進入，但沒有有向邊離開的節(jié)點。在鄰接矩陣中若行元素全部為零，則該行對應(yīng)節(jié)點即為匯點。

可達矩陣：描述有向圖各個節(jié)點間經(jīng)過一定長度通路后能夠到達程度的矩陣形式。系統(tǒng)各要素間的直接或間接關(guān)系能通過可達矩陣加以描述。

縮減可達矩陣：若可達矩陣中兩節(jié)點對應(yīng)的行與列元素相同，則兩節(jié)點組成回路集，回路集中其它節(jié)點可通過其中一個節(jié)點表示，刪掉其余節(jié)點即可完成對可達矩陣的化簡。

2.2 要素集合相關(guān)概念

設(shè)要素集合為N={s_i/i=1，2，…，n}。

前因集A（s_i）：該集合匯集了可達矩陣中第s_i列中所有矩陣元素為1的行對應(yīng)的要素，即要素s_i能夠到達的要素集合為：A（s_i）={s_j∈N/m_ji=1}。

可達集R（S_i）：該集合匯集了可達矩陣中第s_i行中所有矩陣元素為1的列對應(yīng)的要素，即要素s_i能夠到達的要素集合為：R（s_i）={s_j∈/m_ij=1}。

最高級要素集合H：指沒有比它更高級別的要素可以達到，在前因集中包括要素s_i本身與可以到達它的下一級要素，在可達集R（s_i）中只包含其本身，即：

H={s_iN/R（S_i）∩A（s_i）=R（s_i）}

2.3 級間劃分方法基本原理解析

由上一節(jié)概念對級間劃分的基本原理作進一步解析，可得到以下性質(zhì)：

性質(zhì)：若有向圖中不存在回路，則有向圖匯點與最高級要素集合中的要素相對應(yīng)。

證明：設(shè)N={s_i/i=1，2，…，n}為系統(tǒng)要素集合，N中要素s_i與有向圖中的節(jié)點s_i相對應(yīng)。

證明（反證法）：若有向圖中不存在回路，則R（s_i）∩A（s_i）={s_i}。

設(shè)R（s_i）∩A（s_i）中包含s_i和s_j（i≠j），由上一節(jié)前因集和可達集定義可知，s_i與s_j可以相互到達，說明在s_i與s_j之間形成了回路，與假設(shè)矛盾。因此，若有向圖中不存在回路，則：

R（s_i）∩A（s_i={s_i}

根據(jù)該結(jié)論可推出最高級要素集合H滿足以下條件：

H={S_i∈N/R（S_i）={S_i}}

再根據(jù)可達集定義，R（S_i）={S_i}是指要素S_i可到達的要素只有S_i本身，即要素S_i只能到達其本身而不能到達其它要素，對應(yīng)行元素全部為0。因此，根據(jù)上節(jié)定義可知要素S_i是有向圖對應(yīng)的匯點。

綜上所述，最高級要素集合中的要素即對應(yīng)有向圖的匯點，證畢。

2.4 級間劃分算法

ISM一陣上作業(yè)法中的級間劃分方法可由上述性質(zhì)直接得到，詳細(xì)步驟如下：

（1）求解可達矩陣M的縮減可達矩陣M'。

（2）去掉縮減可達矩陣M'中S_i可到達其本身的關(guān)系，也即將矩陣M'中的對角線元素全部變?yōu)?，得到矩陣M。

（3）設(shè)M將系統(tǒng)要素劃分為k個級次，系統(tǒng)中自上而下的k個級次分別為L₁，L₂，…，L_k。定義空集是第0級要素構(gòu)成的集合，即L₀=ψ，并令M₀=M，則L_p的迭代算法為：

2.5 計算量比較

為證明ISM中的優(yōu)化算法計算更為簡便，本節(jié)將對傳統(tǒng)方法與優(yōu)化算法計算量進行比較，具體如下：

設(shè)M為可劃分為k個級次的n階縮減可達矩陣，N（i）（0≤i≤k-1）為第i級要素個數(shù)，其中令N（0）=0，則傳統(tǒng)ISM方法計算量為：

（1）求M的前因集R（S₁），比較n²次。

（2）求M'的先行集A（S_i），比較n²次。

（3）求前因集與先行集的交集R（S_i）∩A（S_i），比較n次。

（4）尋找R（S_i）=R（S_i）∩A（S_i）的第1級要素，比較n次。

綜合以上分析，要求得縮減可達矩陣M'的第1級要素，需要的計算量為：

n²+n²+n=2n²+2n

同理，可求得第2，3，…，k級要素所需計算量分別為：

即減少了一倍左右的計算量，說明優(yōu)化算法比傳統(tǒng)方法更加簡潔，運算速度更快。

3 實例分析

為了更加直觀地說明本文提出方法的簡潔性和有效性，本節(jié)將以文獻中的可達矩陣為例（見表1），應(yīng)用上一節(jié)提出的算法對系統(tǒng)要素進行級間劃分。

第1步：輸入可達矩陣M。

第2步：從第一行起循環(huán)比較每一行與其它行數(shù)據(jù)。

第3步：刪除重復(fù)數(shù)據(jù)行，計算縮減可達矩陣M。根據(jù)表1中的可達矩陣M求縮減矩陣M'，由于沒有相同的行與列，因此縮減可達矩陣為M'=M。

第5步：循環(huán)遍歷矩陣M，IF次行全為0，則為第1級

4 結(jié)語

通過對ISM中級間劃分方法的基本原理作進一步解析，發(fā)現(xiàn)級間劃分的本質(zhì)為：若在有向圖中不存在回路，則最高級要素集合中的要素與有向圖中的匯點相互對應(yīng)，一次能直接從縮減可達矩陣中找出有向圖匯點，從而更方便、快捷地對系統(tǒng)要素進行分層，進而對解釋結(jié)構(gòu)模型方法進行優(yōu)化。為方便計算機實現(xiàn)，本文給出相應(yīng)優(yōu)化算法，并通過實證分析驗證算法的可行性。因此，本文研究結(jié)果為ISM中的級間劃分方法提供了一種新詮釋。