改進(jìn)蟻群算法在云環(huán)境下路徑優(yōu)化設(shè)計

崇陽

摘 要 云環(huán)境作為一種新的網(wǎng)絡(luò)服務(wù)環(huán)境，提供大量的網(wǎng)絡(luò)資源服務(wù)，云環(huán)境中的資源分配問題受帶寬、負(fù)載以及響應(yīng)時間的影響。蟻群算法是一種自適應(yīng)搜索算法，對組合優(yōu)化問題的解決發(fā)揮了重大的作用，但是其缺陷是容易陷入局部最優(yōu)以及搜索速度慢。本文提出的蟻群優(yōu)化算法，將蟻群算法和遺傳算法結(jié)合起來，能夠加快蟻群算法的收斂速度，提高搜索速度，降低云環(huán)境下的網(wǎng)絡(luò)負(fù)載，使得云環(huán)境下的任務(wù)運行時間有效縮短，網(wǎng)絡(luò)利用率明顯提高。

關(guān)鍵詞 云環(huán)境；蟻群算法；路徑優(yōu)化

中圖分類號：TP3 文獻(xiàn)標(biāo)識碼：A 文章編號：1671-7597（2014）09-0046-02

云環(huán)境是一種新的網(wǎng)絡(luò)服務(wù)環(huán)境，具有強大的網(wǎng)絡(luò)資源，強調(diào)網(wǎng)絡(luò)資源的共享，為用戶的信息訪問和資源共享提供了方便的信息平臺。隨著人們對云計算的廣泛認(rèn)可和推廣，云計算的規(guī)模也在不斷的擴大，如何提高云計算的服務(wù)性能，增加網(wǎng)絡(luò)利用率逐漸成為云計算時代社會關(guān)注的重點問題。

蟻群算法通過對螞蟻種群覓食過程的模擬，利用螞蟻群落在覓食的多條路徑上所留下的信息元素的累積來找出最佳的路徑。蟻群算法在解決組合優(yōu)化的優(yōu)化方面具有其獨特的優(yōu)勢。但是，在對規(guī)模較大的系統(tǒng)進(jìn)行處理時，采用蟻群算法往往會陷入局部最優(yōu)解的缺陷，而且搜索的時間也較長，這就導(dǎo)致在其選擇的局部最優(yōu)路徑上的負(fù)載過大，網(wǎng)絡(luò)發(fā)生擁堵或者癱瘓。云計算的路徑優(yōu)化實際上就是資源分配的組合方式的最優(yōu)化選擇，通過改進(jìn)的蟻群算法在云環(huán)境下的路徑優(yōu)化，實現(xiàn)云環(huán)境下的網(wǎng)絡(luò)資源優(yōu)化分配，這對降低網(wǎng)絡(luò)負(fù)載，提高網(wǎng)絡(luò)訪問率和利用率具有重要意義。

1 蟻群算法

螞蟻群落在尋覓食物的時候在其經(jīng)過的路徑上會留下信息素，螞蟻們能夠?qū)@種信息素進(jìn)行感知，并根據(jù)信息素的強度來決定自身的前進(jìn)方向。螞蟻種群的集體覓食行動就形成了一種信息反饋：越短的路徑，經(jīng)過的螞蟻數(shù)量就越多，則遺留下來的信息素強度越高，后來的螞蟻就越容易選擇這條路徑。在螞蟻群落中就是通過這種方式來進(jìn)行個體間的信息交流，并以最短路徑來找到食物。蟻群算法就是在蟻群覓食的行為基礎(chǔ)上衍生出來的一種模擬進(jìn)化算法。

螞蟻群落中有m只螞蟻，螞蟻種群的集合用來表示，第k只螞蟻覓食的路徑用來表示，當(dāng)蟻群中的所有螞蟻走完全部路徑后，在解集中求出最優(yōu)解，也就是最優(yōu)路徑，即，第k只螞蟻的覓食路徑為最優(yōu)解，記做min。螞蟻群落中的所有螞蟻經(jīng)歷所有節(jié)點后有重新回歸到原點，最短路徑的第k只螞蟻為繁殖螞蟻進(jìn)行迭代更新后，弧上所遺留的信息素全部揮發(fā)的下限值為。

