0 引言

    云計算是一種依托于虛擬化技術(shù)，通過異構(gòu)技術(shù)將分布于不同地域的各類計算機(jī)資源聚合到云端進(jìn)行統(tǒng)一管理，再利用多樣化的部署方式，以網(wǎng)絡(luò)為載體向用戶提供基礎(chǔ)設(shè)施、平臺、應(yīng)用程序等服務(wù)的計算模式。在云計算中，用戶可以不用購買任何硬件和軟件，只需要支付一定的服務(wù)費(fèi)用，就可以隨時通過任何連接至網(wǎng)絡(luò)的終端設(shè)備獲取到需要的計算、存儲、處理、網(wǎng)絡(luò)等資源。

    而隨著云技術(shù)的發(fā)展和云平臺的廣泛部署，云中的工作流調(diào)度問題成為一個重要的研究課題^[1]，在云計算服務(wù)交付的過程中，由于用戶直接面對的是虛擬機(jī)資源，而真正解決問題的是虛擬機(jī)映射的實(shí)際的物理資源，因此如何將任務(wù)合理分配到資源執(zhí)行是研究者所重點(diǎn)關(guān)注的。

1 多目標(biāo)優(yōu)化任務(wù)調(diào)度算法

    在對未知的探索過程中，問題沒有解決時，人們首先總會想盡一切辦法將問題解決，得到一個準(zhǔn)確可行的解決方案，然后會對該解決方案進(jìn)行優(yōu)化直到“最好”。當(dāng)不惜一切代價將該目標(biāo)優(yōu)化到極限時，往往發(fā)現(xiàn)得到的解決方案雖然能達(dá)到預(yù)期的效果，但是過程中可能會付出比較大的代價。隨著科學(xué)的進(jìn)步，方法的增加，人們開始考慮解決方案的合理性、實(shí)時性、成本等問題。

    隨著科技水平的不斷進(jìn)步，想要使得解決方案的適應(yīng)人群更加廣泛，需要面臨的問題就會更加復(fù)雜，往往需要同時進(jìn)行多個目標(biāo)的優(yōu)化。這種在優(yōu)化設(shè)計中，要求多個目標(biāo)達(dá)到最優(yōu)的問題被稱為多目標(biāo)優(yōu)化或者多約束問題。在這種情況下，局限于于單目標(biāo)優(yōu)化的傳統(tǒng)算法就難以很好地解決問題?；趩l(fā)式思想的智能化算法應(yīng)運(yùn)而生。

    啟發(fā)式思想的智能化算法，通常是人們根據(jù)直觀感受、社會經(jīng)驗或者生物啟發(fā)，然后總結(jié)創(chuàng)新所構(gòu)造出的算法。其思想在于：解決多約束問題時，在可以接受的花費(fèi)的前提下得到一個解決方案，給出盡量滿足多個目標(biāo)優(yōu)化的一個可行解。其核心點(diǎn)在于“多目標(biāo)優(yōu)化”，即對于每一個實(shí)例來說，也許當(dāng)下解并不是它的最優(yōu)解，但卻是多個實(shí)例在盡量滿足需求條件下的極優(yōu)解。

    常用的啟發(fā)式思想的智能化算法包括兩類^[2]：

    第一類是基于生物啟發(fā)(Biological Inspiration，BI)的算法，包括遺傳算法(Genetic Algorithm，GA)、模因算法(Memetic Algorithm，MA)、獅子算法(Lion Algorithm，LA)、帝國競爭算法(Imperialist Competitive Algorithm，ICA)，是在云計算中與任務(wù)調(diào)度相關(guān)的少數(shù)生物啟發(fā)算法。

    第二類是基于群體智能(Swarm Intelligence，SI)的算法，包括蟻群算法(Ant Colony Optimization algorithms，ACO)、粒子群優(yōu)化(Particle Swarm Optimization，PSO)、模擬退火算法(Simulated Annealing Algorithm，SA)、人工蜂群(Artificial Bee Colony Algorithm，ABC)、貓群優(yōu)化(Cat Swarm Optimization Algorithm，CSO)、蝙蝠算法(Bat Algorithm，BA)、風(fēng)驅(qū)動優(yōu)化算法(Wind Driven Optimization Algorithm，WDO)等。

    其中如LA、WDO、BA、ICA已被用于各種優(yōu)化問題，但是在云環(huán)境中，這些算法無法單獨(dú)地完成任務(wù)調(diào)度。另外，由于目前最新提出的方法缺乏考慮負(fù)載平衡、VM遷移、可靠性、執(zhí)行成本和云中工作流調(diào)度的安全目標(biāo)，相比較于ACO、GA、PSO、SA算法，由于提出時間比較早，在后續(xù)被廣大的學(xué)者們不斷地進(jìn)行優(yōu)化改進(jìn)，各方面的性能已經(jīng)比較完善了。所以在云計算中，任務(wù)調(diào)度的大部分工作是使用GA、ACO、PSO和SA算法完成的^[2]。

    要想達(dá)到更好的效果，除了對原有的算法進(jìn)行改進(jìn)、融合，也可以重新發(fā)明創(chuàng)造出新的算法，當(dāng)然難度是有的，但是在有了之前學(xué)者們創(chuàng)造算法的經(jīng)驗，一個新算法的誕生相比之前還是比較容易的。相比較于ACO、GA、PSO、SA這些經(jīng)典的算法，在后續(xù)不斷有新的算法被創(chuàng)造出來。

