【正文】 1定義 多項(xiàng)式算法給定問題 P， 算法 A， 對(duì)一個(gè)實(shí)例 I， 存在多項(xiàng)式函數(shù) g(x)， 使（ XX ）成立，稱 算法 A對(duì)實(shí)例 I是多項(xiàng)式算法 ；若存在多項(xiàng)式函數(shù) g(x)， 使（ XX ）對(duì)問題 P的任意實(shí)例 I都成立，稱 算法 A為解決該問題 P的多項(xiàng)式算法 .當(dāng) g(x)為指數(shù)函數(shù)時(shí)，稱 A為 P的指數(shù)時(shí)間算法。描述算法的好壞 —— 計(jì)算復(fù)雜性 —— 討論計(jì)算時(shí)間與問題規(guī)模之間的關(guān)系。n 傳統(tǒng)的評(píng)價(jià)方法 算法收斂性（從極限角度考慮） 收斂速度（線性、超線性、二次收斂等）4傳統(tǒng)運(yùn)籌學(xué)面臨新挑戰(zhàn)n 現(xiàn)代問題的特點(diǎn) 離散性問題 —— 主要以組合優(yōu)化（針對(duì)離散問題，定義見后）理論為基礎(chǔ) 不確定性問題 —— 隨機(jī)性數(shù)學(xué)模型 半結(jié)構(gòu)或非結(jié)構(gòu)化的問題 —— 計(jì)算機(jī)模擬、決 策支持系統(tǒng) 大規(guī)模問題 —— 并行計(jì)算、大型分解理論、近似理論n 現(xiàn)代優(yōu)化方法 追求滿意 —— 近似解 實(shí)用性強(qiáng) —— 解決實(shí)際問題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)化問題n 計(jì)算復(fù)雜性的概念n 啟發(fā)式算法7 組合優(yōu)化問題 1/8 組合優(yōu)化（ binatorial optimization） :解決離散問題的優(yōu)化問題 —— 運(yùn)籌學(xué)分支。 14 組合優(yōu)化問題 8/815 計(jì)算復(fù)雜性的概念 1/11n 評(píng)價(jià)算法的好壞 —— 計(jì)算時(shí)間的多少、解的偏離程度n 例 非對(duì)稱距離 TSP問題的算法實(shí)現(xiàn)：所有路徑枚舉。這些具體值稱為 數(shù)據(jù) ；這些數(shù)據(jù)輸入計(jì)算機(jī)所占的空間稱為 實(shí)例的長度 （ size） .18 計(jì)算復(fù)雜性的概念 4/11 一類最優(yōu)化問題是由一些類似的具體問題（實(shí)例）組成的，每一個(gè)具體問題可表達(dá)成二元組（ F,C） .F為可行解集合 。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ù)雜性、解的效果。微粒群算法也是起源于對(duì)簡單社會(huì)系統(tǒng)的模擬，最初是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。從螞蟻系統(tǒng)開始，基本的蟻群算法得到了不斷的發(fā)展和完善，并在 TSP以及許多實(shí)際優(yōu)化問題求解中進(jìn)一步得到了驗(yàn)證。這種改進(jìn)型算法能夠以更快的速度獲得更好的解。 43 5/7 在對(duì) AS進(jìn)行直接完善的方法中， MAXMIN Ant System是一個(gè)典型代表。 46 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 1/5 隨著群智能理論和應(yīng)用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問題，并取得了意想不到的收獲。同時(shí)根據(jù)信息素?fù)]發(fā)機(jī)制實(shí)現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。 經(jīng)過多年的發(fā)展， ACO已成為能夠有效解決實(shí)際二次規(guī)劃問題的幾種重要算法之一。 為了說明蟻群算法的原理，先簡要介紹一下螞蟻搜尋食物的具體過程。最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。再經(jīng)過 36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為 24和 6，比值為 4： 1。同時(shí)，人工蟻群再選擇下一條路徑的時(shí)候是按一定算法規(guī)律有意識(shí)地尋找最短路徑，而不是盲目的。 螞蟻在尋找過程中，或者找到一個(gè)解后，會(huì)評(píng)估該解或解的一部分的優(yōu)化程度，并把評(píng)價(jià)信息保存在相關(guān)連接的信息素中。否則，若，則以概率 ， 到達(dá) j， ；若則到達(dá) 重復(fù) STEP 2。 算法中包括信息素更新的過程 1 信息素?fù)]發(fā)（ evaporation） 信息素痕跡的揮發(fā)過程是每個(gè)連接上的信息素痕跡的濃度自動(dòng)逐漸減弱的過程，由 表示，這個(gè)揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴(kuò)展。此時(shí)，觀察 GBAS的計(jì)算過程。由于螞蟻的一步轉(zhuǎn)移概率是隨機(jī)的，從 到 也是隨機(jī)的，是一個(gè)馬爾可夫過程。蟻群算法在解決這類問題時(shí)，只需要建立一個(gè)虛擬的始終點(diǎn)，就可以把 TSP問題的解法推廣，用于諸多的優(yōu)化問題。第 步按 TSP算法的轉(zhuǎn)移概率公式行走選擇 。 第三部分為問題的約束條件。 信息素的在線更新（異步更新方式）即螞蟻每行走一步，立即回溯并且更新行走路徑上的信息素。99 信息素的更改 4/6 GBAS算法是典型的離線信息素更新方式。蟻環(huán)離線更新方法很好地保證了殘留信息不至于無限積累，非最優(yōu)路徑會(huì)逐漸隨時(shí)間推移被忘記?；谖浵仭靶畔⑺乇?”來完成局部信息的刷新計(jì)算。本 書 可供人工智能、 計(jì) 算機(jī)科學(xué)、信息科學(xué)、控制工程、管理工程、交通工程、網(wǎng) 絡(luò) 工程、智能 優(yōu)化算法及智能自 動(dòng) 化等 領(lǐng) 域的廣大 師 生和科技人 員 學(xué)習(xí) 及參考。 參考文獻(xiàn)： 基于蟻群系統(tǒng)的分布式 RWA 算法研究 孫海金 , 朱　娜 , 周乃富 2022 年　第 2 期 光通信研究104 3/5 蟻群算法用于計(jì)算機(jī)網(wǎng)絡(luò)路由參考文獻(xiàn)：計(jì)算機(jī)網(wǎng)絡(luò)中的組播路由算法 謝銀祥 105 應(yīng)用 4/5106 5/5 蟻群算法用于聚類（蟻群蟻卵分類） 思想：把待聚類的數(shù)據(jù)隨機(jī)散布在一個(gè)平面上，放置若干只虛擬螞蟻使其在平面上隨機(jī)運(yùn)動(dòng)。研究 RWA 問題的目的是盡可能減少所需要的波長數(shù)和降低光路連接請(qǐng)求的阻塞率。相對(duì)而言，單螞蟻離線更新方式記憶信息少，只需要記憶第 s只螞蟻的路徑，并通過信息素更新后，釋放該螞蟻的所有記錄信息。 蟻群離線更新方式是在蟻群中的 m只螞蟻全部完成 n城市的訪問（第 k1次蟻群循環(huán)）后，統(tǒng)一對(duì)殘留信息進(jìn)行更新處理。94 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 系數(shù)的確定 3/3 殘留信息的相對(duì)重要程度 和預(yù)見值的相對(duì)重要程度 體現(xiàn)了相關(guān)信息痕跡和預(yù)見度對(duì)螞蟻決策的相對(duì)影響。91 解的表達(dá)形式與算法的實(shí)現(xiàn) 4/4 算法的實(shí)現(xiàn) 對(duì)蟻群重復(fù)以上過程，比較 m只螞蟻的裝包值 并記憶具有最大裝包值的螞蟻為 t。 TSP問題尋找的是最短回路，而一般優(yōu)化問題中， STEP 3 中的判斷條件 需要根據(jù)實(shí)際問題進(jìn)行修改。73 蟻群優(yōu)化算法 — 算法模型和收斂性分析 馬氏過程的收斂定義 GBAS算法的收斂性分析74 馬氏過程的收斂定義 蟻群優(yōu)化算法的每步迭代對(duì)應(yīng)隨機(jī)變量 其中 為信息素痕跡； 為 n城市的一個(gè)排列，最多有 個(gè)狀態(tài)。69 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 10/12重復(fù)外循環(huán)，由于上一次得到的 W2已經(jīng)是全局最優(yōu)解，因此按算法步驟 3的信息素更新規(guī)則，無論螞蟻如何行走，都只是對(duì) W2路線上的城市信息素進(jìn)行增強(qiáng)，其他的城市信息素進(jìn)行揮發(fā)。這種方式可以實(shí)現(xiàn)由單個(gè)螞蟻無法實(shí)現(xiàn)的集中行動(dòng)。比較 m只螞蟻中的路徑長度，記走最短路徑的螞蟻為 t。算法步驟如下：STEP 0 對(duì) n個(gè)城市的 TSP問題，城市間的距離矩陣為 ，給 TSP圖中的每一條弧 賦信息素初值 ，假設(shè) m只螞蟻在工作，所有螞蟻都從同一城市 出發(fā)。57 蟻群算法與 TSP問題 1/3TSP問題表示為一個(gè) N個(gè)城市的有向圖 G=（ N， A），其中 城市之間距離目標(biāo)函數(shù)為 ，其中