毕业设计（论文）-云制造模式下的服务组合优化.docx

全套设计加扣 3012250582南京邮电大学 毕 业 设 计（论 文）题 目云制造模式下的服务组合优化专 业网络工程学生姓名班级学号指导教师指导单位物联网学院 日期： 2017年 1月 15日至 2017年 6月 16日毕业设计（论文）原创性声明本人郑重声明：所提交的毕业设计（论文），是本人在导师指导下，独立进行研究工作所取得的成果。除文中已注明引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写过的作品成果。对本研究做出过重要贡献的个人和集体，均已在文中以明确方式标明并表示了谢意。 论文作者签名： 日期： 年 月 日摘 要 当今世界，国内外经济发展日新月异。面对互联网金融的冲击，制造业正面临着前所未有的挑战。云制造模式充分融合了现有的制造模式，利用企业对于制造资源的共享的需求，将企业的制造资源池联系在一起，提供制造资源服务，提高了制造资源的使用率。而在云制造模式中服务组合问题是解决优化资源配置的关键，制造服务组合问题（Manufacturing Service Composition，MSC）就是如何选择合适的服务来完成制造任务，但是传统的计算方法不能有效的解决MSC问题。因此，采用智能优化算法来解决MSC问题便成为当前研究的热点。本文从云制造模式研究意义和背景入手，概括归纳了云制造模式下服务组合模型的特征。根据MSC问题研究的步骤，选择合理的服务质量参数，建立了云制造模式下服务组合适应度函数模型。利用标准粒子群算法对模型进行仿真，并针对粒子群算法在问题规模增大的情况下表现不佳的缺点，提出了一种改进的粒子群算法（an Improved Particle Swarm Optimization，IPSO），对原始粒子群算法进行了优化。通过实验仿真，分析了在子任务数量和候选服务集数量不断变化的情况下IPSO算法的性能，并与其他三种开源算法进行比较。结果表明，在数据规模比较大时，IPSO算法的优化效果和收敛精度都远好于对比的开源算法。关键词：云制造；服务组合；粒子群算法；智能优化 ABSTRACTNowadays, domestic and international economic development is changing with each passing day. The manufacturing industry is facing unprecedented challenges because of the Internet banking. The cloud manufacturing mode fully integrates the existing manufacturing model, using the demand of enterprise for manufacturing resource sharing. This mode links the manufacturing resources pool together to provide the manufacturing resource services. The service composition problem in the cloud manufacturing mode is the key to resolving the optimal resource allocation problem. The key factor in the application of cloud manufacturing mode is how to choose the right service to complete manufacturing tasks. The problem of Manufacturing Service Composition (Manufacturing Service Composition, MSC) is how to choose the right service to complete the manufacturing tasks, but the traditional method of computing does not solve the MSC problem effectively. Therefore, using the intelligent optimization algorithm to solve MSC problem has become the focus of current research.This paper begins with the research meaning and background of cloud manufacturing mode, summarizes the characteristics of the service composition model under the cloud manufacturing model. According to the steps of the MSC problem, this paper selects the reasonable quality of service parameters and establish the model of the fitness function in the cloud manufacturing mode. In view of the disadvantages of particle swarm optimization, we used standard particle swarm optimization to simulate the model, and proposed an improved particle swarm optimization(an Improved Particle Swarm Optimization，IPSO)algorithm. This algorithm is suitable for the large-scale data. Through experiment simulation, this paper analyzes the IPSO algorithm performance and compar with the other three open source algorithms with the changing of subtasks and candidate services. The results show that the optimized results of IPSO algorithm and the convergence accuracy are better than the open source algorithms when the data scale is large.Key words：Cloud Manufacturing; Service Composition; Particle Swarm Optimization; Intelligent Optimization目 录第一章 绪论11.1 研究的背景和意义11.2国内外研究现状21.3 主要研究内容和章节安排3第二章 服务组合问题42.1服务组合问题的定义42.1.1基本服务组合问题的定义42.1.2单任务服务组合42.1.3多任务服务组合52.2服务组合问题模型的建立62.2.1制造云服务组合的三个阶段62.2.2制造云的QoS参数选择与函数建立72.3服务组合问题研究流程102.4本章小结11第三章 一种改进的粒子群算法123.1标准粒子群算法123.1.1标准粒子群算法理论123.1.2标准粒子群算法原理123.1.3标准粒子群算法的流程143.1.4标准粒子群算法优缺点153.2一种改进的粒子群算法实现163.2.1改进策略163.2.2算法改进163.2.3算法参数的选取173.2.4算法流程223.3对比算法描述233.3.1DE算法描述233.3.2GL25算法描述243.4本章小结25第四章 仿真实验与结果分析264.1实验模拟环境264.1.1云制造模式数据集选取264.1.2QoS模型建立264.1.3实验环境配置274.2 与其他算法的比较与分析274.2.1开源算法的选取274.2.2子任务集不变算法比较274.2.3候选任务集不变算法比较334.3算法收敛性分析394.4实验结果分析414.5本章小结42结束语43致 谢44参考文献45全套设计加扣 3012250582第一章 绪论1.1 研究的背景和意义当前世界经济发展迅速，数据处理量大，整个制造业的市场需求也发生着迅速的变化，面对日新月异的市场发展，经济全球化的大潮一方面为生产带来了许多便捷，另一方面也加剧了市场的竞争，而中国的传统支柱产业制造业也不知不觉陷入了比较尴尬的境地，一部分的大型企业掌握着生产制造的资源，却因开工不足而被迫闲置，浪费了许多的资源。另一方面一些中小型企业因为资源不足无法完成制造需求。可以说中国的制造业到了最紧张的时期，这种说法并非是“空穴来风”，目前国内的许多小成本制造商基本面临着亏本甚至倒闭的严重问题，如图1.1所示为国家统计局公布的2016年9月中国制造业采购经理指数图1： 图1.1 2016年9月中国制造业采购经理指数图从图中可见从2015年9月以来制造业采购经理指数增长幅度缓慢，甚至出现下降，这与当前中国经济发展速度是不成正比的。在这种形势下，许多中小型企业为了自身的生存团结起来，共享制造资源，共同克服制造难题，而对于大型企业来说也愿意合理利用他们的闲置资源，其中的关键问题就是汇聚制造资源，对服务进行优化配置，这就意味着企业制造资源的共享成为了新的研究方向与挑战。云制造（Cloud Manufacturing，CMfg）的概念应运而生，“制造即服务”是云制造追求的宗旨，它融合了现有的制造模式，充分利用企业对于制造资源的共享的需求，在企业间建立共享的制造资源服务平台，为加入平台的企业和用户提供制造资源服务，提高了制造资源的使用率。在这种共享模式中，一般存在着三种角色：服务提供商、服务平台和服务用户2。其中服务提供商提供制造资源以及包装好的制造服务；服务用户产生制造需求，这种需求一般被划分为功能性的和非功能性的，本文针对研究的服务质量（Quality of Service，QoS）问题为非功能性需求问题3；服务平台分析产生的需求并合理安排划分，选择相对最优的制造服务来满足不同的需求。基于这种共享模式的云制造模式已经成为了中国制造业智能化发展的方向。服务组合（Service Composition)是使用特定的方式以给定的需求为标准将若干服务组合成为一个逻辑整体的方法、过程和技术4。云制造环境下的服务组合就是在当前大规模工业制造生产情况下对制造业的各个需求参数进行模拟组合来降低生产成本。云制造模式下的服务组合问题的研究过程实际上就是QoS参数的选择与适配的对应过程。在实际制造环境中，随着不同服务质量需求的制造指数的增加，如何合理的配置服务资源，选择最佳服务的服务组合路径成为了难题，制造服务组合问题（Manufacturing Service Composition，MSC）就是这样一个难题。MSC问题由于其数量级巨大，路径组合问题可以被抽象为一个NP（Non-deterministic Polynomia）难问题，因此使用传统的计算方法显然不能解决这个问题，现代科学家对自然界进行深入的研究后，开发了一系列的智能算法用于解决这个问题，然而当前智能算法大多着眼于局部优化策略或者是全局优化策略，很少有算法能兼顾这两者，这会造成在研究这类问题时存在着优化程度不够或是算法过早收敛的情况。同时MSC问题的研究的考虑规模也偏小，存在对于子任务数量的设置偏小、候选任务服务集设置不合理等问题，随着大数据时代的到来，制造业的个性化与多样化需求也越来越多，一个任务也必定会分成许多子任务，子任务数量的增加就意味着MSC问题规模的增加，那么大规模的MSC问题的研究不可避免。本文借助研究粒子群算法对于该问题的影响与不足，对算法进行改进与比较，尤其是在针对相对较大规模情况下的算法收敛性的比较与研究。综上所述，在当前经济环境下，云制造已经成为中国制造业发展的新方向，而云制造模式下的服务组合也成为了必不可少的研究内容。1.2国内外研究现状服务组合问题是本文要解决的最根本的问题，然而针对这个问题，目前为止，MSC问题的研究仍然比较有限，而在Web环境中的服务组合的研究已经相对比较成熟。Web服务组合使用简单的逻辑把用户在网络中的需求服务简化为一条路径5，把离散的各类相关Web服务组织成一个更加强大的系统服务，简单的说就是把无序的服务有序化，用来支持企业内外的Web服务应用。Web服务组合可以从组合的方向上分为静态组合与动态组合两种类型。无论是在静态还是动态模型中，QoS参数的合理选择以及对应适应度函数的确定都成为了重中之重。然而在研究MSC问题时，制造服务具有的多样性、复杂性、行业特殊性造成Web服务组合不能够简单迁移成为云制造模式下的服务组合问题6。对比Web服务组合，云制造环境下的服务组合中如何合理的调度与分配资源成为了棘手的问题，对于服务的组合能够把具体的需求问题抽象为数学问题，我们可以建立对应的数学模型对服务的需求进行分析。目前国内对于云制造环境下的服务组合研究仍然较为缺失，陶飞等7对云制造中的资源、制造云服务、制造云这三者之间的关系进行了解释与比较并设计了云制造服务组合模型的研究特点和组织结构。夏亚梅等8为了解决服务组合优化与QoS参数选择局限等问题，提出过一种更新的蚁群算法来动态匹配服务组合模型。上述的研究人员都对MSC问题提出了新的模型与研究方向。1.3 主要研究内容和章节安排综合考虑了上述研究背景，本文针对云制造模式下的组合问题进行探索，建立针对云制造模式中的QoS参数约束的模型，建立服务组合路径，并利用改进的粒子群算法对模型进行仿真模拟，综合横向比较在较大数据规模情况下改进算法与一般开源算法之间的区别。第一章阐述云制造模式产生背景和原因、服务组合问题研究的现状，概括了云制造服务组合问题的研究方向，并简述了论文的基本框架。第二章具体介绍云制造模式下服务组合问题的问题定义，以及针对问题建立起的QoS参数模型。第三章介绍了标准粒子群算法对于服务组合问题的解决机制与在实际应用中的不足之处，阐述针对粒子群算法的优化策略。第四章针对云制造服务组合模型应用改进的粒子群算法进行模拟实验并对结果进行分析。第二章 服务组合问题2.1服务组合问题的定义2.1.1基本服务组合问题的定义 服务组合问题是把一系列无序需求问题有序化的过程。云制造环境下的服务组合就是指在当前大规模工业制造生产情况下对制造业的各个需求参数进行模拟组合来降低生产成本9。服务组合问题并不是简单的把所有需求的服务进行排列，服务如何进行最优化的排列需要建立完善的数学模型，通常可以把这种架构称为面向服务的架构10（Service-Oriented Architecture，SOA）。SOA的应用构造包含以下几种与之息息相关的技术：（1）建模技术：在云制造模式下的服务组合就是在调研企业制造生产实际后，对于企业的制造流程与需求进行模型化，用数学符号与公式描述企业制造中的服务组合问题，在这个阶段中，由服务平台创建描述服务的数学模型，包括请求任务与请求任务的规定完成时间、对任务可靠性的需求程度和任务产生的经费开销的估计、任务的可维护性指标等。（2）分析和仿真技术：在此部分中，服务平台将对服务组合模型的建立情况进行定性和定量的分析，对服务组合路径进行组合，通过设计实际的制造场景数据对过程进行仿真测试，发现关键路径的组合方法。（3）编程技术：针对制定好的服务组合模型将其转换成可执行的服务组合代码。利用智能算法进行优化处理，对结果进行仿真测试。（4）部署和执行技术：在这个阶段将把编好的服务组合代码在实际的执行引擎上进行执行，对实际场景下的执行结果进行测试，进一步改进并进行实际部署。（5）监控技术：在监控工具帮助下，对服务组合代码应用于云制造场合中的数据进行实时的反馈与分析，对程序发生的错误及时发出警告监控服务组合的执行情况。（6）优化技术：根据监控反馈的结果对服务组合模型与代码进行更新优化。由于操作空间有限，本文只针对前3个步骤进行讨论与实践。在深入研究了用户的请求服务数量与请求服务之间的复合关系后，可以把在云制造模式下的服务组合问题分为单任务情况下的服务组合问题与多任务情况下的服务组合问题。2.1.2单任务服务组合面向单任务的服务组合与优化问题11-13（Single-Task Oriented Services Composition and Optimization，STO-SCO），所谓单任务指的是当用户向服务平台提交了一种服务需求后，服务平台选择合理的基础服务进行组合以达到最佳QoS的规划过程，在满足单个任务请求的QoS约束的前提下，实现服务组合整体QoS的最大化。在基本服务组合问题中，服务组合问题存在着四种基本结构模式：（1）串行结构；（2）并行结构；（3）选择结构；（4）循环结构。基于这四种结构模式，可以把用户的任务请求组合为一个粗粒度的服务模型，再在粗粒度模型的基础上对请求任务进行组合优化成为一个相对结构良好的组合模型13。通常情况下，单任务情况下的服务组合问题的模型通过数学方法来刻画，采用非功能参数指标对于任务请求进行描述，即QoS约束，QoS约束参数一般包含时间、成本、可维护性、可靠性等因素。在给出了QoS约束参数后，需要针对参数结合模型进一步给出服务组合问题评价指标的具体计算公式 12。文献14提出了一种服务模型，这个模型采用自适应网络感知的形式，建立了QoS参数转换的机制，并利用改进遗传算法进行仿真，综合考虑优化所耗时间和用户任务请求完成度之间的关系；文献15重新定义评估模型，在现在使用的QoS评估模型中加入两个分类参数，把制造资源分成软资源和硬资源，并且评估了软硬服务之间的联系与区别，定义了软硬服务之间的转化方法，从用户请求角度出发，完整的诠释了重视用户请求的服务组合模型。文献16提出了一种新的服务组合问题解决方法，颠覆了传统的思想，在服务组合模型中，评估属性通常从制造者自身出发，即我拥有什么资源，我能提供什么服务，却很少考虑用户需要哪些服务也没有个性化定制用户的需求，该文献提出的层次分析法指的是在已有的QoS参数基础上建立QoE评价指标，综合考虑服务提供者已经拥有的资源、用户在制造生产活动中的实际需求，从而提高服务组合的服务质量。我们已经充分了解了单任务情况下云制造服务组合的问题描述与研究现状，本文最主要针对单任务情况下的制造云服务组合问题进行深入的研究与讨论。2.1.3多任务服务组合面向多任务的服务组合与优化问题，即用户在制造模式中的需求可能不止一种，那么用户可能给服务平台提交了多个任务请求，服务平台选择其中一个或多个基础云制造服务，合理配置QoS服务组合参数，从全方位满足用户多样性的需求。由于多任务服务组合指的是多个任务请求之间的并发调度，那么就说明在多任务模型中每一个子任务都具有其具体的功能性需求。因此，多任务的服务组合问题，需要的是组合好的多个任务请求进行整体的决策，并不是从字面上理解的多个单任务模型情况下的堆叠。也就是说并不是每个需求的最优相加后就能得到多任务下的优化情况，目前对于多任务的服务组合问题的研究仍然在如火如荼的进行着。文献17提出了针对实际制造环境中的多任务请求模式问题，分析多个任务请求组合在一起的服务组合结构模式问题，提出了多任务模式下QoS评价指标的建立函数和计算方法，该文献建立一个面向用户的多任务服务组合模型。但这些其实还远远不够，多任务研究问题中，如何综合考虑制造者资源与用户的复合请求问题仍然没有一个非常完美的答案。实际上多任务环境下的服务组合问题仍然等待模型的完善与突破，在本文的研究中，未着重研究讨论多任务情况下的服务组合问题。2.2服务组合问题模型的建立解决服务组合优化问题，必须对请求的任务建立框架与模型，对比工作流管理系统中QoS参数的确定与模型的建立，对应服务组合情况中的QoS参数需要考虑在实际生产生活中制造行业对于服务参数的需求，建立起对应的参数转化，并采用相加相减设置合理权重等方式对参数进行组合12，并编写适应度函数。在实际场景中的云制造服务组合是一个有向图，有着许多路径结构包括顺序、并行、循环等结构，这些结构可以被转换成为序列结构。根据上述序列结构能有效的建立起参数的转换机制。2.2.1制造云服务组合的三个阶段 单任务云制造模式下的服务组合问题是一个非常典型的MSC问题，可以分为云制造任务分解、需求服务匹配、云制造服务路径组合三个阶段18，综合三个阶段的结果生成服务组合路径19-20。云制造服务组合路径选择结构如图2.1所示：（1）云制造任务分解过程：首先用户发起了云制造任务请求，云服务平台可以将由任务请求分解成为一个个的不能再被分解的子任务，实际上来说，服务组合的维度就是由这些子任务数决定的，假设表示云制造单一子任务。那么，其中D表示子任务数，如图2.1子任务图中所示，图中D取值为4。考虑可以把任务请求分解为4个独立的子任务。（2）需求服务匹配过程：对于第一阶段中的每一个被分解的子任务，根据任务请求在制造云服务平台中搜索对应的候选云服务，挑选出来的候选云服务组成了候选云服务集，每个个子任务都会搜索对应的服务。如图2.1中需求服务匹配图所示，对于上一阶段的四个子任务进行相互的匹配与组合。（3）云制造服务路径组合过程：针对前两个阶段所产生的结果，从步骤（2）生成的序列中随机抽取一个候选云服务，对于抽取出来的云服务，利用智能算法生成组合路径，在多条组合路径中进行优选，优选过程实际上就是QoS参数选择和对应适应度函数建立的过程。如图2.1中组合路径图所示：图2.1 服务组合路径选择结构图2.2.2制造云的QoS参数选择与函数建立分析调研目前在制造业中产生的服务组合的实例，结合在制造生产过程中对生产因素的控制指标和用户的需求指标，我们可以建立针对MSC问题的QoS参数21，结合这些参数就可以把具体的服务组合问题进行数学模型化与形式化，建立起对应的数学函数，并根据调研结果给出合理的约束条件。在一般的QoS参数选择模型中，都是把选择的参数相加后求取参数的最小值就是问题的最优值，但是云制造服务和一般的模型有所不同，需要考虑生活中的实际需求情况，简单的相加并不能满足用户实际的需求情况。假设子任务数是已经经过分解后的单一任务需求，其中D代表单个给定请求的子任务数，表示第一个子任务，表示第D个子任务，i 代表对应子任务数，表示第i个子任务。本文中假设候选服务集为集合，并定义候选服务集数目为，那么对于每个子任务来说包含个候选服务，其中 j 代表候选服务数， 。使用的QoS指标集评价每个候选服务。根据前期的调研结果，选定主要的QoS指标如下：（1）时间T：在云制造服务组合模型中，T指的是过程中所有产生的与时间有关的参数。T既包括服务本身需要执行的时间也包括在服务处理传输时系统交互消耗的时间。组合效果要想达到最佳化效果，那么时间参数越小越好。在服务组合问题中，时间指标采取相加的形式，并最终取求和最小的那组时间指标，定义为随变化的一个变量，则时间函数如公式（2-1）所示： （2）成本C：在云制造服务组合模型中，C指的是服务用户为了达成该服务所花的代价与开销。同样C既包括服务本身成本也包括在系统交互时产生的成本，在成本函数中包含两个部分共同构成，分别是服务本身时间和系统交互时间，这两个时间相加之后才是最终的成本函数的结果。在成本问题考虑中，成本越小越优的特性是毋庸置疑的，同样成本因素也必须采用累加求和的方式进行，同样定义为随变化的一个变量，即定义成本函数如公式（2-2）所示： （3）可靠性R：在云制造服务组合模型中，R指的是一个服务能否正常持续运行的评估因素，可靠性要求是对于现在企业一个非常实际的约束参数，针对这个约束参数可以有许多考量标准，如单位时间内的平均故障率等，在考虑可靠性因素时，由于使用的都是概率参数故不能对各个参数进行累加处理，但是可靠性因素仍然是越大越优，对于可靠性因素需要取累乘处理结果的最大值，面对当前问题就是减去的可靠性参数，即定义为随变化的一个变量，可靠性函数如公式（2-3）所示： （4）可维护性MA：在云制造服务组合模型中，MA指的是云制造服务组合资源能够应付突发事故的能力和可维护的能力，可维护性是成功处理事故总数的比例占意外事故总数的比例，在实际使用中用户更加青睐可维护性高的服务，那么对于可维护性参数来说，同样需要取可维护性因素累乘的最大值，同样需要在适应度函数中减去这个参数，并定义为随变化的一个变量，即定义可维护性函数如公式（2-4）所示： （5）信誉V：在云制造服务组合模型中，V指的是服务信誉即在给定的条件下能否完成服务请求，它用来衡量一个服务的能力，这个服务参数最主要来用于用户的评价反馈，在制造环节中，一个制造服务的信誉反馈决定了这个服务在用户心中的质量标准，同样信誉参数也应该选择平均值计算进行考量，假设N为任务请求数，并定义为随变化的一个变量，那么信誉函数如公式（2-5）所示： 综上所述是服务组合的QoS的参数选择，综合考虑上述参数，能够建立起一个相对完整的描述制造云服务质量的模型，在实际应用场景中的云制造服务组合路径可以被抽象为一个有向图，能够用连接关系来代表错综复杂的路径结构，其中主要包含四种子结构：顺序、并行、选择和循环结构。在一定条件下，为了减少问题的复杂性，并行，选择性和循环结构可以被转换成序列结构。因此，本文的MSC问题是基于序列结构建模。在这种结构中，表示参数的个数，而则表示第个参数的QoS值。在本文建立的模型中，我们选取5个参数，根据参数特点，对这5个参数详细的描述他们各自的计算方法，QoS参数含义及计算方法如表2.1所示：表2.1 QoS参数含义及计算方法表寻找最佳路径的目的是尽量减少T，C参数指标，同时最大化R，M，V参数指标，前文已经给出了各自参数的计算公式。我们使用常用的加权求和法来计算最终的服务质量结果。因此，制造云服务组合的QoS适应度函数MSC问题的目标函数如公式（2-6）所示： 其中。相对应的w值为每个参数的对应权重，在本文实验中，对各个权重考虑比例一致。对于一个服务组合的适应度函数来说，越小证明越优22，所以在计算适应度值的过程中需要对适应度函数取最小值处理，即最终适应度函数的取值为公式（2-7）所示： 在完成了适应度函数的建立后就完成了服务组合优选模型的建立，接下来需要考虑的问题就是如何通过数学仿真方法，智能计算结果并针对用户完善这个QoS服务优选模型。2.3服务组合问题研究流程本文研究的主要问题是云制造模式下的服务组合问题，针对当前制造业面临的实际问题提出的组合服务研究，云制造模式下的服务组合问题的流程分为几个部分共同构成，首先对提出的服务组合需求进行分析，分解制造任务，接着进行需求的匹配过程，然后选取合适的服务质量参数，建立拓扑转换机制，形成服务组合路径，最后使用智能算法对模型进行仿真测试，在本文中还将横向比较各优化算法，分析改进后的算法对于解决云制造环境下的服务组合优化问题的优势。本文中的云制造服务组合问题研究流程图如图2.2所示：图2.2 云制造服务组合问题研究流程图2.4本章小结本章首先定义了服务组合问题，对于服务组合问题的建立与解决步骤给出了较为详细的解释，叙述了单任务和多任务情况下的服务组合问题的本质与当前研究结果并叙述了本文主要研究的方向，然后根据云制造模式下的特性和用户使用制造产品的因素等建立了问题分析步骤，依据3个步骤对服务组合问题进行分析，并选取了5个指标共同描述服务的质量，给出了每个指标的计算方法，得出了QoS量化表达式。最后，在这些分析基础上，得出适应度函数的计算表达式。本章主要建立了服务组合问题研究的数学模型。第三章 一种改进的粒子群算法3.1标准粒子群算法 在前一章QoS适应度函数建立后，基本解决了MSC路径选择问题，但MSC问题由于其数量级巨大，路径组合过于复杂，通过穷举法进行计算消耗的时间无法计算，可以被抽象为一个NP难问题，因此使用传统的计算方法显然不能解决这个问题，现代科学家对自然界进行深入的研究后，开发了一系列的智能算法用于解决这个问题，在本文研究中针对标准的粒子群算法进行研究与改进。我们通过讨论标准粒子群算法（Standard Particle Swarm Optimization，SPSO）的局限性，提出了一种在大规模数据环境下能够更好解决服务组合问题的改进算法。3.1.1标准粒子群算法理论粒子群优化（Particle Swarm Optimization, PSO）算法是20世纪末由两位学者受到了人工生命研究结果的启发，提出了一种类似于自然界中鸟群觅食迁徙的过程的基于群体的全局搜索优化算法，自然界中的各种生物都有群体的生活方式与习惯，研究人员在对自然界中群体性行为研究中考虑迁移研究到人工智能服务上，能够在计算机上模拟自然界中普遍存在的群体行为。在研究鸟类觅食过程仿真模型中，学者发现每只鸟都遵循一定的规则：（1）不与相邻的同伴发生碰撞；（2）学习同伴的飞行速度；（3）当群体拥有共同目标时总是向中心靠拢一起接近目标。如果遵循上述这三条规律的话，我们就可以通过计算机仿真模拟出鸟群飞行的路径。在这个规律基础上，研究者们提出了粒子群算法，他的基本思想就是收到鸟类觅食的群体活动的影响，运用上述的三条规则，把单个鸟比作一个粒子，对于粒子进行更新演化，描述其群体迁徙路径，使得粒子飞向解空间，最终形成一个粒子群。在解决服务组合问题时，分布式制造系统可以通过粒子群优化算法选择一个最佳的服务组合方案23。粒子群算法具有参数结构少、结构简单、没有交叉与变异运算并拥有记忆性等优势，但同样也存在着缺乏动态调节、收敛程度低、解决问题存在局限性等劣势。在大规模数据情况下，SPSO算法的劣势显然不能完全适应服务组合问题的需求，仍然需要算法的理解与改进。3.1.2标准粒子群算法原理鸟群的飞行实际上是一个决策过程，在一个个粒子的初始阶段，他们的位置都是随机产生的，飞行方向也是随机的，每只鸟都想吃到食物，但食物的位置却是不固定的，自然界的鸟在飞行过程中会自动组成一个群落，互相学习共享共同寻找食物。粒子群算法也是如此，每只鸟（粒子）都会与相邻的粒子组成一个群落，每只鸟通过自身掌握的经验和信息估计目前寻找到的食物的价值，这个价值就是适应值，也是最终输出的解值，每只鸟在飞行过程中会不断相互比较和更新这个适应值，最终找到一个最优值，这个值被称为局部最优值（Pbest）。鸟类在群体中也会互相比较更新适应值，在通过所有群体比较之后得出的最优值就被称为全局最优值（Gbest）24。SPSO算法原理也可以通过数学公式的方法来描述，假设我们拥有D维的粒子搜索空间，表示每个粒子的维数与位置，粒子的总数为N，表示第个粒子的D维矢量，就表示第一个粒子的一维矢量位置，那么粒子群落空间的表达式如公式（3-1）所示： 表示每个粒子的速度矢量，即为第个粒子的D维矢量速度，表示第一个粒子的一维矢量速度，那么粒子的速度矢量定义如公式（3-2）所示： 第个粒子的个体的极值可以被定义为，为第个粒子的D维矢量个体极值，表示第一个粒子的一维矢量个体极值，那么粒子个体极值公式如公式（3-3）所示： 第个粒子的全局的极值可以被定义为，为粒子的个体极值比较后相对的全局极值的D维矢量，表示一维矢量的全局极值，全局极值的表示公式如公式（3-4）所示： 上述公式（3-3）与（3-4）即为粒子需要跟踪比较的两个极值，这两个极值就决定了算法粒子最终的位置，粒子需要通过互相之间的比较来进行位置速度更新，假设c1和c2为学习因子，为惯性权重，r1和r2为在0到1之间随机产生的两个数，那么粒子具备的惯性速度即为，表示粒子惯性状态即保持当前搜索速度情况。粒子具备速度即为，这表示的是粒子的记忆能力，即相比较历史上的最佳的位置进行迁移的能力，这是粒子根据自身的经验产生的结果。粒子具备的社会速度即为，这部分的速度表示的是粒子群体活动的能力，即粒子做出像群体或局部解空间最佳位置移动的能力。综上所述，粒子根据公式用来更新自己位置和速度的表达式如公式（3-5），（3-6）所示： 其中；表示的是惯性权重，是一个非负数，为约束因子，用来控制速度变量的权重25。粒子群算法用于解决服务组合问题时就是把通过适应度函数组合好后的数据作为一个个需要更新的粒子，对于每个服务质量结果的组合进行上述的迭代更新过程，最终收敛成为一个相对最优的服务质量组合结果。3.1.3标准粒子群算法的流程SPSO算法在解决服务组合问题时的步骤流程如下：（1）随机初始化种群中各个粒子的位置、速度，完成参数的设置；（2）分别计算随机粒子适应度，得出初始的适应度值；（3）根据步骤（2）产生的结果，计算出两个极值初始结果；（4）根据公式（3-5）更新粒子的飞行速度；（5）根据公式（3-6）更新每个粒子的当前位置；（6）对每个粒子，比较自身现在位置与历史位置，向更好的位置方向进行迁徙。这个位置即为当前最好位置，也就是个体极值（Pbest）；（7）在当前群落中比较所有的当前最好位置和历史上最好的位置，仍然向更好的位置方向进行迁徙，可以得到全局极值（Gbest），更新一次适应度值就记录一次，用于观察算法的收敛性；（8）在服务组合问题中，我们使用迭代次数来控制粒子群算法的结束，如果满足了迭代次数，停止当前搜索，否则返回步骤（2）；（9）输出粒子全局极值以及算法收敛过程中的每次迭代的值。SPSO算法流程图如图3.1所示：图3.1 SPSO算法流程图3.1.4标准粒子群算法优缺点 粒子群算法作为一个兼具全局搜索能力与局部优化策略的智能优化算法，非常依赖控制参数的选择，这些控制参数包括粒子群的初始化、惯性因子、学习因子等等。标准的粒子群算法有着许多的优点：（1）算法适用场合广，不完全依赖于问题类型，所以对服务组合类问题也有着不错的优化效果；（2）计算简单容易实现；（3）搜索能力较强，同时具有局部的搜索策略与全局搜索能力；（4）搜索全局最优解的能力强，云制造模式下，数据集维度较大，对全局最优解的期望性较强。SPSO算法的缺陷也是非常明显的：（1）算法局部搜索能力较差，算法发明时间早，搜索准确程度不够高；（2）算法早熟问题明显，在应用SPSO算法解决高纬度复杂的问题时，算法非常容易陷入过早收敛，也就是说鸟（粒子）在觅食过程中没有找到最好的食物就停了下来，因为粒子的飞行动力不足，丧失了多样性，飞行速度几乎为零。（3）算法搜索性能对参数的选择依赖性大，参数选择直接影响算法的搜索能力，对待特定问题，需要选择不同的参数配置。（4）算法研究有限，对待大规模多约束问题的研究相对比较少。标准粒子群算法在解决服务组合问题时存在着收敛度低，大规模数据集下算法性能差的许多缺点，因此许多研究者也尝试对粒子群算法进行更新演化。根据当前的研究结果，本文同样对粒子群算法在大规模数据集下的性能提升进行了算法的改进。综上所述，标准粒子群算法在解决单目标约束优化问题上仍然存在明显的缺陷，本文提出了一种改进的粒子群算法（an Improved Particle Swarm Optimization，IPSO）来解决这个缺陷。3.2 一种改进的粒子群算法实现云制造模式下，数据维度比较大，即使是针对单任务情况下的服务组合问题，数据的运算量仍然非常可观。这就需要选择一个针对全局进行优化的算法。SPSO算法正是这样一个算法，因此我们在本次实验中选用的就是针对粒子群算法全局优化策略的研究与改进。本文针对优化问题，混合改进了粒子群算法的惯性权重和学习因子，让他们更加适应于大规模数据集情况，相比较其他三种对比算法性能会有明显的提升。3.2.1改进策略算法的核心就是算法的更新公式，对算法更新公式的合理改进就可以使得算法适应于不同场景下的问题，在解决云制造模式服务组合问题时，对于算法的全局搜索能力需求较大，希望改进后的粒子群算法可以在处理高维度问题时优化性能更好。粒子群的改进策略如下：（1）惯性权重参数选择，如果惯性权重参数选择较大，那么粒子的速度权重就比较大，粒子运动更加剧烈，全局的搜索能力就会增强，如果惯性权重设置比较小，那么算法的局部精度就会更强，收敛精度也会随之增强26；（2）更改学习因子，粒子群算法中存在两个正整数学习因子和，分别表示粒子的自身经验与群体经验，SPSO算法中学习因子的选择相对固定，无法满足大规模数据问题，合理的更改学习因子能够极大的避免算法陷入局部最优的问题。3.2.2 算法改进智能算法是优化计算的一种方法，显而易见的是一个算法的性能特点关键看的是更新公式，对于更新公式的优化就是对于算法的优化，而观察粒子群算法更新公式（14）可以发现粒子群算法的公式中包含有很多的参数，在保持粒子群算法局部策略不变的基础上，改变粒子群算法更新公式中的参数选择完成对于算法的改进：（1）惯性权重：顾名思义，惯性权重指的是惯性运动在算法中的比例，在物理学中，惯性指的是一个物体保持运动的状态，同样在PSO算法中，作为个体存在的粒子也是具有“惯性”的，这样会使得粒子保持运动状态27。粒子惯性权重越大说明算法的全局搜索能力越优，在大规模问题处理下的表现也就越好，但针对云制造模式下的服务组合问题，并不是一味的追求全局的最优解，局部的搜索策略也同样重要，本文希望通过合理的设置惯性权重，达到局部与全局搜索兼顾的结果。在标准粒子群算法中，通常设置惯性权重参数为一个定量，一般根据算法的版本，取值在0.6到0.75之间。如果惯性权重是一个变量取值的话，通常在迭代开始时设置一个非常大的惯性因子，然后逐步缩小其取值，这样粒子群在开始搜索时，可以搜索较大的解空间，得到合适的最优值，对于全局搜索的性能较好，后期逐渐减小惯性权重，让粒子收缩到一个比较优的区域内进行精密的搜索，局部的策略使得算法搜索的准确度也就越来越高。至于的取值，本章下一节将进行论述。（2）学习因子：学习因子指的是粒子在运动过程中调整自身的能力，可以类比于人类在面对选择时，依靠历史上的经验进行选择的权重或是依靠自身的现在经验进行选择的权重28。学习因子的选择直接决定了粒子“听谁的话”，粒子听谁的话就决定粒子寻优运动的方向，也就能决定一个算法的优化值。现有的对学习因子的研究基本与惯性权重的设置相同，在粒子群寻优过程中，我们希望前期粒子比较活泼，能够在大范围解空间内搜寻全局最优点，这样算法就不至于在很早的时候就陷入了局部最优。那么想要达到这一点，我们需要把取的比大，这样粒子就向自己历史上的最优Pbest值学习的多，而向社会的最优Gbest学习的少，这样算法的全局性就比较强，但在算法收敛后期同样需要精细的搜索，那么设置就需要相反的和，使得粒子向社会最优Gbest的局部解空间收缩，增强算法的局部搜索能力。综上所述，本文通过对SPSO算法中的惯性权重值和学习因子值的合理改进来更新算法公式，使得改进后的算法能够适用于云制造模式下的服务组合问题模型。这种改进算法本文称其为IPSO算法。3.2.3算法参数的选取在本文中，对粒子群算法的改进机制就是对算法的更新公式中的参数进行改进，IPSO算法主要对SPSO算法中的惯性权重值和学习因子值的合理改进来更新算法公式。通过观察标准粒子群关于速度的更新公式（12）可以发现，速度更新公式中的可变参数有惯性权重，学习因子和。作为一个兼具全局搜索能力和局部优化策略的智能算法，这些参数的合理设置共同决定了粒子群算法偏重方向。在本文研究的云制造服务组合问题中，全局的优化策略更应该被考虑，因为数据空间维度大，快速的寻优是目标重点，但是局部策略仍然不可忽视，在确定了大致的解后仍然需要局部的策略对算法进行持续的优化，避免算法的早熟。（1）粒子数m的选取：在参数设置选择阶段，首先需要考虑选取的参数就是粒子数m，粒子数的确定就确定了搜索的范围。在粒子群算法实验中粒子数m一般取值为20到40之间，调研显示，在针对大多数粒子群算法所解决问题中，粒子个数一般取在30个左右，但是粒子数量越多，搜索的空间也就越大，但是算法运行的时间也会随之增加。云制造服务组合问题研究的数据规模大，所以粒子的搜索空间相对来说也要大一些，在本文实验中，粒子数m的值选取为50。（2）惯性权重：惯性权重是评判算法收敛性的最主要的因素之一，在值比较大时，粒子飞行的幅度大，局部搜索能力比较弱，但是全局的搜索能力就比较强，如果值比较小，则相反。惯性因子比较大时，粒子运动激烈，会偏离原先的寻优区域，在新的方向上进行搜索，这样粒子就能搜索更大的空间，发现新的解域；而惯性因子越小，粒子在较大程度上会保留原先的寻优轨道，但是搜索空间的减小，就意味着搜索精度的增加，但是也会加速算法收敛29。在本文所用开源算法SPSO2007版本中，惯性权重的选值为12*log2，这是一个大于1.5的数值，但是仍然是一个固定不变的惯性权重，即无论在算法的前期或者是中期这都是一个基本基于全局最优的问题研究，同样选取SPSO2007算法的原因也在于此，这是一个典型的权重不变的问题的解决，并且是一个基于全局优化策略的问题的解决。本文模型需要综合考虑算法的全局策略和局部策略，动态改变粒子群算法中的惯性权重参数一直是研究的热点。一般的动态模型是在算法进化过程中动态的改变