蟻群算法原理與應(yīng)用-wenkub
2023-05-24 06:21:46 本頁面
【正文】 的集合， dij(i, j=1,1,…,n) 是 lij的 Euclidean距離，即 ?22( ) ( )ij i j i jd x x y y? ? ? ?G=(C, L)是一個(gè)有向圖， TSP的目的是從有向圖 G中尋出長度最短的 Hamilton圈， 即一條對(duì) C={c1, c2, …, } 中 n個(gè)元素（城市）訪問且只訪問一次的最短封閉曲線 17 TSP (Traveling Salesman Problem) ? TSP簡單形象描述 給定 n個(gè)城市，一個(gè)旅行商從某一城市出發(fā)，訪問各城市一次且僅有一次后再回到原出發(fā)城市，要求找出一條最短的巡回路徑 可分為對(duì)稱 TSP (Symmetric Traveling Salesman Problem) 和非對(duì)稱 TSP (Asymmetric Traveling Salesman Problem) ? TSP是 NPC問題 ? n城市規(guī)模的 TSP，存在 (n1)!/2條不同閉合路徑。每只螞蟻僅根據(jù)其周圍的局部環(huán)境作出反應(yīng)，也只對(duì)周圍的局部環(huán)境產(chǎn)生影響； –螞蟻對(duì)環(huán)境的反應(yīng)由其內(nèi)部模式?jīng)Q定。 12 P、 NP、 NPC、 NPhard問題 ? NP類問題 (Nondeterministic Polynomial) –若存在一個(gè)多項(xiàng)式函數(shù) g(x) 和一個(gè)驗(yàn)證算法 H, 對(duì)一類判定問題 A的任何一個(gè)“是”回答，滿足其輸入長度 d(s)不超過 g(d(I)), 其中 d(I)為 I的輸入長度，且驗(yàn)證算法中 S為 I的“是”回答的計(jì)算時(shí)間不超過 g(d(I)), 則稱判定問題 A為非多項(xiàng)式確定問題。 ants can choose to go around it following one of the two different paths with equal probability. c) On the shorter path more pheromone is laid down. 5 Fig. 2. An example with artificial ants a) The initial graph with distances. b) At time t=0 there is no trail on the graph edges。 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. 6 雙橋?qū)嶒?yàn) (Goss S, 1989) Naturwissenschaften 76, 579581 (1989) Selfanized Shortcuts in the Argentine Ant S. Goss, S. Aron, J. L. Deneubourg, and J. M. Pasteels Unit of Behavioural Ecology, . 231, Universit6 Libre de Bruxelles, B 1050 Bruxelles 7 Fig. 1. A colony of I humilis selecting the short branches on both modules of the bridge a) one module of the bridge b) and c): photos taken 4 and 8 min after placement of the bridge 8 雙橋?qū)嶒?yàn)數(shù)學(xué)模型 ()()( ) ( )hAA hhABmkPmm k m k??? ? ?假設(shè)條件： 非對(duì)稱橋上的信息量與過去一個(gè)時(shí)間段內(nèi)經(jīng)過該橋的螞蟻數(shù)目成正比； 某一時(shí)刻螞蟻按照橋上殘留的信息量多少來選擇其中某座橋 經(jīng)過該橋的螞蟻數(shù)目越多則橋上的殘留信息量就越大 設(shè)短橋?yàn)?A，長橋?yàn)?B， mA和 mB分別表示經(jīng)過橋 A和橋 B的螞蟻數(shù)目 mA + mB = m 當(dāng)所有 m只螞蟻都經(jīng)過兩座橋之后，第 m+1只螞蟻選擇橋 A的概率為： 而選擇橋 B的概率為： ( ) 1 ( )BAP m P m??9 ? 參數(shù) h 和 k用以匹配真實(shí)實(shí)驗(yàn)數(shù)據(jù) ? 第 m+1只螞蟻首先計(jì)算 ? 然后生成一個(gè)在區(qū)間 [0,1]上均勻分布的隨機(jī)數(shù) ? 若 ，則選擇橋 A，否則選擇橋 B ()APm()APm???()APm? ?10 基本蟻群算法的數(shù)學(xué)模型 11 P、 NP、 NPC、 NPhard問題 ? P類問題 –所有可用 DTM (Deterministic onetape Turing Machine) 在多項(xiàng)式時(shí)間內(nèi)求解的判定問題 Π的集合。 – NP類問題是所有可用 NDTM (NonDeterministic onetape Turing Machine)在多項(xiàng)式時(shí)間內(nèi)求解的判定問題 Π的集合 13 P、 NP、 NPC、 NPhard問題 ? NPC類問題 (NPComplete) – 是 NP類中最困難的一類問題。即螞蟻是反應(yīng)型適應(yīng)性主體 –在個(gè)體水平上，每只螞蟻僅根據(jù)環(huán)境做出獨(dú)立選擇；在群體水平上，單只螞蟻的行為是隨機(jī)的，但蟻群可通過自組織過程形成高度有序的群體行為。 ?18 基本蟻群算法數(shù)學(xué)模型 ? 設(shè) bi(t)表示 t時(shí)刻位于元素 i的螞蟻數(shù)目， τij (t)為 t時(shí)刻路徑 (i, j)上的信息量， n表示 TSP規(guī)模， m為蟻群中螞蟻總數(shù)，則 是 t時(shí)刻集合 C中元素（城市）兩兩連接 lij上殘留信息量的集合，在初始時(shí)刻各條路徑上的信息量相等，并設(shè) τij(0)=const, 基本蟻群算法的尋優(yōu)是通過有向圖 g=(C, L, Γ)實(shí)現(xiàn)的。在 t時(shí)刻螞蟻 k由元素（城市） i轉(zhuǎn)移到元素（城市） j的狀態(tài)轉(zhuǎn)移概率： [ ( ) ] [ ( ) ], i f
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1