1.1 人工蜂群算法

    ABC是受到蜂群采集蜂蜜的行為過程所啟發(fā)，由KARABOGA D^[3]提出的一種組合優(yōu)化算法。

    ABC對于給定問題的任何解決方案都由蜜蜂進(jìn)行覓食的蜜源代表，即每一個蜜源代表一個解決方案。算法終止后，蜜量最豐厚(被采集次數(shù)最多)的蜜源就是給定問題的最優(yōu)解。

    算法模擬蜂群的覓食行為，主要有三個概念：蜜源(food sources)、雇傭蜂(Employed foragers)、失業(yè)蜂(Unemployed foragers)，失業(yè)蜂分為觀察蜂和偵察蜂。其中，偵察蜂的主要任務(wù)是尋找蜜源，蜂群采集的蜜源都是偵察蜂發(fā)現(xiàn)的，偵察產(chǎn)生多樣性^[4]；雇傭蜂的主要任務(wù)是招募蜜蜂對蜜源進(jìn)行采集；觀察蜂的主要任務(wù)是有選擇性地響應(yīng)雇傭蜂的招募采蜜。

    ABC主要可以分成三個階段進(jìn)行。

    尋找蜜源：偵察蜂在搜索空間尋找蜜源，找到后變?yōu)楣蛡蚍洌⒏鶕?jù)蜜源的位置到巢穴的距離、蜜量等信息對其進(jìn)行適應(yīng)度分析，一只雇傭蜂對應(yīng)一個蜜源。

    蜜源采集：雇傭蜂回到巢穴后會在特定的區(qū)域向其他蜜蜂分享蜜源信息，觀察蜂根據(jù)雇傭蜂分享的蜜源信息，選擇適應(yīng)度高的蜜源進(jìn)行采集，每進(jìn)行一次采集，蜜源就得到一次優(yōu)化，沒有蜜的蜜源則無法得到優(yōu)化。采集進(jìn)行的次數(shù)越多，蜜源得到的優(yōu)化越多，即解決方案越好。

    放棄蜜源：蜜源在經(jīng)過limit次數(shù)采集沒有得到提升后，則認(rèn)定蜜被采集完，放棄該蜜源，其對應(yīng)的雇傭蜂變?yōu)閭刹旆?，繼續(xù)在搜索空間搜索其他蜜源。

    與蟻群算法直觀地將路徑長短作為解的優(yōu)劣不同，蜂群將每個蜜源被采集的次數(shù)作為解優(yōu)劣判斷的標(biāo)準(zhǔn)。也很好理解，即采集的次數(shù)越多，對應(yīng)蜜量越多，該蜜源就越好，則解越優(yōu)。

    ABC在尋優(yōu)過程中會不斷地和種群內(nèi)的成員分享信息，收斂速度快。

    每個蜜源被采集完后，其對應(yīng)的雇傭蜂會變成偵察蜂繼續(xù)在搜索空間進(jìn)行搜索，在一定程度上降低了算法陷入局部最優(yōu)的概率。

    針對算法的靈活問題，文獻(xiàn)[5]提出一種自適應(yīng)人工蜂群算法，其工作流與ABC算法相似，在蜜蜂分配技術(shù)和動態(tài)蜜蜂角色分配邏輯上作出了改進(jìn)，根據(jù)需要可以在允許的范圍內(nèi)，增加或者是減少雇傭蜂的數(shù)量，通過更加動態(tài)的蜜蜂資源分配，提高了算法的效率，并且使解的適應(yīng)值提高了8%左右。

    在ABC算法中，如何設(shè)計適應(yīng)度函數(shù)、種群更新過程以及如何避免局部最優(yōu)是影響算法效率和收斂性的關(guān)鍵。為了提高算法的全局搜索能力，文獻(xiàn)[6]在ABC算法的基礎(chǔ)上引入遺傳算法中的交叉算子，提出了一種基于交叉的全局人工蜂群算法，有效地提高了算法的搜索效率，避免陷入局部最優(yōu)。

    針對ABC容易陷入局部最優(yōu)的問題，文獻(xiàn)[7]提出了一種改進(jìn)的具有先進(jìn)搜索能力的人工蜂群算法，通過增加搜索次數(shù)和引入擾動因子來提高ABC算法的搜索能力。偵察產(chǎn)生多樣性，偵察次數(shù)越多，產(chǎn)生的解就越加多樣，就越不容易陷入局部最優(yōu)。

