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