基于混合算法的艦船虛擬機優化設置方案研究*

閔紹榮　趙俊杰　謝紅勝

(中國艦船研究設計中心　武漢　430064)

MIN Shaorong　ZHAO Junjie　XIE Hongsheng

(China Ship Development and Design Center, Wuhan　430064)

?

基于混合算法的艦船虛擬機優化設置方案研究*

閔紹榮趙俊杰謝紅勝

(中國艦船研究設計中心武漢430064)

論文介紹了在考慮艦船業務對計算性能需求的前提下的艦船刀片服務器虛擬機優化設置方案。對艦船虛擬機設置因素進行了分析，結合遺傳算法與蟻群算法的優點，形成混合優化設置算法，并詳細闡述了利用混合算法進行虛擬機優化設置的實現過程。

虛擬機; 混合算法; 優化設置

MIN ShaorongZHAO JunjieXIE Hongsheng

(China Ship Development and Design Center, Wuhan430064)

Class NumberTP301.6

1　引言

隨著虛擬機技術的飛速發展，虛擬機技術必將廣泛運用于艦船作戰平臺、艦艇作戰系統等方面的優化設計領域，依據艦船業務的差異性進行艦船虛擬機資源的優化設置，是一種全新的研究方向，隨著艦艇研制技術的發展，該方向的研究工作將逐步得到重視[1～2]。

本文介紹的基于混合算法的艦船虛擬機優化設置方案能夠充分考慮艦船業務對計算性能要求的差異性[3～5]，并通過選取CPU資源與網絡帶寬資源作為主要影響因素，建立了艦船虛擬機優化設置模型。利用遺傳算法的全局搜索能力[6]與蟻群算法的發現最優解能力[7～9]，形成混合算法，求得艦船刀片服務器虛擬機優化設置最優方案。對艦艇研制過程中虛擬機技術的應用具有非常重要的意義。

2　優化設置多因素分析

刀片服務器的多核CPU的核數、網絡帶寬是固定的。并且在虛擬機設置過程中，艦船業務對與CPU資源、網絡帶寬資源的性能要求是不一致的。根據這兩個特點建立艦船虛擬機優化設置過程中的CPU資源、網絡帶寬資源分配原則[10]：

1)分配給單一刀片服務器上各個虛擬機的總CPU核數與網絡帶寬要分別小于等于此刀片服務器總的CPU核數與網絡帶寬。MJ表示第j個刀片服務器，mji表示第j個刀片服務器上第i個虛擬機設置。表達公式為

(1)

2)確保刀片服務器中設置的每個虛擬機都能獲得滿足其性能需要的CPU資源、網絡帶寬資源份額。用z(j)表示第j個刀片服務器的設置是否滿足艦船業務要求，表達公式為

(2)

3)每個虛擬機用戶在進行CPU資源、網絡帶寬資源分配時需要考慮預留資源來保證業務的正常運行。

4)盡可能地使得多核CPU資源、網絡帶寬資源得到有效利用。

3　混合算法框架

混合優化算法是通過汲取兩種傳統的啟發式算法各自的優點，克服其缺陷，爭取在求解精度上達到最優。艦船刀片服務器虛擬機優化設置中資源分配的混合優化算法的基本框架圖如圖1所示。

圖1　混合算法框架圖

4　算法模型與實現流程

4.1遺傳算法初次分配

4.1.1遺傳編碼

根據艦船多層級刀片服務器虛擬機優化設置中數據結構特點，本文研究選擇樹形編碼技術，相比于其他編碼技術，樹形編碼技術對數據進行分級歸類，便于對本文研究中存在的不同類型數據進行編碼。具體的編碼規則如下。

本文研究中用一個樹表示遺傳算法解的編碼(如圖2所示)。樹的根結點表示機柜編號，即對具體的某一個機柜內的刀片服務器進行虛擬機優化設置。第二層子結點表示機柜內的刀片服務器編號。第三層子結點表示設置的虛擬機編號，與艦船業務編號一一對應，本文研究中只考慮一個虛擬機上執行一個艦船業務的情況。第四層葉節點表示虛擬機的重要參數，包括設置CPU核數，設置網絡帶寬以及業務需求情況等。業務需求定義如式(3)所示：

