基于混沌蟻群算法的云計(jì)算應(yīng)用優(yōu)化研究?

戰(zhàn) 非，張少茹

（1.西安航空學(xué)院計(jì)算機(jī)學(xué)院，西安 710077；2.西安交通大學(xué)醫(yī)學(xué)院，西安 710049）

基于混沌蟻群算法的云計(jì)算應(yīng)用優(yōu)化研究?

戰(zhàn) 非1，張少茹2

（1.西安航空學(xué)院計(jì)算機(jī)學(xué)院，西安 710077；2.西安交通大學(xué)醫(yī)學(xué)院，西安 710049）

以改進(jìn)蟻群算法應(yīng)用在云計(jì)算中的不足為目的，討論了蟻群算法基本原理和云計(jì)算下應(yīng)用的缺陷。提出一種適合云計(jì)算的混沌蟻群改進(jìn)算法，該算法通過Logistic映射產(chǎn)生混沌量，根據(jù)混沌遍歷性和有界性對蟻群算法初始路徑進(jìn)行混沌初始化，同時(shí)加入混沌擾動(dòng)調(diào)整算法信息素更新策略，改進(jìn)了蟻群算法收斂速度慢和易陷入局部最優(yōu)的缺點(diǎn)。最后通過CloudSim搭建仿真云環(huán)境并進(jìn)行算法調(diào)度實(shí)驗(yàn)，通過橫向?qū)Ρ葮?biāo)準(zhǔn)蟻群算法和Dijkstra算法，證明混沌蟻群算法在執(zhí)行效率和相對標(biāo)準(zhǔn)差等方面優(yōu)于其他算法，更加適合于云計(jì)算環(huán)境。

云計(jì)算，蟻群算法，混沌理論，云仿真

0 引言

云計(jì)算中面向海量數(shù)據(jù)的處理，同時(shí)以分布式計(jì)算為基礎(chǔ)，需要計(jì)算處理的數(shù)據(jù)也分布于不同的節(jié)點(diǎn)［1-2］。為了提高云計(jì)算的效率，合理調(diào)度和分配計(jì)算節(jié)點(diǎn)和資源顯得至關(guān)重要，最優(yōu)問題求解算法和調(diào)度算法的應(yīng)用成為提高云服務(wù)響應(yīng)時(shí)間的核心。目前常見的模擬退火、遺傳算法、神經(jīng)網(wǎng)絡(luò)和蟻群算法等都已經(jīng)被應(yīng)用在調(diào)度問題和求解最優(yōu)解問題上。

蟻群算法源于螞蟻種群的覓食行為，在路徑規(guī)劃和資源調(diào)度等問題上被廣泛應(yīng)用，但由于蟻群算法初始階段完全依賴隨機(jī)性選擇路徑，易造成算法收斂速度慢的缺點(diǎn)，同時(shí)對經(jīng)過路徑信息素更新的均勻分配策略會(huì)導(dǎo)致算法易陷入局部最優(yōu)。針對以上缺點(diǎn)，本文提出了一種混沌蟻群算法，該算法利用混沌的遍歷性和有界性對原始算法進(jìn)行改進(jìn)，并且對信息素濃度更新策略進(jìn)行優(yōu)化，最后通過仿真實(shí)驗(yàn)進(jìn)行驗(yàn)證。

1 蟻群算法分析

1.1 蟻群算法基本原理

蟻群算法來源于自然界螞蟻種群覓食現(xiàn)象，蟻群在未知食物在什么地方的前提下開始尋找食物，當(dāng)個(gè)體螞蟻找到食物后，在其經(jīng)過的路徑上會(huì)釋放揮發(fā)性信息素，其濃度表征路徑的遠(yuǎn)近。其他螞蟻在尋找食物的過程中，在一定范圍內(nèi)感知信息素的強(qiáng)弱，永遠(yuǎn)朝著信息素濃度較多的方向移動(dòng)，在整體運(yùn)行一段時(shí)間后，會(huì)產(chǎn)生出一條最短的路徑，大多數(shù)螞蟻依照此路徑運(yùn)動(dòng)［3-4］。

1.2 蟻群算法數(shù)學(xué)模型

開始時(shí)期，螞蟻隨機(jī)選擇一條路徑，因?yàn)榇藭r(shí)各條路徑上的信息素濃度基本相同，使用禁忌表來記錄螞蟻k所走過的路徑，該表將根據(jù)螞蟻運(yùn)動(dòng)的過程實(shí)時(shí)進(jìn)行調(diào)整，用來表示在t時(shí)刻螞蟻k選擇地點(diǎn)j作為目標(biāo)的狀態(tài)轉(zhuǎn)移概率：

