關(guān)于進(jìn)化算法記憶存儲(chǔ)方法的探討

摘要:針對(duì)進(jìn)化算法的不同個(gè)體表示，分析研究了基于進(jìn)化個(gè)體或其特征的存儲(chǔ)表示和基于進(jìn)化種群的概率記憶存儲(chǔ)表示兩類存儲(chǔ)方法#65377;通過研制分析可以看出，有效的搜索歷史記憶存儲(chǔ)方法能很好進(jìn)行數(shù)據(jù)的存儲(chǔ)和管理#65377;如果記憶的存儲(chǔ)方法與進(jìn)化算法的控制過程相配合，則整個(gè)進(jìn)化算法會(huì)變得更加有效#65377;

關(guān)鍵詞:進(jìn)化算法; 短期策略; 長期策略

中圖分類號(hào):TP18文獻(xiàn)標(biāo)志碼:A

文章編號(hào):10013695(2007)04008803

進(jìn)化算法是組合優(yōu)化問題中的高級(jí)啟發(fā)式算法之一#65377;目前進(jìn)化算法在工程運(yùn)用中相當(dāng)廣泛，特別對(duì)解決NP問題^[1]的求解具有很好的效果#65377;而對(duì)于功能強(qiáng)大#65380;搜索效果好的啟發(fā)式算法最基本的要素就是這個(gè)算法有沒有使用搜索記憶功能^[2]#65377;一般來說，對(duì)于一個(gè)啟發(fā)式算法，如果使用的搜索記憶功能越好，搜索過程也就更能逼近問題的最優(yōu)解#65377;而搜索記憶存儲(chǔ)方法是搜索記憶功能運(yùn)用的關(guān)鍵#65377;一個(gè)好的記憶存儲(chǔ)方法不僅能節(jié)約整個(gè)算法占用的存儲(chǔ)空間(臨時(shí)內(nèi)存存儲(chǔ)或長期的硬盤存儲(chǔ))，而且也能引導(dǎo)搜索更快地朝著全局最優(yōu)的方向搜索，更好地脫離搜索區(qū)域的局部最優(yōu)點(diǎn)#65377;

使用搜索記憶功能引導(dǎo)搜索啟發(fā)式搜索最早由Glover于1986年在禁止接近法(Tabu Search)中首次提出^[3]#65377;禁止接近法搜索將最近搜索經(jīng)歷的解或其屬性寫入禁止接近列表中，以后產(chǎn)生的點(diǎn)禁止再朝這些已經(jīng)訪問的點(diǎn)方向進(jìn)行搜索#65377;禁止接近法采用將最近訪問的點(diǎn)形成一個(gè)列表，然后禁止向這些已經(jīng)訪問的點(diǎn)進(jìn)行搜索#65377;這種利用歷史記憶的搜索方法能更有效地避免陷入局部最優(yōu)，同時(shí)也能有效避免在一定范圍內(nèi)形成搜索的回路^[4]#65377;

進(jìn)化算法的搜索空間一般都比較大，如果不考慮一個(gè)有效的方法存儲(chǔ)已搜索過的解空間，而將所有訪問過的每一個(gè)解都直接保存下來是無效的，有時(shí)也是往往不可能實(shí)現(xiàn)的#65377;另外，探討進(jìn)化算法的搜索記憶存儲(chǔ)方法對(duì)于利用搜索歷史的方式方法，對(duì)歷史數(shù)據(jù)的查找使用也有重要意義#65377;本文在前人對(duì)記憶存儲(chǔ)研究的基礎(chǔ)上，討論如何在進(jìn)化算法中使用#65380;記錄搜索的歷史數(shù)據(jù)#65377;著重分析和研究了兩種常用的記憶存儲(chǔ)方法，即基于隱碼的二進(jìn)制編碼存儲(chǔ)方法和基于進(jìn)化種群的概念記憶存儲(chǔ)表示#65377;相信能對(duì)進(jìn)化算法實(shí)際問題中使用記憶存儲(chǔ)和搜索起到一定的借鑒作用#65377;

