云计算环境下基于改进遗传算法的任务调度算法

云计算环境下的并行计算任务调度算法研究随着云计算技术的广泛应用，计算资源的管理和调度问题变得尤为重要。

在云计算环境下，计算资源的动态分配和任务调度是实现高效利用资源的关键。

而并行计算任务调度算法则是其中的核心问题。

本文将对云计算环境下的并行计算任务调度算法进行探讨与研究。

一、云计算环境下的并行计算任务调度背景随着云计算技术的快速发展，云计算平台成为了大规模科学计算和商业应用的重要基础设施。

在云计算环境下，资源虚拟化技术可以将一组物理资源抽象为多个虚拟资源，并动态地对其进行管理和调度。

虚拟化技术的出现使得云计算平台可以弹性地为用户提供不同量级的计算资源，这些资源可以通过云计算平台进行快速分配和调度。

针对云计算平台中的并行计算任务调度问题，任务调度算法是实现资源高效利用和满足用户需求的关键。

二、并行计算任务调度算法研究现状在现有的并行计算任务调度算法中，主要的思路分为三类：贪心算法、遗传算法和粒子群算法。

1. 贪心算法贪心算法是最基本、最简单的调度算法。

它通过不断地选择当前最优的任务和最合适的资源进行执行，来实现任务的尽早完成。

贪心算法的优点在于计算复杂度低，且对于有确定性的特定情况下表现出良好的效果。

但是贪心算法会出现局部最优解，容易造成全局最优解的缺失。

2. 遗传算法遗传算法是一种模拟进化过程的全局搜索算法。

它将各个可行解表示为基因，通过交叉、变异等操作来进行群体进化。

遗传算法可以用于解决复杂的优化问题，其搜索效率高、易于编程和实现。

但是在一定程度上会受到参数的选择和搜索空间的大小的影响。

3. 粒子群算法粒子群算法是一种基于群体智能的优化算法。

它通过引入群体智能算法的概念，在人工群体中模拟自然界中的鸟群或鱼群的行为，通过不断地调整各个“粒子”的位置和速度来达到全局最优解。

粒子群算法具有全局优化的能力，且易于实现。

但是算法极易受到初始化参数、搜索空间的大小和算法参数的影响。

三、并行计算任务调度算法研究展望针对云计算环境下的并行计算任务调度问题，当前的研究重点主要集中在以下几个方面：1. 任务预测模型的建立云计算环境下的任务调度必须考虑任务动态性的影响。

云计算环境下的虚拟机动态调度算法研究第一章绪论随着云计算技术的快速发展，在云计算环境中进行动态调度是非常重要的。

虚拟机是云环境中最常见的一种计算资源，虚拟机的有效调度能够提高整个云计算平台的可用性和系统资源利用率。

本文将从虚拟机动态调度算法的角度出发，探讨云计算环境下如何有效地进行虚拟机动态调度。

第二章虚拟机动态调度的相关算法2.1 基于遗传算法的虚拟机动态调度遗传算法是一种优化算法，通过模仿自然界进化的过程来寻找最优解。

基于遗传算法的虚拟机动态调度方法通过优化虚拟机分配和调度策略来提高云计算平台的资源利用率和性能。

该方法将虚拟机作为遗传算法中的个体进行管理和优化，通过交叉、突变等遗传操作生成新一代个体，使虚拟机分配达到最优解。

2.2 基于粒子群算法的虚拟机动态调度粒子群算法是一种优化算法，通过模拟鸟群行为来寻找最优解。

基于粒子群算法的虚拟机动态调度方法将虚拟机作为粒子进行管理和优化，通过粒子的移动和角速度来寻找最优解。

该方法在实现简单的同时，能够优化虚拟机的分配策略和调度策略，并能够快速响应云计算平台的资源变化。

2.3 基于模拟退火算法的虚拟机动态调度模拟退火算法是一种随机优化算法，它通过接受恶化解的策略来避免局部最优解。

基于模拟退火算法的虚拟机动态调度方法通过在虚拟机调度中引入退火启发策略，寻找最优解。

该方法能够应对虚拟机调度过程中的复杂环境变化，提高云计算平台的系统性能。

2.4 基于蚁群算法的虚拟机动态调度蚁群算法是一种模仿蚂蚁行为来寻找最优解的优化算法。

基于蚁群算法的虚拟机动态调度方法将虚拟机分配视为一个蚁群在搜索最优解的过程，通过信息素和启发函数实现虚拟机分配和调度。

该方法能够自适应处理动态变化的云计算环境，实现最优化的虚拟机分配。

第三章实验方法和结果为了验证各种虚拟机动态调度算法的有效性，在本文中建立了模拟云环境。

使用各种不同的虚拟机调度算法进行手机和实验，从而得出各种算法的性能比较结果。