2 云環(huán)境服務(wù)的資源分配

在云環(huán)境中，資源分布規(guī)模巨大，十分復(fù)雜，在任何時段的某一路線所承載的網(wǎng)絡(luò)負(fù)荷的變化是不確定的，大幅度的負(fù)載變化使得資源需求壓力增加，現(xiàn)有的資源無法對用戶需求很好的滿足。但是如果對資源需求的預(yù)期分配過高，又有可能造成資源的浪費，是網(wǎng)絡(luò)資源的利用率大打折扣。物理節(jié)點和鏈路負(fù)載的不平衡狀態(tài)不僅是成本增加，而且資源利用率低，造成浪費，同時還造成了服務(wù)滿意度的降低。要改變這種不平衡的狀態(tài)，提高云環(huán)境的資源利用率，就需要對資源進(jìn)行合理的預(yù)估和分配。云環(huán)境下的網(wǎng)絡(luò)平臺每個單元都有一個主要的任務(wù)節(jié)點和一個任務(wù)分配節(jié)點組成。對于任何一個鏈路，都可定義為三種屬性，即費用函數(shù)、時延函數(shù)和帶寬函數(shù)。在云環(huán)境下對網(wǎng)絡(luò)路徑進(jìn)行優(yōu)化，實際上就是在網(wǎng)絡(luò)平臺上，從源點S到終點M，尋找一條最優(yōu)的路徑。在滿足帶寬約束、時延約束、費用約束三個條件的基礎(chǔ)上，τ（Tsm）的取值越小說明資源分配越合理，資源利用率越高。

3 改進(jìn)的蟻群優(yōu)化算法云環(huán)境下路徑優(yōu)化

蟻群算法從誕生到發(fā)展至今，已經(jīng)有多種蟻群優(yōu)化的算法，并且在實際的應(yīng)用中，表現(xiàn)出良好的應(yīng)用效果。但是從蟻群優(yōu)化算法的應(yīng)用結(jié)果綜合分析，其存在很大的隨機性和不確定型，在對大規(guī)模的優(yōu)化組合問題的解決時，常表現(xiàn)出受到局部最優(yōu)解的限制、收斂速度的缺點，對提高資源利用率具有不利的影響。本文提出的蟻群優(yōu)化算法的改進(jìn)方法將遺傳算法與蟻群算法結(jié)合起來，充分利用了遺傳算法在全局搜索中表現(xiàn)出來的快速隨即的優(yōu)勢特點，將其在蟻群算法的迭代中融入進(jìn)來，不僅使原算法的求解高精確性得以保持，而且有效的提高了收斂的速度。在此基礎(chǔ)上，將逆轉(zhuǎn)變異策略加以引進(jìn)，使陷入局部最優(yōu)的風(fēng)險得到了有效的規(guī)避，使種群的多樣性得以良好的維持。

