支持扩展QoS约束的动态虚拟企业伙伴选择模型

张以文 倪志伟 王 力 李志东

1．合肥工业大学过程优化与智能决策教育部重点实验室，合肥，230009 2．安徽大学，合肥，230039

0 引言

虚拟企业以其低成本、快速响应市场机遇以及良好的适应能力，越来越受到业界的重视。合理的伙伴选择是虚拟企业成功的关键。目前，虚拟企业的伙伴选择研究主要有两条技术路线：①基于多属性决策方法研究［1－3］，基于 A HP（层次分析法）、DEA（数据包络分析）、模糊决策等方法和理论来进行伙伴选择，这些方法还只是局部搜索的优化方法，可操作性较差；②基于智能算法的伙伴选择［4－7］，但已有研究大多是基于静态虚拟企业背景下进行的，不能很好地体现伙伴选择的动态性。传统的静态虚拟企业组织结构相对固定，成员数量相对稳定，在建立虚拟组织时，需要一致的成员企业的业务接口以及相互之间统一的文件交互格式［8］，代价高，可伸缩性差。企业间异构的应用系统平台、不一致的数据格式、信息集成和共享困难是导致静态虚拟企业滞后的合作伙伴发现和选择的重要原因。随着信息技术与网络技术的飞速发展，网络经济已成为重要的经济模式，动态虚拟企业成为网络经济的主要表现形式，动态虚拟企业具有松散耦合、异构性、不稳定性和动态性等特点。但随着网络中潜在的虚拟企业合作伙伴明显增多，使得动态虚拟企业对于合作伙伴的选择、评价和动态绑定变得更加复杂。Web服务（WS）技术是良好的解决方案，基于Web服务技术的动态虚拟企业集成已成为人们研究的热点。Web服务技术为企业集成双方提供了一种松散藕合的机制，特别是统一描述、发现和集成（universal description discovery and integration，UDDI）机制能为企业的注册提供统一的管理平台，使企业能够实时动态地发现现有的和潜在的合作伙伴，集成新的企业合作伙伴，从而使虚拟企业合作伙伴的动态选择成为可能。但目前的研究还只主要集中在解决企业间系统异构性和提高信息集成及共享等方面［9－10］，较少涉及 Web服务架构下的动态虚拟企业伙伴选择问题，尤其是已有UDDI的研究工作缺乏对注册企业服务能力的评价机制，未能充分发挥Web服务架构的显著优势，对动态虚拟企业合作伙伴的选择产生了严重障碍。本文提出一种基于Web服务架构的动态虚拟企业伙伴选择扩展模型（dynamic virtual enterprise partner selection extended model，DVEPSEM）来支持大规模的动态虚拟企业伙伴选择，通过实验验证了模型的有效性和合理性。

图1 动态虚拟企业伙伴选择扩展模型

1 动态虚拟企业伙伴选择扩展模型

Web服务技术的出现为动态虚拟企业伙伴选择提供了技术支撑，但现有Web服务架构下的服务发现算法研究主要考虑应答时间、服务器负载、服务成本和网络延迟等因素。在动态虚拟企业伙伴选择中更重要的是应考虑商务合作层面的因素，如成本因素、生产时间、合作信任度、风险因素等，需要对现有 Web服务架构进行扩展，提出了一种动态虚拟企业伙伴选择扩展模型，如图1所示。

1．1 DVEPSEM模型分析

定义1 WS＝｛Function，QoS｝。WS为企业Web服务，其中，Function是企业服务的功能属性集合，表示企业的某种服务能力，QoS是服务质量（QoS）的属性集合。

定义2 QoS ＝ ｛QoStrad，QoSextr｝。QoStrad是指传统服务质量（QoStrad）属性集合（如应答时间、服务器负载等），QoSextr是指企业商务合作层面的服务质量属性集合（如成本因素、产品质量和合作信誉度等），为伙伴选择提供依据。本文主要研究基于扩展QoS（QoSextr）的动态虚拟企业伙伴选择问题。

定义3 WS类（即企业服务类）是由不同企业发布、具有实现相同功能的一组企业服务集合，同一个企业服务类中企业功能相同，但各自的QoSextr性能不同。

