aai51自然計算及群體智能(存儲版)
【正文】 C短， M1回到 A點時， M2 才到 C點。 therefore, ants choose whether to turn right or left with equal probability. c) At time t=1 trail is stronger on shorter edges, which are therefore, in the average, preferred by ants. 37 要點 ? 螞蟻群居群動，很少有獨行俠， ? 選擇 信息素濃的路徑 ， 喜歡熱鬧， ? 追求蟻氣（人氣） ? 人也類似。每只螞蟻僅根據(jù)其周圍的局部環(huán)境作出反應(yīng)，也只對周圍的局部環(huán)境產(chǎn)生影響； – 螞蟻對環(huán)境的反應(yīng)由其內(nèi)部模式?jīng)Q定。 只輸出：目標函數(shù)值， 無需梯度信息。 – 一個有向圖Ｄ可簡記為 (V, E). 50 TSP (Traveling Salesman Problem) ? TSP 設(shè) 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條不同閉合路徑。 46 P、 NP、 NPC、 NPhard問題 ? NP類問題 (Nondeterministic Polynomial) – 若存在一個多項式函數(shù) g(x) 和一個驗證算法 H, 對一類判定問題 A的任何一個“是”回答，滿足其輸入長度 d(s)不超過 g(d(I)), 其中 d(I)為 I的輸入長度，且驗證算法中 S為 I的“是”回答的計算時間不超過 g(d(I)), 則稱判定問題 A為非多項式確定問題。 沒有集中的指揮 ? 無所作為 ? 蟻群，復雜的社會行為： – 協(xié)同工作 – 筑巢、覓食、遷徙、清掃蟻巢、撫養(yǎng)后代 – 依靠群體能力發(fā)揮出超出個體的智能 28 蟻群算法特點 ? 模擬螞蟻群體智能行為的仿生優(yōu)化算法 ? 較強的魯棒性 ? 優(yōu)良的分布式計算機制 ? 易于與其它方法結(jié)合 29 螞蟻的生物學特征 ? 別稱：玄駒、蚍蜉、狀元子 ? 屬 節(jié)肢動物門 ， 昆蟲綱 ， 膜翅目 ， 蟻科 ? 在昆蟲界種類最多，生存量最大 ? 約 260屬， 16000多種，已命名的 9000多種 ? 拖動 1400自重的食物 ? 舉起自重 400倍的物體 ? 起源于 1億年前的恐龍時代 30 螞蟻的社會形態(tài) ? 蟻后、雄蟻、工蟻、兵蟻 ? 信息交流方式：化學通信 ? 分泌化學刺激物：信息素 (pheromone) ? 彼此平等，利他主義 ? 個體協(xié)作，協(xié)調(diào)一致 ? 共和國 31 螞蟻的群體行為 ? 螞蟻個體簡單 ? 群體：高度機構(gòu)化的社會組織 ? 遠超螞蟻個體能力 ? 行為 1：覓食 – 食物隨機散布 – 找到
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1