利索能及
我要发布
收藏
专利号: 201911391039X
申请人: 浙江工业大学
专利类型:发明专利
专利状态:已下证
更新日期:2026-07-29
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

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。