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

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

3、素更新方式,17,2.3 螞蟻系統(tǒng)理論,AS算法（螞蟻圈版本）對TSP的求解流程主要有兩大步驟：路徑構(gòu)建和信息素更新,1.路徑構(gòu)建,定義5.1 AS中的隨機比例規(guī)則：對每只螞蟻k，路徑記憶向量 按照訪問順序記錄了所有k已經(jīng)經(jīng)過的城市序號。設(shè)螞蟻k當前所在的城市為i，則其選擇城市j作為下一個訪問對象的概率為：,其中， 表示從城市i可以直接到達的且又不在螞蟻訪問過的城市序列 中的城市集合。 是一個啟發(fā)式信息，通常由 直接計算。 表示邊 上的信息量,18,2.3 螞蟻系統(tǒng)理論,1.路徑構(gòu)建,19,2.3 螞蟻系統(tǒng)理論,2.信息素更新,初始化時：,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)建,所有螞蟻都從當前城市移動到 下一個城市。,兩種構(gòu)建方式，對于螞蟻系統(tǒng)來說是等價的，因為他們都 沒有明顯地改變算法的行為特征。對于其他ACO算法而言 這兩種方法就不等價了，例如：ACS算法。,27,3.1 精華螞蟻系統(tǒng),提出背景：,精華螞蟻系統(tǒng)是對基礎(chǔ)AS的第一次改進，它在原AS信息 素更新原則上增加了一個對至今最優(yōu)路徑的強化手段。,提出背景：,28,蟻群優(yōu)化算法,29,3.1 精華

5、螞蟻系統(tǒng),信息素的更新：,信息素的更新：,信息素的更新：,30,3.2 基于排列螞蟻系統(tǒng),提出背景：,基于排列的螞蟻系統(tǒng)就是這樣的一種改進版本，在每一輪所有螞蟻 構(gòu)建完路徑后，將按照所得路徑的長度進行排名，只有生成了至今 最優(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ǔ)上的改進：,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中的偽隨機比例規(guī)則：對于螞蟻k，路徑記憶向量 按照訪問順序記錄了所有k已經(jīng)經(jīng)過的城市序號。設(shè)螞蟻k當前所在城市 為i，則下一個訪問城市,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ī)則,對每只螞蟻，每當其經(jīng)過一條邊 時，