用于虛擬機安置問題的快速啟發式算法

梁建斌

（廣東工業大學，廣州510006）

0 引言

云計算是分布式計算的一種特殊形式［1］，它可以按需訪問可配置的計算資源共享池，如網絡、服務器、存儲和服務［2］。它通過最少的管理工作或者與最少的服務進行快速配置和發布［3］，是網格計算、并行計算和分布式計算的商業實現［4］。虛擬化技術提供云服務的技術支持，所有硬件資源經過虛擬化成為統一的資源［5］。虛擬機根據客戶應用和所需硬件資源（如CPU、RAM和ROM等）創建，然后托管到服務器上運行［6］。

隨著客戶對計算能力的需求不斷增長，促使云服務提供商部署越來越多的數據中心。用于服務器以及冷卻服務器的設備能源成本顯著增加，甚至已經超過硬件的購置成本［7］。云數據中心的能源相關成本達到運營總成本的一半［8］。因此，數據中心的生命周期成本通常由能耗決定［9］。目前，數據中心的資源使用與能源消耗比例并不高。即使服務器的CPU使用率只有10%，仍消耗服務器能耗峰值的50%以上的能源［10］。虛擬化技術允許一臺服務器上同時讓幾個虛擬機分享硬件資源，與Xen、VMware和Hyper-V一樣，允許將物理資源作為虛擬機進行共享與調配［11］，使得虛擬機整合變得可行。

虛擬機整合可以降低能源消耗，因此虛擬機安置問題（Virtual Machine Placement，VMP）被提出，一個尋求在服務器上獲得虛擬機最佳部署的問題［12－13］。有效的分配有助于通過降低運行主機的操作成本來實現經濟效益的最大化［14］。VMP是NP難問題［15］，計算難度大，且需要盡可能少的運算時間。過去的研究中，線性規劃是VMP的最早解決方式［16－17］。線性規劃簡單，且確保獲得最優解。但是隨著問題規模增大，計算時間將不可接受。啟發式算法被應用解決VMP［18］，然而啟發式算法方法簡單，計算時間短，但容易陷入局部最優。使用群體算法解決VMP，如蟻群系統、遺傳算法（Genetic Algorithm，GA）［19］和 粒 子 群 優 化（Particle Swarm Optimization，PSO）［20］，不僅避免陷入局部最優，也能在可控時間內得到高質量解。然而，目前群體算法的運算時間明顯過長。雖然啟發式算法具有陷入局部最優的風險，如果克服了這個缺點，可以在更短的時間內獲得可行解。本文提出一種避免局部最優解的啟發式算法——強插算法。

本文的其余部分如下：第1部分回顧VMP的相關研究；第2部分概述VMP的模型和強插算法的算法原理；第3部分描述強插算法的具體步驟和流程；第4部分分別使用強插算法，RGGA（Reordering Grouping Genetic Algorithm）［19］和OMEACS（Order Exchange and Migration Ant Colony System）［21］在不同的環境下實驗并對數據進行比較和分析；第5部分給出結論。

1 相關工作

線性規劃是最早用于解決虛擬機整合問題的算法［22］。FFD（First-Fit Decreasing）是背包問題中簡單且結果可靠的算法。BISON（Bin Packing Solution Procedure）算法［23］首先對所有背包采用FFD策略，然后執行分支與綁定的步驟。MBS（Minimal Bin Slack）［24］以背包為主，從物品中找到最適合當前背包的組合。Wu等人［25］提出了一種基于模擬退火的局部搜索算法。Murtazaev等人提出了結合First-Fit和Best Fit算法的SERCON方法，同時考慮最小化服務器和發生遷移的虛擬機數量［26］。Zhu等人［27］同時考慮CPU、內存和網絡帶寬因素，設計不同的算法，最大限度地降低能耗。Lago等人［28］同時考慮了服務器的硬件和帶寬，提出一種在異構環境下調度虛擬機的啟發式算法。

