基于蟻群算法的物流車輛路徑優(yōu)化問(wèn)題的研究(編輯修改稿)
2025-03-28 14:16 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 蹤跡增長(zhǎng)得越快 ； ③ 協(xié)同工作機(jī)制：螞蟻個(gè)體通過(guò)信息素進(jìn)行信息交流。 螞蟻算法采用人工螞蟻模擬自然界螞蟻的尋徑方式，每個(gè)人工螞蟻的行為符合下列 規(guī)律 人工螞蟻的尋徑規(guī)律 根據(jù)路徑上的信息素濃度 ， 以相應(yīng)的概率來(lái)選取下一步路徑； 01 不再選取自己本次循環(huán)已經(jīng)走過(guò)的路徑為下一步路徑 ， 用一個(gè)數(shù)據(jù)結(jié)構(gòu) ( tabu list )來(lái)控制這 一點(diǎn)； 02 當(dāng)完成了一次循環(huán)后 ， 根據(jù)整個(gè)路徑長(zhǎng)度來(lái)釋放相應(yīng)濃度的信息素 ， 并更新走過(guò)的路徑上的信息素濃度 03 基于 TSP的基本 蟻群算法的數(shù)學(xué)模型 以 TSP為例說(shuō)明 Dorigo等人提出的螞蟻系統(tǒng) (Ant System)模型 ,其目標(biāo)函數(shù)是： 模型中會(huì)用到的變量 : 目m為蟻群中 螞蟻的總數(shù)n為TSP規(guī)模const(0)τ上的信息素濃度, j) (i, 時(shí)刻路徑 (t)為tτ的螞蟻數(shù)目 時(shí)刻位于城市i (t)表示tbijiji?在 t 時(shí)刻螞蟻 k 由城市 i 轉(zhuǎn)移到城市 j的狀態(tài)轉(zhuǎn)移概率 為了 避免殘留信息素過(guò)多引起殘留信息淹沒(méi)啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪?duì)所有 n個(gè)城市的遍歷（也即一個(gè)循環(huán)結(jié)束）后，要對(duì)殘留信息進(jìn)行更新處理 。 t+n時(shí)刻在路徑 (i, j)上的信息量可按照如下規(guī)則進(jìn)行調(diào)整。 ρ 表示信息素?fù)]發(fā)系數(shù)，則 1ρ 表示信息素殘留因子，為了防止信息的無(wú)限積累， ρ 的取值范圍為： ρ 含于 [0,1) 根據(jù) 信息素更新策略的不同， Dorigo M 提出了三種不同的基本蟻群算法模型，分別稱之為 AntCycle 模型、 AntQuantity 模型及AntDensity模型 的不同求法：)(其主要區(qū)別在于kij t??AntCycle 模型 AntQuantity模型 AntDensity模型 ? α 值的大小表明留在每個(gè)結(jié)點(diǎn)上的信息量受重視的程度，α 值越大，螞蟻選擇以前選過(guò)的點(diǎn)的可能性越大，但過(guò)大會(huì)使搜索過(guò)早陷入局部最小 點(diǎn) β 的大小表明啟發(fā)式信息受重視的程度， β 越大，表明選擇路徑時(shí)越依賴啟發(fā)式信息 ? 表示揮發(fā)程度的ρ 對(duì)收斂結(jié)果有很大的影響，實(shí)驗(yàn)表明，取值太大或太小，運(yùn)行結(jié)果都不理想，一般取 ? Q值會(huì)影響算法的收斂速度， Q過(guò)大會(huì)使算法收斂于局部最小值，過(guò)小又會(huì)影響算法的收斂速度，隨著問(wèn)題規(guī)模的增大 Q的值也需隨之變化 螞蟻算法中 Q 、 α 、 β 、 ρ 等參數(shù)對(duì)算法性能有很大影響 基本蟻群算法的程序結(jié)構(gòu)流程 改迚 ACO及 TSP求解 蟻群算法的基本步驟： 基本蟻群算法的改進(jìn) 一系列 研究結(jié)果發(fā)現(xiàn)，用基本螞蟻算法求解時(shí) 容易如下出現(xiàn) 兩個(gè) 問(wèn)題： 搜索進(jìn)行到一定程度后 ，所有的個(gè)體發(fā)現(xiàn)的解基木完全一致 ， 出現(xiàn)停滯現(xiàn)象 ， 不能再對(duì)解空間進(jìn)一步搜索 ， 導(dǎo)致可能無(wú)法找到全局最優(yōu)解 收斂到全局最優(yōu)解的時(shí)間長(zhǎng) ， 求解結(jié)果反復(fù)在局部最優(yōu)解和全局最優(yōu)解之間震蕩 。 改進(jìn)算法中位于 第 i個(gè)結(jié)點(diǎn)的螞蟻 k，按以下選擇策略移動(dòng)到結(jié)點(diǎn) j： 內(nèi)隨機(jī)取值})]([)]({[arg m axall o wed依照以下概率在h其中 uki?? ?? ttU iuiuallowedk??改進(jìn)算法的轉(zhuǎn)移規(guī)則 改進(jìn)的蟻群算法采用 確定性選擇和隨機(jī)選擇相結(jié)合的選擇策略，并且在搜索過(guò)程中動(dòng)態(tài)調(diào)整確定性選擇的概率。 改進(jìn)算法的信息素 局部更新規(guī)則 其中， γ 稱為學(xué)習(xí) 率， δ 稱為揮發(fā)因子。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1