1搜索記憶存儲(chǔ)的總體要求

自從禁止接近搜索開始使用搜索記憶功能以來，很多高級(jí)啟發(fā)式算法的改進(jìn)或新的啟發(fā)式算法都開始利用搜索歷史經(jīng)歷的功能，如分散搜索(Scatter Search)^[5，6]#65380;分布概率評(píng)估算法(EDA)^[7]#65380;引導(dǎo)的變異算子^[8]等#65377;這些使用搜索歷史的方式大致可以分為兩種策略，即短期策略和長期策略^[9]#65377;短期策略是指搜索的歷史只能影響到近期的有限步驟搜索，能在一定范圍內(nèi)避免重復(fù)搜索和搜索的回路#65377;短期搜索的優(yōu)點(diǎn)是一般需要存儲(chǔ)的搜索歷史時(shí)間不是很長，占用的存儲(chǔ)空間也不是很大，后面的新搜索經(jīng)歷可以替代一些過時(shí)的存儲(chǔ)經(jīng)歷#65377;然而短期搜索也有其缺點(diǎn)，就是搜索歷史的作用是短期的，不能對(duì)整個(gè)搜索過程進(jìn)行影響，也不能避免整個(gè)搜索過程(或大范圍的搜索過程)的重復(fù)和搜索回路#65377;長期策略是指搜索歷史可以影響到后來的所有搜索過程，后面的搜索過程利用全部搜索的歷史搜索經(jīng)驗(yàn)#65377;當(dāng)然搜索的空間一般都很大，長期搜索想記錄每一個(gè)搜索的個(gè)體是有一定難度的#65377;這種搜索記憶方法有些是基于概率#65380;有些也基于個(gè)體的影響程度#65380;基于個(gè)體的適應(yīng)度函數(shù)質(zhì)量等#65377;長期策略可以說優(yōu)點(diǎn)是顯而易見的，它能夠指引整個(gè)搜索過程，但也有其缺點(diǎn):其搜索記憶存儲(chǔ)方法的表示相當(dāng)重要，往往占用的存儲(chǔ)空間也較大;記憶過程中相關(guān)的計(jì)算量也較短期策略要大，搜索控制的復(fù)雜度也較短期搜索有相應(yīng)的提高#65377;

對(duì)于特定的進(jìn)化算法，搜索記憶存儲(chǔ)應(yīng)該滿足一定的約束條件#65377;搜索記憶存儲(chǔ)方法總體應(yīng)該為進(jìn)化算法的整體性能服務(wù)，它是整個(gè)進(jìn)化算法的一個(gè)組成部分#65377;所以搜索記憶存儲(chǔ)方法應(yīng)該滿足以下幾個(gè)條件:

(1)搜索記憶存儲(chǔ)方法應(yīng)該與進(jìn)化算法的個(gè)體表示方法相適應(yīng)#65377;對(duì)于不同的個(gè)體表示方法，應(yīng)該有不同的搜索記憶存儲(chǔ)方法#65377;

(2)搜索記憶存儲(chǔ)方法應(yīng)該與進(jìn)化算法的控制過程相適應(yīng)#65377;進(jìn)化的控制過程要利用記憶存儲(chǔ)的內(nèi)容#65377;記憶存儲(chǔ)的內(nèi)容可以是個(gè)體信息，也可以是個(gè)體信息相對(duì)應(yīng)的特征#65377;當(dāng)然如果控制過程是基于利用搜索歷史的概率分布知識(shí)，則存儲(chǔ)的內(nèi)容可能是個(gè)體基因組對(duì)應(yīng)的概率分布#65377;

(3)搜索記憶存儲(chǔ)方法應(yīng)該充分考慮存儲(chǔ)和搜索的效率#65377;存儲(chǔ)方式與搜索方法也是相對(duì)應(yīng)的#65377;如果存儲(chǔ)的效率較高，則相同的存儲(chǔ)空間就能存更多的歷史數(shù)據(jù)#65377;同樣如果相對(duì)應(yīng)的搜索效率較高的話，就能夠在使用歷史數(shù)據(jù)時(shí)更有效，整個(gè)進(jìn)化算法也會(huì)更有效，進(jìn)化的速度也會(huì)得到相應(yīng)提高#65377;

