基于改進模擬退火算法的虛擬機調度優(yōu)化方法

宋楊

（徐州生物工程職業(yè)技術學院 江蘇省徐州市 221006）

近年來，在計劃經(jīng)濟時期的制造企業(yè)生產(chǎn)過程中，仍然是采用人為管控的方式進行生產(chǎn)調度的安排，但是人為的調度難免會受到個人主觀情緒的影響，也無形中加劇了調度的偏差，影響其可靠性，再加上缺乏理論依據(jù)，往往會造成調度的時效性不夠理想，針對這一問題，虛擬機調度應運而生。借助云計算這一先進的計算理念展開，云計算調度算法會為虛擬機調度分配的多目標優(yōu)化。提供更多解決的思路，更能夠打破傳統(tǒng)人工手動調度存在的弊端。其中，基于云計算的負載均衡，更能夠實現(xiàn)資源開銷的合理分配，避免過多請求集中在一些硬件節(jié)點上所導致的網(wǎng)絡擁堵或性能下降[1]。

1 模擬退火算法相關概述

1.1 算法來源

模擬退火算法是由N.Metropolis 學者在1953年所提出的。直到1983年一些學者將模擬退火的核心思想加以優(yōu)化和改良，并將其于較為復雜組合優(yōu)化問題里加以利用，收到了很好的效果。至此其得到了越來越多學者關注，在應用上開始逐漸豐富起來，并引起其他國家關注，也開始擴展到更多的行業(yè)領域應用中。

1.2 Metropolis接受準則

該準則核心思想正是模擬退火算法，其以固體物質于退火過程里表現(xiàn)出的特點為依據(jù)。物理層面固體退火當中，會大致分為三個物理過程。首先是物質升溫，當物質吸收了越來越多的熱能之后，其內部粒子能量隨之攀升，粒子運動加速，當熱能蓄積到極限后，這些粒子運動擺脫了原本彼此間達成的平衡限制，固體便會改變形態(tài)，有固體進入液體形態(tài)[2]。其次，等溫過程。物質不再吸熱而是不斷放熱，當溫度和環(huán)境溫度持平時，物質和環(huán)境不發(fā)生熱交換，物質溫度穩(wěn)定在一定范圍之內。內部粒子自由會有所降低。當降低到足夠穩(wěn)定的狀態(tài)不再發(fā)生改變時，便處在了平衡狀態(tài)。第三是冷卻過程。當固體溫度持續(xù)降低最后到一定程度后，地球內部粒子數(shù)量會不斷降低，也可能會逐漸影響其全部運動時的效果，而一直到所有其他粒子全部運動趨于穩(wěn)定時，而此時外部環(huán)境能量也處在最低狀態(tài)，不能持續(xù)給予地球內部粒子以熱能，這會導致所有粒子達到了平衡狀態(tài)。Metropolis 接受準則的利用，目的是讓模擬退火算法終止時所得解成為最優(yōu)解，這樣將模擬退火算法局部最優(yōu)的可能性得到規(guī)避[3]。

1.3 算法操作過程

關于模擬退火處理算法的基本操作步驟主要包括以下幾個方面：第一點是數(shù)據(jù)初始化。第一點是初始化。設置初始解的溫度值解為的是t0，初始溫度解為的是溫度s，每個初始溫度t 的迭代替換次數(shù)為溫度l，初始解為溫度的一點設定對于一個算法從隨機模式搜索中的過程中開始轉換到成為算法局部模式搜索中的過程隨機會可以起到明顯的提控制度的作用，其中迭加取代替換次數(shù)l 的一點設定更是對隨機會保證算法局部搜索過程解析度質量的不斷提升速度有著一個顯著效果，第二點設定是對算法進行搜索步驟。第三點一直到第五點的迭加替代次數(shù)操作。初始溫度的設定對于算法從隨機搜索過程中轉換為局部搜索過程會起到明顯控制作用,其中迭代次數(shù)L 的設定更是對會算法搜索解質量的提升有著顯著效果,第二點是對進行步驟第三點到第五點的迭代操作。第三點主要是通過利用算法中的運算可以產(chǎn)生一個新解,第四點主要是通過計算給定目標兩個函數(shù)的差值,當給定目標兩個函數(shù)值的差值最大小于0，則計算接受這個新解,否則要以具體的一個概率函數(shù)來計算接受這個新解。第五點是接受算法終止的條件并且滿足終止條件時需要輸出當時的解，從而結束算法[4]。第六點是對當前溫度進行衰減系數(shù)的衰減計算，并且重復第二點的步驟。具體流程圖如圖1 所示。

