与E³-MOGA算法^[8]相同, SMOGA中的每个个体代表三类用户分类的服务组合, 并且将每个个体解码为一个基因组, 图2给出了一个个体基因的实例。个体中每个基因解码为具体服务实例的数量, 该个体对应的抽象流程包含了4个抽象服务, 每个抽象服务有3个具体服务用于实现(每个服务组合有4× 3=12个基因), 并且它代表白金卡、金卡和银卡三类用户的服务组合(12× 3=36个基因)。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 个体的表示Fig.2 An example of particle’ s position

由个体的基因组表示可知, 每个基因代表其所关联的具体服务实例的数量, 对于与抽象服务关联的一组具体服务实例的数量, SMOGA中将其定义为与抽象服务关联的候选服务, 具体定义如下:

定义1 候选服务:在每个个体的基因组中, 将与某个抽象服务的所有具体服务关联, 并且不全为0的基因片段, 定义为与该抽象服务关联的候选服务。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 交叉操作的过程Fig.3 Process of crossover operation

SMOGA中的交叉操作将采用以候选服务组合为单位的两点交叉操作。如图3所示, 虚线将个体分解为候选服务的组合, 并且这些分界点将成为个体交叉点。图中个体 的具体交叉过程分为3个步骤, 首先, 利用随机的方式为每个待交叉的个体选定两个交叉点, 即交叉点1和交叉点2, 则每个个体被分为3个部分, 即部分1, 部分2和部分3; 其次, 再次利用随机的方式确定交叉的部分, 图中选定的为部分2; 最后, 对于交叉个体对应的交叉部分进行交叉操作, 产生新的个体

SMOGA中所采用的变异操作将首先选定个体中的一个候选服务, 然后改变候选服务中的某个基因, 被改变基因的个体为变异操作产生的个体。每个候选服务以 被确定为变异对象。然后以候选服务确定的相同方式确定该候选服务中的一个基因, 并且将其随机改变。

为了保证变异的有效性, 将其与本文设计的一种局部搜索过程IPLS相结合, 用于变异操作后对产生的子代个体进行性能的提升, IPLS过程定义如下。

Algorithm IPLS

input:chromosome s;

output:chromosome s';

begin

s'=s;

for each a'∈ N(s) do //Neighborhood exploration

if(a' s'∧ f(a')< f(s'))then s'= a';

end if

end for

end

IPLS由两个比较重要的部分组成, 邻域探索以及接受条件。当一个个体在其邻域内探索到一个新个体解, 仅当新个体不被原个体支配且满足效用值小于原个体时才被接受。而对于个体 其定义如下。

定义2 邻域:对于给定的邻域规模 的邻域。

在该策略中, 同时考虑了一个个体支配其他个体和被其他个体支配的情况。给定当前的个体集 可计算如下:

显然, 一个个体的 指标。

式中:

基于以上定义, 个体 的效用值可计算如下:

SMOGA中使用轮盘赌的方法来实现对群体中的个体的优胜劣汰操作, 从父代中以效用值的比例作为概率, 选取一些个体遗传到下一代群体。由个体 的效用函数, 可以得到它在轮盘赌选择方法中的概率为:

将集合中的所有个体按照效用值的大小排列, 在每次选择中, 产生一个[0, 1]的随机数, 作为选择指针来确定被选个体。

基于以上的表示, 给出SMOGA的描述如下:

算法SMOGA

g← 0

P⁰← randomly generated μ individuals

repeat until g == g_max {

Q^k← ⌀

div=CalculateDiversity(P^g)

for each particle i in P^g{

//parent selection via Roulette Wheel

P_a(g)← RWSelection(P^g)

P_b(g)← RWSelection(P^g)

//Reproduction via two-point crossover

q₁(g), q₂(g)← Crossover(P_a(g), P_b(g))

//Mutation on reproduced offspring

q₁(g)← Mutation (q₁(g))

q₁ (g)← IPLS (q₁(g))

add q₁ (g) to Q^g if Q^g does not contain q₁ (g)

q₂(g)← Mutation (q₂(g))

q₂ (g)← IPLS (q₂(g))

add q₂ (g) to Q^g if Q^g does not contain q₂ (g)

}

AssignUtilityValues(P^g∪ Q^g)

Gbest^k+1← Top μ of P^g∪ Q^g

g← g+1

}

实验采用了文献[8]中两种不同的抽象流程结构, 对应3个不同的Case, 对于每个Case, 算法SMOGA运行得到的解集与算法NSGA-II、E³-MOGA运行得到的解集进行比较。由于所有对比算法具有相同的复杂度, 所以将适应度函数评价次数作为终止条件, 将它设置为Level* Length* 10⁴, 其中Level为每个个体所表示的服务组合的等级个数, Length为个体包含的抽象服务的个数。

第一个流程包括4个抽象服务, 与case1相对应, 结构如图1所示。每个抽象服务与3个QoS级别不同具体服务相关联, 所有具体服务的QoS属性变化服从某种分布概率。case1的SLA等级约束包括白金卡和金卡用户对throughput和latency的最低约束, 银卡用户对throughput和cost的最低约束, 以及对三类用户总cost的最低约束。根据case1的抽象流程结构, 将case1的目标和属性聚合公式结合得到case1的各目标函数, 将三类用户的约束条件和属性聚合公式结合得到case 1的约束条件。依据终止条件设置, 将case1的适应度函数评价次数设置为1.2× 10⁵, 所有结果都为10次独立运行的均值。

