aai51自然計算及群體智能-資料下載頁
2025-05-07 18:02本頁面
【正文】 PC NPhard ?NP P NPhard NPC 48 基本蟻群算法模型 ? 基本假設 – 螞蟻之間通過信息素和環(huán)境進行通信。每只螞蟻僅根據(jù)其周圍的局部環(huán)境作出反應，也只對周圍的局部環(huán)境產(chǎn)生影響； – 螞蟻對環(huán)境的反應由其內(nèi)部模式?jīng)Q定。即螞蟻是反應型適應性主體 – 在個體水平上，每只螞蟻僅根據(jù)環(huán)境做出獨立選擇；在群體水平上，單只螞蟻的行為是隨機的，但蟻群可通過自組織過程形成高度有序的群體行為。 49 TSP (Traveling Salesman Problem) ? 有向圖 – 有向圖 D的三元組為 (V, E, f)，其中 V是一個非空集合，其元素稱為有向圖的結點； E是一個集合，其元素稱為有向圖的弧段（邊）； f是從E到 VxV上的一個映射（函數(shù)）。 – E中的元素總是和 V中的序偶對有對應關系，可用 V中的序偶代替 E中的元素。 – 一個有向圖Ｄ可簡記為 (V, E). 50 TSP (Traveling Salesman Problem) ? TSP 設 C={c1, c2, …, } 是 n個城市的集合， L={lij|ci, cj C}是集合 C中的元素（城市）兩兩連接的集合， dij(i, j=1,1,…,n) 是 lij的 Euclidean距離，即 ?22( ) ( )i j i j i jd x x y y? ? ? ?G=(C, L)是一個有向圖， TSP的目的是從有向圖 G中尋出長度最短的 Hamilton圈， 即一條對 C={c1, c2, …, } 中 n個元素（城市）訪問且只訪問一次的最短封閉曲線 51 TSP (Traveling Salesman Problem) ? TSP簡單形象描述 給定 n個城市，一個旅行商從某一城市出發(fā)，訪問各城市一次且僅有一次后再回到原出發(fā)城市，要求找出一條最短的巡回路徑 可分為對稱 TSP (Symmetric Traveling Salesman Problem) 和非對稱 TSP (Asymmetric Traveling Salesman Problem) ? TSP是 NPC問題 ? n城市規(guī)模的 TSP，存在 (n1)!/2條不同閉合路徑。 ?52 蟻群算法 時間 ： 20世紀 90年代 地點 ： 意大利 人物 ： 意大利 M． Dorigo， V． Maniezzo， A． Colorni 目的 ： 模擬自然界螞蟻搜索路徑的行為， 結果 ： 群體智能理論 應用 ： 求解 NP問題 （ TSP問題、分配問題、 jobshop調(diào)度問題）， 解復雜優(yōu)化問題（離散優(yōu)化問題）有優(yōu)勢 53 應用領域 ?解決大多數(shù)優(yōu)化問題 ?或轉(zhuǎn)化為優(yōu)化求解的問題。 ?分類、聚類、模式識別、 ?多目標優(yōu)化、 ?QoS、 ?流程規(guī)劃 ?信號處理 ?機器人控制、 ?決策支持 54 背景 群體智能理論包括： 微粒群算法， Particle Swarm Optimization, PSO 魚群 鳥群 追尾 ? 蟻群算法 (Ant Colony Optimization, ACO) ? 簡單社會系統(tǒng)的模擬 55 蟻群優(yōu)化算法研究背景 與傳統(tǒng)進化算法 梯度算法的差異 ：， 概率搜索 1 并行 +分布 ， 無中控， 個別螞蟻死亡 無關大局 2 因而程序 堅固 。 3 非直接 信息交流 ，（廣播） 4 可處理 離散 對象 5 實現(xiàn)簡單 56 實現(xiàn)簡單 算法中僅涉及各種基本的數(shù)學操作， 對 CPU和內(nèi)存的要求不高。 只輸出：目標函數(shù)值， 無需梯度信息。（導數(shù)，微分）
環(huán)評公示相關推薦
鄂ICP備17016276號-1