李尉，陳雨，高小龍

（四川大學(xué)電子信息學(xué)院，成都610065）

0 引言

云計(jì)算概念提出至今已有10年的時(shí)間了，在此期間，此項(xiàng)技術(shù)得到的巨大的進(jìn)步與發(fā)展，成為計(jì)算機(jī)技術(shù)又一次的巨變。云計(jì)算是分布式計(jì)算、并行計(jì)算、效用計(jì)算、網(wǎng)絡(luò)存儲(chǔ)、虛擬化、負(fù)載均衡、熱備份冗余等傳統(tǒng)計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)發(fā)展融合的產(chǎn)物。其中云計(jì)算最為基礎(chǔ)性的服務(wù)為基礎(chǔ)設(shè)施即服務(wù)（IaaS），其原理是通過(guò)將物理服務(wù)器進(jìn)行分塊，按照客戶(hù)需求的大小把物理服務(wù)器以虛擬機(jī)為最小單位的形式提供給客戶(hù)。在實(shí)際應(yīng)用中，提供云計(jì)算服務(wù)的公司根據(jù)預(yù)估的情況來(lái)研究一種高利用率的虛擬機(jī)放置方案。這樣有利于物理服務(wù)器的資源利用率的最大化，降低能耗，提高經(jīng)濟(jì)效應(yīng)。虛擬機(jī)放置問(wèn)題一般被歸類(lèi)為NP難問(wèn)題中的裝箱問(wèn)題。對(duì)于這類(lèi)問(wèn)題，當(dāng)前提出的解決方案主要集中在三個(gè)方向：?jiǎn)l(fā)算式算法、遺傳算法和模擬退火算法。例如，在啟發(fā)算式BFD算法的基礎(chǔ)上進(jìn)行改進(jìn)，使得在虛擬機(jī)初始化放置是得到有效的優(yōu)化。通過(guò)改進(jìn)的FFD算法，來(lái)尋找虛擬機(jī)放置問(wèn)題的最優(yōu)解。在傳統(tǒng)的遺傳算法基礎(chǔ)上，針對(duì)傳統(tǒng)分組問(wèn)題的適應(yīng)性差的缺點(diǎn)提出重新構(gòu)造分組的方法，來(lái)提高虛擬機(jī)初始化放置的資源利用率。上述三個(gè)方向中，啟發(fā)算式算法的優(yōu)點(diǎn)是簡(jiǎn)單、快速、易于實(shí)現(xiàn)。但缺點(diǎn)也比較明顯，全局化搜索的幾率低，容易陷入局部的最優(yōu)解。遺傳算法作為裝箱問(wèn)題的現(xiàn)代優(yōu)化方法之一，在解決高維度、高復(fù)雜及非線性問(wèn)題的優(yōu)化中具有全局最優(yōu)、效率高以及易于并行計(jì)算等優(yōu)點(diǎn)，有很強(qiáng)的問(wèn)題解決能力，但是有著收斂速度慢和易于陷入局部最優(yōu)解的缺點(diǎn)。而本文主要研究的方向是弱化的虛擬機(jī)的初始化放置問(wèn)題，一般將其建模為帶限定條件的一維離線裝箱問(wèn)題，屬于低緯度、高精度的問(wèn)題，所以上述兩種方法不太適用。由于一般組合優(yōu)化問(wèn)題與物質(zhì)的退火過(guò)程具有很大的相似性，因此，此種智能優(yōu)化算法通常被用來(lái)解決組合優(yōu)化的問(wèn)題。又因?yàn)樵撍惴ǖ木植克阉髂芰^強(qiáng)，而且具有運(yùn)行時(shí)間段的有點(diǎn)。所以本文主要研究模擬退火算法，并針對(duì)傳統(tǒng)模擬退火算法前期溫度下降過(guò)快、初始解較差導(dǎo)致全局搜索能力不足和迂回搜索等缺點(diǎn)進(jìn)行改進(jìn)。

1 模擬退火算法

1.1 模擬退火算法的實(shí)現(xiàn)

