一种改进萤火虫算法的CMP任务调度方法

摘要

本发明提供一种改进萤火虫算法的CMP任务调度方法，步骤1：萤火虫种群的预计输入数量N，介质对光的吸收系数为γ，初始步长因子α，最大吸引度β0，吸引度阈值βM；步骤2：根据初始化策略对萤火虫种群数量及其位置进行初始化；步骤3：根据萤火虫位置计算其适应度值；步骤4：每个萤火虫向比自己亮度高的萤火虫飞行，计算其到达新位置后的适应度值，若优于原位置，则到达新位置，否则停留在原位置；步骤5：对寻优结果进行判定，若满足终止条件，则结束迭代进程，否则重复步骤3操作，对萤火虫粒子进行再次迭代。本发明加快了萤火虫粒子的收敛速度，并极大地降低了寻优过程中陷入局部最优解的可能性，减少不必要的迭代次数，缩短了任务调度的完成时间。

说明书

技术领域

本发明涉及一种CMP任务调度方法，尤其涉及一种改进萤火虫算法的CMP任务调度方法，属于任务调度技术领域。

背景技术

随着计算机软件科技水平日益趋向成熟的发展，现代应用对计算机硬件性能的要求不断提高。在半导体工艺发展相对缓慢的限制下，仅靠提高单核主频不足以维持摩尔定律，多核处理器(Chip Multi-core Processor)应运而生。在多核处理器的支持下，一个芯片汇集多个处理器核，以最小的代价满足了提高系统性能、负载均衡的需求。当然，为了能让多核处理器的优越性得到发挥和体现，一个好的任务调度算法是必不可缺的。

为了能够得到最优的任务调度策略，相关学者将群体智能算法用于任务调度序列的求解中，并在实际的应用当中证明了这一理论体系的实践可能性。作为一种相对新颖的群体智能算法，萤火虫算法的思想来源于模拟萤火虫之间的信息交流行为。群体中的每个个体(萤火虫粒子)是对应问题的一个候选解。萤火虫算法的搜索依靠个体之间的吸引而产生移动，适应度较差(较暗)的萤火虫向适应度较好(较亮)的萤火虫移动。

萤火虫算法虽然在寻优问题上能表现出比较好的性能，但仍然存在着一些不足之处，如收敛速度慢以及在复杂问题上易陷入局部最优等。

发明内容

本发明的目的是为了解决收敛速度慢以及在复杂问题上易陷入局部最优的问题而提供一种改进萤火虫算法的CMP任务调度方法。

本发明的目的是这样实现的：

一种改进萤火虫算法的CMP任务调度方法，所述方法包括以下步骤：

步骤1：定义参数含义，初始化基本参数如下：

萤火虫种群的预计输入数量N(N为正整数)，介质对光的吸收系数为γ，初始步长因子α，最大吸引度β

步骤2：根据初始化策略对萤火虫种群数量及其位置进行初始化；

步骤3：根据萤火虫位置计算其适应度值，适应度值越高的亮度越高；

步骤4：每个萤火虫向比自己亮度高的萤火虫飞行，计算其到达新位置后的适应度值，若优于原位置，则到达新位置，否则停留在原位置；

步骤5：对寻优结果进行判定，若满足终止条件，则结束迭代进程，否则重复步骤3操作，对萤火虫粒子进行再次迭代。

本发明还包括这样一些特征：

所述步骤2初始化策略如下：

(1)根据探索范围将解空间等分为

(2)采用随机生成的方式加入新的萤火虫粒子；

(3)若输入的新萤火虫与距离最近的萤火虫间的相对吸引度大于β

(4)重复进行步骤(3)，直至每个分组的初始萤火虫数都达到

所述步骤5终止条件如下：

对寻优结果进行判定，设置一个阈值max_step，并记录寻优结果保持不变的次数f_step，若f_step＞max_step，则终止寻优过程。

与现有技术相比，本发明的有益效果是：

本发明改进萤火虫算法的初始化方法，使各萤火虫的初始位置分布更为均匀，从而加快了萤火虫粒子的收敛速度，并极大地降低了寻优过程中陷入局部最优解的可能性；通过改进寻优终止策略，减少不必要的迭代次数，缩短了任务调度的完成时间。

附图说明

图1是基于改进萤火虫算法的CMP任务调度流程图。

具体实施方式

下面结合附图与具体实施方式对本发明作进一步详细描述。

本发明的目的是提供一种改进的萤火虫算法的CMP任务调度方法。