（1）企业联盟UDDI机制接受WS的发布，并在领域本体的支持下（图1中弯曲虚线表示领域本体到相应服务类的映射）将企业WS按其服务功能进行分类，使得每个企业服务（或原子企业服务组合，考虑可能有若干小型企业合作完成一项子任务，看成一个服务）属于某个服务类（图1中矩形虚线表示一个服务类），利用本体对企业服务功能明确的形式化的规范说明，提高企业服务分类的精确性，消除信息语义的多重性以及信息关系的匮乏和非统一性问题。

（2）QoS监控系统负责企业服务类各服务QoSextr标准量化工作，并对企业服务QoSextr动态监督，接受客户企业反馈信息并实时动态更新企业QoSextr，为企业能力公正合理的评价提供保障，为伙伴选择提供决策信息（如服务质量、信誉度等）支持。

（3）核心企业是虚拟企业的发起者，将实现目标划分成若干个子任务，子任务之间可以并行执行，通过工作流引擎建立任务间的先序关系，如图2所示。其中，TKi表示目标任务组合中第i项子任务，从起始任务到终止任务路径表示虚拟企业实现目标任务的工作流程。伙伴选择的任务是为每类子任务从相应服务类中选择一个理想的企业服务共同构成一个企业服务组合，优化的企业服务组合即为动态虚拟企业伙伴选择的目标，以期达到以最快的速度、最低的成本、最好的质量实现企业目标，提高企业的敏捷性和快速响应市场的能力，成员组合一经确定，核心企业建立私有UDDI并向伙伴成员发送注册邀请。

图2 虚拟企业任务状态图

（4）伙伴企业为寻求市场机遇，将自己的能力封装成WS，发布到企业联盟UDDI，以期待与其他企业的合作，提高企业自身的竞争能力，当被某核心企业邀请时，对核心企业和合作目标进行评估，若接受邀请则在核心企业私有UDDI内注册，否则，反馈拒绝接受邀请的消息。

虚拟企业各个成员通过基于XML的SOAP协议作为标准通信协议，完成各个成员间应用程序的无缝集成。虚拟企业解散时各成员企业反馈相关合作企业信誉度等QoSextr信息。

为实现伙伴企业快速精确的查找，可选用OWL－S（语义 Web服务标识语言）来描述企业服务的知识本体，提供企业服务的词汇表，描述服务的语义，根据服务的Function进行推理。OWL－S主要通过Service Profile、Service Model和Ser vice Gr ounding三个类来描述服务做什么、如何做以及如何访问等三方面的语义，从而允许服务的自动发现、执行、组合和运行的监视。每一个服务轮廓都是Profile Ontology（轮廓本体）中定义的轮廓类（Class Ser vicePr ofile）的一个实例。如〈profile：profile r df：ID＝ “Profile Enterprise Web＿Ser vice”〉，在OWL－S中规范了一系列的属性来描述服务Profile Ontology，在原有属性的基础上进行属性扩展，利用“f unction Description”属性来描述服务的Function信息，利用“Qos Constraints”来描述企业QoSextr信息。企业服务类在“ServiceCategory”中加以描述。扩展Ser vice Pr ofile结构如图3所示。

图3 扩展Service Profile本体

1．2 基于DVEPSEM的伙伴选择数学模型

设TK ＝ ｛TKi｜i＝1，2，…，n｝为虚拟企业需要完成的n类子任务的集合，WSi＝｛wsij｜j＝1，2，…，mi｝为UDDI内能够完成子任务TKi的某候选企业服务类，mi为该服务类中服务数量。设Ii＝ ｛ti，qi，ci，…｝为服务类WSi的 QoSextr评价指标集合，其中，ti为时间指标，qi为质量指标，ci为价格指标，省略号为其他可选指标。每个服务类指标集合不同，但可取ti、qi、ci作为动态虚拟企业（因为动态虚拟企业要求快速的市场应变能力下以低廉的成本创造高质量的产品或服务）各服务类公共评价指标，即QoSextr＝｛生产时间，产品质量，生产成本｝。设核心企业对TKi类子任务合作伙伴的QoSextr约束为生产时间不超过tmaxi、产品质量不低于qmini、生产成本不高于cmaxi，则动态虚拟企业伙伴选择问题可描述为满足约束的多目标决策问题：

s．t．∀i，若 ∃j使得dij＝1，那么wsij必须满足：