進化算法因為在VMP中的優異表現而得到了發展［29］。VMP可被視作背包問題［19］，David Wilcox等人將FFD應用到GGA（Grouping Genetic Algorithm）中，并提供了可靠的交叉算子，從而提出RGGA算法。Ibrahim等人［30］在考慮響應時間的前提下，提出了一種自適應遺傳算法。Mi等人［31］使用GA同時優化資源使用率和減少能源消耗問題，多目標模型開始出現，一個改良的GA［32］使用了模糊多目標評價函數來優化VMP。Wang等人［33］提出了同時考慮最大化資源使用率，均衡多維資源的使用率和減少應用交流成本的優化模型，并使用GA進行解決。Raju等人［34］提出了EAMOCA（Energy-Aware Multi-Objective Chiropteran Algorithm）算法，其目的是在最大化資源利用率的同時最小化執行時間和能耗。Li等人［35］考慮了硬盤資源的上限和下限，將改進的PSO應用到VMP中，避免陷入局部最優。Wan等人［36］提出了一種同時考慮虛擬機熱／冷啟動和熱／冷關閉的云計算資源分析模型，得到云平臺的性能指標，并建立了一個多目標優化模型對云平臺的性能和成本進行優化。

2 背景

2.1 VMP

VMP目的是使用盡可能少的服務器容納所有的虛擬機。理想狀態下大部分服務器滿載。問題定義如下：

假設存在N個虛擬機（以下簡稱虛擬機）與M個服務器（以下簡稱服務器）。V＝｛v1，v2，...vi，...，vN｝代表虛擬機集合，vi＝｛vci，vri｝代表虛擬機vi需求的CPU與RAM資源。P＝｛p1，p2，...pi，...，pM｝代表服務器集合。pj＝｛pcj，prj｝代表服務器pj的CPU與RAM資源上限。B＝｛b1，b2，...，bi，...，bN｝代表安置方案，i∈［1，N］代表虛擬機編號，bi∈［1，N］表示將vi放入對應編號的服務器中。VMP問題如下描述：

式（2）中yj是服務器是否空閑的標志。如果yj＝0，代表該服務器空閑。式（3）與（4）分別統計每臺服務器中虛擬機占用CPU和RAM的總和，并要求各項資源的使用不能超出該服務器對應資源的上限。

2.2 First-Fit算法

用于VMP的First-Fit算法最早由文獻［5］提出。First-Fit算法難以得到VMP的最優解，但是時間復雜度低，且步驟簡單，用作強插算法的評價函數。

2.3 強插算法

在虛擬機的安置過程中會出現一個趨勢：各項資源需求小的虛擬機（以下簡稱小虛擬機）大量存在于高負載服務器中，各項資源需求量大的虛擬機（以下簡稱大虛擬機）大量存在于低負載服務器中。這個趨勢導致安置方案過早收斂于局部最優解。本文提出的強插算法的設計思路是避免這種趨勢的發生。也就是使用低負載服務器中的大虛擬機交換高負載服務器中若干個小虛擬機，從而打破安置方案的原有結構，而小虛擬機也盡可能不交換到低負載服務器中，進一步降低低負載服務器的負載。當存在若干個服務器負載足夠低，可進行虛擬機再安置，減少服務器數量。

強插算法需要解決的問題是：已知大虛擬機和服務器集合，如何從服務器集合中找到含有最合適用作交換的小虛擬機集合的服務器？該問題可被拆分為兩個子問題：

（1）交換后，服務器負載率的影響是否最低？

（2）交換的小虛擬機集合對其他服務器的提升效果是否最好？

強插算法的解決方案如下：

（1）從各個服務器中選出一批與大虛擬機需求比較接近的小虛擬機集合，并限制在對服務器負載率影響在不大的范圍里。為此算法使用了強插算子確保選出的小虛擬機集合的需求總和與大虛擬機的需求盡可能接近。

（2）從選出的所有集合中選出一個提升其他服務器負載表現最好的集合。為此算法使用了再填充算子，讓所有小虛擬機集合都嘗試安置到其他高負載服務器上。

強插算法每次迭代都需要先對服務器篩選。因此強插算法分為三個部分：選舉算子、變異算子和調整算子。

3 算法流程

3.1 初始化和參數設置

強插算法的參數會隨著計算規模增大而增大，因此需要對問題先執行一次First-Fit算法，得到初始的安置方案B。B的服務器數量與最優安置方案所需要的服務器數量處于同一數量級，用于估計計算規模。根據Pub計算：

其中pNum和wNum分別是候選服務器集合規模和惡劣服務器集合的規模。

3.2 選舉算子

選舉算子分為三步：評價，選出惡劣服務器集合，和選出候選服務器集合。首先每臺服務器統計各項資源使用情況，然后根據以下公式得到評價值：

