一种面向云计算任务调度的改进人工蜂群算法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN113656153A(43)申请公布日2021.11.16(21)申请号202110730173.9(22)申请日2021.06.29(71)申请人桂林理工大学地址541004广西壮族自治区桂林市七星区建干路12号(72)发明人谢晓兰张启明翟青海刘亚荣梁容华(51)Int.Cl.G06F9/48(2006.01)G06F9/50(2006.01)G06N3/00(2006.01)权利要求书2页说明书4页附图1页(54)发明名称一种面向云计算任务调度的改进人工蜂群算法(57)摘要本发明提出了一种面向云计算任务调度的改进人工蜂群算法。包括4个步骤：首先基于对数的适应度评价方式体现个体差异，然后基于改善轮盘赌的选择策略，提升收敛速度，接着改进跟随蜂的搜索方式，引入个体当前最优值，最后改进跟随蜂食物源的更新策略，借鉴模拟退火的思想保留较差解，防止早熟。与标准人工蜂群算法相比，本发明所述算法在云计算任务调度中具有很强的局部搜索能力，在算法的前期不断探索全局最优解，且在后期也具有良好的局部探索能力。同时，鉴模拟退火算法的思想，增加种群多样性，使得算法能够尽可能避免陷入局部最优解，从而最终收敛的结果更好。CN113656153ACN113656153A权利要求书1/2页1.一种面向云计算任务调度的改进粒子群算法，其特征在于，包括以下步骤：步骤S1.基于对数的适应度评价方式：本发明引入基于对数的适应度评价方式，增大差异，对解相似但不同的个体加以区分，使优秀个体有更大机率被跟随开采；针对在传统适应度值计算中，当种群中解的精度差异较大的情况下，函数值却可能相近，导致适应度值相同，被选择的概率也就相同，体现不出个体之间的差异的问题，也就需要一种在解精度差异很小时，对应的函数值相差很大的函数，由此适应度评价方式为：式(1)中fi为对应解的函数值；步骤S2.基于改善轮盘赌的选择策略：本发明对算法中的轮盘赌方法进行改进；改进的轮盘赌法是在轮盘赌选择法的基础上用每个蜜源的适应度函数的值减去最小的适应度值，这样适应度值最小也就是蜜量最低的蜜源被选择的概率为0，从而提升了算法的收敛性，解决由于标准人工蜂群算法中最差解的干预，导致算法的收敛速度降低的问题；根据适应度函数求出当前所有蜜源的适应度向量fitt，t代表当前蜜源代数，对fitt中的数据采用如下方法处理：式(2)中，代表第t代蜜源中适应度的最小值，表达式如下：将处理后的适应度值按适应度比例法处理；步骤S3.改进跟随蜂的搜索方式：本发明将个体当前最优值引入到跟随蜂的搜索方式中去，使得算法的收敛速度提高，提高算法的局部搜索能力；在改进人工蜂群算法中，个体当前最优值记为xbest，xbest表示每只蜜蜂记住自己到目前为止发现的最好位置；这样跟随蜂的搜索方式变为：式(4)中第一部分为当前蜜源位置，第二部分表示已搜该蜜源的蜜蜂的历史最好位置对前当前位置的影响，通过向历史最好位置靠拢进而提高算法的局部搜索能力，其中是[‑1,1]之间的随机数，vij是替代xij的新蜜源位置；与标准人工蜂群算法不同的是，将个体当前最优解引入跟随蜂的位置更新过程，但是不改变雇佣蜂的搜索方式，这样做保留了算法局部搜索的随机性，不至于陷入局部最优，又通过引导跟随蜂向最优解靠拢，加快算法的收敛速度，提高搜索的精度和速度；步骤S4.改进跟随蜂食物源的更新策略：本发明对跟随蜂采用式(4)的方式进行领域搜索，将个体当前最优解的影响发挥至最大，这样得到的解从质量上看都会很高，因此在得到新解的适应度值比当前位置的适应度值低的情况下不能全盘否定，所以在跟随蜂寻优的过程中，为了防止陷入局部最优，本发明通过借鉴模拟退火算法中的“以一定的概率接受较差解”的思想，给出了一种新的食物源更新策略，定义如下概率因子：2CN113656153A权利要求书2/2页式(5)中fitxi是当前蜜源的适应度值，fitvi是新蜜源的适应度值，ε的取值取决于想要以怎样的概率接受较差解，ε越大，接受较差解的概率就越小，本发明中ε取值为5；在模拟退火算法中，接受较差解的概率会随着时间的推移，温度的降低而不断减少；在本发明中，将接受较差解的概率与解的质量相关联，如果较差解与原解的适应度差值越小，‑ε则接受该较差解的概率越大，反之概率越小，概率因子Pi的取值范围是(0，e)；跟随蜂的搜索策略如下：步骤S41跟随蜂以改进轮盘赌的方式选择食物源xi；步骤S42按照式(4)进行局部搜索，得到新的食物源vi；步骤S43分别计算xi、vi的适应度值fitxi、fitvi，如果fitvi>fitxi则更新食物源，否则执行步骤4；步骤S44根据式(5)计算跟随蜂选择较差解vi的概率Pi，如果Pi>rand，更新食物源，rand为