基于信息熵混沌遗传算法求解网格工作流调度问题

《基于信息熵混沌遗传算法求解网格工作流调度问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于信息爛混沌遗传算法求解网格工作流调度问题摘要：网格发展的主要思想是有效的利用分布在世界各地的计算资源。而在网格环境下，是通过很多相互依赖的任务来描述作业的，这让工作流调度面临巨大的挑战。在本文中，提出了一个改进型的混沌遗传演算法来解决在工作流应用程序中的调度优化问题，它利用信息炳的概念动态调整了交叉和变异概率，优化了传统的遗传算法，并最终通过实验证明了算法的有效性。关键词：网格计算；工作流调度；混沌遗传算法；炳中图分类号：TP393文献标识码：A文章编号：1006-4311(2014)01-0194-03

2、0引言网格工作流调度问题不同于一般的任务调度，在调度时不仅要考虑为任务选择一个最佳资源，还要考虑各个任务之间的时序与因果关系等一系列的约束条件，以及协调各个任务的执行来达到最终的目标，这种调度集中于多元化相互依存的管理任务的执行及映射［1］。网格工作流调度问题中，在既定的工艺流程下，每一个任务有不同的服务器或机器可供选择，它们完成时间不同，且一个服务器上可能同时有不同的任务需要执行，它类似于柔性流水车间调度问题，相比于传统车间调度问题它更加复杂，大大增加了调度的灵活性，更符合生产的实际情况［2,3］。在现代制

3、造业中，它具有很强的代表性，可以广泛应用于精密仪器生产，化工，制药等流程工业中。一般来说，在分布式服务上映射任务的问题属于NP难题。尽管工作流调度可以进行穷举搜索，但复杂的求解方法不仅效率低下而且很难得到问题的最优解。本文为解决动态网格环境下的工作流调度问题，拟采用一种鲁棒性较强的全局寻优算法一一遗传算法［4］。遗传算法的优点是实际操作简单，搜索能力强，易于并行化，但其缺点是具有局限性，容易产生收敛停滞和易陷入局部极值点的问题［5］。因此本文在传统遗传算法的基础上，引入混沌系统，并利用信息炳的概念动态调整交叉

4、和变异概率，从而提高了算法的准确性及效率。1工作流调度问题描述网格结构可以利用工作流简化成简洁的结构模型［6］,以便在研究问题时能够从繁琐的网格结构中得到一种有利于调度研究的模型。一个工作流的运行过程通常可以利用有向图模型（DAG）来建模。设定工作流调度问题为：2混沌遗传算法设计混沌是一种在确定性系统中不定期而又长期的行为，其对初始条件十分敏感，且与杂乱的随机系统具有明显的差异。混沌系统的随机性实际上是受到约束的，对于空间具有很强的遍历性，这种模式更符合生物的进化。与原有的随机搜索相比，混沌系统的遍历性能够在

5、全局范围内进行无重复搜索，减少搜索的盲目性及随机性[7],进而提高搜索的效率。以下是改进的混沌遗传算法的具体实现过程。2.1编码对于网格环境下的工作流调度问题，用传统的基于工序的编码方法将无法得到最终的解，因为其不仅简单的对所有任务的执行进行合理的排序，更为重要的是为每一个任务的执行分配一个合理的服务器，使得最终的结果满足用户的需求。图1中的染色体表示工作流调度的一个可行解，其由两部分组成，第一部分为任务的编码，第二部分为服务分配的编码，它的总长度等于调度问题的任务总数。2.2种群初始化及适应度函数在生成初始

6、种群时，本文利用混沌系统来取代原有的随机生成方式。具体做法是将待优变量利用事先定义的混沌机制映射到混沌空间，成为混沌变量。进化中生成的混沌变量可用以下的方程式进行定义：其中C(I)表示执行个体I需实际成本总和，C表不该工作流的预算成本。2.3遗传操作遗传操作是对选择的个体进行交叉和变异操作，产生继承优良特性的下一代，经过不断的迭代，最终将收敛到“最适应环境”的个体。2.3.1选择算子选择即从当前种群中选择适应值髙的染色体以生成交配池的过程。本文在选取选择算子时所采用的方法是轮盘赌，该方法能够使得上一代染色体的

7、基因得到遗传，这是由于适应度值较高的个体更容易在算法中被选中[8]o2.3.2交叉算子在进行交叉操作时，本文对利用轮盘赌选出的染色体基于交叉概率交换一部分基因，最终生成新的染色体，此染色体有机会获得更优秀的基因，产生更优的解。本文中我们采用两点交叉的方法，具体操作步骤如下：①利用Random函数产生两个随机数作为交叉位，根据交叉位将父代染色体分为三个区域，parti,part2,part3o②交换两个父代中的part2部分。③生成的子代为交换了part2后的父代，其它的基因位都保持不变。④重复步骤①-③，得到

8、所需新种群。此外，交叉概率（PV）是控制交叉操作的使用频率，本文采用的是动态选取的方法。（见2.4节）2.3.3变异算子变异操作一定程度上能避免种群有效基因的缺失，从而增加种群的多样性。本文针对遗传算法局部搜索能力差的特点，对变异概率（PW）采用动态选取的方法（见2.4节）。2.4交叉概率和变异概率设计自适应遗传算法的核心在于种群的不断优化，而在种群的不同进化时期对于交叉、变异概率有不同的需求。在种