【正文】 式算法模型，可充分利用多 處 理器 4 對(duì)問題 定 義 的 連續(xù) 性無特殊要求 5 算法 實(shí)現(xiàn)簡(jiǎn)單 38 蟻群優(yōu)化算法研究背景 3/3 群智能方法易于實(shí)現(xiàn)，算法中僅涉及各種基本的數(shù)學(xué)操作，其數(shù)據(jù)處理過程對(duì) CPU和內(nèi)存的要求也不高。微粒群算法也是起源于對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬，最初是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。36 蟻群優(yōu)化算法研究背景 1/3 群智能理論研究領(lǐng)域有兩種主要的算法：蟻群算法 (Ant Colony Optimization, ACO)和微粒群算法（ Particle Swarm Optimization, PSO）。用該方法求解 TSP問題、分配問題、 jobshop調(diào)度問題，取得了較好的試驗(yàn)結(jié)果．雖然研究時(shí)間不長，但是現(xiàn)在的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問題（特別是離散優(yōu)化問題）方面有一定優(yōu)勢(shì)，表明它是一種有發(fā)展前景的算法．35 蟻群優(yōu)化算法應(yīng)用領(lǐng)域 這種方法能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉(zhuǎn)化為優(yōu)化求解的問題。提出了許多用以解決復(fù)雜優(yōu)化問題的新方法，如進(jìn)化規(guī)劃、進(jìn)化策略、遺傳算法等，這些算法成功地解決了一些實(shí)際問題。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ù)雜性、解的效果。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)單，易修改。24 計(jì)算復(fù)雜性的概念 10/11n 利用復(fù)雜性分析對(duì)組合優(yōu)化問題歸類。問題是在 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)系。這些具體值稱為 數(shù)據(jù) ；這些數(shù)據(jù)輸入計(jì)算機(jī)所占的空間稱為 實(shí)例的長度 （ size） .18 計(jì)算復(fù)雜性的概念 4/11 一類最優(yōu)化問題是由一些類似的具體問題（實(shí)例）組成的，每一個(gè)具體問題可表達(dá)成二元組（ F,C） .F為可行解集合 ?？梢詮膬煞矫婷枋觯? （ 1）對(duì)所有參數(shù)的一般性描述； （ 2）答案（或解）必須滿足的性質(zhì)。以目前二進(jìn)制計(jì)算機(jī)中的存儲(chǔ)和計(jì)算為基礎(chǔ)，以理論的形式系統(tǒng)描述，是評(píng)估算法性能的基礎(chǔ)。到 31個(gè)城市時(shí)，要計(jì)算 325年。 14 組合優(yōu)化問題 8/815 計(jì)算復(fù)雜性的概念 1/11n 評(píng)價(jià)算法的好壞 —— 計(jì)算時(shí)間的多少、解的偏離程度n 例 非對(duì)稱距離 TSP問題的算法實(shí)現(xiàn)：所有路徑枚舉。 問題描述：一商人去 n個(gè)城市銷貨，所有城市走一遍再回到起點(diǎn)，使所走路程最短。通過數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，可以涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸和通信網(wǎng)絡(luò)等許多方面。1算法設(shè)計(jì)與分析 第七章補(bǔ)充材料 蟻群算法介紹山東師范大學(xué)計(jì)算機(jī)系授課：徐連誠， 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ì)論、庫存論、對(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é)模型：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年首先提出，國際上稱之為中國郵遞員問題。12 組合優(yōu)化問題 6/813 組合優(yōu)化問題 7/8例 3 裝箱問題（ bin packing） 尺寸為 1的箱子有若干個(gè)，怎樣用最少的箱子裝下 n個(gè)尺寸不超過 1 的物品，物品集合為： 。 計(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í)間增加很快。描述算法的好壞 —— 計(jì)算復(fù)雜性 —— 討論計(jì)算時(shí)間與問題規(guī)模之間的關(guān)系。17 計(jì)算復(fù)雜性的概念 3/11n 問題 （ problem） ： 要回答的一般性提問，通常含有若干個(gè)滿足一定條件的參數(shù)（或自由變量）。n 實(shí)例 （ instance） :給問題的所有參數(shù)指定具體值，得到問題的一個(gè)實(shí)例。C是費(fèi)用函數(shù)，是由 F到 R（ 實(shí)數(shù)集）的映像。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í)例的輸入長度：n 實(shí)例的輸入長度是 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í)間算法。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)論， 作者：堵丁柱等，