基于節(jié)約算法和移動方向的禁忌搜索算法.pdf

1、隨著優(yōu)化算法和啟發(fā)式算法的提出，國內(nèi)外掀起了研究智能優(yōu)化算法的熱潮。禁忌搜索是一種新的智能優(yōu)化算法，是由美國科學(xué)家Glovr教授于1986年正式提出。禁忌搜索(TS)在智能算法中獨樹一幟，成為一個研究熱點，受到了國內(nèi)外學(xué)者的廣泛關(guān)注，并應(yīng)用到組合優(yōu)化和函數(shù)優(yōu)化問題中。本文基于原禁忌搜索的思想提出一種改進的禁忌搜索算法，并把這種改進算法應(yīng)用到實際問題中。
　　 在前期工作的基礎(chǔ)上，本文主要的工作包括針對禁忌搜索算法對初始解依賴性強

2、的缺點，利用c-w節(jié)約算法得到初始解。禁忌搜索算法設(shè)計的框架中初始解尤為關(guān)鍵，初始解的好壞制約著搜索的收斂速度。通過c-w節(jié)約算法得到高質(zhì)量解，構(gòu)造算法新的搜索起點，加強了集中性搜索力度。在仿真實驗中驗證了其有效性。
　　 同時針對禁忌搜索算法中集中性與多樣性搜索并重的情況下，多樣性不足的缺點，從下面兩個方面改進算法，拓寬搜索領(lǐng)域，加強多樣性搜索，增加靈活性。通過改進禁忌表存儲結(jié)構(gòu)，定義優(yōu)質(zhì)解和劣質(zhì)解的出現(xiàn)次數(shù)這兩個概念，不只利

3、用禁忌表禁忌最近的搜索，還記錄這些移動是否有所改進，記錄下改進的信息，表明新解的改變程度，在搜索決策中并入這些信息，使得搜索往利于改進的方向進行。T S中確定性的搜索過程制約了它的靈活性，所以在禁忌搜索原則確定的基礎(chǔ)上，根據(jù)搜索中的移動信息，增加概率性因素，在評價函數(shù)中增加一個概率函數(shù)，把確定性選擇過程變?yōu)楦怕市缘?，從而改進搜索方向，拓寬搜索領(lǐng)域，使得更好的解有更大的被選中的機會。
　　 旅行商問題(TSP)是典型的組合優(yōu)化難題