一種解釋結構模型的優化算法研究

彭曉易 李穎 李晶

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

關鍵詞：解釋結構模型;縮減可達矩陣;匯點;優化算法

DOI：10.11907/rjdk.191537 開放科學（資源服務）標識碼（OSID）：

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

0 引言

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

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

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

1 解釋結構模型方法步驟

建立解釋結構模型的主要步驟為：

（1）確定系統構成要素。

（2）建立鄰接矩陣。

（3）建立可達矩陣。

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

（5）建立ISM。根據各要素層級關系建立解釋結構模型。

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

系統要素集合為：

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

系統要素s_i與有向圖節點相互對應。

2.1 圖論中相關概念

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

有向圖：有向邊和節點組成的網絡圖可以表示為G={E，S}，G為有向圖，E為有向邊集合，S為節點集合。

鄰接矩陣：描述圖中每個節點之間兩兩關系的矩陣表示形式，其反映了系統各要素之間的直接對應關系。

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

可達矩陣：描述有向圖各個節點間經過一定長度通路后能夠到達程度的矩陣形式。系統各要素間的直接或間接關系能通過可達矩陣加以描述。

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

2.2 要素集合相關概念

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

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

可達集R（S_i）：該集合匯集了可達矩陣中第s_i行中所有矩陣元素為1的列對應的要素，即要素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 級間劃分方法基本原理解析

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

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

證明：設N={s_i/i=1，2，…，n}為系統要素集合，N中要素s_i與有向圖中的節點s_i相對應。

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

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

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

根據該結論可推出最高級要素集合H滿足以下條件：

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

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

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

2.4 級間劃分算法

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

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

（2）去掉縮減可達矩陣M'中S_i可到達其本身的關系，也即將矩陣M'中的對角線元素全部變為0，得到矩陣M。

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

2.5 計算量比較

為證明ISM中的優化算法計算更為簡便，本節將對傳統方法與優化算法計算量進行比較，具體如下：

設M為可劃分為k個級次的n階縮減可達矩陣，N（i）（0≤i≤k-1）為第i級要素個數，其中令N（0）=0，則傳統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級要素所需計算量分別為：

即減少了一倍左右的計算量，說明優化算法比傳統方法更加簡潔，運算速度更快。

3 實例分析

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

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

第2步：從第一行起循環比較每一行與其它行數據。

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

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

4 結語

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