其中pcj和prj分別是服務器的CPU和RAM資源上限，pccj和pcrj分別是服務器當前CPU和RAM的使用情況，ac和ar是服務器CPU資源上限和RAM資源上限的比值。當服務器CPU資源上限是RAM資源上限兩倍時，ac＝1，ar＝2。服務器的負載率越高，評價值越高。選取評價值最低的wNum臺服務器構成惡劣服務器集合。

候選服務器集合則由兩部分服務器構成：隨機服務器集合和較差服務器集合。較差服務器集合是除了惡劣服務器集合以外，負載率最差的服務器集合。由于負載率較低，在再填充算子中可以被安置入更多小虛擬機。隨機服務器集合是從未被選取的其他服務器中隨機選取。其中，較差服務器集合規模worsePMsSize

和隨機服務器集合規模randomPMsSize分別如下：

其中，ω是較差服務器占比。

3.3 變異算子

變異算子由強插算子和再填充算子組成。在一次變異中，需要依次選取惡劣服務器集合中的每一個大虛擬機執行強插算子，結果交由再填充算子進一步處理，決定最終的交換方案。

強插算子試圖將惡劣服務器集合中的所有大虛擬機都交換到候選服務器集合中，對負載率影響盡可能小的情況下改變候選服務器中的虛擬機結構。

為了交換的大虛擬機和小虛擬機集合的需求盡可能接近，在強插算子中，選中的大虛擬機需要對所有候選服務器進行一次強插算子，得到若干個候選的小虛擬機集合。大虛擬機和所有小虛擬機集合將通過再填充算子進一步處理。強插算子分為4個步驟：排序、產生計算序列、評價和篩選。

排序是以大虛擬機為對照，將候選服務器中的虛擬機進行分類和排序。排序的順序為：A類虛擬機、B類虛擬機、C類虛擬機和D類虛擬機。其中，A類虛擬機的各項資源需求都大于等于大虛擬機；B類虛擬機則具有一項資源需求大于大虛擬機，其余資源需求小于大虛擬機；C類虛擬機的資源需求都小于大虛擬機，但至少一項資源需求不低于大虛擬機該項資源需求的一半；D類虛擬機的資源需求都小于大虛擬機該項資源需求的一半。

產生計算序列將產生等同于B、C、D類虛擬機數量總和的計算序列。A類虛擬機不會產生計算序列，因為A類虛擬機各項資源需求都大于大虛擬機，如果發生交換，只讓服務器的各項資源使用率下降，且難以再填充到其他服務器。每個計算序列都以P排序的結果副本為初始序列，選取B、C、D類虛擬機中的未被選取過的一個虛擬機，從原來的位置中取出并放到序列的末尾，最后將大虛擬機放到序列的首位。形成一條新的計算序列。

對每一條計算序列使用First-Fit算子進行計算并根據以下公式進行評價：

其中pccsj和pcrsj分別是大虛擬機交換到服務器后，服務器的CPU和RAM使用情況。適應度越少，說明交換方案在強插算子中越合理。如果交換后，服務器的各項資源使用情況都上升，說明本次交換可以單純地提升服務器的負載率，因此適應度設置為0。否則使用服務器的資源空閑權重和作為評價值。

每條計算序列在經過First-Fit算子后，除了適應度外，還獲得了在First-Fit算子中無法被安置入服務器的虛擬機，它們構成了小虛擬機集合。小虛擬機集合將在大虛擬機對所有候選服務器都進行強插算子后進行匯總，并將交給再填充算子進行進一步的處理。

變異算子的最后，最終交換方案中剩余的小虛擬機集合將被安置到惡劣服務器中。為了更進一步降低惡劣服務器集合的總負載，再填充算子將盡可能地將虛擬機保留在候選服務器集合中。為了找到保留效果最好的小虛擬機集合，需要對強插算子得到的所有小虛擬機集合都執行一次再填充算子。再填充算子具有兩個步驟：排序和再填充與評價。

再填充算子通過提升候選服務器集合的總負載來降低惡劣服務器集合的總負載。一方面，資源需求量更大的虛擬機更難被安置入服務器。另一方面，將資源需求量大的虛擬機安置入候選服務器集合更符合再填充算子的目標。再填充算子需要先從資源需求量大的虛擬機開始執行，因此需要先對每個小虛擬機集合根據資源需求總量進行排序。資源需求總量的公式如下：