在云環(huán)境下對于每個用戶提出的資源請求，服務(wù)集群會有一個請求任務(wù)和資源分配的組合的推薦，其所推薦的組合往往是優(yōu)化的。改進(jìn)后的蟻群優(yōu)化算法在當(dāng)前的分配策略中進(jìn)行一個最優(yōu)的策略的搜索，與此同時，所有與資源狀態(tài)有所關(guān)聯(lián)，對資源有所影響的因素都通過信息素來進(jìn)行描述，從而快速的得到最優(yōu)的預(yù)測結(jié)果。我們在云環(huán)境下蟻群優(yōu)化算法進(jìn)行路徑的優(yōu)化改進(jìn)時，可從對TSP問題和云環(huán)境資源分配問題的對比的角度出發(fā)，將二者的特征進(jìn)行關(guān)聯(lián)對比，從中得到改進(jìn)蟻群算法的啟示。我們將TSP問題與云環(huán)境資源分配問題各自的特征進(jìn)行對比，發(fā)現(xiàn)二者的差異性主要表現(xiàn)在以下幾個方面：1）云環(huán)境中的網(wǎng)絡(luò)資源不具有固定的拓?fù)浣Y(jié)構(gòu)，需要將資源活動過程中的相互作用來形成拓?fù)淠M的作用，而TSP問題中的城市間是存在有不等距離的相連并可達(dá)的邊；2）在云環(huán)境中信息素的表示是建立在對資源的計算能力等關(guān)聯(lián)系數(shù)的基礎(chǔ)之上的，而TSP問題中信息素是通過城市與城市間的不等的距離來進(jìn)行表示的；3）在云環(huán)境中需要利用資源自有的計算能力等屬性來對啟發(fā)信息加以表示。

在此基礎(chǔ)上對蟻群算法的改進(jìn)以現(xiàn)有的資源量為基礎(chǔ)，對下個任務(wù)執(zhí)行需要的資源分配量得計算方法進(jìn)行調(diào)整，在某個固定的t時段的信息濃度時，資源自有屬性用ηj來表示，用分別表示信息素的重要程度和資源自有屬性的重要程度，則計算方法改變?yōu)椋?/p>

（1）

上式中的歸屬于云計算已有的資源。在云環(huán)境下，有任務(wù)數(shù)量M個，向N個資源上進(jìn)行分配，通過改進(jìn)的蟻群優(yōu)化算法對各資源上對分配的任務(wù)的執(zhí)行所用的最短時間進(jìn)行計算，實現(xiàn)資源利用路徑的優(yōu)化。這個過程也就是求的下面函數(shù)最小值的過程：endprint

（2）

在上式中，M是向云計算提出的任務(wù)數(shù)量，向資源i進(jìn)行任務(wù)的分配，任務(wù)數(shù)量為mi，其最大值為資源執(zhí)行任務(wù)的上限。

4 仿真實驗檢驗

圖1 三種算法執(zhí)行任務(wù)時間對比分析圖

本文通過云計算仿真平臺，對改進(jìn)的蟻群算法進(jìn)行了仿真實驗檢驗，我們采用了輪循調(diào)度算法（RR）、蟻群優(yōu)化算法（ACO）、MACO三種算法進(jìn)行了資源分配的路徑對比，對各種算法執(zhí)行任務(wù)的時間結(jié)構(gòu)進(jìn)行記錄并對比分析。在對相同任務(wù)的執(zhí)行情況的情況下，對三種算法進(jìn)行任務(wù)執(zhí)行的時間進(jìn)行記錄和對比，結(jié)果如圖1所示。

從實驗結(jié)果對比圖來看，輪循調(diào)度算法執(zhí)行任務(wù)的時間隨著任務(wù)數(shù)量的增加而增加，蟻群優(yōu)化算法因為初始信息素數(shù)量較少的原因，執(zhí)行任務(wù)較慢，隨著信息素的不斷積累，任務(wù)執(zhí)行速度越來越快。最終結(jié)果改進(jìn)后的蟻群算法比其它算法任務(wù)執(zhí)行效率高。

5 結(jié)束語

標(biāo)準(zhǔn)蟻群算法在對大規(guī)模的組合優(yōu)化的過程中，具有收斂速度慢、陷入局部最優(yōu)化的缺陷，要解決這一難題，本文在對結(jié)合云環(huán)境的特征以及其與TSP問題的對比的基礎(chǔ)上，對標(biāo)準(zhǔn)蟻群算法加以改進(jìn)，將遺傳算法引入進(jìn)來，將其與蟻群算法相結(jié)合，加上逆轉(zhuǎn)變異策略的引入，使標(biāo)準(zhǔn)蟻群算法的缺陷問題得到了有效的解決。本文研究改進(jìn)蟻群算法在云環(huán)境下路徑的優(yōu)化設(shè)計通過仿真實驗的檢驗，與RR、MACO兩種算法進(jìn)行任務(wù)執(zhí)行時間的對比，結(jié)果表明，改進(jìn)后的蟻群算法在云環(huán)境下達(dá)到了路徑優(yōu)化的目的，實現(xiàn)了資源的高效分配，有效的提高了資源的利用率。