1.3 蟻群算法的不足

上述標(biāo)準(zhǔn)蟻群算法在云計(jì)算環(huán)境下執(zhí)行存在以下缺點(diǎn)：

（1）計(jì)算時(shí)間相對較長，可能出現(xiàn)停滯現(xiàn)象。單個(gè)螞蟻?zhàn)鳛楠?dú)立個(gè)體隨機(jī)移動(dòng)，當(dāng)蟻群數(shù)量較大時(shí)，在眾多路徑中快速尋找到最優(yōu)路徑將比較困難［5］。因?yàn)樵趯匠跏茧A段，每條路徑信息素濃度分布基本相同，要使較優(yōu)路徑上的信息素濃度顯著高于其他路徑，需要一個(gè)較長的進(jìn)化過程。云計(jì)算中對服務(wù)響應(yīng)時(shí)間要求較高，算法執(zhí)行效率較低會(huì)大大降低響應(yīng)時(shí)間。

（2）標(biāo)準(zhǔn)蟻群算法采用了信息素均勻分配策略，對經(jīng)過的所有路徑增加相同的信息素濃度，但是忽略了路徑本身的重要性。每次路徑上信息素濃度的變化會(huì)相應(yīng)產(chǎn)生一個(gè)尋找最優(yōu)路徑的候選路徑，但候選路徑并不能都稱為最優(yōu)路徑，這種信息素增量方式會(huì)一定程度上造成錯(cuò)誤的引導(dǎo)信息，會(huì)對算法搜索效率產(chǎn)生影響甚至產(chǎn)生停滯現(xiàn)象。

2 混沌蟻群算法

本文討論的混沌主要指一種對初始條件非常敏感的時(shí)間演化行為，通過混沌運(yùn)動(dòng)的特性可以進(jìn)行搜索的優(yōu)化?；煦缡且环N典型的非線性現(xiàn)象，能夠按照自己的規(guī)律，在一定范圍內(nèi)無重復(fù)遍歷全部狀態(tài)同時(shí)局限于一個(gè)有界范圍內(nèi)［6］。本文正式利用混沌運(yùn)動(dòng)的遍歷性和有界性去改善蟻群算法路徑選擇上對完全隨機(jī)性的依賴。這里提出一種改進(jìn)算法—混沌蟻群算法（Chaos Ant Colony Optimization）。

2.1 Logistic映射

混沌通常指由確定性方程得到的隨機(jī)運(yùn)動(dòng)狀態(tài)，常見的混沌系統(tǒng)有Logistic系統(tǒng)、Chen系統(tǒng)、Lorenz系統(tǒng)等［7］。本文的研究和實(shí)驗(yàn)都基于Logistic映射，其迭代公式為：

其中 μ 為控制參數(shù)，xi+1∈（0，1）。當(dāng) 3.569 945 6＜μ≤4時(shí)，Logistic映射表現(xiàn)出混沌狀態(tài)；當(dāng)μ=4時(shí)，呈現(xiàn)典型混沌特征，具有隨機(jī)性、規(guī)律性、遍歷性和對初值敏感性等。本文將取μ=4，以Logistic映射作為混沌信號發(fā)生器。

2.2 混沌理論對蟻群算法的改進(jìn)

標(biāo)準(zhǔn)蟻群算法難以從大量路徑中較快地找到最優(yōu)路徑，收斂速度較慢，難以提供較快的響應(yīng)?；煦缦伻核惴ǜ倪M(jìn)策略為：利用混沌運(yùn)動(dòng)特性進(jìn)行搜索的優(yōu)化和加入混沌擾動(dòng)更新信息素濃度增量。下面分別進(jìn)行說明。

2.2.1 混沌初始化

標(biāo)準(zhǔn)蟻群算法初始階段，螞蟻對大量路徑選擇的概率相同，造成難以較短時(shí)間找到較優(yōu)路徑［8］?，F(xiàn)利用混沌運(yùn)動(dòng)遍歷性進(jìn)行改進(jìn)，首先通過Logistic映射產(chǎn)生與初始路徑數(shù)目相同的混沌量，用類似載波形式將混沌引入路徑，使初始路徑表現(xiàn)混沌狀態(tài)。然后利用混沌變量搜索，進(jìn)行混沌初始化，從中選擇較優(yōu)路徑并且在這些路徑上留下不同的信息素量，用此作為初始階段螞蟻選擇路徑的依據(jù)。較優(yōu)路徑的數(shù)量可根據(jù)具體應(yīng)用設(shè)置，不同信息素濃度的取值根據(jù)不同策略設(shè)置（如根據(jù)路徑長度不同按比例設(shè)置）。

