模糊情况下带时序约束服务流程的构建与优化

梁合兰，杜彦华，李苏剑

（北京科技大学 机械工程学院，北京 100083）

0 引言

随着面向服务的体系架构及云计算的迅速发展，Web服务（简称服务）已经成为企业信息系统的重要组成元素。如何在海量的候选服务中快速灵活地选择并构建出满足用户需求的最优服务流程，已经成为当前学术界和工业界关注的热点问题［1-3］。

由于企业业务策略、法律法规设定等原因，服务流程中常常存在时序约束［2-3］。如果时序约束存在错误或者不一致，将会对企业造成不必要的损失甚至灾难性的后果。而测量不精确、信息不完备、描述信息模糊及信息包含噪声等原因，往往导致时序约束具有不确定性［2］。因此，在服务流程构建过程中必须考虑模糊不确定情况下的时序一致性问题，以保证服务流程的正常执行。

针对基于服务质量（Quality of Service，QoS）的服务优选或组合问题，国内外从服务组合［4-7］、云制造［8-12］和服务流程优化［2-3，13-20］三个领域分别开展了相关研究。但是，上述研究少有考虑不确定情况下的QoS全局优化问题，特别是少有考虑带模糊不确定性的服务时序约束问题。在求解方面，上述研究方法多用于求解确定性服务组合模型，不能直接套用到模糊问题求解上，且求解效率有待提高。

针对上述研究［2-20］的不足，本文提出一种新的服务流程构建与优化方法。首先，建立了模糊情况下带时序约束的服务流程优化模型，该模型不但能有效表达QoS属性及时序约束的模糊化内涵，而且具有较好的普适性；然后，基于模糊机会约束理论及模糊满意度法，将多目标模糊约束模型进行等价转化，采用基于信息素的混合遗传算法实现模型求解。该算法借鉴蚁群算法中的信息素思想，不仅利用亲代染色体和服务自身携带的局部优化信息，还利用信息素记录的全局优化信息指导染色体的交叉，从而提高算法效率。

与上述已有方法［2-20］相比，本文的主要创新点如下：①构建了模糊情况下带时序约束的服务流程优化模型，弥补了现有研究缺乏描述QoS属性及时序约束模糊不确定性的不足；②设计了高效的求解方法。首先，基于模糊机会约束和满意度法的模型等价转化，既保留了模糊信息量，也满足了启发式算法求解模糊服务流程优化问题的需求；然后，通过基于信息素的混合遗传算法来实现更好的执行时间和求解精度。

1 相关工作

目前，针对服务优选或组合问题，国内外学者从服务组合、云制造和服务流程优化三个领域分别开展了相关研究，下面分别进行详细述评。

1.1 服务组合方面

这方面与本问题相关的具体研究内容包括基于QoS计算的服务组合［4-5］、基于语义的QoS 服务组合［6-7］等。具体来说，文献［4］针对基于中间件平台的QoS 感知的确定性服务组合问题，建立了整数规划模型并进行求解；文献［5］设计了改进变异算子求解确定性服务组合问题，该模型考虑了服务组合和原子服务的时间约束；文献［6-7］设计了基于语义的QoS全局优化模型，并通过重心法实现了QoS属性去模糊化。

上述研究［4-7］侧重于封装的服务组合和原子服务的时间要求，少有考虑具有模糊不确定性的服务时序约束。且针对不确定情况下QoS全局优化的研究［6-7］，采用去模糊化处理，存在不能反映决策者风险偏好等业务因素的不足。

1.2 制造网格与云制造方面

制造网格基于网格技术将分散资源进行封装和集成，以透明的方式为用户提供各类制造服务，从而实现资源的集成和优化运行［8］。针对确定性网格服务组合问题，文献［8］提出了基于粒子群优化算法的制造网格资源服务组合优选方法；针对资源服务优选问题没有考虑用户感受及QoS评估的语义差异性等不足，文献［9］提出基于了直觉模糊集的服务匹配算法。

云制造是一种利用网络和云制造服务平台，按用户需求组织网上制造资源，为用户提供各类按需制造服务的一种网络化制造新模式［10］。针对制造云服务组合问题，文献［11］建立了基于QoS的多任务云服务组合问题模型，并提出基于矩阵实数编码的改进遗传算法求解；文献［12］在语义服务和模糊集理论的基础上，提出一种语义服务模糊匹配方法。

上述研究［8-12］多针对确定性服务优选问题的建模及求解。对于不确定情况下的服务优选问题［9，12］，采用模糊匹配方法只能满足单个服务的最优选择，不能保证服务组合的全局最优。目前缺乏不确定情况下QoS全局优化的建模及求解方法。

1.3 服务流程

相关研究工作主要集中于服务QoS 的不确定性表征及基于QoS的服务流程优化两个方面。

（1）QoS的不确定性表征 主要有基于概率分布理论［2-3］、基于区间数理论［13-14］、基于模糊数 理论［15-16］三类方法。其中，基于概率分布的方法将QoS属性定义成服从一定分布的随机量，但由于统计量不足或随机因素规律性不强，将导致分布规律产生偏差或无法得到分布函数；基于区间数的方法通过区间数描述属性值的变化，但属性值在区间上遵循均匀分布，不能反映服务的偏好性；基于模糊数的方法通过模糊数描述QoS属性，较好地反映了服务的不确定性及偏好性。

（2）基于QoS的服务流程优化 主要可分为两类方法：①精确求解方法，如整数规划、分支定界［13，17］；②启发式优化算法［18-20］，如蚁群算法、遗传算法。精确算法在求解大规模服务优化问题上存在计算时间较长的弊端；启发式优化算法在执行时间上具有更好的优势，但此类算法多用于求解确定性服务流程优化模型，不能直接套用到模糊问题求解上，而且其进化过程多单一地依靠局部或全局优化信息，求解效率有待提高。此外，目前在建模方面也缺乏带模糊时序约束的服务流程优化模型。

