基于案例决策理论的仿真任务共同体服务选择算法

汪　霆,刘高峰

(海军工程大学电子工程学院,湖北 武汉　430033)

基于案例决策理论的仿真任务共同体服务选择算法

汪霆,刘高峰

(海军工程大学电子工程学院,湖北 武汉430033)

摘要:资源分配优化是面向服务(SOA)的大型多用途仿真系统的关键问题,而含有不确定状态或效果的服务选择是资源分配优化中的一个难点。针对以上问题,提出了构建仿真任务共同体的方法,基于案例的决策理论(CBDT)的思想,设计了一种不确定型仿真任务共同体服务选择算法(CBDSSA)。算法通过服务选择案例相似度的层次化运算,生成相似历史案例集,计算得到相似历史案例的方案效用值,最终评估出目标服务选择方案综合效用值并排序备选。算例验证表明,算法约束条件少,层次结构分明,运算结果直观,为仿真任务共同体服务选择问题提供了一种新的思路和实践手段,对大型多用途仿真系统资源分配优化研究具有一定的参考价值。

关键词:面向服务;仿真系统;基于案例的决策理论;仿真任务共同体;服务选择

通常,仿真系统中的“资源”可以分为:以数据、模型和算法等为特征的基础类资源;以仿真建模工具、运行支撑软件、管理类设施等为特征的仿真支撑类资源;以功能应用、模拟器材等为特征的仿真应用类资源[1]。在分布式仿真环境下,应对作战训练、方案推演、装备论证和装备试验等多种类型的联合仿真应用,克服地域和平台限制,实现仿真资源的动态配置与优化组合,满足异地/异构仿真单元的功能集成和信息交互,是仿真系统重组重构研究的一个难点问题[2]。以往采用分布式仿真技术[3]构建的仿真系统一般都是刚性的,需要在确定的环境下,按照预定的目标以及确定的仿真流程运行,仿真资源的使用模式相对固化,已不能全面满足日趋复杂的多用途仿真系统柔性重组的应用需要。随着国内外关于体系结构技术的持续研究表明[4-8],面向服务(SOA)体系结构以其具有的服务重用性、服务互操作性及服务之间的松耦合性等优势,已成为多用途仿真系统中的关键技术之一。在仿真任务需求牵引下,构建仿真任务共同体,是面向服务的仿真系统实现仿真资源按需组合与高效利用,最终满足仿真系统多用途化目标的有效手段,其目的在于利用仿真任务共同体搭建某一仿真任务阶段的临时性的逻辑功能仿真系统,如既可是作战模拟训练系统,也可是作战方案推演系统或武器装备论证仿真系统等,并能够灵活的组合和解聚。但是,在构建仿真任务共同体过程中,随着仿真系统规模的扩大和新加入服务增多,将会出现大量服务的运行效果或某些服务状态无法量化的情况,从这些含有不确定运行效果或状态的备选服务中选择出仿真任务共同体所需服务是一个首要解决的难点问题。

一般解决这类问题的办法可以采用基于案例的推理方法(case-based reasoning, CBR)[9],通过计算目标案例与历史案例的相似性, 然后提取具有最大相似性的历史案例, 并将提取出的历史案例中的决策方案作为目标案例的解决方案。但需要说明的是: 运用基于CBR的决策方法, 并没有考虑到提取出的历史案例所对应方案的具体实施效果, 所以不能保证提取出的决策方案实施效果最优,事实上往往容易出现提取出的决策方案的实施效果较差的情形,因此,传统CBR方法有可能会影响服务选择的结果或质量。基于案例的决策理论(CBDT)[10]则是对CBR方法的一种改进,该方法不仅仅计算目标案例和历史案例的相似度,并且关联和考虑了相似历史案例的具体实施效果。

本文在基于案例的决策理论基础上,设计了一种不确定型仿真任务共同体服务选择算法(CBDSSA),能够在无法预先获取服务全部状态或实施效果的情况下,通过对服务选择案例相似度的层次化的运算,提取出目标案例的相似历史案例,并在计算相似度和效用值的基础上确定出每个备选方案的综合效用值, 最终依据综合效用值的大小对备选方案排序和优选,以解决广义不确定型服务选择问题。

