1、基金项目:国家自然科学基金资助项目(61261015,61561043)收稿日期:2021-06-09 修回日期:2021-07-22 第 40 卷 第 4 期计 算 机 仿 真2023 年 4 月 文章编号:1006-9348(2023)04-0358-04基于层次梯度挖掘的数据智能调度算法仿真周晓晶,谷 钰(长春工业大学,吉林 长春 130012)摘要:针对当前的数据调度算法存在执行费用较高、调度耗时较长且数据资源负载不均衡的问题,提出层次梯度挖掘的数据智能调度算法。采用挖掘主题数据库和层次梯度两者构建层次业务数据库,挖掘数据局部频繁项。根据数据挖掘结果,建立执行时间、执行费用和负载均衡为
2、智能调度目标,构建数据智能调度模型。利用自适应遗传蚁群优化算法对模型求解,最终实现数据智能调度。仿真结果表明:所提算法下数据资源负载结果更均衡,同时还能够有效降低执行费用和调度时长。由此可得结论:本研究具有理想的应用效果。关键词:层次梯度挖掘;数据智能调度;自适应遗传蚁群优化算法;局部频繁项中图分类号:TP391 文献标识码:BSimulation of Data Intelligent Scheduling AlgorithmBased on Hierarchical Gradient MiningZHOU Xiao-jing,GU Yu(Changchun University of Te
3、chnology,Changchun Jilin 130012,China)ABSTRACT:In this paper,the data intelligent scheduling algorithm based on hierarchical gradient mining wasstudied in order to reduce the execution cost,shorten the scheduling time and balance the load of data resources.Firstly,the hierarchical business database
4、derived from mining topic database and hierarchical gradient was estab-lished to mine local frequent items.Secondly,according to the data mining results,the execution time,executioncost and load balancing were set as the intelligent scheduling objectives in order to build the data intelligent schedu
5、-ling model.Then,the adaptive genetic ant colony optimization algorithm was introduced to solve the model.Eventual-ly,data intelligent scheduling was achieved.The simulation results show that the algorithm not only reduces the exe-cution cost,shortens the scheduling time,but also balances the load o
6、f data resources.KEYWORDS:Hierarchical gradient mining;Data intelligent scheduling;Adaptive genetic ant colony optimization al-gorithml;Local frequent items1 引言互联网技术和数字化进程的日益发展,数据开始呈爆炸式趋势增加,传统计算模式已经无法满足当前的处理需求。同时在上述背景下,各种商业化计算模式已经出现,全部应用程序和数据的 IT 资源应用较为广泛,结合网络服务方式为用户提供便利。虽然用户能够实时访问大量的数据和资源,但是,获取适配的资
7、源和数据配置难度较大。用户如何合理有效利用这些资源成为当前研究的主要内容,其中包括数据调度1,2问题。在此背景下,相关专家给出了一些较好的研究成果,例如王晓雷等人3优先构建虚拟网络功能调度模型,将功能链的服务时间最小化。同时通过 Q-learning 动态调度算法,优化虚拟网络功能的调度顺序和虚拟机选择问题,最终实现优化调度。聂黎等人4通过染色体编码和解码方案以及适应度函数,提出一种新的博弈调度模型,通过博弈调度求解算法获取模型的最小纳什均衡,实现优化调度。但是由于上述两种方法未能在实际研究过程中应用层次梯度挖掘方法,导致资源负载不均衡,执行费用较高、调度所需时间较长。设计一种新的层次梯度挖掘
8、的数据智能调度算法。优化资源负载的均衡性,挖掘数据局部频繁项。根据数据挖掘结果,构建数据智能调度模型,可优化资源负载的均衡性,降低调度的耗时。利用自适应遗传蚁群优化算法853对模型求解,最终实现数据智能调度的择优,选择费用最低的调度方案。2 算法设计2.1 数据层次梯度挖掘步骤1)设定数据源为 D=(O,I),其中,O 和 I 分别代表数据对象和属性的有限集合,其中数据属性即一个项目,可以表示为 I=i1,i2,i3,in。数据对象可以被称为事务,主要采用通过不同的属性值5进行标识。2)在数据源 D 中,含有大量项目集 X 的数目也可以称为 X 的绝对支持数,表示为 X.sup。3)在 D 中
9、,假设 X.sup|D|minsup,其中,|D|代表数据源记录总数,项目集 X 为频繁项,这种动态变化的最小支持度阈值也称为层次梯度,将其表示为 LadderDegree(L),L 代表挖掘深度。在本次研究过程中,LadderDegree(L)代表一个深度函数。4)数据库是通过不同的层次概念建立的,各个数据库中不包含 1-频繁项目 X,全部都是由 1-频繁项目 X 后面的全部项目构成,数据库即层次业务数据库。5)在数据源 D 中,抽取全部含有挖掘主题的数据记录,进而构成全新的挖掘主题数据库。6)通过挖掘主题形成主题数据库。然后层次梯度的概念进行搜索,直至深度搜索结束,形成局部最大的频繁项目集
10、6,7。同时统计出最大频繁项目集在 D 上的统计数,最终形成关联规则。7)主站点通过 Web Services 捕获各个异构站点数据形成全新的频繁项主题数据库。通过弱化熵模型,分析全部数据,最后获取所需要的关联规则,通过关联规则得到最终的数据挖掘结果。2.2 数据智能调度模型构建作为一种全新的计算模式,数据的相关体系框架一定能够完成数据集合分布处理。全部需要完成调度的任务均是由无数个任务模型构成的,一般能够划分为两种类型,独立任务和工作任务。对于各个独立任务而言,需要结合任务粒度将各个独立任务进行分割,使其满足分布式处理需求。同时,各个独立任务之间存在密切的联系。对于工作流任务而言,节点也是通
11、过分布式进行处理,确保各个节点满足相互作用的关系。为更加详细描述不同数据之间的关联性,需要将不同的工作任务进行全面融合,其中采用的任务模型如图 1 所示。T0T9为任务序号。数据主要利用虚拟技术将不同资源对应的节点转换为虚拟集群8,并且结合数据的属性信息对数据进行统一化处理,将其全部传输至数据中心完成处理和调度。数据任务调度就是将各种不同的任务利用任务列表传输至对应的虚拟机进行调度处理。当全部数据完成分配工作后,利用虚拟机进行调度。其中,衡量调度方案优劣的标图 1 任务模型准即在数据调度过程中各种开销的取值。利用对 M 个虚拟机和 N 个调度任务所在环境的计算,即可获取 MN中的分配调度策略;
12、分别对数据的属性和虚拟机的属性等进行组合目标优化,在 MN种调度方案中获取满足调度需求的最优解。当任务完成分配,调度方案就会被数据中心代理转交至数据中心进行对应的数据智能调度处理。有关于数据智能调度模型的描述如下所示:1)对应任务的列表位置为 T=t1,t2,t3,tm,对应该任务的数据总量位置为 Numi。2)VM=m1,m2,mn为虚拟机列表,将各个虚拟机的处理能力设定为 Mips,各个虚拟机的价格为 Pricev。3)执行时间数据任务的总执行时间为totaltime=max(timeVM1,timeVM2,timeVMm)(1)式中,totaltime 代表总执行时间。单一虚拟机的执行时
13、间为timeVMi=sizeMips(2)式中,timeVMi 代表单一虚拟机9执行任务所需要的总时长;size 代表虚拟机的任务总数;Mips 代表第 i 个虚拟机的处理能力。4)执行费用totalcos t=mi=1Pricevsize(3)式中,Pricev代表虚拟机的价格。5)负载均衡值load=mi=1Numi-nm()2(4)式中,load 代表负载均衡值。当虚拟机执行任务的规模增加时,负载也会相应增加;反之,如果任务分配越均匀,则系统的负载也就越均衡。由于数据智能调度是付费模式的,所以用户在进行数据调度的过程中不需要考虑分布式处理地详细细节,只需要将提交的任务数据传输至数据中心进
14、行分布化处理即可,但是用户更加关注的是任务提交的总时长和执行费用的高低,即953totaltime 和 totalcost 两个目标函数的取值为最小,而负载均衡方差越小,证明系统越稳定;则数据智能调度模型的目标函数为min(totalcost)=mi=1Pricevsizemin(totaltime)=max(timeVM1,timeVM2,timeVMm)min(load)=mi=1Numi-nm()2|(5)2.3 模型优化1)编码设计在遗传算法中,可行任务分配策略是由单一染色体表示,以下主要使用资源-任务的间接编码方式进行编码,使其能够获取更加理想的调度结果。2)适应度函数适应度函数10
15、即目标优化函数,优先对两个目标函数进行联合优化处理,但是由于任务执行费用和时间两者之间的数量级差异比较明显。为了确保两者统一,需要对其进行标准化处理,同时加入加权求和方法展开适应度函数设计。1)执行时间函数可以表示为fT(i)=1/totaltime(i)1/totaltime(1)+1/totaltime(2)1/totaltime(r)(6)式中,totaltime(i)代表虚拟机 i 在执行调度任务所花费的时间。其中,totaltime(i)的取值越小,则说明对应的函数值越大。2)执行费用函数能够表示为fC(i)=1/totalcost(i)1/totalcost(1)+1/totalc
16、ost(2)1/totalcost(r)(7)式中,totalcost(i)代表虚拟机 i 在执行调度任务时所花费的成本。其中,totalcost(i)的取值越小,则说明对应的函数值就越大。当目标函数经过标准化处理之后,取值范围为0,1。利用式(8)给出适应度函数的具体表达形式F(i)=fT(i)+(1-)fC(i)(8)3)选择算子将轮盘赌法设定为选择算法,所谓轮盘赌法,即比例选择算法。如果种群规模为 G,则个体 i 被选中的遗传概率为pi=F(i)ri=1F(i)(9)式中,F(i)代表个体适应度;4)交叉操作交叉概率 Pc的选取对于整个算法具有十分重要的意义。当交叉概率11取值越大,则说明算法引入其它群体的速度也就越快,同时优良信息丢失的速度也会相应增加。为了有效避免上述情况的发生,需要利用自适应方式控制交叉概率对个体速度产生的影响。利用式(9)给出自适应交叉概率计算式Pc=k1(fmax-f)fmax-favg,f favgk2,f favg(10)式中,favg代表种群的平均适应度;fmax代表种群的最大适应度取值;f 代表各个交叉个体的适应度值。5)变异操作当算法进行变异操
