基于混沌蚁群算法的云计算应用优化研究⋆

战 非，张少茹

（1.西安航空学院计算机学院，西安 710077；2.西安交通大学医学院，西安 710049）

基于混沌蚁群算法的云计算应用优化研究⋆

战 非1，张少茹2

（1.西安航空学院计算机学院，西安 710077；2.西安交通大学医学院，西安 710049）

以改进蚁群算法应用在云计算中的不足为目的，讨论了蚁群算法基本原理和云计算下应用的缺陷。提出一种适合云计算的混沌蚁群改进算法，该算法通过Logistic映射产生混沌量，根据混沌遍历性和有界性对蚁群算法初始路径进行混沌初始化，同时加入混沌扰动调整算法信息素更新策略，改进了蚁群算法收敛速度慢和易陷入局部最优的缺点。最后通过CloudSim搭建仿真云环境并进行算法调度实验，通过横向对比标准蚁群算法和Dijkstra算法，证明混沌蚁群算法在执行效率和相对标准差等方面优于其他算法，更加适合于云计算环境。

云计算，蚁群算法，混沌理论，云仿真

0 引言

云计算中面向海量数据的处理，同时以分布式计算为基础，需要计算处理的数据也分布于不同的节点［1-2］。为了提高云计算的效率，合理调度和分配计算节点和资源显得至关重要，最优问题求解算法和调度算法的应用成为提高云服务响应时间的核心。目前常见的模拟退火、遗传算法、神经网络和蚁群算法等都已经被应用在调度问题和求解最优解问题上。

蚁群算法源于蚂蚁种群的觅食行为，在路径规划和资源调度等问题上被广泛应用，但由于蚁群算法初始阶段完全依赖随机性选择路径，易造成算法收敛速度慢的缺点，同时对经过路径信息素更新的均匀分配策略会导致算法易陷入局部最优。针对以上缺点，本文提出了一种混沌蚁群算法，该算法利用混沌的遍历性和有界性对原始算法进行改进，并且对信息素浓度更新策略进行优化，最后通过仿真实验进行验证。

1 蚁群算法分析

1.1 蚁群算法基本原理

蚁群算法来源于自然界蚂蚁种群觅食现象，蚁群在未知食物在什么地方的前提下开始寻找食物，当个体蚂蚁找到食物后，在其经过的路径上会释放挥发性信息素，其浓度表征路径的远近。其他蚂蚁在寻找食物的过程中，在一定范围内感知信息素的强弱，永远朝着信息素浓度较多的方向移动，在整体运行一段时间后，会产生出一条最短的路径，大多数蚂蚁依照此路径运动［3-4］。

1.2 蚁群算法数学模型

开始时期，蚂蚁随机选择一条路径，因为此时各条路径上的信息素浓度基本相同，使用禁忌表来记录蚂蚁k所走过的路径，该表将根据蚂蚁运动的过程实时进行调整，用来表示在t时刻蚂蚁k选择地点j作为目标的状态转移概率：

1.3 蚁群算法的不足

上述标准蚁群算法在云计算环境下执行存在以下缺点：

（1）计算时间相对较长，可能出现停滞现象。单个蚂蚁作为独立个体随机移动，当蚁群数量较大时，在众多路径中快速寻找到最优路径将比较困难［5］。因为在寻径初始阶段，每条路径信息素浓度分布基本相同，要使较优路径上的信息素浓度显著高于其他路径，需要一个较长的进化过程。云计算中对服务响应时间要求较高，算法执行效率较低会大大降低响应时间。

（2）标准蚁群算法采用了信息素均匀分配策略，对经过的所有路径增加相同的信息素浓度，但是忽略了路径本身的重要性。每次路径上信息素浓度的变化会相应产生一个寻找最优路径的候选路径，但候选路径并不能都称为最优路径，这种信息素增量方式会一定程度上造成错误的引导信息，会对算法搜索效率产生影响甚至产生停滞现象。

2 混沌蚁群算法

本文讨论的混沌主要指一种对初始条件非常敏感的时间演化行为，通过混沌运动的特性可以进行搜索的优化。混沌是一种典型的非线性现象，能够按照自己的规律，在一定范围内无重复遍历全部状态同时局限于一个有界范围内［6］。本文正式利用混沌运动的遍历性和有界性去改善蚁群算法路径选择上对完全随机性的依赖。这里提出一种改进算法—混沌蚁群算法（Chaos Ant Colony Optimization）。

2.1 Logistic映射

混沌通常指由确定性方程得到的随机运动状态，常见的混沌系统有Logistic系统、Chen系统、Lorenz系统等［7］。本文的研究和实验都基于Logistic映射，其迭代公式为：