2 问题描述及形式化模型

为构建优化的服务流程，首先需要根据业务需求进行抽象服务流程定义。本文首先介绍基于Petri网的抽象服务流程模型，并在服务流程不确定因素分析的基础上，建立本文问题的形式化模型。

2.1 服务流程的抽象模型

Petri网作为一种具有直观图形表示的形式化模型，在模型的逻辑、时间和性能的分析方面得到了广泛应用，因此本文使用Petri网定义抽象服务流程。

定义1 Petri网PN［21］。PN=（P，T，F），其中：P表示库所集合；T表示任务集合；F⊂（P×T）∪（T×P）表示连库所和变迁的有向弧集合。

定义2 工作流网WF-Net［21］。一个Petri网只有当满足以下条件时可以称为工作流网：①包含2个特殊的库所ε和θ，其中：ε是初始库所，即·ε=∅；θ是结束库所，即θ·=∅。②如果添加一个变迁来连接库所θ和ε，即·t=｛θ｝，t·=｛ε｝，则Petri网被连接起来。

2.2 服务流程的不确定因素分析

服务流程的不确定因素主要包括以下两方面：①由于测量不精确、信息不完备等原因，部分QoS属性度量具有模糊不确定性；②时间属性及客户对服务时序要求的模糊性，将导致模糊时序约束的产生。

（1）模糊QoS属性

流程由服务组合而成，为构建QoS优化的服务流程，必须定义候选服务的质量属性。根据国际标准ISO 8402和ITU E.800对QoS的定义，本文考虑其中时间、成本和可靠性（为表述一致，后文中均按此顺序描述）3个最具代表性的QoS属性。

因为任意模糊数都可以利用一个梯形模糊数逼近［22］，所以本文采用梯形模糊数反映QoS 属性的模糊性，如图1所示。

图1显示了服务的第k个质量属性xk2，xk3，xk4］，k=1，2，3。式中：xk1和xk4分别为梯形模糊数的上界和下界，［xk2，xk3］为隶属度为1的点集。例如，某服务的时间属性～A1=［4，5，7，9］表示该服务最理想的处理时间为［5，7］个单位时间；随着所要求的处理时间的减少或增加，服务在相应时间内完成的可能性减少，当服务时间在［0，4）或（9，+∞）时，其完成可能性为0。

（2）模糊时序约束

作为流程中常见的时间信息，时序约束通常表示活动之间的时序关系、某个活动执行期限以及活动与某个日期集绑定等。实际服务流程中往往存在时序约束，但是传统的确定性时间窗不能反映时序约束的不确定性和偏好性，因此本文用梯形模糊时间窗代替传统时间窗的定义。梯形模糊时间窗表示为关于时间π的梯形模糊数，时间不确定性或偏好性由该模糊数的隶属度函数μ（～π）表示。

为了表达一致，采用相对时序约束形式［2］表达所有约束。例如，抽象服务流程中存在相对时序约束DR（i，j）≤［0，0，7，9］，表示客户最希望任务j能在任务i开始后7个时间单位内完成，其满意度为1；否则，随着处理时间的增加，顾客满意度减少，应尽量避免；当任务j的结束时间离任务i开始时间大于9个时间单位时，客户满意度为0，即顾客不能接受。

此外，时间属性的模糊性将导致服务流程的处理时间DR（i，j）存在模糊性。根据其取值区间，模糊时序约束满足程度可分为完全满足、部分满足和完全违反三大类（如图2），但该分类原则仅简单判定了模糊约束是否满足一致性，而在实际业务环境中，决策者更关注模糊时序约束的满足程度是否达到特定服务水平，且针对不同的服务流程，可能存在不同的服务水平要求。

为了量化判定服务流程是否满足模糊时序约束，本文定义模糊时序约束满足性如下：

定义3 模糊时序约束满足性［23］。设抽象服务流程中存在模糊时序约束Pos｛DR（i，j）≤～B｝≥α，且～B=［y1，y2，y3，y4］，α∈［0，1］及DR（i，j）的模糊处理时间为=［x1，x2，x3，x4］。定义时序约束的满足程度为Pos｛DR（i，j）≤～B｝=Area｛［E，F］∩μ其 中：［E，F］表示边及围成的区域表示的隶属度函数，Area｛·｝表示面积计算。若Pos｛DR（i，j）≤｝≥α成立，则模糊时序约束满足。

以时序约束Pos｛DR（i，j）≤［0，0，7，9］｝≥0.9为例，现已知任务i开始到任务j结束的模糊时间窗DR（i，j）=［4，5，7-10］。根据定义3，可计算出2=4，即4=0.875。因为0.875＜0.9，所以可判断时序约束Pos｛DR（i，j）≤［0，0，7，9］｝≥0.9不满足。

根据模糊时序约束满足性定义，变量α反映了模糊时序约束满足程度的最低要求。因此，流程决策者应根据模糊时序约束的重要程度对α进行设置。以网上购物流程为例，该流程中存在多个时序约束，其中部分约束是由于法律法规、业务安全性等原因设置的，如“客户必须在60s内完成支付平台验证码输入”，针对这类严格不能违反的约束，可将其α设置为1；部分约束是为提高客户服务水平、便于业务操作等原因设定的，如“顾客网上下单到代理商发货的时间控制在24h内”，该类约束非严格不能违反，但也需保证达到预期的服务水平下限要求。因此，企业可综合考虑企业战略目标、客户等级、产品特点等因素设置相应的α值。

2.3 本文问题的形式化模型

