禁忌搜索和應(yīng)用

目錄TOC\o"1-3"\h\u13630一、摘要 212316二、禁忌搜索簡介 24311三、禁忌搜索的應(yīng)用 277661、現(xiàn)實情況 2152852、車輛路徑問題的描述 3212933、算法思路 3149684、具體步驟 3179675、程序設(shè)計簡介 3159246、算例分析 49432四、禁忌搜索算法的評述和展望 425672五、參考文獻(xiàn) 5禁忌搜索及應(yīng)用摘要工程應(yīng)用中存在大量的優(yōu)化問題,對優(yōu)化算法的研究是目前研究的熱點之一。禁忌搜索算法作為一種新興的智能搜索算法具有模擬人類智能的記憶機(jī)制,已被廣泛應(yīng)用于各類優(yōu)化領(lǐng)域并取得了理想的效果。本文介紹了禁忌搜索算法的特點、應(yīng)用領(lǐng)域、研究進(jìn)展,概述了它的算法基本流程,評述了算法設(shè)計過程中的關(guān)鍵要點,最后探討了禁忌搜索算法的研究方向和發(fā)展趨勢。二、禁忌搜索簡介禁忌搜索（TabuSearch或TabooSearch，簡稱TS）的思想最早由Glover(1986)提出，它是對局部領(lǐng)域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)算法，是對人類智力過程的一種模擬。TS算法通過引入一個靈活的存儲結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來避免迂回搜索，并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效探索以最終實現(xiàn)全局優(yōu)化。相對于模擬退火和遺傳算法，TS是又一種搜索特點不同的meta-heuristic算法。迄今為止，TS算法在組合優(yōu)化、生產(chǎn)調(diào)度、機(jī)器學(xué)習(xí)、電路設(shè)計和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域取得了很大的成功，近年來又在函數(shù)全局優(yōu)化方面得到較多的研究，并大有發(fā)展的趨勢。禁忌搜索是人工智能的一種體現(xiàn)，是局部領(lǐng)域搜索的一種擴(kuò)展。禁忌搜索最重要的思想是標(biāo)記對應(yīng)已搜索的局部最優(yōu)解的一些對象，并在進(jìn)一步的迭代搜索中盡量避開這些對象（而不是絕對禁止循環(huán)），從而保證對不同的有效搜索途徑的探索。禁忌搜索涉及到鄰域（neighborhood）、禁忌表（tabulist）、禁忌長度（tabulength）、候選解（candidate）、藐視準(zhǔn)則（aspirationcriterion）等概念。三、禁忌搜索的應(yīng)用禁忌搜索應(yīng)用的領(lǐng)域多種多樣，下面我們簡單的介紹下基于禁忌搜索算法的車輛路徑選擇。現(xiàn)實情況物流配送過程的成本構(gòu)成中，運輸成本占到52%之多，如何安排運輸車輛的行駛路徑，使得配送車輛依照最短行駛路徑或最短時間費用，在滿足服務(wù)時間限制、車輛容量限制、行駛里程限制等約束條件下，依次服務(wù)于每個客戶后返回起點，實現(xiàn)總運輸成本的最小化，車輛路徑問題正是基于這一需求而產(chǎn)生的。求解車輛路徑問題（vehicleroutingproblem簡記vrp）的方法分為精確算法與啟發(fā)式算法，精確算法隨問題規(guī)模的增大，時間復(fù)雜度與空間復(fù)雜度呈指數(shù)增長，且vrp問題屬于np-hard問題，求解比較困難，因此啟發(fā)式算法成為求解vrp問題的主要方法。禁忌搜索算法是啟發(fā)式算法的一種，為求解vrp提供了新的工具。本文通過一種客戶直接排列的解的表示方法，設(shè)計了一種求解車輛路徑問題的新的禁忌搜索算法。因此研究車輛路徑問題，就是要研究如何安排運輸車輛的行駛路線，使運輸車輛依照最短的行駛路徑或最短的時間費用，依次服務(wù)于每個客戶后返回起點，總的運輸成本實現(xiàn)最小。車輛路徑問題的描述車輛路徑問題的研究目標(biāo)是對一系列送貨點或取貨點，確定適當(dāng)?shù)呐渌蛙囕v行駛路線，使車輛有序地通過它們，在滿足一定的約束條件（如貨物需求量、發(fā)送量交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等）下，達(dá)到一定的目標(biāo)（如路程最短、費用最小、時間盡量少、使用車輛盡量少等)。參見下圖2.1所示：其中0表示配送中心，1～８表示客戶編號。在本文中為使得問題易于理解，將該問題描述為：有一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，且每個客戶的位置和需求量一定，一個物流中心提供這些貨物，并有一個車隊負(fù)責(zé)分送貨物，每臺配送車輛的載重量一定，這里假設(shè)車輛的型號一致，即最大載重量和最遠(yuǎn)行駛里程數(shù)相同，要求合理安排車輛配送路線，使配送總路程最短，同時得滿足一定的約束條件，即每條路線總需求量之和不得超過配送車輛的載重量、每條路線行駛的里程數(shù)不得超過配送車輛的最遠(yuǎn)里程數(shù)、每一客戶需求必須滿足且僅由一臺車輛配送。算法思路本文先用插入式啟發(fā)算法得到車輛路徑問題的初始可行解，再利用禁忌搜索算法對初始解進(jìn)行改造。4、具體步驟（1）構(gòu)造初始解時，先用客戶直接排列的解的表示方法，隨機(jī)生成某一不重復(fù)的客戶排列序列，然后按照車輛路徑問題的約束條件，依次將解的元素（客戶）劃入各條配送路徑中，由此產(chǎn)生車輛路徑問題的初始解，計算出當(dāng)前解的目標(biāo)函數(shù)值，這里的目標(biāo)函數(shù)值為各車輛配送路徑的里程數(shù)總和。（2）通過隨機(jī)交換兩客戶位置來生成當(dāng)前解的鄰域解，則有c2n=n*(n-1)/2個客戶直接排列序列，然后按照車輛路徑問題的約束條件,依次將解的元素（客戶）劃入各條配送路徑中，由此計算出各鄰域解的目標(biāo)函數(shù)值。（3）根據(jù)藐視準(zhǔn)則來評價當(dāng)前解的鄰域解，更新當(dāng)前解與禁忌表。若候選解的目標(biāo)值優(yōu)于當(dāng)前的最優(yōu)目標(biāo)值，不管其禁忌屬性如何，更新為當(dāng)前最優(yōu)解并更新禁忌表，否則判別該方案的兩個客戶交換是否被禁忌：若被禁忌，選取次優(yōu)解后繼續(xù)該步驟；若未被禁忌，更新該解為當(dāng)前解并更新禁忌表。（4）若所有的候選對象均被禁忌，則根據(jù)隊列fifo原則，對禁忌表中隊頭元素取消其禁忌屬性；禁忌表的更新為將其中所有的禁忌對象的禁忌長度減1，禁忌長度為0的對象取消其禁忌屬性。（5）重復(fù)迭代指定步長的（2）～（4），輸出車輛配送方案的最終結(jié)果。5、程序設(shè)計簡介算法中，無論是初始解的構(gòu)造還是鄰域內(nèi)尋優(yōu)，都涉及到對大量配送點進(jìn)行的操作，如構(gòu)造初始解時，針對車輛路徑問題的約束條件將客戶劃分到不同的路徑中；更新禁忌表時的將禁忌對象放入表中以及滿足藐視準(zhǔn)則時的禁忌對象的解禁。程序中針對該問題，采用了隊列的形式，通過改進(jìn)的隊列基本操作來實現(xiàn)路徑的分配與禁忌表的更新問題。下面給出定義的幾個結(jié)構(gòu)體：（1）客戶位置的無重復(fù)隨機(jī)生成以及客戶需求量的隨機(jī)生成實際配送系統(tǒng)中的客戶的地理位置相對獨立，且彼此之間服從獨立均勻分布，為簡易起見，程序中對客戶的地理位置分布與客戶的需求量只簡單地使用c語言中的rand()函數(shù)進(jìn)行隨機(jī)分配，其中物流中心的地理位置默認(rèn)為（0，0），為了保證生成的客戶位置沒有重復(fù)，用c_location[j].x==c_location[i].x&&c_location[j].y==c_location[i].y語句來判定，其中c_location數(shù)組采用cpoint結(jié)構(gòu)體，用于存儲客戶的位置，demand數(shù)組用于存儲客戶需求量，這兩個數(shù)組均被定義為全局變量。（2）客戶隨機(jī)序列的生成算法中采用客戶直接排列的解的表示方式，隨機(jī)生成初始解，即無重復(fù)的客戶隨機(jī)排列序列數(shù)組a。（3）初始解的車輛路徑分配將客戶隨機(jī)序列數(shù)組a中的各個值賦值到i_now數(shù)組中，i_now數(shù)組用于記錄當(dāng)前的最優(yōu)解，定義車輛的最大負(fù)載量vehicle_max，這里假設(shè)物流中心車輛的型號一致并且不考慮車輛的最大行駛距離。（4）當(dāng)前解的鄰域結(jié)構(gòu)通過依次交換兩客戶位置來生成當(dāng)前解的鄰域解，則有c2n=n*(n-1)/2個客戶直接排列序列。i_now的鄰域解，用數(shù)組exchange_solution記錄。用與初始分配方案相似的算法，可以求出exchange_solution數(shù)組中每一個車輛分配路線的車輛數(shù)以及車輛所行駛的總里程數(shù)，分別記錄到數(shù)組n_num和s中。（5）尋找當(dāng)前解鄰域結(jié)構(gòu)的評價值最優(yōu)方案先從數(shù)組s中尋找到車輛行駛里程數(shù)最短的方案，記其下標(biāo)為ibest，判斷該方案是由當(dāng)前解的哪兩個客戶交換得到的，記作i_x和i_y。根據(jù)禁忌準(zhǔn)則對該局部最優(yōu)解進(jìn)行處理，可以替換為當(dāng)前最優(yōu)解的條件有二：(1)這兩個元素的交換是可行的、未被禁忌的；(2)其解優(yōu)于當(dāng)前解，不管其是否禁忌均替換當(dāng)前最優(yōu)解，更新禁忌表，將禁忌表中各禁忌對象的禁忌步長減1，當(dāng)禁忌步長為0時，取消禁忌對象的禁忌屬性，而當(dāng)替換方案中的所有對象均被禁忌后，根據(jù)fifo原則，取消隊頭元素的禁忌屬性。算例分析這里用microsoftvisualc++對車輛路徑問題的禁忌搜索算法進(jìn)行編程，通過對相對獨立的隨機(jī)分布在（0，100]平方公里范圍內(nèi)的指定客戶數(shù)、且客戶的需求為的（0，指定的客戶數(shù)]范圍內(nèi)的隨機(jī)數(shù)的vrp實例進(jìn)行求解，進(jìn)行了實驗計算。設(shè)在某物流中心有10臺配送車輛，車輛的最大載重量均為10單位，在不考慮車輛一次配送的最大行駛距離的情況下，需要向10個客戶運送貨物，作者利用計算機(jī)隨機(jī)產(chǎn)生了范圍在0～100內(nèi)的10個客戶的位置坐標(biāo)（坐標(biāo)無重復(fù)情況）以及客戶的貨物需求量，其中物流中心的坐標(biāo)默認(rèn)為（0，0），各個客戶的坐標(biāo)位置與需求量如下圖2.3所示，要求合理安排配送車輛的行車路徑，使配送的總里程數(shù)最短。為簡便起見，本文設(shè)各客戶相互之間及物流中心與客戶之間的距離均采用直線距離，該距離可根據(jù)客戶和物流中心的坐標(biāo)計算得到。本文基于車輛路徑問題的簡單描述，采用客戶直接排列的解的表示方法，相比較現(xiàn)有研究成果將車輛路徑問題描述為網(wǎng)絡(luò)圖問題的有向邊排列方法，表示更加直觀、算法策略更加簡單并易于理解，而且算法在迭代過程中產(chǎn)生的解均為可行解，算法的收斂速度得到明顯改善。實驗的計算結(jié)果表明，用禁忌搜索算法求解車輛路徑問題能夠跳出局部最優(yōu)解，實現(xiàn)全局最優(yōu)化，所得到的最終解決方案相比較初始方案質(zhì)量更優(yōu)，尋優(yōu)性能良好。四、禁忌搜索算法的評述和展望禁忌搜索算法作為一種新興的智能搜索算法具有模擬人類智能的記憶機(jī)制,已被廣泛應(yīng)用于各類優(yōu)化領(lǐng)域并取得了理想的效果。本文簡述了禁忌搜索算法的發(fā)展、特點及應(yīng)用,給出了基本禁忌搜索算法實現(xiàn)的流程,對禁忌搜索設(shè)計過程中的關(guān)鍵步驟進(jìn)行了分析和總結(jié),為推廣禁忌搜索算法在優(yōu)化領(lǐng)域的應(yīng)用有一定意義。今后關(guān)于禁忌搜索算法的研究熱點主要有以下幾個方面。(1)與其他優(yōu)化算法結(jié)合,如與傳統(tǒng)啟發(fā)式算法、遺傳算法、模擬退火算法、粒子群算法、神經(jīng)網(wǎng)絡(luò)算法、蟻群算法、混沌算法等結(jié)合,構(gòu)成更新型的混合優(yōu)化算法。(2)為推廣禁忌搜索算法在超大規(guī)模優(yōu)化領(lǐng)域中的應(yīng)用,突破禁忌搜索的串行性限制,研究并行禁忌搜索算法。包括基于問題空間分解的并行策略和基于多禁忌搜索任務(wù)的并行策略。五、參考文獻(xiàn)[1]王凌.智能優(yōu)化算法及其應(yīng)用[M].北京:清華大學(xué)出版社,2001.[2]李新振,騰歡.自適應(yīng)遺傳——禁忌搜索混合算法在PMU最優(yōu)配置中的應(yīng)用[J].四川電力技術(shù),2009,32(3):56-60.[3]劉嘉敏,董宗然,馬廣焜.基于禁忌搜索算法求解集裝箱裝載問題[J].沈陽工業(yè)大學(xué)學(xué)報,2009,31(2):212-216.[4]王竹芳,潘德惠.用遺傳:禁忌搜索混合算法求解組合投資問題[J].東北大學(xué)學(xué)報(自然科學(xué)版),2006,27(1):111-114.[5]肖麗,劉光遠(yuǎn),賀一等.基于禁忌搜索的模糊神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化[J].計算機(jī)科學(xué),2006,33(7):217-219.[6]宋曉宇,孟秋宏,曹陽.求解JobShop調(diào)度問題的改進(jìn)禁忌搜索算法[J].信息工程與電子技術(shù),2008,30(1):94-96.[7]黃志,黃文奇.一種基于禁忌搜索的作業(yè)車間調(diào)度算法[J].計算機(jī)工程與應(yīng)用,2006,42(3):12-14.[8]段鳳華,符卓.有軟時窗約束帶取送作業(yè)的車輛路徑問題及其禁忌搜索算法研究[J].計算機(jī)工程與科學(xué),2009,31(3):68-70.[9]汪翼,孫林巖,李剛,等.集裝箱車輛調(diào)度問題的變鄰域禁忌搜索算法[J].工業(yè)工程與管理,2008,13(5):6-10.[10]孫艷豐,鄭加齊,王德興,等.基于遺傳算法的約束優(yōu)化方法評述[J].北方交通大學(xué)學(xué)報,2000,24(6):14-19.[11]陳年生,李臘元,董武世,等.基于禁忌搜索的QoS路由算法[J].計算機(jī)工程與應(yīng)用,2005,41(8):134