2基于隱碼的二進(jìn)制編碼存儲(chǔ)表示

在使用搜索記憶功能時(shí)，一開始人們比較容易想到的是使用記錄搜索過的個(gè)體或其特征的信息#65377;禁止接近法搜索的原形也就是使用歷史記錄個(gè)體的信息，而改進(jìn)的禁止接近法算法因?yàn)楦械酱鎯?chǔ)完整個(gè)體信息不是很有效(有些個(gè)體的表示較為復(fù)雜，存儲(chǔ)空間較大)，所以改用了存儲(chǔ)其個(gè)體的部分特征#65377;應(yīng)該講存儲(chǔ)特征是存儲(chǔ)方法一個(gè)層次上的抽象，能夠比較有效地利用存儲(chǔ)空間#65377;

直接存儲(chǔ)完整的個(gè)體或其特征一般采取的是列表方式，記為Slist#65377;對(duì)于短期策略，由于列表長度一般是固定的，設(shè)為N#65377;列表的管理一般采取先進(jìn)先出的管理方式進(jìn)行，當(dāng)要加入一個(gè)新的搜索點(diǎn)P時(shí)，先判斷當(dāng)前列表長度;如果Slist.Length()==N時(shí)，則先退出一個(gè)列表中數(shù)據(jù)Slist.Pop()，然后將新的數(shù)據(jù)加入到列表Slist.Push(P)中#65377;對(duì)于長期策略，由于要記錄保持所有搜索過的點(diǎn)或其特征，必須用新的方法來進(jìn)行存儲(chǔ)#65377;下面分析一種新的基于隱碼的二

進(jìn)制編碼存儲(chǔ)表示方法#65377;

2.1基于隱碼的二進(jìn)制編碼存儲(chǔ)方法

基于隱碼的二進(jìn)制編碼存儲(chǔ)方法是指在存儲(chǔ)已經(jīng)搜索的二進(jìn)制串個(gè)體或二進(jìn)制串對(duì)應(yīng)的個(gè)體屬性時(shí)，還記錄一個(gè)相對(duì)應(yīng)的二進(jìn)制隱碼串#65377;二進(jìn)制隱碼串的長度與其個(gè)體的二進(jìn)制長度相一致#65377;如果二進(jìn)制隱碼串某幾個(gè)位置的值為“1”時(shí)，則表示相對(duì)應(yīng)的二進(jìn)制個(gè)體的位置上所有可能的取值都已經(jīng)被搜索過了#65377;圖1可以看出帶有隱碼表示對(duì)應(yīng)已經(jīng)搜索過的個(gè)體#65377;

從基于隱碼的二進(jìn)制表示的定義可以看出，這種表示方法的效率是與隱碼串中“1”的個(gè)數(shù)有關(guān)系的#65377;稱隱碼串中“1”的個(gè)數(shù)為表示度d，圖1中的表示度為2#65377;基于隱碼的二進(jìn)制表示實(shí)際表示個(gè)體數(shù)目為2d，而一般個(gè)體編碼串對(duì)應(yīng)的個(gè)體是這一組個(gè)體中適應(yīng)度最好的個(gè)體#65377;

2.2基于隱碼的二進(jìn)制編碼存儲(chǔ)性能分析

有時(shí)可能要計(jì)算多個(gè)基于隱碼的二進(jìn)制表示能代表多少不同的個(gè)體#65377;如果兩個(gè)個(gè)體編碼串分別為x#65380;y;其對(duì)應(yīng)的隱碼串為mx#65380;my#65377;每個(gè)編碼串代表的個(gè)體集合為X#65380;Y;編碼串的長度為L;l表示編碼串的位置(1≤l≤L);xl#65380;yl#65380;mxl#65380;myl表示個(gè)體和隱碼串在l處對(duì)應(yīng)的值#65377;對(duì)應(yīng)筆者在此先定義兩個(gè)基于隱碼的二進(jìn)制表示之間的海明距離(Hamming Distance):

