局域搜索演算法

❶ 禁忌搜索演算法淺析

姓名：劉家沐

學號：19011210553

網路來源，有刪減

【嵌牛導讀】：針對TSP問題等類似的NP-hard 問題，如果能在盡量少的計算量的情況下找到一個最優或者是較優的解成為當前一個熱門的討論話題，禁忌搜索演算法便是其中之一

【嵌牛鼻子】：禁忌搜索演算法   最優化問題    TSP問題

【嵌牛正文】：

背景：禁忌搜索演算法（Tabu Search）是由美國科羅拉多州大學的Fred Glover教授在1986年左右提出來的，是一個用來跳出局部最優的搜尋方法。在解決最優問題上，一般區分為兩種方式：一種是傳統的方法，另一種方法則是一些啟發式搜索演算法。

使用傳統的方法，我們必須對每一個問題都去設計一套演算法，相當不方便，缺乏廣泛性，優點在於我們可以證明演算法的正確性，我們可以保證找到的答案是最優的；而對於啟發式演算法，針對不同的問題，我們可以套用同一個架構來尋找答案，在這個過程中，我們只需要設計評價函數以及如何找到下一個可能解的函數等，所以啟發式演算法的廣泛性比較高，但相對在准確度上就不一定能夠達到最優，但是在實際問題中啟發式演算法那有著更廣泛的應用。 

禁忌搜索是一種亞啟發式隨機搜索演算法，它從一個初始可行解出發，選擇一系列的特定搜索方向(移動)作為試探，選擇實現讓特定的目標函數值變化最多的移動。為了避免陷入局部最優解，TS搜索中採用了一種靈活的「記憶」技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向。 TS是人工智慧的一種體現，是局部領域搜索的一種擴展。禁忌搜索是在領域搜索的基礎上，通過設置禁忌表來禁忌一些已經歷的操作，並利用藐視准則來獎勵一些優良狀態，其中涉及鄰域 、禁忌表、禁忌長度、候選解、藐視准則等影響禁忌搜索演算法性能的關鍵因素。迄今為止，TS演算法在組合優化等計算機領域取得了很大的成功，近年來又在函數全局優化方面得到較多的研究，並大有發展的趨勢。

局域搜索：在一個小的搜索范圍里，進行搜索，或者根據結果逐步擴大搜索范圍，但是這樣會容易陷入局部最優

為了獲得好解，可以採用的策略有(1)擴大鄰域結構，(2)變鄰域結構    ，(3)多初始點。但這些策略依然無法保證演算法具備跳出局優的能力。

禁忌搜索：

為了找到「全局最優解」，就不應該執著於某一個特定的區域。局部搜索的缺點就是太貪婪地對某一個局部區域以及其鄰域搜索，導致一葉障目，不見泰山。 禁忌搜索 就是對於找到的一部分局部最優解，有意識地避開它（但不是完全隔絕），從而獲得更多的搜索區間。兔子們找到了泰山，它們之中的一隻就會留守在這里，其他的再去別的地方尋找。就這樣，一大圈後，把找到的幾個山峰一比較， 珠穆朗瑪峰 脫穎而出。

當兔子們再尋找的時候，一般地會有意識地避開泰山，因為他們知道，這里已經找過，並且有一隻兔子在那裡看著了。這就是禁忌搜索中「禁忌表（tabu list）」的含義。那隻留在泰山的兔子一般不會就安家在那裡了，它會在一定時間後重新回到找最高峰的大軍，因為這個時候已經有了許多新的消息，泰山畢竟也有一個不錯的高度，需要重新考慮，這個歸隊時間，在禁忌搜索裡面叫做「禁忌長度（tabu length）」；如果在搜索的過程中，留守泰山的兔子還沒有歸隊，但是找到的地方全是華北平原等比較低的地方，兔子們就不得不再次考慮選中泰山，也就是說，當一個有兔子留守的地方優越性太突出，超過了「best so far」的狀態，就可以不顧及有沒有兔子留守，都把這個地方考慮進來，這就叫「特赦准則（aspiration criterion）」。這三個概念是禁忌搜索和一般搜索准則最不同的地方，演算法的優化也關鍵在這里。

主要思路：

1、在搜索中，構造一個短期循環記憶表-禁忌表，禁忌表中存放剛剛進行過的 |T|（T稱為禁忌表）個鄰居的移動，這種移動即解的簡單變化。

2、禁忌表中的移動稱為禁忌移動。對於進入禁忌表中的移動， 在以後的 |T| 次循環內是禁止的，以避免回到原來的解，從而避免陷入循環。|T| 次循環後禁忌解除。

3、禁忌表是一個循環表，在搜索過程中被循環的修改，使禁忌表始終保持 |T| 個移動。

4、即使引入了禁忌表，禁忌搜索仍可能出現循環。因此，必須給定停止准則以避免出現循環。當迭代內所發現的最好解無法改進或無法離開它時，演算法停止。

總結：

與傳統的優化演算法相比，TS演算法的主要特點是：

 1．從移動規則看，每次只與最優點比較，而不與經過點比較，故可以爬出局部最優。

 2．選優規則始終保持曾經達到的最優點，所以即使離開了全局最優點也不會失去全局最優性。

 3．終止規則不以達到局部最優為終止規則，而以最大迭代次數、出現頻率限制或者目標值偏離成都為終止規則

禁忌搜索是對人類思維過程本身的一種模擬，它通過對一些局部最優解的禁忌（也可以說是記憶）達到接納一部分較差解，從而跳出局部搜索的目的。因而在計算搜索領域有著廣泛應用。

❷ 區域網按照拓撲結構可分為哪幾種類型有什麼優點

1、匯流排拓撲結構

匯流排拓撲結構將網路中的所有設備通過相應的硬體介面直接連接到公共匯流排上，結點之間按廣播方式通信，一個結點發出的信息，匯流排上的其它結點均可「收聽」到。

優點：結構簡單、布線容易、可靠性較高，易於擴充，是區域網常採用的拓撲結構。

2、星型拓撲結構

每個結點都由一條單獨的通信線路與中心結點連結。

優點：結構簡單、容易實現、便於管理，連接點的故障容易監測和排除。

3、環形拓撲結構

環形拓撲結構各結點通過通信線路組成閉合迴路，環中數據只能單向傳輸。

優點：結構簡單、容易實現，適合使用光纖，傳輸距離遠，傳輸延遲確定。

4、樹型拓撲結構

是一種層次結構，結點按層次連結，信息交換主要在上下結點之間進行，相鄰結點或同層結點之間一般不進行數據交換。

優點：連結簡單，維護方便，適用於匯集信息的應用要求。

5、網狀拓撲結構
又稱作無規則結構，結點之間的聯結是任意的，沒有規律。

優點：系統可靠性高，比較容易擴展，但是結構復雜，每一結點都與多點進行連結，因此必須採用路由演算法和流量控制方法。目前廣域網基本上採用網狀拓撲結構。