要實(shí)現(xiàn)混沌初始化，核心是要讓產(chǎn)生的混沌量能夠一一對應(yīng)每一條路徑，這里采用排列構(gòu)造理論實(shí)現(xiàn)。假設(shè)（1，2，3）代表3個(gè)地點(diǎn)，其全排列代表所有路徑，總數(shù)為3！=6種。構(gòu)造C的第1位取最小標(biāo)號，第2位以后遞增，設(shè)首構(gòu)造為123，首相量V設(shè)為11，結(jié)合每一個(gè)構(gòu)造的序號D，可形成DVC表，只要能實(shí)現(xiàn)D/C轉(zhuǎn)換，就可以實(shí)現(xiàn)混沌信號一一對應(yīng)至所有路徑。以3個(gè)地點(diǎn)為例，DVC表如表1所示：

表1 DVC表

要實(shí)現(xiàn)表1中D到C的轉(zhuǎn)換，首先要完成D到V的轉(zhuǎn)換，轉(zhuǎn)換公式如下：

其次，由V向C轉(zhuǎn)換可通過V的指針功能進(jìn)行，本例中以123作為首構(gòu)造，1，2，3分別對應(yīng)標(biāo)號1，標(biāo)號 2和標(biāo)號 3。如表 1中序號 5對應(yīng)的V=v1v2=31向量，最終確定對應(yīng)構(gòu)造C的過程為：首先從首構(gòu)造123中取v1=3對應(yīng)標(biāo)號為3的值，也就是123中的3，然后剩下12；然后取v2=1對應(yīng)剩下的12中的標(biāo)號為1的值，即1；最后只剩下2。所以由V=31向量得到的C構(gòu)造為312。

然后通過V構(gòu)造C，最終實(shí)現(xiàn)混沌量xi與構(gòu)造C的一一對應(yīng)關(guān)系。

2.2.2 混沌擾動(dòng)調(diào)整信息素

為了進(jìn)一步改進(jìn)蟻群算法的性能，在進(jìn)行混沌初始化之后，在信息素濃度更新策略中加入混沌擾動(dòng)，以避免出現(xiàn)局部最優(yōu)解而陷入停滯。更新策略如下：

xi，j為根據(jù)式（2）產(chǎn)生的混沌量，q 為系數(shù)。

2.3 混沌蟻群算法流程

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

（1）nc→0，根據(jù)式（2）產(chǎn)生混沌量，根據(jù)式（3）、式（4）進(jìn)行混沌初始化，調(diào)整初始狀態(tài)下路徑上的信息素濃度，將M個(gè)螞蟻放于N個(gè)地點(diǎn)上。其中nc為搜索次數(shù)；

（4）當(dāng)Lk長度小于初始給定路徑長度值時(shí)，按照式（5）更新當(dāng)前路徑的信息素濃度；

（6）若nc＜預(yù)先設(shè)置迭代次數(shù)或出現(xiàn)都為重復(fù)解則跳轉(zhuǎn)至（2）；

（7）輸出當(dāng)前最優(yōu)解。

3 仿真實(shí)驗(yàn)

本次實(shí)驗(yàn)采用云計(jì)算仿真軟件CloudSim進(jìn)行，其基本流程包括：首先模擬云環(huán)境，創(chuàng)建計(jì)算節(jié)點(diǎn)和分發(fā)云任務(wù)數(shù)及資源；其次設(shè)定服務(wù)參數(shù)，根據(jù)目前常規(guī)硬件配置和網(wǎng)絡(luò)帶寬創(chuàng)建虛擬機(jī)；再次通過混沌蟻群算法進(jìn)行資源調(diào)度，當(dāng)算法找到符合服務(wù)要求的最優(yōu)路徑，提供資源并進(jìn)行綁定；最后輸出仿真結(jié)果。

3.1 仿真實(shí)驗(yàn)核心過程

CloudSim仿真過程中，調(diào)用特定類方法中的仿真參數(shù)如帶寬（bw），內(nèi)存（ram），PE 數(shù)（pesNumber）等參數(shù)的取值根據(jù)常規(guī)虛擬機(jī)硬件水平設(shè)置［9-10］。CloudSim調(diào)用CACO算法仿真流程圖如下頁圖1所示。

3.2 實(shí)驗(yàn)結(jié)果

