面向成本優(yōu)化的SBS虛擬化資源調(diào)配論文
在現(xiàn)有關于虛擬化資源優(yōu)化分配的研究中，應用通常為單層或多層邏輯組成結構. 然而，對于由不同組件服務按照多種組合邏輯( 如順序結構、分支結構、并行結構和循環(huán)結構等) 構成的與已有研究不同，本文針對基于 SBS 的云應用的資源優(yōu)化分配問題，提出了一種以滿足端到端平均響應時間為約束，以最小化資源使用成本為目標的虛擬化資源分配優(yōu)化模型及其遺傳算法的實現(xiàn). 在該模型中，定義了組件服務資源配置的概念，并給出了組件服務候選資源配置的確定方法，從而將資源優(yōu)化分配問題轉(zhuǎn)換為一個資源配置組合優(yōu)化問題，進而采用遺傳算法求解. 實驗驗證了本文的資源分配優(yōu)化模型的有效性，并且表明提出的遺傳算法實現(xiàn)收斂速度快，且與線性規(guī)劃算法相比，在較大問題規(guī)模上可以快速獲得質(zhì)量更高的解.
1 基于成本的 SBS
資源分配優(yōu)化模型本節(jié)首先定義組件服務的資源配置，并給出其確定方法，進而將 SBS 資源優(yōu)化分配建模為一個資源配置的組合優(yōu)化問題.
1. 1 確定候選資源配置為了確定組件服務的候選資源配置，需要獲取任意資源向量與該組件服務平均響應時間之間的映射關系，本文稱描述該映射關系的模型為組件服務的資源模型. 另外，還要確定資源使用成本的計算模型，即資源定價模型.
1. 1. 2 資源定價模型實際中，不同的資源類型可以采用多種定價模型，如線性定價模型、指數(shù)型定價模型等. 本文假設資源使用成本與資源分配量、資源使用時長呈正比，并對所有資源類型均采用線性定價模
2 基于遺傳算法
求解優(yōu)化模型根據(jù)優(yōu)化模型可知，組件服務的資源配置組合優(yōu)化是個 NP 難問題，而遺傳算法是解決最優(yōu)化問題的`有效方法之一，因此本文采用遺傳算法進行求解. 首先，采用一維編碼方式對個體進行二進制編碼，基因位取值滿足式( 5) 和式( 6) ; 然后，采用通用的遺傳算子進行種群的繁殖，為了減少無效解，對交叉操作和變異操作進行了一定限制，使其滿足優(yōu)化模型的約束條件. 另外，在適應度函數(shù)中引入了罰函數(shù)，從而降低在解空間中無對應可行解的個體的適應度，加快收斂速度.隨機等距的方式抽取個體，從而更好地保持種群多樣性.交叉算子采用單點交叉. 為了使新的個體仍然滿足約束條件式( 5) ，將交叉點的取值限制為不同段基因的分割點.變異算子采用位點變異，將變異基因位的值取非. 與交叉算子類似，為滿足式( 5) ，如果變異后的值為1，則將該基因位所屬基因段中其他基因位的值均置為0，否則，則在變異后，隨機從該基因位所屬基因段中的其他基因位中選擇一個并取非.最后，本文通過設定遺傳代數(shù)作為終止迭代的條件，相比通過設定精度來終止迭代，可以防止由于種群過大、要求精度較高而引起的搜索時間過長的情況.
3 實驗與分析
本節(jié)主要驗證本文的遺傳算法的收斂速度，并將其與線性規(guī)劃算法在 SBS 資源分配優(yōu)化模型上解的質(zhì)量和求解效率兩方面進行比較.
3. 1 實驗設置
3. 2. 1 遺傳算法的收斂速度該組實驗考察本文提出的遺傳算法的收斂速度，這對于在合理時間內(nèi)求得最優(yōu)解具有重要意義. 為了使算法能以較大概率收斂到最優(yōu)解，本文在適應度函數(shù)中引入了罰函數(shù)，以物理機個數(shù)取值15 為例，與未采用罰函數(shù)的適應度函數(shù)相比較，結果如圖3 所示.根據(jù)圖4 可知，對于不同的物理機數(shù)量，遺傳算法得到的最小資源使用成本略高于線性規(guī)劃算法，而且隨著物理機數(shù)量的增加，兩種算法得到的最小資源使用成本均呈降低趨勢，這是由于解空間擴大增加了求得更優(yōu)解的可能性，同時物理機增多也會有助于減少資源配置之間的沖突，進而產(chǎn)生更多的可行解.2) 求解優(yōu)化模型消耗的時間. 在求解優(yōu)化模型時，遺傳算法和線性規(guī)劃算法消耗的時間對比結果如圖5 所示.明顯要高于未引入罰函數(shù)時，這是因為在解空間中沒有可行解的個體不會遺傳到下一代，因此可在一定程度提高收斂到最優(yōu)解的概率.
3. 2. 2 與線性規(guī)劃比較該組實驗通過物理機數(shù)量在 10 ～50 之間的變化，與常用的求解約束優(yōu)化問題的線性規(guī)劃算法在解的質(zhì)量( 以部署 SBS 的資源使用成本度量) 和求解效率( 以求解優(yōu)化模型消耗的時間度量) 兩方面進行比較.1) 部署 SBS 的資源使用成本. 遺傳算法和線性規(guī)劃算法求得的最小資源使用成本對比如圖 4所示.圖4 最小資源使用成本對比Fig. 4 Comparison of the lowest resource costs根據(jù)圖4 可知，對于不同的物理機數(shù)量，遺傳算法得到的最小資源使用成本略高于線性規(guī)劃算法，而且隨著物理機數(shù)量的增加，兩種算法得到的最小資源使用成本均呈降低趨勢，這是由于解空間擴大增加了求得更優(yōu)解的可能性，同時物理機增多也會有助于減少資源配置之間的沖突，進而產(chǎn)生更多的可行解.2) 求解優(yōu)化模型消耗的時間. 在求解優(yōu)化模型時，遺傳算法和線性規(guī)劃算法消耗的時間對比結果如圖5 所示.圖5 消耗時間對比Fig. 5 Comparison of solving time根據(jù)圖5 可知，兩種算法的時間消耗均隨著物理機數(shù)量的增加而呈上升趨勢. 當物理機數(shù)較小( 小于25) 時，線性規(guī)劃算法的時間消耗要低于遺傳算法; 而當物理機數(shù)量較大時，線性規(guī)劃算法的時間消耗顯著增加，此時遺傳算法的效率要優(yōu)于線性規(guī)劃.
綜上實驗結果表明: 本文的遺傳算法能夠在可接受的時間內(nèi)收斂到最優(yōu)解，并且適應度函數(shù)中的罰函數(shù)對于提高算法的收斂速度具有比較明顯的效果; 遺傳算法求解得到的資源分配方案的資源使用成本比較接近線性規(guī)劃得到的最優(yōu)解;與線性規(guī)劃相比，當組件服務的候選資源配置較多時，本文的遺傳算法可以在更短時間內(nèi)求得最優(yōu)資源配置組合.4 結 語本文針對基于SBS 的應用在云環(huán)境部署時的資源優(yōu)化分配問題，提出了一種基于資源配置的組合優(yōu)化思想、以最小化資源使用成本且滿足應用SLA 和物理機資源約束的資源分配優(yōu)化模型，并根據(jù)該優(yōu)化模型的特點給出了改進的遺傳算法.
實驗驗證了本文提出的優(yōu)化模型的有效性，并且表明其基于遺傳算法的實現(xiàn)具有較快的收斂速度，同時可獲得接近線性規(guī)劃最優(yōu)解的資源配置組合，但在問題規(guī)模較大時求解效率明顯優(yōu)于后者.
【面向成本優(yōu)化的SBS虛擬化資源調(diào)配論文】相關文章：
高校人力資源成本會計核算探討論文03-10
歌詞是調(diào)配語文大菜的佐料10-07
議論文優(yōu)化論據(jù)：務實08-03
面向大海作文06-03
精選成本管理辦法論文11-29
《京劇的虛擬性》閱讀答案06-21
虛擬與現(xiàn)實作文05-13
層次化立體化教學大學英語論文02-26