论文部分内容阅读
摘 要 云环境作为一种新的网络服务环境，提供大量的网络资源服务，云环境中的资源分配问题受带宽、负载以及响应时间的影响。蚁群算法是一种自适应搜索算法，对组合优化问题的解决发挥了重大的作用，但是其缺陷是容易陷入局部最优以及搜索速度慢。本文提出的蚁群优化算法，将蚁群算法和遗传算法结合起来，能够加快蚁群算法的收敛速度，提高搜索速度，降低云环境下的网络负载，使得云环境下的任务运行时间有效缩短，网络利用率明显提高。
关键词 云环境；蚁群算法；路径优化
中图分类号：TP3 文献标识码：A 文章编号：1671-7597（2014）09-0046-02
云环境是一种新的网络服务环境，具有强大的网络资源，强调网络资源的共享，为用户的信息访问和资源共享提供了方便的信息平台。随着人们对云计算的广泛认可和推广，云计算的规模也在不断的扩大，如何提高云计算的服务性能，增加网络利用率逐渐成为云计算时代社会关注的重点问题。
蚁群算法通过对蚂蚁种群觅食过程的模拟，利用蚂蚁群落在觅食的多条路径上所留下的信息元素的累积来找出最佳的路径。蚁群算法在解决组合优化的优化方面具有其独特的优势。但是，在对规模较大的系统进行处理时，采用蚁群算法往往会陷入局部最优解的缺陷，而且搜索的时间也较长，这就导致在其选择的局部最优路径上的负载过大，网络发生拥堵或者瘫痪。云计算的路径优化实际上就是资源分配的组合方式的最优化选择，通过改进的蚁群算法在云环境下的路径优化，实现云环境下的网络资源优化分配，这对降低网络负载，提高网络访问率和利用率具有重要意义。
1 蚁群算法
蚂蚁群落在寻觅食物的时候在其经过的路径上会留下信息素，蚂蚁们能够对这种信息素进行感知，并根据信息素的强度来决定自身的前进方向。蚂蚁种群的集体觅食行动就形成了一种信息反馈：越短的路径，经过的蚂蚁数量就越多，则遗留下来的信息素强度越高，后来的蚂蚁就越容易选择这条路径。在蚂蚁群落中就是通过这种方式来进行个体间的信息交流，并以最短路径来找到食物。蚁群算法就是在蚁群觅食的行为基础上衍生出来的一种模拟进化算法。
蚂蚁群落中有m只蚂蚁，蚂蚁种群的集合用来表示，第k只蚂蚁觅食的路径用来表示，当蚁群中的所有蚂蚁走完全部路径后，在解集中求出最优解，也就是最优路径，即，第k只蚂蚁的觅食路径为最优解，记做min。蚂蚁群落中的所有蚂蚁经历所有节点后有重新回归到原点，最短路径的第k只蚂蚁为繁殖蚂蚁进行迭代更新后，弧上所遗留的信息素全部挥发的下限值为。
2 云环境服务的资源分配
在云环境中，资源分布规模巨大，十分复杂，在任何时段的某一路线所承载的网络负荷的变化是不确定的，大幅度的负载变化使得资源需求压力增加，现有的资源无法对用户需求很好的满足。但是如果对资源需求的预期分配过高，又有可能造成资源的浪费，是网络资源的利用率大打折扣。物理节点和链路负载的不平衡状态不仅是成本增加，而且资源利用率低，造成浪费，同时还造成了服务满意度的降低。要改变这种不平衡的状态，提高云环境的资源利用率，就需要对资源进行合理的预估和分配。云环境下的网络平台每个单元都有一个主要的任务节点和一个任务分配节点组成。对于任何一个链路，都可定义为三种属性，即费用函数、时延函数和带宽函数。在云环境下对网络路径进行优化，实际上就是在网络平台上，从源点S到终点M，寻找一条最优的路径。在满足带宽约束、时延约束、费用约束三个条件的基础上，τ（Tsm）的取值越小说明资源分配越合理，资源利用率越高。
3 改进的蚁群优化算法云环境下路径优化
蚁群算法从诞生到发展至今，已经有多种蚁群优化的算法，并且在实际的应用中，表现出良好的应用效果。但是从蚁群优化算法的应用结果综合分析，其存在很大的随机性和不确定型，在对大规模的优化组合问题的解决时，常表现出受到局部最优解的限制、收敛速度的缺点，对提高资源利用率具有不利的影响。本文提出的蚁群优化算法的改进方法将遗传算法与蚁群算法结合起来，充分利用了遗传算法在全局搜索中表现出来的快速随即的优势特点，将其在蚁群算法的迭代中融入进来，不仅使原算法的求解高精确性得以保持，而且有效的提高了收敛的速度。在此基础上，将逆转变异策略加以引进，使陷入局部最优的风险得到了有效的规避，使种群的多样性得以良好的维持。
在云环境下对于每个用户提出的资源请求，服务集群会有一个请求任务和资源分配的组合的推荐，其所推荐的组合往往是优化的。改进后的蚁群优化算法在当前的分配策略中进行一个最优的策略的搜索，与此同时，所有与资源状态有所关联，对资源有所影响的因素都通过信息素来进行描述，从而快速的得到最优的预测结果。我们在云环境下蚁群优化算法进行路径的优化改进时，可从对TSP问题和云环境资源分配问题的对比的角度出发，将二者的特征进行关联对比，从中得到改进蚁群算法的启示。我们将TSP问题与云环境资源分配问题各自的特征进行对比，发现二者的差异性主要表现在以下几个方面：1）云环境中的网络资源不具有固定的拓扑结构，需要将资源活动过程中的相互作用来形成拓扑模拟的作用，而TSP问题中的城市间是存在有不等距离的相连并可达的边；2）在云环境中信息素的表示是建立在对资源的计算能力等关联系数的基础之上的，而TSP问题中信息素是通过城市与城市间的不等的距离来进行表示的；3）在云环境中需要利用资源自有的计算能力等属性来对启发信息加以表示。
在此基础上对蚁群算法的改进以现有的资源量为基础，对下个任务执行需要的资源分配量得计算方法进行调整，在某个固定的t时段的信息浓度时，资源自有属性用ηj来表示，用分别表示信息素的重要程度和资源自有属性的重要程度，则计算方法改变为：
（1）
上式中的归属于云计算已有的资源。在云环境下，有任务数量M个，向N个资源上进行分配，通过改进的蚁群优化算法对各资源上对分配的任务的执行所用的最短时间进行计算，实现资源利用路径的优化。这个过程也就是求的下面函数最小值的过程： （2）
在上式中，M是向云计算提出的任务数量，向资源i进行任务的分配，任务数量为mi，其最大值为资源执行任务的上限。
4 仿真实验检验
图1 三种算法执行任务时间对比分析图
本文通过云计算仿真平台，对改进的蚁群算法进行了仿真实验检验，我们采用了轮循调度算法（RR）、蚁群优化算法（ACO）、MACO三种算法进行了资源分配的路径对比，对各种算法执行任务的时间结构进行记录并对比分析。在对相同任务的执行情况的情况下，对三种算法进行任务执行的时间进行记录和对比，结果如图1所示。
从实验结果对比图来看，轮循调度算法执行任务的时间随着任务数量的增加而增加，蚁群优化算法因为初始信息素数量较少的原因，执行任务较慢，随着信息素的不断积累，任务执行速度越来越快。最终结果改进后的蚁群算法比其它算法任务执行效率高。
5 结束语
标准蚁群算法在对大规模的组合优化的过程中，具有收敛速度慢、陷入局部最优化的缺陷，要解决这一难题，本文在对结合云环境的特征以及其与TSP问题的对比的基础上，对标准蚁群算法加以改进，将遗传算法引入进来，将其与蚁群算法相结合，加上逆转变异策略的引入，使标准蚁群算法的缺陷问题得到了有效的解决。本文研究改进蚁群算法在云环境下路径的优化设计通过仿真实验的检验，与RR、MACO两种算法进行任务执行时间的对比，结果表明，改进后的蚁群算法在云环境下达到了路径优化的目的，实现了资源的高效分配，有效的提高了资源的利用率。
参考文献
[1]史恒亮，唐振民.基于蚁群优化算法的云数据库动态路径规划[J].计算机科学，2012（05）.
[2]爱静，郝志峰.双向反馈蚁群算法在网络负载均衡问题的研究[J].计算机工程与应用2011（36）.
[3]丁建立，陈增强，袁著祉.遗传肃反与蚁群算法的融合[J].计算机研究与发展，2011，9（40）：1352-1356.
[4]Nie Yu，Wu Xing.Shortest path problem consi-dering ontime arrival probability[J].Transportation Research Part B：Methodological，2012，43（6）：597-613.
关键词 云环境；蚁群算法；路径优化
中图分类号：TP3 文献标识码：A 文章编号：1671-7597（2014）09-0046-02
云环境是一种新的网络服务环境，具有强大的网络资源，强调网络资源的共享，为用户的信息访问和资源共享提供了方便的信息平台。随着人们对云计算的广泛认可和推广，云计算的规模也在不断的扩大，如何提高云计算的服务性能，增加网络利用率逐渐成为云计算时代社会关注的重点问题。
蚁群算法通过对蚂蚁种群觅食过程的模拟，利用蚂蚁群落在觅食的多条路径上所留下的信息元素的累积来找出最佳的路径。蚁群算法在解决组合优化的优化方面具有其独特的优势。但是，在对规模较大的系统进行处理时，采用蚁群算法往往会陷入局部最优解的缺陷，而且搜索的时间也较长，这就导致在其选择的局部最优路径上的负载过大，网络发生拥堵或者瘫痪。云计算的路径优化实际上就是资源分配的组合方式的最优化选择，通过改进的蚁群算法在云环境下的路径优化，实现云环境下的网络资源优化分配，这对降低网络负载，提高网络访问率和利用率具有重要意义。
1 蚁群算法
蚂蚁群落在寻觅食物的时候在其经过的路径上会留下信息素，蚂蚁们能够对这种信息素进行感知，并根据信息素的强度来决定自身的前进方向。蚂蚁种群的集体觅食行动就形成了一种信息反馈：越短的路径，经过的蚂蚁数量就越多，则遗留下来的信息素强度越高，后来的蚂蚁就越容易选择这条路径。在蚂蚁群落中就是通过这种方式来进行个体间的信息交流，并以最短路径来找到食物。蚁群算法就是在蚁群觅食的行为基础上衍生出来的一种模拟进化算法。
蚂蚁群落中有m只蚂蚁，蚂蚁种群的集合用来表示，第k只蚂蚁觅食的路径用来表示，当蚁群中的所有蚂蚁走完全部路径后，在解集中求出最优解，也就是最优路径，即，第k只蚂蚁的觅食路径为最优解，记做min。蚂蚁群落中的所有蚂蚁经历所有节点后有重新回归到原点，最短路径的第k只蚂蚁为繁殖蚂蚁进行迭代更新后，弧上所遗留的信息素全部挥发的下限值为。
2 云环境服务的资源分配
在云环境中，资源分布规模巨大，十分复杂，在任何时段的某一路线所承载的网络负荷的变化是不确定的，大幅度的负载变化使得资源需求压力增加，现有的资源无法对用户需求很好的满足。但是如果对资源需求的预期分配过高，又有可能造成资源的浪费，是网络资源的利用率大打折扣。物理节点和链路负载的不平衡状态不仅是成本增加，而且资源利用率低，造成浪费，同时还造成了服务满意度的降低。要改变这种不平衡的状态，提高云环境的资源利用率，就需要对资源进行合理的预估和分配。云环境下的网络平台每个单元都有一个主要的任务节点和一个任务分配节点组成。对于任何一个链路，都可定义为三种属性，即费用函数、时延函数和带宽函数。在云环境下对网络路径进行优化，实际上就是在网络平台上，从源点S到终点M，寻找一条最优的路径。在满足带宽约束、时延约束、费用约束三个条件的基础上，τ（Tsm）的取值越小说明资源分配越合理，资源利用率越高。
3 改进的蚁群优化算法云环境下路径优化
蚁群算法从诞生到发展至今，已经有多种蚁群优化的算法，并且在实际的应用中，表现出良好的应用效果。但是从蚁群优化算法的应用结果综合分析，其存在很大的随机性和不确定型，在对大规模的优化组合问题的解决时，常表现出受到局部最优解的限制、收敛速度的缺点，对提高资源利用率具有不利的影响。本文提出的蚁群优化算法的改进方法将遗传算法与蚁群算法结合起来，充分利用了遗传算法在全局搜索中表现出来的快速随即的优势特点，将其在蚁群算法的迭代中融入进来，不仅使原算法的求解高精确性得以保持，而且有效的提高了收敛的速度。在此基础上，将逆转变异策略加以引进，使陷入局部最优的风险得到了有效的规避，使种群的多样性得以良好的维持。
在云环境下对于每个用户提出的资源请求，服务集群会有一个请求任务和资源分配的组合的推荐，其所推荐的组合往往是优化的。改进后的蚁群优化算法在当前的分配策略中进行一个最优的策略的搜索，与此同时，所有与资源状态有所关联，对资源有所影响的因素都通过信息素来进行描述，从而快速的得到最优的预测结果。我们在云环境下蚁群优化算法进行路径的优化改进时，可从对TSP问题和云环境资源分配问题的对比的角度出发，将二者的特征进行关联对比，从中得到改进蚁群算法的启示。我们将TSP问题与云环境资源分配问题各自的特征进行对比，发现二者的差异性主要表现在以下几个方面：1）云环境中的网络资源不具有固定的拓扑结构，需要将资源活动过程中的相互作用来形成拓扑模拟的作用，而TSP问题中的城市间是存在有不等距离的相连并可达的边；2）在云环境中信息素的表示是建立在对资源的计算能力等关联系数的基础之上的，而TSP问题中信息素是通过城市与城市间的不等的距离来进行表示的；3）在云环境中需要利用资源自有的计算能力等属性来对启发信息加以表示。
在此基础上对蚁群算法的改进以现有的资源量为基础，对下个任务执行需要的资源分配量得计算方法进行调整，在某个固定的t时段的信息浓度时，资源自有属性用ηj来表示，用分别表示信息素的重要程度和资源自有属性的重要程度，则计算方法改变为：
（1）
上式中的归属于云计算已有的资源。在云环境下，有任务数量M个，向N个资源上进行分配，通过改进的蚁群优化算法对各资源上对分配的任务的执行所用的最短时间进行计算，实现资源利用路径的优化。这个过程也就是求的下面函数最小值的过程： （2）
在上式中，M是向云计算提出的任务数量，向资源i进行任务的分配，任务数量为mi，其最大值为资源执行任务的上限。
4 仿真实验检验
图1 三种算法执行任务时间对比分析图
本文通过云计算仿真平台，对改进的蚁群算法进行了仿真实验检验，我们采用了轮循调度算法（RR）、蚁群优化算法（ACO）、MACO三种算法进行了资源分配的路径对比，对各种算法执行任务的时间结构进行记录并对比分析。在对相同任务的执行情况的情况下，对三种算法进行任务执行的时间进行记录和对比，结果如图1所示。
从实验结果对比图来看，轮循调度算法执行任务的时间随着任务数量的增加而增加，蚁群优化算法因为初始信息素数量较少的原因，执行任务较慢，随着信息素的不断积累，任务执行速度越来越快。最终结果改进后的蚁群算法比其它算法任务执行效率高。
5 结束语
标准蚁群算法在对大规模的组合优化的过程中，具有收敛速度慢、陷入局部最优化的缺陷，要解决这一难题，本文在对结合云环境的特征以及其与TSP问题的对比的基础上，对标准蚁群算法加以改进，将遗传算法引入进来，将其与蚁群算法相结合，加上逆转变异策略的引入，使标准蚁群算法的缺陷问题得到了有效的解决。本文研究改进蚁群算法在云环境下路径的优化设计通过仿真实验的检验，与RR、MACO两种算法进行任务执行时间的对比，结果表明，改进后的蚁群算法在云环境下达到了路径优化的目的，实现了资源的高效分配，有效的提高了资源的利用率。
参考文献
[1]史恒亮，唐振民.基于蚁群优化算法的云数据库动态路径规划[J].计算机科学，2012（05）.
[2]爱静，郝志峰.双向反馈蚁群算法在网络负载均衡问题的研究[J].计算机工程与应用2011（36）.
[3]丁建立，陈增强，袁著祉.遗传肃反与蚁群算法的融合[J].计算机研究与发展，2011，9（40）：1352-1356.
[4]Nie Yu，Wu Xing.Shortest path problem consi-dering ontime arrival probability[J].Transportation Research Part B：Methodological，2012，43（6）：597-613.