資源需求總量越大的虛擬機在排序后的序列中的位置越靠前。然后，根據排序后的序列執行再填充。首先，獲得除了該小虛擬機集合對應的服務器以外的所有候選服務器當前資源使用情況的副本。接著，從序列依次取出虛擬機，遍歷副本中的每個服務器。如果虛擬機可以被安置到該服務器中，那么更新副本中該服務器的資源使用情況，并從序列中去除掉該虛擬機。最后，計算序列的適應度。序列中可能存在無法被安置的虛擬機，而序列的適應度即序列中剩余虛擬機的資源需求總量。剩余的虛擬機集合和適應度值是該小虛擬機集合在再填充算子中的結果。

選出適應度最低的小虛擬機集合，它以及所對應的服務器編號和大虛擬機就是大虛擬機最終的交換方案。剩余的虛擬機集合將被隨機安置到惡劣服務器集合中的任意服務器中，且不會再參與變異算子。

3.4 調整算子

變異算子降低了惡劣服務器集合的總負載，但同時也帶來了新的問題：

（1）降低了總負載，但是不能降低服務器數量。

（2）由于變異算子的最后，將虛擬機隨機安置到惡劣服務器，可能會出現超載的情況。

問題1中，普遍的情況是存在若干低負載服務器，可通過重新安置其中的虛擬機來降低服務器的使用數量。問題2中，可以將重新安置超載服務器和低負載服務器中的虛擬機消除超載現象。因此，問題1和2可以合并為一個比VMP規模小的子問題。

子問題的復雜度低于VMP。由于出現問題的服務器都是惡劣服務器，經歷了變異算子，惡劣服務器集合的總負載很有可能降低了。原有的惡劣服務器集合安置已經是合理的安置方案，再得到一個合理的安置方案并不困難。另外，變異算子已經占用了大量運算時間，算法需要采用時間更短的調整算子來調整惡劣服務器集合中的虛擬機。調整算子分為兩個步驟：挑選服務器和remove算子。

首先，根據負載情況從所有服務器中選出符合以下條件的服務器：

其中，是負載系數。當一項資源使用率低于μ時，認為服務器的負載率過低。負載率過低的服務器和超載服務器將通過remove算子作進一步的處理。

在RGGA算法中，變異算子由swap算子，move算子和remove算子組成，swap算子和move算子提供的有效變異最多。但這兩個算子只能作用于兩個服務器之間，不適合多個服務器同時進行虛擬機整合。因此，強插算法采用remove算子作為調整算子。

為了提高remove算子的效率，調整算子將重復執行a次，選取服務器數量最少的安置方案作為調整算子的最終方案。

3.5 總流程

算法的總流程如圖1所示，具體步驟如下。

圖1 總體流程圖

（1）使用First-Fit算法，獲得初始安置方案B和Pub，根據Pub設置pNum和wNum。設置t＝0和Tmax。

（2）計算各個服務器的資源使用情況，并根據資源使用情況對所有服務器進行排序。

（3）使用選舉算子分別選出候選服務器集合和惡劣服務器集合。

（4）逐一選取惡劣服務器集合中的所有虛擬機，使用強插算子獲得該虛擬機對應的交換方案。并執行交換方案，更新候選服務器集合中的虛擬機構成。

（5）選出超載和低負載服務器，使用調整算子獲得一個合理的再安置方案。

（6）如果t＝Tmax，算法結束。否則，設置t＝t＋1并跳到步驟（2）。

4 實驗部分

實驗部分將測試強插算法的性能。所有算法均使用Java實現，硬件環境CPU型號Intel Core i5－7550，8G內存。包含4種不同環境下的實驗：TestA1和TestA2是同構服務器環境下不同虛擬機類型的兩個測試，TestB和TestC分別在同構服務器與異構服務器的環境下瓶頸資源測試。強插算法的對比算法是使用遺傳算法的RGGA和使用蟻群系統的OMEACS。強插算法的相關參數設置如下：ω＝0.4，μ＝0.99，a＝50。RGGA和OMEACS的參數值與原始論文中的一致。TestA1，TestA2和TestB中，最大迭代次數均為Tmax＝100，TestC由于異構環境更復雜，最大迭代次數均為Tmax＝1000。所有算法的最大迭代次數和FEs如表1所示。所有算法均每個實例中都獨立重復執行100次，FEs和運算時間對應首次得到全局最優解所需要的FEs和運算時間。

表1 各個算法最大迭代次數和FEs

4.1 TestA大規模同構服務器測試

