用于多维尺寸可变装箱的遗传算法新编码

董其欢

摘 要： 传统的装箱算法已经无法解决多维尺寸可变装箱问题，而用遗传算法获取近似最优解的方法被越来越多的学者采用。针对传统遗传算法在多维尺寸可变装箱问题中的低效编码方式，文章提出一种新型的遗传算法编码方式。在某公司虚拟机资源分配场景下进行实验，并与传统FFD算法及传统编码方式的遗传算法进行对比。结果表明采用新编码方式的遗传算法结果更优。

关键词： 多维； 尺寸可变装箱问题； 遗传算法； 编码方式

中图分类号：TP301.6 文献标志码：A 文章编号：1006-8228（2018）08-61-03

New coding of genetic algorithm for multi-dimensional variable size bin packing problem

Dong Qihuan

（Hangzhou Dianzi University， Hangzhou， Zhejiang 310018， China）

Abstract： Traditional bin packing algorithm cannot resolve multi-dimensional variable size bin packing problem， so many researcher choose Genetic algorithm to get an approximate optimal solution. Aiming at the inefficient coding of traditional Genetic algorithm in multi-dimensional variable size bin packing problem， this article presented a new coding method of Genetic algorithm. The method is verified in a company's virtual machine resource assignment scenario， and compared with traditional FFD algorithm and the Genetic algorithm with traditional coding， the results show that the Genetic algorithm with new coding has a better performance.

Key words： multi-dimension； variable size bin packing problem； Genetic algorithm； coding

0 引言

裝箱问题在实际生活、生产中应用广泛。对于一维装箱问题的研究非常多，除了传统的FDD[1]，BFD算法，还有很多学者使用各种遗传算法解决这个问题[2]。尺寸可变装箱是经典装箱问题的一种扩展，即存在不同尺寸的物品和箱子，要求将物品全部装入箱子后，箱子的总容量最小。不过一般的尺寸可变装箱问题只考虑了一个尺寸维度，然而实际工程中尺寸都是多维的，比如运输集装箱要考虑物品的长、宽、高以及重量，快递包裹中物品的重量、体积，价值等[3]。适用于传统一维装箱问题的FFD、BFD等算法，在多维尺寸可变装箱问题场景下会产生大量的空闲资源碎片。而传统的遗传算法，在多维尺寸可变装箱场景使用时会有编码长度过长、计算缓慢、效率低下的问题。

某公司云服务器在分配虚拟机的过程中，根据虚拟机类型、数量以及服务器类型进行优化分配，优化分配要考虑的维度有CPU和内存两个维度，这是一个典型的多维尺寸可变装箱应用场景。本文针对这个优化分配场景，建立数学模型，并采用一种新型编码方式的遗传算法来解决这个分配问题。用C++语言实现该遗传算法，并同时实现了传统的FFD算法和传统物品编码方式的遗传算法，经过试验对比，结果表明采用了新编码方式的遗传算法优于传统遗传算法和FFD算法。并且相比于传统遗传算法，新编码方式在计算速度上有巨大的提升。

1 问题描述和数学模型

某公司云服务器在分配虚拟机资源过程中，要同一时间段处理一批虚拟机的申请。分配过程中要同时考虑各个虚拟机需要的CPU资源和内存资源，并且云服务器种存在多种规格的服务器。研究的目的是在把所有的虚拟机分配到服务器上后，所使用的服务器总资源尽量小，即产生的空闲资源碎片尽量少，这样可以最大限度的利用服务器资源，以降低运营成本。

可将此问题进行数学描述：计划要分配的虚拟机类型有K种，其中第i种虚拟机类型需要配置数量为Ni、单个虚拟机需要的CPU个数为Ci、需要的内存数量为Mi， i∈{（1，2，3，4，…，K）}；给定服务器类型L种，设其中第j种服务器类型计划使用的数量为SNj、单个服务器拥有的CPU数量为SCj、内存数量为SMj，j∈{（1，2，3，4，…，L）}；分配结果评分公式如下：

其中ScoreC代表CPU的资源使用率，ScoreM代表内存的资源使用率，最终的评估结果两者各占50%权重，Score为分配方案的最终得分。

2 算法的研究与设计

在传统的装箱问题中，遗传算法主要采用两种编码方式：基于箱子的编码方式（BBR）和基于物品的编码方式（ORB）[4]；经典的基于箱子编码方式的遗传算法是Hybrid Grouping Genetic Algorithm（HGGA）算法[5]，而Multi-chromosomal Grouping Genetic Algorithm（MGGA）算法[6]正好相反，代表了基于物品编码方式的遗传算法。然而在箱子尺寸可变并且尺寸维度不是惟一的情况下，这些传统的遗传算法因为要在线计算每个种群的装箱方案，而且在适应度函数中要嵌套FFD算法等其他装箱算法，所以计算速度慢，效率低。显然在线计算是遗传算法的瓶颈所在，国内有学者开始尝试离线算法[7]。为了提高遗传迭代效率，加快收敛速度，本次研究采用一种新型半离线计算的编码方式：先将每种箱子满配置的分配方案保存在一张列表中，用列表的行索引作为基因，每个染色体就是一个索引的集合；在遗传过程中，计算染色体的适应度函数时只需对其基因进行查表即可获取配置方案，从而快速计算出其适应值，显著提高遗传效率。

2.1 染色體结构设计

根据本次研究的实验场景，将所有的服务器满配置情况进行计算并保存到一张表中。对于每种服务器类型，满配置的情况即满足服务器CPU和内存同时被全部占用：

