欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2016102807194
申请人: 浙江理工大学
专利类型:发明专利
专利状态:已下证
专利领域: 电通信技术
更新日期:2023-08-24
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于遗传算法的服务器负载均衡方法,其特征在于包括如下步骤:

1)采用二维十进制对空间的候选解进行编码,随机产生初始种群;

2)通过Mean-Variance模型计算资源利用率和执行时间,从而得到组合适应度函数对种群中的个体进行评估检测;具体包括如下步骤:S01负载指数的衡量

通过服务器运行时的参数得到负载指数,所述的参数包括CPU占用率,内存及带宽利用率;

其中每个服务器的内存利用率定义为:

式中:Vmi为服务器i的已用内存,Pmi为服务器i的总内存;

CPU占用率的定义为:

式中:Vci为服务器i已被占用的CPU,Pci是服务器i的总CPU;

带宽利用率的定义为:

式中:Vbi为服务器i已被占用的带宽,Pbi则是服务器i的总带宽;

S02服务器i的资源利用率为:

Rui=k1Mui+k2Cui+k3Bui

式中:k1,k2,k3为常数,且k1+k2+k3=1;

S03用Mean-Variance模型计算资源利用率及执行时间假设对m个服务器进行资源利用率的配置,对应的资源利用率为随机变量Rui,总的资源利用率为:其中wi代表m个服务器中资源利用率的权值向量,i=1,2,...,m,期望up和负载均衡时间σ2p分别为:其中,ui是服务器i资源利用率的期望,而cov(Rui,Ruj)表示任意两个服务器资源利用率Rui,Ruj的协方差又写作σij,Mean-Variance模型通过求解约束优化问题来获得最优的权重向量,最小执行时间makespan为:约束条件:

在限制条件下求解Rui资源利用率组合时的最小执行时间,关于最值问题通过拉格朗日目标函数求得,构建拉格朗日式如下:其中λ1和λ2是拉格朗日乘数,通过计算L相对于wi和拉格朗日乘数的导数为0的等式来获得最优的权重向量,即分别对wi,λ1,λ2求偏导:S04由最优的权重向量可得到总的资源利用率及执行时间,组合适应度函数:适应度函数用来评价负载调度任务的质量,响应时间越少,资源利用率越高时,适应度值越高,表示负载均衡策略越好;

3)当最优字符串的适应度稳定时或迭代达到预设的次数时,算法终止并输出最优适应度字符串;否则执行步骤4);

4)按轮盘赌选择方法对适应性强的字符串进行选择,选择的字符串进行循环交叉及变异运算;得到新的种群,并返回步骤2)。

2.根据权利要求1所述的一种基于遗传算法的服务器负载均衡方法,其特征在于所述的步骤1)具体包括如下步骤:S01:采用二维十进制对空间的候选解进行编码,每个解被编码为一个由两个属性表示的十进制数组,即作,其中Ti,Pj分别表示任务i和被分配的服务器j,S02:编码后的数组采用随机函数产生N个初始串结构数据,每个串结构数据称为一个字符串,N个字符串构成了一个群体,将随机产生的N个初始串结构数据作为初始种群。

3.根据权利要求1所述的一种基于遗传算法的服务器负载均衡方法,其特征在于所述的步骤3)具体为:遗传算法以初始种群进行适应度计算,并判断算法是否达到迭代的终止条件,所述的算法迭代终止条件为某一代种群中最大适应度Fmax与最小适应度Fmin之差小于设定常数e或迭代次数达到预设的迭代次数;算法终止时输出此时的最优适应度字符串;若算法未终止,则进行选择、交叉、变异,并用所得到的新一代群体取代上一代群体继续循环执行迭代。

4.根据权利要求1所述的一种基于遗传算法的服务器负载均衡方法,其特征在于所述的步骤4)具体为:S01轮盘赌策略进行选择

种群大小为N,种群中的字符串X的适应度为Fx,则被选择遗传到下一代群体的概率为:首先确定轮盘的插槽值,根据适应度概率叠加到前一个字符串的概率上得到槽值,每个字符串都会占据一个槽值,群体全部字符串的适应性的分布由一张饼图来表示,根据字符串适应度的概率将下一个字符串的概率加到前一个字符串的概率上形成一个个不同的块,随机在0到1中产生数字,决定哪个字符串被留到下一代,适应值越大,适应度的概率越大,表示在圆盘上面积越大,被选中的概率也就越大,字符串被选中的概率与适应度函数值成正比;

S02循环交叉操作

完成选择操作后,被保留的字符串转换为一维的,随机选择部分字符串进行交叉操作,首先将经过选择操作后的种群一一配对,在相互配对的两个字符串A和B中随机选择一个,在其中一个字符串A中随机选择起始交叉点,设所对应的任务为ni,现在需要在字符串A中找到任务nj,nj是B字符串中与任务ni对应位置的任务,下一次反过来需要找到A字符串中nj在B字符串所对应相同位置的任务nk,这个过程循环进行,直到字符串A中有任务将要循环查找到起始点的任务ni时结束,同时剩余空隙位置将被对方未被选择的剩余任务交换填充,完成整个循环交叉后的操作结果为A’,B’;

S03变异操作

交叉操作后进行交换变异,字符串将重新转换成二维形式,在保证选择两个服务器中的两个不同任务进行交换的条件下,根据变异概率选择一字符串,在此字符串中随机选择一个服务器并在这个被选的服务器中选择一个需要执行的任务,在同一字符串中选择第二个服务器,同样在此服务器中选择另一个任务,将两个任务交换位置;

完成变异后,回到步骤2),字符串将产生新的适应度值。