禁忌搜索(Tabu search,Ts)算法的思想最早由Glover在1986提出,它是對(duì)局部鄰域搜索的一種擴(kuò)展, LPO2506I-682LC是一種全局逐步尋優(yōu)算法,是對(duì)人類智力過程的一種模擬。TS算法通過引入靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來避免迂回搜索,并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài),進(jìn)而保證多樣化,以實(shí)現(xiàn)全局優(yōu)化。Ts算法最重要的思想是標(biāo)記對(duì)應(yīng)已搜索的局部最優(yōu)解的一些對(duì)象,并在進(jìn)一步的迭代搜索中盡量避開這些對(duì)象(而不是絕對(duì)禁止循環(huán)),從而保證對(duì)不同的有效搜索途徑的探索。在Ts算法中,首先按照隨機(jī)方法產(chǎn)生一個(gè)初始解作為當(dāng)前解,然后在當(dāng)前解的鄰域中搜索若干個(gè)解,取其中的最優(yōu)解作為新的當(dāng)前解。為了避免陷入局部最優(yōu)解,這種優(yōu)化方法允許一定的下山操作(使解的質(zhì)量變差)。另外,為了避免對(duì)已搜索過的局部最優(yōu)解的重復(fù),TS算法使用禁忌表記錄已搜索的局部最優(yōu)解的歷史信息,這在一定程度上使搜索過程避開局部極值點(diǎn),從而開辟新 的搜索區(qū)域。Ts算法的流程圖如圖3-10所示。