论文部分内容阅读
摘要：本文对于常见的遗传蚁群算法，根据云计算环境，提出了智能化的编码方案，过滤掉冗余编码，并把最短完成时限写进适应函数，在算法初始阶段过滤掉不符合时间要求的调度方案，并在蚁群算法中进行了双重收敛加速，并考虑到了负载均衡。实验证明，本算法取得了较好的效果。
关键词：云计算；改进型遗传蚁群算法；智能编码；双重收敛加速
中图分类号：TP301.6 文献标识码：A 文章编号：1007-9599 （2012） 23-0000-02
1 引言
云计算是一种以“租赁服务”为目标的商业实现。它的理念来自于用户经常发现他们需要的是某种服务，而不是通常购买的软件，平台或者服务器。如果用户不需要购买，只需要租赁这些资源，那该是一件多么美好的事情。普遍来讲，云计算就是通过互联网将数据中心的各种资源打包成服务向外提供。
而目前云计算的任务调度（任务资源映射）没有通用的算法。常用的启发式任务调度算法系统开销大，且没有考虑到用户的要求，负载均衡方面也不理想。所以人们提出了一种遗传蚁群融合算法，即保留了遗传算法前期搜索速度快的优点，也保证了蚁群算法搜索后期高效的优势，但存在着编码不够合理，适应函数不够规范，融合点的定位不够动态，蚁群算法收敛加速不够等缺点。本文在一种常用的遗传蚂蚁算法基础上（参考文献[8]）进行改进，试图使其调度性能更加理想。
2 算法的改进
2.1 染色体编码的改进
文献[8]提出了这样一种编码方案，采用十进制实数编码，每个染色体代表一种调度方案。假设有i个任务j个资源，则染色体长度i+j。资源与任务映射规则如下：调度任务到最邻近的右端资源。比如当前有5个任务3个计算节点，则数字1到5表示任务，6到8表示资源。编码12734856表示任务1，2分配给7；3和4分配给8；5给6.解码规则为逆运算。
然而由于12734856实际上和21743856是一样的，这种编码会带来极大的资源浪费。对此假如有5个任务，我们先对任务队列排序，优先级较大的或较小的任务靠前，编码为1到5，这样出现了7个位置，先对位置7随机一个资源，这样可以保证任务得到完全调度（在本例中即保证染色体必需由678的一个结尾），再对另外两个资源节点随机分配1到6的位置，并不许重复（不允许12673458这样的染色体出现，虽然它也有可能表示一定意义，比如67123458表示67节点可能负载比较重而不分配新到任务。在本步骤忽略这种情况，负载均衡由蚁群算法控制。）。比如资源6随机到的位置是3，7对应4，8对应7，则生成字符串应为12637458。
2.2 适应函数的改进
由于我们在初代染色体的生成上采用了较小任务优先调度的思想以期总时间较短的思想，这就很可能造成每个资源节点上任务完成总时间较好但一个用户的各个子任务的平均完成时间不佳。为了解决这个问题，适应函数设计如下。
其中costi表示i个有最短完成时限的任务，deadline（i）表示这个任务的最短完成时限。如果有最短时限要求的任务未能按时完成，则适应度置0，；其他的按平均完成时间设置适应度。当都完成最短时限时，我们根据用户的完成时间期望（或者付费额度或者任务优先级）设置加权参数M和N，分别核算用户TASK1和TASK2的加权完成时间再计算平均值。
比如说有12634758染色体，其中135属于用户1的子任务，24属于用户2，用户1时间期望比用户2高，或者他付费更多，那么我们就分别计算用户1的135子任务分别调度到678的时间之和再乘以系数m，24调度给67的时间之和再乘以系数n，得到的和再除以任务数。在本文中，为简化实验只设定两个用户，且m=1.2，n=0.9。
这话改进方式不仅仅以完成时间以最重要的适应度度量，而且考虑到了任务的时间期待或者优先级，更符合云环境商业应用的特点。
2.3 此种编码方式下遗传算子设计
（1）根据适应函数值大小排序，从队列中选出按百分比P值，选择P/2（P值自定）个染色体，再另随机选出P/2个染色体选择准备进行交叉；
（2）交叉操作采用Davis顺序交叉方法；如P1=126|374|58和P2=162|348|57，保留割点间的片段得到N1=XXX|374|XX和N2=XXX|348|XX，为得到后代N1，将P2中去除374得到16285，依次插入P1得到P1=16237485.这样做的好处是既保证了交叉的有效性，又保证了我们任务排序的约束。由于我们在编码时设定了两点约束，即资源节点不允许相邻，且必须以资源节点结束，所以我们需要定义修补算子。
修补算子定义如下：如果存在资源节点相邻，则相邻的后一个节点向右交换直至符合规定；如果不以资源节点结束，则自右向左寻找最近的资源与最后一位交换。如在本例中最终得到的P1=16237458。
（3）变异算子在本文中简化为修补算子，因为此种编码方案不能进行常规变异。交叉操作后适应函数有改进的保留，无改进或有未按最短时限完成的任务则丢弃。
2.4 遗传算法与蚁群算法融合点的改进
如上图所示，为最大限度的利用遗传算法的搜索初期速度快，蚁群算法后期效率高的特点，融合应在tb和td之间最合适（tc最佳）。但常见的融合点设计无论是遗传固定的代数，还是当遗传进化率低于固定值时结束，都不能正确的定位tb与td区间。本文提出一种新的思路：
（1）如果遗传迭代次数大于最小迭代次数，连续N代遗传进化率都在下降，且连续M代本代最优解适应值小于当前最优解适应值，则视为遗传算法可结束。
（2）如果遗传迭代次数达到最大迭代次数，则结束遗传算法。
这种思路基于这样一种想法——如果我们设置一定连续代遗传进化率小于固定值作为遗传算法的结束条件（或超出最大代），那么我们寻找到的时间点通常在td之后。如果不能准确定位tc点，那么在tb之后，且没有更优解的情况下，尽早进入蚂蚁算法可以使算法更加的简洁高效。 2.5 蚁群算法的改进
2.5.1 在初始化信息素后，即根据一定量的最优染色体进行初始信息素增加。
进入蚁群算法后更新方程重写如下：τjnew= τjold+lj c ηj
其中lj表示当前资源节点的任务负载率，为已完成任务和负载总量，负载率低的增加信息素多一点。ηj为评估当前资源节点QoS质量的参数，如带宽，CPU占用率等，QoS状态好的节点增加信息素多一点。c为调整参数。这样设计更新方程既考虑了负载平衡可以使收敛具有一定的方向性，加速收敛。
2.5.2 任务i和资源j的映射概率改写为：
Pij=
其中 j为资源j的当前的状态，表征CPU利用率，可用内存，可用带宽等。 和 为调整参数。需要注意的是因为我们在更新方程中已经根据资源状态（当时包含了负载率）控制了信息素分布，所以现在的 值应较常规蚂蚁算法比较小。收敛加速的双重控制可以更精确的加速收敛，通过不断调整参数达到理想的收敛速度。
2.5.3 为了避免蚁群算法后期常常陷入局部最优解，如果在最大迭代代数的3/4代之前连续N代收敛于同一解，则降低该解所分布资源的信息素为之前的R倍。本文选择R为0.4。
3 算法仿真结果
上述结果表明在所搜索节点比率减小或规模扩大时，本算法优势明显。
4 小结
本文根据云环境的特点，对常用的遗传蚁群融合算法进行改良，提出了比较智能的编码方案；并提出了独特的融合算法；更加动态的定位融合点；根据资源的状态，在算法进入蚁群算法后提出了双重约束，更加精确的控制收敛速度又保证了负载均衡。最终试验证明取得了较好的效果。
参考文献：
[1]刘鹏.云计算的定义和特点[J].中国云计算.
[2]马学彬，温涛，郭权，王刚.一种基于遗传算法的网格任务调度算法[J].东北大学学报.
[3]高曙，郑德.一种基于蚁群算法的任务调度方法.
[4]陈峻，沈洁，秦玲.蚁群算法进行连续参数优化的新途径[J].系统工程理论与实践，2003.
[5]马良，蒋馥.多目标旅行售货员问题的蚂蚁算法求解[J].系统工程理论方法应用，1999.
[6]房秉毅，张云勇，程莹.云计算国内外发展现状分析[J].电信科学，2010，8A：1-5.
[7]王静宇，谭跃生，陈振江.基于遗传蚁群混合算法的网络任务调度研究[J].计算机与信息技术，2008，9（3）：53-55.
[8]张雨，李芳，周涛.云计算环境下予以遗传蚁群算法的任务调度研究.计算机工程与应用，2012.9.
[9]华夏渝，郑骏，胡文心.基于云计算环境的蚁群优化计算资源分配算法.华东师范大学学报，2010.01.
[10]Downey and D.Feitelson.1999.The elusive goal of work-load characterization. In Performance Evaluation Review， pages 14-29.
[11]Albert Greenberg.2008. VL2： a scalable and flexible data center network.51-62，SIGCOMM.
[12]A. Land and A. Doig. 1960.An automatic method of solving discrete programming problem ，Econometrica.pp. 497-520.
[13]Germain R C， RANA O F. 2009. The Convergence of Clouds， Grids， and Autonomics [J]. IEEE.Internet Computing，12（6）：9.
[14]Haifeng Yu， Amin Vahdat. 2002. Minimal Replication Cost for Availability， PODC， Monterey，Califormia， USA.
[15]J. Lockwood， N. McKeown， G. Watson， G. Gibb， P. Hartke， J. Naous， R. Raghuraman， and J. Luo.2007. NetFPGA–An Open Platform for Gigabit-rate Network Switching and Routing. In IEEE International Conference on Microelectronic Systems Education.
关键词：云计算；改进型遗传蚁群算法；智能编码；双重收敛加速
中图分类号：TP301.6 文献标识码：A 文章编号：1007-9599 （2012） 23-0000-02
1 引言
云计算是一种以“租赁服务”为目标的商业实现。它的理念来自于用户经常发现他们需要的是某种服务，而不是通常购买的软件，平台或者服务器。如果用户不需要购买，只需要租赁这些资源，那该是一件多么美好的事情。普遍来讲，云计算就是通过互联网将数据中心的各种资源打包成服务向外提供。
而目前云计算的任务调度（任务资源映射）没有通用的算法。常用的启发式任务调度算法系统开销大，且没有考虑到用户的要求，负载均衡方面也不理想。所以人们提出了一种遗传蚁群融合算法，即保留了遗传算法前期搜索速度快的优点，也保证了蚁群算法搜索后期高效的优势，但存在着编码不够合理，适应函数不够规范，融合点的定位不够动态，蚁群算法收敛加速不够等缺点。本文在一种常用的遗传蚂蚁算法基础上（参考文献[8]）进行改进，试图使其调度性能更加理想。
2 算法的改进
2.1 染色体编码的改进
文献[8]提出了这样一种编码方案，采用十进制实数编码，每个染色体代表一种调度方案。假设有i个任务j个资源，则染色体长度i+j。资源与任务映射规则如下：调度任务到最邻近的右端资源。比如当前有5个任务3个计算节点，则数字1到5表示任务，6到8表示资源。编码12734856表示任务1，2分配给7；3和4分配给8；5给6.解码规则为逆运算。
然而由于12734856实际上和21743856是一样的，这种编码会带来极大的资源浪费。对此假如有5个任务，我们先对任务队列排序，优先级较大的或较小的任务靠前，编码为1到5，这样出现了7个位置，先对位置7随机一个资源，这样可以保证任务得到完全调度（在本例中即保证染色体必需由678的一个结尾），再对另外两个资源节点随机分配1到6的位置，并不许重复（不允许12673458这样的染色体出现，虽然它也有可能表示一定意义，比如67123458表示67节点可能负载比较重而不分配新到任务。在本步骤忽略这种情况，负载均衡由蚁群算法控制。）。比如资源6随机到的位置是3，7对应4，8对应7，则生成字符串应为12637458。
2.2 适应函数的改进
由于我们在初代染色体的生成上采用了较小任务优先调度的思想以期总时间较短的思想，这就很可能造成每个资源节点上任务完成总时间较好但一个用户的各个子任务的平均完成时间不佳。为了解决这个问题，适应函数设计如下。
其中costi表示i个有最短完成时限的任务，deadline（i）表示这个任务的最短完成时限。如果有最短时限要求的任务未能按时完成，则适应度置0，；其他的按平均完成时间设置适应度。当都完成最短时限时，我们根据用户的完成时间期望（或者付费额度或者任务优先级）设置加权参数M和N，分别核算用户TASK1和TASK2的加权完成时间再计算平均值。
比如说有12634758染色体，其中135属于用户1的子任务，24属于用户2，用户1时间期望比用户2高，或者他付费更多，那么我们就分别计算用户1的135子任务分别调度到678的时间之和再乘以系数m，24调度给67的时间之和再乘以系数n，得到的和再除以任务数。在本文中，为简化实验只设定两个用户，且m=1.2，n=0.9。
这话改进方式不仅仅以完成时间以最重要的适应度度量，而且考虑到了任务的时间期待或者优先级，更符合云环境商业应用的特点。
2.3 此种编码方式下遗传算子设计
（1）根据适应函数值大小排序，从队列中选出按百分比P值，选择P/2（P值自定）个染色体，再另随机选出P/2个染色体选择准备进行交叉；
（2）交叉操作采用Davis顺序交叉方法；如P1=126|374|58和P2=162|348|57，保留割点间的片段得到N1=XXX|374|XX和N2=XXX|348|XX，为得到后代N1，将P2中去除374得到16285，依次插入P1得到P1=16237485.这样做的好处是既保证了交叉的有效性，又保证了我们任务排序的约束。由于我们在编码时设定了两点约束，即资源节点不允许相邻，且必须以资源节点结束，所以我们需要定义修补算子。
修补算子定义如下：如果存在资源节点相邻，则相邻的后一个节点向右交换直至符合规定；如果不以资源节点结束，则自右向左寻找最近的资源与最后一位交换。如在本例中最终得到的P1=16237458。
（3）变异算子在本文中简化为修补算子，因为此种编码方案不能进行常规变异。交叉操作后适应函数有改进的保留，无改进或有未按最短时限完成的任务则丢弃。
2.4 遗传算法与蚁群算法融合点的改进
如上图所示，为最大限度的利用遗传算法的搜索初期速度快，蚁群算法后期效率高的特点，融合应在tb和td之间最合适（tc最佳）。但常见的融合点设计无论是遗传固定的代数，还是当遗传进化率低于固定值时结束，都不能正确的定位tb与td区间。本文提出一种新的思路：
（1）如果遗传迭代次数大于最小迭代次数，连续N代遗传进化率都在下降，且连续M代本代最优解适应值小于当前最优解适应值，则视为遗传算法可结束。
（2）如果遗传迭代次数达到最大迭代次数，则结束遗传算法。
这种思路基于这样一种想法——如果我们设置一定连续代遗传进化率小于固定值作为遗传算法的结束条件（或超出最大代），那么我们寻找到的时间点通常在td之后。如果不能准确定位tc点，那么在tb之后，且没有更优解的情况下，尽早进入蚂蚁算法可以使算法更加的简洁高效。 2.5 蚁群算法的改进
2.5.1 在初始化信息素后，即根据一定量的最优染色体进行初始信息素增加。
进入蚁群算法后更新方程重写如下：τjnew= τjold+lj c ηj
其中lj表示当前资源节点的任务负载率，为已完成任务和负载总量，负载率低的增加信息素多一点。ηj为评估当前资源节点QoS质量的参数，如带宽，CPU占用率等，QoS状态好的节点增加信息素多一点。c为调整参数。这样设计更新方程既考虑了负载平衡可以使收敛具有一定的方向性，加速收敛。
2.5.2 任务i和资源j的映射概率改写为：
Pij=
其中 j为资源j的当前的状态，表征CPU利用率，可用内存，可用带宽等。 和 为调整参数。需要注意的是因为我们在更新方程中已经根据资源状态（当时包含了负载率）控制了信息素分布，所以现在的 值应较常规蚂蚁算法比较小。收敛加速的双重控制可以更精确的加速收敛，通过不断调整参数达到理想的收敛速度。
2.5.3 为了避免蚁群算法后期常常陷入局部最优解，如果在最大迭代代数的3/4代之前连续N代收敛于同一解，则降低该解所分布资源的信息素为之前的R倍。本文选择R为0.4。
3 算法仿真结果
上述结果表明在所搜索节点比率减小或规模扩大时，本算法优势明显。
4 小结
本文根据云环境的特点，对常用的遗传蚁群融合算法进行改良，提出了比较智能的编码方案；并提出了独特的融合算法；更加动态的定位融合点；根据资源的状态，在算法进入蚁群算法后提出了双重约束，更加精确的控制收敛速度又保证了负载均衡。最终试验证明取得了较好的效果。
参考文献：
[1]刘鹏.云计算的定义和特点[J].中国云计算.
[2]马学彬，温涛，郭权，王刚.一种基于遗传算法的网格任务调度算法[J].东北大学学报.
[3]高曙，郑德.一种基于蚁群算法的任务调度方法.
[4]陈峻，沈洁，秦玲.蚁群算法进行连续参数优化的新途径[J].系统工程理论与实践，2003.
[5]马良，蒋馥.多目标旅行售货员问题的蚂蚁算法求解[J].系统工程理论方法应用，1999.
[6]房秉毅，张云勇，程莹.云计算国内外发展现状分析[J].电信科学，2010，8A：1-5.
[7]王静宇，谭跃生，陈振江.基于遗传蚁群混合算法的网络任务调度研究[J].计算机与信息技术，2008，9（3）：53-55.
[8]张雨，李芳，周涛.云计算环境下予以遗传蚁群算法的任务调度研究.计算机工程与应用，2012.9.
[9]华夏渝，郑骏，胡文心.基于云计算环境的蚁群优化计算资源分配算法.华东师范大学学报，2010.01.
[10]Downey and D.Feitelson.1999.The elusive goal of work-load characterization. In Performance Evaluation Review， pages 14-29.
[11]Albert Greenberg.2008. VL2： a scalable and flexible data center network.51-62，SIGCOMM.
[12]A. Land and A. Doig. 1960.An automatic method of solving discrete programming problem ，Econometrica.pp. 497-520.
[13]Germain R C， RANA O F. 2009. The Convergence of Clouds， Grids， and Autonomics [J]. IEEE.Internet Computing，12（6）：9.
[14]Haifeng Yu， Amin Vahdat. 2002. Minimal Replication Cost for Availability， PODC， Monterey，Califormia， USA.
[15]J. Lockwood， N. McKeown， G. Watson， G. Gibb， P. Hartke， J. Naous， R. Raghuraman， and J. Luo.2007. NetFPGA–An Open Platform for Gigabit-rate Network Switching and Routing. In IEEE International Conference on Microelectronic Systems Education.