式（1）中，当子任务间是并行关系时，取并行任务间的最大时间（图2中子任务TK2和TK3）。式（2）中，C1为虚拟企业各子任务花费（主要是企业自身成本估计）之和，C2为虚拟企业相邻任务（i→i＋1）间企业连接成本（如运输费用等），lwsij，ws（i＋1）k为 服 务 类 WSi中 的 服 务j 和 服 务 类WSi＋1中的服务k之间的连接成本，若wsij被选中则dij为1，否则为0。twsij、cwsij和qwsij分别为服务类WSi中的第j个服务所需的生产时间、生产成本和能够提供的服务质量。

以上指标可能在数量级上存在很大差异，为防止在决策中发生“大数吃小数现象”，按下式将各指标进行归一化处理：

按照式（5）负作用指标将式（3）转化为最小化问题：

对于∀wsi服务类集合，若wsij被选中，必须满足下式，即DVEPSEM模型下伙伴选择（多目标决策问题）转换为下式的组合优化问题：

其中，｛λi1，λi2，λi3｝为指标权重，满足，并行任务间求解时的最大时间。

2 基于DVEPSEM的伙伴选择改进算法

基于多约束的虚拟企业伙伴选择问题已被证明是NP问题［11］。自适应遗传算法（AGA）能够有效地解决此类问题，遗传算法具有很好的全局寻优能力。但是，随着信息技术与网络技术的飞速发展，网络中潜在的企业合作伙伴明显增多，问题的搜索空间变得越来越大，本文利用伙伴选择企业QoSextr约束问题本身的数学特征，在制定相关规则的基础上，较大程度地降低问题求解空间，提出了一种改进的IAGA算法，利用理想点法和欧氏距离构造相应的适应度函数，最后返回q个最优企业组合信息，为企业领导层或领域专家的进一步决策提供信息支持。

2．1 伙伴初步筛选

为减少服务类WSi搜索空间中的服务数量，制定以下规则：

规则1 在任一服务类WSi中，对于∀wsij（j＝1，2，…，mi），若合取式（4）不成立，则删除wsij。

规则2 在任一服务类WSi中，如果（qwsij≥qwsik）∧ （twsij≤twsik）∧ （c′wsij≤cwsik），j≠k，则删除wsik。其中，c′wsij＝cwsij＋max lwsij，ws（i＋1）k；k＝1，2，…，mi＋1。

2．2 算法准备

（1）编码方法。令 X ＝ ｛x1，x2，…，xn｝（xi＝1，2，…，mi）为任一染色体，xi为服务类WSi中的某一服务，如染色体｛2，4，1，5，3｝，表示子任务TK1选中了可完成该子任务的某服务类WSi中的企业服务wsi2，其余类似。

（2）交叉概率Pc和变异概率Pm：

式中，fmax和f为群体最大适应度和平均适应度；f′为两交叉个体较大的适应度；f为要变异个体的适应度；k1、k2、k3、k4取（0，1）区间的值。

对于不同的个体，适应度高的个体应给予保护，每个个体拥有不同的Pc和Pm。

（3）适应度函数设计。选用理想点法构造适应度函数，设有n个子任务构成的业务流程f1（x），f2（x），…，fn（x），对于每个目标函数分别有其最优值为f＋i。那么，可以将向量（f＋1，f＋2，…，f＋n）看作向量函数（f1（x），f2（x），…，fn（x））的正理想点。同理，将向量（f－1，f－2，…，f－n）看作向量函数（f1（x），f2（x），…，fn（x））的负理想点。基于欧式距离构造适应度函数为：

式中，l为目标函数个数（本文中l＝3）。

关于指标权重λij，对于同一个指标，不同的服务类由于企业完成任务性质不同可以赋以不同的权重。

2．3 算法描述

（1）按照规则进行伙伴初步筛选；

（2）初始化种群大小n，prior f itness［q］；

（3）随机产生初始种群X0；

（4）选择操作，采用轮盘选择策略进行个体选择；

（5）交叉操作，以概率Pc决定个体是否进行交叉操作，采用简单的双子双亲法，交配位随机取位；

（6）变异操作，以变异概率Pm指定其变异点，对变异点的基因值由除该基因值以外的随机产生的［1，mi］之间的数值取代；

（7）计算每个个体适应度值，进行适应度排序，将当前种群适应度前q个适应度值和相应个体信息保存到数组prior f itness［q］中；

