计算机应用 ›› 2012, Vol. 32 ›› Issue (08): 2165-2167.DOI: 10.3724/SP.J.1087.2012.02165

• 先进计算 • 上一篇    下一篇

改进自适应差分进化算法求解大规模整数任务分配

王永皎   

  1. 河南城建学院 计算机科学与工程系,河南 平顶山 467007
  • 收稿日期:2012-02-01 修回日期:2012-03-14 发布日期:2012-08-28 出版日期:2012-08-01
  • 通讯作者: 王永皎
  • 作者简介:王永皎(1977-),女,河南新乡人,副教授,博士,主要研究方向:人工智能、图像处理。

Improved self-adaptive differential evolution algorithm for large-scale integer task assignment

WANG Yong-jiao   

  1. Department of Computer Science and Engineering, Henan University of Urban Construction, Pingdingshan Henan 467044, China
  • Received:2012-02-01 Revised:2012-03-14 Online:2012-08-28 Published:2012-08-01
  • Contact: WANG Yong-jiao

摘要: 针对0-1任务规划模型存在维数灾维的问题,提出一种基于改进自适应差分进化(SADE)算法的大规模整数任务分配算法。首先,将任务分配的0-1规划模型转化整数规划模型,不仅大幅减少了优化变量的维数,还减少了整式约束条件;然后,将常用的变异算子DE/rand/1/bin和DE/best/2/bin结合起来组成新的自适应变异算子,使得自适应差分进化算法既有较快的收敛速度,又降低了变异算子对具体问题的依赖;并用改进自适应差分进化算法求解整数规划。最后,通过典型的任务分配实例验证了算法在优化大规模任务分配的有效性和快速性。

关键词: 自适应差分进化算法, 任务分配, 0-1规划, 整数规划, 变异

Abstract: In order to solve the problem that the general 0-1 task assignment has dimension disaster problem, an integer task assignment based on improved Self-Adaptive Differential Evolution (SADE) algorithm was proposed. Firstly, 0-1 task assignment model was transferred into integer task assignment model, which not only decreased the dimension of variable, but also decreased equation constraints. Then, classical DE/rand/1/bin and DE/best/2/bin mutation operators were added with linear weight, which made the SADE algorithm not only converge quickly, but also decrease independence on concrete problem, and the integer task assignment model was optimized by the improved SADE algorithm. At last, several classic task assignment problems were tested. The experimental results show that the proposed algorithm is effective and speedy on the large-scale task assignment.

Key words: Self-Adaptive Differential Evolution (SADE) algorithm, task assignment, 0-1 programming, integer programming, variation

中图分类号: