蟻群算法原理與應用-展示頁
2025-05-25 06:21本頁面
【正文】 rail is stronger on shorter edges, which are therefore, in the average, preferred by ants. 6 雙橋?qū)嶒?(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ū)嶒灁?shù)學模型 ()()( ) ( )hAA hhABmkPmm k m k??? ? ?假設條件： 非對稱橋上的信息量與過去一個時間段內(nèi)經(jīng)過該橋的螞蟻數(shù)目成正比； 某一時刻螞蟻按照橋上殘留的信息量多少來選擇其中某座橋 經(jīng)過該橋的螞蟻數(shù)目越多則橋上的殘留信息量就越大 設短橋為 A，長橋為 B， mA和 mB分別表示經(jīng)過橋 A和橋 B的螞蟻數(shù)目 mA + mB = m 當所有 m只螞蟻都經(jīng)過兩座橋之后，第 m+1只螞蟻選擇橋 A的概率為： 而選擇橋 B的概率為： ( ) 1 ( )BAP m P m??9 ? 參數(shù) h 和 k用以匹配真實實驗數(shù)據(jù) ? 第 m+1只螞蟻首先計算 ? 然后生成一個在區(qū)間 [0,1]上均勻分布的隨機數(shù) ? 若 ，則選擇橋 A，否則選擇橋 B ()APm()APm???()APm? ?10 基本蟻群算法的數(shù)學模型 11 P、 NP、 NPC、 NPhard問題 ? P類問題 –所有可用 DTM (Deterministic onetape Turing Machine) 在多項式時間內(nèi)求解的判定問題 Π的集合。1 自然計算與群體智能 趙林亮 計算機應用技術研究所 2 蟻群算法 趙林亮 計算機應用技術研究所 3 參考文獻 APPEARED IN PROCEEDINGS OF ECAL91EUROPEAN CONFERENCE ON ARTIFICIAL LIFE, PARIS, FRANCE, ELSEVIER PUBLISHING,134–142. Distributed Optimization by Ant Colonies Alberto Colorni, Marco Dorigo, Vittorio Maniezzo Dipartimento di Elettronica, Politeico di Milano Piazza Leonardo da Vinci 32, 20213 Milano, Italy IEEE Transactions on Systems, Man, And Cyberics Part B: Cyberics, , Feb 1996. 2941 Ant System: Optimization by a Colony of Cooperating Agents Marco Dorigo, Member, IEEE, Vittorio Maniezzo, and Alberto Colorni 4 Fig. 1. An example with real ants a) Ants follow a path between points A and E. b) An obstacle is interposed。 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。簡記為 O(p(n)) –即 P={L: 存在一個多項式時間 DTM程序 M，是的 L=LM} , 其中 LM表示程序 M所識別的語言。 12 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為非多項式確定問題。 – 有重要實際意義和工程背景 – TSP (Traveling Salesman Problem) ? Symmetric。每只螞蟻僅根據(jù)其周圍的局部環(huán)境作出反應，也只對周圍的局部環(huán)境產(chǎn)生影響； –螞蟻對環(huán)境的反應由其內(nèi)部模式?jīng)Q定。 15 TSP (Traveling Salesman Problem) ? 有向圖 –有向圖 D的三元組為 (V, E, f)，其中 V是一個非空集合，其元素稱為有向圖的結(jié)點； E是一個集合，其元素稱為有向圖的弧段（邊）； f是從E到 VxV上的一個映射（函數(shù)）。 –一個有向圖Ｄ可簡記為 (V, E). 16 TSP (Traveling Salesman Problem) ? TSP 設 C={c1, c2, …, } 是 n個城市的集合， L=
研究報告相關推薦
鄂ICP備17016276號-1