在現(xiàn)有關(guān)于虛擬化資源優(yōu)化分配的研究中，應(yīng)用通常為單層或多層邏輯組成結(jié)構(gòu). 然而，對(duì)于由不同組件服務(wù)按照多種組合邏輯( 如順序結(jié)構(gòu)、分支結(jié)構(gòu)、并行結(jié)構(gòu)和循環(huán)結(jié)構(gòu)等) 構(gòu)成的與已有研究不同，本文針對(duì)基于 SBS 的云應(yīng)用的資源優(yōu)化分配問(wèn)題，提出了一種以滿足端到端平均響應(yīng)時(shí)間為約束，以最小化資源使用成本為目標(biāo)的虛擬化資源分配優(yōu)化模型及其遺傳算法的實(shí)現(xiàn). 在該模型中，定義了組件服務(wù)資源配置的概念，并給出了組件服務(wù)候選資源配置的確定方法，從而將資源優(yōu)化分配問(wèn)題轉(zhuǎn)換為一個(gè)資源配置組合優(yōu)化問(wèn)題，進(jìn)而采用遺傳算法求解. 實(shí)驗(yàn)驗(yàn)證了本文的資源分配優(yōu)化模型的有效性，并且表明提出的遺傳算法實(shí)現(xiàn)收斂速度快，且與線性規(guī)劃算法相比，在較大問(wèn)題規(guī)模上可以快速獲得質(zhì)量更高的解.

　　1 基于成本的 SBS

　　資源分配優(yōu)化模型本節(jié)首先定義組件服務(wù)的資源配置，并給出其確定方法，進(jìn)而將 SBS 資源優(yōu)化分配建模為一個(gè)資源配置的組合優(yōu)化問(wèn)題.

　　1. 1 確定候選資源配置為了確定組件服務(wù)的候選資源配置，需要獲取任意資源向量與該組件服務(wù)平均響應(yīng)時(shí)間之間的映射關(guān)系，本文稱描述該映射關(guān)系的模型為組件服務(wù)的資源模型. 另外，還要確定資源使用成本的計(jì)算模型，即資源定價(jià)模型.

　　1. 1. 2 資源定價(jià)模型實(shí)際中，不同的資源類型可以采用多種定價(jià)模型，如線性定價(jià)模型、指數(shù)型定價(jià)模型等. 本文假設(shè)資源使用成本與資源分配量、資源使用時(shí)長(zhǎng)呈正比，并對(duì)所有資源類型均采用線性定價(jià)模

　　2 基于遺傳算法

　　求解優(yōu)化模型根據(jù)優(yōu)化模型可知，組件服務(wù)的資源配置組合優(yōu)化是個(gè) NP 難問(wèn)題，而遺傳算法是解決最優(yōu)化問(wèn)題的有效方法之一，因此本文采用遺傳算法進(jìn)行求解. 首先，采用一維編碼方式對(duì)個(gè)體進(jìn)行二進(jìn)制編碼，基因位取值滿足式( 5) 和式( 6) ; 然后，采用通用的遺傳算子進(jìn)行種群的繁殖，為了減少無(wú)效解，對(duì)交叉操作和變異操作進(jìn)行了一定限制，使其滿足優(yōu)化模型的約束條件. 另外，在適應(yīng)度函數(shù)中引入了罰函數(shù)，從而降低在解空間中無(wú)對(duì)應(yīng)可行解的個(gè)體的適應(yīng)度，加快收斂速度.隨機(jī)等距的方式抽取個(gè)體，從而更好地保持種群多樣性.交叉算子采用單點(diǎn)交叉. 為了使新的個(gè)體仍然滿足約束條件式( 5) ，將交叉點(diǎn)的取值限制為不同段基因的分割點(diǎn).變異算子采用位點(diǎn)變異，將變異基因位的值取非. 與交叉算子類似，為滿足式( 5) ，如果變異后的值為1，則將該基因位所屬基因段中其他基因位的值均置為0，否則，則在變異后，隨機(jī)從該基因位所屬基因段中的其他基因位中選擇一個(gè)并取非.最后，本文通過(guò)設(shè)定遺傳代數(shù)作為終止迭代的條件，相比通過(guò)設(shè)定精度來(lái)終止迭代，可以防止由于種群過(guò)大、要求精度較高而引起的搜索時(shí)間過(guò)長(zhǎng)的情況.

　　3 實(shí)驗(yàn)與分析

　　本節(jié)主要驗(yàn)證本文的遺傳算法的收斂速度，并將其與線性規(guī)劃算法在 SBS 資源分配優(yōu)化模型上解的質(zhì)量和求解效率兩方面進(jìn)行比較.

　　3. 1 實(shí)驗(yàn)設(shè)置

