基于生物地理学优化算法的在线课程查询调度算法研究

王剑钊,刘佳娜

(1.黑龙江中医药大学医学信息工程学院,黑龙江 哈尔滨 150040; 2.哈尔滨职业技术学院,黑龙江 哈尔滨 150040)

随着在线课程技术和互联网技术的快速发展,各大高校纷纷开设大规模开放在线课程(MOOC,massive open online course),对互联网资源和带宽构成严重挑战,如何在互联网资源有限的环境下,为MOOC提供高效和准确的在线课程查询操作成为推动和普及MOOC的关键因素[1]。自适应查询处理器(AQP,adaptive query processing)作为MOOC的核心组件对平衡系统负载、映射查询方案具有决定性作用。传统的查询调度算法主要考虑提高查询速度[2],对于系统负载平稳问题并未考虑。而实际应用中,由于MOOC查询的大规模和应用固定性特点[3],为了降低系统资源成本,必须要求AQP考虑查询系统负载的平衡问题。为提高查询效率和平衡系统负载,提出一种基于生物地理学优化算法(BBO,biogeography-based optimization)优化平衡负载的自适应查处调度器(BAQP,balanced adaptive query processing)在线课程查询算法,通过优化查询期望代价矩阵(QEC,query expected cost)实现在线课程最优化查询和调度。

1 BBO算法

BBO算法通过模拟栖息地之间的物种迁移进行寻优,将栖息地视为所要优化问题的可能解,运用栖息地的适应度指数(HSI,habitat suitability index)评价每个解集的好坏,寻优时,首先随机产生多个栖息地NP作为所要优化问题的初始解,之后通过栖息地之间的物种迁移进行信息交换,增加栖息地的物种多样性,提高栖息地的HSI,从而获得所要优化问题的最优解。该算法主要步骤如下。

1.1 算法初始化

初始化BBO算法参数:栖息地最大变异率和最大迁入率分别为mmax和I,栖息地最大迁出率为E,每个栖息地可容纳的最大物种数量为Smax,随机产生NP个栖息地[5],即

xij=xjmin+(xjmax-xjmin)×rand,

(1)

其中:xij为栖息地Xi=[xi1,xi2,…,xiD]的第j维解变量;xjmax、xjmin分别为第j维变量的上限和下限值。

1.2 迁移

通过迁移实现栖息地之间的信息交换,可以实现解空间的广域搜索。由BBO算法基本原理可知,栖息地的HSI和物种多样性成正比例关系,栖息地的HSI越高,其可容纳的物种数量越多,所以物种数量Si和栖息地Xi之间存在一定的数学映射关系,根据HSI值的大小对Xi重新排序,原来的栖息地Xi被赋值新的i值,重新排序之后的栖息地Xi的物种数量Si[6]为

Si=Smax-i,i∈{1,2,…,NP}

(2)

栖息地Xi的迁入率λi和迁出率μi分别为

(3)

1.3 变异

通过变异操作[7]可以模拟某一栖息地发生自然灾害或者突发疾病,导致HSI发生改变,结合迁入率λi和迁出率μi可以计算出栖息地Xi的物种概率Pi,即

(4)

由BBO算法原理可知,变异率mi与物种概率Pi存在反比例关系,所以栖息地Xi的变异率[8]mi为

(5)

其中:mmax为栖息地的最大变异率;Pmax为物种概率的最大值。

2 BAQP模块结构

BAQP[9-10]的系统负载平衡主要通过5个模块自适应实现,5个模块分别为监测模块、预测模块、规划模块、执行模块和反馈模块。BQAP模块结构如图1所示。

图1 BAQP模块结构Fig.1 BAQP module structure

监控模块与元数据服务和反馈执行信息模块连接,分别接收数据资源动态信息、静态信息和反馈执行信息,同时将查询处理任务和元数据服务的资源信息提交给评估模块处理。

评估模块与监控模块相连接,其可以根据系统设定的资源状态阈值预测和判断查询系统的内存剩余、系统CPU、网络I/O的下一阶段资源状态和服务器用户量负载,判定该资源是否参与查询算法调度规划,提高查询系统的执行效率。

规划模块通过调度算法根据目标函数实现最优或者次优方法的查询规划。执行模块根据规划模块的计算结果,监督各个模块的进度执行情况,并将查询情况反馈给监控模块。

反馈模块收集查询执行的动态实时信息,并将反馈执行信息提交给监控模块。

3 在线课程查询优化算法

BAQP的核心组成部分是查询优化算法,其可以为查询系统提供动态查询和资源调度映射方案,其涉及如下定义[11-12]:

资源单元:在线课程查询时,分配给查询的最小资源数量,记作R;消耗资源单元量:一个请求消耗的资源单元数量,记作Q(i);时间单元:查询时查询占用时间的最小单元,记作t。

若可提供的资源量为R={R1,R2,…,Rn},查询消耗的资源量为Q={Q1,Q2,…,Qn},QEC(i,j)为查询任务Q(i)在资源R(j)上的资源负载耗费比值,其可表示为

QEC(i,j)=α×Nct(i,j)+β×work_load(i,j),

(6)

其中:α、β为权值,可以取静态值或者动态值,并且α+β=1;Nct(i,j)为子查询Q(i)在资源R(j)上的带宽负载耗费比值;work_load(i,j)为查询i在资源j上服务端资源负载耗费比值。Nct(i,j)公式为

Nct(i,j)=Rbandwidth(j)/Qbandwidth(i),

(7)

work_load(i,j)公式为

(8)

