蟻群算法原理與應(yīng)用(已修改)
2025-05-29 06:21 本頁面
【正文】 1 自然計(jì)算與群體智能 趙林亮 計(jì)算機(jī)應(yīng)用技術(shù)研究所 2 蟻群算法 趙林亮 計(jì)算機(jī)應(yīng)用技術(shù)研究所 3 參考文獻(xiàn) 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。 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è)條件： 非對稱橋上的信息量與過去一個時間段內(nèi)經(jīng)過該橋的螞蟻數(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ì)算 ? 然后生成一個在區(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)式時間內(nèi)求解的判定問題 Π的集合。簡記為 O(p(n)) –即 P={L: 存在一個多項(xiàng)式時間 DTM程序 M，是的 L=LM} , 其中 LM表示程序 M所識別的語言。 –若存在一個多項(xiàng)式時間 DTM程序，它在編碼策略 e之下求解判定問題 Π，即 L[Π, e]∈ P,則稱該判定問題屬于 P類問題。 12 P、 NP、 NPC、 NPhard問題 ? NP類問題 (Nondeterministic Polynomial) –若存在一個多項(xiàng)式函數(shù) g(x) 和一個驗(yàn)證算法 H, 對一類判定問題 A的任何一個“是”回答，滿足其輸入長度 d(s)不超過 g(d(I)), 其中 d(I)為 I的輸入長度，且驗(yàn)證算法中 S為 I的“是”回答的計(jì)算時間不超過 g(d(I)), 則稱判定問題 A為非多項(xiàng)式確定問題。 – NP類問題是所有可用 NDTM (NonDeterministic onetape Turing Machine)在多項(xiàng)式時間內(nèi)求解的判定問題 Π的集合 13 P、 NP、 NPC、 NPhard問題 ? NPC類問題 (NPComplete) – 是 NP類中最困難的一類問題。 – 有重要實(shí)際意義和工程背景 – TSP (Traveling Salesman
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號-1