2023年數(shù)學(xué)建模美賽備戰(zhàn)參考—禁忌搜索算法 禁忌搜索算法是組合優(yōu)化算法的一種，是局部搜索算法的擴(kuò)展。禁忌搜索算法是人工智能在組合優(yōu)化算法中的一個(gè)成功應(yīng)用。禁忌搜索算法的特點(diǎn)是采用了禁忌技術(shù)。所謂禁忌就是禁止重復(fù)前面的工作。禁忌搜索算法用一個(gè)禁忌表記錄下已經(jīng)到達(dá)過(guò)的局部最優(yōu)點(diǎn)，在下一次搜索中，利用禁忌表中的信息不再或有選擇地搜索這些點(diǎn)。? 禁忌搜索算法實(shí)現(xiàn)的技術(shù)問(wèn)題是算法的關(guān)鍵。禁忌搜索算法涉及侯選集合、禁忌對(duì)象、評(píng)價(jià)函數(shù)、特赦規(guī)則、記憶頻率信息等概念。 評(píng)價(jià)函數(shù)是侯選集合元素選取的一個(gè)評(píng)價(jià)公式，侯選集合的元素通過(guò)評(píng)價(jià)函數(shù)值來(lái)選取。以目標(biāo)函數(shù)作為評(píng)價(jià)函數(shù)是比較容易理解的。目標(biāo)值是一個(gè)非常直觀的指標(biāo)，但有時(shí)為了方便或易于計(jì)算，會(huì)采用其他函數(shù)來(lái)取代目標(biāo)函數(shù)。 在禁忌搜索算法的迭代過(guò)程中，會(huì)出現(xiàn)侯選集中的全部對(duì)象都被禁忌，或有一對(duì)象被禁，但若解禁則其目標(biāo)值將有非常大的下降情況。在這樣的情況下，為了達(dá)到全局最優(yōu)，我們會(huì)讓一些禁忌對(duì)象重新可選。這種方法稱為特赦，相應(yīng)的規(guī)則稱為特赦規(guī)則。 在計(jì)算的過(guò)程中，記憶一些信息對(duì)解決問(wèn)題是有利的。如一個(gè)最好的目標(biāo)值出現(xiàn)的頻率很高，這使我們有理由推測(cè)：現(xiàn)有參數(shù)的算法可能無(wú)法再得到更好的解。根據(jù)解決問(wèn)題的需要，我們可以記憶解集合、被禁對(duì)象組、目標(biāo)值集合等的出現(xiàn)頻率。頻率信息有助于進(jìn)一步加強(qiáng)禁忌搜索的效率。我們可以根據(jù)頻率信息動(dòng)態(tài)控制禁忌的長(zhǎng)度。一個(gè)最佳的目標(biāo)值出現(xiàn)的頻率很高，有理由終止計(jì)算而將此值認(rèn)為是最優(yōu)值。