《高級算法設計》課件 第6、7章 在線算法；啟發(fā)式算法

高級算法設計與分析在線算法目錄基本概念確定性在線算法在線最小生成樹時間序列搜索隨機在線算法租買問題在線二分圖最大匹配概述離線算法在前面討論的算法中，問題實例的所有數(shù)據(jù)在計算時，都是已知的，稱為離線算法在線算法問題實例的數(shù)據(jù)是逐漸到來的，但是又需要對已經(jīng)到來的數(shù)據(jù)進行計算，也就是說算法必須在輸入數(shù)據(jù)不是很完全可知的情況下，完成相應的計算并輸出結(jié)果如股票買賣、物流中的裝車問題在線算法是近似算法概述人工智能算法試圖從以往的數(shù)據(jù)中尋找出規(guī)律，并根據(jù)目前的分配狀態(tài)，來智能的分配目前到達的任務在線算法數(shù)據(jù)完全未知假設存在一個對手(adversary)：這個對手對設計的算法了如指掌，所以能夠針對算法給出最壞數(shù)據(jù)到達實例(稱為最壞實例)，來使得算法的效率最低，所以設計在線算法時，通常需要分析在最壞實例下算法的性能。概述：流程股票買賣為例概述：定義競爭度ρ概述：定義在線算法的下界下界表達式給出了在最差實例下，任意在線算法ALG和OPT存在大于等于的關系，如果某算法ALG′的ρ=α，且c=0,b=0，說明在線算法ALG′的性能已經(jīng)最優(yōu)，因為所有在線算法在最壞實例下都是大于等于競爭度ρ的，當在線算法ALG′的競爭度是小于等于ρ，顯然ALG′已經(jīng)最優(yōu)。確定性在線算法：在線最小生成樹在線最小生成樹圖中的頂點不是一開始就已知，而是逐個到達，并要求一旦一個頂點到達就需要加入到樹中，且讓生成的樹總代價盡量小。一個比較簡單的在線算法是讓到達的頂點通過離樹內(nèi)最近的頂點加入到樹中。如，在第k個頂點到達時，選取前面k?1個頂點中和第k個頂點距離最近的頂點，通過此頂點將第k個頂點加入到樹中。我們把這種算法稱為最小生成樹的貪心在線算法。確定性在線算法：在線最小生成樹在線最小生成樹確定性在線算法：在線最小生成樹確定性在線算法：在線最小生成樹確定性在線算法：在線最小生成樹確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索目錄基本概念確定性在線算法在線最小生成樹時間序列搜索隨機在線算法租買問題在線二分圖最大匹配隨機在線算法策略的做出是隨機性，形成隨機在線算法，隨機在線算法的好處是，假設的對手無法猜測算法的策略。隨機在線算法：租買問題隨機在線算法：租買問題隨機在線算法：租買問題隨機在線算法：租買問題隨機在線算法：租買問題隨機在線算法：租買問題隨機在線算法：租買問題回到上面租買問題的例子ρ=4/3

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