　　3. 2. 1 遺傳算法的收斂速度該組實(shí)驗(yàn)考察本文提出的遺傳算法的收斂速度，這對(duì)于在合理時(shí)間內(nèi)求得最優(yōu)解具有重要意義. 為了使算法能以較大概率收斂到最優(yōu)解，本文在適應(yīng)度函數(shù)中引入了罰函數(shù)，以物理機(jī)個(gè)數(shù)取值15 為例，與未采用罰函數(shù)的適應(yīng)度函數(shù)相比較，結(jié)果如圖3 所示.根據(jù)圖4 可知，對(duì)于不同的物理機(jī)數(shù)量，遺傳算法得到的最小資源使用成本略高于線性規(guī)劃算法，而且隨著物理機(jī)數(shù)量的增加，兩種算法得到的最小資源使用成本均呈降低趨勢(shì)，這是由于解空間擴(kuò)大增加了求得更優(yōu)解的可能性，同時(shí)物理機(jī)增多也會(huì)有助于減少資源配置之間的沖突，進(jìn)而產(chǎn)生更多的可行解.2) 求解優(yōu)化模型消耗的時(shí)間. 在求解優(yōu)化模型時(shí)，遺傳算法和線性規(guī)劃算法消耗的時(shí)間對(duì)比結(jié)果如圖5 所示.明顯要高于未引入罰函數(shù)時(shí)，這是因?yàn)樵诮饪臻g中沒(méi)有可行解的個(gè)體不會(huì)遺傳到下一代，因此可在一定程度提高收斂到最優(yōu)解的概率.

　　3. 2. 2 與線性規(guī)劃比較該組實(shí)驗(yàn)通過(guò)物理機(jī)數(shù)量在 10 ～50 之間的變化，與常用的求解約束優(yōu)化問(wèn)題的線性規(guī)劃算法在解的質(zhì)量( 以部署 SBS 的資源使用成本度量) 和求解效率( 以求解優(yōu)化模型消耗的時(shí)間度量) 兩方面進(jìn)行比較.1) 部署 SBS 的資源使用成本. 遺傳算法和線性規(guī)劃算法求得的最小資源使用成本對(duì)比如圖 4所示.圖4 最小資源使用成本對(duì)比Fig. 4 Comparison of the lowest resource costs根據(jù)圖4 可知，對(duì)于不同的物理機(jī)數(shù)量，遺傳算法得到的最小資源使用成本略高于線性規(guī)劃算法，而且隨著物理機(jī)數(shù)量的增加，兩種算法得到的最小資源使用成本均呈降低趨勢(shì)，這是由于解空間擴(kuò)大增加了求得更優(yōu)解的可能性，同時(shí)物理機(jī)增多也會(huì)有助于減少資源配置之間的沖突，進(jìn)而產(chǎn)生更多的可行解.2) 求解優(yōu)化模型消耗的時(shí)間. 在求解優(yōu)化模型時(shí)，遺傳算法和線性規(guī)劃算法消耗的時(shí)間對(duì)比結(jié)果如圖5 所示.圖5 消耗時(shí)間對(duì)比Fig. 5 Comparison of solving time根據(jù)圖5 可知，兩種算法的時(shí)間消耗均隨著物理機(jī)數(shù)量的增加而呈上升趨勢(shì). 當(dāng)物理機(jī)數(shù)較小( 小于25) 時(shí)，線性規(guī)劃算法的時(shí)間消耗要低于遺傳算法; 而當(dāng)物理機(jī)數(shù)量較大時(shí)，線性規(guī)劃算法的時(shí)間消耗顯著增加，此時(shí)遺傳算法的效率要優(yōu)于線性規(guī)劃.

　　綜上實(shí)驗(yàn)結(jié)果表明: 本文的遺傳算法能夠在可接受的時(shí)間內(nèi)收斂到最優(yōu)解，并且適應(yīng)度函數(shù)中的罰函數(shù)對(duì)于提高算法的收斂速度具有比較明顯的效果; 遺傳算法求解得到的資源分配方案的資源使用成本比較接近線性規(guī)劃得到的最優(yōu)解;與線性規(guī)劃相比，當(dāng)組件服務(wù)的候選資源配置較多時(shí)，本文的遺傳算法可以在更短時(shí)間內(nèi)求得最優(yōu)資源配置組合.4 結(jié) 語(yǔ)本文針對(duì)基于SBS 的應(yīng)用在云環(huán)境部署時(shí)的資源優(yōu)化分配問(wèn)題，提出了一種基于資源配置的組合優(yōu)化思想、以最小化資源使用成本且滿足應(yīng)用SLA 和物理機(jī)資源約束的資源分配優(yōu)化模型，并根據(jù)該優(yōu)化模型的特點(diǎn)給出了改進(jìn)的遺傳算法.

　　實(shí)驗(yàn)驗(yàn)證了本文提出的優(yōu)化模型的有效性，并且表明其基于遺傳算法的實(shí)現(xiàn)具有較快的收斂速度，同時(shí)可獲得接近線性規(guī)劃最優(yōu)解的資源配置組合，但在問(wèn)題規(guī)模較大時(shí)求解效率明顯優(yōu)于后者.