任务分配与调度的共同进化方法

并行与分布式计算环境中随着独立任务的增多，传统进化类单种群的任务分配与调度算法的效率与效力随之大为降低，该文在分析传统解完整编码单种群进化类算法的基础上，基于生物界多物种间共同进化的机制提出了任务分配与调度的合作式共同进化计算模型，并探讨了任务分配与调度问题中的子种群合作方式与个体的适应值计算方法。此外，从数学上分析了基于合作式共同进化的任务分配与调度算法的性能，指出共同进化调度方法中好的调度方案能以高于传统单种群进化算法的递增指数递增。仿真分析证实了算法的理论分析结果，算法具有实际工程价值。

Task Allocation & Scheduling by Computational Model of Coevolution

Task allocation and scheduling plays a key role in network computing environment and makes a notable impact on the overall performance. Scheduling problems are known to be in general NP complete, only sub optimal can be obtained by classical scheduling approaches in most cases. Though the conventional single population based genetic algorithms (CSGAs) can find solutions with better quality than classical approaches for scheduling problems, the efficacy and efficiency of CSGA decrease with the increase of number of tasks in parallel and distributed systems. By analyzing the mechanism that makes CSGA in scalable, this paper firstly proposed a task allocation and scheduling algorithm based on computational model of cooperative coevolution, which is inspired by the coevolutionary phenomena of natural species. Then, some related work is discussed, including permutation representation of chromosome, genetic operators such as improved crossover, internal crossover and migration as a kind of mutation, cooperative interactions among species by selecting the best individual as its cooperative representative, combination of sub schedules into a whole, and fitness computation of individuals. The algorithm was analyzed mathematically, which shows that the exponential increase index of the coevolution based scheduling algorithm is higher than that of CSGA. At last, simulation results of the proposed algorithm and CSGA are given, which verify the theoretical results, and show that the convergence and optimal/sub optimal of proposed algorithm are better than that of CSGA. The algorithm is of practical use in engineering.