1基本问题描述

仿真任务共同体服务选择算法中，仿真任务共同体是主体,服务质量是标准,服务选择是手段。三者共同构成了算法的应用环境,必须准确定义与界定。

1.1仿真任务共同体定义

目前,任务共同体尚无一致的理解和定义。文献[11]通过对网络中心化仿真的研究,给出了仿真任务共同体的概念:“为了完成某一共同的仿真任务,由分布在网络上面的相关仿真资源和设施组成的虚拟组织,类似于HLA 联邦或传统的仿真系统的概念,但它是虚拟系统,当任务执行完毕就解散。仿真任务共同体由若干成员构成,成员主要是仿真应用类资源,也包括仿真支撑类中的数据采集、仿真控制等仿真管理设施资源。”这一定义是基于未来网络栅格条件下的网络中心化仿真概念,强调了组成任务共同体节点的类别是应用类资源及仿真管理设施,没有明确仿真实装节点以及数据模型等的作用,同时,这一定义也不是面向服务的,具有一定的局限性。

仿真任务共同体实际上是一种目的性较强的临时性的仿真系统。本文在文献[12]基础上,将多用途仿真系统中的仿真任务共同体定义为:在共同的仿真任务牵引下,将分布式的仿真节点群、对应服务群、管理类设施、数据模型库等仿真软硬件资源,构成一个具有特定功能和用途的仿真逻辑系统,并能够根据不同的仿真应用需要灵活的聚合和解聚,最终实现仿真系统资源优化分配和仿真任务管理的目标,如图1所示。

图1　任务共同体定义描述

1.2服务质量描述

在明确仿真任务共同体的定义和其重要意义基础上,对仿真任务共同体服务选择的标准和依据进行规范,这一标准和依据就是服务质量(QoS)[13-14]。为更好地对服务质量进行描述,选择6种具有代表性、共通性的非功能属性作为QoS指标,即服务代价P(Price)、服务执行时间E(Execution Time)、服务可靠性R(Reliability)、服务延迟D(Delay)、服务容量C(Capacity)和服务信誉Rep(Reputation)。用六元组的形式表示为

QoS=

其中,服务代价指服务运行需要占用的各类资源,如计算资源、网络资源等;服务执行时间指服务作为一种程序,获取输出结果所需时间;服务可靠性代表该服务在仿真系统中正常运行的可靠程度衡量;服务延迟指服务在服务请求方发出申请直至服务响应的时间延迟;服务容量是调用及被调用的能力指标,服务信誉指衡量服务能够被正常调用的度量。

1.3服务选择的界定

在仿真任务共同体中,存在多个仿真节点,每个仿真节点所对应的仿真服务群不是孤立存在的,而是有一定的交叉、包含等关系,且在同一服务群中能实现特定功能用途的服务存在一个或多个,这些服务具有不同的服务质量(QoS)以及特定的约束条件,如图2所示。

图2　任务共同体服务群关系描述

如何在复杂的仿真环境和不断变化的仿真条件下,从庞大服务群中快速选择出所需要求的服务,实现仿真节点各取所需,同时仿真任务共同体效益最大化(包括个体最优和整体最优)是需要解决的关键性问题,即仿真任务共同体服务选择。

按照服务相关信息可感知的程度,将仿真任务共同体服务选择分为两大类:确定型服务选择和广义不确定型[10]服务选择。若服务的全部状态、使用条件及效果均已知,则为确定型服务选择;但是若备选服务运行效果无法预期,服务参数无法完全量化的有限服务方案选择问题称为广义不确定型服务选择。

本文设计的CBDSSA算法以广义不确定型服务选择问题为研究对象,选取基于案例的决策理论(CBDT)为算法理论依据。

2基于CBDT的仿真任务共同体服务选择问题描述

