差分进化算法及其在云计算任务调度中的应用研究

兰州交通大学  朱宇航

本文拟将其改进后应用于云计算任务调度问题。改进分两个步骤：首先，对基本差分进化算法本身的不足进行改进；然后以此为基础，面向云计算任务调度问题的特点，再作进一步的改进。针对差分进化算法本身的不足，本文提出了改进的离散差分进化算法：MDDE。提出了差分进化算法的离散化原则，使之可以应用到组合优化问题。然后，针对算法优化性能的不足，提出了进化过程前后期的概念。在进化前期设置了并行多种群，并定义了一种综合差分策略，即进化前后期分别采用差分策略DE1与DE2，均衡了MDDE算法的全局探索和局部挖掘的能力，保证了算法在进化前期拥有良好的全局探索能力，在后期拥有快速的局部挖掘性能。提出了贪婪交叉原则，并新增了变异操作之后的选择机制，进一步加快了算法的收敛速度。将MDDE算法应用到TSP问题的求解中，验证了其优化性能。结合云计算任务调度的特点，本文在MDDE算法的基础上提出了满足QoS需求的云计算任务调度算法：TC-MDDE。按照离散化原则，结合任务顺序编码法，针对差分运算出现非法编码的问题，定义了绝对值取整求余映射法进行非法编码的合法化处理，保证了变异操作的顺利进行。针对云计算任务调度问题中QoS的多样化需求，定义了参数灵活的适应度函数，能够根据用户不同的时间和成本需求，调整时间与成本的权值系数，达到对调度结果的影响。

差分进化算法及其在云计算任务调度中的应用研究