(完整版)蟻群算法的數(shù)學(xué)模型

1、蟻群算法的數(shù)學(xué)模型螞蟻k(k 1,2 ,m)在運(yùn)動(dòng)過(guò)程中，運(yùn)動(dòng)轉(zhuǎn)移的方向由各條路徑上 的信息量濃度決定。為方便記錄可用tabuk(k 1,2, ,m)來(lái)記錄第k只螞蟻當(dāng)前已走過(guò)的所有節(jié)點(diǎn)，這里可以稱存放節(jié)點(diǎn)的表為禁忌表；這個(gè)存放節(jié)點(diǎn)的集合會(huì)隨著螞蟻的運(yùn)動(dòng)動(dòng)態(tài)的調(diào)整。在算法的搜索過(guò)程 中，螞蟻會(huì)智能地選擇下一步所要走的路徑。設(shè)m表示螞蟻總數(shù)量，用dj (i, j 0,1, ,n 1)表示節(jié)點(diǎn)i和節(jié)點(diǎn)j 之間的距離，j(t)表示在t時(shí)刻ij連線上的信息素濃度。在初始時(shí)刻,m只螞蟻會(huì)被隨機(jī)地放置，各路徑上的初始信息素濃度是相同的。在t時(shí)刻，螞蟻k從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的狀態(tài)轉(zhuǎn)移概率為Pjij j (t

2、)ij (t) ij (t)k allowed kkcPij0,j allowedother2-1其中，allowedkc tabuk表示螞蟻k下一步可以選擇的所有節(jié)點(diǎn)，C為全部節(jié)點(diǎn)集合；為信息啟發(fā)式因子，在算法中代表軌跡相對(duì)重要程度，反映路徑上的信息量對(duì)螞蟻選擇路徑所起的影響程度， 該值越大，螞蟻間的協(xié)作性就越強(qiáng)；可稱為期望啟發(fā)式因子，在算法中代表能見度的相對(duì)重要性。ij是啟發(fā)函數(shù)，在算法中表示由節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的期望程度，通?？扇 1/dj。在算法運(yùn)行時(shí) 每只螞蟻將根據(jù)(2-1)式進(jìn)行搜索前進(jìn)。在螞蟻運(yùn)動(dòng)過(guò)程中，為了避免在路上殘留過(guò)多的信息素而使啟發(fā)信息被淹沒，在每只螞蟻遍歷完成后，要

3、對(duì)殘留信息進(jìn)行更新處理。由此，在t+n時(shí)刻,路徑(i,j)上信息調(diào)整如下j t n 1j(t) j(t)(2-2)mij(t) k(t)(2-3)k 1在式中，常數(shù) 0,1表示信息素?fù)]發(fā)因子，表示路徑上信息量的 損耗程度，的大小關(guān)系到算法的全局搜索能力和收斂速度，則可用1-代表信息素殘留因子，ik(t)表示一次尋找結(jié)束后路徑(i,j)的信 息素增量。在初始時(shí)刻ij 0 0, ik(t)表示第k只螞蟻在本次遍歷結(jié)束后路徑(i,j)的信息素。由于信息素更新策略有所不同，學(xué)者 Dorigo M研究發(fā)現(xiàn)了三種 不同的基本蟻群算法模型，分別記為“蟻周系統(tǒng)”(Ant-Cycle)模型、“蟻量系統(tǒng)” (An

4、 t-Qua ntity)模型及“蟻密系統(tǒng)” (An t-De nsity)模 型，三種模型求解ik(t)方式存在不同?！跋佒芟到y(tǒng)” (Ant-Cycle)模型ikL?第k只螞蟻?zhàn)哌^(guò)ij(2-4)0, other“蟻量系統(tǒng)”(An t-Qua ntity)模型k ijQdj0,第k只螞蟻在t和t+1之間走過(guò)ijother(2-5)“蟻密系統(tǒng)”(An t-De nsity)模型kijQ, 第 k 只螞蟻在 t 和 t+1 之間走過(guò) ij (2-6)0, other從上邊各公式可以看出三種模型的主要區(qū)別是： “蟻量系統(tǒng)”和“蟻 密系統(tǒng)”中，信息素是在螞蟻完成一步后更新的，即采用的是局部信 息；而在“蟻周系統(tǒng)”中路徑中信息素是在螞蟻完成一個(gè)循環(huán)后更新 的，即應(yīng)用的是整體信息。 在一系列標(biāo)準(zhǔn)測(cè)試問