定義1基于隱碼表示的個(gè)體x#65380;y之間海明距離是指兩個(gè)對(duì)應(yīng)集合X#65380;Y內(nèi)個(gè)體的海明距離的最小值:

Hd(x，y)=min(hd(xi，yi)) xi∈X，yj∈Y(1)

根據(jù)基于隱碼表示的方法，可以將式(1)利用式(2)進(jìn)行計(jì)算:

Hd(x，y)=∑Ll=1B|xl-yl|，

B=1if mxl=myl=00otherwise(2)

當(dāng)有N個(gè)基于隱碼表示的個(gè)體xi(1≤i≤N)，其對(duì)應(yīng)表示的個(gè)體集合為Xi，則這N個(gè)集合并集所代表的個(gè)體數(shù)目為|∪i∈IXi|#65377;其中I表示集合{1，2…，N}#65377;根據(jù)容斥原理，這N個(gè)集合的并集可表示為

對(duì)于求幾個(gè)基于隱碼的交集，可以通過其海明距離來進(jìn)行求解#65377;如果其海明距離為0，則交集不為空，交集的個(gè)體數(shù)目為2m，m為其隱碼位全為1的數(shù)目#65377;具體公式如下:

對(duì)于一個(gè)剛剛進(jìn)化產(chǎn)生的個(gè)體x，如何判斷其是否已經(jīng)被搜索過，主要是通過x(其隱碼看成全為0)和所有的基于隱碼的二進(jìn)制表示的海明距離來判斷#65377;如果其中有一個(gè)海明距離為0，表示個(gè)體x已經(jīng)屬于這個(gè)基于隱碼的二進(jìn)制表示的集合#65377;如果x不在搜索的歷史中則判x和其對(duì)應(yīng)全為0的隱碼串能否與現(xiàn)在歷史記錄進(jìn)行合并#65377;x和y滿足合并的條件和方法如下:x和y對(duì)應(yīng)的掩碼串相等即mx=my，且Hd(x，y)=1#65377;在這種情況下有且僅有一個(gè)位置l*滿足mxl*=myl*=0且xl*≠yl*#65377;這里將對(duì)應(yīng)掩碼相應(yīng)l*位置為1，個(gè)體的二進(jìn)制表示由x或y表示(一般由適應(yīng)度最大的表示)#65377;

2.3基于隱碼的二進(jìn)制編碼存儲(chǔ)分析結(jié)論

基于隱碼的二進(jìn)制編碼存儲(chǔ)方法對(duì)于存儲(chǔ)空間的節(jié)約方面還是比較有效的，特別是對(duì)隱碼的表示度較大的情況下節(jié)約空間比較可觀#65377;但是經(jīng)過仔細(xì)分析也可以看出，如果該種表示方法不能與進(jìn)化算法進(jìn)行有效的配合或調(diào)整，在比較壞的情況下存儲(chǔ)空間的消耗也是很大的，特別是在個(gè)體不能進(jìn)行合并的情況下#65377;例如對(duì)于編碼長度為L的編碼串，在最壞的情況下不能合并的個(gè)體數(shù)目M滿足式(5)#65377;在實(shí)際問題中，在使用基于隱碼的二進(jìn)制編碼存儲(chǔ)方法的同時(shí)也要結(jié)合一些局部的搜索方法提高個(gè)體解的合并程度#65377;

