论文研究-改进差分进化算法求解整数任务分配.pdf

所需积分/C币:50 2019-09-10 21:10:49 474KB .PDF
70
收藏 收藏
举报

针对0-1任务规划模型存在维数灾维的问题,提出了一种基于改进差分进化算法的整数任务分配算法。将任务分配的0-1规划模型转化整数规划模型,不仅大幅降低了优化变量的维数,还减小了整式约束条件;将差分进化算法常用的变异算子DE/rand/1/bin和DE/best/2/bin结合起来组成新的变异算子,使得DE既保持了种群的多样性,又有较快的收敛速度和搜索精度,并用改进的差分进化算法求解整数规划;通过典型的任务分配实例验证了该算法在优化大规模任务分配的有效性和快速性。
王永皎:改进差分进化算法求解整数任务分配 2012,48(31) 55 v, if rand(sCR, or j=nbr(i) 为:种群规模NP=60,缩放因子F=0.5,交叉概卒CR= otherwise 07,0-1规划模型的最大迭代代数为20004000 其中,mn(为,]之间的均匀分布随机数,CR为60008000时于(,m分别设置为(5,3),(10.6) 范围在[0,1之间的交叉概率;mnbr()为{1,2,…,D} (15,9)和(20,12)),整数规划模型的最大迭代代数 之间的随机量。 为200、400、600和800。本文采用同样的方法产生 33选择操作 12个问题,每一个问题分别用改进的差分进化算法 DF采用“贪婪”的搜索策略,经过变异与交叉璨对0-1规划模型和整数规划模型进行优化,并且独立 作后生成的试验个体+1与x进行竞争,只当1蓝行10次,取平均最优值、方差和平均耗时进行比 较,如表1所示。 的适应度值较x更优时才被选作子代,否则直接将 从表1可以看出,整数规划模型的平均耗时只有 作为子代,即 0-1规划模型的平均耗的1/10,其主要原因是整数规 n,f(x+)<f( 划模型优化变量的维数只有0-1规划模型的1/n,同时 (7) otherwise 满足等式约東条件,大大简化了优化的过程。在优 其中/为目标函数 化小规模的任务分配问题时,0-1规划模型和整数规 划模型两种模型的均能搜索到最优解,且方差为0, 4实验结果及分析 但在优化大规模的任务分配问题时,整数规划模型 TAP问题中,不同工作之间的通信由任务交互表的平均最优值、方差和平均耗时均显著小于01规划 模型,充分说明将任务分配的0-1规划模型转化为整 (TIG)来说明。集合G(V,E)用来详细解释TIG,其数规划模型不仅可以简化计算,而且还可以加快算 中,V是r个节点的集合,用来代表个被执行的任法的收敛,这种优势在人规模任务分配时,表现尤为 务;每个边缘(,∈E与cn有关,它表示仅当工作i 突出。 中和被分配给不同处理器时所蒙受的通信成木。Yin 等"定义了集合G(,E)的工作交互密度d,用它米计5结论 算TG中工作通信的比例。为了测试算法对不同规 本文将TAP的0-模型转化为整数模型,使得 模的问题的适应性,Yin等将(,m)分别设置为(5,3),TAP的优化变量维数不会随任务数和处理器数的增 (10,6),(15,9)和(20,12),并设置了3种不同的工作加而呈几何级数增长,仅为0-1模型的1/n(n为处理 交互密度d,分别为0.3、0.5和0.8。TAP的其他参数器数),同时,自然满足等式约束条件:将DE的两种 都是在·定范围内随机产生的,具体可参见文献[1常用的变异算子 DE/rand/1/bin和 DE/best2/bin结合 计算机的配置:操作系统为 Windows Xp,CPU起来组成新的变异算子,不仅可保持DE种群的多样 为 Mobile AMd Sempron Processor2600+,内冇为性,还可以加快DE的收敛。本文算法在求解大规模 768MDDR,仿真环境为 Matlab7.03DE的参数设置任务分配时,性能尤为突出,具有广泛的应用前景。 表1改进的差分进化算法求解两种任务规划模型的比较 0-1规划模型 整数规划模型 平均最优方差平均耗时平均最优方差平均耗时 0.3 310.5764 17.5262310.5764 1.3880 4495524 18.128144955240 1.3399 0.8343.100521.017.5923330.18490 1.3369 0.3755.251664.673.786167238843.15215.4008 1060.5857.500068.3738973708.8694 5.4268 0.81014.400059.873.9383902.610216.16565.5730 0.31222.9000814204.2747730.085034.649714.8033 1590.519750000162.0204.11551517900076.900014.8223 082253.8000121.020392921717.200015.800014.8293 0.32644.8000223.444948631489200033.900033.7445 20120.53567.6000183.0463.14702635000078.500034.1832 0.84603.2000608.4461.17003317.1000114.900033.8817 下转114页)

...展开详情
试读 3P 论文研究-改进差分进化算法求解整数任务分配.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-改进差分进化算法求解整数任务分配.pdf 50积分/C币 立即下载
1/3
论文研究-改进差分进化算法求解整数任务分配.pdf第1页

试读结束, 可继续阅读

50积分/C币 立即下载