基于遗传退火混合算法的网格铁路信息服务组合优化研究

柴峥嵘，张俊龙，郝崇凯

（神华包神铁路集团 乌兰木伦车站，鄂尔多斯 017209）

基于遗传退火混合算法的网格铁路信息服务组合优化研究

柴峥嵘，张俊龙，郝崇凯

（神华包神铁路集团 乌兰木伦车站，鄂尔多斯 017209）

在研究网格铁路信息服务相关理论的基础上，应用加权求和法构建了基于QoS的网格铁路信息服务组合优化模型，并利用遗传退火混合算法对模型进行求解，最后以购票服务为例，运用Matlab进行仿真计算，验证了基于QoS的网格铁路信息服务组合优化模型的合理性与遗传退火混合算法的正确性。

网格；铁路信息服务；QoS；服务组合

随着互联网计算和服务化进程的发展，未来铁路信息化建设面对多样化及动态多变的需求。虽然Web Service可在一定程度上实现IT资源的互联互通，但其仍缺乏有效集群、负载均衡及多用户协同操作等能力[1]。网格的出现与发展为铁路信息化建设提供了一种跨管理域的IT资源优化配置与应用全面集成的发展方案[2～3]。

本文从服务组合的非功能性特征出发，引入QoS作为网格铁路信息服务组合综合能力的评价指标[4]，研究基于QoS的网格铁路信息服务组合优化模型及算法，为解决相关的服务组合优化问题提供理论参考。

1 基础理论

1.1 网格的本质

网格是继万维网之后在全球兴起的一种新型网络计算平台，旨在实现Internet由基本的通讯、信息交互提升到资源共享与全面协作，为用户提供一种跨管理域资源共享与应用集成的支撑环境[5]。网格的本质可概括为“广泛共享、有效聚合、充分释放”[6]，广泛共享是指通过各种方法、技术和策略将网络上的各种资源提供给网络上众多用户共享使用；有效聚合是指将网络上的海量资源通过协同与集成，联合完成应用任务；充分释放是指基于用户需求将网络上的各类资源的聚合效能传送给用户，为用户提供多样化、个性化的信息服务、计算服务和决策支持服务。

1.2 网格铁路信息服务概述

铁路信息服务就是把铁路信息系统、计算机技术等现代高新技术有机聚合，以互联网为传输媒介将铁路信息及相关软件传送给用户，满足铁路业务信息化需求的一种网络服务形式。网格铁路信息服务即铁路信息服务在网格环境下的深化与拓展，它为满足铁路用户多层次、多样化、个性化的需求提供了可能和强有力的技术支撑。

本文借鉴Web服务组合的定义将网格铁路信息服务组合概括为：当单个网格铁路信息服务无法满足用户需求时，将若干小粒度服务依照一定的逻辑方式进行有机合成[7]，实现服务重用、服务增值，最终满足用户的多样化、个性化需求的过程。文中将由网格铁路信息服务组合构造得到的服务称为“组合网格铁路信息服务”（CGS，Composite Grid Railway Information Service），而提供子功能的单一服务称为“基本网格铁路信息服务”（GS，Basic Grid Railway Information Service）。

2 基于QoS的网格铁路信息服务组合优化模型构建及算法设计

2.1 QoS属性定义及规范化

QoS（Quality of Service）可作为一个衡量服务使用满意程度的综合指标。本文拟从用户关注的角度来确定网格铁路信息服务QoS属性，包括执行时间、费用、可用性、信誉度、可靠性和安全性。其中，服务GS的执行时间qti(GS)是服务对消费者的请求进行处理的时间；费用qpr(GS)是指服务消费者向服务拥有方支付的服务使用成本；信誉度qrep(GS)是服务使用者对服务可信任程度的衡量；服务GS的可靠性qrel(GS)是指服务请求在一定条件下，特定的最大期望时间内完成相应任务的能力；服务GS的可用性qrel(GS)是衡量网格服务系统能够持续对用户进行服务的尺度；服务GS的安全性qse(GS)可通过量化为一个取值区间来反应其高低。

网格铁路信息服务的QoS属性分为效益型和成本型2类，前者是指QoS值越高，质量越高的属性，如可用性、信誉度等；后者是指QoS值越高，质量越低的属性，如费用、执行时间等。为消除量纲和单位不同等所带来的影响，在量化过程中需对QoS属性进行规范化处理，具体如下：

对于效益型质量属性：

2.2 组合网格铁路信息服务QoS模型

对于组合服务中任意2个基本服务GSi和GSj，如果它们之间存在顺序、并行、分支和自循环的4种关系，如图1所示，则称GSi和GSj之间具有控制逻辑关系CR=(GSi, GSj) 。

图1 基本网格服务间控制逻辑关系

本文将组合网格铁路信息服务视为一个大粒度、功能增值的网格铁路信息服务，其QoS模型如下：

其中，Qtime(GS)、Qpr(GS)、Qrep(GS)、Qrel(GS)、Qav(GS)、Qse(GS) 分别表示组合网格铁路信息服务的执行时间、费用、信誉度、可靠性、可用性和安全性指标。依据基本服务间的控制逻辑关系，给出组合网格铁路信息服务的各指标的计算方法，如表1所示。

