【正文】 個城市，固定 1個為起終點需要 (n1)!個枚舉，設(shè)計算機 1秒能完成 24個城市的枚舉，則城市數(shù)與計算時間的關(guān)系如下表： 15 計算復(fù)雜性的概念 2/11 城市數(shù) 24 25 26 27 28 29 30 31 計算時間 1 sec 24 sec 10 min hour day day year 325 year 隨城市增多，計算時間增加很快。 12{ , , ... }na a a13 組合優(yōu)化問題 8/8 ? ?11m i n. . 1 , 1 , 2 , , , 1 , 1 , 2 , , , 0 , 1 , 1 , 2 , , 。 問題描述：一商人去 n個城市銷貨，所有城市走一遍再回到起點，使所走路程最短。通過數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，可以涉及信息技術(shù)、經(jīng)濟管理、工業(yè)工程、交通運輸和通信網(wǎng)絡(luò)等許多方面。1 內(nèi) 容 一、啟發(fā)式方法概述 二、蟻群優(yōu)化算法 2 背 景 ? 傳統(tǒng)實際問題的特點 連續(xù)性問題 —— 主要以微積分為基礎(chǔ)，且問題規(guī)模較小 ? 傳統(tǒng)的優(yōu)化方法 追求準(zhǔn)確 —— 精確解 理論的完美 —— 結(jié)果漂亮 主要方法：線性與非線性規(guī)劃、動態(tài)規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī)劃等；排隊論、庫存論、對策論、決策論等。 ? 傳統(tǒng)的評價方法 算法收斂性（從極限角度考慮） 收斂速度（線性、超線性、二次收斂等） 3 傳統(tǒng)運籌學(xué)面臨新挑戰(zhàn) ? 現(xiàn)代問題的特點 離散性問題 —— 主要以組合優(yōu)化（針對離散問題，定義見后）理論為基礎(chǔ) 不確定性問題 —— 隨機性數(shù)學(xué)模型 半結(jié)構(gòu)或非結(jié)構(gòu)化的問題 —— 計算機模擬、決 策支持系統(tǒng) 大規(guī)模問題 —— 并行計算、大型分解理論、近似理論 ? 現(xiàn)代優(yōu)化方法 追求滿意 —— 近似解 實用性強 —— 解決實際問題 ? 現(xiàn)代優(yōu)化算法的評價方法 算法復(fù)雜性 4 現(xiàn)代優(yōu)化 (啟發(fā)式 )方法種類 ? 禁忌搜索（ tabu search） ? 模擬退火（ simulated annealing） ? 遺傳算法（ geic algorithms） ? 神經(jīng)網(wǎng)絡(luò)（ neural works） ? 蟻群算法（群體（群集）智能， Swarm Intelligence） ? 拉格朗日松弛算法（ lagrangean relaxation） 5 1 現(xiàn)代優(yōu)化計算方法概述 ? 組合優(yōu)化問題 ? 計算復(fù)雜性的概念 ? 啟發(fā)式算法 6 組合優(yōu)化問題 1/8 組合優(yōu)化（ binatorial optimization） :解決離散問題的優(yōu)化問題 —— 運籌學(xué)分支。 數(shù)學(xué)模型： 決策變量有限點集約束函數(shù)目標(biāo)函數(shù), . ,0)(.. )( m i nDxxgtsxf??7 組合優(yōu)化問題 2/8 組合優(yōu)化問題的三參數(shù)表示： ? ?? ? .|)(m i n)(,:::,0)(,|:),(FxxfxfFxxFxfxgDxxFDfFD??????????最優(yōu)解，如果可行解（點）目標(biāo)函數(shù)有限點集可行域決策變量定義域8 組合優(yōu)化問題 3/8 ? 例 1 01背包問題（ 01 knapsack problem） 裝包？問題：如何以最大價值件物品單位價值，第件物品單位體積，第背包容積.,1:.,1::niicniiabii????9 組合優(yōu)化問題 4/8 ? ?? ? .1,0i0i 1( 1 .3 ) .,1,1,0 ( 1 .2 ) ,as .t .( 1 .1 ) m a xn1ii1iniiiniiDxnixbxxc????????????物品，不裝第物品裝第，其中決策變量包容量限制總價值數(shù)學(xué)模型：?10 組合優(yōu)化問題 5/8 ? 例 2 旅行商問題（ TSP,traveling salesman problem） 管梅谷教授 1960年首先提出，國際上稱之為中國郵遞員問題。 11 組合優(yōu)化問題 6/8 ij1ij1m i n ( ) . 1. 1 , 2 , , , ( ) i 1. 1 , 2 , , , ij ijijnjnidxx i nx j n??????????數(shù)學(xué)模型：總路長只從城市 出來一次? ?? ?, ( ) 1 , 2 1 , 1 , 2 , , , ( ) 0 , 1 , , 1 , 2 , , , . ( ) : i j , s : s 1 , iji j sijijijjx s s n s nx i j n i jdijx?? ? ? ? ? ?? ? ???只走入城市 一次在任意城市子集中不形成回路決策變量其中城市 與城市 之間的距離 集合 中元素的個數(shù)，走城市 和城市0.: , ,: , ,ij jiij jiijT SP d d i jT SP d d i j???????之間的路徑，不走城市 和城市 之間的路徑對稱距離非對稱距離12 組合優(yōu)化問題 7/8 例 3 裝箱問題（ bin packing） 尺寸為 1的箱子有若干個，怎樣用最少的箱子裝下 n個尺寸不超過 1 的物品，物品集合為： 。 1 , 2 , , , B :1 , 0 .Bibbni i biibibBs t x i na x b Bx i n b Bibxib??????? ? ??? ????數(shù)學(xué)模型：其中 裝下全部物品需要的箱子，第 物品裝在第 個箱子，第 物品不裝在第 個箱子14 計算復(fù)雜性的概念 1/11 ? 評價算法的好壞 —— 計算時間的多少、解的偏離程度 ? 例 非對稱距離 TSP問題的算法實現(xiàn)：所有路徑枚舉。到 31個城市時，要計算 325年。以目前二進(jìn)制計算機中的存儲和計算為基礎(chǔ)，以理論的形式系統(tǒng)描述，是評估算法性能的基礎(chǔ)?？梢詮膬煞矫婷枋觯? （ 1）對所有參數(shù)的一般性描述； （ 2）答案（或解）必須滿足的性質(zhì)。這些具體值稱為 數(shù)據(jù) ；這些數(shù)據(jù)輸入計算機所占的空間稱為 實例的長度 （ size） . 17 計算復(fù)雜性的概念 4/11 一類最優(yōu)化問題是由一些類似的具體問題（實例）組成的，每一個具體問題可表達(dá)成二元組（ F,C） .F為可行解集合 。問題是在 F中找到一個點 f*，使對 F中任意的 f，有 C(f*) C(f),稱 f*為這一具體問題的最優(yōu)解（或全局最優(yōu)解） . ?18 計算復(fù)雜性的概念 5/11 ? 算法計算量的度量： 加、減、乘、除、比較的總運算次數(shù)與實例的計算機計算時的二進(jìn)制輸入數(shù)據(jù)的大小關(guān)系。19 計算復(fù)雜性的概念 6/11 ? 算法計算量的度量之例 —— TSP枚舉法 ? ?? ?21 , , , ( 1 ) !( 1 ) ! ! 。22 計算復(fù)雜性的概念 9/11 定義 多項式算法 給定問題 P， 算法 A， 對一個實例 I， 存在多項式 函數(shù) g(x)， 使（ XX ）成立，稱 算法 A對實例 I是 多項式算法 ； 若存在多項式函數(shù) g(x)， 使（ XX ）對問題 P的任 意實例 I都成立，稱 算法 A為解決該問題 P的多項 式算法 . 當(dāng) g(x)為指數(shù)函數(shù)時，稱 A為 P的指數(shù)時間算法。 ? 定義 多項式問題 給定一個組合優(yōu)化問題，若存在一個多項式算法，稱該問題為多項式時間可解問題，或簡稱 多項式問題 (或 P問題 ). 所有多項式問題的集合記為 P. ? 例：線性規(guī)劃是否為多項式問題？ 24 計算復(fù)雜性參考書 11/11 ? 計算復(fù)雜性 , 作者： Christos， Papadimitriou 清華大學(xué)出版社， 2022年 9月 第 1版 ? 計算復(fù)雜性導(dǎo)論， 作者：堵丁柱等， 高等教育出版社， 2022年 8月第 1版 25 啟發(fā)式算法 _定義 1/6 ? 啟發(fā)式算法（ heuristic algorithm） ? 定義 1. 基于 直觀或經(jīng)驗 構(gòu)造的算法，在可接受的花費（時間、空間）下，給出待解組合優(yōu)化問題的每個實例的一個 可行解 ，該可行解與最優(yōu)解偏差事先不一定可以預(yù)計 . ? 定義 2. 啟發(fā)式算法是一種技術(shù)，在可接受的計算費用內(nèi)尋找最好解，但不保證該解的可行性與最優(yōu)性，無法描述該解與最優(yōu)解的近似程度。 27 啟發(fā)式算法 _不足 3/6 不足： （ 1）不能保證求得全局最優(yōu)解； （ 2）解的精度不穩(wěn)定，有時好有時壞； （ 3）算法設(shè)計與問題、設(shè)計者經(jīng)驗、技術(shù) 有關(guān)，缺乏規(guī)律性； （ 4）不同算法之間難以比較。 (2）概率分析 （ probability analysis） 用最壞情況分析，會因一個最壞實例影響總體評價 . 在實例數(shù)據(jù)服從一定概率分布情形下，研究算法復(fù)雜性和解的效果 . (3)大規(guī)模計算分析 通過大量實例計算，評價算法效果 . ? 注意數(shù)據(jù)的隨機性和代表性 . 31 2 蟻群優(yōu)化算法 1. 蟻群優(yōu)化算法概述 2. 蟻群優(yōu)化算法概念 3. 算法模型和收斂性分析 4. 算法實現(xiàn)的技術(shù)問題 5. 應(yīng)用 6. 參考資料 32 蟻群優(yōu)化算法概述 ? 起源 ? 應(yīng)用領(lǐng)域 ? 研究背景 ? 研究現(xiàn)狀 ? 應(yīng)用現(xiàn)狀 33 蟻群優(yōu)化算法起源 20世紀(jì) 50年代中期創(chuàng)立了仿生學(xué)，人們從生物進(jìn)化的機理中受到啟發(fā)。 20世紀(jì) 90年代意大利學(xué)者 M． Dorigo， V． Maniezzo，A． Colorni等從生物進(jìn)化的機制中受到啟發(fā)，通過模擬自然界螞蟻搜索路徑的行為，提出來一種新型的模擬進(jìn)化算法 —— 蟻群算法，是群智能理論研究領(lǐng)域的一種主要算法?，F(xiàn)在其應(yīng)用領(lǐng)域已擴展到多目標(biāo)優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識別、電信 QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號處理、機器人控制、決策支持以及仿真和系統(tǒng)辯識等方面，群智能理論和方法為解決這類應(yīng)用問題提供了新的途徑 。前者是對螞蟻群落食物采集過程的模擬，已成功應(yīng)用于許多離散優(yōu)化問題。 36 蟻群優(yōu)化算法研究背景 2/3 與大多數(shù)基于梯度的應(yīng)用優(yōu)化算法不同，群智能依靠的是 概率搜索算法。而且，這種方法只需目標(biāo)函數(shù)的輸出值，而無需其梯度信息。更為重要是，群智能潛在的并行性和分布式特點為處理大量的以數(shù)據(jù)庫形式存在的數(shù)據(jù)提供了技術(shù)保證。 38 蟻群優(yōu)化算法研究現(xiàn)狀 1/7 90年代 Dorigo最早提出了蟻群優(yōu)化算法 螞蟻系統(tǒng)（ Ant System, AS）并將其應(yīng)用于解決計算機算法學(xué)中經(jīng)典的旅行商問題（ TSP）。這些 AS改進(jìn)版本的一個共同點就是增強了螞蟻搜索過程中對最優(yōu)解的探索能力，它們之間的差異僅在于搜索控制策略方面。 39 2/7 最初提出的 AS有三種版本： Antdensity、 Antquantity和 Antcycle。通過與其它各種通用的啟發(fā)式算法相比，在不大于 75城市的 TSP中，這三種基本算法的求解能力還是比較理想的，但是當(dāng)問題規(guī)模擴展時， AS的解題能力大幅度下降。較早的一種改進(jìn)方法是精英策略 (Elitist Strategy)，其思想是在算法開始后即對所有已發(fā)現(xiàn)的最好路徑給予額外的增強，并將隨后與之對應(yīng)的行程記為 Tgb