在進(jìn)化算法中，現(xiàn)在很多問題用實(shí)數(shù)進(jìn)行表示#65377;如果實(shí)數(shù)采用二進(jìn)制方式進(jìn)行編碼的話，同樣可以直接采取上述的基于隱碼的二進(jìn)制編碼存儲(chǔ)方法進(jìn)行表示#65377;如果個(gè)體是直接用實(shí)數(shù)進(jìn)行表示的個(gè)體，則可以采取下面的方法將進(jìn)化結(jié)果的個(gè)體采取轉(zhuǎn)變?yōu)槎M(jìn)制的方式進(jìn)行存儲(chǔ)表示#65377;假定個(gè)體是由L個(gè)實(shí)數(shù)變量表示，記為xi(1≤i≤L)#65377;根據(jù)xi允許的誤差范圍和每個(gè)變量的搜索范圍可以構(gòu)建一個(gè)二進(jìn)制串#65377;這個(gè)二進(jìn)制串的長度也是固定的，不過中間有L-1個(gè)點(diǎn)將這個(gè)二進(jìn)制串分割成L段，每一段代表一個(gè)數(shù)量變量值#65377;整個(gè)二進(jìn)制串的存儲(chǔ)方法可以采用上面介紹的基于隱碼的表示方法#65377;

基于隱碼的二進(jìn)制編碼存儲(chǔ)方法能夠有效地節(jié)約搜索歷史個(gè)體的存儲(chǔ)空間#65377;但仍然需要較大的內(nèi)存空間，在實(shí)施時(shí)可以數(shù)據(jù)庫的方式進(jìn)行存儲(chǔ)，這樣能有效進(jìn)行數(shù)據(jù)查找和處理#65377;另外一種思路就是不具體存儲(chǔ)每一個(gè)個(gè)體或其屬性，而是在搜索過程中以概率的方式存儲(chǔ)種群中各個(gè)基因組對(duì)應(yīng)的分布#65377;

3基于進(jìn)化種群的概率記憶存儲(chǔ)

3.1基于進(jìn)化種群的概率記憶存儲(chǔ)表示

基于進(jìn)化種群的概率記憶存儲(chǔ)是指不具體存儲(chǔ)每一個(gè)個(gè)體，而是記錄搜索歷史中每個(gè)屬性所分布的概率#65377;對(duì)于一個(gè)L位的二進(jìn)制串，每一位可以看成個(gè)體的一個(gè)屬性，則用一個(gè)向量表示其屬性的概率分布

p=(p1，p2，…，pL)#65377;如果進(jìn)化算法中種群的數(shù)量為N，相應(yīng)的個(gè)體記為xi=(xi1，…，xiL)，i=1，2，…，N#65377;則對(duì)于向量p的初始值，如果種群是隨機(jī)初始化的，則可以把向量初始化為05(表示該位取0或取1的概率相等)#65377;如果種群的初始化采用啟發(fā)式方法，則用式(6)進(jìn)行初始化:

pj=∑Ni=1xij/N， j=1，…，L(6)

對(duì)于在進(jìn)化過程中，通過交叉#65380;變異算子或其他控制方法由種群的父代Pop(t)產(chǎn)生新的一代Pop(t+1)#65377;在產(chǎn)生下一代后需要對(duì)種群概率分布進(jìn)行更新:

3.2基于進(jìn)化種群的概率記憶存儲(chǔ)分析

基于進(jìn)化種群的概率記憶存儲(chǔ)所占用的存儲(chǔ)空間是一定的#65377;其中概率分布向量代表個(gè)體屬性的概率值，只是在下一代產(chǎn)生中用一個(gè)變量λ作為更新的速率參數(shù)，取值范圍為(0，1]#65377;λ越大表示當(dāng)前種群對(duì)概率分布的貢獻(xiàn)比例越大#65377;對(duì)于極端的情況當(dāng)λ=1時(shí)，表示當(dāng)前的概念分布僅是當(dāng)前種群中個(gè)體屬性的分布狀況#65377;

基于進(jìn)化種群的概率記憶存儲(chǔ)的控制過程可以結(jié)合進(jìn)化過程中的遺傳變異算子進(jìn)行控制#65377;在一定的概率條件下采用遺傳和變異算子進(jìn)行產(chǎn)生子代，而剩下的概率情況采用基于進(jìn)化種群的概率記憶存儲(chǔ)表示#65377;這樣有利于結(jié)合常規(guī)進(jìn)化算法和基于種群的概率記憶的優(yōu)點(diǎn)，使搜索過程在利用搜索歷史記憶的基礎(chǔ)上快速達(dá)到問題的最優(yōu)解或近似最優(yōu)解#65377;

