一种解释结构模型的优化算法研究

来源:用户上传      作者:

　　摘要：解释结构模型被广泛应用于医疗、教育等领域，但相关理论发展较为缓慢。为加快解释结构模型的计算速度，丰富解释结构模型相关理论，通过对系统各要素所对应有向图的本质关系进行分析，对该模型中的级间划分方法作更深一步解析并给出优化算法，发现有向图中若不存在回路，则有向图汇点对应的是最高级要素集合中的要素，因此汇点可以从缩减可达矩阵中直接找出，从而能对复杂系统要素更快地进行分层。对应的优化算法相比传统方法减少了一倍左右的计算量，并通过实证分析进行验证。该研究结果为解释结构模型方法优化提供了一种新诠释。
　　关键词：解释结构模型;缩减可达矩阵;汇点;优化算法
　　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={si/i=1，2，…，n}，且划分级次为k，级间划分表示为L（n）=[L1，L2…，L3]。其中L1，L2，…，Lk是系统要素自上而下的k个级次。定义第0级要素所构成的集合为空集，即L0=ψ，则Lp迭代算法为：
　　（5）建立ISM。根据各要素层级关系建立解释结构模型。
　　2 级间划分方法基本原理解析及其算法
　　系統要素集合为：
　　N={si/i=1，2，…，n}
　　系统要素si与有向图节点相互对应。
　　2.1 图论中相关概念
　　回路：闭链或回路的起点和终点为同一点。
　　有向图：有向边和节点组成的网络图可以表示为G={E，S}，G为有向图，E为有向边集合，S为节点集合。
　　邻接矩阵：描述图中每个节点之间两两关系的矩阵表示形式，其反映了系统各要素之间的直接对应关系。
　　汇点：有且仅有有向边进入，但没有有向边离开的节点。在邻接矩阵中若行元素全部为零，则该行对应节点即为汇点。
　　可达矩阵：描述有向图各个节点间经过一定长度通路后能够到达程度的矩阵形式。系统各要素间的直接或间接关系能通过可达矩阵加以描述。
　　缩减可达矩阵：若可达矩阵中两节点对应的行与列元素相同，则两节点组成回路集，回路集中其它节点可通过其中一个节点表示，删掉其余节点即可完成对可达矩阵的化简。
　　2.2 要素集合相关概念
　　设要素集合为N={si/i=1，2，…，n}。
　　前因集A（si）：该集合汇集了可达矩阵中第si列中所有矩阵元素为1的行对应的要素，即要素si能够到达的要素集合为：A（si）={sj∈N/mji=1}。
　　可达集R（Si）：该集合汇集了可达矩阵中第si行中所有矩阵元素为1的列对应的要素，即要素si能够到达的要素集合为：R（si）={sj∈/mij=1}。
　　最高级要素集合H：指没有比它更高级别的要素可以达到，在前因集中包括要素si本身与可以到达它的下一级要素，在可达集R（si）中只包含其本身，即：
　　H={siN/R（Si）∩A（si）=R（si）} 　　2.3 级间划分方法基本原理解析
　　由上一节概念对级间划分的基本原理作进一步解析，可得到以下性质：
　　性质：若有向图中不存在回路，则有向图汇点与最高级要素集合中的要素相对应。
　　证明：设N={si/i=1，2，…，n}为系统要素集合，N中要素si与有向图中的节点si相对应。
　　证明（反证法）：若有向图中不存在回路，则R（si）∩A（si）={si}。
　　设R（si）∩A（si）中包含si和sj（i≠j），由上一节前因集和可达集定义可知，si与sj可以相互到达，说明在si与sj之间形成了回路，与假设矛盾。因此，若有向图中不存在回路，则：
　　R（si）∩A（si={si}
　　根据该结论可推出最高级要素集合H满足以下条件：
　　H={Si∈N/R（Si）={Si}}
　　再根据可达集定义，R（Si）={Si}是指要素Si可到达的要素只有Si本身，即要素Si只能到达其本身而不能到达其它要素，对应行元素全部为0。因此，根据上节定义可知要素Si是有向图对应的汇点。
　　综上所述，最高级要素集合中的要素即对应有向图的汇点，证毕。
　　2.4 级间划分算法
　　ISM一阵上作业法中的级间划分方法可由上述性质直接得到，详细步骤如下：
　　（1）求解可达矩阵M的缩减可达矩阵M'。
　　（2）去掉缩减可达矩阵M'中Si可到达其本身的关系，也即将矩阵M'中的对角线元素全部变为0，得到矩阵M。
　　（3）设M’将系统要素划分为k个级次，系统中自上而下的k个级次分别为L1，L2，…，Lk。定义空集是第0级要素构成的集合，即L0=ψ，并令M0=M，则Lp的迭代算法为：
　　2.5 计算量比较
　　为证明ISM中的优化算法计算更为简便，本节将对传统方法与优化算法计算量进行比较，具体如下：
　　设M’为可划分为k个级次的n阶缩减可达矩阵，N（i）（0≤i≤k-1）为第i级要素个数，其中令N（0）=0，则传统ISM方法计算量为：
　　（1）求M’的前因集R（S1），比較n2次。
　　（2）求M'的先行集A（Si），比较n2次。
　　（3）求前因集与先行集的交集R（Si）∩A（Si），比较n次。
　　（4）寻找R（Si）=R（Si）∩A（Si）的第1级要素，比较n次。
　　综合以上分析，要求得缩减可达矩阵M'的第1级要素，需要的计算量为：
　　n2+n2+n=2n2+2n
　　同理，可求得第2，3，…，k级要素所需计算量分别为：
　　即减少了一倍左右的计算量，说明优化算法比传统方法更加简洁，运算速度更快。
　　3 实例分析
　　为了更加直观地说明本文提出方法的简洁性和有效性，本节将以文献中的可达矩阵为例（见表1），应用上一节提出的算法对系统要素进行级间划分。
　　第1步：输入可达矩阵M。
　　第2步：从第一行起循环比较每一行与其它行数据。
　　第3步：删除重复数据行，计算缩减可达矩阵M’。根据表1中的可达矩阵M求缩减矩阵M'，由于没有相同的行与列，因此缩减可达矩阵为M'=M。
　　第5步：循环遍历矩阵M，IF次行全为0，则为第1级
　　4 结语
　　通过对ISM中级间划分方法的基本原理作进一步解析，发现级间划分的本质为：若在有向图中不存在回路，则最高级要素集合中的要素与有向图中的汇点相互对应，一次能直接从缩减可达矩阵中找出有向图汇点，从而更方便、快捷地对系统要素进行分层，进而对解释结构模型方法进行优化。为方便计算机实现，本文给出相应优化算法，并通过实证分析验证算法的可行性。因此，本文研究结果为ISM中的级间划分方法提供了一种新诠释。
转载注明来源:https://www.xzbu.com/8/view-15278162.htm