基于遗传算法的云计算任务调度策略刘宇光;崔倩;张淼【期刊名称】《信息技术》【年(卷),期】2017(000)008【摘要】The research on task scheduling in cloud computing is always the focus of many scholars.When the traditional genetic algorithm is used to perform task scheduling,its convergence speed is slow and evolutionary rate is not high.It is difficult to achieve satisfactory results.The gene space balance strategy is used to improve the population initialization step of genetic algorithm.The strategy increases the diversity of genes and effectively improves the low evolution efficiency of traditional genetic algorithm and the convergence speed.%云计算服务中的任务调度问题一直是学者们的研究重点.使用传统遗传算法进行任务调度时,算法的收敛速度慢、进化速率不高,很难达到理想的结果.文中使用基因空间均匀分布策略对遗传算法初始化种群步骤进行了优化,提高了基因的多样性,有效地改善了传统遗传算法进化效率低的问题,提升了收敛速度.【总页数】4页(P177-180)【作者】刘宇光;崔倩;张淼【作者单位】北京教育网络和信息中心系统管理部,北京100035;北京教育网络和信息中心系统管理部,北京100035;北京科技大学,北京100083【正文语种】中文【中图分类】TP301.6【相关文献】1.基于动态遗传算法的云计算任务节能调度策略研究 [J], 钟潇柔;翟健宏2.基于动态遗传算法的云计算任务节能调度策略研究 [J], 钟潇柔;翟健宏;3.基于遗传算法的云计算资源调度策略研究 [J], 徐文忠;彭志平;左敬龙4.基于改进萤火虫算法的云计算任务调度策略 [J], 朱利华;朱玲玲5.基于QoS和服务收益的云计算任务调度策略研究 [J], 陈为满;贺宗梅;陈畅因版权原因，仅展示原文概要，查看原文内容请购买。

大规模云计算环境下的任务调度优化算法随着云计算技术的快速发展，云计算环境已成为许多企业、组织和个人处理海量数据的首选方案。

然而，在这种环境下，如何调度和分配大量任务成为了一个挑战。

如何优化任务调度算法，最大限度地提高计算资源的利用率和系统的性能，是实现高效云计算的重要一环。

大规模云计算环境下的任务调度算法需要考虑多种因素，如任务类型、执行时间、资源需求以及系统负载等。

其中最重要的是，任务调度算法必须能够自适应地根据当前系统负载情况合理地对任务进行调度和分配。

现有的任务调度算法可以分为集中式调度算法和分布式调度算法两类。

其中，集中式调度算法通常由中央调度器来负责任务的调度和分配。

它的优点是调度过程相对简单，容易实现，但同时也有其局限性，如单点故障、可扩展性差等问题。

而分布式调度算法则通过将任务和资源分散到不同的节点上进行调度和分配，可以有效避免这些问题，同时也可以更好地适应大规模的云计算环境。

在分布式调度算法中，最常用的是基于任务的动态调度算法和基于资源管理的动态调度算法。

其中，基于任务的动态调度算法可以根据任务的类型、执行时间和资源需求等信息来判断任务的优先级和调度顺序。

而基于资源管理的动态调度算法则是通过对云计算资源的实时监测来判断任务调度的优先级和调度顺序，以最大限度地提高资源的利用效率。

在实际应用中，任务调度算法的优化需要综合考虑多方面因素。

例如，如何在保障任务完成的同时，更好地利用云计算资源，如何有效地平衡任务的负载，提高系统的稳定性和可靠性等。

这些问题在实践中都需要仔细思考和解决。

总之，大规模云计算环境下的任务调度优化算法是实现高效云计算的重要一环。

在未来的发展中，我们需要不断探索和改进任务调度算法，以更好地满足不同场景下的需求，推动云计算技术的创新和发展。

考虑资源约束的云计算资源调度算法云计算技术的快速发展使得大量的数据可以被高效地处理和存储，这也促进了云计算资源调度算法的发展。

云计算资源调度算法运用于数据中心，以提高服务器资源的利用率，减少资源浪费，实现数据中心的经济性和高效性。

本文将从资源约束的角度，介绍几种常见的云计算资源调度算法。

一、基于遗传算法的云计算资源调度算法遗传算法是模拟生物进化过程，通过自然选择、基因重组等方式对种群进行优化，从而获得更好的解决方案。

云计算资源调度问题可以被视为一个优化问题，在资源约束的限制下，实现资源分配和任务调度的最佳组合。

基于遗传算法的云计算资源调度算法可以在不断迭代中逐渐优化种群，获得最优解。

遗传算法天然具有不断优化、适应性强等特点，可以较好地处理资源约束的云计算资源调度问题。

二、基于模拟退火算法的云计算资源调度算法模拟退火算法是一种通过模拟金属物质的退火过程来求解复杂优化问题的算法。

模拟退火算法通过一种接受差解的策略，使之有机会跳出局部极小点，并且能够在全局上进行搜索。

云计算资源调度问题中涉及到的约束条件较多，通过模拟退火算法可以有效解决复杂度较高的问题，得到较好的资源调度方案。

三、基于禁忌搜索算法的云计算资源调度算法禁忌搜索算法利用一个禁忌表来避免搜索过程中出现重复状态，从而避免局部最优解。

在云计算资源调度问题中，禁忌搜索算法可以有效地避免出现重复状态以及在搜索过程中避免落入局部最优解。

基于禁忌搜索算法的云计算资源调度算法可以提高搜索的效率和准确性。

