【正文】 1算法設(shè)計(jì)與分析 第七章補(bǔ)充材料 蟻群算法介紹山東師范大學(xué)計(jì)算機(jī)系授課：徐連誠(chéng)， 3432， 2022年 9月 5日 — 2022年 1月 20日2內(nèi) 容一、啟發(fā)式方法概述二、蟻群優(yōu)化算法3背 景n 傳統(tǒng)實(shí)際問題的特點(diǎn) 連續(xù)性問題 —— 主要以微積分為基礎(chǔ)，且問題規(guī)模較小n 傳統(tǒng)的優(yōu)化方法 追求準(zhǔn)確 —— 精確解 理論的完美 —— 結(jié)果漂亮 主要方法：線性與非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī)劃等；排隊(duì)論、庫(kù)存論、對(duì)策論、決策論等。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é)分支。通過數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，可以涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸和通信網(wǎng)絡(luò)等許多方面。 數(shù)學(xué)模型：8 組合優(yōu)化問題 2/8組合優(yōu)化問題的三參數(shù)表示： 9 組合優(yōu)化問題 3/8n 例 1 01背包問題（ 01 knapsack problem）10 組合優(yōu)化問題 4/811 組合優(yōu)化問題 5/8n 例 2 旅行商問題（ TSP,traveling salesman problem） 管梅谷教授 1960年首先提出，國(guó)際上稱之為中國(guó)郵遞員問題。 問題描述：一商人去 n個(gè)城市銷貨，所有城市走一遍再回到起點(diǎn)，使所走路程最短。12 組合優(yōu)化問題 6/813 組合優(yōu)化問題 7/8例 3 裝箱問題（ bin packing） 尺寸為 1的箱子有若干個(gè)，怎樣用最少的箱子裝下 n個(gè)尺寸不超過 1 的物品，物品集合為： 。 14 組合優(yōu)化問題 8/815 計(jì)算復(fù)雜性的概念 1/11n 評(píng)價(jià)算法的好壞 —— 計(jì)算時(shí)間的多少、解的偏離程度n 例 非對(duì)稱距離 TSP問題的算法實(shí)現(xiàn)：所有路徑枚舉。 計(jì)算時(shí)間： n個(gè)城市，固定 1個(gè)為起終點(diǎn)需要 (n1)!個(gè)枚舉，設(shè)計(jì)算機(jī) 1秒能完成 24個(gè)城市的枚舉，則城市數(shù)與計(jì)算時(shí)間的關(guān)系如下表：16 計(jì)算復(fù)雜性的概念 2/11城市數(shù)24 25 26 27 28 29 30 31計(jì)算時(shí)間1sec24sec10minhourdaydayyear325year隨城市增多，計(jì)算時(shí)間增加很快。到 31個(gè)城市時(shí)，要計(jì)算 325年。描述算法的好壞 —— 計(jì)算復(fù)雜性 —— 討論計(jì)算時(shí)間與問題規(guī)模之間的關(guān)系。以目前二進(jìn)制計(jì)算機(jī)中的存儲(chǔ)和計(jì)算為基礎(chǔ)，以理論的形式系統(tǒng)描述，是評(píng)估算法性能的基礎(chǔ)。17 計(jì)算復(fù)雜性的概念 3/11n 問題 （ problem） ： 要回答的一般性提問，通常含有若干個(gè)滿足一定條件的參數(shù)（或自由變量）?？梢詮膬煞矫婷枋觯? （ 1）對(duì)所有參數(shù)的一般性描述； （ 2）答案（或解）必須滿足的性質(zhì)。n 實(shí)例 （ instance） :給問題的所有參數(shù)指定具體值，得到問題的一個(gè)實(shí)例。這些具體值稱為 數(shù)據(jù) ；這些數(shù)據(jù)輸入計(jì)算機(jī)所占的空間稱為 實(shí)例的長(zhǎng)度 （ size） .18 計(jì)算復(fù)雜性的概念 4/11 一類最優(yōu)化問題是由一些類似的具體問題（實(shí)例）組成的，每一個(gè)具體問題可表達(dá)成二元組（ F,C） .F為可行解集合 。C是費(fèi)用函數(shù)，是由 F到 R（ 實(shí)數(shù)集）的映像。問題是在 F中找到一個(gè)點(diǎn) f*，使對(duì) F中任意的 f，有 C(f*) C(f),稱 f*為這一具體問題的最優(yōu)解（或全局最優(yōu)解） .19 計(jì)算復(fù)雜性的概念 5/11n 算法計(jì)算量的度量： 加、減、乘、除、比較的總運(yùn)算次數(shù)與實(shí)例的計(jì)算機(jī)計(jì)算時(shí)的二進(jìn)制輸入數(shù)據(jù)的大小關(guān)系。n 正整數(shù) x的二進(jìn)制位數(shù)是 :(整數(shù)到二進(jìn)制的轉(zhuǎn)換 ) 20 計(jì)算復(fù)雜性的概念 6/11n 算法計(jì)算量的度量之例 —— TSP枚舉法計(jì)算量的統(tǒng)計(jì)：21 計(jì)算復(fù)雜性的概念 7/11n 實(shí)例的輸入長(zhǎng)度：n 實(shí)例的輸入長(zhǎng)度是 n的多項(xiàng)式函數(shù)n 枚舉法的基本計(jì)算量是 n的階乘函數(shù)， 隨 n的增加，比指數(shù)函數(shù)增加得還快 .22 計(jì)算復(fù)雜性的概念 8/1123 計(jì)算復(fù)雜性的概念 9/11定義 多項(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í)間算法。24 計(jì)算復(fù)雜性的概念 10/11n 利用復(fù)雜性分析對(duì)組合優(yōu)化問題歸類。n 定義 多項(xiàng)式問題 給定一個(gè)組合優(yōu)化問題，若存在一個(gè)多項(xiàng)式算法，稱該問題為多項(xiàng)式時(shí)間可解問題，或簡(jiǎn)稱 多項(xiàng)式問題 (或 P問題 ). 所有多項(xiàng)式問題的集合記為 P.n 例：線性規(guī)劃是否為多項(xiàng)式問題？25 計(jì)算復(fù)雜性參考書 11/11n 計(jì)算復(fù)雜性 , 作者： Christos， Papadimitriou清華大學(xué)出版社， 2022年 9月 第 1版n 計(jì)算復(fù)雜性導(dǎo)論， 作者：堵丁柱等， 高等教育出版社， 2022年 8月第 1版26 啟發(fā)式算法 _定義 1/6n 啟發(fā)式算法（ heuristic algorithm）n 定義 1. 基于 直觀或經(jīng)驗(yàn) 構(gòu)造的算法，在可接受的花費(fèi)（時(shí)間、空間）下，給出待解組合優(yōu)化問題的每個(gè)實(shí)例的一個(gè) 可行解 ，該可行解與最優(yōu)解偏差事先不一定可以預(yù)計(jì) .n 定義 2. 啟發(fā)式算法是一種技術(shù)，在可接受的計(jì)算費(fèi)用內(nèi)尋找最好解，但不保證該解的可行性與最優(yōu)性，無法描述該解與最優(yōu)解的近似程度。n 特點(diǎn)（與傳統(tǒng)優(yōu)化方法不同）： 憑直觀和經(jīng)驗(yàn)給出算法；不考慮所得解與最優(yōu)解的偏離程度 .27 啟發(fā)式算法 _優(yōu)點(diǎn) 2/6 優(yōu)點(diǎn)：（ 1）有可能比簡(jiǎn)化數(shù)學(xué)模型解的誤差??；（ 2）對(duì)有些難題，計(jì)算時(shí)間可接受；（ 3）可用于某些最優(yōu)化算法（如分支定界算 法）之中的估界；（ 4）直觀易行；（ 5）速度較快；（ 6）程序簡(jiǎn)單，易修改。28 啟發(fā)式算法 _不足 3/6不足：（ 1）不能保證求得全局最優(yōu)解；（ 2）解的精度不穩(wěn)定，有時(shí)好有時(shí)壞；（ 3）算法設(shè)計(jì)與問題、設(shè)計(jì)者經(jīng)驗(yàn)、技術(shù) 有關(guān)，缺乏規(guī)律性；（ 4）不同算法之間難以比較。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ù)雜性、解的效果。 (2）概率分析 （ probability analysis） 用最壞情況分析，會(huì)因一個(gè)最壞實(shí)例影響總體評(píng)價(jià) . 在實(shí)例數(shù)據(jù)服從一定概率分布情形下，研究算法復(fù)雜性和解的效果 . (3)大規(guī)模計(jì)算分析 通過大量實(shí)例計(jì)算，評(píng)價(jià)算法效果 .n 注意數(shù)據(jù)的隨機(jī)性和代表性 .322 蟻群優(yōu)化算法1. 蟻群優(yōu)化算法概述2. 蟻群優(yōu)化算