蟻群算法的數(shù)學模型

1、精選優(yōu)質文檔-傾情為你奉上蟻群算法的數(shù)學模型 螞蟻在運動過程中，運動轉移的方向由各條路徑上的信息量濃度決定。為方便記錄可用來記錄第 k 只螞蟻當前已走過的所有節(jié)點，這里可以稱存放節(jié)點的表為禁忌表；這個存放節(jié)點的集合會隨著螞蟻的運動動態(tài)的調(diào)整。在算法的搜索過程中，螞蟻會智能地選擇下一步所要走的路徑。 設 m 表示螞蟻總數(shù)量，用表示節(jié)點 i 和節(jié)點 j 之間的距離，表示在 t 時刻連線上的信息素濃度。在初始時刻，m只螞蟻會被隨機地放置，各路徑上的初始信息素濃度是相同的。在 t 時刻，螞蟻 k 從節(jié)點i轉移到節(jié)點 j 的狀態(tài)轉移概率為 其中，表示螞蟻 k 下一步可以選擇的所有節(jié)點，C 為全部節(jié)點集合

2、；為信息啟發(fā)式因子，在算法中代表軌跡相對重要程度，反映路徑上的信息量對螞蟻選擇路徑所起的影響程度，該值越大，螞蟻間的協(xié)作性就越強；可稱為期望啟發(fā)式因子，在算法中代表能見度的相對重要性。是啟發(fā)函數(shù)，在算法中表示由節(jié)點i 轉移到節(jié)點 j 的期望程度，通常可取。在算法運行時每只螞蟻將根據(jù)(2-1)式進行搜索前進。 在螞蟻運動過程中，為了避免在路上殘留過多的信息素而使啟發(fā)信息被淹沒，在每只螞蟻遍歷完成后，要對殘留信息進行更新處理。由此，在t+n時刻,路徑(i,j)上信息調(diào)整如下 (2-2) (2-3) 在式中，常數(shù) 表示信息素揮發(fā)因子,表示路徑上信息量的損耗程度,的大小關系到算法的全局搜索能力和收斂速

3、度，則可用代表信息素殘留因子,表示一次尋找結束后路徑(i,j)的信息素增量。在初始時刻,表示第 k 只螞蟻在本次遍歷結束后路徑(i,j)的信息素。 由于信息素更新策略有所不同，學者Dorigo M 研究發(fā)現(xiàn)了三種不同的基本蟻群算法模型，分別記為“蟻周系統(tǒng)”(Ant-Cycle)模型、“蟻量系統(tǒng)”(Ant-Quantity)模型及“蟻密系統(tǒng)”(Ant-Density)模型，三種模型求解 方式存在不同?！跋佒芟到y(tǒng)”(Ant-Cycle)模型 第k只螞蟻走過 (2-4)“蟻量系統(tǒng)”(Ant-Quantity)模型 第k只螞蟻在t和t+1之間走過 (2-5)“蟻密系統(tǒng)”(Ant-Density)模型 第k只螞蟻在t和t+1之間走過 (2-6)從上邊各公式可以看出三種模型的主要區(qū)別是：“蟻量系統(tǒng)”和“蟻密系統(tǒng)”中，信息素是在螞蟻完成一步后更新的，即采用的是局部信息；而在“蟻周系統(tǒng)”中路徑中信息素是在螞蟻完成一個循環(huán)后更新的，即應用的是整體信息。在一系列標準測試問題上運行的實驗表明，“蟻周系統(tǒng)”