四、基于粒子群优化算法的云计算资源调度算法粒子群优化算法是受群体行为中的群体智慧启发而发展起来的一种优化方法。

在粒子群优化算法中，每个群体中的个体通过学习其它个体的经验来更新自身状态，从而得到最优解。

粒子群优化算法在资源调度问题中，可以充分利用群体行为，从而达到更好的资源调度效果。

五、基于混合遗传算法和粒子群优化算法的云计算资源调度算法混合遗传算法和粒子群优化算法分别具有各自的优点，混合这两种算法可以充分利用它们的优势。

遗传算法在云计算应用实例-公交车智能调度一、应用实例背景城市公交车辆运营调度的任务就是有效管理和合理分配有限车辆资源, 调整供需平衡, 以解决供需矛盾, 达到所求的目标最佳, 而调度问题本身的组合优化特征存在近似复杂性, 实际调度系统所采用的数学模型都对运行环境作了大大简化, 因此, 仅靠已有的寻优改进还远远不能满足运营调度方案的实时性和有效性要求。

文献[ 3- 6] 的研究都未能从系统角度考虑公交调度系统的整体优化问题。

公交时刻表的生成与车辆调度之间存在着有机联系, 因此, 虽然按照这些既有的模型算法可以得出上述公交调度问题较好的解决方案, 却不能够保证系统的解决方案从总体上讲是最优的。

本文将云模型理论与遗传算法( genetic algo rithm, GA) 相结合, 充分利用云模型云滴的随机性和稳定倾向性特点, 在GA 中运用云模型理论进行交叉、变异优化操作, 不但能够维持GA 种群的多样性, 而且在寻优能力上也得到提高, 改善了GA 的优化性能及其鲁棒性, 从而可提高公交车辆运营调度的效率与车辆调度的稳定性。

二、算法简介云模型是一个遵循正态分布规律并具有稳定倾向的随机数集, 其三个数字特征用期望值Ex 、熵En 和超熵He 来表征, 反映了定性概念的整体GA 是一种求解问题的高效并行全局搜索算法。

目前研究发现, 在调整交叉概率pc和变异概率pm 的过程中存在许多模糊概念和信息, 这一特点决定了可以用模糊理论工具来获取和处理这些不确定信息。

本文充分利用云模型云滴的随机性和稳定倾向性特点, 将云模型的Y 条件云生成算法实现交叉操作, 基本云生成算法实现变异操作, 使概率值既具有传统的趋势性, 满足快速寻优能力, 又具有随机性, 实现p c 和p m 的自适应调整, 从而提高了避免陷入局部最优的能力, 构成了全新的云遗传算法三、应用实验实例3.1公交车辆调度问题公交车辆运输调度问题就是指在固定行驶线路上, 根据不同时段、依照一定的先序关系, 合理编排运输车辆运行的作业形式, 达到供需平衡, 满足性能指标。

改进遗传算法在云计算资源优化调度中的应用
鞠成恩;赵晓侠;王明兴;问尤龙
【期刊名称】《软件导刊》
【年(卷),期】2018(017)004
【摘要】在大量用户请求云计算资源服务时,如何合理组织资源和任务调度是云计算的关键技术之一.如果分配调度方法不合理,就可能产生用户需求得不到满足和资源使用不均衡等问题.在传统遗传算法基础上,将模拟退火算法与遗传算法相融合,扩大遗传算法的搜索领域,解决遗传算法早熟收敛现象,使云资源分配更加合理,以提高云资源利用率.在CloudSim平台上进行仿真,结果表明该方式能较好地对云计算资源进行分配,在能耗、带宽等约束条件下达到云资源最优调度的目的.
【总页数】3页(P45-46,50)
【作者】鞠成恩;赵晓侠;王明兴;问尤龙
【作者单位】昆明理工大学信息工程与自动化学院 ,云南昆明650500;昆明理工大学信息工程与自动化学院 ,云南昆明650500;昆明理工大学信息工程与自动化学院 ,云南昆明650500;昆明理工大学信息工程与自动化学院 ,云南昆明650500
【正文语种】中文
【中图分类】TP312
【相关文献】
1.改进的多目标量子遗传算法在南水北调东线工程江苏段水资源优化调度中的应用[J], 方国华;郭玉雪;闻昕;黄显峰
2.云计算环境中优化混合遗传算法的资源调度研究 [J], 王静;陈家琪
3.云计算中基于改进遗传算法的多目标优化调度 [J], 王昱; 左利云
4.云计算中基于改进遗传算法的多目标优化调度 [J], 王昱; 左利云
5.改进遗传算法在云计算资源优化调度中的应用 [J], 鞠成恩[1];赵晓侠[1];王明兴[1];问尤龙[1]
因版权原因，仅展示原文概要，查看原文内容请购买。