(3)

式中mji表示第j個物理機上第i個虛擬機的虛擬CPU核數分配情況，nji表示第j個物理機上第i個虛擬機的網絡帶寬分配情況，Gz表示第z個艦船業務的CPU核心數量需求，Qz表示第z個艦船業務的網絡帶寬資源需求。Z表示第Z個刀片服務器，Lz表示此虛擬機設置的刀片服務器位置。

圖2　樹形編碼

4.1.2適應度函數設計

為了滿足遺傳算法“優勢劣汰”的原則，選擇出優良染色體，將適應度函數定義P(k)為

(4)

其中，f(i)表示第i個虛擬機的設置合理性驗證結果，公式為

(5)

h(i)表示第i個虛擬機的設置的滿意度，公式為

(6)

式中Lv為考慮虛擬機性能對于執行艦船業務有一定盈余情況下對于計算資源的最佳業務需求值。

r(k)表示此樹形解的合理性驗證結果，公式為

(7)

式中mji表示第j個物理機上第i個虛擬機的虛擬CPU核數分配情況，nji表示第j個物理機上第i個虛擬機的網絡帶寬分配情況，Mj表示第j個物理機的最大CPU核心數量，Nj表示第j個物理機的最大網絡帶寬能力。

4.1.3生成初始種群

設種群規模為M，艦船業務數為N。生成初始種群的算法流程如圖3所示。

圖3　生成初始種群

4.1.4選擇復制

利用復制方法，提高種群的適應度，使得種群得到進化。首先計算出所有單個樹形染色體的適應度值后,先選擇滿足約束條件的染色體,然后通過輪盤賭法,設定隨機適應度閾值,選擇出性能好的樹形染色體,在選取中，適應度值高的染色體被選中的概率更大。基本步驟如下:

Step l:從初始形成的樹形解中隨機選取一定數目樹形解，計算每一個樹形解的適應度值P(k)，并計算總和∑P(k)；

Step 2:生成一個隨機數m0，要求其在區間(0，∑P(k)]中；

Step 3:將選擇得到的樹形解的適應度值進行累加，大于或等于m0時，選擇最后累加的樹形解進行復制；

Step 4:當復制的樹形解數目等于選取的樹形解數目時結束。若不等于，則重復Step 2和Step 3。

4.1.5交叉、變異操作

遺傳算法主要通過交叉算子互換樹形染色體基因位組合產生新個體。當子代個體的適應度值大于父代個體時則替換父代染色體。本文研究由于樹形染色體結構的特殊性將采用四種交叉策略：內部點交換；外部點交換；內部塊交換；外部塊交換。如圖4所示。變異操作針對于樹形染色體第四層數據進行，若變異后的子染色體適應度函數大于變異前的適應度函數，則選取子染色體形成新的染色體群。

圖4　染色體交換

4.1.6終止條件與參數控制

本文設置好最大迭代次數lmax與最小迭代次數lmin，保證迭代次數num的區間，保證算法的準確性。公式為

lmin≤num≤lmax

(8)

對群體適應度進行檢測，設置群體的總適應度進化率wmin，即群體總適應度最小增長值。若增長率小于wmin，則結束迭代。公式為

(9)

4.2蟻群算法優化求解

4.2.1設置蟻群算法初始信息素

遺傳算法中種群的數據結構是樹形結構，具有特殊性，因此在進行初始信息素轉換的過程中，根據優化解樹形結構的特殊性，以第三層數據為基礎將樹形解分解，即將設置的每一個虛擬機方案看作一個單獨結點，再將每一個單獨結點按照業務分類，如此可以形成一個有向圖。如圖5所示。

圖5　蟻群算法資源示意圖

形成初始資源圖后，為蟻群算法的進行形成初始信息素，具體公式為

(10)

ιij(t)表示在t時刻從結點i到結點j的路徑(用Eij表示)的信息素。

4.2.2轉移概率設計

(11)