1.2 帝國競爭算法

    ICA是一種受到帝國主義競爭過程所啟發(fā)，由ATASHPAZ-GARGARI E和LUCAS C^[8]提出的一種社會政治類型的進(jìn)化算法，可用于解決連續(xù)優(yōu)化問題^[9]。

    ICA對于給定問題的任何解決方案都由一個國家代表，即每一個國家都代表一個解決方案。算法結(jié)束后，最強(qiáng)大的國家就是給定問題的最優(yōu)解。

    ICA主要分為幾個階段進(jìn)行：

    帝國形成：對每個國家進(jìn)行適應(yīng)度計算，取適應(yīng)度較高的作為殖民國家，其余為殖民地，并根據(jù)殖民國家的適應(yīng)度高低，將殖民地分配給殖民國家，適應(yīng)度越高分配的殖民地越多，由每個殖民國家及其殖民地一起組成帝國。一個殖民國家對應(yīng)一個帝國，每個帝國的適應(yīng)度為組成它的成員的適應(yīng)度的總和。

    同化和革命：在帝國中，殖民地會受到殖民國家的影響，逐漸地被同化，趨于其殖民國家，提高自身適應(yīng)度，同樣，殖民地也可能反抗統(tǒng)治進(jìn)行革命，若革命成功則取代原殖民國家，形成一個新的帝國。

    帝國競爭：當(dāng)?shù)蹏鴥?nèi)部同化完成后，要想繼續(xù)壯大勢力，就需要和其他帝國競爭，此時比較帝國的適應(yīng)度，即適應(yīng)度低的被適應(yīng)度高的帝國所吞噬，其殖民地全部轉(zhuǎn)移到競爭勝利的帝國中，直至全部國家都在同一個帝國中，此時算法終止，該帝國即為給定問題的最優(yōu)解決方案。

    ICA算法的優(yōu)點(diǎn)是簡單、省時；缺點(diǎn)是帝國的每一代都進(jìn)行競爭，這導(dǎo)致有些殖民地還沒有被其帝國同化就被其他帝國競爭奪走了，加快了算法早熟。

    ICA最大的特點(diǎn)在于：(1)同化：目的在于增加殖民國家對殖民地的影響，提升帝國內(nèi)國家的求解質(zhì)量；(2)革命：目的在于提升算法解的多樣性，能夠減少算法陷入局部最優(yōu)的可能性。

    文獻(xiàn)[10]通過研究FFSP提出一種改進(jìn)了的帝國主義競爭算法。在帝國主義競爭結(jié)束后，通過增加群體改革操作，提高算法群的全局搜索能力，用隨機(jī)解代替各帝國中最弱的群體，提高算法的優(yōu)化性能；然后在ICA的帝國競爭中，采取保留精英個體策略，當(dāng)?shù)蹏鴥?nèi)沒有殖民地時，將該帝國當(dāng)作殖民地進(jìn)入到其他帝國中，因為精英個體有利于算法的收斂。通過改進(jìn)有效地避免了算法過早收斂并陷入局部極值的問題。

    文獻(xiàn)[11]將ICA應(yīng)用到了多目標(biāo)低碳并行機(jī)調(diào)度的問題中，為了提高算法的求解質(zhì)量，采用了新策略進(jìn)行帝國的初始化，將成本考慮到初始化的影響因素中；在帝國同化殖民地的過程中，引入了自適應(yīng)同化影響因子和兩次同化操作，實(shí)現(xiàn)了自適應(yīng)殖民地革命；新添了一種帝國聯(lián)合的競爭方式；最后，為了防止算法早熟，將每代都進(jìn)行競爭改進(jìn)為每隔N代進(jìn)行競爭。通過實(shí)驗驗證了改進(jìn)ICA在求解低碳PMSP方面的搜索優(yōu)勢。

    文獻(xiàn)[12]將ICA作了改進(jìn)，應(yīng)用到現(xiàn)實(shí)工業(yè)中存在的鏈重入流車間調(diào)度問題中。文獻(xiàn)認(rèn)為具有相同收斂性的帝國主義者，應(yīng)該分配相同數(shù)量的殖民地，并以此運(yùn)用新的戰(zhàn)略來初始化帝國；在實(shí)施殖民地革命和帝國主義競爭過程中，為了避免了在弱國上浪費(fèi)資源，只有帝國主義和一些好的殖民地在革命的步驟中被選擇，通過實(shí)驗表明了改進(jìn)后的帝國主義革命在使用使性能方面有顯著的提高。