萤火虫算法虽然在寻优问题上通常能够表现出比较好的性能，但仍存在着一些不可忽视的缺陷。比如，标准的萤火虫算法采用的是随机生成的初始化方式，这种初始化方式有极大的可能会导致萤火虫种群的初始位置分布不均，从而令萤火虫种群的收敛速度变得缓慢，并且在复杂的寻优问题上容易陷入局部最优解。另外，标准的萤火虫算法采用的寻优终止策略是当达到最大迭代次数后对其进行终止。而在实际应用中，最大迭代次数若设置的过大，会增加不必要的迭代时间和计算花销，反之，则可能导致输出结果与实际最优值有较大偏差。

针对上述萤火虫算法存在的问题，本发明对标准萤火虫算法的初始化方式和寻优终止策略做出了改进。

首先，为了减少寻优过程中陷入局部最优解的可能性，本发明在初始化时将解空间进行了分组，并通过萤火虫粒子之间的吸引度对萤火虫粒子进行了筛选，从而达到萤火虫种群初始化分布均匀的效果。

其次，本发明在寻优过程中引入了阈值max_step和寻优结果保持不变的次数f_step，若f_step＞max_step，则终止寻优过程。

改进的萤火虫算法包括以下步骤：

步骤1：定义参数含义，初始化基本参数如下：

萤火虫种群的预计输入数量N(N为正整数)，介质对光的吸收系数为γ，初始步长因子α，最大吸引度β

步骤2：根据改进的初始化策略对萤火虫种群数量及其位置进行初始化；

步骤3：根据萤火虫位置计算其适应度值，适应度值越高的亮度越高；

步骤4：每个萤火虫向比自己亮度高的萤火虫飞行，计算其到达新位置后的适应度值，若优于原位置，则达到新位置，否则停留在原位置；

步骤5：根据改进的终止条件对寻优结果进行判定，若满足条件，则结束迭代进程，否则重复步骤3操作，对萤火虫粒子进行再次迭代。

本发明在原有基础上改进了萤火虫算法的初始化方式，通过求解萤火虫样本之间的吸引度筛选出N个优质的萤火虫样本，使各萤火虫的初始位置分布更为均匀，从而加快了萤火虫粒子的收敛速度，并极大地降低了寻优过程中陷入局部最优解的可能性。在寻优过程的后期，N个萤火虫经过多次的迭代后，对寻优情况进行判定，当满足条件时，结束寻优过程，以确保在达到求最优解目标的同时，减少不必要的迭代次数所造成的时间和空间的花销。

本发明的详细步骤如下：

步骤1：假设X

步骤2：根据改进初始化策略对萤火虫种群数量及其位置进行初始化，初始化步骤如下：

(1)根据探索范围将解空间等分为

(2)采用随机生成的方式加入新的萤火虫粒子；

(3)若输入的新萤火虫与距离最近的萤火虫间的相对吸引度大于β

其中，r

(4)重复进行步骤(3)，直至每个分组的初始萤火虫数都达到

步骤3：根据萤火虫位置计算其适应度值，适应度值越高的亮度越高；

步骤4：每个萤火虫向比自己亮度高的萤火虫飞行，计算其到达新位置后的适应度值，若优于原位置，则达到新位置，否则停留在原位置，位置的更新方式依照如下公式：

x

步骤5：对寻优结果进行判定，设置一个阈值max_step，并记录寻优结果保持不变的次数f_step，若f_step＞max_step，终止寻优过程，反之则进行下一次迭代。

本发明的应用实例为针对CMP架构的应用，通过改进的萤火虫算法对每个核进行最佳调度策略选择，但本发明的保护范围并不仅仅局限在此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，凡依本发明技术方案作变换或替换的，都应该涵盖在本发明的保护范围内。因此，本发明的保护范围都应以权利要求的保护范围为准。

综上所述：本发明提供一种改进萤火虫算法的CMP任务调度方法。基础的的萤火虫算法虽然在寻优问题上能表现出比较好的性能，但仍然存在着一些不足之处，如收敛速度慢以及在复杂问题上容易陷入局部最优等。针对这些问题，本发明对萤火虫算法的初始化进行了改进，根据萤火虫粒子之间的吸引度筛选出N个优质的萤火虫粒子，使各萤火虫的初始位置分布更为均匀，从而加快了萤火虫种群的收敛速度，并极大地降低了寻优过程中陷入局部最优解的可能性。在寻优过程的后期，N个萤火虫经过多次的迭代后，对寻优情况进行判定，当满足条件时，结束寻优过程，以确保在达到求最优解目标的同时，减少不必要的迭代次数。