一種基于遺傳算法的副本優(yōu)化問題求解方法

《一種基于遺傳算法的副本優(yōu)化問題求解方法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、一種基于遺傳算法的副本優(yōu)化問題求解方法：針對分布式存儲系統(tǒng)中的副本優(yōu)化問題，本文提出一種利用遺傳算法進行求解的方法。首先對副本優(yōu)化問題進行了數(shù)學(xué)描述和建模，其次介紹了如何設(shè)計遺傳算法中的編碼、適應(yīng)度函數(shù)以及選擇、交叉和變異方法，最后通過實例進行了驗證。結(jié)果表明，該方法能有效求解副本優(yōu)化問題?！　￡P(guān)鍵詞：分布式存儲系統(tǒng)；遺傳算法；副本分發(fā)　　　　1引言　　遺傳算法（GeicAlgorithm，GA）是根據(jù)自然界的“物競天擇，適者生存”現(xiàn)象而提出的一種隨機搜索方法，最早由美國Michigan大學(xué)的Holland教授于2

2、0世紀70年代提出。該算法將優(yōu)化問題的求解看成是自然界中生物的進化過程，通過模擬生物進化過程中的遺傳規(guī)律，引入選擇、交叉和變異等方法，從而達到尋優(yōu)的目的。　　近年來，遺傳算法作為一種有效的工具，已經(jīng)被廣泛應(yīng)用于最優(yōu)化問題的求解中。副本優(yōu)化問題是一個NP完全問題。對此，本文提出一種基于遺傳算法的副本優(yōu)化問題求解方法，并設(shè)計了遺傳算法的編碼、適應(yīng)度函數(shù)以及選擇、交叉和變異方法?！　?遺傳算法　　在遺傳算法中，首先對問題的可能解按照某種形式進行編碼，并隨機生成初始種群，然后根據(jù)預(yù)定的評價函數(shù)對每一個體計算適應(yīng)值，從中選擇

3、適應(yīng)度高的個體進行復(fù)制，再通過遺傳操作來產(chǎn)生新的種群。如此反復(fù)迭代進化，最后收斂到適應(yīng)環(huán)境的染色體上。　　遺傳算法維持由一群個體組成的種群P（t）（t為遺傳的代數(shù)），每一個體均代表優(yōu)化問題的一個潛在的解，它們被評價優(yōu)劣并得到其適應(yīng)值。其中，某些個體要經(jīng)歷稱作遺傳操作的隨機變換，并由此產(chǎn)生新的個體。主要有兩種變換方法：（1）雜交的方法是將兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新的個體；（2）變異的方法是將一個個體改變從而獲得新的個體。新產(chǎn)生的后代C（t）繼續(xù)被評價優(yōu)劣，然后從父代種群P（t）和C（t）中選擇比較優(yōu)秀

4、的個體形成新的種群。這樣，經(jīng)過若干代以后，算法收斂到一個最優(yōu)個體，該個體很有可能就是問題的最優(yōu)或次優(yōu)解?！　?基于遺傳算法的副本分發(fā)模型求解方法　　3.1副本優(yōu)化問題描述及建?！　≡诜植际酱鎯ο到y(tǒng)中，一個合理優(yōu)化的副本方案，應(yīng)該能夠以最小的副本數(shù)使得各個節(jié)點的單個請求響應(yīng)時間滿足給定的約束條件，并且在此基礎(chǔ)上盡可能地使得系統(tǒng)總的請求響應(yīng)時間最小化。由此，可以描述為如下集合覆蓋問題（SetCoveringProblem,SCP）：　　其中，bi=0或1，aji=0或1，n為節(jié)點的個數(shù)，1≤i≤n。約定：當節(jié)點Si包含

5、文件的副本時，bi=1，否則bi=0；當節(jié)點Sj從Si處訪問文件的時間滿足用戶給定要求時，aji=1，否則aji=0?！　CP是一個經(jīng)典的組合優(yōu)化問題，已經(jīng)被證明是一個NP完全問題。對此，本文將采用遺傳算法進行求解?！　?.2副本分發(fā)模型求解　　3.2.1編碼　　在副本優(yōu)化問題中，將需要創(chuàng)建副本的節(jié)點標記為1，其它節(jié)點標記為0。這樣，問題的解就可以表示為一組由0、1組成的二進制串。記rs為采用二進制進行編碼后的個體，則其可表示為b1b2…bn。其中，n為個體基因總數(shù)，也即總的節(jié)點個數(shù)。　　3.2.2適應(yīng)度函數(shù)　　

6、對于任意個體rs，只要某個節(jié)點的單個請求響應(yīng)時間不能夠滿足用戶給定的要求，則該個體應(yīng)予以淘汰，相應(yīng)的適應(yīng)值應(yīng)該盡可能小。反之，當所有節(jié)點的單個請求響應(yīng)時間均能滿足用戶給定的要求時，rs所需創(chuàng)建的副本數(shù)越少，則表明其優(yōu)良程度越高，相應(yīng)的適應(yīng)值應(yīng)該越大。此外，當兩個個體所需創(chuàng)建的副本數(shù)相同時，總的請求響應(yīng)時間越少的個體，其適應(yīng)值應(yīng)該越大。于是，本文設(shè)計的適應(yīng)度函數(shù)定義為：　　其中，ε為一充分小的正數(shù)，T為在沒有創(chuàng)建任何副本情況下系統(tǒng)總的請求響應(yīng)時間，T'為系統(tǒng)實際總的請求響應(yīng)時間，RTi為節(jié)點i的訪問時間，Tthres

7、hold為給定的時間要求?！　?.2.3選擇　　首先根據(jù)適應(yīng)度函數(shù)依次計算當前種群中個體的適應(yīng)值，適應(yīng)值大的個體將直接保留到下一代種群中。然后根據(jù)個體的適應(yīng)值計算出其相對適應(yīng)值，并作為該個體的選擇概率。不妨設(shè)種群規(guī)模為m，則個體rsi被選中遺傳到下一代種群的概率為：　　最后，采用輪盤賭選擇（roulette（即變異率）隨機地改變?nèi)旧w串上的一位或多位基因，其作用是增加種群的多樣性，擴大搜索空間。具體過程如下：　　1）首先生成一隨機數(shù)k，k作為隨機變量服從于[0，1]上的均勻分布；　　2）如果k≤pm，則對該個體進行

8、變異；否則，不進行變異?！　∽儺愡^程如下：　　1）用隨機函數(shù)產(chǎn)生一個變異位（例子中變異位為3）；　　2）將變異個體的變異位取反，其它基因保持不變。　　例如：0000011100→0010011100　　3.2.6終止條件　　在迭代過程中，如果解空間連續(xù)3次保持不變，稱此為收斂。當滿足上述條件時，如果迭代次數(shù)少于某個預(yù)設(shè)下限，則為收斂過早，此時應(yīng)重新生成新的初