学位论文 > 优秀研究生学位论文题录展示

基于遗传算法多目标P2P任务调度策略研究

作　者: 牛庆建
导　师: 孟宪福
学　校: 大连理工大学
专　业: 计算机软件与理论
关键词: P2P网络 任务调度 遗传算法 多目标 拍卖理讼
分类号: TP393.02
类　型: 硕士论文
年　份: 2010年
下　载: 70次
引　用: 0次
阅　读: 论文下载
 

内容摘要


随着P2P网络的高速发展,如何构建系统性能高、稳定性强、扩展能力好的分布式对等网络计算系统成为目前的研究热点,任务调度是构建分布式对等计算的一项重要技术,任务调度算法的好坏直接制约着对等计算的整体性能。任务调度是指根据一定的策略将需要调度的任务按规定的时序分配到网络中的处理节点上,该问题被证明是一个NP完全问题。目前,根据任务模型是否存在约束关系可分为关联任务调度以及并行任务调度。与仅考虑任务执行时间的传统调度算法不同,P2P网络结构的特点决定了P2P任务调度是受任务执行时间、结点间的通信时间和任务调度费用等多个因素制约的,因此,在P2P网络下进行任务调度需要综合考虑这些因素。针对P2P环境下多目标约束的关联任务调度,提出了基于多目标遗传算法的P2P关联任务调度机制。针对目前遗传算法解决关联任务调度中染色体采用直接编码易出现非可能解的问题,设计了新颖的双染色体,并同时设计了相应的双交叉以及双变异操作,从而避免了非可行解的出现。同时,对任务的评价是建立在任务执行时间、任务调度费用以及节点通信时间三个因素的基础上的,建立了任务执行时间、调度费用以及通信时间三个目标函数,然后采用有界精英保留操作建立精英种群从而使算法具有良好的收敛性以获得高质量的解,引入共享染色体的方法对染色体的适应度值进行调整,从而保证了种群的多样性,避免了早熟收敛,最后通过实验验证了任务调度算法的可行性。针对P2P环境下多目标约束的并行任务调度,提出了一种基于多属性组合拍卖的并行任务调度机制。首先从招标者的视角出发,选取任务执行时间、执行费用和通信时间三个因素作为组合拍卖赢家的标准,建立多属性组合拍卖任务调度的数学模型。然后根据协同进化的思想,给出了一种多目标单亲遗传算法,并通过设计新颖的启发式染色体以及自适应基因重组算子对模型进行求解。实验结果表明,基于多属性组合拍卖的任务调度比传统的方法更能优化任务调度的性能。

全文目录


摘要  4-5
Abstract  5-9
1 绪论  9-19
  1.1 P2P网络技术  9
  1.2 P2P网络特点  9-10
  1.3 P2P网络体系结构  10-14
  1.4 P2P网络技术的应用  14-16
  1.5 P2P网络的研究现状  16-17
    1.5.1 国外研究现状  16-17
    1.5.2 国内研究现状  17
  1.6 论文的主要工作  17-18
  1.7 论文的组织结构  18-19
2 P2P任务调度以及遗传算法  19-27
  2.1 P2P任务调度  19-24
    2.1.1 P2P任务调度的特点  19-20
    2.1.2 任务调度的目标  20-21
    2.1.3 任务调度的流程  21-22
    2.1.4 任务调度算法  22-24
  2.2 遗传算法  24-26
    2.2.1 遗传算法的基本理论  24-25
    2.2.2 遗传算法的基本流程  25-26
  2.3 本章小结  26-27
3 基于多目标遗传算法的P2P关联任务调度机制  27-41
  3.1 问题的提出  27-28
  3.2 相关模型与定义  28-30
  3.3 算法设计  30-38
    3.3.1 多目标遗传算法  30-31
    3.3.2 染色体  31-33
    3.3.3 目标函数  33
    3.3.4 种群的初始化以及适应度值  33-35
    3.3.5 双交叉操作  35-36
    3.3.6 双变异操作  36
    3.3.7 选择操作  36-37
    3.3.8 任务调度完全算法  37-38
  3.4 实验与结果分析  38-40
  3.5 小结  40-41
4 基于多属性组合拍卖的P2P并行任务调度机制  41-53
  4.1 问题的提出  41-42
  4.2 多属性组合拍卖模型  42-43
    4.2.1 模型描述  42
    4.2.2 限定条件  42
    4.2.3 模型建立  42-43
  4.3 算法设计与问题求解  43-49
    4.3.1 多目标单亲遗传算法  44
    4.3.2 适应度函数  44-45
    4.3.3 编码策略  45
    4.3.4 种群初始化  45-46
    4.3.5 选择操作  46
    4.3.6 基因重组算子  46-48
    4.3.7 任务调度流程  48-49
  4.4 实验结果与分析  49-52
  4.5 小结  52-53
结论  53-54
参考文献  54-57
攻读硕士学位期间发表学术论文情况  57-58
致谢  58-60

相似论文

  1. 基于差分进化算法的JSP环境下成套订单研究,F273
  2. 天然气脱酸性气体过程中物性研究及数据处理,TE644
  3. 压气机优化平台建立与跨音速压气机气动优化设计,TH45
  4. 基于蚁群算法的电梯群优化控制研究,TU857
  5. 基于遗传算法的模糊层次综合评判在高职教学评价中的应用,G712
  6. 部队人员网上训练与考核系统的开发,TP311.52
  7. 基于并行算法的模糊综合评价模型的设计与应用,TP18
  8. 基于神经网络的牡蛎呈味肽制备及呈味特性研究,TS254.4
  9. 基于遗传算法的中短波磁天线的设计及实现,TN820
  10. 基于遗传算法的柑橘图像分割,TP391.41
  11. 基于混合自适应遗传算法的动态网格调度问题研究,TP393.09
  12. 基于遗传—牛顿算法的公交优化调度,TP18
  13. 基于遗传算法优化的BP网络对生物柴油制备工艺的优化,TE667
  14. 基于云理论和蜜蜂进化型遗传算法的纹理合成研究,TP391.41
  15. 基于遗传算法和粗糙集的聚类算法研究,TP18
  16. 海底管道修复连接器的研究,TE973
  17. 基于遗传算法的淠史杭灌区渠系配水优化编组模型的研究,S274
  18. 遗传算法在物流仓储优化中的应用研究,F259.2
  19. 基于遗传算法的矿山资源优化调度模型的研究,O224
  20. 基于粒子群算法的区域水资源优化配置研究,TV213.4
  21. 磁流变阻尼器的力学特性及其在火炮反后坐中的应用研究,TB535.1

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 计算机网络 > 一般性问题 > 计算机网络结构与设计
© 2012 www.xueweilunwen.com