蟻群算法及其應(yīng)用.ppt

1、1,蟻群算法及其應(yīng)用,2,啟發(fā)式算法_分類,現(xiàn)代優(yōu)化算法： 80年代初興起 禁忌搜索（tabu search） 模擬退火（simulated annealing） 神經(jīng)網(wǎng)絡(luò)（neural networks） 遺傳算法（genetic algorithms） 螞蟻算法（Ant Algorithm，群體智能，Swarm Intelligence）,3,遺傳算法,遺傳算法(GeneticAlgorithm,GA)是1962年密切根大學(xué)Holland教授首次提出的一種全局優(yōu)化算法，它借用了生物遺傳學(xué)的觀點(diǎn)，通過自然選擇、遺傳、變異等作用機(jī)制，實(shí)現(xiàn)各個(gè)體的適應(yīng)性的提高，并迅速推廣到優(yōu)化、搜索、機(jī)器學(xué)習(xí)等

2、方面。,4,遺傳算法的過程,5,蟻群算法,1 原理 2 在TSP中的應(yīng)用及改進(jìn) 3 在QoS多播路由中的應(yīng)用,6,1 蟻群算法原理,20 世紀(jì)90 年代初，意大利學(xué)者Dorigo 等受螞蟻覓食行為的啟發(fā)，提出了蟻群算法，是一種仿生算法。 螞蟻在覓食過程中可以找出巢穴到食物源的最短路徑，為什么？ （1）信息素(pheromone) （2）正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。,7,簡化的螞蟻尋食過程,螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過9個(gè)時(shí)間單位時(shí)的情形：走ABD的

3、螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。,8,簡化的螞蟻尋食過程,經(jīng)過18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。,9,自然蟻群與人工蟻群,相似之處在于：都是優(yōu)先選擇信息素濃度大的路徑。 兩者的區(qū)別： （1）在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)。 （2）人工蟻群選擇路徑時(shí)不是盲目的。而是按一定規(guī)律有意識(shí)地尋找最短路徑。例如，在TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。,10,應(yīng)用一：TSP問題,旅行商問題（TSP,traveling salesman problem）1960年首先提出。

4、問題描述： 一商人去n個(gè)城市銷貨，所有城市走一遍再回到起點(diǎn)，使所走路程最短。 TSP在許多工程領(lǐng)域具有廣泛的應(yīng)用價(jià)值 例如電路板布線、VLSI芯片設(shè)計(jì)、機(jī)器人控制、交通路由等。 TSP的求解是NP-hard問題。隨著城市數(shù)目的增多,問題空間將呈指數(shù)級增長。,11,TSP問題的數(shù)學(xué)描述,TSP問題表示為一個(gè)N個(gè)城市的有向圖G=（N，A），其中 城市之間距離 目標(biāo)函數(shù)為 其中， ，為城市1,2，n的 一個(gè)排列， 。,12,螞蟻算法求解TSP,下面以TSP為例說明基本蟻群算法模型。 首先將m只螞蟻隨機(jī)放置在n個(gè)城市，位于城市i的第k只螞蟻選擇下一個(gè)城市j的概率為:,13,螞蟻算法求解TSP,其中：

5、表示邊（i，j）上的信息素濃度； 是啟發(fā)信息，d是城市i和j之間的距離； 和反映了信息素與啟發(fā)信息的相對重要性； 表示螞蟻k已經(jīng)訪問過的城市列表。 當(dāng)所有螞蟻完成周游后，按以下公式進(jìn)行信息素更新。,14,螞蟻算法求解TSP,其中：為小于1的常數(shù)，表示信息的持久性。,其中：Q為常數(shù)；lk表示第k只螞蟻在本次迭代中走過的路徑，Lk為路徑長度。,15,求解TSP算法步驟,初始化隨機(jī)放置螞蟻，為每只螞蟻建立禁忌表tabuk，將初始節(jié)點(diǎn)置入禁忌表中; 迭代過程 k=1 while k=ItCount do (執(zhí)行迭代) for i = 1 to m do (對m只螞蟻循環(huán)) for j = 1 to n

6、 - 1 do (對n個(gè)城市循環(huán)) 根據(jù)式(1)，采用輪盤賭方法在窗口外選擇下一個(gè)城市j; 將j置入禁忌表,螞蟻轉(zhuǎn)移到j(luò); end for end for 計(jì)算每只螞蟻的路徑長度; 根據(jù)式(2)更新所有螞蟻路徑上的信息量; k = k + 1; end while 輸出結(jié)果,結(jié)束算法.,16,蟻群的規(guī)模和停止規(guī)則,一、蟻群大小 一般情況下蟻群中螞蟻的個(gè)數(shù)不超過TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。 二、終止條件 1 給定一個(gè)外循環(huán)的最大數(shù)目； 2 當(dāng)前最優(yōu)解連續(xù)K次相同而停止，其中K是一個(gè)給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)。,17,螞蟻算法的缺點(diǎn),螞蟻算法的缺點(diǎn)： 1）收斂速度慢 2）易于陷入局部最優(yōu)

7、 改進(jìn)： 1）采用局部優(yōu)化，設(shè)計(jì)了三種優(yōu)化算子。 2）采用蟻群優(yōu)化算法。 3）其它優(yōu)化算法,18,改進(jìn)一：局部優(yōu)化（算子1 ）,19,對Kroa100，算子1優(yōu)化前后的路徑如圖所示。優(yōu)化前（28596），算子1優(yōu)化后（26439）,20,改進(jìn)一：局部優(yōu)化（算子2 ）,21,對Kroa100，算子2優(yōu)化前后的路徑如圖所示。算子1（26439），算子2優(yōu)化后（23012）,22,TSP具有鄰域特征，設(shè)置候選窗口，窗口大小應(yīng)取一個(gè)合理值。 螞蟻總是優(yōu)先選擇候選窗口中的城市。搜索結(jié)束后，根據(jù)候選窗口對路徑進(jìn)行優(yōu)化，如果將候選窗口內(nèi)的節(jié)點(diǎn)交換到當(dāng)前節(jié)點(diǎn)附近后距離更短，則進(jìn)行變異。,改進(jìn)一：局部優(yōu)化（算子

8、3 ）,23,對Kroa100，算子3優(yōu)化前后的路徑如圖所示。（23012），算子3優(yōu)化后（21282）,24,收斂特性對比,25,改進(jìn)二：蟻群優(yōu)化算法,1)ACS采用了更為大膽的行為選擇規(guī)則，在城市r的螞蟻k轉(zhuǎn)移到城市s的規(guī)則為:,26,2.1.4蟻群優(yōu)化算法,第三，僅對全局最優(yōu)解邊上的信息素進(jìn)行加強(qiáng)，更新如下:,27,其它改進(jìn),1）精英策略 2）基于排序的螞蟻系統(tǒng) 3） MAX-MIN螞蟻系統(tǒng),28,應(yīng)用二：QoS多播路由問題,什么是多播路由？ 構(gòu)造一棵費(fèi)用最小的多播樹，且滿足以下限制條件： (1) d(T(s, D)D （延時(shí)） (2) dj(T(s, D)DJ （抖動(dòng)） (3) pl(T(s, D)PL （丟包率） (4) b(T(s, D)B. （帶寬）,29,路徑的QoS參數(shù)計(jì)算,30,