混合蚁群算法求解分布式系统任务分配问题

Hybrid ant colony algorithm task allocation problem in distributed systems

任务分配问题是被公认的NP-hard问题,应用广泛。在对分布式系统任务分配问题进行分析的基础上,将蚂蚁寻求任务分配方案的过程用一种新的图形表示方式来实现。针对蚁群优化算法易陷入局部最优的固有缺陷,提出了一种新的混合算法,该算法将蚁群优化算法与简单禁忌搜索算法相结合,增强了算法的局部搜索能力,提高了任务分配问题解的质量。实验结果表明混合算法的求解性能较优。

The task allocation problem is a NP-hard problem and it has numerous applications. Based on the analysis about task allocation problem in distributed system, a new graph representation for solving it is designed. Aiming at easily plunging into local optimization of the ant colony optimization algorithm, a new hybrid algorithm is proposed. It adopts tabu search in ant colony optimization algorithm to enhance its ability of local search and improve the quality of the solution. The experiments show that the proposed algorithm has better performance.