基于遺傳珊瑚礁優(yōu)化算法的負(fù)載均衡問(wèn)題

袁赫潞,溫長(zhǎng)吉,2,吳建雙,朱允剛,于合龍,2

(1.吉林農(nóng)業(yè)大學(xué) 信息技術(shù)學(xué)院,長(zhǎng)春 130118;2.吉林省精準(zhǔn)農(nóng)業(yè)與大數(shù)據(jù)工程研究中心,長(zhǎng)春 130118;3.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,長(zhǎng)春 130012)

信息時(shí)代,云計(jì)算技術(shù)能實(shí)現(xiàn)其強(qiáng)大的資源配置功能,其核心技術(shù)是通過(guò)負(fù)載均衡策略層收集量化信息,并根據(jù)負(fù)載均衡策略完成分配任務(wù).在目前的拓?fù)渚W(wǎng)絡(luò)下,負(fù)載均衡提供了一種廉價(jià)且透明有效的方法,擴(kuò)展網(wǎng)絡(luò)設(shè)備和服務(wù)器的帶寬、增加吞吐量、加強(qiáng)網(wǎng)絡(luò)數(shù)據(jù)處理能力、提高網(wǎng)絡(luò)的靈活性和可用性.

早期集中式負(fù)載均衡方法具有部署簡(jiǎn)單、高效且平臺(tái)易維護(hù)的特點(diǎn)[1].但當(dāng)面對(duì)高峰用戶(hù)訪問(wèn)量和任務(wù)數(shù)量過(guò)多時(shí),中心管理服務(wù)器將會(huì)面臨單點(diǎn)失效的瓶頸[2].針對(duì)上述問(wèn)題,分布式負(fù)載均衡具有不設(shè)中心控制服務(wù)器,即每個(gè)服務(wù)器都參與任務(wù)調(diào)度和分配,因此具有較好的拓展性.分布式負(fù)載均衡如何優(yōu)化平臺(tái)資源配置,提升資源能耗利用率是研究的關(guān)鍵問(wèn)題之一,代表性工作包括傳統(tǒng)優(yōu)化調(diào)度模型和基于群智能算法.Bittencourt等[3]提出了一種基于博弈論的分布式負(fù)載均衡算法,網(wǎng)絡(luò)服務(wù)器之間通過(guò)博弈相互轉(zhuǎn)嫁負(fù)載使自己的負(fù)載最小化,從而使系統(tǒng)達(dá)到均衡實(shí)現(xiàn)最優(yōu)的負(fù)載均衡；文獻(xiàn)[4]提出了一種優(yōu)化配置模型,該模型通過(guò)計(jì)算不同工作負(fù)載下關(guān)于服務(wù)器的功耗運(yùn)行動(dòng)態(tài)優(yōu)化管理,進(jìn)而有效減少基礎(chǔ)資源的能源消耗并增加能源的應(yīng)用效率；文獻(xiàn)[5]提出了通過(guò)WiFi接入點(diǎn)把卸載任務(wù)給云的一種節(jié)能調(diào)度模型,在總完工時(shí)間的約束下得到了最少設(shè)備的消耗；文獻(xiàn)[6]提出了一種引入局部搜索算子提高搜索能力和加速收斂速度的改進(jìn)遺傳算法模型,實(shí)現(xiàn)了節(jié)能任務(wù)調(diào)度;文獻(xiàn)[7]提出了利用人工蜂群算法解決負(fù)載均衡問(wèn)題,并設(shè)計(jì)了新的問(wèn)題模型；Kechagiopoulos等[8]提出了基于粒子群優(yōu)化算法；Nayeem等[9]提出了基于精英策略的遺傳算法負(fù)載均衡設(shè)計(jì)方案.