參考文獻(xiàn)

[1]史恒亮，唐振民.基于蟻群優(yōu)化算法的云數(shù)據(jù)庫動態(tài)路徑規(guī)劃[J].計算機科學(xué)，2012（05）.

[2]愛靜，郝志峰.雙向反饋蟻群算法在網(wǎng)絡(luò)負(fù)載均衡問題的研究[J].計算機工程與應(yīng)用2011（36）.

[3]丁建立，陳增強，袁著祉.遺傳肅反與蟻群算法的融合[J].計算機研究與發(fā)展，2011，9（40）：1352-1356.

[4]Nie Yu，Wu Xing.Shortest path problem consi-dering ontime arrival probability[J].Transportation Research Part B：Methodological，2012，43（6）：597-613.endprint

（2）

在上式中，M是向云計算提出的任務(wù)數(shù)量，向資源i進(jìn)行任務(wù)的分配，任務(wù)數(shù)量為mi，其最大值為資源執(zhí)行任務(wù)的上限。

4 仿真實驗檢驗

圖1 三種算法執(zhí)行任務(wù)時間對比分析圖

本文通過云計算仿真平臺，對改進(jìn)的蟻群算法進(jìn)行了仿真實驗檢驗，我們采用了輪循調(diào)度算法（RR）、蟻群優(yōu)化算法（ACO）、MACO三種算法進(jìn)行了資源分配的路徑對比，對各種算法執(zhí)行任務(wù)的時間結(jié)構(gòu)進(jìn)行記錄并對比分析。在對相同任務(wù)的執(zhí)行情況的情況下，對三種算法進(jìn)行任務(wù)執(zhí)行的時間進(jìn)行記錄和對比，結(jié)果如圖1所示。

從實驗結(jié)果對比圖來看，輪循調(diào)度算法執(zhí)行任務(wù)的時間隨著任務(wù)數(shù)量的增加而增加，蟻群優(yōu)化算法因為初始信息素數(shù)量較少的原因，執(zhí)行任務(wù)較慢，隨著信息素的不斷積累，任務(wù)執(zhí)行速度越來越快。最終結(jié)果改進(jìn)后的蟻群算法比其它算法任務(wù)執(zhí)行效率高。

5 結(jié)束語

標(biāo)準(zhǔn)蟻群算法在對大規(guī)模的組合優(yōu)化的過程中，具有收斂速度慢、陷入局部最優(yōu)化的缺陷，要解決這一難題，本文在對結(jié)合云環(huán)境的特征以及其與TSP問題的對比的基礎(chǔ)上，對標(biāo)準(zhǔn)蟻群算法加以改進(jìn)，將遺傳算法引入進(jìn)來，將其與蟻群算法相結(jié)合，加上逆轉(zhuǎn)變異策略的引入，使標(biāo)準(zhǔn)蟻群算法的缺陷問題得到了有效的解決。本文研究改進(jìn)蟻群算法在云環(huán)境下路徑的優(yōu)化設(shè)計通過仿真實驗的檢驗，與RR、MACO兩種算法進(jìn)行任務(wù)執(zhí)行時間的對比，結(jié)果表明，改進(jìn)后的蟻群算法在云環(huán)境下達(dá)到了路徑優(yōu)化的目的，實現(xiàn)了資源的高效分配，有效的提高了資源的利用率。

參考文獻(xiàn)

[1]史恒亮，唐振民.基于蟻群優(yōu)化算法的云數(shù)據(jù)庫動態(tài)路徑規(guī)劃[J].計算機科學(xué)，2012（05）.