在仿真任务共同体服务选择中,“案例”对应的是“服务”的选择与分配方案,可以是节点的服务选择方案,也可能是仿真任务共同体整体的分配方案。历史案例是存储在案例库中为了解决当前服务选择问题而可能被用来辅助决策的历史服务选择方案, 而目标案例是基于当前服务选择背景下,其可采取的备选服务选择方案加上虚拟的服务选择效果综合构成的案例。

为表述方便,设目标案例数M={1,2,…,m},历史案例数N={1,2,…,n},问题属性维度H={1,2,…,h},方案属性维度G={1,2,…,g},效果属性维度F={1,2,…,f},并明确几个集合如下。

1)设Z={(P1,C1,E1),(P2,C2,E2),…, (Pn,Cn,En)}表示由n个案例构成的历史案例集,其中(Pj,Cj,Ej)表示第i个历史案例,Pj,Cj,Ej分别代表“问题”、

“方案”和“效果”。记Pobj为目标问题,Cobj={C1obj, C2obj,…, Cmobj}为目标问题Pobj可采用的备选方案集,其中Ciobj表示第i个备选方案,记X为备选方案Ciobj的实施效果,在这里,X是未知的。因此,目标案例可以表示为(Pobj,Ciobj,X)。

将以上关系整理后如表1所示, 表中“问题”、“方案”及“效果”属性可以是数值型的,也可以是符号型描述[15-16]。

表1　问题、方案及效果属性描述

3基于案例决策方法的CBDSSA算法

为解决上述问题,从广义不确定型案例决策基本思想出发,提出基于案例决策的不确定型仿真任务共同体服务选择算法(CBDSSA),其基本流程如图3所示。

图3　CBDSSA算法流程图

3.1“问题”与“方案”的相似度计算

数值型属性:

(1)

符号型属性:

(2)

第二步:计算“方案”属性AlC在目标案例(Pobj,Ciobj,X)与历史案例(Pj,Cj,Ej)之间的相似度Simk(Cobj,Cj)。将计算公式设计为:

数值型属性:

(3)

符号型属性:

(4)

第三步:在“问题”属性相似度基础上,计算关于“问题”的目标案例与历史案例的相似度Sim(Pobj,Pj)。

设计为:

(5)

其中,Sim(Pobj,Pj)取值区间为(0,1],值越大表明历史案例中的问题与当前需解决的问题相识度越高。

计算公式为

(6)

其中，Sim(Ciobj,Cj) 取值区间为(0,1],值越大,表明历史案例中的方案与备选方案的相似度越高。

3.2构建相似案例集

3.3计算“问题-方案”组合的目标案例与历史案例相似度

(7)

3.4计算历史案例“实施效果”效用值

历史案例“实施效果”属性由数值型和语言型两类组成,要对不同历史案例实施效果的效用值进行计算,前提就是要对各属性值进行规范、量化。

其中,qjemax是相似历史案例集ZPC中qje属性最大值,此公式用以消除数值量纲影响,并做归一化处理。

语言型属性一般表示实施效果或者类似的表述类信息,在这里分为5个等级,记为:Scale={S1(优),S2(良),S3(中),S4(差),S5(极差)},对应数值为:S1=1,S2=0.8,S3=0.6,S4=0.4,S5=0.2。

由此,可得到相似历史案例(Pj,Cj,Ej)实施效果效用值u(Ej):

(8)

3.5计算综合效用值及方案优选

计算备选方案Ciobj综合效用值Ui：

(9)

最后,根据Ui值的大小对备选方案进行排序,并从中选出最优方案。

4算例验证

4.1算例验证背景设定

通过专家打分方式,确定出“问题”的属性权重向量、“方案”属性权重向量以及方案实施的“效果”属性权重向量分别为：

wp=(0.19, 0.21, 0.20, 0.18, 0.23),

wC=(0.24, 0.23, 0.22, 0.14, 0.08, 0.09),

wE=(0.6,0.2,0.2),