2.3 优化模型的构建

本文构建的优化模型实质上是达到组合服务执行时间、费用的最小化同时，实现其信誉度、可靠性、可用性及安全性的最大化。应用加权求和法将多目标优化问题转化为单目标优化问题[8]，具体模型如下：

表1 组合网格铁路信息服务的QoS计算方法

QoS(CGS)—组合网格铁路信息服务的综合QoS值；

Qti(CGS)—组合网格铁路信息服务执行时间；

Qpr(CGS)—组合网格铁路信息服务的费用；

Qrep(CGS)—组合网格铁路信息服务信誉度；

Qrel(CGS)—组合网格铁路信息服务的可靠性；

Qav(CGS)—组合网格铁路信息服务的可用性；

Qse(CGS)—组合网格铁路信息服务的安全性 ；

Wti—用户给定或系统默认的组合网格铁路信息服务的执行时间权值；

Wpr—用户给定或系统默认的组合网格铁路信息服务的费用权值；

Wrep—用户给定或系统默认的组合网格铁路信息服务的信誉度权值；

Wrel—用户给定或系统默认的组合网格铁路信息服务的可靠性权值；

Wav—用户给定或系统默认的组合网格铁路信息服务的可用性权值；

Wse—用户给定或系统默认的组合网格铁路信息服务的安全性权值；

Ati—用户设定的组合网格铁路信息服务的执行时间阈值；

Bpr—用户设定的组合网格铁路信息服务的费用阈值；

Crep—用户设定的组合网格铁路信息服务的信誉度阈值；

Drep—用户设定的组合网格铁路信息服务的可靠性阈值；

Eav—用户设定的组合网格铁路信息服务的可用性阈值；

Fse—用户设定的组合网格铁路信息服务的安全性阈值。

2.4 基于遗传退火混合算法的求解设计

本文设计的遗传退火混合算法以遗传算法为主，并对遗传操作后产生的每个个体实施模拟退火。以下分别就混合算法实施过程中的染色体编码、种群初始化、适应度函数的选取、遗传操作和模拟退火操作等进行详细设计。

2.4.1 染色体编码