TestA1的實例生成方法提出于RGGA，與TestA2具有相同的特點：理想安置方案中，服務器的所有資源都被生成的虛擬機占滿。TestA1具有9個實驗用例。所有用例的服務器都具有500單位CPU和500單位RAM；每個虛擬機的CPU需求是位于［1，128］的隨機整數，RAM需求是位于［0，100］的隨機整數。TestA1的虛擬機生成方法以服務器為單位，不斷生成虛擬機，直到存在虛擬機生成后，服務器某項資源不足以負載該虛擬機時，將該虛擬機的各項資源需求改為服務器剩余資源量，從而實現滿載。除最后一個虛擬機外，其他虛擬機都是隨機生成，因此各個虛擬機之間的資源需求差距很大。

續表

從表2看出，強插算法總能獲得比其他算法更好的結果，體現了強插算法在TestA1中的穩定性。RGGA在實例A11和A15中獲得與強插算法相同的最優解，但是平均值顯示出結果并不穩定。OMEACS則難以獲得與強插算法同等質量的解。此外，在所有實例中，強插算法首次獲得最優全局最優解的時間和FEs都遠低于RGGA和OMEACS。

表2 TestA1在不同虛擬機規模下的實驗結果對比

TestA2的虛擬機生成方式與TestA1不同。首先確定服務器安置的虛擬機數量，按照均勻分布的方式生成虛擬機的各項資源需求。因此，TestA2的所有實例的理想安置方案中的每個服務器的托管虛擬機之間的資源需求差別不大。對比表2和表3，TestA2具有相同的服務器和更少的虛擬機，但所有算法都需要更多的運算時間和FEs，說明TestA2難度高于TestA1。從表3可見，強插算法穩定得到最高質量的安置方案。RGGA在TestA2的總體表現弱于TestA1，僅在實例TestA21獲得與強插算法相同質量的安置方案，在其他實例則無法穩定。OMEACS無法獲得與強插算法相同質量的安置方案，且在A21、A22、A27中過早收斂于局部最優解中。強插算法在時間復雜度上依然優秀。

表3 TestA2在不同虛擬機規模下的實驗結果對比

從TestA可以看出，強插算法可以穩定得到接近于最優安置方案的方案，且首次獲得最優全局最優解的時間也遠低于其他算法，說明強插算法優化規則的合理性。

4.2 TestB大規模同構服務器測試

因為發展趨勢，RAM的體量比CPU大，往往CPU密集型的任務導致瓶頸資源問題。TestB設置了9個不同規模的實例B1～B9測試三個算法在瓶頸資源環境下的性能。所有實例服務器均擁有16核CPU和32GB的RAM；虛擬機的CPU需求是［1，4］中的隨機整數，RAM需求是［1，8］中的隨機整數，所有隨機整數服從均勻分布。每個虛擬機有25%幾率需求4內核，同時有25%幾率需求7GB或者8GB的RAM，因此CPU與RAM的使用率接近10∶9，CPU成為了瓶頸資源。TestB的虛擬機生成方法完全隨機，不會提前設置需求的服務器數量，并在生成后使用以下公式對服務器數量進行估計：

其中，pci和pri分別是第i臺服務器能提供的CPU和RAM資源上限，分別是該服務器上所有虛擬機需求的CPU和RAM總量。推算公式目的是以所有虛擬機需求總和的最大值來推算至少需要的服務器數量，在實際測試中，由于虛擬機需求的隨機性和復雜性，需要的服務器數量可能大于這個值。

表4包含了三個算法在TestB的表現。RGGA僅在B1和B3中獲得最優安置方案，OMEACS僅在B1和B2中獲得最優安置方案，但是兩個算法都不穩定。一方面，強插算法在所有的實例都能穩定地獲得最優安置方案。另一方面，強插算法首次獲得最優解所需要的運算時間和FEs遠低于RGGA和OMEACS。

表4 TestB在不同虛擬機規模下的實驗結果對比

4.3 TestC異構服務器環境下瓶頸資源問題

之前的測試，所有服務器都是同構服務器。TestC將在異構環境下進行測試。TestC根據目前兩種主流服務器型號設置實驗：s0（32核CPU和64GB的RAM）和s1（64核CPU和256GB內存）。TestC包含5個實例，s0和s1服務器的比例為1∶1。虛擬機的CPU資源需求是處于區間［1，8］的隨機整數，RAM資源需求是處于［1，32］的隨機整數。因此，TestC也是一個瓶頸資源場景。

