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