其中:Rbandwidth(j)、Qbandwidth(j)分别为带宽资源单元和带宽消耗资源单元;work_load(i,j,k)为查询i和资源j的CPU、内存和服务器的查询资源耗费单元量/资源单位量。

4 基于BBO-QEC的在线课程查询算法

4.1 适应度函数

在线课程查询时,为了平衡查询资源之间的负载以及降低负载的消耗,运用BBO算法对BAQP的期望代价矩阵QEC(i,j)进行优化。当QEC(i,j)越大时,说明查询该课程所耗费的资源单元量越多,同时耗费的负载代价也越大。因此BBO-QEC的适应度函数为

Min QEC(i,j)=α×Nct(i,j)+

β×work_load(i,j)。

(9)

4.2 算法流程

基于BBO-QEC的在线课程查询算法流程为:

Step1读取查询课程队列Q={Q1,Q2,…,Qn}和QEC矩阵;

Step2BBO算法初始化:mmax、I、E、Smax以及种群规模N和最大迭代次数Iter,随机产生NP个栖息地作为初始种群;

Step3根据适应度函数式(9)计算每个栖息地的HSI,并进行降序排列,计算降序排列之后栖息地Xi的迁入率λi、迁出率μi和物种数量Si;

Step4根据迁入率λi和迁出率μi进行迁移操作;

Step5结合迁入率λi和迁出率μi可以计算出栖息地Xi的物种概率Pi,之后确定栖息地Xi的变异率mi;

Step6根据变异率mi进行变异操作;

Step7判断算法终止条件,若当前迭代次数t>Iter,则输出最优查询方案;反之,返回Step3～Step7。

5 实证分析

5.1 模拟环境

为验证新算法的有效性和可靠性,建立如下在线课程查询模拟环境:

(1) 建立资源队列R={R1,R2,…,R4},Rk=[Rcpu(k),Rmemory(k),Rload(k),Rnet(k)],其中k=4,[0,300]之间随机生成大小为4×4的资源剩余单元量矩阵;

(2) 建立在线课程查询队列Q={Q1,Q2,…,Q5},Qi=[Rcpu(i),Qmemory(i),Qload(i),Qnet(i)],其中i=5,[0,30]之间随机生成大小为5×4的资源消耗单元量矩阵;

(3) 通过(1)～(2),结合公式(6)建立大小为5×4的QEC矩阵;

(4) 对比BBO-QEC、Min-Min算法和Max-Min算法,并输出计算结果。

Min-Min算法[13]是首先映射小的任务,并且映射到执行快的机器上。执行过程具体可以描述为:计算要参与映射事件的每个任务在各个机器上的期望完成时间,找到每个任务的最早完成时间及其对应的机器;从中找出最小且最早完成时间的任务,将该任务指派给获得它的机器;指派完成后,更新机器期望就绪时间并将已完成映射的任务从任务集合中删除。重复上面的过程,直到所有的任务都被映射完。

Max-Min算法[14]与Min-Min算法类似。同样要计算每一任务在任一可用机器上的最早完成时间,不同的是Max-Min算法首先调度大任务,任务到资源的映射是选择最早完成时间最大的任务映射到所对应的机器上。

5.2 评价方法

在MOOC系统中,当查询任务满足其最低资源单元量时,在线课程查询能够流畅执行。因此,评价在线课程查询调度算法的性能主要考虑查询调度方案是否可以平衡系统资源,降低系统负载消耗,而不是考虑传统的时间消耗或者执行速度。

若资源i的负载消耗系数值定义为

(9)

系统的总体负载消耗系数makeload为

makeload=max(TR),

(10)

其中:makeload为所有负载消耗系数值的最大值,其值越小则说明算法的平衡系统的能力越强,系统整体负载越小。

5.3 结果分析

BBO算法设置:最大变异率mmax=0.01、I=E=1、Smax以及种群规模N=30和最大迭代次数Iter=100,NP=100。静态权值和动态权值的对比结果分别如图2和图3所示。静态权值和动态权值查询性能误差对比分别见表1和表2。

图2(a)为静态权值环境下5任务和4资源10次随机运行实验的makeload值对比图;图2(b)为静态权值环境下100任务和20资源10次随机运行实验的makeload值对比图。由图2(a)和图2(b)以及表1可知,整体情况下,BBO-QEC的makeload值小于Min-Min和Max-Min算法,从而说明BBO算法较Min-Min和Max-Min算法具有更强的系统负载平衡能力和较低的系统负载率,可以有效降低系统消耗系数。

图2 静态权值查询性能对比Fig.2 Static weighted value query performance comparison

图3 动态权值查询性能对比Fig.3 Dynamic weighted value query performance comparison

表1 静态权值查询性能误差对比

表2 动态权值查询性能误差对比

图3(a)为动态权值环境下5任务和4资源10次随机运行实验的makeload值对比图;图3(b)为动态权值环境下100任务和20资源10次随机运行实验的makeload值对比图。由图3(a)和图3(b)及表3可知,整体情况下,BBO-QEC的makeload值小于Min-Min和Max-Min算法,从而说明BBO算法较Min-Min和Max-Min算法具有更强的系统负载平衡能力和较低的系统负载率,可以有效降低系统消耗系数。

6 结论

为解决MOOC系统查询负载均衡问题,降低系统负载率,在BAQP的基础上,提出一种基于BBO算法优化QEC的在线课程查询调度算法。选择系统的总体负载消耗系数作为评价指标,运用BBO算法优化获取在线课程的最优查询方案。通过静态权值和动态权值不同任务和资源查询调度性能对比可知,BBO算法较Min-Min和Max-Min算法具有更强的系统负载平衡能力和较低的系统负载率,可以有效降低系统消耗系数。