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