珊瑚礁優(yōu)化(coral reef optimization,CRO)算法[10]是一種模擬珊瑚蟲(chóng)群體行為和珊瑚礁組成的智能優(yōu)化算法,通過(guò)珊瑚蟲(chóng)種群的繁殖、競(jìng)爭(zhēng)、淘汰等環(huán)節(jié)實(shí)現(xiàn)優(yōu)化.珊瑚礁優(yōu)化算法中的有性和無(wú)性繁殖,以及毀滅機(jī)制實(shí)現(xiàn)信息的種群間共享機(jī)制,增強(qiáng)全局搜索能力.文獻(xiàn)[11]運(yùn)用珊瑚礁優(yōu)化算法得到了較客觀的效果.針對(duì)無(wú)線接入網(wǎng)的分布問(wèn)題,文獻(xiàn)[12]證明了珊瑚礁優(yōu)化算法在實(shí)際應(yīng)用中具有較強(qiáng)解決問(wèn)題的能力.但目前基本珊瑚礁優(yōu)化算法仍存在缺陷,如在繁殖過(guò)程中種群多樣性受限,搜索精度偏低,易陷入局部最優(yōu)解等.針對(duì)上述問(wèn)題,本文提出一種改進(jìn)的珊瑚礁優(yōu)化算法----遺傳珊瑚礁優(yōu)化算法(cenetic algorithm and coral reef optimization,GACRO),即在珊瑚蟲(chóng)的每次進(jìn)化過(guò)程中,將遺傳算法中的交叉和變異算子引入到珊瑚礁優(yōu)化算法的種群進(jìn)化迭代中,在保留基本珊瑚礁優(yōu)化算法中每個(gè)珊瑚蟲(chóng)信息共享機(jī)制的同時(shí),有效提升全局搜索能力,增加種群多樣性,提升算法的優(yōu)化性能,避免算法過(guò)早陷入局部最優(yōu)的問(wèn)題,并將改進(jìn)的遺傳珊瑚礁優(yōu)化算法應(yīng)用于負(fù)載均衡中.

1 相關(guān)理論及問(wèn)題描述

1.1 算法簡(jiǎn)介

遺傳算法(GA)是模擬生物進(jìn)化論中自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程計(jì)算模型,其通過(guò)對(duì)問(wèn)題所屬解空間中的解向量進(jìn)行編碼,利用生成的染色體建立初始種群,通過(guò)選擇、交叉和變異等操作從適應(yīng)度函數(shù)中選出優(yōu)秀個(gè)體,進(jìn)而實(shí)現(xiàn)問(wèn)題尋優(yōu).

珊瑚礁優(yōu)化算法(CRO)是一種模擬珊瑚蟲(chóng)群體行為和珊瑚礁組成的智能優(yōu)化算法.珊瑚蟲(chóng)種群的進(jìn)化行為分為繁殖、競(jìng)爭(zhēng)、淘汰等階段.繁殖行為又可分為外部有性繁殖、內(nèi)部有性繁殖和無(wú)性繁殖.首先將珊瑚礁記為Am×n,外部有性繁殖概率記為Pb,內(nèi)部有性繁殖概率記為1-Pb,死亡概率記為Pd,無(wú)性繁殖概率記為Pa,且Pa=Pd[13]；然后進(jìn)行外部有性繁殖和內(nèi)部有性繁殖,若在迭代次數(shù)(步長(zhǎng)K)內(nèi)未被選擇則會(huì)被釋放到水中,根據(jù)適應(yīng)度函數(shù)對(duì)計(jì)算珊瑚蟲(chóng)的健康值進(jìn)行排序并進(jìn)行幼蟲(chóng)安置；進(jìn)行無(wú)性繁殖時(shí),在礁上所有的珊瑚蟲(chóng)都會(huì)通過(guò)健康值進(jìn)行水平排序,根據(jù)概率Pa進(jìn)行復(fù)制并再次排序,若礁上存在一些不健康的珊瑚蟲(chóng)則為死亡概率.一系列操作完成則表示一次迭代完成,若符合算法的終止條件則輸出,若不符合算法的終止條件則需進(jìn)行第二次迭代,直至滿(mǎn)足算法的終止條件為止,輸出最優(yōu)解.珊瑚礁優(yōu)化算法流程如圖1所示.

圖1 珊瑚礁優(yōu)化算法流程Fig.1 Flow chart of CRO algorithm

