基于改進(jìn)模擬退火算法的虛擬機(jī)調(diào)度優(yōu)化方法

宋楊

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

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

1 模擬退火算法相關(guān)概述

1.1 算法來(lái)源

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

1.2 Metropolis接受準(zhǔn)則

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

1.3 算法操作過(guò)程

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

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

圖2：云計(jì)算中虛擬機(jī)調(diào)度框架

2 虛擬機(jī)調(diào)度問(wèn)題分析

2.1 問(wèn)題介紹

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

2.2 問(wèn)題類型及特點(diǎn)

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

3 基于改進(jìn)模擬退火算法的虛擬機(jī)調(diào)度優(yōu)化實(shí)驗(yàn)

3.1 系統(tǒng)架構(gòu)

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

3.2 改進(jìn)的模擬退火調(diào)度算法

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

3.3 實(shí)驗(yàn)對(duì)比

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