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

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

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

王永皎

河南城建学院，河南平顶山 467044

出版日期:2012-11-01 发布日期:2012-10-30

Improved differential evolution algorithm for integer task assignment

WANG Yongjiao

Henan University of Urban Construction, Pingdingshan, Henan 467044, China

Online:2012-11-01 Published:2012-10-30

摘要/Abstract

摘要： 针对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

王永皎. 改进差分进化算法求解整数任务分配[J]. 计算机工程与应用, 2012, 48(31): 53-55.

WANG Yongjiao. Improved differential evolution algorithm for integer task assignment[J]. Computer Engineering and Applications, 2012, 48(31): 53-55.

[1]	陈宝童，王丽清，蒋晓敏，姚寒冰. 群智协同任务分配研究综述[J]. 计算机工程与应用, 2021, 57(20): 1-12.
[2]	钱峥远，曾国荪. 精英化岛屿种群引导的差分进化算法[J]. 计算机工程与应用, 2021, 57(20): 73-81.
[3]	崔彩霞，毕超超，范勤勤. 基于隐马尔可夫链的自适应MODE及应用[J]. 计算机工程与应用, 2021, 57(14): 83-94.
[4]	李荣，贺兴时，杨新社. 基于差分进化的飞蛾算法在电力调度中的应用[J]. 计算机工程与应用, 2021, 57(13): 258-268.
[5]	杨雅洁，苌道方，余芳. 考虑AGV避碰的自动化码头多资源协同调度[J]. 计算机工程与应用, 2020, 56(6): 246-253.
[6]	沈鑫，邹德旋，张强. 采用双变异策略的自适应差分进化算法及应用[J]. 计算机工程与应用, 2020, 56(4): 146-157.
[7]	王梦娇，尹翔，黄宁馨. 基于迁移学习的多任务分配算法[J]. 计算机工程与应用, 2020, 56(13): 150-155.
[8]	迟宗正，董绍正，郭童，任志磊，周宽久，郭禾. 求解风力发电机布局问题的超启发式算法研究[J]. 计算机工程与应用, 2019, 55(7): 220-225.
[9]	唐震，殷志祥，崔建中，杨静，孙侠. DNA折纸术在一类特殊的整数规划问题中的应用[J]. 计算机工程与应用, 2019, 55(16): 49-54.
[10]	陈友玲，赵金鹏，兰桂花，黄典. 基于双边知识匹配的产品开发任务分配方法[J]. 计算机工程与应用, 2018, 54(22): 223-228.
[11]	刘利斌1，2，隆广庆1，2，上官珍萍1. 差分进化与有理谱方法求解奇异摄动问题[J]. 计算机工程与应用, 2018, 54(17): 225-230.
[12]	钱武文，柴军瑞，张子映，谈然. 基于反射变异策略的自适应差分进化算法[J]. 计算机工程与应用, 2018, 54(15): 161-168.
[13]	王雪琴1，蒋建国1，2，齐美彬1，2. 全局分层关联网络流在多目标跟踪中的应用[J]. 计算机工程与应用, 2018, 54(14): 180-185.
[14]	王国豪1，2，李庆华1，刘安丰2. 一种云工作流任务调度能效优化算法[J]. 计算机工程与应用, 2018, 54(10): 90-98.
[15]	张锦华1，宋来锁2，张元华3，李富昌4. 加权变异策略动态差分进化算法[J]. 计算机工程与应用, 2017, 53(4): 156-162.