圖1：模擬退火算法流程圖

圖2：云計算中虛擬機調度框架

2 虛擬機調度問題分析

2.1 問題介紹

隨著兩次工業(yè)革命的發(fā)展，其進步更是影響甚至決定著國家的持續(xù)性經(jīng)濟發(fā)展實力和國際話語權，而制造業(yè)當中生產(chǎn)調度系統(tǒng)使用頻率最高，故而后者質量直接決定了制造業(yè)的發(fā)展水平，特別是目前在國際國內制造業(yè)逐漸與互聯(lián)網(wǎng)計算機云計算等一些先進的技術相結合下，更是發(fā)生著質的轉變。生產(chǎn)調度技術因為屬于核心技術范疇，故而其受到影響尤為劇烈。云計算驅動下制造業(yè)水平有所突破，但信息化技術深入發(fā)展無形中也加劇了生產(chǎn)調度問題的復雜度，特別是虛擬機調度作為云計算，云數(shù)據(jù)環(huán)境下成熟發(fā)展的產(chǎn)物，更是加劇了其調度的難題和復雜力，目前這種虛擬機調度方法往往超出了個人決策能力范圍，若是單純依靠個人經(jīng)驗和能力進行調度，往往無法達到預期效果。除此之外，因為經(jīng)濟發(fā)展速度加快，世界一體化進程加深，人們需要更加復雜的功能產(chǎn)品，這種產(chǎn)品也會越來越左右著人們的生活習慣和生活方式，這要求制造業(yè)必須提升該類產(chǎn)品生產(chǎn)能力，意味著其承受著巨大的生產(chǎn)壓力，需要其在產(chǎn)量、質量上多做功課解決二者間矛盾，還需要提高生產(chǎn)設備利用水平，這說明之前的調度方式已經(jīng)不能滿足制造企業(yè)的發(fā)展現(xiàn)狀，其中便需要虛擬機調度加以優(yōu)化，更好的應用云計算模式下來提高調度效率，增強企業(yè)的生存發(fā)展能力[4]。

2.2 問題類型及特點

目前基于虛擬機調度的問題類型有以下幾點，第一點是單機調度，是指在同一臺設備上完成所有生產(chǎn)加工任務。需要進行排隊優(yōu)化，第二點是多級并行調度，指的是多個功能相同設備上同時進行多種產(chǎn)品的加工，不過該種調度具有較深的復雜性，需要進行深度優(yōu)化方可發(fā)揮優(yōu)良作用。第三點是多累積調度，是指產(chǎn)品需要在不同功能的設備上有次序地進行加工生產(chǎn)，多類機經(jīng)常會出現(xiàn)流水作業(yè)調度和柔性流水作業(yè)調度這個問題。目前車間的虛擬機調度中出現(xiàn)的問題，也包括了以下幾個特點，首先是普遍性，指的是制造業(yè)采用虛擬調度機已經(jīng)是普遍現(xiàn)象。其次是復雜性，這是因為調度的環(huán)境載體存在諸多影響因素，在不同的背景下，調度優(yōu)化目標也各不相同，而伴隨著調度規(guī)模加大，導致調度問題求解有關計算也變得復雜起來。再次，動態(tài)隨機性，這是由車間生產(chǎn)環(huán)境決定的，其中存在著很多動態(tài)變化因素，而這些因素都會無形中加劇虛擬機調度動態(tài)靈活的。效果第四點是多樣性，在生產(chǎn)調度中所受到的約束條件過多，在不同的需求下，問題目標也各不相同，而基于生產(chǎn)條件完成的時間調度目標，基于生產(chǎn)成本優(yōu)化等交通目標，也無形中造成了生產(chǎn)車間較多問題的多樣性[5]。

