【正文】 ，得到問題的一個實例。描述算法的好壞 —— 計算復(fù)雜性 —— 討論計算時間與問題規(guī)模之間的關(guān)系。12 組合優(yōu)化問題 6/813 組合優(yōu)化問題 7/8例 3 裝箱問題（ bin packing） 尺寸為 1的箱子有若干個，怎樣用最少的箱子裝下 n個尺寸不超過 1 的物品，物品集合為： 。n 傳統(tǒng)的評價方法 算法收斂性（從極限角度考慮） 收斂速度（線性、超線性、二次收斂等）4傳統(tǒng)運籌學(xué)面臨新挑戰(zhàn)n 現(xiàn)代問題的特點 離散性問題 —— 主要以組合優(yōu)化（針對離散問題，定義見后）理論為基礎(chǔ) 不確定性問題 —— 隨機性數(shù)學(xué)模型 半結(jié)構(gòu)或非結(jié)構(gòu)化的問題 —— 計算機模擬、決 策支持系統(tǒng) 大規(guī)模問題 —— 并行計算、大型分解理論、近似理論n 現(xiàn)代優(yōu)化方法 追求滿意 —— 近似解 實用性強 —— 解決實際問題n 現(xiàn)代優(yōu)化算法的評價方法 算法復(fù)雜性5現(xiàn)代優(yōu)化 (啟發(fā)式 )方法種類n 禁忌搜索（ tabu search）n 模擬退火（ simulated annealing）n 遺傳算法（ geic algorithms）n 神經(jīng)網(wǎng)絡(luò)（ neural works）n 蟻群算法（群體（群集）智能， Swarm Intelligence） n 拉格朗日松弛算法（ lagrangean relaxation）61 現(xiàn)代優(yōu)化計算方法概述n 組合優(yōu)化問題n 計算復(fù)雜性的概念n 啟發(fā)式算法7 組合優(yōu)化問題 1/8 組合優(yōu)化（ binatorial optimization） :解決離散問題的優(yōu)化問題 —— 運籌學(xué)分支。通過數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，可以涉及信息技術(shù)、經(jīng)濟管理、工業(yè)工程、交通運輸和通信網(wǎng)絡(luò)等許多方面。 14 組合優(yōu)化問題 8/815 計算復(fù)雜性的概念 1/11n 評價算法的好壞 —— 計算時間的多少、解的偏離程度n 例 非對稱距離 TSP問題的算法實現(xiàn)：所有路徑枚舉。以目前二進制計算機中的存儲和計算為基礎(chǔ)，以理論的形式系統(tǒng)描述，是評估算法性能的基礎(chǔ)。這些具體值稱為 數(shù)據(jù) ；這些數(shù)據(jù)輸入計算機所占的空間稱為 實例的長度 （ size） .18 計算復(fù)雜性的概念 4/11 一類最優(yōu)化問題是由一些類似的具體問題（實例）組成的，每一個具體問題可表達成二元組（ F,C） .F為可行解集合 。24 計算復(fù)雜性的概念 10/11n 利用復(fù)雜性分析對組合優(yōu)化問題歸類。29 啟發(fā)式算法 _分類 4/6（ 1）一步算法（ 2）改進算法（迭代算法） (3) 數(shù)學(xué)規(guī)劃算法 (4) 解空間松弛法 30 啟發(fā)式算法 _分類 5/6（ 5）現(xiàn)代優(yōu)化算法： 80年代初興起n 禁忌搜索（ tabu search）n 模擬退火（ simulated annealing）n 遺傳算法（ geic algorithms）n 神經(jīng)網(wǎng)絡(luò)（ neural works）n 螞蟻算法（ Ant Algorithm， 群體（群集）智能， Swarm Intelligence）（ 6）其他算法： 多種啟發(fā)式算法的集成 . 31 啟發(fā)式算法 _性能分析 6/6（ 1）最壞情形分析 （ worst case analysis） 利用最壞實例分析計算復(fù)雜性、解的效果。用該方法求解 TSP問題、分配問題、 jobshop調(diào)度問題，取得了較好的試驗結(jié)果．雖然研究時間不長，但是現(xiàn)在的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問題（特別是離散優(yōu)化問題）方面有一定優(yōu)勢，表明它是一種有發(fā)展前景的算法．35 蟻群優(yōu)化算法應(yīng)用領(lǐng)域 這種方法能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉(zhuǎn)化為優(yōu)化求解的問題。微粒群算法也是起源于對簡單社會系統(tǒng)的模擬，最初是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。已完成的群智能理論和應(yīng)用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問題的新方法。從螞蟻系統(tǒng)開始，基本的蟻群算法得到了不斷的發(fā)展和完善，并在 TSP以及許多實際優(yōu)化問題求解中進一步得到了驗證。在 Antdensity和 Antquantity中螞蟻在兩個位置節(jié)點間每移動一次后即更新信息素，而在 Antcycle中當所有的螞蟻都完成了自己的行程后才對信息素進行更新，而且每個螞蟻所釋放的信息素被表達為反映相應(yīng)行程質(zhì)量的函數(shù)。這種改進型算法能夠以更快的速度獲得更好的解。 AntQ將螞蟻算法和一種增強型學(xué)習(xí)算法 Qlearning有機的結(jié)合了起來。 43 5/7 在對 AS進行直接完善的方法中， MAXMIN Ant System是一個典型代表。與 “精英策略 ”相似，在此算法中總是更新更好進程上的信息素，選擇的標準是其行程長度 決定的排序，且每個螞蟻放置信息素的強度通過下式中的排序加權(quán)處理確定，其中，ｗ為每次迭代后放置信息素的螞蟻總數(shù)。 46 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 1/5 隨著群智能理論和應(yīng)用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問題，并取得了意想不到的收獲。 47 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 2/5 蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。同時根據(jù)信息素揮發(fā)機制實現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。 Lumer和 Faieta將 Deneubourg提出將蟻巢分類模型應(yīng)用于數(shù)據(jù)聚類分析。 經(jīng)過多年的發(fā)展， ACO已成為能夠有效解決實際二次規(guī)劃問題的幾種重要算法之一。50 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 5/5 許多研究者將 ACO用于了武器攻擊目標分配和優(yōu)化問題、車輛運行路徑規(guī)劃、區(qū)域性無線電頻率自動分配、 Bayesian works的訓(xùn)練和集合覆蓋等應(yīng)用優(yōu)化問題。 為了說明蟻群算法的原理，先簡要介紹一下螞蟻搜尋食物的具體過程。與此同時釋放出與路徑長度有關(guān)的信息素。最終整個蟻群會找出最優(yōu)路徑。55 簡化的螞蟻尋食過程 3/3 假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過 36個時間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從 D點取得了食物，此時 ABD的路線往返了 2趟，每一處的信息素為 4個單位，而 ACD的路線往返了一趟，每一處的信息素為 2個單位，其比值為 2： 1。再經(jīng)過 36個時間單位后，兩條線路上的信息素單位積累為 24和 6，比值為 4： 1。 人工蟻群中把具有簡單功能的工作單元看作螞蟻。同時，人工蟻群再選擇下一條路徑的時候是按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定： 1 信息素值 也稱信息素痕跡。 螞蟻在尋找過程中，或者找到一個解后，會評估該解或解的一部分的優(yōu)化程度，并把評價信息保存在相關(guān)連接的信息素中。61 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 2/12STEP 1 （外循環(huán)）如果滿足算法的停止規(guī)則，則停止計算并輸出計算得到的最好解。否則，若，則以概率 ， 到達 j， ；若則到達 重復(fù) STEP 2。用如下公式對 W路徑上的信息素痕跡加強，對其他路徑上的信息素進行揮發(fā)。 算法中包括信息素更新的過程 1 信息素揮發(fā)（ evaporation） 信息素痕跡的揮發(fā)過程是每個連接上的信息素痕跡的濃度自動逐漸減弱的過程，由 表示，這個揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴展。這種增強過程中進行的信息素更新稱為離線的信息素更新。此時，觀察 GBAS的計算過程。70 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 11/12重復(fù)外循環(huán)，由于 W2全局最優(yōu)解， GBAS只記錄第一個最優(yōu)解，因此一但得到了全局最優(yōu)解，信息素的更新將不再依賴于以群的行走路線，而只是不斷增強最優(yōu)路線的信息素，同時進行揮發(fā)。由于螞蟻的一步轉(zhuǎn)移概率是隨機的，從 到 也是隨機的，是一個馬爾可夫過程。 的變化僅由 決定，而與先前的狀態(tài)無關(guān)，這是一個典型的馬爾可夫過程。蟻群算法在解決這類問題時，只需要建立一個虛擬的始終點，就可以把 TSP問題的解法推廣，用于諸多的優(yōu)化問題。設(shè)有一個容積為 b的背包， n個尺寸分別為 ，價值分別為 的物品， 01背包問題的數(shù)學(xué)模型為：假設(shè)其解的順序表達形式為　　　　　　　　，其中　　　為　　　　　　的一個排列。第 步按 TSP算法的轉(zhuǎn)移概率公式行走選擇 。