分层混合局部搜索策略异构多核系统调度

摘要

Genetic algorithm is prone to premature and weak in local optimisation capabilityto solve the problem oftasks scheduling for heterogeneous multi-core system.In light of this,with the local search algorithm and genetic algorithm combined,this paper proposesa genetic algorithm for hierarchical hybrid local searchcreatively to solve the problemof tasks scheduling forheterogeneous multi-core system.In this algorithm,the initial population is generated by the new hierarchical optimization strategy,3-opt algorithm will be applied to some individuals for optimisation and variation,the improved Lin-Kernighan algorithm will be employed for optimization for those excellent individuals in the population.The simulation results show that the proposed genetic algorithm for hierarchical hybrid local search can get high-quality solution efficiently when applied to solve the problem oftasks scheduling for heterogeneous multi-core system.%针对遗传算法解决异构多核系统的任务调度问题容易产生早熟现象及其局部寻优能力较差的缺点,将局部搜索算法与遗传算法相结合,创新性地提出一种求解异构多核系统的任务调度问题的分层混合局部搜索遗传算法.该算法提出一种新的分层优化策略以产生初始种群,在变异操作中,对部分个体设计3-opt优化变异,对种群中的优秀个体用改进的Lin-Kernighan算法进行优化.仿真实验结果表明,分层混合局部搜索遗传算法求解异构多核系统的任务调度问题时可以高效获得高质量的解.