第二个流程为多个抽象服务的顺序流程结构, 与case2和case3相对应, case2流程结构为10顺序连接的抽象服务, case3流程结构为15个顺序连接的抽象服务。每个抽象服务与3个具体服务相关联, 所有具体服务属性值都是确定的, 即QoS属性没有按概率分布, 所有抽象服务都与这些具体服务相关联。依据终止条件设置, 将case2和case3的适应度函数评价次数设置为3.0× 10⁶和4.5× 10⁶, 所有结果都为10次独立运行的均值。

假设每个具体服务最多部署10个服务实例, 则一个用户分类的服务组合的搜索空间复杂度为 表示连续抽象服务的个数。那么, 粒子所代表的3个用户分类为一个解的搜索空间复杂度为 这一数字代表了所有可能的服务实例的组合。由此, case1的流程结构所对应的搜索空间复杂度为 case2的流程结构所对应的搜索空间复杂度为 , case3的流程结构所对应的搜索空间复杂度为 分析表明, 即使抽象流程所涉及的抽象服务的数目不大, 在关联的具体服务数量不多的情况下, SSC问题的搜索空间仍然很巨大。

SMOGA中的主要参数包括群体规模pop_size和变异概率a。如果不考虑算法的复杂度, pop_size对算法效果的影响是显著的, 当群体规模过大时, 不易收敛, 反而影响求解的效果, 实验将群体规模的取值范围设定为从50到200以25为增量的7个值。变异概率 是比群体规模更加敏感的参数, 将它的取值范围设置为从0.10到0.40以0.05为增量的7个值。

为研究参数的影响, 分别在3.1小节中设置的2个不同的数据集和3个不同的case上对这些参数进行实验测试。由于不同case所得解集的hyper-volume值的数量级别不同, 将它按如下的公式进行转换:

式中: 为算法SMOGA在case i上第j个参数的取值为第 值时所得解集的hyper-volume值, 所对应的7个解集的hyper-volume值中最大的hyper-volume值由max( )表示, G_ij(max( ))表示这个最大值的数量级别, 如0.005的数量级别为0.001。在这个过程中, 算法SMOGA对于每种参数设置, 在每个case上运行10次, 得到的hyper-volume值经过式(6)进行转换, 结果如图4所示。先讨论pop_size的影响, 设定α 的初始值为0.35, 从图4中pop_size的参数调整图可以看出, pop_size=100效果较好。设定pop_size为100, 调整α 的取值, 得到图4中α 的参数调整图, 可以看出α =0.35时效果较好, 所以认为pop_size=100和α =0.35为一种相对较好的设置。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 参数对算法性能的影响Fig.4 Effects of different parameter on performance

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 参数对算法性能的影响Fig.4 Effects of different parameter on performance

针对多等级服务部署问题, 将算法SMOGA与近期提出的E³-MOGA(多目标遗传算法)和NSGA-II(快速非支配排序遗传算法)在3个不同流程结构的case上进行实验, 这些算法的参数和终止条件为3.2小节所设定。实验将所有算法实验所得解集的hyper-volume值进行比较。表1给出了每个算法在所有case上运行得到20个结果的最大hyper-volume值, 最小hyper-volume值, 均值和变异系数(CV%)。变异系数是一种相对变异的度量, 等于标准差除以均值; 变异系数小则说明所有运行结果的hyper-volume分布较为均匀, 偏差较小, 变异系数较大则说明hyper-volume值之间差别较大。从表1可知, 用算法SMOGA求得解集的最大hyper-volume值、最小hyper-volume值和均值都比算法E³-MOGA、算法NSGA-II的相应值大, 而且在所有算法中变异系数(CV%)最小, 因此认为算法SMOGA比算法E³-MOGA和算法NSGA-II更稳定有效。而且它的有效性在图5中得到进一步的证明, 图5中明确显示了每个case上所有算法的hyper-volume值分布图。它给出了每种算法的hyper-volume值分布, 包括最小观察值、低四分位值、中位值、高四分位值和最大观察值。与E³-MOGA和NSGA-II相比, 算法SMOGA为个体设置的效用值函数更能有效地找出个体之间的细微差别, 区分个体的质量, 过滤质量低劣的个体, 保留效用值高的个体进入下一次迭代。而且算法SMOGA中的变异策略, 每次对个体进行微小的改变, 防止因为变化太大将好的解遗漏, 同时结合局部搜索中的领域概念, 使得变异效果不理想的个体有机会经过多次变异得到效果优异的解。

表1

Table 1

表1(Table 1)

表1 不同算法Hyper-volume值对比[最大/最小/均值/(变异系数)] Table 1 Hyper-volume obtained by compared algorithms[max/min/ave(cv%)] Algorithm case 1 case 2 case 3 NSGA-II 0.000216/0.000099/0.0000789(0.7003) 0.3731/0.0031/0.1079(0.8099) 0.00118/0.000021/0.00049(0.8021) E3-MOGA 0.000437/0.0000122/0.000185(0.7227) 1.8372/0.0835/0.5515/(0.789) 0.01763/0.00068/0.0046(0.9939) SMOGA 0.001135/0.0002975/0.0004445(0.6693) 4.5191/1.4376/1.9175(0.749) 0.04468/0.01219/0.01672(0.7291)

表1 不同算法Hyper-volume值对比[最大/最小/均值/(变异系数)] Table 1 Hyper-volume obtained by compared algorithms[max/min/ave(cv%)]

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 Hyper-volume值分布图Fig.5 Statistical results of hyper-volume of compared algorithms on different cases

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 Hyper-volume值分布图Fig.5 Statistical results of hyper-volume of compared algorithms on different cases

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 Hyper-volume值分布图Fig.5 Statistical results of hyper-volume of compared algorithms on different cases