1.3 蝙蝠算法

    BA是受到蝙蝠在黑夜中依靠超聲波進(jìn)行覓食的啟發(fā)，由Yang Xinshe^[13]所提出的一種元啟發(fā)式算法，可用于解決非線性的全局優(yōu)化問題。

    蝙蝠不像螞蟻，沒有視力全靠慣性運(yùn)動，相反，一些蝙蝠有很好的視力，大多數(shù)蝙蝠也有非常敏感的感覺。但是其主要特點(diǎn)是依靠超聲波進(jìn)行覓食，所以，BA只關(guān)注蝙蝠的回聲定位和相關(guān)行為，并聲明以下3個理想化的規(guī)則^[14]：

    (1)所有蝙蝠都使用回聲定位來感知距離，以某種方式區(qū)別獵物與背景障礙。

    (2)蝙蝠在位置x以速度v隨機(jī)飛行，以發(fā)出固定的頻率、可變的波長和音量的脈沖(超聲波)來搜索獵物。在搜索過程中，蝙蝠能根據(jù)距離目標(biāo)的鄰近程度，自動調(diào)整發(fā)射的脈沖波長（或頻率）和發(fā)射率。

    (3)假設(shè)在靠近獵物過程中，響度在一個設(shè)定的范圍內(nèi)變化。

    BA對于給定問題的任何解決方案都由進(jìn)行覓食的蝙蝠所代表，即一只蝙蝠代表一個解決方案，最早到達(dá)目標(biāo)點(diǎn)的蝙蝠就是給定問題的最優(yōu)解。

    蝙蝠群體隨機(jī)散布在搜索空間中的各個位置，每只蝙蝠發(fā)出不同的脈沖頻率來搜尋獵物，開始采用較低的脈沖頻度和較大的脈沖響度，一旦發(fā)現(xiàn)了獵物，則開始向獵物靠近，在靠近目標(biāo)的過程中不斷變化脈沖的波長、發(fā)射頻率和響度(降低響度^[15]，增加發(fā)射頻率)，同時通過和處于較優(yōu)位置蝙蝠的比較，在向獵物移動的同時向較優(yōu)位置的蝙蝠移動，這樣通過多次搜索和移動后，當(dāng)達(dá)到終止條件時(達(dá)到最大迭代次數(shù)、到達(dá)目標(biāo)點(diǎn))，程序結(jié)束^[16]。

    算法的優(yōu)點(diǎn)是分布式、并行性、模型簡單、收斂速度快。缺點(diǎn)是個體缺乏多樣性，易陷入局部最優(yōu)。

    為了了解BA的性能，文獻(xiàn)[17]將BA應(yīng)用到一些眾所周知的、困難但多樣的基準(zhǔn)設(shè)計問題進(jìn)行測試，通過測試結(jié)果發(fā)現(xiàn)，BA能夠準(zhǔn)確對問題進(jìn)行求解，但是算法中參數(shù)的微調(diào)會影響B(tài)A算法的性能。

    文獻(xiàn)[18]將BA算法作了改進(jìn)，融合了遺傳算法并應(yīng)用到了產(chǎn)品的選擇性拆卸序列規(guī)劃問題中，由于BA中，個體缺乏多樣性、變異性，在蝙蝠種群的更新過程中引入GA的交叉與變異機(jī)制，增強(qiáng)了算法搜索解的多樣性，最后通過實(shí)驗驗證了改進(jìn)后算法相比改進(jìn)前的的優(yōu)越性。

    文獻(xiàn)[19]將BA與GA進(jìn)行了融合改進(jìn)，提出了一種自適應(yīng)進(jìn)化蝙蝠算法(Self-adaptive Evolution Bat Algorithm，SEBA)，并應(yīng)用到了網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的問題中，采用標(biāo)簽傳播的方式進(jìn)行種群初始化，在更新蝙蝠的速度時，將BA中速度轉(zhuǎn)化為GA的變異概率，再作為SEBA的速度更新；在進(jìn)行位置更新時引入GA的交叉和變異算子，還對種群中共享的最優(yōu)位置進(jìn)行擾動操作。通過與GA融合過程中的多個操作，增加了算法的多樣性，提高了算法的精度。