基于改进GA的云计算任务调度策略任金霞;刘敏【摘要】针对传统遗传算法在云计算任务调度过程中的收敛速度慢和易早熟等问题,提出了一种基于遗传优化算法的双适应度函数改进算法.该算法采用任务完成时间和任务完成成本为双适应度函数,引入个体相似度概念来提高种群质量;采用并列选择法进行选择操作,并且采用自适应规则约束交叉和变异操作,提高种群个体质量,加速进化策略可以有效地避免早熟.结果表明,改进的遗传算法有效地加快了云任务作业调度的收敛速度,并改善了易早熟等现象.【期刊名称】《沈阳工业大学学报》【年(卷),期】2019(041)003【总页数】6页(P320-325)【关键词】遗传算法;双适应度函数;并列选择法;收敛速度;易早熟;自适应规则;个体相似度;加速进化【作者】任金霞;刘敏【作者单位】江西理工大学电气工程与自动化学院, 江西赣州 341000;江西理工大学电气工程与自动化学院, 江西赣州 341000【正文语种】中文【中图分类】TP393随着计算机技术的迅猛发展，云计算技术已成为现今社会的一个研究热点和重点.云计算是在分布式计算、网格计算和并行计算等基础上发展起来的一种全新的大规模计算模式，利用虚拟技术和高速网络技术来解决大规模的大数据处理问题，有很多企业做出较大投入且获得很好的成果，如亚马逊的‘弹性云’、IBM的‘蓝云’、Google的超大搜索引擎和微软的‘Windows Azure’等.随着互联网技术的发展，互联网数据量会越来越大，对云计算技术的要求也越来越高，用户要求以最小的时间跨度来完成任务，同时企业要求尽可能带来盈利，关于云计算任务调度策略的研究成为研究重点，现在较常用的云任务调度策略主要有蚁群算法[1]、遗传算法[2]和粒子群算法[3]等启发式仿生算法及其改进算法，Min-min算法[4]等非仿生式算法及其改进算法.企业型云计算是以盈利为目的，所以很多文献的任务调度策略中心主要是以任务完成时间和任务完成成本为优化目标.文献[5]为避免早熟现象等问题提出了一种基于负载均衡和任务时间的双适应度函数改进遗传算法；文献[6]针对传统遗传算法迭代次数多和耗时久的问题提出了一种以执行时间和执行费用为优化目标的改进遗传算法；文献[7]提出了一种考虑时间和成本约束的改进遗传算法.但是，这些文献针对未成熟收敛现象均未提出较好的改进办法，在遗传算法后期可能会出现总是淘汰接近最优解的个体或者所有个体陷入同一极值而终止算法的情况，无法达到降低任务完成时间和成本的优化目标.本文提出了基于任务完成时间和任务完成成本的双适应度函数的改进遗传算法(time and cost genetic algorithm，TCGA)，引入个体相似度概念和采用并列选择法进行选择遗传操作，尽可能保证种群多样性，同时在算法后期采用加速收敛策略加快算法的收敛速度.1 云计算任务调度现今社会上采用的云计算编程模式是1995年由Google公司提出的Map/Reduce模式，这种模式是把云任务分成若干个子任务，各子任务按要求随机分配给虚拟机上的资源计算节点并执行，最后将结果进行整合处理输出，各任务或子任务之间是相互独立的，在虚拟机上进行并行运算.这样可以减少任务执行时间且降低成本损耗，但各虚拟资源计算节点的任务处理性能有差异，所以各子任务完成时间不同，同时各虚拟资源计算节点完成任务的单位成本不同，产生的成本消耗也不同.各虚拟资源计算节点单位时间完成单位任务所产生的成本损耗为单位成本.云计算采用的是按需收费、即时付费的资源服务模式，一般满足以下几个条件：1) 为了有利于虚拟机的任务执行，云任务会被分解成若干个大小均匀的子任务，子任务会被随机地分配在不同的虚拟资源上执行；2) 每个子任务在虚拟资源计算节点上的执行时间是可监控的、可计算的；3) 每个虚拟资源计算节点的单位成本是可估算的、已知的.每个计算节点完成的子任务所用的时间可表示为etcij，etcij为资源节点j执行子任务i所消耗的时间，costij为资源节点j执行子任务i的成本消耗，costj为资源节点j的单位成本，则有costij=costj·etcij.设云任务有TASK个，子任务数为虚拟资源数为n，任务执行时间为etcij，则有(1)式中：task(k)_lengthi为云任务k中的子任务i的长度，i∈{1，2，…，m}；mipsj为虚拟资源j的处理性能，j∈{1，2，…，n}.云计算环境下的子任务在虚拟资源中进行计算时是并行独立完成的，所以子任务在各虚拟资源中执行时间的最大值为云任务调度的执行时间花费ExecuteTime，任务完成时间CompleteTime为任务执行时间与任务传输时间之和，云任务在各虚拟资源的执行成本花费ExcuteCost与传输成本花费求和即为任务调度总成本花费CompleteCost.云任务k的执行时间为(j∈[1，n])(2)云任务在虚拟资源上的传输时间为(3)式中，transj为虚拟资源j的传输性能.任务完成时间为任务执行时间与任务传输时间之和，即CompleteTimek=ExecuteTimek+ttkj(4)云任务k的总成本花费为任务执行成本与传输成本之和，即(5)式中，costtj为虚拟资源j的传输成本.2 改进遗传算法2.1 遗传算法遗传算法是1967年美国Michigan大学Holland教授和他的学生们受生物模拟技术启发，提出的一种基于生物基因遗传和进化机制的自适应概率优化算法.遗传算法具有高效性、高鲁棒性和实用性，发展极为迅速，自提出后，在工程技术、科学计算和社会经济等方面被大面积的引用吸收，引起了全世界范围有关学者的高度重视[8-11].遗传算法的优点很多，但是经过多年的发展和完善，依然存在许多问题未得到解决，例如：1) 遗传算法易陷入早熟中，迄今为止没有得到很好的解决办法；2) 在遗传算法后期，最优解会出现左右摆动情况，导致收敛速度变慢.2.2 编码与解码编码是遗传算法中的一个重要步骤，也是一个首要解决的问题，与编码相对应的则是解码.遗传算法的常用编码方式较多，可分为二进制编码、浮点编码和符号编码三大类，又可分为直接编码方式和间接编码方式，采用不同的编码方式对遗传算法的执行结果有不同效果.本文采用的是资源任务编码方式，这种编码方式较为直观，操作简单易行，易于理解，不易出错，且染色体长度即基因的数量为子任务数量，每个子任务对应一个被分配到的资源.如染色体{2，3，2，1，4，3，1，2，4，3}，10个子任务分配给4个虚拟资源，编号为1、2、3和4的虚拟资源上的子任务数分别为2、3、3和2，即J1：{4，7}，J2：{1，3，8}，J3：{2，6，10}，J4：{5，9}，其中，J为虚拟资源，括号内为子任务在染色体中的基因排列位置.图1为任务资源映射关系图.图1 任务资源映射关系Fig.1 Task-resource mapping relationship若长度为l的染色体为{1，3，4，2，3，m-2，1，3，…，m，m-1}，则任务与虚拟资源的映射关系如表1所示.表1 映射关系Tab.1 Mapping relationship资源ID任务数任务ID121,7214332,5,8413︙︙︙m-11lm1l-12.3 适应度函数设计适应度函数值在一定程度上决定了个体被选作为父代遗传到下一代的概率，适应度值较大的遗传到下一代的概率较大，适应度值较小的遗传到下一代的概率较小，所以适应度函数的选择很关键，本文选择的适应度函数是任务完成时间适应度函数和任务完成成本适应度函数.时间适应度函数为(6)(7)式中：ulb为任务平衡负载因子，表示虚拟资源的利用率情况，ulb越大表示虚拟资源利用率越高；CompleteTimemax为任务完成时间的最大值.成本适应度函数为(8)任务完成所花费时间越少的分配策略越接近最优解，运行算法所需的成本代价越低其适应度值越大.3 遗传操作3.1 个体相似度传统遗传算法执行一段时间后，个体之间的相似性增大，易陷入局部最优中，本文提出个体相似度的概念来约束个体之间的相似性，加快算法的收敛速度，避免算法陷入局部最优的情况.个体染色体的长度为l，虚拟资源数为n，两个个体之间的海明码距为(9)其中，(10)相似度为(11)3.2 选择操作选择操作是遗传算法的基本操作，使用比例算子进行运算，选择操作的目的是为了从当前种群中选出优秀的个体，使其有机会作为父体把优良的基因通过繁殖遗传给下一代.为了保证种群个体多样性，个体相似度大于90%的保留适应度值大的个体，适应度值小的个体被淘汰.本文主要从时间适应度函数和成本适应度函数来考虑，个体的适应度值越大，被选中作为父代繁殖遗传的可能性就越大，反之越小.种群中个体被选中的概率为(12)式中，fiti为个体i的适应度函数值.本文采用最优保存策略进行选择操作，在选择操作时，把种群中所有个体的适应度函数值按照从大到小的顺序排列，首先把适应度值最大的0.5%的个体去掉，再把剩下的前10%的个体直接入选到子代种群中，剩余的个体通过轮盘赌算法进行个体选择.本文采用并列选择法对时间适应度值和成本适应度值进行选择，即按上述选择方法分别选出合适时间适应度值的个体和成本适应度值的个体，再与通过交叉和变异遗传操作生成新的个体共同组成新的子代种群.在选择这个遗传操作过程中可能会淘汰一些染色体，为了保证种群的规模，每次遗传操作开始前添加随机生成的若干个个体保持种群规模不变.3.3 交叉和变异操作交叉操作是按概率从种群中选出两个个体交换彼此的某个或某些位产生新的子代，交叉操作的方式有很多，如单点交叉、均匀交叉和多点交叉等.变异操作是以较小的概率将个体的某个或某些位值变异为其他等位基因生成新的个体，变异方式有基本位变异和均匀变异等.交叉和变异操作决定了遗传算法的寻优搜索能力.交叉概率公式为(13)式中：fitmax为种群中的最大适应度值；fitavg为平均适应度值；fit1和fit2为种群中要交叉的个体适应度值；k1为交叉概率调节常数；k2为交叉概率常数.当交叉个体适应度值较大时(fiti≥fitavg)，这时可以缩小个体交叉概率，防止较优的个体被破坏；当适应度值较小时，扩大个体交叉概率，期望可以繁殖出新的较优个体.为了提高局部寻优能力，加快收敛速度，使用变异算子微调个体的某个或某些位，变异概率公式为(14)式中：fiti为种群中要变异的个体的适应度值；k3为变异概率调节常数；k4为变异概率常数.当要变异个体适应度值较大时(fiti≥fitavg)，适应度值越大，变异的可能性越小，在一定程度上防止较优个体被破坏.在遗传算法后期会出现适应度值很集中的情况，这种情况很大程度上降低了算法的收敛速度.本文提出加速收敛策略[12]，当种群个体适应度值的最大值和最小值差与适应度值平均值的比值ω小于收敛阈值θ时，调节交叉概率调节常数k1和变异概率调节常数k3，使得个体的交叉和变异概率变大，加快局部搜索速度，提高算法的收敛速度.3.4 种群初始化设种群的大小规模为S，云任务总数为TASK，子任务数为m，虚拟资源数为n，则种群初始化可描述为：由系统随机生成S个长度为m的染色体，基因值为[1，n]之间的随机数.3.5 算法流程图2为算法流程图.由系统随机生成初始种群，计算种群中个体的适应度值，并按遗传操作进行执行寻找最优解，步骤如下：1) 种群初始化.系统随机生成大小规模为S的初始种群.2) 终止算法条件.算法迭代次数是否达到最大值或找到最优解，是则终止算法；否则继续执行.3) 选择操作.计算种群个体适应度函数值，排列后通过最优保存策略选取前10%为下一代种群个体，采用轮盘赌方式对剩余个体进行选择操作.4) 交叉操作.随机选取两个个体进行交叉操作生成新种群的个体.图2 算法流程图Fig.2 Flow chart of algorithm5) 变异操作.随机选择一个个体进行变异操作生成新种群的个体.6) 对新生成种群个体进行判断筛选是否找到最优解，有则输出结果；无则跳转到步骤2)中.4 仿真实验结果分析本文采用墨尔本大学Buyya教授领导开发的CloudSim仿真模拟器对算法进行仿真模拟实验，并对实验结果进行比较分析.将本文方法与遗传算法、文献[5]中的SAIGA算法进行实验对比，分析比较各算法在不同情况下的任务完成时间、任务完成成本和收敛结果.对算法中的各参数取值进行初始化，如表2所示.表2 参数初始化Tab.2 Parameter initialization参数名称取值交叉概率调节常数k15.00交叉概率常数k20.80变异概率调节常数k35.00变异概率常数k40.08收敛阈值θ0.01算法初始条件：种群规模S取值为30，子任务数m取值为1 000，虚拟资源n取值为10，虚拟资源的单位成本costj和传输成本costtj由系统随机生成，算法的最大迭代次数设置为100.实验结果如图3～5所示.图3 任务完成时间对比Fig.3 Comparison of task completion time图3中总任务数量为1 000个，从图3中可以看出，在相同任务数量情况下，分别运行遗传算法、TCGA算法和SAIGA算法，在迭代次数较少时，3种算法的任务完成时间各不相同，TCGA算法花费时间最少，遗传算法花费时间最多，但是3种算法花费的时间相差较小；随着迭代次数的增多，3种算法花费的时间差距越来越大，在最大迭代次数的情况下，TCGA算法的任务完成时间比遗传算法和SAIGA算法分别降低了13%和8%.图4 任务完成成本对比Fig.4 Comparison of task completion cost图5 收敛结果对比Fig.5 Comparison of convergence results图4中总任务数量为1 000个，从图4中可以看出，TCGA算法、遗传算法和SAIGA算法在算法初期，任务完成成本相差不大；随着算法迭代次数的增多，3种算法的任务完成成本会降低且降低的程度各不相同，算法之间的任务完成成本差距变大，TCGA算法的任务完成成本相比较于遗传算法和SAIGA算法分别降低了4%和3%.图5中总任务数量为1 000个，从图5中可以看出，TCGA算法、遗传算法和SAIGA算法的收敛速度各不相同，随着迭代次数的增加，收敛所需时间差距变大，遗传算法的收敛速度最慢，TCGA算法的收敛速度更快，寻优时间最短.综上分析可知，本文提出的双适应度函数改进遗传算法的任务完成时间更短，成本更低，收敛速度更快，寻优能力更强，能较好地完成云任务调度问题.5 结论云计算调度优化策略通常是以任务完成时间和任务完成成本为优化目标，本文提出并列选择法根据适应度函数值确定选择概率完成选择操作，把任务完成时间和任务完成成本作同等地位来处理云计算任务调度的优化问题，这样能根据各自优化目标函数选出符合要求的个体，本文算法没有考虑其他因素对云任务调度过程的影响，如网络服务质量等，下一步讨论研究需要把这些因素考虑在内.参考文献( References) :【相关文献】[1]聂清彬，蔡婷，王宁.改进的蚁群算法在云计算资源调度中的应用[J].计算机工程与设计，2016，37(8)：2016-2020.(NIE Qing-bin，CAI Ting，WANG Ning.Application of improved ant colony algorithm in resource allocation of cloud computing [J].Computer Engineering and Design，2016，37(8)：2016-2020.)[2]屈迟文.基于改进遗传算法的云计算任务调度研究 [J].世界科技研究与发展，2013，35(5)：616-619.(QU Chi-wen.Research on cloud computing task scheduling based on improved genetic algorithm [J].World Sci-Tech R & D，2013，35(5)：616-619.)[3]赵莉.基于改进量子粒子群算法的云计算资源调度 [J].南京理工大学学报，2016，40(2)：223-228.(ZHAO Li.Cloud computing research scheduling based on improved quantum particle swarm optimization algorithm [J].Journal of Nanjing University of Science and Technology，2016，40(2)：223-228.)[4]郭平，李涛，李琪.一种云计算环境下的负载调度算法 [J].系统工程理论与实践，2014，34(增刊1)：269-275.(GUO Ping，LI Tao，LI Qi.A scheduling strategy on load balancing in cloud computing [J].Systems Engineering Theory & Practice，2014，34(Sup1)：269-275.)[5]刘峰，毕利，杨军.一种用于云计算资源调度的改进遗传算法 [J].计算机测量与控制，2016，24(5)：202-206.(LIU Feng，BI Li，YANG Jun.An improved genetic algorithm for cloud computing resource scheduling [J].Computer Measurement & Control，2016，24(5)：202-206.)[6]陈晓燕，姚高伟，张鲲，等.一种改进的遗传算法在云计算中的应用 [J].信阳师范学院学报(自然科学版)，2015，28(3)：438-441.(CHEN Xiao-yan，YAO Gao-wei，ZHANG Kun，et al.Application of an improved genetic algorithm in cloud computing [J].Journal of Xinyang Normal University(Natural Science Edition)，2015，28(3)：438-441.)[7]朱宗斌，杜中军.基于改进GA的云计算任务调度算法 [J].计算机工程与应用，2013，49(5)：77-80.(ZHU Zong-bin，DU Zhong-jun.Improved GA-based task scheduling algorithm in cloud computing [J].Computer Engineering and Application，2013，49(5)：77-80.)[8]孙晓燕，陈姗姗，巩敦卫，等.基于区间适应值交互式遗传算法的加权多输出高斯过程代理模型[J].自动化学报，2014，40(2)：172-184.(SUN Xiao-yan，CHEN Shan-shan，GONG Dun-wei，et al.Weighted multi-output Gaussian process-based surrogate of interactive genetic algorithm with indivi-dual’sinterval fitness [J].Acta Automatica Sinica，2014，40(2)：172-184.)[9]袁满，刘耀林.基于多智能体遗传算法的土地利用优化配置 [J].农业工程学报，2014，30(1)：191-199.(YUAN Man，LIU nd use optimization allocation based on multi-agent genetic algorithm [J].Transactions of the Chinese Society of Agricultural Engineering，2014，30(1)：191-199.)[10]胡瑾，何东健，任静，等.基于遗传算法的番茄幼苗光合作用优化调控模型 [J].农业工程学报，2014，30(17)：220-227.(HU Jin，HE Dong-jian，REN Jing，et al.Optimal re-gulation model of tomato seedling’s photosynthesis based on genetic algorithm [J].Transactions of the Chinese Society of Agricultural Engineering，2014，30(17)：220-227.)[11]马小雨.基于自适应遗传算法的DFB激光器模糊PID温控系统 [J].沈阳工业大学学报，2017，39(4)：454-458.(MA Xiao-yu.Fuzzy PID temperature control system for DFB laser based on adaptive genetic algorithm [J].Journal of Shenyang University of Technology，2017，39(4)：454-458.)[12]袁雪莉，钟明洋.改进遗传算法的并行任务调度 [J].计算机工程与应用，2011，47(10)：56-59. (YUAN Xue-li，ZHONG Ming-yang.Parallel task scheduling algorithm using improved genetic algorithm [J].Computer Engineering and Applications，2011，47(10)：56-59.)。

