服务计算中服务质量的多目标优化模型与求解研究

服务计算中服务质量的多目标优化模型与求解研究摘要：随着信息技术的不断发展和进步，传统的面向组件和系统的架构模式逐渐演变成面向服务的设计模式。服务计算作为一种新兴的计算模式，涉及到运筹学、系统工程等多门学科，其中的服务质量的优化过程，也越来越受到研究者的关注。文中从服务计算中广泛关注的多维度指标体系出发，结合具体的研究问题，总结了3种典型的多目标优化模型，并介绍了常用的多目标优化求解方法。最后对全文进行了总结。关键词：服务计算；服务质量；多目标指标体系1引言近年来，互联网的发展与普及为计算机软件的设计模式带来了新的思路与挑战。随着SOA（ServiceOrientedArchitecture）架构和服务技术的出现，传统的基于硬件和系统的架构模式逐渐转变为面向服务的设计模式。服务计算（ServiceComputing）作为一种新兴的计算模式应运而生。服务是指服务提供商和用户之间为实现特定的商业目标或解决方案的一种契约关系。服务计算则是服务提供商将特定的功能封装成为遵循统一标准的交互式的计算机程序，将其以服务的形式提供给不同商业领域中的多个用户使用的一种计算模式[1]。服务计算涉及到SOA架构，Web服务，网格计算，云计算等。随着服务计算的逐渐普及，用户需求的不断提高，服务计算系统呈现出动态性、松耦合、大规模等显著特点。对服务计算的研究，形成了涉及服务科学与信息技术的交叉学科，成为了目前学术界和工业界的研究热点。服务计算兴起之初，绝大多数研究主要关注于服务计算功能性需求的满足。随着服务计算被广泛应用，各种类型的应用对系统和服务提出了越来越高的要求，其中以服务质量（QualityofService，QoS）为代表的非功能性需求，逐渐被关注。如何对服务计算进行优化，选择最佳的服务解决方案，以适应用户和服务供应商的需求，成为研究者们关注的问题。服务计算的优化过程覆盖服务系统的整个生命周期，涉及到多个学科如运筹学、复杂系统建模、系统工程等[1]。起初研究者们在服务计算的优化过程中仅关注某一个指标，如最小化响应时间或最大化服务收益，因此该类问题常被刻画为单目标优化的问题。针对单目标优化的问题，目前已有一些经典的方法能进行求解，如凸优化方法、动态规划方法等[2][3]。随着用户和服务提供商需求多样化，关注的指标和属性逐渐增加，研究者们开始考虑将多个目标综合在一起进行优化，如何解决服务计算的多目标优化问题成为研究的热点。多目标优化问题不同于单目标优化问题，不同的目标之间可能存在权衡和折中的关系，很可能难以找到满足所有目标的单一最优解。因此单目标优化的方法无法直接适用于多目标优化，多目标优化在基础理论和实现方法上面临了新的挑战，解决多目标优化问题需要寻求新的思路和方法。本文综述了服务计算中多目标优化的模型和方法研究。首先系统地介绍了服务计算优化中所关注的多目标参数，包括4维指标体系和这些指标所涉及的服务计算中经典的问题。其次，总结了服务计算多目标优化最常用的3种模型，分别是线性加权、基于相互关系、帕累托模型，并从适用性解的优劣等方面对这种模型进行了分析和比较。随后，介绍了这3种多目标优化模型对应的解法，最后对全文进行了总结和对服务计算领域进行了展望。2服务计算中的指标体系服务计算的多目标优化涉及到一系列的指标，它们代表着用户、供应商的需求。这些指标有的作为优化的目标，需要被最大化或者最小化；有的作为约束变量，需要满足一定的限制条件。本文将从系统性能指标、安全可信指标、能源指标和经济指标这几个方面来介绍服务计算多目标优化的指标体系。系统性能指标反映了系统的处理能力或者效率，它是一个综合的因素，包括吞吐率、响应时间、阻塞率和利用率。服务计算的安全可信指标是衡量系统服务能力的重要指标，包括可靠性、可用性、可维护性、保险性、完整性和机密性。服务计算的能源指标是指能量消耗和产生的碳氧化合物。服务计算的经济指标包括系统的收益和开销，它们直接影响服务消费者和服务供应商的利益。这四维指标之间并不完全独立，它们两两之间皆相互有一定的影响，共同构成服务计算的指标体系如图1所示。阻塞率吞吐率响应时间利用率性能指标能耗碳氧化合物能源指标安全可信指标经济指标安全性可信赖性机密性完整性可用性可靠性可维护性保险性收益开销图1：服务计算的指标体系3多目标优化模型多目标优化问题不同于单目标优化的问题：单目标优化存在一个全局最优的解，它们或满足系统响应时间最低，或满足系统开销最小。而多目标优化往往难以存在一个满足所有目标函数的最优解。例如想要在最小化响应时间的同时最小化系统开销，可能是不切实际的。因为响应时间低意味着服务等级高，那么很可能为了高的服务等级需要多支付一定的费用。因此解决多目标优化问题需要借助其他的思路。下面总结并介绍服务计算多目标优化中常用的3种模型。3.1线性加权线性加权是多目标优化广泛使用的一种模型。它忽略不同目标函数有不同的单位和范围，通过给不同的目标函数制定相应的权重，将所有的目标函数进行线性加权，用一个综合的效用函数来代表总体优化的目标，从而将多目标优化问题转化成单目标优化问题。对于第i个目标函数()ifx，用iw表示它的权重，那么多目标优化模型可以转化成1min()kiiiwfxsujecttoxS（1）线性加权模型，其优点在于实现简单，仅用缩放后的值来代表原目标，求解也相对比较容易。其缺陷在于刻画目标和解不够精细，用加权的方法直接把指标归一化后相加对原始目标的信息有丢失和遗漏。且制定权重过程需要依据的用户、供应商对不同目标的偏好程度也很难提前获知，即使在已了解偏好程度的情况下，如何准确地制定权重仍然是棘手的问题。因此采用线性加权模型，虽然简便，但解的优劣程度难以保证。3.2基于相互关系多目标优化过程中，有时多个评价指标之间并非独立存在，可以存在一定的相互影响或制约的关系。在这样的情形下，线性加权的方法已不再适用。一些研究考虑指标之间的相互关系，提出了评价公式，用以对多个目标进行更好的综合优化。一个典型的基于相互关系的评价公式为计算机网络中延迟和吞吐量综合优化过程中常用的Power公式。如式（2）所示，其中Throughput为网络的吞吐量，ResponseTime为延迟，为常数，01。Power公式考虑了吞吐量和延迟之间的相互关系，可以用来评价网络中资源分配策略的有效性，用以确定最优负载公式，亦可用来评价Web服务的效率。ReThroughputPowersponseTime（2）3.3帕累托模型帕累托（Pareto）是多目标优化中经典的模型，下面给出帕累托相关的概念。首先介绍两个解之间的比较以及如何判断一个解的优劣情况。当最小化目标时，对于任意两个可行解12,xxS，当条件（3）成立时，1x被称为帕累托优胜2x。1212()(),{1,,}()(),{1,,}iiiifxfxikfxfxik（3）条件（3）即是1x对应的所有目标函数值都不大于2x的目标函数值，且至少有一个目标函数严格地小于2x的目标函数。当目标函数需要被最大化时，对帕累托比较没有大的影响，只需修改下比较的符号即可，如式（4）所示。1212()(),{1,,}()(),{1,,}iiiifxfxikfxfxik（4）帕累托模型中常出现两个解之间无法判断优胜关系的情况。例如目标函数包括响应时间、吞吐率两个优化目标，1x对应的目标函数值为（10，20），2x对应的目标函数值为（5，10），1x的响应时间比2x的差，但是1x的吞吐率要优于2x。帕累托最优解即是这样一组解的集合，它包含了所有不被任何其他解所优胜的解，并且集合中的解没有好坏之分。帕累托模型由于不需要对目标进行归一化，也不需要设定或者引入新的参数、变量（如权重、界限值），直接基于原始目标函数和值进行操作，可以适用于任何目标、任何函数。它不会丢失目标函数和解的信息，解的优劣可以较好保证。但帕累托模型的最优解是一个集合，其中包含不止一个最优解，因此要穷尽并求出所有的帕累托最优解有一定的难度。4多目标优化求解方法在第3节介绍了服务计算多目标优化的模型，它们以不同的方式、从不同的角度刻画优化中的多个目标，在本节中将总结服务计算多目标优化模型对应的求解方法。4.1转化成单目标求解单目标优化在近几十年来的研究和发展中已有比较成熟的体系，根据是否能够得到最优解可以将单目标优化的算法分为最优算法和启发式算法。4.1.1最优算法穷举法可以保证能取得最优解，是一种简单直观的最优算法。它通过枚举的方式列出优化问题所有的解，求解的复杂度依赖于解空间的大小。当解空间比较小时，穷举法能够较快地找到最优值。而当解空间增大时，穷举法由于要遍历所有的解而导致复杂度太高，效率太低。尤其在组合优化问题中，解空间随着变量个数增加以指数速度增长。以服务组合问题为例，假设一个复杂服务由n个子服务组成，而每一个子服务又有m个候选项，那么所有可能的解有nm个，在这样的情况下，使用穷举法无法高效地找到最优解。动态规划是求解最优化问题一类经典的算法，它通过组合子问题的解而解决整个问题。动态规划算法能解决的经典问题包括背包问题、装配线调度问题等。动态规划算法的运行时间取决于子问题的总个数和每个子问题中选择的个数，是这两者的乘积。相比于穷举法，动态规划算法的效率能够大大提高，但它的运行时间是伪多项式时间。图算法也常被使用来解决优化问题。一些研究将服务组合的问题抽象成图论问题，并采用图算法求解。相较于其他方法，图算法更加直观简洁，但某些情况下，使用图算法之前常常要先将原问题进行转化。此外，使用图算法往往需要获取服务部署的拓扑信息，在一些情况下甚至需要全局拓扑，优化前的信息获取可能耗费大量成本。最优算法能够保证求得结果的最优性，当问题比较简单时，它往往只需要多项式的运行时间，效率高而且准确。但当问题的难度逐渐增大时，最优算法很难高效地求出问题的最优解。启发式算法因此应运而生。4.1.2启发式算法贪心算法是求解最优化问题的一类有效的启发式算法，它常用于解决资源分配、任务调度问题[4]。贪心算法通过做出一系列的选择来寻找问题的最优解，对于其中任何一个决策点，贪心算法总是做出能产生当前最佳解的选择，也即达到局部最优解，进而期望能够通过局部最优解得到全局最优解。但贪心算法往往需要对已知的参数进行预处理，且无法保证得到最优解。相对于用复杂的方法求得最优解，很多时候人们更倾向于用快速的算法求得次优解。很多新颖的智能算法如蚁群算法、模拟退火算法、遗传算法等为解决这类难题提供了有利的工具。这些算法模拟自然现象和过程，构造起来直观且易懂，能够极大地提高效率，降低运行时间，但解的优劣无法保证，很多参数都对最终解造成影响。因此，如何设置合理的参数也是智能优化算法面临和需解决的问题。服务计算典型的单目标优化方法如图2所示：服务计算中单目标优化启发式算法最优算法贪心算法智能优化算法穷举法动态规划图算法遗传算法蚁群算法模拟退火算法图2：服务计算中单目标优化方法4.2帕累托模型求解方法帕累托最优解是指所有未被任何其他解所优胜的解。换言之，在维持其他目标函数值不变的情况下，它们拥有某一目标函数的最优值。帕累托最优解代表了不同目标之间的权衡，它们在多目标优化中具有举足轻重的地位。为了提高效率，一些关注在较短时间内求得帕累托次优解的启发式算法被提出。其中一种数学规划法通过依次考虑多目标中的某一个目标，仅仅将这个目标作为优化的对象而忽略其他的目标，以此得到该目标相关的若干个最优解，并且计算这些解在所有目标维度的值，之后得到帕累托解。采用这种方法可以得到在各个目标方向比较均衡的帕累托解，解的分布比较平衡。但是它的运行时间也严重依赖于解的个数。多目标进化算法也是求解帕累托解常用的方法。以遗传算法为例，它通过模拟自然界中生物进化的过程，算法最终以非零的概率到达某些收敛点，那些点即为对应问题所求的解。遗传算法主要有选择、交叉、变异这三个步骤。选择过程对应了自然界中物种选择，交叉过程模拟了生物的交配，而变异对应于基因变化的过程。遗传的基本单位是染色体，它代表了问题的解。因此遗传算