禁忌搜索及其并行化研究.pdf

1、禁忌搜索（Tabu Search或Taboo Search，TS）是一種新的智能優(yōu)化算法，由美國科羅拉多大學(xué)系統(tǒng)科學(xué)家Glover教授于1986年正式提出。TS與模擬退火（SA）、進化計算（EC）、蟻群算法（ACS）、粒子群優(yōu)化（PSO）、人工免疫系統(tǒng)（AJS）等一樣，都屬于自然計算（Natural Computation，NC）的研究范疇。TS以其靈活的存儲結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來避免迂回搜索，在智能優(yōu)化算法中獨樹一幟，受到了自然計算領(lǐng)

2、域?qū)W者的廣泛關(guān)注，在組合優(yōu)化及函數(shù)優(yōu)化領(lǐng)域中得到了廣泛的應(yīng)用。 本文在前人成果及前期工作的基礎(chǔ)上，重點研究了禁忌搜索在TSP問題、前向神經(jīng)網(wǎng)絡(luò)和多維背包問題中的應(yīng)用，并就如何實現(xiàn)禁忌搜索的并行化提出了三種并行策略，論文的主要創(chuàng)新點可以歸納如下： （1）針對禁忌搜索中集中性搜索與多樣性搜索之間的矛盾，提出了一種自適應(yīng)搜索策略。該策略將鄰域中的元素劃分為兩部分，即集中性元素和多樣性元素，分別用于集中性搜索和多樣性搜索，然后根

3、據(jù)搜索的進程，自適應(yīng)地調(diào)整候選集中的集中性元素與多樣性元素的數(shù)量，以協(xié)調(diào)此矛盾。以TSP問題為例做了仿真實驗，結(jié)果顯示，該策略具有框架靈活、通用性較強、與具體問題無關(guān)等優(yōu)點，可推廣應(yīng)用于其它問題的求解。與神經(jīng)網(wǎng)絡(luò)方法的對比顯示，基于該策略的禁忌搜索算法具有更高的求解質(zhì)量。 （2）針對前向神經(jīng)網(wǎng)絡(luò)中BP算法的不足，提出了一種前向神經(jīng)網(wǎng)絡(luò)的自適應(yīng)禁忌搜索訓(xùn)練算法，主要解決了如何實現(xiàn)連續(xù)變化函數(shù)值的禁忌操作、上述集中性與多樣性的自適應(yīng)

4、搜索策略的推廣應(yīng)用等關(guān)鍵問題。該算法具有全局尋優(yōu)、訓(xùn)練精度高、收斂速度快等優(yōu)點，以異或問題和函數(shù)逼近問題為例進行了仿真實驗，并與BP算法進行了對比，結(jié)果顯示該算法具有較高的性能。 （3）借鑒認(rèn)知認(rèn)心理學(xué)中關(guān)于記憶系統(tǒng)的研究成果，在禁忌搜索中引入長時記憶機制，提出了一種基于雙禁忌表的禁忌搜索算法，并成功應(yīng)用于多維背包問題的求解。做了大量的仿真實驗，并與克隆選擇算法進行了對比，結(jié)果顯示該算法具有求解質(zhì)量高、收斂速度快等優(yōu)點。