通過在CloudSim中進(jìn)行實(shí)驗(yàn)，設(shè)定執(zhí)行的任務(wù)數(shù)為20～100，計(jì)算節(jié)點(diǎn)數(shù)為20個(gè)。為了更好地說明混沌蟻群算法在云計(jì)算中優(yōu)勢，選取了傳統(tǒng)調(diào)度算法Dijkstra算法及標(biāo)準(zhǔn)蟻群算法，在相同實(shí)驗(yàn)參數(shù)情況下的執(zhí)行并進(jìn)行對比。每種算法執(zhí)行10次取平均值，算法執(zhí)行時(shí)間對比圖和相對標(biāo)準(zhǔn)差結(jié)果圖如圖2和圖3所示：

圖1 CloudSim仿真流程圖

圖2 任務(wù)執(zhí)行時(shí)間結(jié)果圖

圖3 相對標(biāo)準(zhǔn)差結(jié)果圖

通過圖2可得，當(dāng)任務(wù)數(shù)量較少時(shí)，3種算法在云環(huán)境中執(zhí)行時(shí)間差距較小，但是隨著任務(wù)量的增加，混沌蟻群算法的執(zhí)行效率要高于其他兩種算法。在實(shí)際云環(huán)境中，任務(wù)數(shù)和計(jì)算節(jié)點(diǎn)數(shù)量會(huì)指數(shù)級增長，混沌蟻群算法的執(zhí)行效率優(yōu)勢會(huì)更大。圖3展示了任務(wù)分配結(jié)果的相對標(biāo)準(zhǔn)差，當(dāng)任務(wù)數(shù)增加，混沌蟻群算法的偏差值越來越小并趨于線性漸進(jìn)，同樣優(yōu)于其他兩種算法。通過以上分析，云計(jì)算的特點(diǎn)就是并行處理大量任務(wù)，通過混沌蟻群算法進(jìn)行資源調(diào)度可以有效地改進(jìn)標(biāo)準(zhǔn)蟻群算法的缺陷，更加適應(yīng)常規(guī)云計(jì)算的要求。

4 結(jié)論

本文主要對云計(jì)算中的調(diào)度算法進(jìn)行研究，討論了蟻群算法在云計(jì)算中具有的缺陷。改進(jìn)算法通過引入混沌理論，提出一種適合于云計(jì)算的混沌蟻群算法，通過模擬云環(huán)境進(jìn)行仿真實(shí)驗(yàn)，證明了混沌蟻群算法能夠有效改善標(biāo)準(zhǔn)蟻群算法的不足，更加適合應(yīng)用在云計(jì)算中。

［1］劉正偉，文中領(lǐng)，張海濤.云計(jì)算和云數(shù)據(jù)管理技術(shù)［J］.計(jì)算機(jī)研究與發(fā)展，2012，49（S1）：26-31.

［2］陳全，鄧倩妮.云計(jì)算及其關(guān)鍵技術(shù)［J］.計(jì)算機(jī)應(yīng)用，2009（9）：2563-2564.

［3］孟湘來.基于云計(jì)算的數(shù)據(jù)中心構(gòu)建探析［J］.中國企業(yè)教育，2012（22）：240-241.

［4］崔杰，蘭紅星，李陶深.基于Hadoop的海量數(shù)據(jù)存儲(chǔ)平臺設(shè)計(jì)與開發(fā)［J］.計(jì)算機(jī)研究與發(fā)展，2012，49（S1）：12-18.

［5］劉鵬.云計(jì)算［M］.北京：電子工業(yè)出版社，2010：37-45.

［6］王鵬，董靜宜.一種云計(jì)算架構(gòu)的實(shí)現(xiàn)方法研究［J］.計(jì)算機(jī)工程與科學(xué)，2009，31（S1）：11-13.

［7］王意潔，孫偉東，周松，等.云計(jì)算環(huán)境下的分布存儲(chǔ)關(guān)鍵技術(shù)［J］.軟件學(xué)報(bào)，2012，23（4）：962-986.

［8］李文，梁昔明.基于混沌優(yōu)化和最速下降法的一種混合算法［J］.計(jì)算機(jī)技術(shù)與自動(dòng)化，2003，22（2）：12-14.

［9］劉軍民，高岳林.基于混沌搜的微分進(jìn)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，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

國家自然科學(xué)基金資助項(xiàng)目（71373203）

戰(zhàn) 非（1981- ），男，陜西西安人，碩士。研究方向：軟件工程、云計(jì)算、通信工程，軟件開發(fā)、移動(dòng)互聯(lián)網(wǎng)應(yīng)用。