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

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

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

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

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