计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (31): 53-55.

• 研究、探讨 • 上一篇    下一篇

改进差分进化算法求解整数任务分配

王永皎   

  1. 河南城建学院,河南 平顶山 467044
  • 出版日期:2012-11-01 发布日期:2012-10-30

Improved differential evolution algorithm for integer task assignment

WANG Yongjiao   

  1. Henan University of Urban Construction, Pingdingshan, Henan 467044, China
  • Online:2012-11-01 Published:2012-10-30

摘要: 针对0-1任务规划模型存在维数灾维的问题,提出了一种基于改进差分进化算法的整数任务分配算法。将任务分配的0-1规划模型转化整数规划模型,不仅大幅降低了优化变量的维数,还减小了整式约束条件;将差分进化算法常用的变异算子DE/rand/1/bin和DE/best/2/bin结合起来组成新的变异算子,使得DE既保持了种群的多样性,又有较快的收敛速度和搜索精度,并用改进的差分进化算法求解整数规划;通过典型的任务分配实例验证了该算法在优化大规模任务分配的有效性和快速性。

关键词: 差分进化算法, 任务分配, 整数规划

Abstract: In order to overcome the problem that the general 0-1 task assignment exists dimension disaster problem, an integer task assignment based on modified differential evolution algorithm is proposed. The 0-1 task assignment model is transferred into integer task assignment model, which not only decreases the dimension of variable, but also decreases equation constrains. Then, the classical DE/rand/1/bin and DE/best/2/bin mutation operators are added with linear weight, which make the DE algorithm not only maintain diversity of population, but also convergent quickly. The integer task assignment model is optimized by the modified differential algorithm. Several classic task assignment problems are tested, and the experimental results show that the proposed algorithm has good performance in the large scale task assignment problem.

Key words: differential evolution algorithm, task assignment, integer programming