蟻群優(yōu)化算法.ppt

1、蟻群優(yōu)化算法 Ant Colony Optimization,2,蟻群優(yōu)化算法,3,1.1 基本原理,提 出,性 質(zhì),4,1.1 基本原理,（1）螞蟻沒有發(fā)育完全的視覺感知系統(tǒng)，其在尋找食物的過程中是如何選擇路徑的呢？ （2）螞蟻往往像軍隊(duì)般有紀(jì)律、有秩序地搬運(yùn)食物，它們通過什么方式進(jìn)行群體間的交流協(xié)作呢？,信息素是一種化學(xué)物質(zhì)，由螞蟻?zhàn)陨磲尫牛菍?shí)現(xiàn)蟻群內(nèi) 間接通信的物質(zhì)。螞蟻隨機(jī)選擇路徑，但是能感知當(dāng)前地 面上的信息素濃度，并傾向于往信息素濃度高的方向前進(jìn)。,信息素,5,1.1 基本原理,雙橋?qū)嶒?yàn),（a）兩個(gè)路具有同樣的長度,自身催化（正反饋）過程,6,1.1 基本原理,雙橋?qū)嶒?yàn),（b）兩

2、條分支具有不同長度,路徑探索,7,1.1 基本理論,（c）30分鐘后添加短分支,雙橋?qū)嶒?yàn),8,1.1基本理論,9,1.1基本理論,蟻群覓食現(xiàn)象和蟻群優(yōu)化算法的基本定義對照表,10,1.2 研究進(jìn)展,歷史進(jìn)展,11,1.2 研究進(jìn)展,算法進(jìn)展,12,1.2 研究進(jìn)展,理論進(jìn)展,13,蟻群優(yōu)化算法,14,2.1 TSP問題,問題簡述：,第一個(gè)ACO螞蟻系統(tǒng)，就是以NP難的TSP問題 作為應(yīng)用實(shí)例提出的。,15,2.2 貪婪算法,基本理論,P87頁，四個(gè)城市間的距離矩陣如下：,用貪婪算法求解： 例如從城市A出發(fā)得,路徑長度為：1+2+4+3=10,16,2.3 螞蟻系統(tǒng)理論,AS系統(tǒng)三個(gè)版本：,信息

3、素更新方式,17,2.3 螞蟻系統(tǒng)理論,AS算法（螞蟻圈版本）對TSP的求解流程主要有兩大步驟：路徑構(gòu)建和信息素更新,1.路徑構(gòu)建,定義5.1 AS中的隨機(jī)比例規(guī)則：對每只螞蟻k，路徑記憶向量 按照訪問順序記錄了所有k已經(jīng)經(jīng)過的城市序號。設(shè)螞蟻k當(dāng)前所在的城市為i，則其選擇城市j作為下一個(gè)訪問對象的概率為：,其中， 表示從城市i可以直接到達(dá)的且又不在螞蟻訪問過的城市序列 中的城市集合。 是一個(gè)啟發(fā)式信息，通常由 直接計(jì)算。 表示邊 上的信息量,18,2.3 螞蟻系統(tǒng)理論,1.路徑構(gòu)建,19,2.3 螞蟻系統(tǒng)理論,2.信息素更新,初始化時(shí)：,20,2.3 螞蟻系統(tǒng)理論,參數(shù)設(shè)置,21,2.3 螞

4、蟻系統(tǒng)理論,參數(shù)設(shè)置,22,2.3 螞蟻系統(tǒng)理論,參數(shù)設(shè)置,23,2.3 螞蟻系統(tǒng)理論,參數(shù)設(shè)置,24,2.4 螞蟻系統(tǒng)算法,2,25,2.4 螞蟻系統(tǒng)算法,結(jié)束條件,26,2.4 螞蟻系統(tǒng)算法,構(gòu)建方式,順序構(gòu)建,所有螞蟻都從當(dāng)前城市移動到 下一個(gè)城市。,兩種構(gòu)建方式，對于螞蟻系統(tǒng)來說是等價(jià)的，因?yàn)樗麄兌?沒有明顯地改變算法的行為特征。對于其他ACO算法而言 這兩種方法就不等價(jià)了，例如：ACS算法。,27,3.1 精華螞蟻系統(tǒng),提出背景：,精華螞蟻系統(tǒng)是對基礎(chǔ)AS的第一次改進(jìn)，它在原AS信息 素更新原則上增加了一個(gè)對至今最優(yōu)路徑的強(qiáng)化手段。,提出背景：,28,蟻群優(yōu)化算法,29,3.1 精華

5、螞蟻系統(tǒng),信息素的更新：,信息素的更新：,信息素的更新：,30,3.2 基于排列螞蟻系統(tǒng),提出背景：,基于排列的螞蟻系統(tǒng)就是這樣的一種改進(jìn)版本，在每一輪所有螞蟻 構(gòu)建完路徑后，將按照所得路徑的長度進(jìn)行排名，只有生成了至今 最優(yōu)路徑的螞蟻和排名在前（w-1）的螞蟻才允許釋放信息素，螞 蟻在邊（i,j）上釋放的信息素的權(quán)值由螞蟻的排名決定。,31,3.2 基于排列螞蟻系統(tǒng),信息素的更新：,32,3.3 最大最小螞蟻系統(tǒng),最大最小螞蟻系統(tǒng),提出背景：,33,3.3 最大最小螞蟻系統(tǒng),在基本AS算法基礎(chǔ)上的改進(jìn)：,34,3.3 最大最小螞蟻系統(tǒng),信息素更新,35,3.3 最大最小螞蟻系統(tǒng),信息素限制,36,3.3 最大最小螞蟻系統(tǒng),信息素的初始化與重新初始化,37,3.4 蟻群系統(tǒng),蟻群系統(tǒng)與AS不同,38,3.4 蟻群系統(tǒng),1.狀態(tài)轉(zhuǎn)移規(guī)則,定義5.2 ACS中的偽隨機(jī)比例規(guī)則：對于螞蟻k，路徑記憶向量 按照訪問順序記錄了所有k已經(jīng)經(jīng)過的城市序號。設(shè)螞蟻k當(dāng)前所在城市 為i，則下一個(gè)訪問城市,39,3.4 蟻群系統(tǒng),1.狀態(tài)轉(zhuǎn)移規(guī)則,40,3.4 蟻群系統(tǒng),參數(shù)設(shè)置,41,3.4 蟻群系統(tǒng),2.信息素全局更新規(guī)則,42,3.4 蟻群系統(tǒng),3.信息素局部更新規(guī)則,對每只螞蟻，每當(dāng)其經(jīng)過一條邊 時(shí)，