令wi的集合为W，Ci的集合为C，Mi的集合为M，则方程组化为：

求得W的所有解的集合构成基因表的一部分，所有类型的服务器的解集构成完成的基因表。以本次研究的场景为例，服务器类型分为General型（56个CPU，128G内存）、High-Performance型（84个CPU，256G内存）和Large-Memory型（112个CPU，192G内存），需要分配的虚拟机类型为Flavor1（需要1个CPU，1G内存）、Flavor2（需要1个CPU，2G内存）和Flavor3（需要1个CPU，4G内存）。比如对于General型的服务器，满配置一共有17种解，解集为{{0，48，8}，{2，45，9}，{4，42，10}，…，{32，0，24}}，其中第一个解表示服务器种配置48个Flavor2型的虚拟机和8个Flavor3虚拟机，第二个解表示配置2个Flavor1型的虚拟机、45个Flavor2型的虚拟机和9个Flavor3型的虚拟机。同理可以求得：Large-Memory型服务器有14个解、Large-Memory型服务器27个解。将所有的解组合成一张二维表，其中的每一行代表一种服务器满配置的方案，每行中的元素代表该方案中各个虚拟机类型配置的数量。

染色体由基因表的索引号组成，染色体中的每个基因代表一个服务器的满配置方案，比如一个染色体{0，2，3，0，2}，如图1所示，表示本次分配使用5个General型的服务器，第一个服务器按基因表中的第0条方案即{0，48，8}配置，第二个服务器按基因表中的第2条方案即{4，42，10}配置，以此类推。

这种基因编码方式兼顾了物品和箱子的表达，并且由于离线设计了配置表，为后期的离线计算提供了部分直接查询的结果，明显加快了计算速度。

2.2 适应度函数设计

适应度函数的输出值直接使用本次研究的评估公式，即服务器资源的使用率。基于新的编码方式，已经给出了配置方案，所以再计算服务器资源使用率时，不需要重新计算虚拟机的配置顺序，可以直接通过染色体中基于的组合来确定适应度的值。

显然大部分情况下，满配置方案是无法凑巧的实现，所以根据基因中的方案判断方案是否真正可行是必要的环节。

首先计算染色体所有基因中各个类型的虚拟机之和SUMi：

再求出和实际配置情况的差距?Ni：

很明显一个Flavor3的配置资源可以配置一个Flavor1或Flavor2，而4个Flavor1的配置资源才能放置一个Flavor3，所以通过比较?N集合中各个元素即可得方案是否可行。如果方案不可行即服务器组合无法容纳目标Flavor数量，则输出资源配置率为0；否则根据目标虚拟机数量和染色体中的基因组合输出配置率usageRate：

3 实验对比

针对3种服务器类型和3种虚拟机类型的场景，随机设置20种虚拟机组合。使用C++编程语言分别实现了采用新型编码方式的遗传算法、传统的基于箱子的编码方式（BBR）的遗传算法以及传统的FFD装箱算法[9]。实验结果表明，采用新型编码方式的遗传算法得分要高于其他两种传统算法，结果如图2所示；而遗产效率显著优于传统遗传算法，结果如图3所示。

4 结束语

本文针对多维尺寸可变装箱问题，提出了一种新的遗传编码，该遗传编码具有解码快、适应度函数计算效率高的特定。通过和传统遗传算法以及传统FFD装箱算法的实验对比，实验数据表明利用该编码可以显著提高遗传效率，获取更优的近似解。虽然本文的模型和算法是为了解决服务器分配虚拟机的场景，但该遗传编码也可以通用到其他类似的多维尺寸可变装箱场景，适用于很多实际生产、生活场景。

这种遗传编码方式也有不足之处，基因表长度和物品种类的数量并非线性关系，在物品种类增长的情况下，基因表长度的增长要快于物品种类的增长。如何在物品种类增长的情况下，进一步控制基因表的长度使之在可使用范围内，是下一步需要研究的内容。

参考文献（References）：

[1] Galambos G， Woeginger G J. On-line bin packing-A

restricted survey[J]. Zeitschrift Für Operations Research，1995.42（1）：25-45

[2] 王静莲，刘弘，李少辉.基于遗传算法的集装箱货物装配方案

研究[J].计算机工程与应用，2005.41（21）：222-223

[3] Friesen D K， Langston M A. Variable Sized Bin Packing[J].

Siam Journal on Computing，2006.15（1）：222-230

[4] 玄光男，程润伟.遗传算法与工程优化[M].清华大学出版社，

2004.

[5] Singh A， Gupta A K. Two heuristics for the one-

dimensional bin-packing problem[J]. Or Spectrum，2007.29（4）：765-781

[6] Bhatia A K， Basu S K. Packing Bins Using

Multi-chromosomal Genetic Representation and Better-

Fit Heuristic[C]// Neural Information Processing， International Conference， ICONIP 2004， Calcutta， India， November 22-25， 2004， Proceedings. DBLP，2004：181-186

[7] 刘瑞瑞.基于遗传模拟退火算法的三维离线装箱优化问题研

究[D].吉林大学硕士学位论文，2014.

[8] Rhee W T， Talagrand M. Martingale inequalities and

NP-complete problems[M]. INFORMS，1987.

[9] Johnson D S， Demers A， Ullman J D， et al. Worst-Case

Performance Bounds for Simple One-Dimensional Packing Algorithms[J]，2008.3（4）：299-325