自适应遗传算法在飞机调度问题中的应用
云计算环境下基于改进遗传算法的任务调度算法
收稿日期:2010-07-15;修回日期:2010-09-06。 基金项目:四川省科技支撑计划项目(06K J T 013;2009GZ0153)。 作者简介:李建锋(1987-),男,河南项城人,硕士研究生,主要研究方向:网格计算、云计算; 彭舰(1970-),男,四川成都人,教授,博士, 主要研究方向:分布式系统、移动计算。 文章编号:1001-9081(2011)01-0184-03 do:i 10.3724/SP .J .1087.2011.00184 云计算环境下基于改进遗传算法的任务调度算法 李建锋,彭 舰 (四川大学计算机学院,成都610065) (ji anpeng @sc https://www.wendangku.net/doc/8918697152.html, .cn ) 摘 要:在云计算中面对的用户群是庞大的,要处理的任务量与数据量也是十分巨大的。如何对任务进行高效 的调度成为云计算中所要解决的重要问题。针对云计算的编程模型框架,提出了一种具有双适应度的遗传算法(DFGA ),通过此算法不但能找到总任务完成时间较短的调度结果,而且此调度结果的任务平均完成时间也较短。通过仿真实验将此算法与自适应遗传算法(AGA )进行比较,实验结果表明,此算法优于自适应遗传算法,是一种云计算环境下有效的任务调度算法。 关键词:云计算;遗传算法;双适应度;任务调度 中图分类号:T P393 文献标志码:A Task scheduli ng al gorith m based on improved genetic algorith m i n cloud co mputi ng environ m ent LI Jian feng ,PE NG Jian (C olle ge of Co mpu te r S cie nce ,S ichuan Un i versit y,Chengd u S ic huan 610065,Ch i na ) Abstract :T he number of users i s huge in c l oud computi ng ,and t he nu mber o f tasks and t he a m ount of da ta are also huge.H ow to schedule tasks efficiently i s an i m portant i ssue to be reso l ved i n c l oud computi ng env iron m ent .A Doub l e F itness G enetic A lgor i th m (DFGA )w as brought up for t he prog ramm i ng fram e w ork o f c l oud computi ng.T hrough th i s a l gor ith m,the be tter task scheduli ng no t only sho rtens to tal task comp l e ti on ti m e and a lso has shorter average co m pletion ti m e .T he re i s a contrast bet ween DFGA and Adapti ve G ene tic A l gor it hm (AGA )t hrough si m u lati on exper i m ent ,and the resu lt i s :t he DFGA i s be tter ,it is an effi c i ent task schedu li ng a l go rith m i n c l oud co m puti ng env iron m ent . K ey words :cloud co m puti ng ;G ene ti c A l go rith m (GA );doub le fitness ;task schedu li ng 0 引言 近几年云计算[1-2]成为了人们讨论的热点。目前IB M 、G oog l e 、Am azon 、M icroso ft 等纷纷涉足云计算,提供了众多基于云计算的服务,如Gm a il 、Goog le E arth 、G oog l e Ana l y ti cs 、G oog l e 搜索、G oog l e 文档[3];Am azon 的弹性云计算(EC2)服务和存储服务(S3);M i crosoft 的W i ndow s L ive W eb 应用套件及H ot m ail 等[4]。 云计算是并行计算、网格计算[5-6]的发展,是分布式计算的一种,其最基本的思想是透过网络将庞大的计算处理程序自动分拆成无数个较小的子程序,再交由多部服务器所组成的庞大系统,经搜寻、计算分析之后将处理结果回传给用户,提供这些资源的网络被称为 云 。云计算所提供的服务面向的用户群是庞大的,因此 云 中的任务数量是巨大的,系统每时每刻都要处理海量的任务,所以任务调度[7]是云计算中的重点与难点。本文对如何充分利用 云 中的资源使其中的任务进行高效合理的调度进行了研究,提出了一种基于双适应度遗传算法(D oub l e F itness G enetic A l go rith m,DFGA )的任务调度算法,并通过了仿真实验,验证了其良好的性能。 1 云计算中的编程模型 目前的云计算环境中大部分采用G oog le 提出的M ap /R educe 的编程模式[8],大部分信息技术厂商提出的 云 计划 中采用的编程模型,都是采用基于M ap /R educe 的思想开发的编程工具,它特别适用于产生和处理大规模的数据集。其执行过程如图1所示。 图1 M ap /R educe 的具体执行过程 从图1可以看出,M ap /R educe 有6个过程,可分为两个主要阶段。 M ap 阶段 把一个较大的任务通过M ap/R educe 函数分割为M 个较小的子任务,然后配给多个w orker(被分配为执行M ap 操作的wo rker)并行执行,输出处理后的中间文件; 第31卷第1期 2011年1月 计算机应用 Journal o f Computer A pp licati ons V o.l 31N o .1 Jan .2011
遗传算法在生产调度方面的应用
遗传算法在生产调度方面的应用 合肥工业大学吴磊（20080313）陈超峰（20080321）方振中（20080322）周超（20080332）王伦良（20080340） 摘要：生产调度问题是企业生产甚至国际合作的关键问题，但生产调度问题难以精确求解。遗传算法可以很好的解决这一问题，在生产调度、生产规划、任务分配等方面发挥着极其重要的作用。 关键词：生产调度生产调度方式遗传算法 1.遗传算法 遗传算法是模拟生物在自然环境中的进化过程而形成的一种自适应全局优化概率的搜索算法。它使用群体搜索技术，通过对当前群体施加选择交叉变异等一系列遗传操作，从而产生新一代的群体，并按优胜劣汰的机制逐步使群体进化到包含或接近最优解的状态。 1.1遗传算法的基本运算过程 选择：从当前种群中选出优良的个体作为父代个体。 对各染色体v k计算适合度eval（v k）；k=1,2,3，…，m 计算选择概率： 对各染色体v k ， P=eval（v k）/∑eval(v k) 交叉：对群体中的个体进行两两随即配对 对每一对相互配对的个体，随机设置某一基因之后的位置为交叉点 对每一对相互配对的个体，依设定的交叉概率在其交叉点处相互交换两个个体的染色体，从而产生出两个新的个体。 变异：遗传算法中的所谓变异运算，是将个体染色体编码串中的某些位置上的基因值用其他等位基因替换，从而形成一个新的个体。 2.生产调度 生产调度就是组织执行生产进度计划的工作，是实现生产进度计划的主要手段。生产调度以生产进度计划为依据，生产进度计划要通过生产调度来实现。 在生产调度的事业上，生产调度有管理和工作之分，也就是生产调度管理和生产调度工作，是两个互为联系有有区别的概念。生产调度的作用是职能作用，生产调度工作的作用是职责作用。具体来说，生产调度管理，是指生产调度的计划、实施、检查、总结的期量循环活动的管理，是指生产调度的计划理论、方法、法规等方面的管理。生产调度工作，则有狭义和广义之分，从狭义上说，生产调度工作是指生产调度的业务工作，也就是生产经营管理方面的技术性工作，其内容是生产调度对生产经营动态的了解、掌握、预防、处理，对关键岗位如主机岗位实行控制，对跨车间和跨部门的电、水、风，产、供、销、运等进行协调平衡，对产量、质量、安全、效益等重点环节实行衔接一致的保证；从广义上说，生产调度部门的行政管理方面的具体事项，如业务上，科技上的研讨活动，在岗人员道德和专业知识的教育，业务能量的具体发挥等，可见广义的生产调度工作，其具体活动事项要比生产调度管理大得多，将生产调度管理等同生产调度工作是不准确的。可以概括的说，生产调度工作是生产调度管理的具体表现，生产调度工作的完成是生产调度管理在实际上完成的具体表现。生产调度的重要意义在于：现代工业企业，生产环节多，协作关系复杂，生产连续性强，情
基于遗传算法的任务调度研究
华中师范大学计算机科学系实验报告书 实验题目：基于遗传算法的多任务调度研究课程名称：智能计算 主讲教师：沈显君 辅导教师： 课程编号： 班级： 2011级 实验时间： 2011年11月
基于遗传算法的多任务调度研究 摘要： 本文主要讨论了遗传算法在工程项目中多任务执行优化中的应用，重点对多任务调度 (Resource —constrained project scheduling problem ，RCPSP)问题进行了研究。讨论了资源受限的多任务调度问题，提出了改进的遗传算法优化多任务调度问题的方法，主要从优化算法模型的建立，优化算法设计，算法的实现以及结果分析等几个方面进行了详细论述，并与其它启发式方法进行了对比分析。 关键字：效益最优化；遗传算法；多任务 1．简介 任务调度优化在工程项目管理中是非常重要的，它决定了工程项目利润的高低。遗传算法是一种并行的全局搜索的高效求解问题的方法，本质上就是处理离散优化搜索问题的，它不要求问题空间的连续性，不需要梯度信息，其鲁棒性(Robust)已经得到了证实，在处理大型复杂优化问题上己经取得了显著的成绩，所以在解决多任务调度优化问题时，具有其它方法无法比拟的优势。 2．多任务调度模型的建立 假设存在若干并行任务和一个共享的资源库，包含有若干种可更新资源(renewable resources)，并且所有资源都只有有限的供给量。任务之间除了共享资源外互相独立。为方便对问题进行描述，建立如下的数学模型：多任务调度问题有P 个相互独立的任务，第k 个任务包含n k+1个工作,其中第n k+ 1个任务为任务虚拟的终止工作,不占用资源和时间。这P 个任务共享M 种可更新资源，其中第m 种资源的总量为R m 。用W i 表示第i 个任务的工作集，W ij 表示第i 个任务中的第j 个工作,其工期为d ij ，对第m 种资源的需求量为r ijm ，任务的开始时间标记为S ij ,它的所有紧前任务形成的集合记为P ij 。在时间t 时正在进行的所有任务的集合标记为I t 。考虑到不同任务的重要程度不同,用a k 表示第k 个任务的权重。综合上述假设和采用的符号，资源约束下的多任务调度问题可以描述为公式（1）-(6)： ∑=+? P k n k k k S 1 1,) (*min （1） j i P h d S S t s ij h i h i j i ,,,. .,,,?∈?+≥ （2） .,, ,∑∈?≤t j i I w m ijm t m R r （3）
车辆调度与优化之遗传算法
车辆调度与优化之遗传 算法 SANY GROUP system office room 【SANYUA16H-
遗传算法 遗传算法的遗传操作主要有三种：复制、交叉、变异，这也是遗传算法中最常用的三种算法。 我这次研究的便是第一种操作--复制。 复制操作也叫选择操作，它是从一个旧种群中选择生命力强的个体位串产生新种群的过程。具有高适应度的位串更有可能在下一代中产生一个或多个子孙。 我感觉简单的拿数据来说复制操作可以通过随机方法来实现。首先产生 0~1之间均匀分布的随机数，若某串的复制概率为30%，则当产生的随机数在0.30~1.0之间时，该串被复制，否则被淘汰。 下面以轮盘赌模型为例： t123456 适应度 220018001200950400100值： 令表示群体的适应度值之总和，f(t)表示种群中第t个染色体的适应度值，它被选择的概率P(t)正好为其适应度值所占份额。即P(t)=如上图表中的数据适应值总和=2200+1800+1200+950+400+100=6650 所以P(1)的概率为：P(1)=2200/6650=0.331 即适应度为2200被复制的可能为0.331。 同理可得： P(2)=1800/6650=0.271P(3)=1200/6650=0.180 P(4)=950/6650=0.143P(5)=400/6650=0.060 P(6)=100/6650=0.015
轮盘赌模型 根据上面的理论可以知道P(1)的概率最大，所以最有可能被复制。也就是说从群体中按个体的适应度函数值选择出较适应环境的个体。一般地说，选择将使适应度高的个体繁殖下一代的数目较多，而适应度较小的个体，繁殖下一代的数目较少,甚至被淘汰。
车辆调度与优化之遗传算法
车辆调度与优化之遗传 算法 集团企业公司编码：（LL3698-KKI1269-TM2483-LUI12689-ITT289-
遗传算法 遗传算法的遗传操作主要有三种：复制、交叉、变异，这也是遗传算法中最常用的三种算法。 我这次研究的便是第一种操作--复制。 复制操作也叫选择操作，它是从一个旧种群中选择生命力强的个体位串产生新种群的过程。具有高适应度的位串更有可能在下一代中产生一个或多个子孙。 我感觉简单的拿数据来说复制操作可以通过随机方法来实现。首先产生0~1之间均匀分布的随机数，若某串的复制概率为30%，则当产生的随机数在0.30~1.0之间时，该串被复制，否则被淘汰。 下面以轮盘赌模型为例： 令∑f(f)表示群体的适应度值之总和，f(t)表示种群中第t个染色体的适应度值，它被选择的概率P(t)正好为其适应度值所占份额 f(f)∑f(f) ?。即P(t)=f(f) ∑f(f) 如上图表中的数据适应值总和 ∑f(f)=2200+1800+1200+950+400+100=6650 所以P(1)的概率为：P(1)=2200/6650=0.331 即适应度为2200被复制的可能为0.331。 同理可得：
P(2)=1800/6650=0.271P(3)=1200/6650=0.180 P(4)=950/6650=0.143P(5)=400/6650=0.060 P(6)=100/6650=0.015 轮盘赌模型 根据上面的理论可以知道P(1)的概率最大，所以最有可能被复制。也就是说从群体中按个体的适应度函数值选择出较适应环境的个体。一般地说，选择将使适应度高的个体繁殖下一代的数目较多，而适应度较小的个体，繁殖下一代的数目较少,甚至被淘汰。