禁忌搜索算法評述

《禁忌搜索算法評述》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、禁忌搜索算法評述摘要:工程應(yīng)用中存在大量的優(yōu)化問題,對優(yōu)化算法的研究是目前研究的熱點之一。禁忌搜索算法作為一種新興的智能搜索算法具有模擬人類智能的記憶機制,已被廣泛應(yīng)用于各類優(yōu)化領(lǐng)域并取得了理想的效果。本文介紹了禁忌搜索算法的特點、應(yīng)用領(lǐng)域、研究進展,概述了它的算法基本流程,評述了算法設(shè)計過程中的關(guān)鍵要點,最后探討了禁忌搜索算法的研究方向和發(fā)展趨勢?！　￡P(guān)鍵詞:禁忌搜索算法;優(yōu)化;禁忌表;啟發(fā)式;智能算法　　　　1引言　　工程領(lǐng)域內(nèi)存在大量的優(yōu)化問題,對于優(yōu)化算法的研究一直是計算機領(lǐng)域內(nèi)的一個熱點問題

2、。優(yōu)化算法主要分為啟發(fā)式算法和智能隨機算法。啟發(fā)式算法依賴對問題性質(zhì)的認識,屬于局部優(yōu)化算法。智能隨機算法不依賴問題的性質(zhì),按一定規(guī)則搜索解空間,直到搜索到近似優(yōu)解或最優(yōu)解,屬于全局優(yōu)化算法,其代表有遺傳算法、模擬退火算法、粒子群算法、禁忌搜索算法等。禁忌搜索算法(TabuSearch,TS)最早是由Glover在1986年提出,它的實質(zhì)是對局部鄰域搜索的一種拓展。TS算法通過模擬人類智能的記憶機制,采用禁忌策略限制搜索過程陷入局部最優(yōu)來避免迂回搜索。同時引入特赦(破禁)準則來釋放一些被禁忌的優(yōu)良狀態(tài)

3、,以保證搜索過程的有效性和多樣性。TS算法是一種具有不同于遺傳和模擬退火等算法特點的智能隨機算法,可以克服搜索過程易于早熟收斂的缺陷而達到全局優(yōu)化[1]?！　∑駷橹?TS算法已經(jīng)廣泛應(yīng)用于組合優(yōu)化、機器學(xué)習(xí)、生產(chǎn)調(diào)度、函數(shù)優(yōu)化、電路設(shè)計、路由優(yōu)化、投資分析和神經(jīng)X絡(luò)等領(lǐng)域,并顯示出極好的研究前景[2~9,11~15]。目前關(guān)于TS的研究主要分為對TS算法過程和關(guān)鍵步驟的改進,用TS改進已有優(yōu)化算法和應(yīng)用TS相關(guān)算法求解工程優(yōu)化問題三個方面?！　〗伤阉魈岢隽艘环N基于智能記憶的框架,在實際實現(xiàn)過程中可

4、以根據(jù)問題的性質(zhì)做有針對性的設(shè)計,本文在給出禁忌搜索基本流程的基礎(chǔ)上,對如何設(shè)計算法中的關(guā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)對候選解判斷是否滿足藐視準則?若成立,則用滿足藐視準則的最佳狀態(tài)y替代x成為新的當(dāng)前解,并用y對應(yīng)的禁忌對象替換最早進入禁

5、忌表的禁忌對象,同時用y替換“bestsofar”狀態(tài),然后轉(zhuǎn)步驟(6);否則,繼續(xù)以下步驟?！　?5)判斷候選解對應(yīng)的各對象的禁忌情況,選擇候選解集中非禁忌對象對應(yīng)的最佳狀態(tài)為新的當(dāng)前解,同時用與之對應(yīng)的禁忌對象替換最早進入禁忌表的禁忌對象?！　?6)轉(zhuǎn)步驟(2)?！　∷惴捎脠D1所示的流程圖更為直觀的描述。　　　　3禁忌搜索算法中的關(guān)鍵設(shè)計　　3.1編碼及初始解的構(gòu)造　　禁忌搜索算法首先要對待求解的問題進行抽象,分析問題解的形式以形成編碼。禁忌搜索的過程就是在解的編碼空間里找出代表最優(yōu)解或近似優(yōu)解

6、的編碼串。編碼串的設(shè)計方式有多種策略,主要根據(jù)待解問題的特征而定。二進制編碼將問題的解用一個二進制串來表示[2],十進制編碼將問題的解用一個十進制串來表示[3],實數(shù)編碼將問題的解用一個實數(shù)來表示[4],在某些組合優(yōu)化問題中,還經(jīng)常使用混合編碼[5]、0-1矩陣編碼等?！　〗伤阉鲗Τ跏冀獾囊蕾囕^大,好的初始解往往會提高最終的優(yōu)化效果。初始解的構(gòu)造可以隨機產(chǎn)生,但效果往往不夠理想,通常是基于問題特征信息,借助一些啟發(fā)式方法產(chǎn)生,以保證初始解的性能?！　?.2鄰域移動、鄰域解及鄰域解規(guī)?！　∴徲蛞苿?相

7、關(guān)文獻也稱作鄰域操作、鄰域結(jié)構(gòu)、鄰域變換等。禁忌搜索要想不斷進行就要依賴鄰域移動來不斷拓展搜索空間,鄰域移動是在當(dāng)前解的基礎(chǔ)上,按照特定的移動策略產(chǎn)生一定數(shù)目的新解,這些新解被稱為鄰域解,新解的數(shù)目稱為鄰域解規(guī)模。鄰域移動的設(shè)計通常與問題有關(guān),如排列置換類組合優(yōu)化問題,常用的鄰域移動方法是交換、插入、逆序等[3,6,7,8]。不同的移動將導(dǎo)致鄰域解個數(shù)及其變化情況的不同,進而影響搜索的質(zhì)量和效率。在一些應(yīng)用中為了取得好的搜索效果,會根據(jù)搜索的進展情況動態(tài)改變鄰域移動策略,即變鄰域移動[9]。鄰域移動的

8、設(shè)計策略既要保證變化的有效性還要保證變化的平滑性,即產(chǎn)生的鄰域解和當(dāng)前解既有不同,又不能差異太大。不同使搜索過程向前進行,不能差異太大保證搜索是有序而非隨機的搜索。鄰域解的規(guī)模,也并不總是取可產(chǎn)生鄰域解個數(shù)的上限,可以根據(jù)需要和經(jīng)驗設(shè)定成小于上限的值,以提高搜索的運行效率?！　?.3解的評價函數(shù)　　解的評價函數(shù),相關(guān)文獻又稱其為適應(yīng)值函數(shù)、適配值函數(shù)或適應(yīng)度函數(shù)。對于禁忌搜索空間中的解,通過評價函數(shù)來計算其對應(yīng)的評價函數(shù)值,評價函數(shù)值的大小代表了解的優(yōu)劣