基于混合算法的舰船虚拟机优化设置方案研究*

闵绍荣　赵俊杰　谢红胜

(中国舰船研究设计中心　武汉　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