其中 μ 为控制参数，xi+1∈（0，1）。当 3.569 945 6＜μ≤4时，Logistic映射表现出混沌状态；当μ=4时，呈现典型混沌特征，具有随机性、规律性、遍历性和对初值敏感性等。本文将取μ=4，以Logistic映射作为混沌信号发生器。

2.2 混沌理论对蚁群算法的改进

标准蚁群算法难以从大量路径中较快地找到最优路径，收敛速度较慢，难以提供较快的响应。混沌蚁群算法改进策略为：利用混沌运动特性进行搜索的优化和加入混沌扰动更新信息素浓度增量。下面分别进行说明。

2.2.1 混沌初始化

标准蚁群算法初始阶段，蚂蚁对大量路径选择的概率相同，造成难以较短时间找到较优路径［8］。现利用混沌运动遍历性进行改进，首先通过Logistic映射产生与初始路径数目相同的混沌量，用类似载波形式将混沌引入路径，使初始路径表现混沌状态。然后利用混沌变量搜索，进行混沌初始化，从中选择较优路径并且在这些路径上留下不同的信息素量，用此作为初始阶段蚂蚁选择路径的依据。较优路径的数量可根据具体应用设置，不同信息素浓度的取值根据不同策略设置（如根据路径长度不同按比例设置）。

要实现混沌初始化，核心是要让产生的混沌量能够一一对应每一条路径，这里采用排列构造理论实现。假设（1，2，3）代表3个地点，其全排列代表所有路径，总数为3！=6种。构造C的第1位取最小标号，第2位以后递增，设首构造为123，首相量V设为11，结合每一个构造的序号D，可形成DVC表，只要能实现D/C转换，就可以实现混沌信号一一对应至所有路径。以3个地点为例，DVC表如表1所示：

表1 DVC表

要实现表1中D到C的转换，首先要完成D到V的转换，转换公式如下：

其次，由V向C转换可通过V的指针功能进行，本例中以123作为首构造，1，2，3分别对应标号1，标号 2和标号 3。如表 1中序号 5对应的V=v1v2=31向量，最终确定对应构造C的过程为：首先从首构造123中取v1=3对应标号为3的值，也就是123中的3，然后剩下12；然后取v2=1对应剩下的12中的标号为1的值，即1；最后只剩下2。所以由V=31向量得到的C构造为312。

然后通过V构造C，最终实现混沌量xi与构造C的一一对应关系。

2.2.2 混沌扰动调整信息素

为了进一步改进蚁群算法的性能，在进行混沌初始化之后，在信息素浓度更新策略中加入混沌扰动，以避免出现局部最优解而陷入停滞。更新策略如下：

xi，j为根据式（2）产生的混沌量，q 为系数。

2.3 混沌蚁群算法流程

这里提出的混沌蚁群算法（CACO）流程如下：

（1）nc→0，根据式（2）产生混沌量，根据式（3）、式（4）进行混沌初始化，调整初始状态下路径上的信息素浓度，将M个蚂蚁放于N个地点上。其中nc为搜索次数；

（4）当Lk长度小于初始给定路径长度值时，按照式（5）更新当前路径的信息素浓度；

（6）若nc＜预先设置迭代次数或出现都为重复解则跳转至（2）；

（7）输出当前最优解。

3 仿真实验

本次实验采用云计算仿真软件CloudSim进行，其基本流程包括：首先模拟云环境，创建计算节点和分发云任务数及资源；其次设定服务参数，根据目前常规硬件配置和网络带宽创建虚拟机；再次通过混沌蚁群算法进行资源调度，当算法找到符合服务要求的最优路径，提供资源并进行绑定；最后输出仿真结果。

3.1 仿真实验核心过程

CloudSim仿真过程中，调用特定类方法中的仿真参数如带宽（bw），内存（ram），PE 数（pesNumber）等参数的取值根据常规虚拟机硬件水平设置［9-10］。CloudSim调用CACO算法仿真流程图如下页图1所示。

3.2 实验结果

通过在CloudSim中进行实验，设定执行的任务数为20～100，计算节点数为20个。为了更好地说明混沌蚁群算法在云计算中优势，选取了传统调度算法Dijkstra算法及标准蚁群算法，在相同实验参数情况下的执行并进行对比。每种算法执行10次取平均值，算法执行时间对比图和相对标准差结果图如图2和图3所示：

图1 CloudSim仿真流程图

图2 任务执行时间结果图

图3 相对标准差结果图

通过图2可得，当任务数量较少时，3种算法在云环境中执行时间差距较小，但是随着任务量的增加，混沌蚁群算法的执行效率要高于其他两种算法。在实际云环境中，任务数和计算节点数量会指数级增长，混沌蚁群算法的执行效率优势会更大。图3展示了任务分配结果的相对标准差，当任务数增加，混沌蚁群算法的偏差值越来越小并趋于线性渐进，同样优于其他两种算法。通过以上分析，云计算的特点就是并行处理大量任务，通过混沌蚁群算法进行资源调度可以有效地改进标准蚁群算法的缺陷，更加适应常规云计算的要求。