模擬退火算法的核心思想與熱力學(xué)的原理十分相似。熱力學(xué)上，溫度非常高的情況下液體中大量的原子的運(yùn)動(dòng)方式是相對(duì)的，隨著溫度漸漸的下降，原子的可動(dòng)性也隨之降低。慢慢的形成一個(gè)純凈的晶體，晶體的形態(tài)是能量最低的狀態(tài)，只要是溫度緩慢下降的物體都可以慢慢達(dá)到這種能量最低的狀態(tài)。如果降溫過(guò)程迅速，這種情況下物體不會(huì)達(dá)到這種狀態(tài)，能夠達(dá)到的狀態(tài)只能是一種能量較高的多晶體或非晶體的狀態(tài)。所以，緩緩地降溫是這個(gè)過(guò)程的核心，以爭(zhēng)取足夠的時(shí)間，在大量原子的運(yùn)動(dòng)性喪失前完成重新的排布，這是確保能量達(dá)到低能量狀態(tài)的必須條件。模擬退火算法（Simulated Annealing，SA）的思想最早由 Metropo?lis等人于1953年提出；Kirkpatrick于1983年第一次使用模擬退火算法求解組合最優(yōu)化問(wèn)題。模擬退火算法是一種基于Monte Carlo迭代求解策略的隨機(jī)尋優(yōu)算法。算法的理論依據(jù)是物體的退火過(guò)程和組合優(yōu)化問(wèn)題的求解相似性，通過(guò)模擬高溫退火的過(guò)程來(lái)搜索近似最優(yōu)解。算法的實(shí)現(xiàn)基本步驟為：

（1）選定初始溫度，Markov衰減函數(shù)，終止溫度，初始解，提供解鄰域的構(gòu)造函數(shù)。

（2）在每個(gè)溫度下，由前一個(gè)解出發(fā)，通過(guò)加入隨機(jī)擾動(dòng)機(jī)制，產(chǎn)生原有解的解鄰域。

（3）新解是否被接受是由接受函數(shù)來(lái)確定，接受函數(shù)的主要參數(shù)溫度，由接受的新解形成一定長(zhǎng)度的Markov鏈。

（4）根據(jù)衰減函數(shù)，隨著溫度的降低，接受新解的概率也降低，當(dāng)溫度降低到最低溫度時(shí)候，解狀態(tài)也穩(wěn)定于優(yōu)化問(wèn)題的最優(yōu)狀態(tài)。

圖1 模擬退火算法流程圖

1.2 模擬退火算法的基本原理

模擬退火算法與金屬退火過(guò)程相似。Metropolis準(zhǔn)則表明，粒子在溫度T時(shí)趨于平衡的概率exp（-Δ E/T），其中E為溫度T時(shí)的內(nèi)能，ΔE為其改變量。固體退火和組合優(yōu)化問(wèn)題很相似，固體的內(nèi)在能量就相當(dāng)于組合優(yōu)化問(wèn)題中的接受函數(shù)的函數(shù)值，溫度參數(shù)T也就相當(dāng)于組合優(yōu)化問(wèn)題的控制參數(shù)，這樣組合優(yōu)化問(wèn)題的模擬退火算法就形成了。模擬退火算法就是從最初的解X0和相當(dāng)于溫度的控制參數(shù)初始值T0開(kāi)始，然后通過(guò)反復(fù)的迭代，重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄→降低控制參數(shù)T”的過(guò)程，最后，在結(jié)束的時(shí)候所得到的解就是該組合優(yōu)化問(wèn)題的近似最優(yōu)解，上述過(guò)程就是一種基于Monte Carlo迭代求解的隨機(jī)搜索過(guò)程

1.3 模擬退火算法的缺點(diǎn)

傳統(tǒng)模擬退火算法雖然能夠依概率收斂于全局最優(yōu)解，但是對(duì)于目標(biāo)函數(shù)比較復(fù)雜時(shí)，為了獲得高精度的解，溫度參數(shù)一般需要設(shè)置為一個(gè)較大的初始值，并且在每個(gè)溫度值T下需要重復(fù)執(zhí)行Metropolis算法，所以存在著迭代計(jì)算速度慢，計(jì)算花費(fèi)的時(shí)間比較長(zhǎng)。另外，由于在最優(yōu)解的搜索過(guò)程中，依據(jù)Metropolis算法，對(duì)于劣質(zhì)解在一定程度內(nèi)以某個(gè)概率接受，這個(gè)概率值由溫度值t控制。所以存在丟棄當(dāng)前遇到的最優(yōu)解的可能；以及對(duì)某個(gè)已經(jīng)訪問(wèn)過(guò)的解進(jìn)行多次重復(fù)的搜索，增加運(yùn)行時(shí)間。這些局限使得模擬退火算法無(wú)法在實(shí)際生產(chǎn)生活中廣泛運(yùn)用。

