0 引言

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

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

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

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

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

    啟發(fā)式思想的智能化算法，通常是人們根據(jù)直觀感受、社會(huì)經(jīng)驗(yàn)或者生物啟發(fā)，然后總結(jié)創(chuàng)新所構(gòu)造出的算法。其思想在于：解決多約束問(wèn)題時(shí)，在可以接受的花費(fèi)的前提下得到一個(gè)解決方案，給出盡量滿足多個(gè)目標(biāo)優(yōu)化的一個(gè)可行解。其核心點(diǎn)在于“多目標(biāo)優(yōu)化”，即對(duì)于每一個(gè)實(shí)例來(lái)說(shuō)，也許當(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)化問(wèn)題，但是在云環(huán)境中，這些算法無(wú)法單獨(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)造出來(lái)。

1.1 人工蜂群算法

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

    ABC對(duì)于給定問(wèn)題的任何解決方案都由蜜蜂進(jìn)行覓食的蜜源代表，即每一個(gè)蜜源代表一個(gè)解決方案。算法終止后，蜜量最豐厚(被采集次數(shù)最多)的蜜源就是給定問(wèn)題的最優(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)化，沒(méi)有蜜的蜜源則無(wú)法得到優(yōu)化。采集進(jìn)行的次數(shù)越多，蜜源得到的優(yōu)化越多，即解決方案越好。

    放棄蜜源：蜜源在經(jīng)過(guò)limit次數(shù)采集沒(méi)有得到提升后，則認(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)過(guò)程中會(huì)不斷地和種群內(nèi)的成員分享信息，收斂速度快。

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

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

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

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

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

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

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

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

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

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

    文獻(xiàn)[11]將ICA應(yīng)用到了多目標(biāo)低碳并行機(jī)調(diào)度的問(wèn)題中，為了提高算法的求解質(zhì)量，采用了新策略進(jìn)行帝國(guó)的初始化，將成本考慮到初始化的影響因素中；在帝國(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)。通過(guò)實(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)度問(wèn)題中。文獻(xiàn)認(rèn)為具有相同收斂性的帝國(guó)主義者，應(yīng)該分配相同數(shù)量的殖民地，并以此運(yùn)用新的戰(zhàn)略來(lái)初始化帝國(guó)；在實(shí)施殖民地革命和帝國(guó)主義競(jìng)爭(zhēng)過(guò)程中，為了避免了在弱國(guó)上浪費(fèi)資源，只有帝國(guó)主義和一些好的殖民地在革命的步驟中被選擇，通過(guò)實(shí)驗(yàn)表明了改進(jìn)后的帝國(guó)主義革命在使用使性能方面有顯著的提高。

1.3 蝙蝠算法

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

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

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

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

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

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

    蝙蝠群體隨機(jī)散布在搜索空間中的各個(gè)位置，每只蝙蝠發(fā)出不同的脈沖頻率來(lái)搜尋獵物，開始采用較低的脈沖頻度和較大的脈沖響度，一旦發(fā)現(xiàn)了獵物，則開始向獵物靠近，在靠近目標(biāo)的過(guò)程中不斷變化脈沖的波長(zhǎng)、發(fā)射頻率和響度(降低響度^[15]，增加發(fā)射頻率)，同時(shí)通過(guò)和處于較優(yōu)位置蝙蝠的比較，在向獵物移動(dòng)的同時(shí)向較優(yōu)位置的蝙蝠移動(dòng)，這樣通過(guò)多次搜索和移動(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ì)問(wèn)題進(jìn)行測(cè)試，通過(guò)測(cè)試結(jié)果發(fā)現(xiàn)，BA能夠準(zhǔn)確對(duì)問(wèn)題進(jìn)行求解，但是算法中參數(shù)的微調(diào)會(huì)影響B(tài)A算法的性能。

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

1.4 貓群算法

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

    CSO用貓與貓的行為模型來(lái)構(gòu)造給定問(wèn)題的解決方案，即一只貓的位置代表一個(gè)解決方案，最早到達(dá)目標(biāo)點(diǎn)的貓就是給定問(wè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ù)量就越少，篩選出來(lái)的點(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)跟蹤模式

    跟蹤模式的主要目的是通過(guò)更新貓的速度和位置信息，不斷地向?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)過(guò)實(shí)驗(yàn)驗(yàn)證，改進(jìn)后的算法在迭代過(guò)程中可以避免陷入局部最優(yōu)，有效地提高了算法的搜索能力。

    文獻(xiàn)[23]將CSO進(jìn)行改進(jìn)并與SA融合后，對(duì)連續(xù)化的CSO進(jìn)行離散化操作應(yīng)用到工具約束下多目標(biāo)拆卸線平衡問(wèn)題中。針對(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)過(guò)實(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)階段，大多都使用模型和仿真工具來(lái)模擬云環(huán)境并進(jìn)行必要的實(shí)驗(yàn)^[24]。在仿真實(shí)驗(yàn)做出的效果比較理想或者達(dá)到某一標(biāo)準(zhǔn)時(shí), 再將實(shí)驗(yàn)方法放到實(shí)際的云計(jì)算環(huán)境中來(lái)進(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ā)出來(lái)的一個(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)有的或者是沒(méi)有的云架構(gòu)進(jìn)行建模和模擬；另外，其hyper visor模型允許用戶集成任何云代理策略來(lái)管理一組完全可定制的虛擬機(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ì)算和通信過(guò)程中能量的消耗。

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

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

    對(duì)以上4種主流的云計(jì)算仿真平臺(tái)(模擬器)在提出時(shí)間、編程語(yǔ)言、平臺(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)锡?，陳秀萬(wàn)，肖漢，等.一種求解旅行商問(wèn)題的新型帝國(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)拆卸線平衡問(wèn)題的貓群模擬退火算法[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)