表5包含了三種算法在TestC中的性能。平均值顯示強插算法和RGGA的性能相近。RGGA獲得所有實例中質量最好的安置方案，而強插算法在C2和C5中無法獲得與RGGA相同質量的安置方案。OMEACS僅在C1中獲得最優安置方案。這意味著在異構環境下，VMP問題變得更復雜，強插算法雖然表現不是最優秀，但首次獲得最優全局最優解的時間和FEs仍遠遠低于RGGA。而RGGA雖然可以獲得最優安置方案，但每次的運算結果并不穩定，導致運算時間不穩定。

表5 TestC在不同虛擬機規模下的實驗結果對比

4.4 參數測試

強插算法包含三個參數：較差服務器占比系數ω，調整數量μ和校驗系數a。為了研究這些參數對于安置方案質量的影響，使用TestA1對所有實例進行參數性能的評估。

首先測試較差服務器占比系數ω。在其余參數不變的情況下設置了從0.1－1.0的11個參數實驗。圖2在較差服務器占比系數在TestA的所有測試實例。隨著ω的增加，FEs不斷下降。但是運算時間經歷了下降后上升，曲線大致呈現凹谷的形狀。這說明當上升后，強插算子次數減少，強插算子運算時間上升，整體運算時間上升。當時ω＝0.4，運算時間達到最小值。所以，算法采用ω＝0.4。

圖2 不同的較差服務器占比系數在TestA1各個實例的表現

圖3是調整系數在TestA的所有測試實例。圖3中，FEs大致上隨著調整系數的增加而減少，運算時間大致上呈現凹谷形狀。強插算法通過強插算子和調整算子優化結果，調整次數少，會使算法依賴強插算子優化結果，導致運算時間增長。調整次數多，會進無效的調整算子。因此，在a＝50時獲得可接受的FEs和運算時間。

圖3 不同的調整系數在TestA1各個實例的表現

圖4是校驗系數在TestA的所有測試實例。由于μ＝1無法獲得最優安置方案，因此不予顯示。大體上，Fes一致呈現下降的趨勢。在TestA11-TestA14時，運算時間在μ＝0.98時獲得最小值。而隨著問題規模不斷增加，μ＝0.99才能獲得最小的運算時間。所以，強插算法采用μ＝0.99。

圖4 不同的校驗系數在TestA1各個實例的表現

4.5 收斂速度分析

本部分將評價強插算法的收斂性。使用TestA1為測試實例，使用強插算法，RGGA進行收斂性分析。每個算法具有100次迭代，獨立重復運行100次。

圖5是兩個算法在TestA各個實例中的收斂曲線圖。曲線中的每一個數值是算法100次運行的平均值。盡管RGGA一直在收斂，但是收斂速度過慢，甚至停留在局部最優解中，導致整體運算時間的增加。強插算法的初始化與RGGA類似，因此初始階段與RGGA接近，但是收斂速度快于RGGA，因此最早獲得質量最高的安置方案。

圖5 強插算法和RGGA的收斂曲線對比

5 結語

能源消耗已經是數據中心的主要運營成本，已有的VMP算法可以獲得高質量的安置方案，但是運算時間長。這促使我們提出基于啟發式算法的強插算法，在更短運算時間獲得合理的虛擬機安置方案，通過關閉空閑服務器最小化活動服務器數量。VMP問題是一個復雜的NP難問題，每個服務器中的虛擬機不僅作用于服務器的負載情況，更影響著其他服務器的虛擬機構成。當一個服務器中小虛擬機數量過多時，其他服務器由于缺少小虛擬機，空閑資源無法被利用，相互之間也難以進行虛擬機交換，因而負載率不高。為了解決這個現象，本文提出了強插算法。其中，強插算子將大虛擬機強行到服務器中，打亂服務器的虛擬機原有的虛擬機結構，釋放其中的小虛擬機，提高其他服務器負載。由于強插算子的強隨機性和明確的目的性，克服了啟發式算法的早熟問題。調整算子則用于調整強插算子導致的安置方案不合理的問題。

強插算法被用于不同規模下的同構或異構服務器的測試中。結果表明強插算法在絕大部分測試用例中可以穩定獲得最高質量的安置方案，且運算時間最短。即使不能獲得最高質量的安置方案，結果依然相當接近。結論是，強插算法可以被視作一種高效且高速的VMP算法。