式中，α為信息素的相對重要程度，β為啟發式因子的相對重要程度，Jk(i)為螞蟻k下一步允許選擇的結點集合。τij(t)為結點i與結點j之間的信息素濃度。ηij(t)表示結點i與結點j之間的啟發式因子，即螞蟻由結點i與結點j得可行性程度。h(j)為適應性檢查，公式為

(12)

式中Mj為第j個刀片服務器的CPU核數，mji為第j個刀片服務器上第i個虛擬機的CPU設置核數，Nj為第j個刀片服務器的網絡帶寬，nji為第j個刀片服務器上第i個虛擬機設置的網絡帶寬。

4.2.3信息素更新

當所有螞蟻完成一次周期后，各路徑的信息素更新公式如下所示：

ιij(t+1)=(1-ξ)ιij(t)+Διij

(13)

式中ξ∈(0,1)為信息素更新系數，1-ξ表示信息素殘留系數，ιij(t)表示t時刻從結點i到j的信息素。Διij表示t時刻m只螞蟻總共遺留在路徑eij上的信息素。

4.2.4終止條件

當蟻群算法滿足以下任一條件時,停止迭代,結束算法，得到最優解。

1) 迭代次數number達到設定的最大迭代次數ymax時；

2) 當新種群的子代進化出現明顯停滯現象時。設置群體的總適應度進化率vmin，即群體總適應度最小增長值。若增長率小于vmin，則結束迭代。如下式：

(14)

5　結語

文章通過詳細論述了虛擬機優化設置過程中的資源分配原則，利用遺傳算法得到最優解若干，避免陷入局部最優解的同時，提高了算法速率，再利用蟻群算法得到最優解，為整個艦船刀片服務器虛擬機優化設置求得最優設置方案。在保證艦船業務計算性能要求的同時，提高了艦船虛擬機資源的利用率。

[1] Smith J and Nair R. Virtual Machines: Versatile Platforms for Systems and Processes[M]. Morgan Kaufmann,2005:1-35.

[2] Rosenblum M and Garfinkel T. Virtual Machine Monitors: Current Technology and Future Trends[J]. IEEE Computer,2005,38(5):39-47.

[3] 鄧莉.基于虛擬機遷移的動態資源配置研究[D].武漢:華中科技大學，2013.

[4] 古俐明.集群服務器負載均衡技術研究[J].微計算機信息,2007，23(34)：112-114.

[5] 潘飛,蔣從鋒,徐向華等.負載相關的虛擬機放置策略[J].小型微型計算機系統,2013,34(3):520-524.

[6] 劉愉,趙志文,李小蘭等.云計算環境中優化遺傳算法的資源調度策略[J].北京師范大學學報:自然科學版,2012(8):378-383.

[7] 華夏渝,鄭駿,胡文心.基于云計算環境的蟻群優化計算資源分配算法[J].華東師范大學學報:自然科學版,2010(1):127-134.

[8] Goiri I, Guitart J, Torres J. Economic model of a Cloud provider operating in a federatedCloud [J]. Information Systems Frontiers,2012,14(4):827-843.

[9] 程國建,劉麗景,石彩云,等.一種混合遺傳算法在云計算負載均衡中的應用研宄[J].西安石油大學報(自然科學版),2012,27(2):93-97.

[10] 鄧德傳.虛擬機資源分配的非合作博弈標價模型研究[D].杭州:杭州電子科技大學,2011.

Optimization Settings of Virtual Machine of Warship Based on Hybrid Algorithm*

This paper introduces the optimization design of virtual machine the blade server with considering the calculation of performance requirements of ship business. The factors of virtual machine setting are analyzed. Combining the advantages of genetic algorithm and ant colony algorithm, hybrid optimization algorithm is formed, and the implementation process of optimized settings of virtual machine with using hybrid algorithm is described in detail.

virtual machine, hybrid algorithm, optimized settings

2016年2月11日,

2016年3月23日

閔紹榮,男,碩士,研究員,研究方向：艦船信息系統設計研究、作戰效能評估。趙俊杰,男,碩士研究生，研究方向：艦船信息系統設計研究、作戰效能評估。謝紅勝,男,博士,高級工程師,研究方向：艦船電子工程，決策理論與方法。

TP301.6

10.3969/j.issn.1672-9730.2016.08.027