用于多維尺寸可變裝箱的遺傳算法新編碼

董其歡

摘 要： 傳統(tǒng)的裝箱算法已經(jīng)無法解決多維尺寸可變裝箱問題，而用遺傳算法獲取近似最優(yōu)解的方法被越來越多的學(xué)者采用。針對傳統(tǒng)遺傳算法在多維尺寸可變裝箱問題中的低效編碼方式，文章提出一種新型的遺傳算法編碼方式。在某公司虛擬機資源分配場景下進行實驗，并與傳統(tǒng)FFD算法及傳統(tǒng)編碼方式的遺傳算法進行對比。結(jié)果表明采用新編碼方式的遺傳算法結(jié)果更優(yōu)。

關(guān)鍵詞： 多維； 尺寸可變裝箱問題； 遺傳算法； 編碼方式

中圖分類號：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 引言

裝箱問題在實際生活、生產(chǎn)中應(yīng)用廣泛。對于一維裝箱問題的研究非常多，除了傳統(tǒng)的FDD[1]，BFD算法，還有很多學(xué)者使用各種遺傳算法解決這個問題[2]。尺寸可變裝箱是經(jīng)典裝箱問題的一種擴展，即存在不同尺寸的物品和箱子，要求將物品全部裝入箱子后，箱子的總?cè)萘孔钚　２贿^一般的尺寸可變裝箱問題只考慮了一個尺寸維度，然而實際工程中尺寸都是多維的，比如運輸集裝箱要考慮物品的長、寬、高以及重量，快遞包裹中物品的重量、體積，價值等[3]。適用于傳統(tǒng)一維裝箱問題的FFD、BFD等算法，在多維尺寸可變裝箱問題場景下會產(chǎn)生大量的空閑資源碎片。而傳統(tǒng)的遺傳算法，在多維尺寸可變裝箱場景使用時會有編碼長度過長、計算緩慢、效率低下的問題。

某公司云服務(wù)器在分配虛擬機的過程中，根據(jù)虛擬機類型、數(shù)量以及服務(wù)器類型進行優(yōu)化分配，優(yōu)化分配要考慮的維度有CPU和內(nèi)存兩個維度，這是一個典型的多維尺寸可變裝箱應(yīng)用場景。本文針對這個優(yōu)化分配場景，建立數(shù)學(xué)模型，并采用一種新型編碼方式的遺傳算法來解決這個分配問題。用C++語言實現(xiàn)該遺傳算法，并同時實現(xiàn)了傳統(tǒng)的FFD算法和傳統(tǒng)物品編碼方式的遺傳算法，經(jīng)過試驗對比，結(jié)果表明采用了新編碼方式的遺傳算法優(yōu)于傳統(tǒng)遺傳算法和FFD算法。并且相比于傳統(tǒng)遺傳算法，新編碼方式在計算速度上有巨大的提升。

1 問題描述和數(shù)學(xué)模型

某公司云服務(wù)器在分配虛擬機資源過程中，要同一時間段處理一批虛擬機的申請。分配過程中要同時考慮各個虛擬機需要的CPU資源和內(nèi)存資源，并且云服務(wù)器種存在多種規(guī)格的服務(wù)器。研究的目的是在把所有的虛擬機分配到服務(wù)器上后，所使用的服務(wù)器總資源盡量小，即產(chǎn)生的空閑資源碎片盡量少，這樣可以最大限度的利用服務(wù)器資源，以降低運營成本。

可將此問題進行數(shù)學(xué)描述：計劃要分配的虛擬機類型有K種，其中第i種虛擬機類型需要配置數(shù)量為Ni、單個虛擬機需要的CPU個數(shù)為Ci、需要的內(nèi)存數(shù)量為Mi， i∈{（1，2，3，4，…，K）}；給定服務(wù)器類型L種，設(shè)其中第j種服務(wù)器類型計劃使用的數(shù)量為SNj、單個服務(wù)器擁有的CPU數(shù)量為SCj、內(nèi)存數(shù)量為SMj，j∈{（1，2，3，4，…，L）}；分配結(jié)果評分公式如下：

其中ScoreC代表CPU的資源使用率，ScoreM代表內(nèi)存的資源使用率，最終的評估結(jié)果兩者各占50%權(quán)重，Score為分配方案的最終得分。

2 算法的研究與設(shè)計

在傳統(tǒng)的裝箱問題中，遺傳算法主要采用兩種編碼方式：基于箱子的編碼方式（BBR）和基于物品的編碼方式（ORB）[4]；經(jīng)典的基于箱子編碼方式的遺傳算法是Hybrid Grouping Genetic Algorithm（HGGA）算法[5]，而Multi-chromosomal Grouping Genetic Algorithm（MGGA）算法[6]正好相反，代表了基于物品編碼方式的遺傳算法。然而在箱子尺寸可變并且尺寸維度不是惟一的情況下，這些傳統(tǒng)的遺傳算法因為要在線計算每個種群的裝箱方案，而且在適應(yīng)度函數(shù)中要嵌套FFD算法等其他裝箱算法，所以計算速度慢，效率低。顯然在線計算是遺傳算法的瓶頸所在，國內(nèi)有學(xué)者開始嘗試離線算法[7]。為了提高遺傳迭代效率，加快收斂速度，本次研究采用一種新型半離線計算的編碼方式：先將每種箱子滿配置的分配方案保存在一張列表中，用列表的行索引作為基因，每個染色體就是一個索引的集合；在遺傳過程中，計算染色體的適應(yīng)度函數(shù)時只需對其基因進行查表即可獲取配置方案，從而快速計算出其適應(yīng)值，顯著提高遺傳效率。

