智能优化方法在网格资源调度问题上的分析

《智能优化方法在网格资源调度问题上的分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浙江人学硕．1j学位论文图日录图目录图2．1Minmin算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．16图2．2Minmin算法时间跨度图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．17图2．3最优调度时间跨度图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯18图2．4Minmin算法中任务数与时间跨度问的关系曲线图⋯⋯⋯⋯⋯⋯⋯．19图2．5Maxmin算法中任务数与时问跨度间的关系曲线图⋯⋯⋯⋯⋯⋯⋯20图3．1遗传算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯24图3．2遗传算法中种群个数对解的影响曲线图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯26

2、图3．3遗传算法中交叉率对解的影响曲线图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯27图3．4遗传算法中变异率对解的影响曲线图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯28图3．5遗传算法中任务数与时间跨度关系线图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯29图4．1模拟退火算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯34图4．2模拟退火算法中初始温度对解的影响曲线图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯36图4．3模拟退火算法中任务数与时间跨度的关系曲线图⋯⋯⋯⋯⋯⋯⋯⋯37图5．1捕食搜索流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯39图5．2解空I'日J示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

3、⋯⋯⋯⋯⋯⋯一40图5．3改进后捕食搜索算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．48图5．4改进后捕食搜索算法运行结果图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．49图5．5时间跨度随着资源值增加的变化情况图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯50图5．6几种算法运行结果直方图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一51III浙江人学硕I：学位论文表日录表目录表2．1任务在处理器上执行时间表⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯17表2．2Minmin算法在不同任务数下运算结果表⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．18表2．3Maxmin算法在不同任务数下运算结果表⋯⋯⋯⋯⋯⋯

4、⋯⋯⋯⋯⋯19表3．1不同种群个数条件下遗传算法运算结果表⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯25表3．2不同交叉率下遗传算法运算结果表⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯26表3．3不同变异率下遗传算法运算结果表⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯27表3．4不同任务条件下遗传算法运算结果表⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯28表4．1不同初始温度条件下模拟退火算法运算结果表⋯⋯⋯⋯⋯⋯⋯⋯⋯36表4．2不同任务条件下模拟退火算法运算结果表⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯37表5．1随处理器、任务数变化时，捕食搜索运行结果表⋯⋯⋯⋯⋯⋯⋯⋯43表5．2随处理器、任务数变化时，改进后捕食搜

5、索算法运行结果表⋯⋯⋯49表5．3随着资源值增加时，改进后捕食搜索算法运行结果表⋯⋯⋯⋯⋯⋯50IV浙江火学硕上学位论文第1章绪论1．1课题背景第1章绪论最优化技术是一个较新的科学分支，它所研究的问题是在众多方案中讨论什么样的方案最优，怎样寻找最优方案。线性规划、非线性规划、动态规划、博弈论、存储论、排队论等，这些运筹学的模型的应用使最优化方法的发展达到了一个新的高度，开启了最优化的辉煌时代。自20世纪80年代以来，一些比较新颖的优化算法，如人工神经网络【lJ、遗传算法【2】、模拟退火【31、禁忌搜索[41、蚁群算澍51、粒子群优化算法【6，

6、71及混合优化策略等，通过模拟和揭示某些自然现象或过程而得到发展，其思想和内容涉及数学、物理学、生物进化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路和手段，这些算法独特的优点和机制，引起了在该领域的研究热潮，且在诸多领域得到了成功的应用，在优化领域，由于这些算法构造的直观性与自然机理，因而称作智能优化算法。优化算法在国民经济的各个领域都得到了广泛应用。运输计划、生产计划、设备布置、作业调度、商品定价、路径选择、工作指派等等各种各样的问题都在应用最优化方法。实现生产过程中的最优化，对提高生产效率与效益、节省资源具有重要的作

7、用，同时，优化方法的理论研究对改进算法的性能、拓宽算法应用领域、完善算法体系同样具有重要作用。因此，优化理论与算法的研究是一个同时具有理论意义和实用价值的重要课题。1．1．1优化算法简介传统的优化方法主要有：线性规划的单纯形法，非线性规划的基于梯度的各种迭代算法等。这类算法一般包括如下3个基本步骤：1．选择一个初始解；浙江人学硕f?学位论文第l章绪论2．判断停止条件是否满足；3．向改进方向移动。传统的优化方法的这种计算框架也给它带来了一些较难克服的局限性。这些局限性主要表现在以下几个方面：1．单点运算限制了计算效率的提高；传统的优化方法一般是

8、从一个初始解出发，在每次迭代过程中通常只是对一个点进行运算，这种方法很难发挥现代计算机较高的计算能力，限制了算法的计算速度和求解大规模问题的能力。2．向改进方向移动