【正文】 logy, . 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)求解的判定問題 Π的集合。 –一個(gè)有向圖Ｄ可簡記為 (V, E). 16 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( ) ( )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條不同閉合路徑。 (3)螞蟻的禁忌表索引號(hào) k=1。 34 ? QoS指標(biāo)： – 帶寬 ? 單位時(shí)間內(nèi)能夠在線路上傳送的數(shù)據(jù)量， bps(bit per second)。, : the p r oc e ss de l a y , l oss r a t e o f n od e .rrrsN D N L r46 限制函數(shù) F的定義 121112 2 3112( ) ( ) ( )W he r e i s t he node num be r , A , B a nd C a r e posi t i v e r e a l c oe f f i c i e nt s.H( Z ) =0, if Z 0, othe r wis e H( Z ) =Z .(VVdij ijijjiNNijijjidij ij ij wwF F FF L C PF A H Z B H Z C H ZNZ P L B BZ D L??????? ? ??? ? ?????????31)( 1 ) ( 1 )ddij ij i iNdi i wiD P N N DZ N N L L??? ? ? ?? ? ??47 信息素的全局更新規(guī)則 ? 式中， N表示網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目； A、 B和 C分別表示帶寬可用限制、端到端時(shí)延限制和端到端丟失率限制，且為正實(shí)數(shù)； ? F1表示費(fèi)用限制； F2表示 QoS限制。 ? (3)根據(jù) level1節(jié)點(diǎn)的相鄰關(guān)系，選最少level1節(jié)點(diǎn)數(shù)的路由 (稱為 level1路由 )。每個(gè)路由器即為一個(gè)level0節(jié)點(diǎn)，由多個(gè) level0節(jié)點(diǎn)和 level0鏈路形成的 LAN稱為 level1節(jié)點(diǎn)， level1節(jié)點(diǎn)之間通過 level1鏈路連接。 ? pi (r, s) represents the probability with which the ith ant positioned on node r chooses the next node s, ? phero(i, r, s) the amount of pheromone deposited on the edge between the nodes r and s currently by the ith type of ants, ? Ji(r) the nodes between which and the node r there is an edge and by which the ithtype ant has not passed during its choosing path. 43 信息素局部更新規(guī)則 ? 對(duì)于第 i只螞蟻，如果節(jié)點(diǎn) r, s是該螞蟻所選路徑上的兩個(gè)相鄰節(jié)點(diǎn)，則信息素 phero(i, r, s)用下式來調(diào)節(jié)；否則，不調(diào)節(jié)。當(dāng)網(wǎng)絡(luò)過載或擁塞時(shí)， QoS 能確保