图3描述了一个模糊情况下带时序约束的抽象服务流程模型。该模型由两条并行抽象服务流程WF-Net1和WF-Net2组成。模糊时序约束1～3分别用于描述WF-Net1内及WF-Net1和WF-Net2任务间的时序要求。针对流程中的每一个任务，均存在一个可实现该任务功能的候选服务集合。

为了执行该抽象服务流程，定义服务流程的执行计划如下：

定义4 执行计划EP［20］。设存在抽象服务流程WF-Net=（P，T，F），其任务集合T=｛t1，t2，…，tn｝，任一任务ti均存在一个候选服务集合Si=｛si1，si2，…，simi｝，则抽象服务流程的执行计划可定义为一个任务与候选服务的匹配序列EP=｛〈t1，s1i〉，〈t2，s2j〉，…，〈tn，snk〉｝。其中，序列中包含了抽象服务流程的所有任务，且任一任务有且仅有一个候选服务与之匹配。

由于各候选服务集合中往往存在大量质量不同的服务，这些服务将组合出大量具有不同QoS特征的执行计划。因此，必须在海量的候选服务中快速灵活地编制出最佳的执行计划，以保证在满足时序约束条件下的服务流程QoS最大化。具体就本文所考虑的三类QoS属性而言，即希望所编制的执行计划在时间、成本和可靠性这三方面达到最佳配置。

综上分析，本文问题的形式化模型可描述如下：

目标函数（1）和目标函数（2）表示所选择的服务流程应使完成服务流程的时间和成本尽可能小，且可靠性尽可能大。约束（3）表示任一任务的开始时间应不小于流程中紧前任务的完成时间；约束（4）表示服务流程中各时序约束的满足程度应不小于该约束的最小满足度。需要强调的是，为了简化，若一个事务由多条并行抽象服务流程组成，则假设多服务流程同时开始。如果已知某服务流程开始时间较晚，则在其他流程的起始点增加一个虚任务，且其处理时间为相应的开始时间差，从而保持各服务流程的开始时间一致。

从模型定义可以看出，本文模型具有以下优点：

（1）通过多模糊目标的定义，有效描述了模糊情况下基于QoS最优的服务流程选择标准。与基于QoS属性线性加权的单目标模型［19-20］相比，多模糊目标能使服务流程中各QoS属性均趋向较优状态，避免了整体QoS加权值最优而部分QoS 属性取值过低的缺陷；此外，由于函数中不需要设置各目标的权重值，避免了结果对权重向量敏感的不足。

（2）通过模糊时序约束满足性的量化判定，有效描述了服务流程中的模糊时序约束。决策者可根据模糊时序约束的重要程度，设定不同的满足度阈值α，从而实现服务流程中时序约束的柔性配置。

（3）该模型能有效反映不确定环境下QoS属性的模糊不确定性，且由于确定性或区间型数据均可处理成梯形模糊数，针对存在确定性或区间型数据的QoS属性或时序约束，本文模型仍可适用，即该模型具有较好的普适性。

3 模型求解

针对上述问题模型，本文提出模糊情况下带时序约束的服务流程优化方法，如图4所示。

（1）求解阶段1 多目标模糊约束模型转化。基于模糊机会约束规划和模糊满意度法，将模糊规划问题转化为以QoS满意度最大化为目标的清晰等价模型。

（2）求解阶段2 针对清晰等价模型的求解，提出改进的混合遗传算法。该算法借鉴蚁群算法中的信息素思想，在遗传交叉中综合考虑了局部优化信息和信息素记录的全局优化信息，从而加快了求解效率。

3.1 多目标模糊约束模型的转化

文献［6-7］基于重心法实现QoS 属性去模糊化，但该方法将在较大程度上损失模糊属性的语义，不能反映服务流程执行的可靠性、决策者的风险偏好等业务因素。为保留模糊信息量，本文首先基于模糊机会约束及其清晰等价转化理论，将3.3节的模糊约束模型转化成多目标机会约束的清晰等价模型。考虑到模型中的不同优化目标难以直接比较，进一步基于模糊满意度法，将多目标模糊约束模型转化成以QoS 满意度最大化为目标的清晰等价模型。

（1）模糊问题的清晰等价转化

首先，按照模糊随机规划理论，将带模糊数的目标函数（1）和目标函数（2）转化成目标机会约束函数。根据属性的不同性质，“时间”、“成本”应为成本型属性，其转化公式为式（5）和式（6）；而“可靠性”为效益型属性，转化公式为式（7）和式（8）。

从模糊约束规划的建模思想可知，γ反映了目标函数在不确定环境下的实现机会。根据其定义，γ越小、约束条件成立的可能性越小，即所选择的服务流程不满足满意值的风险越大。因此，决策者应综合考虑服务流程的特点、自身风险偏好等因素进行γ的设置和调整。例如，对于金融、高价值制造等服务流程来说，γ的取值更侧重于不确定情况下服务流程QoS的鲁棒性。因此，针对该类流程应设置γ＞0.5，从而规避不确定情况下QoS的不稳定性。与之相对的普通制造、服务类等服务流程具有市场竞争激烈、服务流程灵活等特点，对服务流程的QoS优劣更为敏感。因此，适当调低γ的水平，如设置γ≤0.5，将更有利于选择出不确定情况下存在高QoS可能性的服务流程。

针对模糊属性值计算，根据服务聚合计算公式［20］和模糊数运算原则，可得计算公式如表1所示。

表1 模糊属性的聚合计算公式

根据表1并结合抽象服务流程模型实例，可计算出该服务流程实例的第i个模糊质量属性值（X）=［Qi1（X），Qi2（X），Qi3（X），Qi4（X）］，其中i=1，2，3。由于上述计算仅涉及梯形模糊数的加法及乘以常量运算，根据模糊数运算法则，所得的仍为梯形模糊数。因此，机会约束式（6）和式（8）可执行清晰等价转化［24］。