1.2 遺傳珊瑚礁優(yōu)化算法

1.2.1 算法設(shè)計(jì) 遺傳珊瑚礁優(yōu)化算法基本思想為: 在每次種群進(jìn)化過(guò)程中,由基本珊瑚礁優(yōu)化算法進(jìn)化獲得的珊瑚蟲(chóng)種群并不直接進(jìn)入下一次迭代操作,而是在進(jìn)入下一次迭代前對(duì)種群中的每個(gè)珊瑚蟲(chóng)進(jìn)行選擇、變異和交叉等一系列操作后得到新的種群.設(shè)第t代種群記為S1,依次進(jìn)行珊瑚礁有性繁殖,判斷K步內(nèi)是否選擇到雙親,如果無(wú)雙親則進(jìn)行內(nèi)部有性繁殖,在K步長(zhǎng)內(nèi)選擇母珊瑚蟲(chóng),否則將其釋放到水中.之后對(duì)幼蟲(chóng)進(jìn)行安置,通過(guò)適應(yīng)度函數(shù)計(jì)算健康值,再進(jìn)行無(wú)性繁殖,對(duì)健康值高低進(jìn)行排序,此時(shí)進(jìn)行遺傳算法中的選擇、交叉、變異操作,形成種群S2,再對(duì)新種群S2進(jìn)行幼蟲(chóng)安置,判斷是否為最優(yōu)值進(jìn)行輸入,否則將進(jìn)入毀滅機(jī)制.遺傳珊瑚礁優(yōu)化算法執(zhí)行步驟如下：

1) 初始化GACRO算法的各參數(shù)，初始化種群S1；

2) 種群S1進(jìn)行外部有性繁殖,根據(jù)概率Pb選擇雙親；

3) 若K步長(zhǎng)內(nèi)選擇雙親,則執(zhí)行步驟6),K步長(zhǎng)內(nèi)未選擇雙親,則執(zhí)行步驟4)；

4) 內(nèi)部有性繁殖,根據(jù)概率(1-Pb)選擇母珊瑚蟲(chóng)；

5) 若K步長(zhǎng)內(nèi)選擇母珊瑚蟲(chóng)，則執(zhí)行步驟6),K步長(zhǎng)內(nèi)未選擇母珊瑚蟲(chóng)則將其釋放到水中；

6) 進(jìn)行幼蟲(chóng)安置,根據(jù)適應(yīng)度函數(shù)計(jì)算健康值并進(jìn)行排序；

7) 無(wú)性繁殖,根據(jù)概率Pd進(jìn)行復(fù)制,并重復(fù)步驟8)進(jìn)行幼蟲(chóng)安置,形成種群S2；

8) 利用遺傳算法對(duì)新珊瑚蟲(chóng)種群進(jìn)行選擇操作,選擇操作后的珊瑚蟲(chóng)種群S2中的珊瑚蟲(chóng)xi,被選中概率為P(xi),在S2中選出一個(gè)珊瑚蟲(chóng)進(jìn)行復(fù)制操作,共進(jìn)行M次,復(fù)制產(chǎn)生的M個(gè)珊瑚蟲(chóng)成為種群S3；

9) 利用遺傳算法對(duì)種群S3進(jìn)行交叉操作,交叉概率為Pc,在種群S3中隨機(jī)選出c個(gè)珊瑚蟲(chóng)進(jìn)行交叉操作,通過(guò)交叉操作隨機(jī)交換兩個(gè)珊瑚蟲(chóng)某些基因,產(chǎn)生新基因組合,用S4替代S3；

10) 利用遺傳算法對(duì)S4進(jìn)行變異操作,確定變異數(shù)m,在種群S4中隨機(jī)選取m個(gè)珊瑚蟲(chóng)變異,新的種群S5代替S4,成為新一代種群；

11) 重復(fù)步驟6),根據(jù)健康值進(jìn)行排序；

12) 判斷是否為最優(yōu)值,若不是則將進(jìn)入毀滅機(jī)制；

13) 輸出最優(yōu)值.