设定相似度阈值为εP=0.5,εC=0.8。

从舰艇作战仿真系统中抽取10个该节点的历史服务选择案例,与3个备选方案一并列入CBDSSA算法计算。其中,表2为历史案例问题属性,表3是目标案例问题、方案及效果属性(未知),表4为历史案例“方案”及“效果”。

4.2算例验证过程

4)在对“效果”属性归一化处理基础上(表7),依据式(8)计算历史案例“实施效果”效用值u(Ej),如表8所示。

表2　历史案例问题属性

表3　目标案例问题、方案及效果属性

表4　历史案例“方案”及“效果”

表5　相似度Siml(Pobj,Pj)及Sim(C1obj,Cj)计算结果

表6　相似度Sim(Pobj,Cobj),(Pj,Cj) 计算结果

表7　“效果”属性归一处理

表8　相似历史案例效用值

5)依据式(9)计算备选方案Ciobj综合效用值Ui,可得U1=0.75,U2=0.65,U3=0.67,在三个备选方案中,U1≻U3≻U2,根据准则,可以选择服务一为最佳方案。

4.3算例验证分析

1)本次算例验证中,案例“问题”设置为5个属性,“方案”设定为6个属性,“效果”设定为3个属性,各组成的属性数量是可以根据需要自由设定的,例如,算例中“方案”选取了服务质量(QoS)的6项指标作为参数,实际在服务选择过程中,服务质量的6项指标不一定全部作为考察依据,同时,其他非服务指标也可纳入考察范围,视具体情形而定。

2)算例设定的权重向量和相似度阈值采取的是专家打分方式,其依据是各属性在仿真系统中起到的作用大小的人工价值评判。例如,“问题”属性向量较为平均,其中可使用时段要求略高,说明系统要求备选服务实时可用,这贴合模拟训练实时性较高的实际;“方案”属性向量值中服务代价、执行时间和可靠性等项取值较高,而服务容量等项权重略低,说明服务6个质量属性中,服务代价、执行时间等指标在服务质量中起到的作用更为重要,服务容量等指标则相对次要;“效果”属性向量取值表明“服务满意度评价”作为一个综合指标,在表达服务效果上更为关键;εP取0.5,εC取0.8的目的是提高“方案”选择门槛,其意义是在“问题”具有一定相似度基础上选择出相似度更高的服务“方案”。以上分析说明,算例中通过专家打分方式设定的权重向量选取与仿真系统属性的价值取向是一致的,具有可信性。

3)由算例验证结果可以看出,“目标案例一”与“历史案例一”在“问题”和“方案”属性上最为相似,且从“效果”属性上可以看出,相似历史案例的“效果”值也较高,说明算例验证确实选择出了最优方案。需要指出的是,从表6中可以看出,“备选服务一”数值最高,是当前最优服务,但是“备选服务二”具有较高效果值的相似历史案例最多,说明“备选服务二”适用性更广,“备选服务三”则性能较为折中。这也说明CBDSSA算法不仅能够找出当前最优服务选择方案,而且能够给出有价值的后备选择,具有现实意义。

5结束语

基于案例决策的不确定型仿真任务共同体服务选择算法(CBDSSA)约束条件少,层次结构分明,运算结果直观,是解决仿真任务共同体广义不确定型服务选择问题的一种有效的新思路和新方法,对大型多用途仿真系统资源分配优化研究具有一定的参考价值。下一步将继续研究CBDT理论在服务组合上的应用。

参考文献:

[1]张睿,王之腾,张宏军，等.浅析建模与仿真领域的现状与发展趋势[J].系统仿真学报,2013,25(8):52-55

[2]范林军,董红林,凌云翔，等.分布式仿真系统中的全局一致性问题研究[J].计算机工程与科学,2016,38(1):131-135

[3]周平,苏银科,沈超. 基于DDS 的分布式数字仿真系统设计与实现[J].系统仿真学报,2014,26(8):1678-1683