3 基于改進模擬退火算法的虛擬機調度優(yōu)化實驗

3.1 系統(tǒng)架構

本文基于改進模擬退火算法的虛擬機，調動優(yōu)化提出了如圖2所示框架，首先，云監(jiān)控平臺系統(tǒng)可以對每個用戶所有任務資源進行系統(tǒng)調度優(yōu)化分配，形成兩個一組同時帶有一個明確任務調度信息的監(jiān)控虛擬機任務列表，隨后根據(jù)任務優(yōu)化調度目標，按照具體的任務調度分配方法，將虛擬機直接部署到具體的監(jiān)控物理機上可以執(zhí)行虛擬機連續(xù)運行。在過程中，監(jiān)控管理單元可能會根據(jù)實際的任務狀況自動作出明確的任務重置或者遷移等一系列管理操作，確保每個用戶的所有任務資源能夠正常連續(xù)運行，通過上述數(shù)據(jù)分析可以得知，目前國內有許多大型虛擬機業(yè)務調度優(yōu)化算法更加多的側重于對于執(zhí)行時間和總成本資源消耗以及能耗等多個方面的綜合優(yōu)化上，但是對于數(shù)據(jù)資源綜合利用率以及執(zhí)行時間成本以及吞吐量和一些其他特定因素影響方面的優(yōu)化研究相對較少，也就是缺乏對企業(yè)云服務供應商另一方面的優(yōu)化考慮。因此，本文更是以系統(tǒng)資源綜合利用率系統(tǒng)執(zhí)行過程成本和系統(tǒng)負載均衡這三者關系作為主要的成本優(yōu)化規(guī)劃目標及戰(zhàn)略目的，是為了進一步提高系統(tǒng)資源綜合利用率并有效減少系統(tǒng)執(zhí)行過程成本，真正有效實現(xiàn)系統(tǒng)物理機與系統(tǒng)物理機之間的成本負載均衡。

3.2 改進的模擬退火調度算法

為有效率的解決以往人工退火調度以及傳統(tǒng)人工調度目標算法全局優(yōu)化，目標單一等級的缺點，基于云和云計算的調度環(huán)境下，調度目標資源更多時就會需要采用各種類似啟發(fā)式的調度算法，同時我們能夠快速達到多種調度目標的全局優(yōu)化，而模擬退火調度算法就是作為一種根據(jù)目標給定調度函數(shù)，利用一定概率的計算方式被用來快速獲取目標全局最優(yōu)化求解的一種啟發(fā)式調度算法，能夠在初期時廣泛的進行搜索?？臻g最優(yōu)通過大量數(shù)據(jù)搜索空間范圍并同時接受一個交叉函數(shù)姐輸出來可以避免整個算法局部陷入空間局部最優(yōu)，而它的缺點則是側重于對空間整體數(shù)據(jù)解析和空間值的認知能力不足，尋求計算效率和空間鎖定要求解空間性能有限。本文提出了HEFT 算法的思想。根據(jù)物理機計算性能，可以求出對應解的過程。使得最終所獲得的結局有更好的計算性能。

3.3 實驗對比

為了更好地評價本文所提出的這種優(yōu)化算法，將進行云環(huán)境的調度模擬。云計算環(huán)境技術中的節(jié)點負載均衡概念是在泛指各個業(yè)務節(jié)點相互利用均衡期間不會出現(xiàn)存在的非負載或節(jié)點過載的各種情況不會發(fā)生。通過該管理算法進行設置并為相關網(wǎng)絡限定負載參數(shù)，能夠有效率地防止上述負載問題，有著更加合理的網(wǎng)絡負載均衡管理性能。