遗传算法在云计算任务调度算法中的应用研究
郑爱媛
【期刊名称】《西安文理学院学报（自然科学版）》
【年(卷),期】2016(019)001
【摘要】介绍云计算技术,分析了云计算环境下任务调度情况,给出了云计算任务调度中基于用户满意度的遗传算法详细设计,该详细设计中重点叙述了编码、适应度函数设计、交叉等遗传算法实现的主要过程.
【总页数】4页(P23-26)
【作者】郑爱媛
【作者单位】福建商业高等专科学校信息管理工程系,福州350012
【正文语种】中文
【中图分类】TP393
【相关文献】
1.基于混合遗传算法的云计算任务节能调度算法 [J], 吴世山;翟健宏
2.基于混合遗传算法的云计算任务节能调度算法 [J], 吴世山;翟健宏;
3.基于改进遗传算法的云计算任务调度算法 [J], 胡艳华;唐新来
4.云计算中一种基于遗传算法与效益驱动的任务调度算法 [J], 戴艳红
5.云计算环境下基于遗传算法的优化的多任务调度算法 [J], 孙政;
因版权原因，仅展示原文概要，查看原文内容请购买。

Hadoop 中任务调度算法的改进苏小会，何婧媛（西安工业大学计算机科学与工程学院，陕西西安710032）摘要：针对Hadoop0.20.0中任务调度算法存在的不足，提出一种基于改进遗传算法（IGA ）的任务调度算法。