1.4 貓群算法

    BA是CSO是受到貓的行為啟發(fā)，由CHU S C等人^[20]提出的一種群智能優(yōu)化算法。

    CSO用貓與貓的行為模型來構(gòu)造給定問題的解決方案，即一只貓的位置代表一個解決方案，最早到達(dá)目標(biāo)點(diǎn)的貓就是給定問題的最優(yōu)解。

    CSO根據(jù)貓的行為構(gòu)建了兩種子模式：尋道(搜索)模式和跟蹤模式。并定義了一種混合比例(MR)，將搜索模式和跟蹤模式結(jié)合在一起融入到算法中，搜索模式尋找目標(biāo)點(diǎn)，再用跟蹤模式靠近。

    (1)尋道模式

    尋道模式也可以稱之為搜索模式，其主要目的是在搜索空間內(nèi)搜索目標(biāo)，并確定下一次可能移動的位置。

    在尋道模式中定義了4個因素：尋優(yōu)內(nèi)存池(SMP)、所選維度的尋優(yōu)范圍(SRD)、改變維度的計數(shù)(CDC)和自定位考慮(SPC)^[21]。

    SMP用于定義每只貓的尋道內(nèi)存大小，即搜尋記憶大小，能夠體現(xiàn)出貓能夠搜尋到的位置點(diǎn)的數(shù)量，并且根據(jù)SMP中每個點(diǎn)的適應(yīng)度大小選擇一個最好的點(diǎn)。SMP越大，能搜索到的點(diǎn)的數(shù)量就越多，篩選出的點(diǎn)就越接近全局最優(yōu)；SMP越小，能搜索到的點(diǎn)的數(shù)量就越少，篩選出來的點(diǎn)有很大概率是局部最優(yōu)值。所以，SMP影響到算法的多樣性。

    SRD聲明所選維度的可變比率。如果選擇一個維度進(jìn)行變異，其變異的范圍由SRD決定，它為所選維度提供了更改的邊界條件。

    CDC指每只貓將要變異的維數(shù)的個數(shù),其值是一個從0到總維數(shù)之間的隨機(jī)值。

    SPC是一個布爾變量，它決定貓是否將當(dāng)前搜索到的位置作為下次移動的候選點(diǎn)之一。

    (2)跟蹤模式

    跟蹤模式的主要目的是通過更新貓的速度和位置信息，不斷地向?qū)さ滥Ｊ街写_定的點(diǎn)進(jìn)行移動，與PSO的移動相似。算法的特點(diǎn)是易陷入局部最優(yōu)，收斂速度慢。

    文獻(xiàn)[22]將CSO作了改進(jìn)并提出了一種新的多目標(biāo)貓群優(yōu)化算法。采用cat映射進(jìn)行初始化人口的個體，并且對CSO中搜索貓和跟蹤貓進(jìn)行靈活的分配，將一部分的貓應(yīng)用于搜索模式，另一部分非隨機(jī)應(yīng)用于跟蹤模式。經(jīng)過實(shí)驗驗證，改進(jìn)后的算法在迭代過程中可以避免陷入局部最優(yōu)，有效地提高了算法的搜索能力。

    文獻(xiàn)[23]將CSO進(jìn)行改進(jìn)并與SA融合后，對連續(xù)化的CSO進(jìn)行離散化操作應(yīng)用到工具約束下多目標(biāo)拆卸線平衡問題中。針對CSO易陷入局部最優(yōu)的缺點(diǎn)，引入SA中的Metropolis準(zhǔn)則，對貓群中完成尋優(yōu)操作的個體進(jìn)行擾動，使其在當(dāng)前目標(biāo)的周圍繼續(xù)進(jìn)行尋優(yōu)操作，增加解的多樣性，最后在位置更新時采取精英保留策略。經(jīng)過實(shí)驗驗證，改進(jìn)后的算法有效增強(qiáng)了算法的全局搜索能力，并且加速了算法的收斂。