（8）判断是否满足结束条件（文中将连续30代个体最大适应度值不变作为结束条件），如不满足则返回步骤（4），否则，返回q个最优个体及其相应适应度值信息prior f itness［q］（q＞1），算法结束。

算法最后返回q个最优个体，这q个个体满足成本低、响应速度快和服务质量高的要求，适应度值非常接近。然而适应度最高的个体并不一定是动态虚拟企业最理想的组合，因为在实际目标实施过程中，企业的合作信誉度、创新能力和服务水平等也是不容忽视的商务合作因素。另外，也可能出现返回的个体中，有一个或若干个企业服务由于企业自身某种客观原因不能接受核心企业请求，即可能出现若干企业服务不可用的情况。所以，返回q个最优个体一方面可以避免服务不可用而重新选择，核心企业决策层还可对这q个最优个体进行进一步的决策（如可采用模糊A HP等决策方法对企业合作信誉度、创新能力和服务水平等综合评价）以选择更为理想的个体，发挥领导决策层或领域专家的主观能动性，以使动态虚拟企业具有更强的竞争优势。

3 实验分析

由于目前还没有标准企业服务测试数据集，故本文采用随机数进行验证。按照图2所示组合流程对动态虚拟企业伙伴选择进行实验，实验平台为Eclipse3．2，算法源码用Java语言实现。为不同服务类随机生成相应指标数据，同一服务类中，生产时间和成本指标设定为某区间［a，b］内的随机数，质量指标设置为［1，10］之间的随机整数，各指标权重λij为0到1之间的随机数，针对权重的约束条件为：0．5］），i＝1，2，…，5。针对生产时间和成本指标的约束条件为：生产时间和成本指标在范围［a，b］内不高于（a＋（b－a＋1）×0．7），质量指标不低于4。针对算法进化代数的约束条件为：连续30代最 大 适 应 度 不 变，k1＝ 0．3， k2＝0．9，k3＝0．01，k4＝0．5。

对自适应遗传算法AGA和IAGA算法在不同服务数规模下进行实验对比分析（相同规模服务数两种算法采用相同随机数），同时，为了分析两种算法查找到的最佳个体是否是实际最优个体，设计了穷尽查找算法（br utalf orce search，BS）求解不同服务数规模下的实际最佳适应度，BS算法可在初步筛选前或筛选后执行。

（1）种群规模1000，每个服务类候选服务数规模从1变化到50时实验对比结果如图4所示。IAGA算法最佳适应度和实际最佳适应度吻合率（指适应度值相同的比率）为96%，在图4中IAGA算法最佳适应度曲线基本被实际最佳适应度曲线所覆盖，终止世代数平均为79．9，最佳适应度大小为0．8752。AGA算法最佳适应度和实际最佳适应度吻合率为84%，终止世代数平均为104．44，最佳适应度大小为0．8706。由于利用筛选机制，IAGA算法在终止世代数和适应度方面表现出了良好的性能。可以看出，随着每个服务类候选服务数量的增加，最大适应度总体呈上升趋势，这说明基于DVEPSEM模型的伙伴选择，随着企业发布的服务数量的增加，核心企业能够查找到更为优化的伙伴组合，从而提高动态虚拟企业市场应变能力和核心竞争力。

图4 在不同服务数规模下的对比实验

（2）种群规模的大小直接影响到IAGA算法和AGA算法最佳适应度和实际最佳适应度吻合率，种群规模从100变化到1000（步长100），对服务类候选服务数从1到50进行200次实验，计算各种群规模下的平均吻合率，实验结果如图5所示。随着种群大小的变化，IAGA算法在适应度吻合率方面始终保持明显的优势，本实验表明，IAGA算法能够解决大规模的伙伴选择，具有很强的全局寻优能力，种群规模应设置为一个较大的值（文中实验应大于600），保证获取的最佳个体为全局最优解。

图5 种群规模对适应度吻合率的影响实验