IGA 算法对初始化种群、交叉和变异操作进行了一些改进，并引入了最优保留策略和加速进化策略。

通过仿真实验将此算法与Hadoop 现有算法进行比较，实验结果表明，此算法优于Hadoop 现有算法，是一种有效的任务调度算法。

关键词：Hadoop 平台；任务调度；遗传算法；加速进化策略中图分类号：TP302文献标识码：A文章编号：1674－6236（2012）22-0033-04Improvement of task scheduling algorithm in hadoopSU Xiao -hui ，HE Jing -yuan（School of Computer Science and Engineering ，Xi ’an Technological University ，Xi ’an 710032，China ）Abstract:A task scheduling algorithm based on improved genetic algorithm （IGA ）was brought up for the deficiences of the task scheduling algorithms in Hadoop0.20.0.IGA algorithm improved the original colony is initialized and crossover and mutation operation ，and introduces retention optimal strategy and evolution acceleration strategy.There is a contrast between IGA and existing algorithm in Hadoop through simulation experiment ，and the result is:the IGA is better ，it is an effective task scheduling algorithm.Key words:hadoop platform ；task scheduling ；genetic algorithm ；evolution acceleration strategy收稿日期：2012-07-23稿件编号：201207143作者简介：苏小会（1970—），男，陕西武功人，硕士，副教授。