（2）基于满意度的多目标转化

经上述处理后，2.3 节的模糊约束模型即转化成多目标机会约束的清晰等价模型。在多目标处理上，考虑到各QoS的属性量纲不一，在进行QoS综合评价时，不同结果难以直接进行比较。因此，本文基于最大模糊满意度法［25］，将多目标模型转化为QoS最优且不确定性程度最小的QoS满意度最大化模型。

综上，可得转化后的模型如下：

式中：目标函数定义为所有满意度中最小的一个；λi为第i个属性的满意度；Qmaxi和Qmini分别表示服务流程中第i个属性的理想解上界和理想解下界。式（12）和式（13）分别为式（6）和式（8）对应的清晰等价形式。

当然，服务流程中可能存在某些属性（如可用性），该类属性的聚合计算涉及模糊数的乘法运算。根据模糊数运算法则，梯形模糊数乘积后将不再是梯形模糊数，因此无法转化为清晰等价形式。针对该类属性，可基于模糊模拟技术产生输入及输出数据，利用神经元网络对产生数据进行训练，从而逼近不确定函数［25］。

3.2 基于信息素的混合遗传算法

通过3.1节转化后的模型可归结为组合优化问题。针对组合优化问题的求解，遗传算法、蚁群算法等启发式优化算法具有较好的执行时间优势。其中，遗传算法借鉴自然界中生物遗传和进化的规律，主要通过选择、交叉和变异算子实现种群的并行全局搜索，并通过评价函数执行种群的优胜劣汰，该算法具有大规模搜索、随机性、鲁棒性、并行性及问题域无关等特性［26］。因此，与其他智能优化算法相比，遗传算法更适合于处理维数很高、规模较大的无数值概念类［27］优化问题。

标准遗传算法主要依靠随机搜索策略，容易陷入未成熟收敛和搜索效率较低［5］。虽然文献［19-20］对标准遗传算法进行了改进，但在构造子个体时仍只利用了父代携带的局部信息。针对文献［19-20］的缺陷，本文设计了基于信息素的混合遗传求解算法。该算法参考文献［28］的算法思想，然而文献［28］针对的是旅行商问题（Traveling Salesman Problem，TSP），与本文问题有较大区别，因此本算法结合问题的特点做了以下调整：①设计了多抽象服务流程优化问题的编码规则，并提出带奖励—惩罚的适应度函数；②设计了适用于本问题的交叉算子，并重新定义了能见度参数，用于度量不确定情况下服务质量的优劣程度；③与文献［28］的排序选择、变异算法不同，本文采用基于锦标赛选择方法与最优保留相结合的选择策略，降低了算法的时间复杂度，通过非均衡的变异概率函数，实现了变异操作的动态调整。

下面描述具体算法设计。

3.2.1 染色体及适应度函数定义

本文的染色体定义为｛x1，x2，…，xn｝，xi∈［1，mi］。其中：n表示服务流程中任务的个数，mi表示第i个任务的候选服务数量。若一个事务由多条并行抽象服务流程组成，则对抽象服务流程进行排序，并依次对流程中的任务进行编码。

以4.1 节的并行抽象服务流程WF-Net1和WF-Net2为例。首先将流程中的任务排序为［t11，t12，t14，t15，t16，t18，t19，t21，t22，t23，t24，t25，t26］；然后依次从各候选服务集合中选择一个服务作为该基因位的值，即可生成一个染色体编码方案。例如，染色体｛3，2，1，2，3，1，2，1，2，1，1，3，2｝表示任务t11选择第3个候选服务，t12选择第2个候选服务。

为了使目标函数值越高的可行个体具有较高适应度，从而有更大的机会遗传给下一代，本文设计了带奖励—惩罚的适应度函数

式中：Fitness（X）为X的适应度，取值范围为［0，3］；F（X）为按式（9）计算的目标函数值，取值范围为［0，1］；V（X）为X的时序约束违反个数；Vnum为时序约束数量；P为X的奖励值，当X为可行染色体时P=1，否则P=0。

3.2.2 基于信息素的交叉算子

在交叉时，针对每个任务，首先判断亲代染色体是否均选择了同一个候选服务，是则将该候选服务保留到子代中；否则，算子按照式（16），以pp（0≤pp≤1）的概率选择最合适的服务（QoS较优且信息素值较高），而以1-pp的概率按照式（17）进行轮盘选择。

式中：Nk（g）表示第g代第k个任务选中的服务；Sk表示第k个任务的候选服务集合；τj（g）表示第g代第j个服务的信息素值；ηj为服务j的能见度，按式（18）计算；β为调节信息素和能见度之间相对重要性的参数；r为随机数。变量R定义如下：

能见度ηj用于反映服务j的QoS 优劣程度。为使整体质量较优的服务被选中的概率较高，本文定义ηj如下：

式中：qmaxki和qminki分别为第k个任务第i个属性的模糊上限和模糊下限；表示候选服务j第i个属性的梯形模糊数。

从上述过程可以看出，本文设计的交叉算子在构造子个体时，除了继承亲代染色体的服务选择信息外，还依靠基于能见度的局部信息及基于信息素的全局优化信息指导服务的选择，并通过一定概率的随机选择保持了种群的多样性。此外，由于本文设计的交叉算子是按照染色体中的基因位顺序依次对各任务重新编码，该方法将不会改变父代染色体中的任务排列顺序，且均适用于单流程或多服务流程的构建优化问题。

3.2.3 信息素更新策略

在遗传算法每代运算后，各服务的信息素值将按照最大—最小蚂蚁系统［29］中的机制进行更新，具体公式如下：

