本发明涉及组合优化算法领域，具体涉及了一种基于改进最大最小蚁群算法mmas(max-minantcolonyalgorithm)的负载均衡调度方法
背景技术：
：随着计算机技术的蓬勃发展，传统的计算模式在现阶段已不能完全满足用户的需求，云计算应运而生，它通过计算机网络向用户提供满足用户需求的并且灵活、可伸缩的计算和存储资源。云计算有着非常广泛的用户群体，几乎时刻都在处理海量的任务。因此，考虑如何合理地分配和利用云环境中的资源、有效地调度用户提交的海量任务且保证整个系统的负载均衡但也面临着一些问题，它会导致任务的完成时间增加、资源的利用率及任务的完成效率达不到期望的要求等等。由于云计算任务调度问题可以抽象成将多个任务随机分配到若干个虚拟机上，属于典型的组合优化问题。神经网络、遗传算法、模拟退火、粒子群算法、蚁群算法等许多用于解决复杂优化问题的新方法，本发明对蚁群算法的高效性、精确性的优点，解决了云计算中虚拟机负载不均衡及任务集完成时间较长的问题，提出了一种基于改进mmas的负载均衡调度算法。蚁群算法是由意大利学者20世纪90年代模拟真实蚂蚁的觅食行为过程而提出的一种启发式仿生优化算法。其灵感来源于蚂蚁寻找食物过程中的路径发现，它主要是在图中寻找优化路径几率的算法。目前，它已被广泛用于解决大多数np类问题的优化求解，如旅行商问题、图像着色、车辆调度、网络路由、多重背包等静态组合优化和动态组合优化问题。它的优点是：(1)采用一种正反馈机制，通过信息素的不断更新，达到最终收敛于最优路径的目的；(2)是一种分布式的优化方法，易于并行实现；(3)是一种全局优化的方法，不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；(4)适合于求解离散优化问题；(5)鲁棒性强。但由于在算法的初始阶段信息素匮乏，所以求解速度较慢。近十几年来，国内外众多学者为了提升蚁群算法的性能，在其改进策略上做了大量的研究。主要是针对基本蚁群算法一般需要较长的搜索时间和易陷入局部最优解等不足，对其参数和模型提出了一些改进方案:dorigo等人通过在当前最优解更新信息素时释放额外的信息素，增强系统的正反馈作用，提出了精英蚂蚁系统eas(elitist-antsystem)；基本蚁群算法和最大最小蚂蚁系统在信息素更新和路径选择问题上均采取固定的模式，这是导致算法出现“早熟”停滞现象的主要原因，针对这一不足，gambardella等人提出了一种自适应蚁群算法aaca(adaptiveantcolonyalgorithm)，通过自适应地调节信息素挥发系数，抑制搜索停滞现象；最大-最小蚁群算法(mmas)是由德国学者t.stuetzle等人提出的，mmas是到目前为止解决tsp、qap等问题最好的蚁群优化算法之一。这种改进型蚁群算法在每次迭代中只允许表现最好的蚂蚁更新路径上的信息素，目的主要在于防止过早的算法停滞现象。蚁群算法具有如下几个优点：正反馈性、较强的鲁棒性、分布性和可扩展性。同时蚁群算法自身也具有不足之处，即计算执行时间较长、容易陷入局部最优解造成停滞。技术实现要素：为了克服现有技术的不足，本发明给出了一种基于改进mmas的负载均衡调度方法，通过双向收敛策略的信息素更新的方式，很好的解决了算法执行时间长的缺点；然后通过限定信息素浓度允许值的上下限，克服了算法过早停滞，增大了解的范围，而且在寻优方面有所改善。为了解决上述技术问题，本发明采用如下的技术方案：一种基于改进mmas的负载均衡调度方法，包括以下步骤：步骤1，参数及环境初始化，过程如下：1.1设置时间t＝0，迭代次数nc＝0，最大迭代次数ncmax，设置蚁群的群体规模，蚂蚁的数量m，并将m只蚂蚁放在每一个结点坐标上；初始化信息素大小；1.2将所有路径的信息素限制在最大值τmax和最小值τmin之间，高于或低于这一区域都会被自动调整为τmax或τmin，保证信息素最小的路径也在选择范围内，设置最大最小的信息素如(1)、(2)式：其中l(t)表示第t次迭代最优路径长度，ρ为信息素挥发系数，将各条路径上的信息素控制在[τmin，τmax]之内，对于超出这个范围的值，大于τmax的就取τmax，若小于τmin则取τmin，这样的好处就是可以有效地避免某条路径上的信息素量远大于其他路径而造成的所有蚂蚁都集中到同一条路径上，从而使算法不再扩散、陷入局部最优；步骤2，随机分布在各结点的蚂蚁开始活动，各蚂蚁依据式(3)的状态转移概率进行路径选择，过程如下：2.1结点上的每只蚂蚁根据由式如下定义的转移概率选择下一个结点，转移概率定义为：其中，τij表示边(i,j)的信息素强度，ηij＝1/cij表示关系i转移到关系j的期望程度，cij为关系i和j的连接代价。α为轨迹的相对重要性，β为期望的相对重要性；2.2m只蚂蚁同时从不同的结点出发，根据式(3)选择下一结点，已去过的放入禁忌表(tabuk)中，用禁忌表存储蚂蚁已经走过的关系,allowedk是蚂蚁k还未选择的结点集合，保证所有解的逻辑可行；步骤3，当蚂蚁移动到新的结点上后，根据式(4)更新其经过路径的信息素，并修改禁忌表，过程如下：首先，一次循环只对本次循环最优解或到目前为止找出最优解的一只蚂蚁进行信息素更新，使得长时间多数路径上信息素量相同，影响最优解的搜索速度；其次，假设蚂蚁创建第一条路径的引导信息主要是城市间的距离信息，这样蚂蚁在所经过的路径上留下的信息就不一定能反映出最优路径的方向，不能保证蚂蚁创建的第一条路径能引导蚁群走向全局最优解；因此，在第一次循环蚂蚁创建的本次循环最优解可能离全局最优解较远，但这条路径的信息素会因正反馈而得到增强，随着算法的重复执行，信息素会积累在这条不是最优的路径上，从而影响全局最优解的搜索速度；再次，一次循环中产生的较差解，对产生最优解不会有很大的帮助，如果增加此较差解路径的信息素，只会影响对最优解的搜索速度，所以应减小这些路径上的信息素，使较多的蚂蚁更快集中到较好路径的搜索上以加快全局最优解搜索速度；3.1使用表示更新后的信息素浓度，表示更新前的信息素浓度，在蚂蚁的每次搜索过程中，都会对信息素按如下公式进行更新：其中，ω为引入的奖惩系数，lcur为当前路径的总长度，llast为上一次的路径的总长度；3.2当出现最优路径时，对当前信息素浓度增加作为奖励，当出现相对较差路径时，则对当前信息素浓度减去作为惩罚，当出现最差路径时，则对当前信息素浓度减去作为严惩，增加双向收敛策略的目的是增加较优路径上的信息素浓度、减小较差路径上的信息素，使较多的蚂蚁更快集中到较好路径的搜索上以加快全局最优解搜索速度，并且扩大了解的范围；步骤4，重复执行步骤2，3，4直到整个蚁群中的每个蚂蚁都找到一个可行路径为止，记录路径总长度，对比所有可行路径，记录最优和最差路径，通过记录的结果对当前最优路径进行“奖励”，对最差路径进行“严惩”，对比上一个路径长的路径进行“轻罚”，更新所有路径的信息素浓度，重新随机选择蚂蚁的位置，对所有路径上的信息素进行全局更新；步骤5，如果迭代次数达到预设迭代次数，则终止搜索，得出最优解，如果未达到迭代次数，并使t＝t 1，转到步骤2。本发明的技术构思为：为了减少在搜索早期算法出现停滞的可能。首先，对算法中信息素浓度引入最大值和最小值限制，克服了算法过早停滞，易陷入局部最优解的缺点；其次，针对蚁群算法在搜索最优路径时会出现收敛速度慢，搜索效率低的问题，在蚁群算法的信息素更新公式中引入赏罚系数，即双向收敛策略。本发明的有益效果表现在：(1)与传统的蚁群算法相比，本发明在限值信息素浓度的大小，使其确定在[τmin,τmax]内，对于信息素浓度超过最大值就取最大值，小于最小值就取最小值，使信息素的大小不至于过大或者过小，避免了算法过早的搜索停滞，很好的增加了蚂蚁寻优的效率，避免群体都陷入局部最优路线上，扩大了解的范围。(2)最大最小蚁群算法的初始信息素的分布均匀，均为τ，使得蚁群算法在算法的早期具有盲目性，蚁群算法在搜索最优路径时会出现收敛速度慢，搜索效率低的问题，不能很快的收敛。本发明对这个问题，在蚁群算法的信息素更新公式中引入双向收敛策略。附图说明图1是基于改进mmas的负载均衡调度方法的流程图；图2是基于改进mmas的负载均衡调度方法的调度架构；图3是虚拟机调度模型；图4是本发明的任务执行流程图；图5是当前最短路径示意图；图6是三种方法对比的结果。图7是三种方法执行时间对比的结果。具体实施方式为了阐明本发明的目的、技术方案和优点，以下结合具体实施例及附图，对本发明做进一步详细说明。参照图1～图7，一种基于改进mmas的负载均衡调度方法，包括以下步骤：步骤1，参数及环境初始化，设置时间t＝0，迭代次数nc＝0，最大迭代次数ncmax，初始化云平台虚拟机的信息素浓度，根据公式(1)、(2)，将所有路径的信息素的值限制在最大值τmax和最小值τmin之间，高于或低于这一区域都会被自动调整为τmax或τmin，并初始化各蚁群的位置；步骤2，如果满足调度的条件(假如有申请且平均负载低于70％)所有蚂蚁根据公式(5)和(6)随机选择任务，每只蚂蚁根据要求选择虚拟机，如图2所示，过程如下：2.1设任务i的运行需要满足3个资源需求q，定义一个负载均衡因子lbij来衡量i任务分配到虚拟机j上后该虚拟机的负载情况，假定任务i分配到虚拟机j上，根据下式计算虚拟机j的负载均衡因子：当q＝1表示cpu资源；当q＝2表示内存资源；当q＝3表示带宽资源。表示任务i分配到虚拟机j后，表示cpu资源在该虚拟机的3种资源中所占的权重；表示内存资源在该虚拟机的3种资源中所占的权重；表示带宽资源在该虚拟机的3种资源中所占的权重；表示任务i分配到虚拟机j上后虚拟机j上可用的q资源的利用率。假设虚拟机负载均衡因子lbij较小，lbij＝0.2，则根据当前的负载情况记录在allowedk中，随着下一蚂蚁的转移，根据概率大小，进行下一虚拟机的选择，较小负载的虚拟机选择的概率就较大；2.2虚拟机的工作负载的详细状态由一个计算资源利用向量来表示，利用cpu利用率、内存利用率和带宽利用率这3个向量来表示资源的利用向量，其中为状态向量。云计算任调度问题描述为将n个任务随机分配到m个虚拟机上，在其分配任务的过程中考虑虚拟机的负载均衡因素，根据公式(5)，如果负载均衡值小于给定的值的话，进行下一步；2.3初始时刻，各个虚拟机上的信息素量相等，设τij(0)＝τmax，所以，蚂蚁k选择虚拟机j去完成任务i的概率为：allowedk表示蚂蚁还未选择的虚拟机的集合；τij是虚拟机j在t时刻信息素浓度值，lbij表示vm的负载均衡因子，用于维持虚拟机的负载均衡，虚拟机的负载均衡因子越小，则选择该虚拟机执行下一个任务的概率就越高，综合能力比较强，期望值也就高，α,β这两个系数表示的是控制信息素和虚拟机的负载程度以及虚拟机的效率值所占的权重指数；步骤3，根据图4(任务执行流程图)，蚂蚁依据式(6)的状态转移概率，节点上的每只蚂蚁根据转移概率选择下一个虚拟机，判断虚拟机的负载状态，当满足调度要求且目标结点不过载，则执行任务或者迁移下一虚拟机，根据蚁群中蚂蚁找到的结点的负载更新信息素，当一只蚂蚁完成了他的任务分配后，依据公式(4)进行信息素的更新策略，并计算完成时间，过程如下：3.1通过上式计算可得负载均衡因子lbij和资源的利用率可以定义当前vmj节点的负载状态loadstatuej，分别是：超载状态(overloaded)、满载状态(fullloaded)、正常负载状态(normalloaded)，其定义如下：如果，或表示任务i请求q资源的数量大于或等于虚拟机j上可用q资源的数量，因此虚拟机j上可用的资源不能满足任务i的资源请求，如果强制将任务i分配到虚拟机j上，虚拟机就会处于超载或满载状态，从而导致该虚拟机负载不均衡或虚拟机的利用率降低，因此，该任务不会分配到该虚拟机上，会转移到下一个可以接收该任务的虚拟机上，反之，如果表示该虚拟机处于可负载状态，且资源利用率不高，可以给该虚拟机分配任务；3.2当满足正常负载状态，得出更新后的信息素浓度，应用在虚拟机调度中则可以抽象参数如下表示，赏罚系数定义如下：tasklengthi表示当前任务i和已分配到j虚拟机上的所有任务的长度之和，单位为mi(millioninstructions)即每秒处理百万条的指令数，totaltasklengthj表示所有任务i和已分配到j虚拟机上的所有任务的长度之和，根据此时的ω可以计算出新的信息素浓度。3.3设τij(t)是虚拟机vmj在t时刻的信息素浓度，信息素浓度的更新公式如下所示：τij(t 1)＝(1-ω*ρ)*τij(t) δτij(t,t 1)(9)其中ρ∈(0,1)是信息素的衰减系数，如果ρ值越大就表明路径的信息素浓度受以前的影响程度就越小，δτij(t,t 1)表示在本次循环中在vmj上的信息素增量。当一只蚂蚁完成了它的遍历，然后找出在当前时刻任务的最短完成时间，那么给这次遍历一个增强，对它所爬行过的虚拟机节点进行全局信息素更新，这时，其值更新如下：δτij(t,t 1)＝d/tij(10)tij表示任务i在最优分配中在vmj上处理花费的时间，d是一个常数。步骤4，当蚂蚁移动到新的任务后，更新其经过路径的信息素，并修改禁忌表，在蚂蚁的每次搜索过程中，都会对信息素按(4)公式进行更新，当所有的蚂蚁完成一次迭代之后，即所有蚂蚁都完成了路径搜索时，跳转到步骤2，然后对路径上的虚拟机进行全局信息素更新；步骤5，计算每只蚂蚁的任务完成时间，并保留当前时刻的最小的任务完工时间；判断是否满足迭代结束条件，如果满足，结束迭代过程并输出最优任务分配方案，否则，转到步骤2，直到满足迭代条件为止。为了测试本算法的有效性，本次对经典的旅行商(tsp)问题进行仿真实验，实验采用的数据集是tsplib的eil51，来进行结果分析。1)仿真条件实验所用操作系统为windows10，仿真软件visualstudio2019，处理器为i5-8250u，安装内存8.00gb。2)参数设置基本蚁群算法的参数设置：蚂蚁数量25，迭代次数为1000，α＝1，β＝3，ρ＝0.5，q＝100，ω＝1.1；遗传算法参数设置：种群大小为100，最大迭代次数为1000，交叉概率：0.9，变异概率：0.1；最大最小蚁群算法中所采用的实验参数为：最大迭代次数为1000，α＝1，β＝2，ρ＝0.85，q＝100，τmax＝20，τmin＝1；3)仿真结果为了防止实验的不确定性以及不可避免的误差，对所有的结果进行多次试验，其中最优解、最差解、平均解是经过10次的加权平均得到，同时算法参数的取值不同，都会出现可能较大的偏差，因此，上述的参数是多次比较后的最优初值。最优解能间接的反应算法的寻优性能、解的范围，采用改进的最大最小蚁群算法的最短路径示意图，如图5所示。1)最短路径比较根据仿真结果，数据集eil51中的51个城市之间的最短距离为428，在寻优性能上改进的最大最小蚁群算法优于遗传算法和基本蚁群算法，得到的三种算法的路径距离比较数据如表1：算法名称最优解最差解平均解mmas428435430.1ga449.2456452aco436459449.3表1从图6可以看出，相对比其他两个算法，采用改进的mmas算法，51个城市之间的距离最短。2)算法执行时间参照图7，算法的执行时间反映了收敛速度和执行效率，从图7可以看出，改进的算法在收敛速度得到了极大的提高，因此，本发明具有高效性、可行性。最大最小蚁群算法实际应用到云计算中的负载均衡调度同样具有可行性，如基本的蚁群算法一样，具有节约开销、提高资源利用率的作用，实验证明，本发明中改进的算法有更高的效率。本说明书未作详细描述的内容属于本领域专业技术人员公知的现有技术。当前第1页1 2 3
技术特征：1.一种基于改进mmas的负载均衡调度方法，其特征在于，所述方法包括以下步骤：
步骤1，参数及环境初始化，过程如下：
1.1设置时间t＝0，迭代次数nc＝0，最大迭代次数设置蚁群的群体规模，蚂蚁的数量m，并将m只蚂蚁放在每一个节点坐标上；初始化信息素大小；
1.2将所有路径的信息素限制在最大值τmax和最小值τmin之间，高于或低于这一区域都会被自动调整为τmax或τmin，保证信息素最小的路径也在选择范围内，设置最大最小的信息素如(1)、(2)式：
其中l(t)表示第t次迭代最优路径长度，ρ为信息素挥发系数，将各条路径上的信息素控制在[τmin，τmax]之内，对于超出这个范围的值，大于τmax的就取τmax，若小于τmin则取τmin，这样的好处就是可以有效地避免某条路径上的信息素量远大于其他路径而造成的所有蚂蚁都集中到同一条路径上，从而使算法不再扩散、陷入局部最优；
步骤2，随机分布在各结点的蚂蚁开始活动，各蚂蚁依据式(3)的状态转移概率进行路径选择，过程如下：
2.1结点上的每只蚂蚁根据由式如下定义的转移概率选择下一个结点，转移概率定义为：
其中，τij表示边(i,j)的信息素强度，ηij＝1/cij表示关系i转移到关系j的期望程度，cij为关系i和j的连接代价，α为轨迹的相对重要性，β为期望的相对重要性；
2.2m只蚂蚁同时从不同的结点出发,根据式(3)选择下一结点，已去过的放入禁忌表(tabuk)中，用禁忌表存储蚂蚁已经走过的关系,allowedk是蚂蚁k还未选择的结点集合，保证所有解的逻辑可行；
步骤3，当蚂蚁移动到新的结点上后，根据式(4)更新其经过路径的信息素，并修改禁忌表，过程如下：
3.1使用表示更新后的信息素浓度，表示更新前的信息素浓度，在蚂蚁的每次搜索过程中，都会对信息素按如下公式进行更新：
其中，ω为引入的奖惩系数，lcur为当前路径的总长度，llast为上一次的路径的总长度；
3.2当出现最优路径时，对当前信息素浓度增加作为奖励，当出现相对较差路径时，则对当前信息素浓度减去作为惩罚，当出现最差路径时，则对当前信息素浓度减去作为严惩，增加双向收敛策略的目的是增加较优路径上的信息素浓度、减小较差路径上的信息素，使较多的蚂蚁更快集中到较好路径的搜索上以加快全局最优解搜索速度，并且扩大了解的范围；
步骤4，重复执行步骤2，3，4直到整个蚁群中的每个蚂蚁都找到一个可行路径为止，记录路径总长度，对比所有可行路径，记录最优和最差路径；
步骤5，通过步骤4的结果对当前最优路径进行“奖励”，对最差路径进行“严惩”，对比上一个路径长的路径进行“轻罚”，更新所有路径的信息素浓度，重新随机选择蚂蚁的位置，对所有路径上的信息素进行全局更新；
步骤6，如果迭代次数达到预设迭代次数，则终止搜索，得出最优解；如果未达到迭代次数，并使t＝t 1，转到步骤2。
技术总结一种基于改进MMAS的负载均衡调度方法，蚁群算法在组合优化问题和NP难的问题上具有高效性和可行性，它具有正反馈性、较强的鲁棒性、分布性和扩展性。针对基本的蚁群算法的计算执行时间较长、容易陷入局部最优解造成停滞，本发明给出了一种改进的最大最小蚁群算法，通过双向收敛的信息素更新的方式，很好的解决了算法执行时间长的缺点；然后通过限定信息素浓度允许值的上下限，克服了算法过早停滞，增大了解的范围，而且在寻优方面有所改善。通过对经典的旅行商问题进行验证，该算法具备了基本蚁群算法所具备的优点，实验表明，该改进算法有更高的执行效率和更好的计算稳定性。
技术研发人员：李胜;王忠超
受保护的技术使用者：浙江工业大学
技术研发日：2019.12.30
技术公布日：2020.06.05
