禁忌搜索算法

1、 tabu search *禁忌搜索算法測控二班 高釗政 201424080217禁忌搜索禁忌搜索 禁忌搜索概述 禁忌搜索的主要思路 禁忌搜索的流程 栗子禁忌搜索算法概述 禁忌禁止重復(fù)前面的操作 禁忌搜索（Tabu Search）算法是一種亞啟發(fā)式(meta-heuristic)隨機(jī)搜索算法，它從一個(gè)初始可行解出發(fā)，選擇一系列的特定搜索方向(移動)作為試探，選擇實(shí)現(xiàn)讓特定的目標(biāo)函數(shù)值變化最多的移動。為了避免陷入局部最優(yōu)解，TS搜索中采用了一種靈活的“記憶”技術(shù)，對已經(jīng)進(jìn)行的優(yōu)化過程進(jìn)行記錄和選擇，指導(dǎo)下一步的搜索方向，這就是Tabu表的建立 為了找到“全局最優(yōu)解”，就不應(yīng)該執(zhí)著于某一個(gè)特定的區(qū)

2、域。局部搜索的缺點(diǎn)就是太貪婪地對某一個(gè)局部區(qū)域以及其鄰域搜索，導(dǎo)致一葉障目，不見泰山。禁忌搜索就是對于找到的一部分局部最優(yōu)解，有意識地避開它（但不是完全隔絕），從而獲得更多的搜索區(qū)間。禁忌搜索算法的主要思路1、在搜索中，構(gòu)造一個(gè)短期循環(huán)記憶表-禁忌表，禁忌表中存放剛剛進(jìn)行過的 |T|（T 稱為禁忌表）個(gè)鄰居的移動，這種移動即解的簡單變化。2、禁忌表中的移動稱為禁忌移動。對于進(jìn)入禁忌表中的移動， 在以后的 |T| 次循環(huán)內(nèi)是禁止的，以避免回到原來的解，從而避免陷入循環(huán)。|T| 次循環(huán)后禁忌解除。3、禁忌表是一個(gè)循環(huán)表，在搜索過程中被循環(huán)的修改，使禁忌表始終保持 |T| 個(gè)移動。4、即使引入了禁忌

3、表，禁忌搜索仍可能出現(xiàn)循環(huán)。因此，必須給定停止準(zhǔn)則以避免出現(xiàn)循環(huán)。當(dāng)?shù)鷥?nèi)所發(fā)現(xiàn)的最好解無法改進(jìn)或無法離開它時(shí)，算法停止。 兔子們找到了泰山，它們之中的一只就會留守在這里，其他的再去別的地方尋找。就這樣，一大圈后，把找到的幾個(gè)山峰一比較，珠穆朗瑪峰脫穎而出。當(dāng)兔子們再尋找的時(shí)候，一般地會有意識地避開泰山，因?yàn)樗麄冎溃@里已經(jīng)找過，并且有一只兔子在那里看著了。這就是禁忌搜索中“禁忌表（tabu list）”的含義。那只留在泰山的兔子一般不會就安家在那里了，它會在一定時(shí)間后重新回到找最高峰的大軍，因?yàn)檫@個(gè)時(shí)候已經(jīng)有了許多新的消息，泰山畢竟也有一個(gè)不錯(cuò)的高度，需要重新考慮，這個(gè)歸隊(duì)時(shí)間，在禁忌搜索

4、里面叫做“禁忌長度（tabu length）”；如果在搜索的過程中，留守泰山的兔子還沒有歸隊(duì)，但是找到的地方全是華北平原等比較低的地方，兔子們就不得不再次考慮選中泰山，也就是說，當(dāng)一個(gè)有兔子留守的地方優(yōu)越性太突出，超過了“best so far”的狀態(tài)，就可以不顧及有沒有兔子留守，都把這個(gè)地方考慮進(jìn)來，這就叫“特赦準(zhǔn)則（aspiration criterion）”。在鄰域中找到最好的解搜索陷入循環(huán)加入禁忌表，避免進(jìn)入循環(huán)禁忌表長度為T： 規(guī)則：不得接受與禁忌表中相同的解禁忌表的變化：第一步搜索時(shí)： 第二步搜索時(shí)： 第三步搜索時(shí)： ，第四步搜索時(shí)： ，.避免陷入循環(huán)原理：當(dāng)解為時(shí)，鄰域最優(yōu)解為，

5、下一步原本應(yīng)該為，但禁忌表中存在，所以選擇次好的，從而避免循環(huán)特赦（藐視）準(zhǔn)則（aspiration criterion）1）基于評價(jià)的規(guī)則，若出現(xiàn)一個(gè)解的目標(biāo)值好于前面任何一個(gè)最佳候選解，可特赦。2）基于最小錯(cuò)誤的規(guī)則，若所有對象都被禁忌，則特設(shè)一個(gè)評價(jià)最優(yōu)的解3）基于影響力的大小，可特赦一個(gè)對目標(biāo)值影響大的對象停止規(guī)則：算法在何種條件下停止1）把最大迭代數(shù)作為停止算法的標(biāo)準(zhǔn)2）在給定數(shù)目的迭代內(nèi)所發(fā)現(xiàn)的最好解無法改進(jìn)或者無法離開時(shí)，算法停止3）最優(yōu)解的目標(biāo)函數(shù)小于指定誤差4）最優(yōu)解的禁忌頻率達(dá)到指定值禁忌搜索算法的步驟例子：四城市非對稱TSP問題，始，終點(diǎn)都為A 第一步，假設(shè)禁忌長度為3例子：四城市非對稱TSP問題，始，終點(diǎn)都為A 第二步例子：四城市非對稱TSP問題，始，終點(diǎn)都為A 第三步例子：四城市非對稱TSP問題，始，終點(diǎn)都為A 第四步例子：四城市非對稱TSP問題