式中：ρ表示信息素的持久度；Fitness（GS）为当前全局最优解GS的适应度。此外，在每次更新中，令τmax=Fitness（GS）／1-ρ，τmin=τmax／2n。若τi（g+1）＞τmax，则τi（g+1）=τmax；若τi（g+1）＜τmin，则τi（g+1）=τmin。从而保证信息素值被限制在区间［τmin，τmax］之内。

由式（19）和式（20）可知，非全局最优解中服务的信息素将因信息素的“蒸发”而减少；而包含在全局最优解中的服务信息素将得到加强，且全局最优解的适应度越高，该解对应的各候选服务的信息素强度增加量越大，从而有利于提高相应服务在交叉操作中被选中的概率。

3.2.4 求解过程

综上可得基于信息素的混合遗传算法的求解过程如下：

算法1 基于混合遗传的服务流程优化算法。

输入：抽象服务流程WF-Net=（P，T，F）；模糊时序约束集合ψ=｛…，Pos｛DR（i，j）≤～dk｝≥αk，…｝；候选服务集合CS=｛s11，…，snmn｝；算法设置参数，包括：种群规模pop＿size，迭代次数G，基于最大信息素与能见度选择的概率pp，信息素与能见度的相对比重β，信息素持久度系数ρ，交叉概率pc，变异概率函数pm（g）和锦标赛候选规模tour＿size。

输出：执行计划X=｛x1，x2，…，xn｝。

步骤1 按抽象服务流程排序，对各流程中的任务依次从其候选服务集合中随机选取一个服务作为染色体基因。根据模糊属性的聚合计算公式和抽象服务流程实例，计算染色体的满意度F（X），并结合时序约束判定结果V（X），获得染色体的适应度。重复本步骤pop＿size次，即生成初始的染色体群体pop，种群大小为pop＿size。

步骤2 按pop中的染色体顺序依次生成随机数r：若r不大于交叉概率pc，则将第i个染色体标识为候选亲代染色体。重复本步骤pop＿size次，从而确定参与交叉的候选亲代染色体集合R。

步骤3 在集合R中按轮盘赌策略选择两个染色体作为亲代染色体，初始化k=1，并按下列操作生成新个体：

（1）当双亲染色体第k个基因位的值相同，则保留亲代的值；否则，按照式（16）确定第k个基因位的值。

（2）k=k+1，重复步骤（1），直到n个任务均匹配上服务。

（3）生成随机数r，若r不大于第g代变异概率pm（g），则对新个体执行单点变异操作。

步骤4 将新个体放入临时种群tempop，若tempop中的个体数量不小于pop＿size／2，则转步骤5；否则转步骤3。

步骤5 对tempop与pop中的染色体，执行基于锦标赛选择方法与最优保留相结合的选择机制。即每次随机从tour＿size个染色体中选择最佳方案，重复本步骤pop＿size次，从而选出pop＿size个染色体赋给pop。进一步，将适应度最高的个体替换pop中适应度最低的个体，从而生成下一代初始种群。

步骤6 判断是否已达到迭代次数G，是则输出最终结果；否则执行信息素更新策略，转步骤2。

本文算法综合了遗传算法和蚁群算法的特点，并通过以下设计达到提高算法精度和收敛速度的目的：①在交叉操作方面，既考虑了优良亲代染色体的局部信息，也考虑了信息素所携带的全局优化信息（如步骤3（1）～步骤3（2）），从而避免了文献［19-20］中单纯依靠局部信息进行交叉的不足；②在选择操作方面，与文献［19-20，28］的排序选择策略相比，采用基于锦标赛选择方法与最优保留相结合的选择策略（如步骤5），有利于降低选择操作的时间复杂度；③在变异操作方面，通过设计变异概率函数（如步骤3（3）），使变异概率随着迭代次数的增加而逐步降低，既有利于保持种群的多样性，也便于算法快速收敛。

4 算例分析

为验证本文算法的可行性，通过一个手机生产实例［20］来介绍和应用本文方法。

4.1 实例说明

为了简化模型，假设一个新手机生产在现实的生产企业中包含2个流程：电子主板生产流程（WFNet1）和外围部件生产流程（WF-Net2）。这2个流程的并行情况如图5所示。

每个任务均执行服务外包策略，相关候选服务信息如表1所示。其中候选服务的QoS属性由［时间，成本，可靠性］组成，且上述属性均为梯形模糊数。如对任务t11来说，有三个候选服务s111～s113可为其提供服务。其中服务s111完成该任务的模糊时间为［4，6，8，10］、成本为［2，3，4，6］、可靠性为［2，4，5，6］。

为了缩短产品投放市场的时间、获得更大的市场占有率，设置相关的时序约束如下：

（1）Pos｛DR（t23，t25）≤［0，0，17，21］｝≥0.9，表示决策者希望“在外围部件的技术文档撰写开始之后最好能在17个工作日内完成外围部件的生产，最晚不能超过21个工作日”，且所选择的服务流程满足该模糊时序约束的程度应不小于90%。

（2）Pos｛DR（t23，t19）≤［0，0，7，12］｝≥1，表示决策者要求“在外围部件的技术文档撰写开始之后最好能在7个工作日内完成主板的生产，最晚不能超过12个工作日”，且所选择的服务流程满足该模糊时序约束的程度应为1。

4.2 模型建立及转化

根据2.3节的形式化模型定义，结合本案例的时序约束，可建立问题模型如下：

表2 各任务对应的候选服务

按照多目标模糊约束模型的转化式（9）～式（14），代入本实例的参数并化简，可建立清晰等价模型如下：

进一步，在式（26）～式（29）的模型中，还需对置信水平γ进行设置。因为手机加工属于制造类服务流程，且市场竞争激烈，所以该流程对QoS的优劣比较敏感；但是，由于手机产品价值较高，其对不确定情况下QoS的鲁棒性同样具有较高要求。综上分析，针对本实例，设置γi=0.5（i=1，2，3）。此外，还将在4.4节对比不同置信水平下求解结果的差异，并就置信水平设置对优化结果的影响进行详细分析。

