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