1.2.2 適應(yīng)度函數(shù)設(shè)計(jì) 云環(huán)境中擁有計(jì)算資源、存儲(chǔ)資源和帶寬等資源,用戶(hù)可根據(jù)自己的需求,對(duì)不同資源進(jìn)行申請(qǐng)和計(jì)費(fèi).由于系統(tǒng)對(duì)各種資源的管理和使用方式不同,因此本文將所有的服務(wù)器都視為計(jì)算服務(wù)器進(jìn)行處理.在負(fù)載均衡策略針對(duì)大量并發(fā)請(qǐng)求任務(wù)進(jìn)行分配時(shí),負(fù)載調(diào)度機(jī)制通過(guò)最小化響應(yīng)時(shí)間及服務(wù)器最大化利用率實(shí)現(xiàn)負(fù)載均衡,優(yōu)化資源配置及效率.

適應(yīng)度函數(shù)設(shè)計(jì)原則如下：設(shè)定任務(wù)數(shù)量、服務(wù)器數(shù)量和計(jì)算能力(每臺(tái)服務(wù)器計(jì)算能力相同)為已知,使用矩陣表示每個(gè)任務(wù)在每個(gè)服務(wù)器上的預(yù)計(jì)花費(fèi)時(shí)間(expect time to complete,ETC).ETCij表示第i個(gè)任務(wù)在第j個(gè)服務(wù)器上花費(fèi)的時(shí)間,設(shè)任務(wù)的數(shù)量為m,服務(wù)器的數(shù)量為n,則

(1)

因?yàn)樗腥蝿?wù)大小和服務(wù)器的計(jì)算能力己知,因此可計(jì)算出所有任務(wù)執(zhí)行的總時(shí)間.設(shè)服務(wù)器j上所有任務(wù)組成的集合為Cj,則服務(wù)器j執(zhí)行完所有任務(wù)所需的時(shí)間為

(2)

花費(fèi)的總時(shí)間為

totalTime=maxCij,

(3)

基于時(shí)間的適應(yīng)度函數(shù)為

(4)

1.2.3 問(wèn)題描述 為解決云計(jì)算環(huán)境中服務(wù)器負(fù)載均衡的問(wèn)題,需要合適的方式將服務(wù)器與任務(wù)的關(guān)系映射到一起,通過(guò)編碼的方式確定種群中個(gè)體的算法表現(xiàn)形式,每個(gè)經(jīng)過(guò)編碼后得到的數(shù)組表示一個(gè)任務(wù)在服務(wù)器上的分配方案.對(duì)每個(gè)任務(wù)和服務(wù)器進(jìn)行唯一性標(biāo)記,經(jīng)過(guò)編碼得到的數(shù)組長(zhǎng)度由任務(wù)總數(shù)確定,數(shù)組中每個(gè)元素對(duì)應(yīng)的值則為任務(wù)對(duì)應(yīng)的服務(wù)器編號(hào).利用云計(jì)算的特征,本文對(duì)每個(gè)云計(jì)算中的子任務(wù)所需占用的服務(wù)器進(jìn)行編碼,子任務(wù)的數(shù)量決定了編碼的長(zhǎng)度,將編碼與云任務(wù)分配相對(duì)應(yīng),采用服務(wù)器—任務(wù)的間接編碼方式.設(shè)有3個(gè)任務(wù),4臺(tái)云計(jì)算服務(wù)器,其中任務(wù)1和2分別由3個(gè)子任務(wù),任務(wù)3有4個(gè)子任務(wù),共計(jì)10個(gè)子任務(wù),此時(shí)珊瑚礁優(yōu)化算法編碼列于表1.由表1可見(jiàn),CRO算法編碼序列為{4,1,2,3,2,1,4,2,1,3},對(duì)該序列進(jìn)行解碼，結(jié)果列于表2.

表1 珊瑚礁優(yōu)化算法編碼

表2 珊瑚礁優(yōu)化算法解碼

