工程科学学报，第40卷，第7期：882-891,2018年7月 Chinese Journal of Engineering,Vol.40,No.7:882-891,July 2018 DOI:10.13374/j.issn2095-9389.2018.07.015;http://journals.ustb.edu.cn 领域QS与资源感知的物流服务动态优化组合方法 徐园园⑧，刘志中，贾宗璞 河南理工大学计算机科学与技术学院，焦作454000 ☒通信作者，E-mail:XUXUXu106@163.com 摘要为了提高物流服务优化组合的动态性、可靠性与用户满意度，本文提出了一种基于全局服务质量(quality of service, Q$)约束分解的能够感知领域质量与资源需求的物流服务优化组合方法.该研究工作首先把学习机制引入人工蜂群算法 (artificial bee colony algorithm,ABC),形成了具有自主学习能力的改进型人工蜂群算法(LABC):之后，应用学习人工蜂群算 法(LABC)将全局QS约束分解成每个物流子任务需要满足的局部QS约束，从而将QoS感知的物流服务优化组合这一全局 优化问题转化成以领域质量为依据的局部最优服务选择问题：其次，在物流服务流程执行的过程中，在感知物流任务节点对 资源需求的前提下，为每一个物流任务节点选择一个具有最优领域Q$的物流服务：与已有的研究工作相比，该方法能够实 现物流服务动态可靠的优化组合.最后，通过模拟实验验证了本文所提出的方法是可行有效的 关键词领域QoS;资源感知；物流服务组合；QS约束分解：人工蜂群算法 分类号TP393.09 Domain QoS and resource-aware logistics web service dynamic optimal composition XU Yuan-yuan,LIU Zhi-zhong,JIA Zong-pu College of Computer Science and Technology,Henan Polytechnic University,Jiaozuo 454000.China Corresponding author,E-mail:xuxuxul06@163.com ABSTRACT With the rapid development of service computing,cloud computing,internet of things,e-commerce,and modern logis- tics industry,cross-domain logistics services cooperation has become the main development trend of the modern logistics industry.The dynamic optimal composition of web services in logistics has become the key technology to create large and powerful logistics services based on the available logistics services of different companies that achieve seamless convergence of logistics services,satisfy user com- plex requirements,and realize the value addition.Recently,owing to the technologies of web services,cloud computing,and service sciences,an increasing number of logistics companies have registered themselves as logistics web service providers.The logistics serv- ices composition should satisfy the user's global QoS constraints and provide the best quality of service (QoS.)Currently,with the rapid development of cloud computing,e-commerce,service computing,and modern logistics industry,many logistics services are available on the network providing similar functions and different levels of QoS.These factors make the problem of determining the opti- mal composition of a logistics service a typical Np-hard problem.This study proposes a method to achieve the dynamic optimal composi- tion of domain QoS and resource-aware logistics services and to realize logistics services that are dynamic,offer quality of domain serv- ices,and are aware of resource requirements.First,the learning artificial bee colony algorithm (LABC)is proposed;LABC is applied to decompose the global QoS constraints into local QoS constraints that logistics task nodes must satisfy and to transform the global opti- mization problem of logistics service composition into a local optimal service selection problem.Second,during the process of logistics service process execution,for each task node,the logistics service with best domain QoS evaluation,which can satisfy the local QoS constraints and resource requirements,is chosen to achieve a high-quality dynamic logistics service and optimal composition of service. The results of simulation experiments show that the proposed method is feasible and effective. KEY WORDS domain QoS;resource-aware;logistics web services composition;QoS constraint decomposition;artificial bee colony 收稿日期：2017-10-09
工程科学学报,第 40 卷,第 7 期:882鄄鄄891,2018 年 7 月 Chinese Journal of Engineering, Vol. 40, No. 7: 882鄄鄄891, July 2018 DOI: 10. 13374 / j. issn2095鄄鄄9389. 2018. 07. 015; http: / / journals. ustb. edu. cn 领域 QoS 与资源感知的物流服务动态优化组合方法 徐园园苣 , 刘志中, 贾宗璞 河南理工大学计算机科学与技术学院, 焦作 454000 苣通信作者, E鄄mail:xuxuxu106@ 163. com 摘 要 为了提高物流服务优化组合的动态性、可靠性与用户满意度,本文提出了一种基于全局服务质量( quality of service, QoS)约束分解的能够感知领域质量与资源需求的物流服务优化组合方法. 该研究工作首先把学习机制引入人工蜂群算法 (artificial bee colony algorithm, ABC),形成了具有自主学习能力的改进型人工蜂群算法(LABC);之后,应用学习人工蜂群算 法(LABC)将全局 QoS 约束分解成每个物流子任务需要满足的局部 QoS 约束,从而将 QoS 感知的物流服务优化组合这一全局 优化问题转化成以领域质量为依据的局部最优服务选择问题;其次,在物流服务流程执行的过程中,在感知物流任务节点对 资源需求的前提下,为每一个物流任务节点选择一个具有最优领域 QoS 的物流服务;与已有的研究工作相比,该方法能够实 现物流服务动态可靠的优化组合. 最后,通过模拟实验验证了本文所提出的方法是可行有效的. 关键词 领域 QoS; 资源感知; 物流服务组合; QoS 约束分解; 人工蜂群算法 分类号 TP393郾 09 收稿日期: 2017鄄鄄10鄄鄄09 Domain QoS and resource鄄aware logistics web service dynamic optimal composition XU Yuan鄄yuan 苣 , LIU Zhi鄄zhong, JIA Zong鄄pu College of Computer Science and Technology, Henan Polytechnic University, Jiaozuo 454000, China 苣Corresponding author, E鄄mail:xuxuxu106@ 163. com ABSTRACT With the rapid development of service computing, cloud computing, internet of things, e鄄commerce, and modern logis鄄 tics industry, cross鄄domain logistics services cooperation has become the main development trend of the modern logistics industry. The dynamic optimal composition of web services in logistics has become the key technology to create large and powerful logistics services based on the available logistics services of different companies that achieve seamless convergence of logistics services, satisfy user com鄄 plex requirements, and realize the value addition. Recently, owing to the technologies of web services, cloud computing, and service sciences, an increasing number of logistics companies have registered themselves as logistics web service providers. The logistics serv鄄 ices composition should satisfy the user爷s global QoS constraints and provide the best quality of service (QoS. ) Currently, with the rapid development of cloud computing, e鄄commerce, service computing, and modern logistics industry, many logistics services are available on the network providing similar functions and different levels of QoS. These factors make the problem of determining the opti鄄 mal composition of a logistics service a typical Np鄄hard problem. This study proposes a method to achieve the dynamic optimal composi鄄 tion of domain QoS and resource鄄aware logistics services and to realize logistics services that are dynamic, offer quality of domain serv鄄 ices, and are aware of resource requirements. First, the learning artificial bee colony algorithm (LABC) is proposed; LABC is applied to decompose the global QoS constraints into local QoS constraints that logistics task nodes must satisfy and to transform the global opti鄄 mization problem of logistics service composition into a local optimal service selection problem. Second, during the process of logistics service process execution, for each task node, the logistics service with best domain QoS evaluation, which can satisfy the local QoS constraints and resource requirements, is chosen to achieve a high鄄quality dynamic logistics service and optimal composition of service. The results of simulation experiments show that the proposed method is feasible and effective. KEY WORDS domain QoS; resource鄄aware; logistics web services composition; QoS constraint decomposition; artificial bee colony
徐园园等：领域Q$与资源感知的物流服务动态优化组合方法 ·883· algorithm 随着服务计算、云计算、物联网、电子商务等高 对模型进行求解.文献[7]为解决第三方物流服务 新技术的迅速发展，智慧物流服务行业也得到快速 平台中服务的优化组合问题，开展了基于智能体的 地发展.目前，通过智能计算技术整合拥有不同业 服务优化组合研究，提出基于agent的Web服务组 务功能的物流服务，从而满足用户的复杂物流服务 合模型，设计服务组合的流程，分析了基于agent的 需求，成为智慧物流服务行业发展的主要方向.而 物流Wb服务组合关键问题.文献[8]为了满足对 如何基于大规模多领域的可用物流服务，聚合成功 云服务组合的个性化需求，对一类含有物流服务的 能强大的可以满足用户复杂业务需要的大粒度物流 服务组合QS评价方法进行研究，建立了有物流服 服务，进而促进物流服务商之间的协作，加速物流服 务的云服务描述模型，在此基础上计算云服务的相 务业的发展与增值，是现代物流服务业发展的主流 关指标，为对指标值进行科学的综合评价，提出了一 方向小.目前，大多数物流公司依据Wb服务、云 种基于历史数据的主客观结合指标权值设定方法. 计算、服务科学等技术，将其拥有的物流业务封装成 文献[9]提出了一种能够感知实时情景信息的物流 物流Web服务，并将这些物流Web服务发布到物 服务动态组合方法，该研究工作通过改进的遗传算 流服务平台上，供物流服务系统调用.物流服务系 法对全局Q$约束进行了分解，得到了物流服务流 统在接收到用户的物流业务需求后，通过组合可用 程每个任务节点需要满足的局部QS约束，以此将 的物流服务形成最优的物流服务组合方案，从而为 属于全局优化问题物流服务组合转变成了局部最优 用户提供一站式的便捷的综合物流服务[].因此， 服务选择问题，在物流服务组合时，选择满足实时情 物流服务优化组合是实现不同物流服务商之间的智 景需求的最优物流服务.但该研究工作采用遗传算 能协作、促进物流行业的快速发展以及提高用户满 法对全局QS约束进行优化分解，效率较低，寻优 意度的关键技术 结果不太理想，并且在进行物流服务组合时，没有考 物流服务优化组合过程可以描述为：物流服务 虑物流服务的领域QS属性以及物流服务执行时 系统在接收到用户的物流业务需求后，对用户的业 所需要的资源状况，本文的研究工作是在该研究工 务需求进行分解，提取出关键的物流子任务，并设计 作基础上开展的深化研究.文献[10]针对基于QS 出由这些关键物流任务节点组成并且能够满足用户 的物流Wb服务组合优化问题，提出了两阶段多目 总业务需求的物流服务流程：之后，针对物流服务流 标蚁群优化法.首先，针对原始数据集中存在被支 程的每个物流子任务，从其候选物流服务集中选取 配候选服务而增加算法求解时间的问题，提出了基 一个具体的物流服务来执行该物流任务，由这些所 于支配的预优化策略：其次，针对属性权重难以确定 选择的物流服务构成的整个物流服务方案即为一个 的问题，提出了不依赖权重的信息素更新策略和启 物流服务组合[).随着云计算、电子商务、服务计算 发信息策略：最后，针对基础蚁群算法容易陷入局部 以及物流行业的快速发展，网络上出现了大规模功 最优的问题，提出了懒蚂蚁策略 能相同或相似而服务质量(quality of service,QoS)有 国外方面，文献[11]基于社会学家提出的在商 很大差别并且具有很强动态性的物流服务，这些因 业圈内，企业更加倾向于与熟悉的伙伴进行合作这 素使得物流服务优化组合问题成为一个典型的Np- 一理念，定义了伙伴圈，减小候选物流服务的规模， hard问题[4-] 结合服务组合的路径规划，提出了基于社交网络的 合作者优先的物流服务组合方法.文献[12]提出了 1研究现状与思考 一种用于解决在物联网环境下物流服务组合的中间 近年来，国内外学者针对物流服务优化组合问 件，该中间件采用分散式协调机制，利用很少的资源 题展开了研究并取得了一定的研究成果.国内方 高效地监测组件服务，并通过实验验证了该方法的 面，文献[6]通过对云物流环境下服务组合问题特 有效性与健壮性 点的分析，构建了多路径云物流服务组合过程模型， 上述QoS感知的物流服务组合方法虽然取得 结合云物流服务组合路径多样性、结构复杂性、资源 了一定的研究成果，但还存在以下不足： 按时刻表触发等特点，采用多属性效用函数理论，建 (1)已有的研究工作通常通过全局优化方法获 立了基于最大效用度的带触发时刻表的多路径服务 取一个近似最优的物流服务组合方案，然而，由于物 组合数学模型，提出融合串行调度的混合遗传算法 流服务具有很强的动态性，往往导致在设计阶段所
徐园园等: 领域 QoS 与资源感知的物流服务动态优化组合方法 algorithm 随着服务计算、云计算、物联网、电子商务等高 新技术的迅速发展,智慧物流服务行业也得到快速 地发展. 目前,通过智能计算技术整合拥有不同业 务功能的物流服务,从而满足用户的复杂物流服务 需求,成为智慧物流服务行业发展的主要方向. 而 如何基于大规模多领域的可用物流服务,聚合成功 能强大的可以满足用户复杂业务需要的大粒度物流 服务,进而促进物流服务商之间的协作,加速物流服 务业的发展与增值,是现代物流服务业发展的主流 方向[1] . 目前,大多数物流公司依据 Web 服务、云 计算、服务科学等技术,将其拥有的物流业务封装成 物流 Web 服务,并将这些物流 Web 服务发布到物 流服务平台上,供物流服务系统调用. 物流服务系 统在接收到用户的物流业务需求后,通过组合可用 的物流服务形成最优的物流服务组合方案,从而为 用户提供一站式的便捷的综合物流服务[2] . 因此, 物流服务优化组合是实现不同物流服务商之间的智 能协作、促进物流行业的快速发展以及提高用户满 意度的关键技术. 物流服务优化组合过程可以描述为:物流服务 系统在接收到用户的物流业务需求后,对用户的业 务需求进行分解,提取出关键的物流子任务,并设计 出由这些关键物流任务节点组成并且能够满足用户 总业务需求的物流服务流程;之后,针对物流服务流 程的每个物流子任务,从其候选物流服务集中选取 一个具体的物流服务来执行该物流任务,由这些所 选择的物流服务构成的整个物流服务方案即为一个 物流服务组合[3] . 随着云计算、电子商务、服务计算 以及物流行业的快速发展,网络上出现了大规模功 能相同或相似而服务质量(quality of service,QoS)有 很大差别并且具有很强动态性的物流服务,这些因 素使得物流服务优化组合问题成为一个典型的 Np鄄 hard 问题[4鄄鄄5] . 1 研究现状与思考 近年来,国内外学者针对物流服务优化组合问 题展开了研究并取得了一定的研究成果. 国内方 面,文献[6]通过对云物流环境下服务组合问题特 点的分析,构建了多路径云物流服务组合过程模型, 结合云物流服务组合路径多样性、结构复杂性、资源 按时刻表触发等特点,采用多属性效用函数理论,建 立了基于最大效用度的带触发时刻表的多路径服务 组合数学模型,提出融合串行调度的混合遗传算法 对模型进行求解. 文献[7]为解决第三方物流服务 平台中服务的优化组合问题,开展了基于智能体的 服务优化组合研究,提出基于 agent 的 Web 服务组 合模型,设计服务组合的流程,分析了基于 agent 的 物流 Web 服务组合关键问题. 文献[8]为了满足对 云服务组合的个性化需求,对一类含有物流服务的 服务组合 QoS 评价方法进行研究,建立了有物流服 务的云服务描述模型,在此基础上计算云服务的相 关指标,为对指标值进行科学的综合评价,提出了一 种基于历史数据的主客观结合指标权值设定方法. 文献[9]提出了一种能够感知实时情景信息的物流 服务动态组合方法,该研究工作通过改进的遗传算 法对全局 QoS 约束进行了分解,得到了物流服务流 程每个任务节点需要满足的局部 QoS 约束,以此将 属于全局优化问题物流服务组合转变成了局部最优 服务选择问题,在物流服务组合时,选择满足实时情 景需求的最优物流服务. 但该研究工作采用遗传算 法对全局 QoS 约束进行优化分解,效率较低,寻优 结果不太理想,并且在进行物流服务组合时,没有考 虑物流服务的领域 QoS 属性以及物流服务执行时 所需要的资源状况,本文的研究工作是在该研究工 作基础上开展的深化研究. 文献[10]针对基于 QoS 的物流 Web 服务组合优化问题,提出了两阶段多目 标蚁群优化法. 首先,针对原始数据集中存在被支 配候选服务而增加算法求解时间的问题,提出了基 于支配的预优化策略;其次,针对属性权重难以确定 的问题,提出了不依赖权重的信息素更新策略和启 发信息策略;最后,针对基础蚁群算法容易陷入局部 最优的问题,提出了懒蚂蚁策略. 国外方面,文献[11]基于社会学家提出的在商 业圈内,企业更加倾向于与熟悉的伙伴进行合作这 一理念,定义了伙伴圈,减小候选物流服务的规模, 结合服务组合的路径规划,提出了基于社交网络的 合作者优先的物流服务组合方法. 文献[12]提出了 一种用于解决在物联网环境下物流服务组合的中间 件,该中间件采用分散式协调机制,利用很少的资源 高效地监测组件服务,并通过实验验证了该方法的 有效性与健壮性. 上述 QoS 感知的物流服务组合方法虽然取得 了一定的研究成果,但还存在以下不足: (1)已有的研究工作通常通过全局优化方法获 取一个近似最优的物流服务组合方案,然而,由于物 流服务具有很强的动态性,往往导致在设计阶段所 ·883·
·884· 工程科学学报，第40卷，第7期 构建的最优物流服务组合方案在运行时失效：此外， 性、灵活性与可靠性，有助于提高物流服务组合的综 这些解决方法不能在物流服务流程执行中进行最优 合服务质量，从而提高用户的满意度.本文工作的 物流服务选择，其动态性与灵活性有待提高 创新点包括： (2)已有的物流服务优化组合方法仅依据物流 (1)提出了一种学习人工蜂群算法，利用该算 服务的一般QS属性进行物流服务优化组合，没有 法将全局QoS约束分解成局部QS约束，从而提高 考虑物流服务的领域服务质量，事实上，物流服务的 了全局QoS约束分解的效率. 领域服务质量更能体现物流服务的质量，更能提高 (2)提出了领域QoS度量模型，该模型可以度 用户的满意度.因此，在进行物流服务优化组合时， 量多种数据类型的领域QS指标.本文提出了一种 需要考虑物流服务的领域QoS. 以一般QoS属性为约束，以领域QoS评价值为依据 (3)已有的研究工作缺乏对物流服务运行时对 的物流服务选择方法，该选择方法可以提高物流服 资源需求的考虑.事实上，每一个物流服务的成功 务组合的领域服务质量 运行都必须获得一定类型与数量资源的支持.因 (3)提出了一种资源满足性检测方法并将其纳 此，在进行物流服务优化组合时，需要考虑物流服务 入物流服务动态优化组合的过程中.该工作能够保 是否具备足够的资源来保证其成功执行，从而提高 证所选择的物流服务具备的资源，从而能够满足完 物流服务组合的成功率. 成该物流任务对资源的需求，降低物流服务优化组 为了弥补现有研究方法中存在的不足，该研究 合的失败率 工作给出了一种能够感知物流服务的领域服务质量 2物流服务优化组合问题 以及资源需求的物流服务动态优化组合方法.本文 首先对人工蜂群算法(artificial bee colony algorithm, 首先以一个包括陆运服务、仓储服务、报关服 ABC)进行了改进，将学习机制引入人工蜂群算法， 务、海运服务以及空运服务的物流服务过程(CLS) 形成了学习人工蜂群算法(LABC):接着，基于学习 为例（如图1所示[]），来介绍物流服务优化组合问 人工蜂群算法(LABC)将全局QoS约束分解成局部 题.其中，CLS:(1≤i≤6)表示候选物流服务集合. QoS约束.通过全局QS约束分解，可以将属于全 基于该流程的物流服务动态优化组合问题，即是从 局优化问题的QS感知的物流服务优化组合问题， 每个物流任务节点对应的候选物流服务集中，依据 转变成一个属于局部优化的最优服务选择问题，这 一定的评价指标选定一个物流服务，使得由这些被 种问题转变在很大程度上降低问题求解的复杂度， 选择的物流服务所构成的物流服务组合，既能满足 提高物流服务优化组合的动态性与灵活性：最后，在 用户提出的QoS约束又具有最优的物流服务质量 物流服务运行过程中，从大量的候选物流服务中，为 随着物联网、云计算、移动终端以及物流行业的 当前的物流任务节点，选择一个能够满足资源需求 快速发展，网络上出现了大量可用的物流服务，使得 与局部Q$约束，又具有最优领域质量评价值的物 物流服务流程中的每个任务节点，具有大规模能够 流服务.该方法能够提高物流服务优化组合的动态 完成相同的物流任务而服务质量确相差很大的物流 存储服务1 陆运服务 存储服务2 报关服务 海运服务 空运服务 CL CLS CLS 图1：物流服务组合示意图 Fig.I Flowchart of the method of optimization of the composition of a logistics service
工程科学学报,第 40 卷,第 7 期 构建的最优物流服务组合方案在运行时失效;此外, 这些解决方法不能在物流服务流程执行中进行最优 物流服务选择,其动态性与灵活性有待提高. (2)已有的物流服务优化组合方法仅依据物流 服务的一般 QoS 属性进行物流服务优化组合,没有 考虑物流服务的领域服务质量,事实上,物流服务的 领域服务质量更能体现物流服务的质量,更能提高 用户的满意度. 因此,在进行物流服务优化组合时, 需要考虑物流服务的领域 QoS. (3)已有的研究工作缺乏对物流服务运行时对 资源需求的考虑. 事实上,每一个物流服务的成功 运行都必须获得一定类型与数量资源的支持. 因 此,在进行物流服务优化组合时,需要考虑物流服务 是否具备足够的资源来保证其成功执行,从而提高 物流服务组合的成功率. 图 1 物流服务组合示意图 Fig. 1 Flowchart of the method of optimization of the composition of a logistics service 为了弥补现有研究方法中存在的不足,该研究 工作给出了一种能够感知物流服务的领域服务质量 以及资源需求的物流服务动态优化组合方法. 本文 首先对人工蜂群算法(artificial bee colony algorithm, ABC)进行了改进,将学习机制引入人工蜂群算法, 形成了学习人工蜂群算法(LABC);接着,基于学习 人工蜂群算法(LABC)将全局 QoS 约束分解成局部 QoS 约束. 通过全局 QoS 约束分解,可以将属于全 局优化问题的 QoS 感知的物流服务优化组合问题, 转变成一个属于局部优化的最优服务选择问题,这 种问题转变在很大程度上降低问题求解的复杂度, 提高物流服务优化组合的动态性与灵活性;最后,在 物流服务运行过程中,从大量的候选物流服务中,为 当前的物流任务节点,选择一个能够满足资源需求 与局部 QoS 约束,又具有最优领域质量评价值的物 流服务. 该方法能够提高物流服务优化组合的动态 性、灵活性与可靠性,有助于提高物流服务组合的综 合服务质量,从而提高用户的满意度. 本文工作的 创新点包括: (1)提出了一种学习人工蜂群算法,利用该算 法将全局 QoS 约束分解成局部 QoS 约束,从而提高 了全局 QoS 约束分解的效率. (2)提出了领域 QoS 度量模型,该模型可以度 量多种数据类型的领域 QoS 指标. 本文提出了一种 以一般 QoS 属性为约束,以领域 QoS 评价值为依据 的物流服务选择方法,该选择方法可以提高物流服 务组合的领域服务质量. (3)提出了一种资源满足性检测方法并将其纳 入物流服务动态优化组合的过程中. 该工作能够保 证所选择的物流服务具备的资源,从而能够满足完 成该物流任务对资源的需求,降低物流服务优化组 合的失败率. 2 物流服务优化组合问题 首先以一个包括陆运服务、仓储服务、报关服 务、海运服务以及空运服务的物流服务过程(CLS) 为例(如图 1 所示[9] ),来介绍物流服务优化组合问 题. 其中,CLSi (1臆i臆6)表示候选物流服务集合. 基于该流程的物流服务动态优化组合问题,即是从 每个物流任务节点对应的候选物流服务集中,依据 一定的评价指标选定一个物流服务,使得由这些被 选择的物流服务所构成的物流服务组合,既能满足 用户提出的 QoS 约束又具有最优的物流服务质量. 随着物联网、云计算、移动终端以及物流行业的 快速发展,网络上出现了大量可用的物流服务,使得 物流服务流程中的每个任务节点,具有大规模能够 完成相同的物流任务而服务质量确相差很大的物流 ·884·
徐园园等：领域Q$与资源感知的物流服务动态优化组合方法 ·885· 服务.事实上，物流服务具有很强的动态性，并且物 服务类S的服务质量 服务类S的质量标尺 流服务资源对物流服务的成功执行具有较大的影 响，如何动态地构建出高质量可用的物流服务组合， 是一个亟需解决的难题 分解 为了解决这一难题，本文提出了一种领域QoS 与资源感知的物流服务动态优化组合方法，其主要 解决过程为：在物流服务流程执行之前，基于学习人 工蜂群算法将用户提出的全局QS约束分解成物 图2QS质量标尺的生成方法 流服务组合流程中每个任务节点需要满足的局部 Fig.2 Generation of the QoS quality scale QS约束：之后，在物流服务组合流程执行的过程 全局Q$约束优化分解的目标是为每个物流 中，从每个任务节点的候选服务集中，为每个任务节 服务类找出一组质量标尺组合（即局部QS约束）. 点选出既能满足局部QoS约束，具备满足应用需要 所求解出的质量标尺组合需要满足：(1)以质量标 的资源数量，同时又具有最优的领域QoS评价值的 尺组合为依据筛选出物流服务聚合成的物流服务组 物流服务.下面，介绍基于学习人工蜂群算法的全 合，也能满足全局QS约束：(2)依据质量标尺组合 局QS约束优化分解. 所筛选出来的候选物流服务的总数越大越好；所以， 3基于学习人工蜂群算法的全局Q0oS约束 用来评价质量标尺组合优劣的指标主要有两个，第 优化分解 一个指标是满足所有质量标尺组合的物流服务总数 本节首先详细介绍全局QoS约束优化分解模 目，其取值越大越好：第二个指标是所筛选出的候选 型：之后，给出学习人工蜂群算法(LABC)的主要优 物流服务的QoS评价值，这个指标的取值越大越 化操作设计，并详细给出了基于学习人工蜂群算法 好.基于上述分析，质量标尺组合的评价公式的定 的全局QoS约束优化分解过程. 义如下式所示： 3.1全局QoS约束优化分解模型 (QLC)(S) (2) 为了完成物流服务运行中的动态优化组合，最 m 重要的一点是确定每个物流任务需要满足的Qo$ 其中，n(QLC:)表示满足第j个物流服务类第i个质 需求：然而，在实际应用中，用户往往只对整个物流 量标尺组合的候选物流服务数量，m表示第j个物 服务提出全局性的QoS约束，因此，只有通过全局 流服务类中包含的候选物流服务的总数；U(S) QoS约束分解才能获取每个任务需要满足的局部 表示在序号为j的服务集中，以序号为i的质量标尺 QoS约束.在对全局QoS约束进行分解时，首先统 组合为依据，筛选到的所有物流服务QoS评价值的 计每个物流任务节点历史候选物流服务Qo$指标 最大值. 的取值情况，利用统计的方法计算出物流服务流程 在对候选物流服务的QoS属性进行评价时，首 中各个任务节点，对应的物流服务类所有QS属性 先对每个QoS指标的取值进行标准化.QoS属性标 的取值区间，基于评分的方法将所确定的每个QoS 准化公式为公式(3)或公式(4).其中，k表示物流 属性的取值区间分成d份，每一份称为一个质量标 服务QoS属性的个数，Q(U,k)表示序号为j的物 尺.一个物流服务类的QS质量标尺的生成过程如 流服务类的第k个QoS指标的最大取值，Qm(j,k) 图2所示[】. 表示序号为j的物流服务类的第k个QS属性的最 图2中，S为物流服务流程中第广个任务节点 小取值.在对候选物流服务进行评价之前，需要对 的物流服务类：k是全局QoS约束中涉及的QoS指 其所有的QS属性值进行标准化，对于效益型的 标的数目：m为第j个任务节点的所具有的候选物 QS指标，依据公式(3)进行标准化：对于成本型的 流服务的数目，每个任务节点对应一个物流服务类； QoS属性依据公式(4)进行标准化. d为质量标尺的数量；9：为第j个物流服务类的第 f(qk)= m个候选物流服务的第k个QoS属性的取值；L为 Qmxj,k)-qk(s） 第j个物流服务类中第k个QoS属性的第d个质量 0G,)-QG,h’if0G,k)≠Q0,k): 标尺，质量标尺符合以下公式条件： 1, if (j,k)=Qi(j,k). Q(j,k)≤L4≤L层≤…≤L≤Qm（j,k)(1) (3)
徐园园等: 领域 QoS 与资源感知的物流服务动态优化组合方法 服务. 事实上,物流服务具有很强的动态性,并且物 流服务资源对物流服务的成功执行具有较大的影 响,如何动态地构建出高质量可用的物流服务组合, 是一个亟需解决的难题. 为了解决这一难题,本文提出了一种领域 QoS 与资源感知的物流服务动态优化组合方法,其主要 解决过程为:在物流服务流程执行之前,基于学习人 工蜂群算法将用户提出的全局 QoS 约束分解成物 流服务组合流程中每个任务节点需要满足的局部 QoS 约束;之后,在物流服务组合流程执行的过程 中,从每个任务节点的候选服务集中,为每个任务节 点选出既能满足局部 QoS 约束,具备满足应用需要 的资源数量,同时又具有最优的领域 QoS 评价值的 物流服务. 下面,介绍基于学习人工蜂群算法的全 局 QoS 约束优化分解. 3 基于学习人工蜂群算法的全局 QoS 约束 优化分解 本节首先详细介绍全局 QoS 约束优化分解模 型;之后,给出学习人工蜂群算法(LABC)的主要优 化操作设计,并详细给出了基于学习人工蜂群算法 的全局 QoS 约束优化分解过程. 3郾 1 全局 QoS 约束优化分解模型 为了完成物流服务运行中的动态优化组合,最 重要的一点是确定每个物流任务需要满足的 QoS 需求;然而,在实际应用中,用户往往只对整个物流 服务提出全局性的 QoS 约束,因此,只有通过全局 QoS 约束分解才能获取每个任务需要满足的局部 QoS 约束. 在对全局 QoS 约束进行分解时,首先统 计每个物流任务节点历史候选物流服务 QoS 指标 的取值情况,利用统计的方法计算出物流服务流程 中各个任务节点,对应的物流服务类所有 QoS 属性 的取值区间,基于评分的方法将所确定的每个 QoS 属性的取值区间分成 d 份,每一份称为一个质量标 尺. 一个物流服务类的 QoS 质量标尺的生成过程如 图 2 所示[13] . 图 2 中,Sj 为物流服务流程中第 j 个任务节点 的物流服务类;k 是全局 QoS 约束中涉及的 QoS 指 标的数目;m 为第 j 个任务节点的所具有的候选物 流服务的数目,每个任务节点对应一个物流服务类; d 为质量标尺的数量;qjkm为第 j 个物流服务类的第 m 个候选物流服务的第 k 个 QoS 属性的取值;L d jk为 第 j 个物流服务类中第 k 个 QoS 属性的第 d 个质量 标尺,质量标尺符合以下公式条件: Qmin (j,k)臆L 1 jk臆L 2 jk臆…臆L d jk臆Qmax(j,k) (1) 图 2 QoS 质量标尺的生成方法 Fig. 2 Generation of the QoS quality scale 全局 QoS 约束优化分解的目标是为每个物流 服务类找出一组质量标尺组合(即局部 QoS 约束). 所求解出的质量标尺组合需要满足:(1) 以质量标 尺组合为依据筛选出物流服务聚合成的物流服务组 合,也能满足全局 QoS 约束;(2)依据质量标尺组合 所筛选出来的候选物流服务的总数越大越好;所以, 用来评价质量标尺组合优劣的指标主要有两个,第 一个指标是满足所有质量标尺组合的物流服务总数 目,其取值越大越好;第二个指标是所筛选出的候选 物流服务的 QoS 评价值,这个指标的取值越大越 好. 基于上述分析,质量标尺组合的评价公式的定 义如下式所示[13] : F(QLCji) = n(QLCi) m ·U max QLCi (Sj) (2) 其中,n(QLCi)表示满足第 j 个物流服务类第 i 个质 量标尺组合的候选物流服务数量,m 表示第 j 个物 流服务类中包含的候选物流服务的总数;U max QLCi ( Sj) 表示在序号为 j 的服务集中,以序号为 i 的质量标尺 组合为依据,筛选到的所有物流服务 QoS 评价值的 最大值. 在对候选物流服务的 QoS 属性进行评价时,首 先对每个 QoS 指标的取值进行标准化. QoS 属性标 准化公式为公式(3)或公式(4). 其中,k 表示物流 服务 QoS 属性的个数,Qmax (j,k)表示序号为 j 的物 流服务类的第 k 个 QoS 指标的最大取值,Qmin ( j,k) 表示序号为 j 的物流服务类的第 k 个 QoS 属性的最 小取值. 在对候选物流服务进行评价之前,需要对 其所有的 QoS 属性值进行标准化,对于效益型的 QoS 指标,依据公式(3)进行标准化;对于成本型的 QoS 属性依据公式(4)进行标准化. f(qk) = Qmax(j,k) - qk(s) Qmax(j,k) - Qmin (j,k) , if Qmax(j,k)屹Qmin (j,k); 1, if Qmax(j,k) = Qmin (j,k) ì î í ïï ïï . (3) ·885·
·886· 工程科学学报，第40卷，第7期 f八q)= 示所有物流服务类共有的第k个QoS指标，QL.为 Q(j,k)-q:(s) 序号为n的物流服务类中，序号为k的QoS属性的 (jk)-Q(jk) if (j,k)≠Qin(j,k); 第e个质量标尺，图3中的一行表示对应物流服务 1 if ,k)=Q(,k) 类的一个质量标尺组合 (4) (2)食物源评价函数. 在把每一个候选物流服务的QS属性值进行 由于食物源是由所有物流服务类的质量标尺组 标准化后，可以根据下式来获得每个候选物流服务 合构成的所以，食物源的评价值应为食物源中每个 的QoS评价值 质量标尺组合评价值的和，根据这种情况，本文给出 了食物源评价函数，如下式所示： U(S)= ∑fg)4 (5) k= F(x)=∑F(QLC) (6) 在公式(5)中，0：表示物流服务的第k个QoS 属性的权重. 其中，为食物源中质量标尺组合的序号（也是物流 全局QS约束优化分解问题亦为最优质量标 服务类的序号)，n为食物源中所有质量标尺组合的 尺组合选择问题，为了实现该问题的高效求解，本文 总数，i为序号为j的物流服务类的一个质量标尺组 对当前性能较好的新型群体智能算法（人工蜂群算 合，F(QLC)表示食物源中第j行的评价值. 法)进行了改进，引入了学习机制，形成了学习人 (3)初始食物源的生成策略 工蜂群算法LABC,之后采用该算法求解最优质量 这里基于随机方法生成规模为SN的初始食物 标尺组合选择问题， 源.操作方法为：对于每一个物流服务类，依次从其 3.2学习人工蜂群算法 质量标尺集合中随机地抽取一个质量标尺，将所抽 为了能够提高人工蜂群算法的全局寻优能力与 取的质量标尺放在一起构成一个质量标尺组合：所 收敛速度，本文将协作学习机制引入人工蜂群算法， 有物流服务类的质量标尺组合形成的一个二维矩阵 使雇佣蜂与观察蜂采用学习操作完成邻域的搜索， 即为一个初始食物源.如此操作，直至生成SN个食 进而生成新的食物源.下面给出用于求解全局QS 物源 约束分解问题的学习人工蜂群算法的设计 (4)改进的雇佣蜂与观察蜂的新食物源生成 (1)食物源模型. 方法. 全局QS约束优化分解的目标是获取每个物 在基本的人工蜂群算法中，雇佣蜂与观察蜂通 过对某一维变量的计算生成新的食物源，而这种处 流任务节点需要满足的QoS约束，由于物流服务组 理方式不能直接用于求解全局Q$约束优化分解 合流程由多个任务节点构成（每个任务节点对应一 个物流服务类)，所以，全局QS约束优化分解问题 问题，为了使人工蜂群算法能够用于求解全局QoS 约束分解问题，本文针对雇佣蜂与观察蜂的邻域搜 的解是由所有物流服务类的质量标尺组合构成，该 索操作进行了改进，对食物源实施基于协作学习的 解不能用一维的食物源编程方式来表示，为了这解 学习操作，协作学习[]是一种根据学习者的特征进 决这一问题，这里构建了一种二维的食物源模型，如 行有效性分组并通过分组形式进行学习的一种策 图3所示 略，具有很好的寻优指导思想，本文引入协作学习机 图3中，LS。表示序号为n的物流服务类，Q表 制可以有效地提高算法的性能 Q 0 Q Q LS QL Q凸 具体操作为：针对当前雇佣蜂所拥有的食物源， Q山 QL. 再随机地从食物源中抽取一定数量的食物源组成一 QL QL QL 个个体组，然后将个体组内的每个解分成若干个子 IS, 部分，这些个体相同的子部分通过相互学习，推选出 QL QL QL 具有最优评价值的子部分，最后由那些具有最优评 价值的子部分构成一个新个体.适用于求解全局 Q.L Q.L Q.人 Q QS约束分解问题的学习操作，如图4所示，其中， 1,2,…,14表示通过随机选取的方式确定的个体， 图3食物源模型 这里把个体中的行当作是个体的组成部分，不同的 Fig.3 Coding method of the food source 行表示个体不同的组成部分，图4中带有颜色部分
工程科学学报,第 40 卷,第 7 期 f(qk) = Qmax(j,k) - qk(s) Qmax(j,k) - Qmin (j,k) , if Qmax(j,k)屹Qmin (j,k); 1, if Qmax(j,k) = Qmin (j,k) ì î í ïï ïï . (4) 在把每一个候选物流服务的 QoS 属性值进行 标准化后,可以根据下式来获得每个候选物流服务 的 QoS 评价值. U(Sj) = 移 k k = 1 f(qk)wk (5) 在公式(5)中,wk 表示物流服务的第 k 个 QoS 属性的权重. 全局 QoS 约束优化分解问题亦为最优质量标 尺组合选择问题,为了实现该问题的高效求解,本文 对当前性能较好的新型群体智能算法(人工蜂群算 法[14] )进行了改进,引入了学习机制,形成了学习人 工蜂群算法 LABC,之后采用该算法求解最优质量 标尺组合选择问题. 3郾 2 学习人工蜂群算法 为了能够提高人工蜂群算法的全局寻优能力与 收敛速度,本文将协作学习机制引入人工蜂群算法, 使雇佣蜂与观察蜂采用学习操作完成邻域的搜索, 进而生成新的食物源. 下面给出用于求解全局 QoS 约束分解问题的学习人工蜂群算法的设计. (1)食物源模型. 全局 QoS 约束优化分解的目标是获取每个物 流任务节点需要满足的 QoS 约束,由于物流服务组 合流程由多个任务节点构成(每个任务节点对应一 个物流服务类),所以,全局 QoS 约束优化分解问题 的解是由所有物流服务类的质量标尺组合构成,该 解不能用一维的食物源编程方式来表示,为了这解 决这一问题,这里构建了一种二维的食物源模型,如 图 3 所示. 图 3 食物源模型 Fig. 3 Coding method of the food source 图 3 中,LSn 表示序号为 n 的物流服务类,Qk 表 示所有物流服务类共有的第 k 个 QoS 指标,QnkLe 为 序号为 n 的物流服务类中,序号为 k 的 QoS 属性的 第 e 个质量标尺,图 3 中的一行表示对应物流服务 类的一个质量标尺组合. (2)食物源评价函数. 由于食物源是由所有物流服务类的质量标尺组 合构成的,所以,食物源的评价值应为食物源中每个 质量标尺组合评价值的和,根据这种情况,本文给出 了食物源评价函数,如下式所示: F(x) = 移 n j = 1 F(QLCji) (6) 其中,j 为食物源中质量标尺组合的序号(也是物流 服务类的序号),n 为食物源中所有质量标尺组合的 总数,i 为序号为 j 的物流服务类的一个质量标尺组 合,F(QLCji)表示食物源中第 j 行的评价值. (3)初始食物源的生成策略. 这里基于随机方法生成规模为 SN 的初始食物 源. 操作方法为:对于每一个物流服务类,依次从其 质量标尺集合中随机地抽取一个质量标尺,将所抽 取的质量标尺放在一起构成一个质量标尺组合;所 有物流服务类的质量标尺组合形成的一个二维矩阵 即为一个初始食物源. 如此操作,直至生成 SN 个食 物源. (4)改进的雇佣蜂与观察蜂的新食物源生成 方法. 在基本的人工蜂群算法中,雇佣蜂与观察蜂通 过对某一维变量的计算生成新的食物源,而这种处 理方式不能直接用于求解全局 QoS 约束优化分解 问题,为了使人工蜂群算法能够用于求解全局 QoS 约束分解问题,本文针对雇佣蜂与观察蜂的邻域搜 索操作进行了改进,对食物源实施基于协作学习的 学习操作,协作学习[15]是一种根据学习者的特征进 行有效性分组并通过分组形式进行学习的一种策 略,具有很好的寻优指导思想,本文引入协作学习机 制可以有效地提高算法的性能. 具体操作为:针对当前雇佣蜂所拥有的食物源, 再随机地从食物源中抽取一定数量的食物源组成一 个个体组,然后将个体组内的每个解分成若干个子 部分,这些个体相同的子部分通过相互学习,推选出 具有最优评价值的子部分,最后由那些具有最优评 价值的子部分构成一个新个体. 适用于求解全局 QoS 约束分解问题的学习操作,如图 4 所示,其中, I1 ,I2 ,…,Ik 表示通过随机选取的方式确定的个体, 这里把个体中的行当作是个体的组成部分,不同的 行表示个体不同的组成部分,图 4 中带有颜色部分 ·886·