2 改進(jìn)的模擬退火算法

2.1 降溫函數(shù)的改進(jìn)

（1）根據(jù)模擬退火的收斂性理論，溫度的高低決定了模擬退火算法進(jìn)行的是全局搜索還是局部搜索，在溫度下降過(guò)快的情況下，模擬退火算法將很快從全局搜索轉(zhuǎn)變?yōu)榫植克阉?，很大可能陷入局部最?yōu)解的狀態(tài)，想要跳出局部最優(yōu)解只能增加內(nèi)部循環(huán)的次數(shù)，這樣會(huì)導(dǎo)致算法運(yùn)行時(shí)間過(guò)長(zhǎng)；如果溫度下降過(guò)慢，雖然可以通過(guò)減少內(nèi)部循環(huán)的次數(shù)的方法來(lái)控制時(shí)間，但是外部循環(huán)次數(shù)也影響了算法運(yùn)行的時(shí)間。因此本文希望通過(guò)改進(jìn)溫度衰減函數(shù)來(lái)提高模擬退火算法的性能。傳統(tǒng)的溫度衰減函數(shù)為單一的函數(shù)，本文采用分段函數(shù)來(lái)替代，前半段溫度較高的時(shí)候，采用衰減較快的函數(shù)來(lái)快速降低溫度。在退火的后期，采用下降平緩的函數(shù)來(lái)使得算法更好地進(jìn)行精細(xì)搜索。

根據(jù)模擬退火的理論，只有在溫度衰減函數(shù)收斂的變化態(tài)勢(shì)比對(duì)數(shù)函數(shù)1log(k)更慢時(shí)，模擬退火算法才能保證依概率1收斂于全局最優(yōu)解。但是采用對(duì)數(shù)函數(shù)的模擬退火算法的運(yùn)行時(shí)間過(guò)長(zhǎng)，所以前m次迭代的溫度衰減函數(shù)決定采用TsIn(k)，希望能迅速找到最優(yōu)解所在的鄰域，m次以后的迭代的溫度衰減函數(shù)使用Ts*0.99k，使得能夠在迭代后期精確的找到全局最優(yōu)解[1]。溫度衰減函數(shù)：

其中m是預(yù)先設(shè)定的值，Ts為起始溫度。通過(guò)比較溫度下降函數(shù)，找到log函數(shù)的拐點(diǎn)所對(duì)應(yīng)的變化次數(shù)。對(duì)log函數(shù)求到可得m=15。針對(duì)存在丟棄當(dāng)前遇到的最優(yōu)解的可能，本文對(duì)傳統(tǒng)模擬退火算法增加了記憶功能。

（2）由于接受準(zhǔn)則的原理存在接受不是最優(yōu)解的可能，而導(dǎo)致放棄最優(yōu)解，所以本文通過(guò)增加存儲(chǔ)環(huán)節(jié)，將當(dāng)前位置的最好狀態(tài)存儲(chǔ)下來(lái)[2]來(lái)保證最終解為最好的狀態(tài)。

2.2 改進(jìn)算法在虛擬機(jī)放置問(wèn)題中的應(yīng)用

問(wèn)題建模：首先，因?yàn)樵诖_定裝箱策略的情況下，所求的解的效果只與待放置虛擬機(jī)的放置順序有關(guān)，所以將虛擬機(jī)的順序作為模擬退后算法在虛擬機(jī)放置問(wèn)題中的解，解決的存儲(chǔ)方式為數(shù)組。這樣還能方便加入擾動(dòng)機(jī)制，容易實(shí)現(xiàn)新舊解的迭代，即解鄰域的構(gòu)造[3]。新解構(gòu)造方法采取的方法是引入一個(gè)隨機(jī)數(shù)產(chǎn)生函數(shù)，用這個(gè)函數(shù)產(chǎn)生兩個(gè)合理范圍內(nèi)的隨機(jī)數(shù)，然后交換以這兩個(gè)隨機(jī)數(shù)為下標(biāo)的虛擬機(jī)得到新的解。本文采用的裝箱策略為最佳適應(yīng)算法（Best Fit）：處理方法為將所有非空箱子的按剩余空間的大小做升序排列，找到按升序排列的第一個(gè)能夠放下當(dāng)前物品的箱子并將該物品放入，否則開(kāi)啟新的箱子?？紤]到改進(jìn)的模擬退火算法加快了前期的溫度下降的趨勢(shì)，所以算法的全局搜索能力下降，初始解設(shè)置為某個(gè)局部最優(yōu)解有利于高效利用算法前期的全局搜索。因此算法的初始解設(shè)置為采用最佳適應(yīng)算法裝箱后的每個(gè)箱子由底部到頂部的各個(gè)虛擬機(jī)的順序。因?yàn)樵谔摂M機(jī)的放置問(wèn)題上的最優(yōu)解為所用到的服務(wù)器的個(gè)數(shù)最少的情況下每個(gè)服務(wù)器的利用率最大，所以評(píng)價(jià)函數(shù)為：

