|
禁忌搜索算法評述
（作者未知） 2011/6/23
摘要:工程應(yīng)用中存在大量的優(yōu)化問題,對優(yōu)化算法的研究是目前研究的熱點(diǎn)之一。禁忌搜索算法作為一種新興的智能搜索算法具有模擬人類智能的記憶機(jī)制,已被廣泛應(yīng)用于各類優(yōu)化領(lǐng)域并取得了理想的效果。本文介紹了禁忌搜索算法的特點(diǎn)、應(yīng)用領(lǐng)域、研究進(jìn)展,概述了它的算法基本流程,評述了算法設(shè)計(jì)過程中的關(guān)鍵要點(diǎn),最后探討了禁忌搜索算法的研究方向和發(fā)展趨勢。
關(guān)鍵詞:禁忌搜索算法;優(yōu)化;禁忌表;啟發(fā)式;智能算法
1 引言
工程領(lǐng)域內(nèi)存在大量的優(yōu)化問題,對于優(yōu)化算法的研究一直是計(jì)算機(jī)領(lǐng)域內(nèi)的一個熱點(diǎn)問題。優(yōu)化算法主要分為啟發(fā)式算法和智能隨機(jī)算法。啟發(fā)式算法依賴對問題性質(zhì)的認(rèn)識,屬于局部優(yōu)化算法。智能隨機(jī)算法不依賴問題的性質(zhì),按一定規(guī)則搜索解空間,直到搜索到近似優(yōu)解或最優(yōu)解,屬于全局優(yōu)化算法,其代表有遺傳算法、模擬退火算法、粒子群算法、禁忌搜索算法等。禁忌搜索算法(Tabu Search, TS)最早是由Glover在1986年提出,它的實(shí)質(zhì)是對局部鄰域搜索的一種拓展。TS算法通過模擬人類智能的記憶機(jī)制,采用禁忌策略限制搜索過程陷入局部最優(yōu)來避免迂回搜索。同時引入特赦(破禁)準(zhǔn)則來釋放一些被禁忌的優(yōu)良狀態(tài),以保證搜索過程的有效性和多樣性。TS算法是一種具有不同于遺傳和模擬退火等算法特點(diǎn)的智能隨機(jī)算法,可以克服搜索過程易于早熟收斂的缺陷而達(dá)到全局優(yōu)化[1]。
迄今為止,TS算法已經(jīng)廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、生產(chǎn)調(diào)度、函數(shù)優(yōu)化、電路設(shè)計(jì)、路由優(yōu)化、投資分析和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域,并顯示出極好的研究前景[2~9,11~15]。目前關(guān)于TS的研究主要分為對TS算法過程和關(guān)鍵步驟的改進(jìn),用TS改進(jìn)已有優(yōu)化算法和應(yīng)用TS相關(guān)算法求解工程優(yōu)化問題三個方面。
禁忌搜索提出了一種基于智能記憶的框架,在實(shí)際實(shí)現(xiàn)過程中可以根據(jù)問題的性質(zhì)做有針對性的設(shè)計(jì),本文在給出禁忌搜索基本流程的基礎(chǔ)上,對如何設(shè)計(jì)算法中的關(guān)鍵步驟進(jìn)行了有益的總結(jié)和分析。
2 禁忌搜索算法的基本流程
TS算法一般流程描述[1]:
(1)設(shè)定算法參數(shù),產(chǎn)生初始解x,置空禁忌表。
(2)判斷是否滿足終止條件?若是,則結(jié)束,并輸出結(jié)果;否則,繼續(xù)以下步驟。
(3)利用當(dāng)前解x的鄰域結(jié)構(gòu)產(chǎn)生鄰域解,并從中確定若干候選解。
(4)對候選解判斷是否滿足藐視準(zhǔn)則?若成立,則用滿足藐視準(zhǔn)則的最佳狀態(tài)y替代x成為新的當(dāng)前解,并用y對應(yīng)的禁忌對象替換最早進(jìn)入禁忌表的禁忌對象,同時用y替換“best so far”狀態(tài),然后轉(zhuǎn)步驟(6);否則,繼續(xù)以下步驟。
(5)判斷候選解對應(yīng)的各對象的禁忌情況,選擇候選解集中非禁忌對象對應(yīng)的最佳狀態(tài)為新的當(dāng)前解,同時用與之對應(yīng)的禁忌對象替換最早進(jìn)入禁忌表的禁忌對象。
(6)轉(zhuǎn)步驟(2)。
算法可用圖1所示的流程圖更為直觀的描述。
3 禁忌搜索算法中的關(guān)鍵設(shè)計(jì)
3.1 編碼及初始解的構(gòu)造
禁忌搜索算法首先要對待求解的問題進(jìn)行抽象,分析問題解的形式以形成編碼。禁忌搜索的過程就是在解的編碼空間里找出代表最優(yōu)解或近似優(yōu)解的編碼串。編碼串的設(shè)計(jì)方式有多種策略,主要根據(jù)待解問題的特征而定。二進(jìn)制編碼將問題的解用一個二進(jìn)制串來表示[2],十進(jìn)制編碼將問題的解用一個十進(jìn)制串來表示[3],實(shí)數(shù)編碼將問題的解用一個實(shí)數(shù)來表示[4],在某些組合優(yōu)化問題中,還經(jīng)常使用混合編碼[5]、0-1矩陣編碼等。
禁忌搜索對初始解的依賴較大,好的初始解往往會提高最終的優(yōu)化效果。初始解的構(gòu)造可以隨機(jī)產(chǎn)生,但效果往往不夠理想,通常是基于問題特征信息,借助一些啟發(fā)式方法產(chǎn)生,以保證初始解的性能。
3.2 鄰域移動、鄰域解及鄰域解規(guī)模
鄰域移動,相關(guān)文獻(xiàn)也稱作鄰域操作、鄰域結(jié)構(gòu)、鄰域變換等。禁忌搜索要想不斷進(jìn)行就要依賴鄰域移動來不斷拓展搜索空間,鄰域移動是在當(dāng)前解的基礎(chǔ)上,按照特定的移動策略產(chǎn)生一定數(shù)目的新解,這些新解被稱為鄰域解,新解的數(shù)目稱為鄰域解規(guī)模。鄰域移動的設(shè)計(jì)通常與問題有關(guān),如排列置換類組合優(yōu)化問題,常用的鄰域移動方法是交換、插入、逆序等[3,6,7,8]。不同的移動將導(dǎo)致鄰域解個數(shù)及其變化情況的不同,進(jìn)而影響搜索的質(zhì)量和效率。在一些應(yīng)用中為了取得好的搜索效果,會根據(jù)搜索的進(jìn)展情況動態(tài)改變鄰域移動策略,即變鄰域移動[9]。鄰域移動的設(shè)計(jì)策略既要保證變化的有效性還要保證變化的平滑性,即產(chǎn)生的鄰域解和當(dāng)前解既有不同,又不能差異太大。不同使搜索過程向前進(jìn)行,不能差異太大保證搜索是有序而非隨機(jī)的搜索。鄰域解的規(guī)模,也并不總是取可產(chǎn)生鄰域解個數(shù)的上限,可以（未完，下一頁）
|