由表2可見(jiàn),子任務(wù){(diào)2,6,9}分配給1號(hào)服務(wù)器,{3,5,8}分配給2號(hào)服務(wù)器,{4,10}分配給3號(hào)服務(wù)器,{1,7}分配給4號(hào)服務(wù)器.一個(gè)珊瑚蟲(chóng)對(duì)應(yīng)一個(gè)任務(wù)集分配策略,則CRO算法編碼序列為{4,1,2,3,2,1,4,2,1,3},與一個(gè)任務(wù)對(duì)應(yīng)服務(wù)器的分配方案相對(duì)應(yīng).服務(wù)器j上執(zhí)行完所分配的任務(wù)集所用時(shí)間F(j)及執(zhí)行完所有任務(wù)的總時(shí)間Completetime分別為

(5)

其中：L(j)表示初始負(fù)載；task表示任務(wù)總數(shù)分配到j(luò)上；R(i,j)表示任務(wù)i在服務(wù)器j上的執(zhí)行時(shí)間；N表示服務(wù)器總數(shù).

1.3 評(píng)價(jià)指標(biāo)

假設(shè)一批小任務(wù)由若干大任務(wù)分解組成,且子任務(wù)劃分?jǐn)?shù)量相同,再假設(shè)任務(wù)數(shù)量超過(guò)服務(wù)器數(shù)量多倍.用M表示任務(wù)總數(shù),Ti表示第i個(gè)子任務(wù),N表示服務(wù)器數(shù)量,VMj表示第j個(gè)服務(wù)器,則第j個(gè)服務(wù)器完成系統(tǒng)交付的所有子任務(wù)時(shí)間為

(6)

其中：Time(Ti,VMj)表示子任務(wù)Ti在服務(wù)器VMj上的執(zhí)行時(shí)間；m表示分配到VMj上的子任務(wù)數(shù)量.所有服務(wù)器執(zhí)行任務(wù)所用的最長(zhǎng)時(shí)間定義為總?cè)蝿?wù)執(zhí)行時(shí)間評(píng)價(jià)函數(shù),即completeTime=max{vmTime(VMj)},j∈[1,N].負(fù)載均衡度DLB評(píng)價(jià)函數(shù)為

(7)

DBL值越接近1負(fù)載均衡度越高,即每個(gè)服務(wù)器完成任務(wù)所用的時(shí)間與總?cè)蝿?wù)完成時(shí)間越接近表示負(fù)載越均衡.

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)參數(shù)初始化

珊瑚礁優(yōu)化算法種群多樣性受限,因此需引入遺傳算法的交叉和變異操作增加種群多樣性,避免陷入局部最優(yōu).交叉概率函數(shù)為

(8)

其中:fmax表示種群最大適應(yīng)度值;favg表示群體平均適應(yīng)度值；f′表示較大的適應(yīng)度值在兩個(gè)交叉?zhèn)€體中.如果f′>favg,則交叉概率Pc變小,避免適應(yīng)度值大的個(gè)體統(tǒng)治群體,出現(xiàn)陷入局部最優(yōu)解的問(wèn)題,設(shè)k1=0.36;如果f′

2.2 CloudSim云計(jì)算仿真工具

CloudSim云計(jì)算仿真工具是一種云計(jì)算仿真軟件[15],以GridSim模型為基礎(chǔ)進(jìn)一步發(fā)展得到了CloudSim,支持云計(jì)算的資源管理和調(diào)度模擬,本文在CloudSim3.0中對(duì)數(shù)據(jù)中心(Datacenter)、虛擬(VM)以及云任務(wù)(Cloudlet)的環(huán)境參數(shù)進(jìn)行配置,見(jiàn)表3.

表3 CloudSim3.0環(huán)境參數(shù)配置

注：MI表示百萬(wàn)條指令.

2.3 實(shí)驗(yàn)結(jié)果與分析

