0 引言

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

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

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

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

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

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

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

    第一類是基于生物啟發(fā)(Biological Inspiration,，BI)的算法，包括遺傳算法(Genetic Algorithm,，GA),、模因算法(Memetic Algorithm，MA),、獅子算法(Lion Algorithm,，LA)、帝國(guó)競(jìng)爭(zhēng)算法(Imperialist Competitive Algorithm,，ICA),，是在云計(jì)算中與任務(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ū)動(dòng)優(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算法,，由于提出時(shí)間比較早,，在后續(xù)被廣大的學(xué)者們不斷地進(jìn)行優(yōu)化改進(jìn)，各方面的性能已經(jīng)比較完善了,。所以在云計(jì)算中,，任務(wù)調(diào)度的大部分工作是使用GA、ACO,、PSO和SA算法完成的^[2],。

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

1.1 人工蜂群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 帝國(guó)競(jìng)爭(zhēng)算法

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

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

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

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

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

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

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

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

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

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

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

1.3 蝙蝠算法

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

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

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

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

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

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

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

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

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

    文獻(xiàn)[18]將BA算法作了改進(jìn)，融合了遺傳算法并應(yīng)用到了產(chǎn)品的選擇性拆卸序列規(guī)劃問題中,，由于BA中,，個(gè)體缺乏多樣性、變異性,，在蝙蝠種群的更新過程中引入GA的交叉與變異機(jī)制,，增強(qiáng)了算法搜索解的多樣性，最后通過實(shí)驗(yàn)驗(yàn)證了改進(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)行種群初始化，在更新蝙蝠的速度時(shí),，將BA中速度轉(zhuǎn)化為GA的變異概率,，再作為SEBA的速度更新；在進(jìn)行位置更新時(shí)引入GA的交叉和變異算子,，還對(duì)種群中共享的最優(yōu)位置進(jìn)行擾動(dòng)操作,。通過與GA融合過程中的多個(gè)操作，增加了算法的多樣性,，提高了算法的精度,。

1.4 貓群算法

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

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

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

    (1)尋道模式

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

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

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

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

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

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

    (2)跟蹤模式

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

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

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

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

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

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

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

2.1 Cloud Sim

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

2.2 MDC sim

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

2.3 I Can Cloud

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

2.4 Green Cloud

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

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

2.5 各仿真平臺(tái)的比較

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

3 結(jié)論

    對(duì)云計(jì)算作了一個(gè)概述，闡述了云計(jì)算環(huán)境下的任務(wù)調(diào)度模型,，并對(duì)其進(jìn)行了分析,，再由任務(wù)調(diào)度引出四個(gè)比較完善、具有代表性的任務(wù)調(diào)度算法ACO,、GA,、PSO、SA,，分別對(duì)它們做了詳細(xì)的分析,，包括基本思想、算法步驟,、算法特點(diǎn)以及可改進(jìn)的方式,，針對(duì)各個(gè)算法的特點(diǎn)，歸納了一些各個(gè)算法兩兩之間可以進(jìn)行改進(jìn)以及融合方法,；再對(duì)比前面四種算法,，對(duì)比較新穎的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] 張?chǎng)锡?，陳秀萬，肖漢,，等.一種求解旅行商問題的新型帝國(guó)競(jìng)爭(zhēng)算法[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é)報(bào)(自然科學(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é)報(bào)(工學(xué)版)，2018,，52(11)：83-90,，98.

[19] 唐朝偉，李彥,，段青言,，等.自適應(yīng)進(jìn)化蝙蝠算法下的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)[J].中南大學(xué)學(xué)報(bào)(自然科學(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ì)算機(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í)驗(yàn)室,，廣東 珠海519087,；

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

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