高級算法設計與分析啟發式算法林海lin.hai@B站：foretmer內容概述模擬退火Tabusearch遺傳算法蟻群算法優化問題經典優化算法通過對解空間的枚舉（離散），或者對目標函數的微分（連續）求最優解默認為存在唯一最優解但很多優化問題無法通過上述方法求得最優解問題不是凸的（凸優化）解空間太大大多數問題只能求出近似解近似算法、隨機算法啟發式算法啟發式算法啟發式算法(heuristicalgorithm)指通過對過去經驗的歸納推理以及實驗分析來解決問題的方法，即借助于某種直觀判斷或試探的方法，以求得問題的次優解或以一定的概率求其最優解，所以可以認為啟發式算法一種基于經驗或者實驗算法的統稱元啟發式算法(metaheuristic)元啟發式算法都從自然界的一些現象取得靈感(e.g.模擬退火、遺傳算法)，通過這些現象獲取的求解過程(元啟發式算法)來解決實際的一些問題啟發式算法元啟發式算法看成構造啟發式算法的一些基礎方法，而啟發式算法就是利用元啟發式算法，結合被求解問題的特征，設計出來的面向特定問題的算法啟發式算法通常基于自然界中發現的一些規律或者準則能夠被計算機計算和處理目標是得出最優解的近似解，但不能確定得到的解就是最優解但通常得到的解比局部最優解要好適用于不同的問題，并能同時考慮一些約束條件啟發式算法啟發式算法局部搜索方法經典的啟發式算法（元啟發式算法）模擬退火（Simulatedannealing）禁忌搜索（Tabusearch）遺傳算法（Geneticalgorithms）蟻群算法（Antcolonies）局部搜索：2-opt算法2-opt變換在旅行商問題中，去除某一回路l的兩條邊e1和e2，形成了兩個子圖，對這兩個子圖重新連接形成新的回路l′，l′是通過對l的2-opt交換形成的局部搜索：2-opt算法局部搜索：2-opt算法局部搜索：3-opt算法內容概述模擬退火Tabusearch遺傳算法蟻群算法模擬退火什么是退火——物理上的由來退火（annealing）現象指物體逐漸降溫的物理現象，溫度愈低，物體的能量狀態會低；夠低后，液體開始冷凝與結晶，在結晶狀態時，系統的能量狀態最低。大自然在緩慢降溫（亦即，退火）時，可“找到”最低能量狀態：結晶。但是，如果過程過急過快，快速降溫（亦稱「淬煉」，quenching）時，會導致不是最低能態的非晶形。模擬退火什么是退火——物理上的由來如下圖所示，首先（左圖）物體處于非晶體狀態。我們將固體加溫至充分高（中圖），再讓其徐徐冷卻，也就退火（右圖）。加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小（此時物體以晶體形態呈現）模擬退火算法概述若目標函數f在第i+1步移動后比第i步更優，即f(Y(i+1))<=f(Y(i))，則總是接受該移動；若f(Y(i+1))>f(Y(i))(即移動后的解比當前解要差)，則以一定的概率接受移動，而且這個概率隨著時間推移逐漸降低（逐漸降低才能趨向穩定）。Metroplis準則模擬退火Metroplis準則溫度越高，算法接受新解的概率越高。這個根據一定概率選擇是否接受差解的方法叫做Metropolos準則模擬退火：算法模擬退火：算法模擬退火：旅行商問題旅行商問題輸入：旅行圖、初始溫度、最小溫度、降溫系數輸出：旅行回路算法隨機選擇城市順序在第i步的基礎上，隨機交換兩個（或多個）城市的順序（移動一步）如果第i+1步的代價更小，則作為當前哈密頓回路，否則依據Metroplis準則定義的概率作為當前回路，重復執行此步驟n次按照降溫系數降低溫度，重復以上步驟直到迭代次數達到預設值或者溫度下降到預設值模擬退火：旅行商問題內容概述模擬退火Tabusearch遺傳算法蟻群算法Tabusearch從一個初始可行解出發，選擇一系列的特定搜索方向（移動）作為試探，選擇實現讓特定的目標函數值變化最多的移動。為了避免陷入局部最優解，TS搜索中采用了一種靈活的“記憶”技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向，這就是Tabu表的建立。標記已經解得的局部最優解或求解過程，并在進一步的迭代中避開這些局部最優解或求解過程。局部搜索的缺點在于，太過于對某一局部區域以及其鄰域的搜索，導致一葉障目。為了找到全局最優解，禁忌搜索就是對于找到的一部分局部最優解，有意識地避開它，從而或得更多的搜索區域。Tabusearch：相關概念鄰域所謂鄰域，簡單的說即是給定點附近其他點的集合。鄰域就是指對當前解進行一個操作(這個操作可以稱之為鄰域動作)可以得到的所有解的集合。鄰域動作鄰域動作是一個函數，通過這個函數，對當前解s，產生其相應的鄰居解集合。例如：對于一個bool型問題，其當前解為：s=1001，當將鄰域動作定義為翻轉其中一個bit時，得到的鄰居解的集合N(s)={0001,1101,1011,1000}，其中N(s)∈S。Tabusearch：相關概念禁忌表禁忌對象：由于需要避免一些操作的重復進行，就要將一些元素放到禁忌表中以禁止對這些元素進行操作，這些元素就是我們指的禁忌對象（通常指找到的局部最優解）。禁忌長度：禁忌長度是被禁對象不允許選取的迭代次數。一般是給被禁對象x一個數（禁忌長度）t，要求對象x在t步迭代內被禁，在禁忌表中采用tabu(x)=t記憶，每迭代一步，該項指標做運算tabu(x)=t?1，直到tabu(x)=0時解禁。侯選集合侯選集合由鄰域中的鄰居組成。常規的方法是從鄰域中選擇若干個目標值或評價值最佳的鄰居入選。Tabusearch：相關概念評價函數（目標函數）評價函數是侯選集合元素選取的一個評價公式，侯選集合的元素通過評價函數值來選取。特赦規則在禁忌搜索算法的迭代過程中，會出現侯選集中的全部對象都被禁忌，或有一對象被禁，但若解禁則其目標值將有非常大的下降情況。在這樣的情況下，為了達到全局最優，我們會讓一些禁忌對象重新可選。這種方法稱為特赦，相應的規則稱為特赦規則。Tabusearch：算法Step1：禁忌表H=空集，并選定一個初始解x1；step2：在xi的鄰域N(xi)中選擇候選集Can_N(xi)；在Can_N(xi)中選一個評價值最佳的解xi+1，xi+1不在禁忌表中，選為當前解xi+1在禁忌表中，滿足破禁條件，xi+1為當前解，否則從不在禁忌表解中，選擇一個最優解step3：重復step2，直到滿足停止條件Tabusearch：例子求下圖的旅行商回路Tabusearch：例子隨機選擇一個城市序列：21543，路徑長度889交換城市長度1?58041?58043?4907禁忌表15?123Tabusearch：例子最優訪問順序：25143，最優長度804當前訪問順序：25143，長度804交換城市長度5?410981?49285?1889禁忌表14?125?13Tabusearch：例子最優訪問順序：25143，最優長度804當前訪問順序：25413，長度928交換城市長度5?110855?410625?3786禁忌表15?324?135?1Tabusearch：例子最優訪問順序：23415，最優長度786當前訪問順序：23415，長度786交換城市長度4?19463?47682?31098禁忌表13?425?334?1Tabusearch：例子最優訪問順序：24315，最優長度768當前訪問順序：24315，長度768交換城市長度4?59644?17371?5907禁忌表14?123?435?3破禁Tabusearch：例子迭代5次最優訪問順序：21345，最優長度737內容概述模擬退火Tabusearch遺傳算法蟻群算法遺傳算法：引例遺傳算法：引例在一代代演化的過程中，父母扇貝的基因組合產生新扇貝，所以遺傳算法會選擇兩個原有的扇貝，然后對這兩個扇貝的染色體進行隨機交叉形成新的扇貝迭代演化也會造成基因突變，遺傳算法讓新產生扇貝的基因以較小的概率發生變異。也就是說，染色體的像素值隨機改變對扇貝像素值和Firefox圖標進行逐一比較，顏色相差得越大的顯然表示越不像。這個評價的函數叫做“適應度函數”，它負責評價扇貝和Firefox的相似程度遺傳算法：交叉遺傳算法：變異遺傳算法：引例遺傳算法遺傳算法遺傳算法遺傳算法遺傳算法遺傳算法遺傳算法遺傳算法遺傳算法遺傳算法：流程遺傳算法：流程遺傳算法：應用遺傳算法：應用遺傳算法：應用遺傳算法：旅行商問題遺傳算法：旅行商問題可能出現非法解遺傳算法：旅行商問題遺傳算法：旅行商問題遺傳算法：旅行商問題內容概述模擬退火Tabusearch遺傳算法蟻群算法蟻群算法螞蟻幾乎是沒有視力的，它們是如何找到食物和家之間的路徑的?在覓食過程中,螞蟻在它所經過的路徑上留下濃度與食物源質量成比例的信息素(pheromone),并能夠感知信息素的存在及其濃度,以此指導自己的運動方向,傾向于朝著信息素濃度高的方向移動于是,蟻群的集體行為便表現出一種信息正反饋現象:某一路徑上走過的螞蟻越多,則后來者選擇該路徑的概率就越大,因此質量好、距離近的食物源會吸引越來越多的螞蟻,信息素濃度的增長速度會更快.螞蟻個體之間就是通過這種信息的交流達到尋找食物和蟻穴之間最短路徑的目的蟻群算法：例子蟻群算法路徑選擇概率蟻群算法：基本蟻群算法城市i和城市j間路徑的信息素更新為：

蟻群算法：基本蟻群算法蟻群算法：蟻群系統對基本蟻群算法的改進在路徑選擇中采用了利用(exploitation)和探索(exploration)相結合的方法蟻群算法：蟻群系統對基本蟻群算法的改進信息素的更新采用了全局更新和局部更新相結合的方案局部更新是所有螞蟻完成一次移動后執行蟻群算法：蟻群系統對基本蟻群算法的改進信息素的更新采用了全局更新和局部更新相結合的方案全局更新是在所有的螞蟻完成了旅行商回路后執行，全局更新僅僅對目前的最優回路上的路徑(邊