4.3 算法求解

针对上述模型，采用基于信息素的混合遗传算法进行求解。在算法参数设置方面，根据问题规模，设置pop＿size=30，G=50，pc=0.8，tour＿size=5；与信息素相关的参数参考文献［28，29］设置为：pp=0.9，β=3，ρ=0.95；变异概率函数参考文献［30］设置为：pm（g）=0.15×（1-0.1（1-g／G））。实验 在2.1GHz的英特尔酷睿2双核处理器和1GB 内存的台式机上完成。由于算法具有随机性，以某次求解为例，具体求解过程如下：

按照算法的步骤1所述，首先随机生成30个染色体，组成初始染色体群体pop。以第1个染色体为例，其编码为｛3，2，1，2，3，1，2，1，2，1，1，3，2｝，通过计算，其对应的三个目标函数的满意度分别为｛0.67，0.72，0.51｝，由于不满足第一个时序约束，适应度为1.01。相应地，通过计算其他染色体的适用度可以看出，初始解的适应度范围为［0.65，2.43］，可行解个数为11。

生成初始解后，根据步骤2，按0.8的交叉概率共选择出21个染色体组成候选亲代染色体集合R。根据步骤3和步骤4，依次从R中按轮盘赌选择两个亲代染色体执行交叉和变异操作，生成临时种群tempop。以适应度为2.42的染色体｛3，2，1，1，3，1，1，3，1，2，1，2，1｝为例，与适应度为2.39的染色体｛3，2，2，1，2，1，2，3，2，2，1，1，2｝的交叉和变异过程如下：亲代染色体中有7个基因位相同，将直接继承到子代中，其他6个基因位根据式（16）重新选择服务，最终生成适应度为2.45的新染色体｛3，2，2，1，1，1，1，3，1，2，1，2，1｝。由于所生成的随机数r大于第1代变异概率阈值pm=0.15×（1-0.1（1-1／50））=0.134，即新染色体｛3，2，2，1，1，1，1，3，1，2，1，2，1｝不执行变异操作。根据步骤5，对tempop与pop中的染色体，基于锦标赛选择与最优保留方法执行选择操作，并确定第1代的染色体组pop。可以看出其适应度的范围为［0.86，2.46］，与初始解比较可知，适应度得到了优化。

重复上述步骤2～步骤5，当迭代次数为21时，解收敛为｛2，2，1，2，2，1，1，3，2，2，2，2，1｝，其适应度为2.50，对应的满意度分别为｛0.61，0.62，0.50｝。基于所获得的最优解，客户可依次为各任务匹配相应的服务，从而确定最优执行计划。

4.4 结果分析

目标机会约束的置信水平γ反映了目标函数在不确定环境下的实现机会。为观察不同置信水平对优化结果的影响，改变模糊目标中的置信水平γi（i=1，2，3），并记录目标函数的满意度变化，结果如表3所示。

表3 改变置信水平对优化结果的影响

从表3可以看出，随着置信水平γi由0.9 降至0.3，最小满意度不断增大。表明在不确定环境下，当手机决策者趋向于选择存在高QoS可能的服务流程时，它可能承担的服务流程不能兑现QoS承诺的风险将增加，该结论与实际相符。同时表3也表明，采用本文的多目标模糊约束模型转化方法能较好地保留模糊信息量，并让手机决策者直观观察到风险与效益的关系，从而权衡并做出决策。

5 算法性能的对比分析

为了验证本文算法在计算效率上的优越性，进一步从求解精度和算法执行时间两方面，将本文算法与改进遗传算法［20］、混合优化算法［28］及最大-最小蚁群算法［29］进行对比。

在案例设计方面，本文设计了三种不同的实验，包括不同的任务数量、不同的候选服务数量和不同的时序约束数量。参数设置为pop＿size=100，G=5000，pc=0.8，tour＿size=10，γi=0.5，β=3，pp=0.9，ρ=0.95，pm（g）=0.15×（1-0.1（1-g／G））。每个候选服务的QoS 都是随机产生的。具体对各属性来说，依次产生4个范围在［1，10］的随机数，并对上述随机数按从小到大排序，从而获得该属性对应的梯形模糊数。所有的实验均在2.1GHz的英特尔酷睿2 双核处理器和1 GB 内存的台式机上完成。考虑到算法的随机性，每组数值取20次结果的平均值。

（1）任务数量的不同

此组实验是为了研究任务数量增加的、不同算法的求解精度和运行时间的差异。在此实验中，任务数量从10增加到50，增幅定为5；固定每个任务候选服务的数量为20，时序约束的数量为5。实验结果如图6和图7所示。

从图6可以看出，本文的求解精度与混合优化算法［28］及最大-最小蚁群算法［29］基本相同，明显优于改进遗传算法［20］，且随着任务数量的增加，求解优化效果越明显。由图7可以看出，本文算法的计算时间明显低于其他三种算法。从时间增长趋势上看，随着任务数量的增加，本文求解时间的增长率最小，而蚁群算法［29］的增长率明显高于其他三类算法。

（2）候选服务数量的不同

此组实验是为了研究不同算法的求解精度及计算时间随候选服务数量的变化而变化的情况。在这组实验中，候选服务的数量从10增加到50，增幅为5；任务和时序约束的个数分别固定为30 和5。实验结果如图8和图9所示。

从图8可以看出，本文的求解精度与混合优化算法［28］及最大-最小蚁群算法［29］基本相同，明显优于改进遗传算法［20］。随着任务数量的增加，上述算法较改进遗传算法［20］的优化程度呈上升趋势。由图9可以看出，本文算法的计算时间明显低于其他三种算法。虽然从增长趋势上看，随着候选服务数量的增加，本文算法计算时间的增长率高于改进遗传算法［20］，但是由于单个任务对应的候选服务数一般不会超过50个，可以认为本文的计算效率仍较改进遗传算法［20］具有优势。

