一種改進(jìn)模擬退火算法在弱化虛擬機(jī)放置中的應(yīng)用

李尉，陳雨，高小龍

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

0 引言

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

1 模擬退火算法

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

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

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

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

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

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

圖1 模擬退火算法流程圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 測試用例

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

3.2 測試結(jié)果

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

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

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

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

4 結(jié)語

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