4 结论

本文主要对云计算中的调度算法进行研究，讨论了蚁群算法在云计算中具有的缺陷。改进算法通过引入混沌理论，提出一种适合于云计算的混沌蚁群算法，通过模拟云环境进行仿真实验，证明了混沌蚁群算法能够有效改善标准蚁群算法的不足，更加适合应用在云计算中。

［1］刘正伟，文中领，张海涛.云计算和云数据管理技术［J］.计算机研究与发展，2012，49（S1）：26-31.

［2］陈全，邓倩妮.云计算及其关键技术［J］.计算机应用，2009（9）：2563-2564.

［3］孟湘来.基于云计算的数据中心构建探析［J］.中国企业教育，2012（22）：240-241.

［4］崔杰，兰红星，李陶深.基于Hadoop的海量数据存储平台设计与开发［J］.计算机研究与发展，2012，49（S1）：12-18.

［5］刘鹏.云计算［M］.北京：电子工业出版社，2010：37-45.

［6］王鹏，董静宜.一种云计算架构的实现方法研究［J］.计算机工程与科学，2009，31（S1）：11-13.

［7］王意洁，孙伟东，周松，等.云计算环境下的分布存储关键技术［J］.软件学报，2012，23（4）：962-986.

［8］李文，梁昔明.基于混沌优化和最速下降法的一种混合算法［J］.计算机技术与自动化，2003，22（2）：12-14.

［9］刘军民，高岳林.基于混沌搜的微分进化算法［J］.计算机工程与应用，2008，44（12）：66-68.

［10］BUYYA R，YEO C S，ENUGOPAL S V.Cloud computing and emerging IT platforms：vision，hype and reality for delivering computing as the 5th utility［J］.Future Generation Computer Systems，2009（25）：599-616.

［11］BUYYA R，MERSHED M.GridSim：a toolkit for the modeling and simulation of distributed resource management and scheduling for Grid computing［J］.Concurrency and Computation：Practice and Experience，2002（14）：1175-1220.

［12］LI J W，JIA C F，LI J，CHEN X F.Outsourcing encryption of attribute-based encryption with MapReduce［C］//Information and Communications Security-14th International Conference，ICICS 2012：191-201.

［13］SUDHA G，SADASIVAM，BAKTAVACHALAM G.A novel approach to mutiple sequence alignment using hadoop data grids［C］//Proceedings of the 2010 Workshop on Massive Data Analytics on the Cloud，2010：472-483.

［14］HAO M，WLODARCZYK T W，RONG C.Performance analysis and optimization of map only left outer join［C］//Proceedings of the 2013 27th InternationalConference on Advanced Information Networking and Applications Workshops IEEE Computer Society，2013：625-631.

［15］CHOI J，REAZ A，MUKHEIJEE B.A survey of user behavior in VoD service andbandwidth-saving multicast streaming schemes［J］.Communications Surveys&Tutorials，IEEE，2012，14（1）：156-169.

A Research on Application Optimization of Cloud Computing Based on Chaos Ant Colony Algorithm

ZHAN Fei1，ZHANG Shao-ru2
（1.School of Computer Science，Xi’an Aeronautical Universities，Xi’an 710077，China；2.Health Science Center，Xian Jiaotong University ，Xi’an 710049，China）

According to the characteristics of cloud computing，this paper discusses the basic principle of Ant Colony Algorithm and the application of cloud computing in the cloud environment resource scheduling.An Ant Colony Algorithm suitable for cloud computing is Put forward by Chaos，generated by logistic map chaotic，according to the amount of chaos to chaos initialization path and adding chaotic disturbance information to adjust the pheromone update strategy，an improvement of the limitation of the Ant Colony Algorithm is realized.Through the cloudsim，a cloud simulation environment is built and experiments are conducted.Through horizontal comparisionof the Ant Colony Algorithm and Dijkstra Algorithm，it is proved that the Chaos Ant Colony Algorithm is better than other algorithms in execution efficiency and the relative standard deviation，and thus more suitable for the cloud computing environment.

cloud computing，ACO，chaos theory，cloud simulation

TN919

A

10.3969/j.issn.1002-0640.2017.07.006

1002-0640（2017）07-0025-04

2016-05-05

2016-07-20

国家自然科学基金资助项目（71373203）

战 非（1981- ），男，陕西西安人，硕士。研究方向：软件工程、云计算、通信工程，软件开发、移动互联网应用。