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

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

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

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