（3）时序约束数量的不同

此组实验是为了研究时序约束个数的增加对求解精度和计算时间的影响。在这组实验中，时序约束数量从5增加到45，增幅为5；任务及其候选服务的数量分别固定为30和10。实验结果如图10 和图11所示。

从图10可以看出，本文的求解精度与混合优化算法［28］及最大-最小蚁群算法［29］基本相同，明显优于改进遗传算法［20］。此外，随着约束数量的增加，本文算法的求解精度稳定，而改进遗传算法的求解精度明显呈下降趋势。由图11可以看出，本文算法的计算时间最短，而蚁群算法［29］的计算时间最长。从增长趋势上看，随着约束数量的增加，改进遗传算法［20］的计算时间增长明显呈上升趋势，其他三类算法的计算时间增长率均较小。

综上分析，通过设计不同任务数量、候选服务数量和时序约束数量的实验，对比发现：

（1）针对上述多组实验，本文算法的求解精度均优于改进遗传算法［20］，计算精度提高了1%～29.6%，特别是随着问题规模的增大，求解精度的优化效果更明显。在求解时间上，本文算法均优于改进遗传算法，其计算时间节约了46.6%～69.2%。但需指出，随着候选服务数量的增加，本文算法的求解时间的增长率高于改进遗传算法。

（2）针对上述多组实验，本文算法的求解精度与混合优化算法［28］基本相同，计算精度最大差别为1.3%。在求解时间上，本文算法明显优于混合优化算法，计算时间节约了58.1%～68.8%。而从时间增长趋势上看，随着问题规模的增大，两种算法的求解时间增长率接近。

（3）针对上述多组实验，本文算法的求解精度与最大-最小蚁群算法［29］基本相同，计算精度最大差别为1%。在求解时间上，本文算法明显优于最大-最小蚁群算法，计算时间节约了82.6%～96.5%。随着问题规模的增大，本文算法在求解时间上的增长率明显低于最大-最小蚁群算法。

分析其原因，就算法的求解精度来说，因为改进遗传算法［20］仅利用了双亲染色体指导子代生成，而本文算法及其他两种算法［28-29］均通过信息素记录迭代过程中的求解经验，并基于所学习到的全局信息指导子代生成，所以更有利于获得较好的求解结果。特别是随着任务数、服务数量和约束的增加，解空间不断扩大，通过信息素反映的全局信息在寻优过程中发挥的作用更加明显。

就算法的求解时间而言，因为最大-最小蚁群算法［29］的运算开销大量花费在基于信息素概率的子代生成计算上，基于信息素的遗传算法框架降低了算法的时间复杂度；且与改进遗传算法［20］和混合优化算法［28］相比，本文算法通过改进的选择及变异策略也进一步降低了算法的时间复杂度，所以具有比其他三类算法更好的求解时间优势。但从算法流程可知，随着候选服务数量的增大，信息素更新及基于信息素交叉操作的运算量将增大，而候选服务数量的增加对改进遗传算法［20］的时间复杂度影响较小，因此在候选服务数量增加的情况下，本文算法的求解时间增长率会高于改进遗传算法［20］。

6 结束语

本文针对普遍存在的时序约束不确定情况，构建了模糊情况下带时序约束的服务流程优化模型。在求解方面，首先基于模糊机会约束理论和最大模糊满意度法，将多目标模糊规划模型转化成以满意度最大化为目标的清晰等价模型，提出基于信息素的混合遗传算法进行求解。该算法不仅利用亲代和服务自身的局部信息，还利用以信息素形式保存的全局信息，因此加快了收敛效率。本文设计了不同任务数量、候选服务数量和时序约束数量的实验，结果表明：与已有成果相比，本文算法在执行时间和求解精度上具有明显优势。

在本文基础上，未来将在如下方面进一步展开工作：①针对流程执行过程中出现的时序异常，如何实现服务流程的动态调整，从而保证时序一致性；②对除基本结构之外的工作流复杂模式进行讨论。

［1］CHEN J，YANG Y.Multiple states based temporal consistency for dynamic verification of fixed-time constraints in grid workflow systems［J］.Concurrency and Computation：Practice and Experience，2007，19（7）：965-982.

［2］DU Yanhua，WANG Xiaofei，YAO Jianshi.Probability based timed compatibility of Web service composition［J］.Practical Applications of Intelligent Systems Advances in Intelligent and Soft Computing，2012，124：31-39.

［3］LIU X，YANG Y，JIANG Y，et al.Preventing temporal violations in scientific workflows：where and how ［J］.IEEE Transactions on Software Engineering，2011，37（6）：805-825.

［4］ZENG L，BENATALLAH，B，DUMAS M，et al.Quality driven Web services composition［C］／／Proceedings of the 12th International Conference World Wide Web.New York，N.Y.，USA：ACM，2003：411-421.

［5］ROSENBERG F，MULLER M，LEITNER P，et al.Metaheuristic optimization of large-scale QoS-aware service compositions［C］／／Proceedings of 2010IEEE International Conference on Services Computing.Washington，D.C.，USA：IEEE，2010：97-104.

［6］YANG F，SU S，LI Z.Hybrid QoS-aware semantic Web service composition strategies［J］.Science in China Series F：Information Sciences，2008，51（11）：1822-1840.

［7］LI Zhen，YANG Fangchun，SU Sen.Fuzzy multi-attribute decision making-based algorithm for semantic Web service composition［J］.Journal of Software，2009，20（3）：583-596（in Chinese）.［李 祯，杨放春，苏 森.基于模糊多属性决策理论的语义Web 服务组合算法［J］.软件学报，2009，20（3）：583-596.］

