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

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

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

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

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