|
禁忌搜索算法評(píng)述
（作者未知） 2011/6/23
（接上頁(yè)）根據(jù)需要和經(jīng)驗(yàn)設(shè)定成小于上限的值,以提高搜索的運(yùn)行效率。
3.3 解的評(píng)價(jià)函數(shù)
解的評(píng)價(jià)函數(shù),相關(guān)文獻(xiàn)又稱其為適應(yīng)值函數(shù)、適配值函數(shù)或適應(yīng)度函數(shù)。對(duì)于禁忌搜索空間中的解,通過(guò)評(píng)價(jià)函數(shù)來(lái)計(jì)算其對(duì)應(yīng)的評(píng)價(jià)函數(shù)值,評(píng)價(jià)函數(shù)值的大小代表了解的優(yōu)劣程度。根據(jù)問(wèn)題的特性,可能評(píng)價(jià)函數(shù)值越大越好,反之也可能越小越好。依據(jù)數(shù)學(xué)方法,兩種目標(biāo)可以等價(jià)轉(zhuǎn)換。直接把優(yōu)化目標(biāo)作為評(píng)價(jià)函數(shù)是一種簡(jiǎn)單、直觀的方法,同時(shí)任何與優(yōu)化目標(biāo)等價(jià)的變換函數(shù)也可以作為評(píng)價(jià)函數(shù)。有時(shí),目標(biāo)函數(shù)的計(jì)算困難或是耗時(shí)較多,則可以取體現(xiàn)問(wèn)題目標(biāo)的特征值來(lái)替代計(jì)算,但必須要保證特征值與問(wèn)題目標(biāo)有一致的最優(yōu)性。
與遺傳算法的評(píng)價(jià)函數(shù)類似,在求解帶有約束的優(yōu)化問(wèn)題時(shí),可以將解違反約束的情況作為懲罰因子加入評(píng)價(jià)函數(shù),從而規(guī)避傳統(tǒng)啟發(fā)式方法中對(duì)于約束的復(fù)雜處理。基本形式如公式(1)。
其中,P(Rj,x)為第j個(gè)約束的懲罰值,當(dāng)解滿足約束時(shí),懲罰值為0。關(guān)于評(píng)價(jià)函數(shù)的設(shè)計(jì)詳見(jiàn)文獻(xiàn)[10]。
3.4 禁忌表、禁忌對(duì)象、禁忌長(zhǎng)度、候選解及禁忌頻率
禁忌表是用來(lái)存放禁忌對(duì)象的一個(gè)容器,被放入禁忌表中的禁忌對(duì)象在解禁之前不能被再次搜索,可見(jiàn)禁忌表模擬了人的記憶機(jī)制,防止搜索陷入局部最優(yōu),進(jìn)而探索更多的搜索空間。禁忌表可以使用數(shù)組、隊(duì)列、棧、鏈表等順序結(jié)構(gòu)實(shí)現(xiàn),每個(gè)順序結(jié)構(gòu)的元素定義根據(jù)具體問(wèn)題確定。
禁忌對(duì)象就是放入禁忌表中的元素,歸納而言,禁忌對(duì)象通�？蛇x取狀態(tài)(解的編碼)本身或狀態(tài)分量或適配值的變化等,禁忌范圍依次擴(kuò)大[1]。其中選取狀態(tài)本身易于理解,也最為常用,禁忌范圍最小。
禁忌長(zhǎng)度就是每個(gè)禁忌對(duì)象在禁忌表中的生存時(shí)間,也稱為禁忌對(duì)象的任期。當(dāng)一個(gè)禁忌對(duì)象加入禁忌表時(shí),設(shè)置其任期為禁忌長(zhǎng)度值,搜索過(guò)程每迭代一次,禁忌表中的各禁忌對(duì)象的任期自動(dòng)減1,當(dāng)某一禁忌對(duì)象任期為0時(shí),將其從禁忌表中刪除。任期不為0的禁忌對(duì)象處于禁忌狀態(tài),不能被搜索過(guò)程選為新解。
候選解是當(dāng)前解鄰域解集的一個(gè)子集。搜索中為了減少搜索的代價(jià)(包括空間和時(shí)間),要求禁忌長(zhǎng)度和候選解集盡量小,但禁忌長(zhǎng)度過(guò)小將使搜索無(wú)法跳出局部最小,候選解集過(guò)小將使搜索早熟收斂。候選解集的大小常根據(jù)問(wèn)題特性和對(duì)算法的要求確定,禁忌長(zhǎng)度的選取則主要有靜態(tài)和動(dòng)態(tài)兩種方法。靜態(tài)方法是指在搜索過(guò)程中,禁忌長(zhǎng)度是一個(gè)固定值,比如,其中n為問(wèn)題維數(shù)或規(guī)模。動(dòng)態(tài)方法是指在搜索過(guò)程中,禁忌長(zhǎng)度也是動(dòng)態(tài)變化的,當(dāng)算法搜索能力較強(qiáng)時(shí),可以增大禁忌長(zhǎng)度從而延續(xù)當(dāng)前的搜索能力,并避免搜索陷入局部?jī)?yōu)解,反之亦然。
禁忌頻率記錄每個(gè)禁忌對(duì)象出現(xiàn)在禁忌表中的次數(shù),以此作為搜索過(guò)程的重要參考,如若某個(gè)對(duì)象出現(xiàn)頻繁,則可以增加禁忌長(zhǎng)度來(lái)避免循環(huán)。此外可以把某對(duì)象的禁忌頻率作為評(píng)價(jià)解的因素加入評(píng)價(jià)函數(shù)來(lái)指導(dǎo)搜索過(guò)程。
3.5 特赦準(zhǔn)則
特赦準(zhǔn)則,相關(guān)文獻(xiàn)也稱為藐視準(zhǔn)則、破禁準(zhǔn)則[11]、釋放準(zhǔn)則等。特赦準(zhǔn)則保證了搜索過(guò)程在全部候選解被禁或是有優(yōu)于當(dāng)前最優(yōu)解的候選解(或狀態(tài))被禁時(shí),能夠釋放特定解(或狀態(tài)),從而實(shí)現(xiàn)高效的全局優(yōu)化搜索。
3.6 終止準(zhǔn)則
終止準(zhǔn)則也稱停止準(zhǔn)則,即算法在何條件下停止搜索過(guò)程。實(shí)際應(yīng)用中無(wú)法使用在禁忌長(zhǎng)度充分大的條件下實(shí)現(xiàn)狀態(tài)空間的遍歷這一理論收斂條件,往往使用如下近似終止(收斂)準(zhǔn)則。
(1)算法迭代次數(shù)達(dá)到指定最大次數(shù)停止[8,11]。
(2)最優(yōu)解的目標(biāo)函數(shù)值小于指定誤差。
(3)最優(yōu)解的禁忌頻率達(dá)到指定值。
4 總結(jié)和展望
本文簡(jiǎn)述了禁忌搜索算法的發(fā)展、特點(diǎn)及應(yīng)用,給出了基本禁忌搜索算法實(shí)現(xiàn)的流程,對(duì)禁忌搜索設(shè)計(jì)過(guò)程中的關(guān)鍵步驟進(jìn)行了分析和總結(jié),為推廣禁忌搜索算法在優(yōu)化領(lǐng)域的應(yīng)用有一定意義。
今后關(guān)于禁忌搜索算法的研究熱點(diǎn)主要有以下幾個(gè)方面。
(1)與其他優(yōu)化算法結(jié)合,如與傳統(tǒng)啟發(fā)式算法、遺傳算法、模擬退火算法、粒子群算法、神經(jīng)網(wǎng)絡(luò)算法、蟻群算法、混沌算法等結(jié)合,構(gòu)成更新型的混合優(yōu)化算法[2,4,5,12~15]。
(2)為推廣禁忌搜索算法在超大規(guī)模優(yōu)化領(lǐng)域中的應(yīng)用,突破禁忌搜索的串行性限制,研究并行禁忌搜索算法。包括基于問(wèn)題空間分解的并行策略和基于多禁忌搜索任務(wù)的并行策略[1]。
(3)對(duì)禁忌搜索算法本身的關(guān)鍵步驟進(jìn)行改良設(shè)計(jì)。如根據(jù)禁忌頻率信息在算法中增加集中搜索和分散搜索,分別實(shí)現(xiàn)優(yōu)良區(qū)域的重點(diǎn)搜索和搜索范圍的擴(kuò)展。
(4)探索禁忌搜索算法適于應(yīng)用的新的優(yōu)化領(lǐng)域。
進(jìn)一步研究禁忌搜索算法中相（未完，下一頁(yè)）
|