2 實(shí)驗環(huán)境

    理論離不開實(shí)驗，理論是否正確要靠合理、正確、足夠多的實(shí)驗對其進(jìn)行驗證。而要做實(shí)驗，除了必要的理論知識，首先要考慮的就是理論所要實(shí)際應(yīng)用的實(shí)驗環(huán)境。

    由于云計算是一個商業(yè)性的計算模式，因此直接將實(shí)驗投入到云環(huán)境中進(jìn)行是不太理智的，另外，專門為一個實(shí)驗搭建一個云環(huán)境也不太現(xiàn)實(shí)。因為云環(huán)境通常都很復(fù)雜，再加上成本比較高，并且做任務(wù)調(diào)度實(shí)驗，任務(wù)數(shù)比較多，需要進(jìn)行大量的計算，所以在實(shí)驗階段，大多都使用模型和仿真工具來模擬云環(huán)境并進(jìn)行必要的實(shí)驗^[24]。在仿真實(shí)驗做出的效果比較理想或者達(dá)到某一標(biāo)準(zhǔn)時, 再將實(shí)驗方法放到實(shí)際的云計算環(huán)境中來進(jìn)行測試。采用仿真實(shí)驗?zāi)M可以節(jié)省成本，避免占用實(shí)際的云計算環(huán)境資源。

    目前主流的云計算仿真平臺(模擬器)包括Cloud Sim、MDC Sim、I Can Cloud、Green Cloud等。

2.1 Cloud Sim

    Cloud Sim是2002年由墨爾本大學(xué)的Grids網(wǎng)格實(shí)驗室基于早期的Grid Sim的版本開發(fā)出來的一個可擴(kuò)展的模擬工具包^[25]，可以對云計算的系統(tǒng)和應(yīng)用程序提供實(shí)驗仿真環(huán)境，以進(jìn)行建模和模擬。后續(xù)基于Cloud Sim還研發(fā)出了相關(guān)產(chǎn)品：(1)有友好的圖形用戶界面，能夠?qū)?shí)驗?zāi)M與編程代碼分離，可以進(jìn)行快速模擬設(shè)置以及增強(qiáng)圖形結(jié)果顯示的Cloud Analyst；(2)可以同時運(yùn)行多個模擬，增強(qiáng)模擬結(jié)果并將其顯示在表格和圖表中的Cloud Reports；(3)方便教學(xué)的Teach Cloud。Cloud Sim是當(dāng)前比較成熟的一個云計算仿真平臺。

2.2 MDC sim

    MDC Sim是2009年LIM S H等人^[26]提出的一個多層數(shù)據(jù)中心的仿真平臺，它被設(shè)計成可插入的三層體系結(jié)構(gòu)，分別為通信層、內(nèi)核層、用戶層。其特點(diǎn)是操作者可以在它的三層體系結(jié)構(gòu)中靈活地試驗不同的設(shè)計方案，能夠在實(shí)際工作中分析各個負(fù)載的性能和功耗，可以對大型的多層數(shù)據(jù)中心進(jìn)行建模和仿真。

