论文研究-适应模糊QoS约束优化的Web服务选择技术研究.pdf

所需积分/C币:9 2019-09-10 17:08:18 687KB .PDF
收藏 收藏
举报

基于QoS优化的全局Web服务选择涉及多目标和多阶段的服务合成,以及各种QoS属性的折衷,如可信性、可用性和声望等,因此提出了适当的基因算法来处理服务选择问题。由于发现质量驱动的Web服务选择是一个NP-hard问题,实际的多目标或QoS标准并不总是明确的,常常包含模糊元素。着重研究多目标Web服务选择过程中模糊QoS属性和适应进化函数之间的关系,以及如何调节个体模糊QoS属性以实现整个种群进化的问题。
682009,45(3) Computer Engineering and Applications计算机工程与应用 而弹性约束允许超过标准范围Km,KM变为实际最大边容易验证等式(15)的QoS约束满足等式(13)。 界,如图2所示 评估模糊QoS数值的约束满意度的一般方法,如图5所示。 (c) P(x a) min(p(T, a), c(x, a)lT )dT SalLey (x, a= (16) c(x alTd 因此,在Web服务选择的进化的过程中,适应函数可表示为 K K、 K nin(p(T,a),c(x, a)lr )dT 图2弹性约束 Fitness(x)=obj(x).c (17) c(,a 此时,约束满意度为 ←c(x,a)≤Ksm(i,a) 0(c,a)= c(x,a)2←Km<c(x,a)≤KMA (12) 基于QoS约束的全局web服务选择的形式化表示 在基于QoS约束优化的全局Web服务选择中,基因算法 ←c(x,a)>KMx(Z,a 由于满意度 Salley(e,a)位于区间p0,1.与约束相关的权所使用的适应函数不总是明确的,而是模糊的。此时,服务选 择按照模糊约束满足问题来处理。 重就将影响适应函数f(x)的QoS属性。 定义1(选择计划, Selection plan)基于模糊QoS约束的 3.2不精确QoS属性数值 全局Web服务选择( Services Selection based on global Fuzzy 对刚性QoS属性, Satler(x,a)=p(c(x,a),a)总是有效的 ° Qos Constraints, WSSFQC)可以表示为元组Psm-<M,7,S, 然而,对许多Q0s属性并非如此。如,响应时间有可能来自 SLA TD>,其中M表示抽象Web服务处理模型,7表示任务集合,S 中断言数值或以前监控的数值。考虑QS值是由区间c(x,a)=表示候选服务集合,TD(t):CS表示满足任务t功能要求 c1,cl而不是边界κ(a)来评估的简单情况,有以下三种情形 的具体Web服务集。其执行计划表示为plam={<t1,s1>,<2,s2>, (1)c2k(a);(2)c1<k(a);(3)c1≤k(a)≤c2 ,<tk,s>},其中t∈PT和s∈ PWSSFoC. TD(t)。设pla 第(1)种情况,任何估计值r∈[c,c位于边界κ(a)中,则 约束满意度 Satler(x,a)=1。第(2)种情况,当cκ<k(a)时,其估 定义2(Qos相关的模糊集,QoS- - related Fuzzy Sets)Ws 计值r超出范围之外,则 Satler(x,a)=0。第(3)种情况表示了 FQC涉及模糊QoS相关集(FQS),如代价,持续时间,声望和可 Ic1,c2]中的部分值可能位于约東范围之内,也可能位于约束范 用性、可依赖性等,也涉及模糊约束水平( fuzzy constraint lev 围之外,此时,约束满意度为 els, FCLev),如poor, good and fair等。可用 Fuzzy( PWSSFQC, Satler(r,a) Ka)-cl (13)FQs, FOLey)表示模糊QoS约束为FQS、选择计划为Ps模 假定由如图3所示的三角模糊数值表示为c(x,a) 糊约束水平为 FCLev的模糊集。 数值r∈(1,c有不同的真实度c(x,a)。范围κ(a)之内 定义3(Q0S约束的模糊表示, Fuzzy Expression for Qos 的一些值(Hr≤k(a)),其p(r,a)=1。范围之外的一些值Vr criteria)给定一个 WSSFQC,特定QoS约束可以表示为模糊表 k(a),其p(r,a)=0。此时,约束满意度为 示( Fuzzy Expression,F),由¨and”操作连接的一组模糊集合 组成。为表示用户的QoS折衷,QoS标准视为一系列模糊表示 Satlev(t, e)=cc(x,a) Ird (14)FE=e1fe2,…fe用“or”操作连接FE中的元素,可得到全部 c(x, a)lrd 用户的QS倾向 考虑与模糊QoS约束相关的 WSSFQC,无论服务选择计划 当模糊QoS数值基于区间e1,c时,即Ⅴr∈[1,cl,其隶属是否满足,其满意度表示为: 函数为c(x,a)r=1;若r≠e1,c2],其隶属函数为c(x,a)r=0 若QoS的值位于区 间c(x a)≡[c1,c2],而不是模糊范围 SatLer(plan )=sup P l ))) ∈FEp∈ Divisiones(Psk)a∈ Fuzzy(n',PQS, FOLey) (a)时(图4) 其中 Divis ione3(Pnsx)是许多部分 WSSFQC的集合,当加入 此时,约束满意度为 p'和p到当前选择计划时,(un(pla)表示其适应能力,由 P(T,ad 下列公式计算得到 SatLer(x, a= (15) u(s)=SatLev(plan U(t, s)) rngnedtasks c(x,a c, K(a) SID CI K KsD CI K 图3模糊(非具体)QoS数值估计 图4非刚性区间QoS值评估 图5非刚性模糊QoS数值评估 秦汝烈:适应模糊QoS约束优化的Web服务选择技术研究 2009,45(3)69 其中d表示没有指派任务的t的当前域,其相应的服务为s阈6讨论和结论 值αn表示最小满意度,d.S表示所有的服务选择集合,即dS 采用基因算法优化目标函数,实现模糊QoS属性的约束满 su(s)>m}。 足研究。同时,试图使用模糊适应函数来调节QoS约束,处理 不精确QoS数值评估。提出的方法能够调节个体模糊QoS属 5web服务基因选择算法的过程实例 性来适应整个种群的进化,具有一定的研究和实用价值。 Wcb服务基因选择算法如下 String Genetic Algorithm() 参考文献: [1 Ignacio RStatistical analysis of the main parameters involved n=0;∥/n:子代数 the design of a genetic algorithm[J .IEEE Transactions on Systems Man and Cybernetics, 2002: 31-37 initialize p(n) by encoding routine ∥p(n):染色体数 2 Zeng L, Benatallah B Quality driven Web services composition[Cy/ fitness evaluation(p) by decoding routing Proc of 12th Intel Conf Word Wide Web(WWw), Budapest, Hun gary,2003:4l1-421 While (not termination condition [3 Yang Lei. Dynamic selection of composite Web services based on a I Crossover p(n) to yield offspring; genetic algorithm optimized new structured neural network[C]/pro Mutation p(n) to yield offspring ceedings of the 2005 International Conference on Cyberworlds Fitness evaluation(p+offspring) by decoding routine (CW’05’),2005 n=n+1; 4 Cardoso J. Quality of Services and semantic composition of work- I return best_solution; flows[D]. Athens, GA: Univ of Georgia, 2002 5 Deb K Multiobjective optimization using evolutionary algorithms[MI 在基因算法操作期间,为保持适当的染色体多样性,进化 Wiley, Chichester, UK: Kalyanmoy Ded, 2001 个体x的适应函数应能控制整个群体的进化,即: 6 Olcer A L.An integrated multi -objective optimization and fuzzy multi-attributive group decision-making technique for subdivision evoluation p(n))=fit tness(x 18 1+H(n) arrangement of Ro-Ro vessels[J]Applied Soft Computing, 2006, 6 其中, fitness(x)表示个体x的适应函数x,H1(t)表示第x个体 21-243. [7 Hisashi S DCGA: a diversity control oriented genetic algorithm[Cp/ 的信息熵,n是所有染色体数。具有较适应数值和较低H、(t)数 The 9th IEee International Conference on Tools with Artificial 值的种群将生存下来,这与达尔文的进化论思想是相一致的。 Intelligence, 1997: 367-374 (上接59页) 来处理,提高了算法的效率。另外,此算法还应用了简单多边形 邻两个顶点P(x,y),PAx,ya),如果x>x则P(x,n)为单调链求凸点的算法,只需要比较相邻的顶点的横坐标值就能 凸点,否则不是顶点,把所有凸点分别依次存入B3,B4 得到要求的凸点,时间复杂度是线性的。 步骤9B(i=1,2,3,4)中的所有点依次按逆时针方向连接 起来,即为所求平面点集的凸包。算法结束。 参考文献 蒋红斐.平面点集凸包快速构建算法的研究J计算机工程与应用, 4算法的时间复杂性 2002,38(20):48-49. [2]金文华基于有序简单多边形的平面点集凸包快速求取算法J计 步骤2需要2「3n2-2次比较操作,假设B1中有n1个点, 算机学报,1998,21(6):533-538 步骤3步骤6只需要 ni log n1次比较和cne为常数)次判断,(31金文华简单快速的平面散乱点集凸包算法门北京航空航天大学 步骤7需要n∑logn次比较和线性次判断,步骤8~步骤9的 学报,1999,25(1):72-75 4]吴中海,叶澄清,潘云鹤.一个改进的简单多边形的凸包算法肌计 算机辅助设计与图形学学报,1997,9(1):9-13 时间复杂度小于0(n),总的时间耗费为n∑gn次比较和线51刘润涛任意多边形顶点凸、凹性判别的简捷算法门软件学报, 性次判断,不会超过O( n log n)。 2002,13(7):1309-1312. 6]俞梅.一种构建离散点集凸包的算法研究上海应用技术学院学 报,2003,6(2):118-120 5结東语 门7吴欣明基于均匀分布的平面点集的凸包加速算法研究[河北农 平面点集求凸壳的时间下限是0( n log n),提出的算法也 业大学学报,2007,3(2):111-13 同样达到了这个下界,并且算法思路清晰,理论缜密,明白易8刘润涛.一种简单多边形凸包的新线性算法工程图学学报,2002 懂;由于采用了二分法来判断点的区域,把点集分成各个区域 (2):120-126

...展开详情
试读 4P 论文研究-适应模糊QoS约束优化的Web服务选择技术研究.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38744270 你的留言是对我莫大的支持
    2019-09-10
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-适应模糊QoS约束优化的Web服务选择技术研究.pdf 9积分/C币 立即下载
    1/4
    论文研究-适应模糊QoS约束优化的Web服务选择技术研究.pdf第1页
    论文研究-适应模糊QoS约束优化的Web服务选择技术研究.pdf第2页

    试读已结束,剩余2页未读...

    9积分/C币 立即下载 >