本文采用D进制数表示长度为n的位串，则染色体可表示为POP=(GS1, GS2,…,GSn)。其中，GSn∈{0,1,K, k, k+1, K, D_1}，GSn取k(0≤k≤D_1）时，表示GSn选择其相应候选服务集中的编号为k的个体GSkn，如图2所示。

图2 染色体编码示意图

2.4.2 种群初始化

初始种群的产生：利用适应度函数f(x)分别计算随机生成的2个个体的适应度大小，将适应度值较大的个体纳入初始群体，达到所要求的群体规模为止。群体大小M取值范围为20～200 ，最大进化代数Maxgene取值范围为100～500 。

2.4.3 适应度函数选取

适应度函数是淘汰或选择个体的重要依据，其一般由目标函数转换得来。由于本文是求解目标函数最大值的问题，因而可以将适应度函数定义为：

其中，f(x)为目标函数，Qk(CGS)为网格铁路信息服务组合的第k个QoS评估值，ωk表示相应的权重系数。

2.4.4 种群进化机制

种群进化包括选择、交叉及变异3个基本操作，本文分别采用轮盘赌法、多点交叉法、基本位变异法实现遗传进化操作。

2.4.5 模拟退火过程

对产生的新一代群体实施退火操作，主要包括：

（1）新解的生成，从经过遗传进化操作所产生的每个个体中随机选取2个基因当作扰动点，分别从对应的服务集中挑选一个候选服务生成新的染色体；

（2）新解的接受，对扰动前后个体的适应度f(xi)与f(xi')进行评价，计算 Δf=f(x)_ f(x')，当 Δf≤ 0，接受该新产生的个体；当Δf＞0且满足Min{1, exp(f(x)_ f(x'))/Tk)}＞random，亦接受新的个体。

3 算例验证及结果分析

3.1 算例说明

假设某人从出发地A市到目的地C市，中途需经过B市进行中转，且需通过查询服务（GS1）、订票服务（GS2）、中转服务（GS3）、付款服务（GS4）和取票服务（GS5）5个基本服务依次执行才能完成车票的购买，如图4所示。其中每个基本服务均有5个功能性相同、非功能属性不同的候选服务可供备选，如查询服务可通过手机、笔记本、ipad等终端实时查询铁路、航空、轮船等客票相关信息；中转服务有火车、大巴、出租车、飞机和轮船等方式。

图4 购票服务示意图

3.2 算例求解过程

3.2.1 数据规范化

根据公式（1）和公式（2），对各候选服务QoS值进行规范化处理，可得结果如表2。

表2 经规范化处理的候选服务QoS参数值

3.2.2 目标函数构建

基于遗传退火混合算法求解购票服务算例，具体步骤如下：

（1）购票服务的QoS评价

本文的购票服务是一个只含有顺序逻辑关系的服务组合，其各维QoS的计算公式如下：

购票服务的执行时间：

（2）购票服务权重的设定

鉴于加权求和法中每个目标的权重系数可采用专家打分法或由经验进行确定，假设购票服务中旅客更注重购票服务的执行时间与费用这2个维度的服务质量，具体如下：

（3）目标函数的建立

采用加权求和法将购票服务这一多目标优化问题转化为单目标优化问题，求得其目标函数：

3.2.3 混合算法的实现

基于遗传退火混合算法运用Matlab软件对算例进行求解，详细步骤如下：

（1）初始化准备

确定初始化下各控制参数：种群规模M=40，个体长度Lind=5，设置种群最大进化代数Maxgene=150，交叉率 Pc=0.88，变异率Pm=0.02，代沟G=0.9，模拟退火初始温度T0=100，退火系数α=0.95。

（2）生成初始种群

预先设定初始种群大小为40，并调用遗传算法工具箱中crtbp函数来创建初始种群，具体调用格式如下：

采用遗传工具箱中的crtbp函数获得初始群体如表4所示（截取前10个）。

表4 初始群体值

（3）个体适应度评价

求解购票服务算例即找出QoS值最大时的服务组合，因而可将购票服务的目标函数作遗传退火混合算法的适应度函数，即：

（4）遗传进化操作

首先在生成的初始群体中随机选择2个个体进行交叉、变异进化操作，在遗传进化操作后产生的新个体i，j分别为：

在2个体中产生一个随机扰动，分别找出2个体的一个临域解i'，j'：

采用的轮盘赌选择、多点交叉、基本位变异操作进化的具体调用方法如下：

（5）模拟退火操作

分别求得2新个体的适应度函数值为f(i')、f(j')，若二者均满足min{1,exp((f(i')_f(i))/Tk)}＞random，则可以接受此新个体，否则拒绝接受，其中random是[0,1]之间的随机数。

3.3 仿真结果及分析

随着遗传进化和退火操作的进行，从种群中搜索最优个体，即求出最优解。图5表示经过150次迭代后购票服务目标函数最大值与均值的变化，图中横坐标表示进化代数，纵坐标代表购票服务综合QoS值。

图5 经过150次迭代后种群目标函数最大值与均值的变化

采用遗传退火混合算法将目标函数迭代150代后输出最优解，即购票服务的最佳组合及相应候选服务如表5所示。

表5 购票服务的最佳服务组合及相应候选

通过计算，得出购票服务综合QoS值为2.223 2，对应的最佳服务组合方案为，即5个基本服务选取的候选服务分别为对本算例分析，可知本文建立的基于QoS的网格铁路信息服务组合优化模型是合理的，同时证明针对模型所设计的遗传退火混合算法的正确性，即能够求出模型的近似最优解。

4 结束语

本文采用加权求和法构建了基于QoS的网格铁路信息服务组合优化模型，针对该模型设计了遗传退火混合算法，并以购票服务为例验证了全局优化模型的合理性及混合算法的正确性。不足之处是未将混合算法与其他智能算法在搜索性能方面进行对比，今后可运用蚁群算法、粒子群算法和禁忌搜索算法等其他智能算法求解该优化模型，进一步验证遗传退火混合算法的整体优越性。

[1] Heather Kreger. Web Services Conceptual Architecture（WSCA 1.0）,IBM Software Group, May2001[EB/OL].http://www.4.ibm.com/software/solutions/web services/pdf/wsca.p

[2] 刘 峰.基于网格服务的地理空间信息共享平台关键技术研究[D].青岛：山东科技大学，2007.

[3] 蔡雯瑛.网格计算在铁路信息系统中的应用[J].铁路计算机应用，2004（1）：7-10.

[4] 候 青.支持QoS约束的Web服务发现与服务组合研究[D]. 重庆：重庆师范大学，2011.

[5] 韩燕波，王桂玲，刘 晨，等.互联网计算的原理与实践[M].北京：科学出版社，2010.

[6] 李 科.网格环境下地理信息服务关键技术研究[D].郑州：解放军信息工程大学，2008.

[7] 付晓东.Web服务组合服务质量保障关键问题研究[D].昆明：昆明理工大学，2008.

[8] 张 敏.约束优化和多目标优化的进化算法研究[D].合肥：中国科学技术大学，2008.

责任编辑 方 圆

Research on optimization for grid railway information service based on Genetic Annealing Hybrid Algorithm

CHAI Zhengrong, ZHANG Junlong, HAO Chongkai
( Ulan Mulun Station, Shenhua Baoshen Railway Group Company, Erdos 017209, China )

Based on the study in related theories about grid railway information services, the composition optimization model of grid railway information service based on QoS was built by using weighted summation method, and Genetic Annealing Hybrid Algorithm was utilized to solve the model. Finally, it was taken the ticket service for example and used Matlab to emulate, testi fi ed the reasonability of the model based on QoS and the correctness and ef fi ciency of the Algorithm.

grid; railway information service; QoS; service composition

U29∶TP39

A

1005-8451（2014）05-0015-06

2013-11-14

柴峥嵘，助理工程师；张俊龙，助理工程师。