2.3 I Can Cloud

    I Can Cloud是采用了Amazon的云計算基礎(chǔ)設(shè)施及服務(wù)，在其之上提出的一個靈活可擴(kuò)展的云計算仿真平臺^[27]，重點(diǎn)對象為大規(guī)模的實(shí)驗，可以對現(xiàn)有的或者是沒有的云架構(gòu)進(jìn)行建模和模擬；另外，其hyper visor模型允許用戶集成任何云代理策略來管理一組完全可定制的虛擬機(jī)，用戶完全可以靈活地定制不同的代理策略。

2.4 Green Cloud

    Green Cloud是2012年KLIAZOVICH D^[28]等人基于包級網(wǎng)絡(luò)模擬器NS2擴(kuò)展的一個可以對云計算數(shù)據(jù)中心進(jìn)行模擬的綠色仿真平臺，其關(guān)注的重點(diǎn)是計算和通信過程中能量的消耗。

與其他的云計算仿真平臺有所不同的是，在云系統(tǒng)工作過程中，Green Cloud會將數(shù)據(jù)中心中計算組件、通信元素、工作負(fù)載等各個部分消耗的能源信息進(jìn)行提取、聚合，然后以一種全新的方式展現(xiàn)出來。因為是包級別的模擬，所以在通信過程中能很好地捕捉到對象之間的交互。

2.5 各仿真平臺的比較

    對以上4種主流的云計算仿真平臺(模擬器)在提出時間、編程語言、平臺、可用性等方面做一個對比，如表1所示。

3 結(jié)論

    對云計算作了一個概述，闡述了云計算環(huán)境下的任務(wù)調(diào)度模型，并對其進(jìn)行了分析，再由任務(wù)調(diào)度引出四個比較完善、具有代表性的任務(wù)調(diào)度算法ACO、GA、PSO、SA，分別對它們做了詳細(xì)的分析，包括基本思想、算法步驟、算法特點(diǎn)以及可改進(jìn)的方式，針對各個算法的特點(diǎn)，歸納了一些各個算法兩兩之間可以進(jìn)行改進(jìn)以及融合方法；再對比前面四種算法，對比較新穎的ACO、ICA、BA、CSO做了分析，包括算法的基本思想、實(shí)現(xiàn)步驟、特點(diǎn)和可改進(jìn)的方式。

參考文獻(xiàn)

[1] WU F，WU Q，TAN Y. Workflow scheduling in cloud：a survey[J]. The Journal of Super Computing，2015，71(9)：3373-3418.

[2] SINGH P，DUTTA M，AGGARWAL N.A review of task scheduling based on meta-heuristics approach in cloud computing[J].Knowledge & Information Systems，2017，52(1)：1-51.

[3] KARABOGA D.An idea based on honey bee swarm for numerical optimization[R].Kayseri: Engineering Faculty Computer Engineering Department，Ereiyes University，2005.

[4] KARABOGA D，GORKEMLI B，OZTURK C，et al.A comprehensive survey：artificial bee colony(ABC) algorithm and applications[J].Artificial Intelligence Review，2014，42(1)：21-57.

[5] REKABY A，YOUSSIF A A，ELDIN A S.Introducing adaptive artificial bee colony algorithm and using it in solving traveling salesman problem[C].2013 Science and Information Conference，2013：502-506.

[6] ZHANG P.Research on global artificial bee colony algorithm based on crossover[C].2017 8th IEEE International Conference on Software Engineering and Service Science(ICSESS)，2017：249-252.

[7] WANG Y，YOU J，HANG J，et al.An improved artificial bee colony(ABC) algorithm with advanced search ability[C].2018 8th International Conference on Electronics Information and Emergency Communication(ICEIEC)，2018：91-94.

[8] ATASHPAZ-GARGARI E，LUCAS C.Imperialist competitive algorithm：an algorithm for optimization inspired by imperialistic competition[C].IEEE Congress on Evolutionary Computation，CEC 2007，2007.

[9] 張鑫龍，陳秀萬，肖漢，等.一種求解旅行商問題的新型帝國競爭算法[J].控制與決策，2016，31(4)：586-592.