基于改进模拟退火算法的云计算任务调度研究云计算技术的出现，推动了互联网时代的发展。

云计算的核心是对海量数据的处理和计算资源的管理。

而云计算任务调度具有决定性的作用，其中改进模拟退火算法成为研究者广泛关注的热点。

本文将从云计算任务调度、模拟退火算法的基本思想以及改进模拟退火算法的实现等方面进行论述。

一、云计算任务调度概述云计算任务调度是指将用户提交的任务分配给云计算环境中的各种虚拟机执行的过程。

调度方案的好坏，直接影响到云计算环境的性能和用户的体验。

一般来说，做出好的调度方案需要考虑以下几个方面：1.任务分布情况：互联网的大数据背景下，各种业务的任务量庞大，任务会在不同的时间和地点产生，任务分布情况不可测。

2.虚拟机配置情况：虚拟机的性能和配置各不相同，因此需要对每台虚拟机进行分析，以便在任务调度的过程中选择合适的机器。

3.网络拓扑和数据传输：数据传输的带宽和速度往往影响任务调度的效率，而虚拟机之间的交互数据流量越多，每个虚拟机的操作就越容易发生阻塞。

基于上述方面提出的要求，实际任务调度是一种NP难问题，以往常用的算法如遗传算法、禁忌搜索、粒子群优化算法、蚁群算法等往往需要极长的计算时间，并且结果不一定稳定或者最优。