（3）种群规模1000，设定每个服务类候选服务数为30时，图6所示为IAGA算法某次运行返回的5个最大适应度值及个体信息。从图6可以看出，5个最优个体中最大适应度值为0．8260，最小适应度值为0．8124，子任务T K3、T K4和T K5的候选服务均相同，为｛16，8，29｝，T K1有两个候选服务16和25，T K2有三个候选服务1、17和23可供选择，为领导层或领域专家进一步决策提供信息支持。IAGA算法查找到的最优伙伴组合｛16，17，16，8，29｝和BS算法查找结果相同，结果是精确解。在算法中还设计了计算任意选取个体适应度值的功能，如果核心企业不选用IAGA算法推荐的这q个个体，还可以在企业DSS支持下选择新个体，如输入个体｛23，14，21，6，18｝，该个体适应度经计算结果为0．3898，可反复输入。图6中distribution（1）含义是经初步筛选以后BS算法计算出的所有个体的适应度值的分布情况，总的个体数为192192，未筛选总个体数为24 300 000，可见IAGA算法能够较大程度地减小伙伴选择搜索空间，从而提高伙伴选择效率和查找准确性。

图6 返回q个最佳个体信息实验

4 总结

采用Web服务技术解决动态虚拟企业系统集成已成为一种完美的解决方案，因此，研究基于Web服务的动态虚拟企业伙伴选择具有非常重要的意义。文中提出了一种动态虚拟企业伙伴选择的扩展模型DVEPSEM，充分考虑了Web服务架构下服务数量会不断变化和动态更新以及服务QoSextr指标约束和监督机制等问题，设计了基于DVEPSEM模型的IAGA算法，通过企业QoSextr约束等规则进行伙伴筛选，减小了搜索空间，利用理想点法和欧氏距离构造适应度函数，同时考虑到企业服务可能出现不可用的情况，返回q个适应度高的优良个体，一方面可以充分发挥领导层或领域专家的决策能力，提高虚拟企业的竞争力，另一方面避免了因个别服务不可用而重新选择，提高效率。实验表明，本文提出的DVEPSEM模型是合理可行的，IAGA算法在进化代数和最佳适应度方面均表现出了明显的优势，支持基于DVEPSEM模型的大规模动态虚拟企业伙伴选择。

［1］ Zhu H，Liu S Y，Fang X R．Method f or Uncertain Multi－attribute Decision Making with Preference Inf or mation in the For m of Inter val Nu mbers Co mplementary Judgment Matrix［J］．Journal of Systems Engineering and Electronics，2007，18（2）：265－269．

［2］ Ye Fei，Li Y N．Group Multi－attribute Decision Model to Partner Selection in the For mation of Virtual Enter prise under Inco mplete Infor mation［J］．Expert Systems with Applications，2009，36（5）：9350－9357．

［3］ 张成考，聂茂林，吴价宝．基于改进型灰色评价的虚拟企业合作伙伴选择［J］．系统工程理论与实践，2007，27（11）：54－60．

［4］ 李剑，景博，牛少彰，等．基于自适应遗传算法的企业动态联盟伙伴选择模型［J］．通信学报，2009，30（8）：78－83．

［5］ 蒋建国，夏 娜，张国富，等．基于蚁群算法的敏捷供应链伙伴选择［J］．系统仿真学报，2006，18（12）：3377－3379．

［6］ Zhao F Q，Hong Y，Yu D M，et al．A Novel Genetic Algorithm f or Partner Selection Problem in Virtual Enter prise［C］／／Proceedings of t he ICMA’04．Chengelu，China，2004：477－482．

［7］ 苏兆品，蒋建国，夏娜，等．一种基于免疫的敏捷虚拟企业伙伴选择算法［J］．中国机械工程，2008，19（8）：925－928．

［8］ Y Rezgui．Role－based Service－oriented Implementation of a Virtual Enterprise：a Case Study in the Constr uction Sector［J］．Co mputers in Industry，2007，58（1）：74－86．

［9］ 张明宝，夏安邦．基于面向服务体系架构的敏捷虚拟企业信息系统框架［J］．计算机集成制造系统，2004，10（8）：985－990．

［10］ Shen W M，Hao Q，Wang S，et al．An Agentbased Service－oriented Integration Architecture f or Collaborative Intelligent Manufacturing［J］．Robotics and Computer－integrated Manufacturing，2007，23（3）：315－325．

［11］ Zeng Z B，Li Y，Zhu W．Partner Selection with a Due Date Constraint in Virtual Enter prises［J］．Applied Mathematics and Co mputation，2006，175（2）：1353－1365．