[10] YUE S，SHUO L，TAN L，et al.Improved imperialist competitive algorithm for flexible flow shop scheduling[C].2017 9th International Conference on Modelling，Identification and Control(ICMIC)，2017：169-174.

[11] 雷德明，潘子肖，張清勇.多目標(biāo)低碳并行機(jī)調(diào)度研究[J].華中科技大學(xué)學(xué)報(自然科學(xué)版)，2018，46(8)：104-109.

[12] CHENG Y，LEI D.An improved imperialist competitive algorithm for reentrant flow shop scheduling[C].2018 37th Chinese Control Conference(CCC)，2018：2206-2211.

[13] YANG X.A new meta heuristic bat-inspired algorithm[J].Computer Knowledge and Technology，2010，284：65-74.

[14] YANG X S.Bat Algorithm for muti-objective optimisation[J].International Journal of Bio-Inspired Computation，2012，3(5)：267-274(8).

[15] SINGH D，SALGOTRA R，SINGH U.A novel modified bat algorithm for global optimization[C].2017 International Conference on Innovations in Information，Embedded and Communication Systems(ICIIECS)，2017：1-5.

[16] 彭敏.基于差分變異蝙蝠算法的裝配序列規(guī)劃方法研究[D].湘潭：湘潭大學(xué)，2014.

[17] YANG X S，GANDOMI A H.Bat algorithm：a novel approach for global engineering optimization[J].Engineering Computations，2012，29(5)：464-483.

[18] 朱卓悅，徐志剛，沈衛(wèi)東，等.基于遺傳蝙蝠算法的選擇性拆卸序列規(guī)劃[J].浙江大學(xué)學(xué)報(工學(xué)版)，2018，52(11)：83-90，98.

[19] 唐朝偉，李彥，段青言，等.自適應(yīng)進(jìn)化蝙蝠算法下的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)[J].中南大學(xué)學(xué)報(自然科學(xué)版)，2018，49(1)：115-123.

[20] CHU S C，TSAI P，PAN J S.Cat swarm optimization[J].Lecture Notes in Computer Science，2006，6：854-858.

[21] TSAI P，ISTANDA V.Review on cat swarm optimization algorithms[C].2013 3rd International Conference on Consumer Electronics，Communications and Networks，2013：564-567.

[22] LUO C，GUO Y，MA Y，et al.A non-random mutiobjective cat swarm optimization algorithm based on CAT MAP[C].2016 International Conference on Machine Learning and Cybernetics(ICMLC)，2016：29-35.

[23] 鄒賓森，張則強(qiáng)，蔡寧，等.工具約束下多目標(biāo)拆卸線平衡問題的貓群模擬退火算法[J].計算機(jī)集成制造系統(tǒng)，2018，24(9)：82-94.

[24] BAHWAIRETH K，TAWALBEH L，BENKHELIFA E，et al.Experimental comparison of simulation tools for efficient cloud and mobile cloud computing applications[J].EURASIP Journal on Information Security，2016 (1)：15.

[25] CALHEIROS R N，RANJAN R，BELOGLAZOV A，et al.CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software：Practice and Experience，2011，41(1)：23-50.

[26] LIM S H，SHARMA B，NAM G，et al.MDCSim：a mutitier data center simulation，platform[C].2009 IEEE International Conference on Cluster Computing and Workshops.IEEE，2009.

[27] ALBERTO N，V?魣ZQUEZ-POLETTI J L，CAMINERO A C，et al.I Can Cloud：a flexible and scalable Cloud infrastructure simulator[J].Journal of Grid Computing，2012，10(1)：185-209.

[28] KLIAZOVICH D，BOUVRY P，KHAN S U.Green Cloud：a packet-level simulator of energy-aware cloud computing data centers[J].Journal of Super Computing，2012，62(3)：1263-1283.

作者信息:

楊  戈1，2，3，趙  鑫1，2，黃  靜1，2

(1.北京師范大學(xué)珠海分校 智能多媒體技術(shù)重點(diǎn)實(shí)驗室，廣東 珠海519087；

2.北京師范大學(xué)珠海分校 信息技術(shù)學(xué)院，廣東 珠海519087；

3.北京大學(xué)深圳研究生院 深圳物聯(lián)網(wǎng)智能感知技術(shù)工程實(shí)驗室，廣東 深圳518055)