2.1 染色體結(jié)構(gòu)設(shè)計

根據(jù)本次研究的實驗場景，將所有的服務(wù)器滿配置情況進行計算并保存到一張表中。對于每種服務(wù)器類型，滿配置的情況即滿足服務(wù)器CPU和內(nèi)存同時被全部占用：

令wi的集合為W，Ci的集合為C，Mi的集合為M，則方程組化為：

求得W的所有解的集合構(gòu)成基因表的一部分，所有類型的服務(wù)器的解集構(gòu)成完成的基因表。以本次研究的場景為例，服務(wù)器類型分為General型（56個CPU，128G內(nèi)存）、High-Performance型（84個CPU，256G內(nèi)存）和Large-Memory型（112個CPU，192G內(nèi)存），需要分配的虛擬機類型為Flavor1（需要1個CPU，1G內(nèi)存）、Flavor2（需要1個CPU，2G內(nèi)存）和Flavor3（需要1個CPU，4G內(nèi)存）。比如對于General型的服務(wù)器，滿配置一共有17種解，解集為{{0，48，8}，{2，45，9}，{4，42，10}，…，{32，0，24}}，其中第一個解表示服務(wù)器種配置48個Flavor2型的虛擬機和8個Flavor3虛擬機，第二個解表示配置2個Flavor1型的虛擬機、45個Flavor2型的虛擬機和9個Flavor3型的虛擬機。同理可以求得：Large-Memory型服務(wù)器有14個解、Large-Memory型服務(wù)器27個解。將所有的解組合成一張二維表，其中的每一行代表一種服務(wù)器滿配置的方案，每行中的元素代表該方案中各個虛擬機類型配置的數(shù)量。

染色體由基因表的索引號組成，染色體中的每個基因代表一個服務(wù)器的滿配置方案，比如一個染色體{0，2，3，0，2}，如圖1所示，表示本次分配使用5個General型的服務(wù)器，第一個服務(wù)器按基因表中的第0條方案即{0，48，8}配置，第二個服務(wù)器按基因表中的第2條方案即{4，42，10}配置，以此類推。

這種基因編碼方式兼顧了物品和箱子的表達，并且由于離線設(shè)計了配置表，為后期的離線計算提供了部分直接查詢的結(jié)果，明顯加快了計算速度。

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

適應(yīng)度函數(shù)的輸出值直接使用本次研究的評估公式，即服務(wù)器資源的使用率。基于新的編碼方式，已經(jīng)給出了配置方案，所以再計算服務(wù)器資源使用率時，不需要重新計算虛擬機的配置順序，可以直接通過染色體中基于的組合來確定適應(yīng)度的值。

顯然大部分情況下，滿配置方案是無法湊巧的實現(xiàn)，所以根據(jù)基因中的方案判斷方案是否真正可行是必要的環(huán)節(jié)。

首先計算染色體所有基因中各個類型的虛擬機之和SUMi：

再求出和實際配置情況的差距?Ni：

很明顯一個Flavor3的配置資源可以配置一個Flavor1或Flavor2，而4個Flavor1的配置資源才能放置一個Flavor3，所以通過比較?N集合中各個元素即可得方案是否可行。如果方案不可行即服務(wù)器組合無法容納目標Flavor數(shù)量，則輸出資源配置率為0；否則根據(jù)目標虛擬機數(shù)量和染色體中的基因組合輸出配置率usageRate：

3 實驗對比

針對3種服務(wù)器類型和3種虛擬機類型的場景，隨機設(shè)置20種虛擬機組合。使用C++編程語言分別實現(xiàn)了采用新型編碼方式的遺傳算法、傳統(tǒng)的基于箱子的編碼方式（BBR）的遺傳算法以及傳統(tǒng)的FFD裝箱算法[9]。實驗結(jié)果表明，采用新型編碼方式的遺傳算法得分要高于其他兩種傳統(tǒng)算法，結(jié)果如圖2所示；而遺產(chǎn)效率顯著優(yōu)于傳統(tǒng)遺傳算法，結(jié)果如圖3所示。

4 結(jié)束語

本文針對多維尺寸可變裝箱問題，提出了一種新的遺傳編碼，該遺傳編碼具有解碼快、適應(yīng)度函數(shù)計算效率高的特定。通過和傳統(tǒng)遺傳算法以及傳統(tǒng)FFD裝箱算法的實驗對比，實驗數(shù)據(jù)表明利用該編碼可以顯著提高遺傳效率，獲取更優(yōu)的近似解。雖然本文的模型和算法是為了解決服務(wù)器分配虛擬機的場景，但該遺傳編碼也可以通用到其他類似的多維尺寸可變裝箱場景，適用于很多實際生產(chǎn)、生活場景。

這種遺傳編碼方式也有不足之處，基因表長度和物品種類的數(shù)量并非線性關(guān)系，在物品種類增長的情況下，基因表長度的增長要快于物品種類的增長。如何在物品種類增長的情況下，進一步控制基因表的長度使之在可使用范圍內(nèi)，是下一步需要研究的內(nèi)容。

參考文獻（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].計算機工程與應(yīng)用，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] 玄光男，程潤偉.遺傳算法與工程優(yōu)化[M].清華大學(xué)出版社，

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] 劉瑞瑞.基于遺傳模擬退火算法的三維離線裝箱優(yōu)化問題研

究[D].吉林大學(xué)碩士學(xué)位論文，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