其中n為所使用的箱子個(gè)數(shù)，O（i）為每個(gè)箱子的利用率，評(píng)價(jià)函數(shù)的結(jié)果為每個(gè)箱子的平均利用率。解的接受概率：

其中，E2為新解，E1為舊解。在新解的效果好于舊解的情況下，新解的接受概率依據(jù)Metropolis算法為1，在新解的效果差于舊解的情況下，用隨機(jī)數(shù)產(chǎn)生函數(shù)得到一個(gè)隨機(jī)概率Rand（x），當(dāng)隨機(jī)概率小于exp（-（E2-E1）/T）時(shí)候接受新解，否則舍棄新解，保留舊解。

3 實(shí)驗(yàn)示例及結(jié)果

與MATLAB平臺(tái)上的仿真不同的是，本文采用C++語(yǔ)言編寫(xiě)代碼，實(shí)現(xiàn)了性能比較完善的專(zhuān)門(mén)放置弱化的虛擬機(jī)的程序。普通虛擬機(jī)放置主要考慮的方面為內(nèi)存和CPU的個(gè)數(shù)。在弱化虛擬機(jī)的放置問(wèn)題上將兩方面的因素簡(jiǎn)化為優(yōu)先考慮某一方面，例如只考慮保證放置的虛擬機(jī)內(nèi)存總空間不超過(guò)服務(wù)器內(nèi)存的情況下，每臺(tái)服務(wù)器CPU的使用率。

3.1 測(cè)試用例

本文將服務(wù)器規(guī)格設(shè)置為CPU個(gè)數(shù)為56，內(nèi)存大小為128GB。選取8種型號(hào)的虛擬機(jī)構(gòu)造兩組數(shù)據(jù)第一組和第二組。每組數(shù)據(jù)選取8種型號(hào)的虛擬機(jī)若干。數(shù)據(jù)構(gòu)成如表1：

3.2 測(cè)試結(jié)果

表1 兩組數(shù)據(jù)的構(gòu)成

在同樣的測(cè)試數(shù)據(jù)下，每組數(shù)據(jù)在每種算法下測(cè)試3次，得到的傳統(tǒng)模擬退火算法和改進(jìn)的模擬退火算法的平均結(jié)果比較如表2。

表2 算法改進(jìn)前后的結(jié)果比較

從實(shí)驗(yàn)結(jié)果可以看到，改進(jìn)的模擬退火算法在數(shù)據(jù)規(guī)模較小的時(shí)候，放置虛擬機(jī)所需的服務(wù)器個(gè)數(shù)于改進(jìn)前的一樣，但是改進(jìn)后的模擬退火算法的運(yùn)行速度明顯快于傳統(tǒng)的模擬退火算法的運(yùn)行速度。

4 結(jié)語(yǔ)

本文通過(guò)改進(jìn)模擬退火算法實(shí)現(xiàn)了弱化虛擬機(jī)放置問(wèn)題的最優(yōu)解搜尋。根據(jù)模擬退火算法的特點(diǎn)，優(yōu)化了單一溫度衰減函數(shù)在算法前期溫度衰減過(guò)慢的缺點(diǎn)，采用組合溫度衰減函數(shù)既加快算法前期的全局最優(yōu)解鄰域的搜索速度，又保證了后期局部最優(yōu)解的搜索質(zhì)量。在解決弱化虛擬機(jī)放置問(wèn)題上將模擬退火算法與啟發(fā)算式（最佳適應(yīng)算法）相結(jié)合，使得模擬退火算法在弱化虛擬機(jī)放置問(wèn)題上使用更加簡(jiǎn)單。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法在數(shù)據(jù)規(guī)模較小的情況下，既保證了解的質(zhì)量也明顯加快了模擬退火算法的運(yùn)行速度。