[4]Zhang Rui, Wang Zhiteng, Mao Shaojie, Sun Xigang. CoST: A Service-Oriented Simulation Architecture[J]. Journal of Theoretical and Applied Information Technology, 2013， 48(3): 1584-1589.

[5]陈钊,赵斯强,宋彬,等.面向服务的集成式海军作战指挥训练系统构建[J].指挥控制与仿真,2015,37(5):82-87.

[6]史扬,董汉权,陆铭华.面向服务的可组合可重用仿真技术研究[J].系统仿真学报,2014,26(7):1522-1526.

[7]龚立,刘高峰,等. SOA下军用仿真系统集成研究[J].武汉理工大学学报(交通科学与工程版),2010,34(6):1121-1128.

[8]Xitong Li, Stuart E, Madnick. Understanding the Dynamics of Service-Oriented Architecture Implementation[J]. Journal of Management Information Systems,2015,32(2):104-133.

[9]李晓辉,刘妍秀.基于实例推理机制(CBR)综述[J].长春大学学报,2006,16(4):68-70.

[10]倪志伟,李建洋,李锋刚,等.案例决策技术及案例决策支持系统研究综述[J].计算机科学,2009,36(11):18-23.

[11]毛少杰,李玉萍,等.网络中心化仿真概念与方法研究[J].系统仿真学报,2010,22(7):1660-1663.

[12]汪霆,刘高峰.一种TCSM模式的服务化模拟训练系统研究[J].计算机与数字工程,2015,43(12):2199-2203.

[13]孙黎阳,李阳,等. 网络中心化仿真任务共同体服务选择算法研究[J].计算机研究与发 展,2014,51(3):650-660.

[14]孙黎阳,林剑柠,等.基于改进粒子群优化算法的网络化仿真任务共同体服务选择[J].兵工学报,2012,33(11):1393-1403.

[15]Gilboa I, Schmeidler D. Case-based decision theory[J]. The Quarterly Journal of Economics, 1995, 110(3): 605-639.

[16]Golosnoy V, Okhrin Y. General uncertainty in portfolio selection: A case-based decision approach[J]. Journal of Economic Behavior& Organization, 2008, 67(3/4): 718-734.

[17]李永海,樊治平,李铭洋.解决广义不确定型决策问题的案例决策方法[J].系统工程学报,2014,29(1):21-28.

[18]王清,赵勇,等.基于阈值的案例决策方法及其在创新设计中的应用[J].控制与决策, 2010,25(10): 1562-1566.

[19]顾东晓,李兴国,梁昌勇,等.案例检索及权重优化方法研究及应用[J].系统工程学报, 2009,24(6): 764-768.

Study of Simulation Task Community Service Selection Algorithm Based on Case-based Decision Theory

WANG Ting,LIU Gao-feng

(College of Electronic Engineering, Naval University of Engineering, Wuhan 430033， China)

Abstract:Resources allocation and optimization becomes a key problems during the research of service-oriented large-scale multipurpose simulation system, in the meanwhile service selection with unknown status is one of the difficulties in resources allocation and optimization. To solve the problems, the paper proposes a method of simulation task community, designed a task community service selection algorithm (CBDSSA) based on case-based decision theory. By the means of coherent calculation, the algorithm can successfully build similar historical case set and create the utility of its implementation effect. Finally, the overall utilities of each alternative service selection cases are calculated and sorted by integrating the similarities and utilities. The algorithm needs fewer constraints and has strong logicality and practical applicability. It provides a new method of practice in task community service selection, and has reference value for the research of service selection of large-scale multipurpose simulation system.

Key words:SOA; simulation system; case-based decision theory; simulation task community; service selection

文章编号：1673-3819(2016)03-0039-07

收稿日期：2016-03-08

作者简介：汪霆(1986-),男,四川达州人,硕士研究生,研究方向为作战指挥系统。 刘高峰(1965-),男,博士,副教授。

中图分类号:TP391.9；E211

文献标志码:A

DOI:10.3969/j.issn.1673-3819.2016.03.007

修回日期： 2016-03-31