因此，模拟退火算法在云计算任务调度过程中的作用引起了学者们的关注。

二、模拟退火算法基本思想模拟退火算法（SA）是一种近似算法。

其作用是在最小化一个连续函数的过程中，不会被绝对最小值“绕过去”，也就是说，SA不会固定在函数的极小值处，而是“跳出去”从而发现其它最小值。

其大致流程如下：1. 初始化一个初温（t）高一些的值，同时设定一个目标函数。

2. 不断重复以下步骤直到达到一定的停顿时间：在选定的基础点周围以随机方式生成新的相邻解；计算新解和原解之间的目标函数差值dE；以Metropolis准则对该解进行接受或拒绝决策。

3. 温度不断降低，以降低接受劣解的概率，最终随着温度降低，算法的搜索范围逐渐减小，同时进一步接近最优解。

基于云计算的调度算法
云计算是一种基于互联网的计算模式，通过将资源整合成虚拟化的方式，提供给用户按需使用。

在云计算环境中，调度算法起着至关重要的作用，它决定了如何合理、高效地利用云中的资源。

云计算的调度算法可以分为两类：静态调度和动态调度。

静态调度是在任务提交之前就确定任务的资源分配，并将任务分配给特定的云服务器；而动态调度是根据任务的实时需求，在任务执行期间动态地调整任务的资源分配。

静态调度算法一般根据任务的资源需求和约束条件，以及云服务器的资源容量和性能指标，选择最佳的云服务器进行任务分配。

常见的静态调度算法有：最小剩余处理时间调度算法、最短作业优先调度算法、最高响应比优先调度算法等。

这些算法能在任务提交之前就确定任务执行的优先级，从而提高任务的执行效率。

为了提高调度算法的效率和性能，还可以利用一些优化技术。

遗传算法、粒子群优化算法等能通过模拟自然界的进化过程，找到最优解；模拟退火算法、蚁群算法等能通过模拟自然界的随机搜索过程，找到较优解。

这些优化技术可以应用于云计算的调度算法中，提高算法的精确度和效率。

基于云计算的调度算法是云计算环境中非常重要的一环。

通过选择合适的调度算法，能够实现云计算资源的合理、高效利用，提高云计算的性能和可靠性。