禁忌搜索算法評述

《禁忌搜索算法評述 》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。

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

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

3、和多樣性。TS算法是一種具有不同于遺傳和模擬退火等算法特點的智能隨機算法,可以克服搜索過程易于早熟收斂的缺陷而達到全局優(yōu)化[1]?！　∑駷橹?TS算法已經廣泛應用于組合優(yōu)化、機器學習、生產調度、函數(shù)優(yōu)化、電路設計、路由優(yōu)化、投資分析和神經網(wǎng)絡等領域,并顯示出極好的研究前景[2~9,11~15]。目前關于TS的研究主要分為對TS算法過程和關鍵步驟的改進,用TS改進已有優(yōu)化算法和應用TS相關算法求解工程優(yōu)化問題三個方面。　　禁忌搜索提出了一種基于智能記憶的框架,在實際實現(xiàn)過程中可以根據(jù)問題的性質做有針對性的設計,本

4、文在給出禁忌搜索基本流程的基礎上,對如何設計算法中的關鍵步驟進行了有益的總結和分析。　　2禁忌搜索算法的基本流程　　TS算法一般流程描述[1]:　　(1)設定算法參數(shù),產生初始解x,置空禁忌表?！　?2)判斷是否滿足終止條件?若是,則結束,并輸出結果;否則,繼續(xù)以下步驟?！　?3)利用當前解x的鄰域結構產生鄰域解,并從中確定若干候選解?！　?4)對候選解判斷是否滿足藐視準則?若成立,則用滿足藐視準則的最佳狀態(tài)y替代x成為新的當前解,并用y對應的禁忌對象替換最早進入禁忌表的禁忌對象,同時用y替換“bestsofar

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

6、而定。二進制編碼將問題的解用一個二進制串來表示[2],十進制編碼將問題的解用一個十進制串來表示[3],實數(shù)編碼將問題的解用一個實數(shù)來表示[4],在某些組合優(yōu)化問題中,還經常使用混合編碼[5]、0-1矩陣編碼等?！　〗伤阉鲗Τ跏冀獾囊蕾囕^大,好的初始解往往會提高最終的優(yōu)化效果。初始解的構造可以隨機產生,但效果往往不夠理想,通常是基于問題特征信息,借助一些啟發(fā)式方法產生,以保證初始解的性能?！　?.2鄰域移動、鄰域解及鄰域解規(guī)?！　∴徲蛞苿?相關文獻也稱作鄰域操作、鄰域結構、鄰域變換等。禁忌搜索要想不斷進行就要依賴

7、鄰域移動來不斷拓展搜索空間,鄰域移動是在當前解的基礎上,按照特定的移動策略產生一定數(shù)目的新解,這些新解被稱為鄰域解,新解的數(shù)目稱為鄰域解規(guī)模。鄰域移動的設計通常與問題有關,如排列置換類組合優(yōu)化問題,常用的鄰域移動方法是交換、插入、逆序等[3,6,7,8]。不同的移動將導致鄰域解個數(shù)及其變化情況的不同,進而影響搜索的質量和效率。在一些應用中為了取得好的搜索效果,會根據(jù)搜索的進展情況動態(tài)改變鄰域移動策略,即變鄰域移動[9]。鄰域移動的設計策略既要保證變化的有效性還要保證變化的平滑性,即產生的鄰域解和當前解既有不同,又

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