下面將本文提出的珊瑚礁遺傳算法(CROGA)與遺傳算法(GA)[13]、珊瑚礁優(yōu)化算法(CRO)[16]、蟻群算法(ACO)[17]、蜂群算法(ABC)[18]、遺傳退火融合算法(GASA)[19-20]、狼群算法(WA)[21]、蛙跳算法(SFLA)的負(fù)載均衡在Cloudsim仿真模擬實(shí)驗(yàn)平臺(tái)中實(shí)現(xiàn).基于服務(wù)器負(fù)載率最大值和機(jī)電負(fù)載標(biāo)準(zhǔn)差兩方面進(jìn)行對(duì)比.采用服務(wù)器負(fù)載率最大值和服務(wù)器負(fù)載率標(biāo)準(zhǔn)差對(duì)負(fù)載均衡度進(jìn)行評(píng)價(jià),其中迭代次數(shù)可證明改進(jìn)算法的有效性.重復(fù)執(zhí)行每項(xiàng)實(shí)驗(yàn)10次,最后取實(shí)驗(yàn)結(jié)果的平均值.

假設(shè)測(cè)試參數(shù)為：測(cè)試任務(wù)數(shù)量1 000個(gè)；群體M=20；迭代次數(shù)T=35；交叉因子C=0.5；變異因子D=0.7；珊瑚礁大小為Am×n;外部有性繁殖概率Pb=0.8；內(nèi)部有性繁殖概率1-Pb=0.2;無(wú)性繁殖概率Pa=0.3;死亡概率Pd=Pa=0.3.測(cè)試函數(shù)定義為適應(yīng)度函數(shù).

2.3.1 算法的有效性分析 下面針對(duì)上述8種算法在任務(wù)數(shù)量由25逐漸增加到250的過(guò)程中,對(duì)最優(yōu)解所需的迭代次數(shù)進(jìn)行比較，不同算法迭代次數(shù)的對(duì)比結(jié)果列于表4.由表4可見(jiàn)：當(dāng)任務(wù)數(shù)量增加時(shí),迭代次數(shù)持續(xù)遞增；在任務(wù)數(shù)量相同的情況下,遺傳算法和蜂群算法的迭代次數(shù)與其他算法相比最多；當(dāng)任務(wù)數(shù)量等于或小于75時(shí),本文提出的遺傳珊瑚礁優(yōu)化算法與其他幾種算法在迭代次數(shù)方面相差不多；當(dāng)任務(wù)數(shù)量逐漸增多且大于75時(shí),遺傳珊瑚礁優(yōu)化算法體現(xiàn)出優(yōu)勢(shì),所需的迭代次數(shù)相比于其他算法更少.表明在運(yùn)行效率上,遺傳珊瑚礁優(yōu)化算法優(yōu)于其他算法,證明了改進(jìn)遺傳珊瑚礁優(yōu)化算法的有效性.

表4 不同算法迭代次數(shù)對(duì)比

2.3.2 評(píng)價(jià)算法的負(fù)載均衡度 服務(wù)器執(zhí)行任務(wù)分配不均衡是導(dǎo)致系統(tǒng)功耗成本過(guò)高的一個(gè)主要原因.表5列出了不同算法服務(wù)器負(fù)載率最大值對(duì)比結(jié)果.由表5可見(jiàn),當(dāng)任務(wù)數(shù)量逐漸增多時(shí),8種算法的服務(wù)器負(fù)載率最大值均增大,但本文提出的遺傳珊瑚礁優(yōu)化算法服務(wù)器的負(fù)載率最大值始終比其他算法小,并且任務(wù)數(shù)量50～300時(shí)負(fù)載率均低于60%,表明本文提出的遺傳珊瑚礁優(yōu)化算法任務(wù)分配更合理.

表5 不同算法服務(wù)器負(fù)載率(%)最大值對(duì)比

綜上所述,本文將遺傳算法的選擇、交叉和變異操作引入到基本珊瑚礁優(yōu)化算法中,提出了一種基于遺傳算法環(huán)境下的遺傳珊瑚礁優(yōu)化算法,能將遺傳算法中的遺傳選擇操作更大地優(yōu)化,有效增加了種群的多樣性,增強(qiáng)了算法的全局搜索能力,提高了網(wǎng)絡(luò)資源利用率,明顯改善了網(wǎng)絡(luò)負(fù)載不均衡的情況.