蟻群算法及其應(yīng)用講座課件

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

2、、機(jī)器學(xué)習(xí)等方面。3第3頁(yè)，共34頁(yè)。遺傳算法的過(guò)程 編碼和初始群體生成個(gè)體適應(yīng)度的評(píng)測(cè)(適值函數(shù) )選擇交叉變異4第4頁(yè)，共34頁(yè)。蟻群算法1 原理2 在TSP中的應(yīng)用及改進(jìn)3 在QoS多播路由中的應(yīng)用5第5頁(yè)，共34頁(yè)。1 蟻群算法原理20 世紀(jì)90 年代初，意大利學(xué)者Dorigo 等受螞蟻覓食行為的啟發(fā)，提出了蟻群算法，是一種仿生算法。螞蟻在覓食過(guò)程中可以找出巢穴到食物源的最短路徑，為什么？（1）信息素(pheromone)（2）正反饋現(xiàn)象：某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。6第6頁(yè)，共34頁(yè)。簡(jiǎn)化的螞蟻尋食過(guò)程螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路

3、線ABD或ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過(guò)9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。7第7頁(yè)，共34頁(yè)。簡(jiǎn)化的螞蟻尋食過(guò)程經(jīng)過(guò)18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。8第8頁(yè)，共34頁(yè)。自然蟻群與人工蟻群相似之處在于：都是優(yōu)先選擇信息素濃度大的路徑。兩者的區(qū)別：（1）在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)。（2）人工蟻群選擇路徑時(shí)不是盲目的。而是按一定規(guī)律有意識(shí)地尋找最短路徑。例如，在TSP問(wèn)題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地

4、的距離。9第9頁(yè)，共34頁(yè)。應(yīng)用一：TSP問(wèn)題旅行商問(wèn)題（TSP,traveling salesman problem）1960年首先提出。問(wèn)題描述：一商人去n個(gè)城市銷貨，所有城市走一遍再回到起點(diǎn)，使所走路程最短。TSP在許多工程領(lǐng)域具有廣泛的應(yīng)用價(jià)值例如電路板布線、VLSI芯片設(shè)計(jì)、機(jī)器人控制、交通路由等。TSP的求解是NP-hard問(wèn)題。隨著城市數(shù)目的增多,問(wèn)題空間將呈指數(shù)級(jí)增長(zhǎng)。 10第10頁(yè)，共34頁(yè)。TSP問(wèn)題的數(shù)學(xué)描述TSP問(wèn)題表示為一個(gè)N個(gè)城市的有向圖G=（N，A），其中城市之間距離目標(biāo)函數(shù)為其中， ，為城市1,2，n的一個(gè)排列， 。11第11頁(yè)，共34頁(yè)。螞蟻算法求解TSP下面

5、以TSP為例說(shuō)明基本蟻群算法模型。首先將m只螞蟻隨機(jī)放置在n個(gè)城市，位于城市i的第k只螞蟻選擇下一個(gè)城市j的概率為: 12第12頁(yè)，共34頁(yè)。螞蟻算法求解TSP其中：表示邊（i，j）上的信息素濃度； 是啟發(fā)信息，d是城市i和j之間的距離； 和反映了信息素與啟發(fā)信息的相對(duì)重要性；表示螞蟻k已經(jīng)訪問(wèn)過(guò)的城市列表。 當(dāng)所有螞蟻完成周游后，按以下公式進(jìn)行信息素更新。 13第13頁(yè)，共34頁(yè)。螞蟻算法求解TSP其中：為小于1的常數(shù)，表示信息的持久性。其中：Q為常數(shù)；lk表示第k只螞蟻在本次迭代中走過(guò)的路徑，Lk為路徑長(zhǎng)度。 14第14頁(yè)，共34頁(yè)。求解TSP算法步驟 初始化隨機(jī)放置螞蟻，為每只螞蟻建立禁

