閔紹榮　趙俊杰　謝紅勝

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

MIN Shaorong　ZHAO Junjie　XIE Hongsheng

(China Ship Development and Design Center, Wuhan　430064)

?

基于混合算法的艦船虛擬機優(yōu)化設(shè)置方案研究*

閔紹榮趙俊杰謝紅勝

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

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

虛擬機; 混合算法; 優(yōu)化設(shè)置

MIN ShaorongZHAO JunjieXIE Hongsheng

(China Ship Development and Design Center, Wuhan430064)

Class NumberTP301.6

1　引言

隨著虛擬機技術(shù)的飛速發(fā)展，虛擬機技術(shù)必將廣泛運用于艦船作戰(zhàn)平臺、艦艇作戰(zhàn)系統(tǒng)等方面的優(yōu)化設(shè)計領(lǐng)域，依據(jù)艦船業(yè)務(wù)的差異性進行艦船虛擬機資源的優(yōu)化設(shè)置，是一種全新的研究方向，隨著艦艇研制技術(shù)的發(fā)展，該方向的研究工作將逐步得到重視[1～2]。

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

2　優(yōu)化設(shè)置多因素分析

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

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

(1)

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

(2)

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

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

3　混合算法框架

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

圖1　混合算法框架圖

4　算法模型與實現(xiàn)流程

4.1遺傳算法初次分配

4.1.1遺傳編碼

根據(jù)艦船多層級刀片服務(wù)器虛擬機優(yōu)化設(shè)置中數(shù)據(jù)結(jié)構(gòu)特點，本文研究選擇樹形編碼技術(shù)，相比于其他編碼技術(shù)，樹形編碼技術(shù)對數(shù)據(jù)進行分級歸類，便于對本文研究中存在的不同類型數(shù)據(jù)進行編碼。具體的編碼規(guī)則如下。

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

(3)

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

圖2　樹形編碼

4.1.2適應(yīng)度函數(shù)設(shè)計

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

(4)

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

(5)

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

(6)

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

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

(7)

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

4.1.3生成初始種群

設(shè)種群規(guī)模為M，艦船業(yè)務(wù)數(shù)為N。生成初始種群的算法流程如圖3所示。

圖3　生成初始種群

4.1.4選擇復(fù)制

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

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

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

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

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

4.1.5交叉、變異操作

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

圖4　染色體交換

4.1.6終止條件與參數(shù)控制

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

lmin≤num≤lmax

(8)

對群體適應(yīng)度進行檢測，設(shè)置群體的總適應(yīng)度進化率wmin，即群體總適應(yīng)度最小增長值。若增長率小于wmin，則結(jié)束迭代。公式為

(9)

4.2蟻群算法優(yōu)化求解

4.2.1設(shè)置蟻群算法初始信息素

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

圖5　蟻群算法資源示意圖

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

(10)

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

4.2.2轉(zhuǎn)移概率設(shè)計

(11)

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

(12)

式中Mj為第j個刀片服務(wù)器的CPU核數(shù)，mji為第j個刀片服務(wù)器上第i個虛擬機的CPU設(shè)置核數(shù)，Nj為第j個刀片服務(wù)器的網(wǎng)絡(luò)帶寬，nji為第j個刀片服務(wù)器上第i個虛擬機設(shè)置的網(wǎng)絡(luò)帶寬。

4.2.3信息素更新

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

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

(13)

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

4.2.4終止條件

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

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

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

(14)

5　結(jié)語

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

[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] 鄧莉.基于虛擬機遷移的動態(tài)資源配置研究[D].武漢:華中科技大學(xué)，2013.

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

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

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

[7] 華夏渝,鄭駿,胡文心.基于云計算環(huán)境的蟻群優(yōu)化計算資源分配算法[J].華東師范大學(xué)學(xué)報:自然科學(xué)版,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] 程國建,劉麗景,石彩云,等.一種混合遺傳算法在云計算負載均衡中的應(yīng)用研宄[J].西安石油大學(xué)報(自然科學(xué)版),2012,27(2):93-97.

[10] 鄧德傳.虛擬機資源分配的非合作博弈標價模型研究[D].杭州:杭州電子科技大學(xué),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日

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

TP301.6

10.3969/j.issn.1672-9730.2016.08.027