4結(jié)束語

進(jìn)化算法利用歷史搜索記憶功能進(jìn)行搜索，是進(jìn)化算法中比較智能和有效的方法#65377;歷史搜索中，記憶是較為關(guān)鍵的問題#65377;本文對(duì)進(jìn)化算法歷史搜索的存儲(chǔ)方法進(jìn)行了研究和探討，著重分析了基于隱碼的二進(jìn)制編碼存儲(chǔ)方法和基于進(jìn)化種群的概率記憶存儲(chǔ)方法#65377;從分析中可以看出，采用基于隱碼的二進(jìn)制編碼存儲(chǔ)方法可以有效地節(jié)約個(gè)體或其屬性的存儲(chǔ)空間#65377;另外對(duì)于實(shí)數(shù)編碼的個(gè)體可以通過二進(jìn)制轉(zhuǎn)換將其轉(zhuǎn)換為基于隱碼的二進(jìn)制編碼的存儲(chǔ)方法#65377;基于進(jìn)化種群的概率記憶存儲(chǔ)方法在占用存儲(chǔ)空間的方面優(yōu)點(diǎn)是比較突出的，它僅僅存儲(chǔ)了搜索歷史的概率分布，而并沒有存儲(chǔ)具體的個(gè)體或其特征的表示#65377;

基于隱碼的二進(jìn)制編碼存儲(chǔ)方法還是有兩大缺點(diǎn):①如果搜索的歷史比較分散，無法進(jìn)行隱碼合并時(shí)所需占用的存儲(chǔ)空間還是比較大的，所以在實(shí)際運(yùn)用時(shí)可以用數(shù)據(jù)庫進(jìn)行管理和存儲(chǔ)數(shù)據(jù)#65377;另外可以結(jié)合補(bǔ)充搜索和局部搜索的方法提高數(shù)據(jù)合并的可能#65377;②歷史數(shù)據(jù)的搜索和合并過程中占用的計(jì)算資源比較大，對(duì)于實(shí)際問題可以采取并行的方式或分布數(shù)據(jù)庫方式進(jìn)行數(shù)據(jù)的存儲(chǔ)和管理#65377;

最后在分析研究進(jìn)化算法的歷史記憶存儲(chǔ)方法時(shí)，本文認(rèn)為還有以下的問題有待進(jìn)行深入的研究和探討:

(1)歷史記憶存儲(chǔ)問題要結(jié)合實(shí)際進(jìn)行運(yùn)用研究，特別是對(duì)于實(shí)際問題，要尋找能代表個(gè)體特征的屬性#65377;對(duì)于個(gè)體表示比較復(fù)雜時(shí)，可以存儲(chǔ)有代表意義的特征屬性進(jìn)行存儲(chǔ)表示，從而節(jié)約實(shí)際的存儲(chǔ)空間#65377;

(2)研究記憶存儲(chǔ)的方法要與進(jìn)化算法的控制結(jié)合進(jìn)行研究，這樣可以使歷史記憶的內(nèi)容和知識(shí)得到充分運(yùn)用#65377;同時(shí)有效的算法控制也能在實(shí)際過程中減少記憶存儲(chǔ)的存儲(chǔ)空間#65377;

(3)對(duì)于概率分布的記憶存儲(chǔ)表示，要研究各基因或?qū)傩灾g的依賴關(guān)系#65377;如果屬性之間是相互獨(dú)立的，則概率的表示可以相互獨(dú)立;如果基因或?qū)傩灾g不是相互獨(dú)立的，可以通過其依賴關(guān)系進(jìn)行分析計(jì)算#65377;

(4)記憶存儲(chǔ)問題的研究可以與其他技術(shù)相結(jié)合進(jìn)行優(yōu)化和提高#65377;例如可以用分布存儲(chǔ)的方法改善數(shù)據(jù)的存儲(chǔ)和管理，也可以用并行的方法提高數(shù)據(jù)的處理能力#65377;

本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。