[2]愛靜，郝志峰.雙向反饋蟻群算法在網(wǎng)絡(luò)負(fù)載均衡問題的研究[J].計算機工程與應(yīng)用2011（36）.

[3]丁建立，陳增強，袁著祉.遺傳肅反與蟻群算法的融合[J].計算機研究與發(fā)展，2011，9（40）：1352-1356.

[4]Nie Yu，Wu Xing.Shortest path problem consi-dering ontime arrival probability[J].Transportation Research Part B：Methodological，2012，43（6）：597-613.endprint

（2）

在上式中，M是向云計算提出的任務(wù)數(shù)量，向資源i進(jìn)行任務(wù)的分配，任務(wù)數(shù)量為mi，其最大值為資源執(zhí)行任務(wù)的上限。

4 仿真實驗檢驗

圖1 三種算法執(zhí)行任務(wù)時間對比分析圖

本文通過云計算仿真平臺，對改進(jìn)的蟻群算法進(jìn)行了仿真實驗檢驗，我們采用了輪循調(diào)度算法（RR）、蟻群優(yōu)化算法（ACO）、MACO三種算法進(jìn)行了資源分配的路徑對比，對各種算法執(zhí)行任務(wù)的時間結(jié)構(gòu)進(jìn)行記錄并對比分析。在對相同任務(wù)的執(zhí)行情況的情況下，對三種算法進(jìn)行任務(wù)執(zhí)行的時間進(jìn)行記錄和對比，結(jié)果如圖1所示。

從實驗結(jié)果對比圖來看，輪循調(diào)度算法執(zhí)行任務(wù)的時間隨著任務(wù)數(shù)量的增加而增加，蟻群優(yōu)化算法因為初始信息素數(shù)量較少的原因，執(zhí)行任務(wù)較慢，隨著信息素的不斷積累，任務(wù)執(zhí)行速度越來越快。最終結(jié)果改進(jìn)后的蟻群算法比其它算法任務(wù)執(zhí)行效率高。

5 結(jié)束語

標(biāo)準(zhǔn)蟻群算法在對大規(guī)模的組合優(yōu)化的過程中，具有收斂速度慢、陷入局部最優(yōu)化的缺陷，要解決這一難題，本文在對結(jié)合云環(huán)境的特征以及其與TSP問題的對比的基礎(chǔ)上，對標(biāo)準(zhǔn)蟻群算法加以改進(jìn)，將遺傳算法引入進(jìn)來，將其與蟻群算法相結(jié)合，加上逆轉(zhuǎn)變異策略的引入，使標(biāo)準(zhǔn)蟻群算法的缺陷問題得到了有效的解決。本文研究改進(jìn)蟻群算法在云環(huán)境下路徑的優(yōu)化設(shè)計通過仿真實驗的檢驗，與RR、MACO兩種算法進(jìn)行任務(wù)執(zhí)行時間的對比，結(jié)果表明，改進(jìn)后的蟻群算法在云環(huán)境下達(dá)到了路徑優(yōu)化的目的，實現(xiàn)了資源的高效分配，有效的提高了資源的利用率。

參考文獻(xiàn)

[1]史恒亮，唐振民.基于蟻群優(yōu)化算法的云數(shù)據(jù)庫動態(tài)路徑規(guī)劃[J].計算機科學(xué)，2012（05）.

[2]愛靜，郝志峰.雙向反饋蟻群算法在網(wǎng)絡(luò)負(fù)載均衡問題的研究[J].計算機工程與應(yīng)用2011（36）.

[3]丁建立，陳增強，袁著祉.遺傳肅反與蟻群算法的融合[J].計算機研究與發(fā)展，2011，9（40）：1352-1356.

[4]Nie Yu，Wu Xing.Shortest path problem consi-dering ontime arrival probability[J].Transportation Research Part B：Methodological，2012，43（6）：597-613.endprint