6、忌表tabuk，將初始節(jié)點(diǎn)置入禁忌表中;迭代過(guò)程k=1while k=ItCount do (執(zhí)行迭代)for i = 1 to m do (對(duì)m只螞蟻循環(huán)) for j = 1 to n - 1 do (對(duì)n個(gè)城市循環(huán)) 根據(jù)式(1)，采用輪盤(pán)賭方法在窗口外選擇下一個(gè)城市j; 將j置入禁忌表,螞蟻轉(zhuǎn)移到j(luò); end for end for 計(jì)算每只螞蟻的路徑長(zhǎng)度; 根據(jù)式(2)更新所有螞蟻路徑上的信息量; k = k + 1;end while輸出結(jié)果,結(jié)束算法.15第15頁(yè)，共34頁(yè)。蟻群的規(guī)模和停止規(guī)則一、蟻群大小 一般情況下蟻群中螞蟻的個(gè)數(shù)不超過(guò)TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。二、終止條件 1

7、給定一個(gè)外循環(huán)的最大數(shù)目； 2 當(dāng)前最優(yōu)解連續(xù)K次相同而停止，其中K是一個(gè)給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)。16第16頁(yè)，共34頁(yè)。螞蟻算法的缺點(diǎn)螞蟻算法的缺點(diǎn)：1）收斂速度慢2）易于陷入局部最優(yōu)改進(jìn)：1）采用局部?jī)?yōu)化，設(shè)計(jì)了三種優(yōu)化算子。2）采用蟻群優(yōu)化算法。3）其它優(yōu)化算法17第17頁(yè)，共34頁(yè)。改進(jìn)一：局部?jī)?yōu)化（算子1 ）18第18頁(yè)，共34頁(yè)。對(duì)Kroa100，算子1優(yōu)化前后的路徑如圖所示。優(yōu)化前（28596），算子1優(yōu)化后（26439） 19第19頁(yè)，共34頁(yè)。改進(jìn)一：局部?jī)?yōu)化（算子2 ）20第20頁(yè)，共34頁(yè)。對(duì)Kroa100，算子2優(yōu)化前后的路徑如圖所示。算子1（264

8、39），算子2優(yōu)化后（23012） 21第21頁(yè)，共34頁(yè)。TSP具有鄰域特征，設(shè)置候選窗口，窗口大小應(yīng)取一個(gè)合理值。螞蟻總是優(yōu)先選擇候選窗口中的城市。搜索結(jié)束后，根據(jù)候選窗口對(duì)路徑進(jìn)行優(yōu)化，如果將候選窗口內(nèi)的節(jié)點(diǎn)交換到當(dāng)前節(jié)點(diǎn)附近后距離更短，則進(jìn)行變異。 改進(jìn)一：局部?jī)?yōu)化（算子3 ）22第22頁(yè)，共34頁(yè)。對(duì)Kroa100，算子3優(yōu)化前后的路徑如圖所示。（23012），算子3優(yōu)化后（21282） 23第23頁(yè)，共34頁(yè)。收斂特性對(duì)比 24第24頁(yè)，共34頁(yè)。改進(jìn)二：蟻群優(yōu)化算法1)ACS采用了更為大膽的行為選擇規(guī)則，在城市r的螞蟻k轉(zhuǎn)移到城市s的規(guī)則為:25第25頁(yè)，共34頁(yè)。2.1.4蟻群優(yōu)化算法第三，僅對(duì)全局最優(yōu)解邊上的信息素進(jìn)行加強(qiáng)，更新如下:26第26頁(yè)，共34頁(yè)。其它改進(jìn)1）精英策略2）基于排序的螞蟻系統(tǒng)3） MAX-MIN螞蟻系統(tǒng)27第27頁(yè)，共34頁(yè)。應(yīng)用二：QoS多播路由問(wèn)題什么是多播路由？構(gòu)造一棵費(fèi)用最小的多播樹(shù)，且滿足以下限制條件：(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. （帶寬）28第28頁(yè)，共34頁(yè)。路徑的QoS參數(shù)計(jì)算29第29頁(yè)，共34頁(yè)。多播樹(shù)的QoS參數(shù)計(jì)算30第30頁(yè)，共34頁(yè)。算法方法1：用蟻