论文部分内容阅读
[摘要]资源调度技术是网格核心服务之一。良好的资源调度能有效地协调和分配网格资源，有效降低网格计算的总执行时间和总耗费量，从而使网格达到最大性能。提出适合网格计算环境的网格资源调度策略的遗传算法原理，并将其作为网格资源调度技术的核心策略来更合理的调度网格资源。
[关键词]网格计算任务调度遗传算法
中图分类号：TP3文献标识码：A文章编号：1671－7597（2009）0510064－02
网格的思想早在1960年就被提出，但是对网格的大规模研究只是近十几年的事，而网格的概念提出于90年代中期，用于表达在高端科学和工程上分布式计算的一种基础构造形式。简单地讲，这种计算模式是利用互联网将分散在不同地理位置的计算机组织成一个“虚拟的超级计算机”，其中每一台参与计算的计算机就是一个“节点”，而整个计算机系统由成千上万个“节点”组成“一张网格”。所以这种计算模式叫做网格计算。
网格的核心服务是网格的重要组成部分，是连接网格底层和高层功能的纽带，是协调整个网格系统有效运转的中枢，资源调度技术是网格核心服务之一。一个良好的资源调度能有效地协调和分配网格资源，有效降低网格计算的总执行时间和总耗费量，从而使网格达到最大的性能。目前网格环境下的资源调度主要在改进调度算法上。著名的Glbous网格环境着重处理了资源发现和标识问题，但在任务的提交和调度算法方面不是很完善。比较老的经典算法有min-min，sufferage等。根据网格计算资源调度系统具体的特点，传统调度算法不能很好的适应网格资源调度的要求。本文针对资源调度中的最优跨越度问题，提出了一种用于于资源调度策略的遗传算法，以提高网格资源调度性能。
一、遗传算法的基本概念
遗传算法将“适者生存”的进化理论引入串结构，在串之间进行有组织但又随机的交换彼此的信息。通过遗传操作，使优良品质被保留下来、组合，从而不断产生出更佳的个体。子代个体中包含父代个体的大量信息，并在总体上优于父代个体，从而使种群向进化发展，即不断接近最优解。
二、遗传算法的基本过程
遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问题。遗传算法对求解问题的本身一无所知，它所需要的仅仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种类；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作。
一般遗传算法主要步骤：
1．随机产生一个有确定长度的特征字符串组成的初始种群。
2．对该字符串种群迭代执行下面两步，直到满足停止准则为止。
（1）计算种群中每个个体字符串的适应值；
（2）应用复制、交叉和变异等遗传算子产生下一代种群。
把在后代中出现的最好的个体字符指定为遗传算法的执行结果，这个结果可以表示问题的一个解。
三、遗传算法的实现过程
以下从染色体的编码和解码、种群的产生、适应度函数、遗传操作对遗传算法的实现进行分析网：
（一）编码和解码
二进制编码方法是遗传算法中常用的一种编码方法，它使用的编码符号集由二进制符号0和1组成的二值符号集{0，1}，它所构成的个体基因是二进制符号串。
假设某一参数的取值范围是[A，B]，等分成2l-1个子部分，记每个等分的长度为，则它能够产生2l种不同的编码，参数的对应关系如下：
其中， 式（l）
假设某一个的编码是：X：xlxl-1x l-2…x1x2
则上述二进制编码所对应的编码公式为：
二进制编码优点：编码、解码操作简单易行；交叉、变异等遗传操作便于实现；符合最小字符集编码原则。缺点是长度较大，对于一些多维、高精度要求的连续函数优化问题，使用二进制编码来表示个体时将会有一些不利之处。
（二）产生种群
产生初始种群方法通常有两种。一种是完全随机方法产生，它适合于对问题解无任何先验知识的情况；另一种是由某些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选取样本。在网格任务调度问题中，产生初始种群的方法即属于后者。
（三）适应度函数
为了体现染色体的适应能力，引入了对问题中的每个染色体都能进行度量的函数，叫做适应度函数（fitness function）。通过适应度函数来决定染色体的优劣程度，它体现了自然进化中的优胜劣汰原则。对于优化问题，适应度函数就是目标函数。例如Tsp[]问题目标是路径总长度为最短，自然地，路径总长度就可作为Tsp问题的适应度函数：
其中wn+1=w1，d（wj，wj+1）表示两个城市间的距离（路径长度）。
适应函数要有效地反映每个染色体与问题的最优解染色体之间的差距。若一个染色体与问题的最优染色体之间的差距较小，则对应的适应度函数值差就较小，否则就较大。适应度函数的取值大小与求解问题对象有很大关系。
（四）遗传操作
简单遗传算法的遗传操作主要有三种：选择（selection）、交叉
（Crossover）、变异（mutation）。
选择操作也叫做复制（reproduction）操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是淘汰还是被遗传。一般地，选择将使适应度较大（优良）的个体有较大的存在机会，而适应度较小（低劣）的个体继续存在的机会也较小，例如通常采用的轮盘赌选择机制， 表示群体的适应值之总和，fi表示群体中第i个染色体的适应度值，它产生后代的能力为其适应度值所占份额 。
交叉操作的简单方式是将被选择出的两个个体P1和P2（如图1所示）作为母体个体，将两者的部分码值进行交换。假设有如下8个位长的两个个体：
10001001，这就是P1和P2的一个后代Q1个体；P2的高五位与P1的低三位组成数串1101110，这就是P1和P2的另一个后代Q2个体。其交换过程如图2所示。
变异操作的简单方式是改变数码串的某个位置的数码只有0和1这两种可能，有如下二进制编码表示：
其码长为8，随机产生一个1}8之间的数k，假如现在k=5，对从右往左的第五位进行变异操作，将原来的0变为1，得到如下数码串（第五位的数字1是经变异操作后出现的）：
二进制编码表示的简单变异操作是将0与1互换，0变为1，1变为0。
现在对tsp的变异操作作简单介绍：随机产生一个l～n之间的数k，决定对回路中的第k个城市的代码w，做变异操作，又产生一个l～n之间的数w替代wk，并将wk加到尾部，得到：
这个串有n+1个数码。注意，数w在此串中重复了，必须删除与数w重复的数以得到合法的染色体。
（五）控制参数
在遗传算法计算中需要控制的参数主要有：种群规模、迭代次数、交叉概率、变异概率等。参数对遗传算法的效果和运行性能有较大影响，在面对具体优化问题时应认真选取。
四、遗传算法的特点
遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找所求问题的答案。因此，遗传算法的求解过程也可看做是最优化过程。需要指出的是：遗传算法并不能保证所得到的是最佳答案，但通过一定的方法，可以将误差控制在容许的范围内。遗传算法具有以下特点：
1．遗传算法是对参数集合的编码而非针对参数本身进行进化；
2．遗传算法是从问题解的编码组开始而非从单个解开始搜索；
3．遗传算法利用目标函数的适应度这一信息而非利用导数或其他辅助信息来指导搜索；
4．遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。
遗传算法利用简单的编码技术和繁殖机制来表现复杂的现象，从而解决非常困难的问题。它不受搜索空间的限制性假设的约束，由于它固有的并行性，遗传算法非常适用于大规模并行计算，已在优化、机器学习和并行处理等领域得到了越来越广泛的应用。
[关键词]网格计算任务调度遗传算法
中图分类号：TP3文献标识码：A文章编号：1671－7597（2009）0510064－02
网格的思想早在1960年就被提出，但是对网格的大规模研究只是近十几年的事，而网格的概念提出于90年代中期，用于表达在高端科学和工程上分布式计算的一种基础构造形式。简单地讲，这种计算模式是利用互联网将分散在不同地理位置的计算机组织成一个“虚拟的超级计算机”，其中每一台参与计算的计算机就是一个“节点”，而整个计算机系统由成千上万个“节点”组成“一张网格”。所以这种计算模式叫做网格计算。
网格的核心服务是网格的重要组成部分，是连接网格底层和高层功能的纽带，是协调整个网格系统有效运转的中枢，资源调度技术是网格核心服务之一。一个良好的资源调度能有效地协调和分配网格资源，有效降低网格计算的总执行时间和总耗费量，从而使网格达到最大的性能。目前网格环境下的资源调度主要在改进调度算法上。著名的Glbous网格环境着重处理了资源发现和标识问题，但在任务的提交和调度算法方面不是很完善。比较老的经典算法有min-min，sufferage等。根据网格计算资源调度系统具体的特点，传统调度算法不能很好的适应网格资源调度的要求。本文针对资源调度中的最优跨越度问题，提出了一种用于于资源调度策略的遗传算法，以提高网格资源调度性能。
一、遗传算法的基本概念
遗传算法将“适者生存”的进化理论引入串结构，在串之间进行有组织但又随机的交换彼此的信息。通过遗传操作，使优良品质被保留下来、组合，从而不断产生出更佳的个体。子代个体中包含父代个体的大量信息，并在总体上优于父代个体，从而使种群向进化发展，即不断接近最优解。
二、遗传算法的基本过程
遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问题。遗传算法对求解问题的本身一无所知，它所需要的仅仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种类；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作。
一般遗传算法主要步骤：
1．随机产生一个有确定长度的特征字符串组成的初始种群。
2．对该字符串种群迭代执行下面两步，直到满足停止准则为止。
（1）计算种群中每个个体字符串的适应值；
（2）应用复制、交叉和变异等遗传算子产生下一代种群。
把在后代中出现的最好的个体字符指定为遗传算法的执行结果，这个结果可以表示问题的一个解。
三、遗传算法的实现过程
以下从染色体的编码和解码、种群的产生、适应度函数、遗传操作对遗传算法的实现进行分析网：
（一）编码和解码
二进制编码方法是遗传算法中常用的一种编码方法，它使用的编码符号集由二进制符号0和1组成的二值符号集{0，1}，它所构成的个体基因是二进制符号串。
假设某一参数的取值范围是[A，B]，等分成2l-1个子部分，记每个等分的长度为，则它能够产生2l种不同的编码，参数的对应关系如下：
其中， 式（l）
假设某一个的编码是：X：xlxl-1x l-2…x1x2
则上述二进制编码所对应的编码公式为：
二进制编码优点：编码、解码操作简单易行；交叉、变异等遗传操作便于实现；符合最小字符集编码原则。缺点是长度较大，对于一些多维、高精度要求的连续函数优化问题，使用二进制编码来表示个体时将会有一些不利之处。
（二）产生种群
产生初始种群方法通常有两种。一种是完全随机方法产生，它适合于对问题解无任何先验知识的情况；另一种是由某些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选取样本。在网格任务调度问题中，产生初始种群的方法即属于后者。
（三）适应度函数
为了体现染色体的适应能力，引入了对问题中的每个染色体都能进行度量的函数，叫做适应度函数（fitness function）。通过适应度函数来决定染色体的优劣程度，它体现了自然进化中的优胜劣汰原则。对于优化问题，适应度函数就是目标函数。例如Tsp[]问题目标是路径总长度为最短，自然地，路径总长度就可作为Tsp问题的适应度函数：
其中wn+1=w1，d（wj，wj+1）表示两个城市间的距离（路径长度）。
适应函数要有效地反映每个染色体与问题的最优解染色体之间的差距。若一个染色体与问题的最优染色体之间的差距较小，则对应的适应度函数值差就较小，否则就较大。适应度函数的取值大小与求解问题对象有很大关系。
（四）遗传操作
简单遗传算法的遗传操作主要有三种：选择（selection）、交叉
（Crossover）、变异（mutation）。
选择操作也叫做复制（reproduction）操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是淘汰还是被遗传。一般地，选择将使适应度较大（优良）的个体有较大的存在机会，而适应度较小（低劣）的个体继续存在的机会也较小，例如通常采用的轮盘赌选择机制， 表示群体的适应值之总和，fi表示群体中第i个染色体的适应度值，它产生后代的能力为其适应度值所占份额 。
交叉操作的简单方式是将被选择出的两个个体P1和P2（如图1所示）作为母体个体，将两者的部分码值进行交换。假设有如下8个位长的两个个体：
10001001，这就是P1和P2的一个后代Q1个体；P2的高五位与P1的低三位组成数串1101110，这就是P1和P2的另一个后代Q2个体。其交换过程如图2所示。
变异操作的简单方式是改变数码串的某个位置的数码只有0和1这两种可能，有如下二进制编码表示：
其码长为8，随机产生一个1}8之间的数k，假如现在k=5，对从右往左的第五位进行变异操作，将原来的0变为1，得到如下数码串（第五位的数字1是经变异操作后出现的）：
二进制编码表示的简单变异操作是将0与1互换，0变为1，1变为0。
现在对tsp的变异操作作简单介绍：随机产生一个l～n之间的数k，决定对回路中的第k个城市的代码w，做变异操作，又产生一个l～n之间的数w替代wk，并将wk加到尾部，得到：
这个串有n+1个数码。注意，数w在此串中重复了，必须删除与数w重复的数以得到合法的染色体。
（五）控制参数
在遗传算法计算中需要控制的参数主要有：种群规模、迭代次数、交叉概率、变异概率等。参数对遗传算法的效果和运行性能有较大影响，在面对具体优化问题时应认真选取。
四、遗传算法的特点
遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找所求问题的答案。因此，遗传算法的求解过程也可看做是最优化过程。需要指出的是：遗传算法并不能保证所得到的是最佳答案，但通过一定的方法，可以将误差控制在容许的范围内。遗传算法具有以下特点：
1．遗传算法是对参数集合的编码而非针对参数本身进行进化；
2．遗传算法是从问题解的编码组开始而非从单个解开始搜索；
3．遗传算法利用目标函数的适应度这一信息而非利用导数或其他辅助信息来指导搜索；
4．遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。
遗传算法利用简单的编码技术和繁殖机制来表现复杂的现象，从而解决非常困难的问题。它不受搜索空间的限制性假设的约束，由于它固有的并行性，遗传算法非常适用于大规模并行计算，已在优化、机器学习和并行处理等领域得到了越来越广泛的应用。