［8］TAO Fei，ZHAO Dongming，HU Yefa，et al.Resource service composition and its optimal selection based on particle swarm optimization in manufacturing grid system ［J］.IEEE Transactions on Industrial Informatics，2008，4（4）：315-327.

［9］TAO Fei，ZHAO Dongming，ZHANG Lin.Resource service optimal-selection based on intuitionistic fuzzy set and non-functionality QoS in manufacturing grid system ［J］.Knowledge and Information System，2010，25（1）：185-208.

［10］LI Bohu，ZHANG Lin，WANG Shilong，et al.Cloud manufacturing：a new service oriented networked manufacturing model［J］.Computer Integrated Manufacturing Systems，2010，16（1）：1-7，16（in Chinese）.［李伯虎，张 霖，王时龙，等.云制造——面向服务的网络化制造新模式［J］.计算机集成制造系统，2010，16（1）：1-7，16.］

［11］LIU Weining，LI Yiming，LIU Bo.Service composition in cloud manufacturing based on adaptive mutation particle swarm optimization［J］.Journal of Computer Applications，2012，32（10）：2869-2874（in Chinese）.［刘卫宁，李一鸣，刘波.基于自适应粒子群算法的制造云服务组合研究［J］.计算机应用，2012，32（10）：2869-2874.］

［12］BAI L，LIU M.Fuzzy sets and similarity relations for semantic Web service matching［J］.Computers and Mathematics with Applications，2011，61（8）：2281-2286.

［13］DU Yanhua，LI Hong，AI Lifeng.Dynamic configuration of service based processes in cloud computing using linear programming［C］／／Proceedings of the 9th World Congress on Intelligent Control and Automation.Washington，D.C.，USA：IEEE，2012：3509-3514.

［14］CHEN J，YANG Y.Localizing temporal constraints in scientific workflows［J］.Journal of Computer and System Sciences，2010，76（6）：464-474.

［15］WANG P.QoS-aware web services selection with intuitionistic fuzzy set under consumer's vague perception［J］.Expert Systems with Applications，2009，36（3）：4460-4466.

［16］JESJE C，JULIA S，VALETTE R.Fuzzy continuous resource allocation mechanisms in workflow management systems［C］／／Proceedings of 2009 23rd Brazilian Symposium on Software Engineering.Washington，D.C.，USA：IEEE Computer Society，2009：236-251.

［17］ARDAGNA D，PERNICI B.Adaptive service composition in flexible processes［J］.IEEE Transactions on Software Engi-neering，2007，33（6）：369-384.

［18］YU J，BUYYA R.Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms［J］.Scientific Programming，2006，14（3）：217-230.

［19］AI L，TANG M.A penalty-based genetic algorithm for QoSaware web service composition with inter-service dependencies and conflicts［C］／／Proceedings of International Conference on Computational Intelligence for Modeling Control &Automation.Washington，D.C.，USA：IEEE，2008：738-743.

［20］DU Y，WANG X，AI L.Dynamic selection of services under temporal constraints in cloud computing［C］／／Proceedings of 2012International Conference on E-Business Engineering.Washington，D.C.，USA：IEEE，2012：252-259.

［21］DU Y，XIONG P，FAN Y，et al.Dynamic checking and solution to temporal violations in concurrent workflow processes［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part A：Systems and Humans，2011，41（6）：1166-1181.

［22］HU Baoqing.Fuzzy basic theory［M］.Wuhan：Wuhan University Press，2010（in Chinese）.［胡宝清.模糊理论基础［M］.武汉：武汉大学出版社，2010.］

［23］ZHOU Y，MURATA T，DEFANTI T.Modeling and performance analysis using extended fuzzy-timing Petri nets for networked virtual environment［J］.IEEE Transactions on System，Man，and Cybernetics—Part B：Cybernetics，2000，30（5）：737-755.

［24］LU M.On crisp equivalents and solutions of fuzzy programming with different chance measures［J］.Information，2003，6（2）：125-134.

［25］LIU Baoding，ZHAO Ruiqing，WANG Gang.Uncertain programming with applications［M］.Beijing：Tsinghua University Press，2003（in Chinese）.［刘宝锭，赵瑞清，王 纲.不确定规划及应用［M］.北京：清华大学出版社，2003.］

［26］LIU Weining，LIU Bo，SUN Dihua.Multi-task oriented service composition in cloud manufacturing ［J］.Computer Integrated Manufacturing Systems，2013，19（1）：199-209（in Chinese）.［刘卫宁，刘 波，孙棣华.面向多任务的制造云服务组合［J］.计算机集成制造系统，2013，19（1）：199-209.］

［27］ZHOU Ming，SUN Shudong.Genetic algorithms：theory and application［M］.Beijing：National Defense Industry Press，1996：11-14（in Chinese）.［周 明，孙树栋.遗传算法原理及应用［M］.北京：国防工业出版社，1996：11-14.］

［28］ZHAO F，LI S，SUN J，et al.Genetic algorithm for the onecommodity pickup-and-delivery traveling salesman problem［J］.Computer &Industry Engineering，2009，56（4）：1642-1648.

［29］STUTZLE T，HOOS H.MAX-MIN ant system［J］.Future Generation Computer Systems，2000，16（8）：889-898.

［30］WANG Wenbin，SUN Qibo，ZHAO Xinchao，et al.Web services selection approach with QoS global optimal based on discrete particle swarm optimization with non-uniform mutation algorithm［J］.Acta Electronica Sinica，2010，38（12）：2774-2779（in Chinese）.［王文彬，孙其博，赵新超，等.基于非均衡变异离散粒子群算法的QoS全局最优Web服务选择方法［J］.电子学报，2010，38（12）：2774-2779.］