隨機(jī)局部搜索算法及其應(yīng)用研究.pdf

1、隨機(jī)局部搜索算法是一種解決計(jì)算機(jī)科學(xué)和運(yùn)籌學(xué)領(lǐng)域中組合最優(yōu)化問題的元啟發(fā)式方法。近年來，由于其簡單、高效的特點(diǎn)而得到越來越多的應(yīng)用。本論文中，我們對(duì)隨機(jī)局部搜索算法進(jìn)行研究，展示了根據(jù)具體問題的特點(diǎn)來設(shè)計(jì)算法的過程。更具體地講，我們選擇集合覆蓋問題作為我們的主要研究目標(biāo)，主要的工作和貢獻(xiàn)有:
　　1.設(shè)計(jì)一個(gè)新的適用于集合覆蓋問題的隨機(jī)局部搜索算法叫做行加權(quán)局部搜索算法（RWLS: Row Weighting Local Sear

2、ch），它具有以下特點(diǎn)1）一個(gè)擾動(dòng)搜索的框架，該框架由兩個(gè)操作函數(shù)（ADD和REMOVE）實(shí)現(xiàn);2）多種禁忌策略來避免搜索的重復(fù)和循環(huán)，包括時(shí)間戳的方法，禁忌表和布爾狀態(tài)檢查的策略;3）一個(gè)權(quán)值調(diào)整的策略來幫助算法跳出局部最優(yōu)。我們對(duì)RWLS和文獻(xiàn)中最好的方法進(jìn)行了比較，在OR-Library上的80個(gè)實(shí)例上的比較結(jié)果顯示RWLS一共更新了14個(gè)已知最好的解，并且在剩下的66實(shí)例上都能夠達(dá)到已知的最好結(jié)果。在7個(gè)超大規(guī)模的鐵路調(diào)度實(shí)例上