一種求解旅行商問題的蟻群優化-微分進化融合方法

2023-05-31 02:16:16 3

專利名稱：一種求解旅行商問題的蟻群優化-微分進化融合方法
技術領域：
本發明一種求解旅行商問題的蟻群優化(Ant Colony Optimization, ACO)國 微分進化(DifferentialEvolution, DE)融合方法，屬於應用人工智慧技術領域。
(二)
背景技術：
旅行商問題(Traveling Salesman Problem, TSP)是一個經典的組合優化問 題，經典的旅行商問題可以描述為 一個商品推銷員要去若干個城市推銷商品， 該推銷員從一個城市出發，需要經過所有城市後，回到出發地。應如何選擇行 進路線，以使總的行程最短。從圖論的角度來看，該問題實質是在一個帶權完 全無向圖中，找一個權值最小的哈密爾頓(Hamilton)迴路。由於該問題的可行解 是所有頂點的全排列，隨著頂點數的增加，會產生組合爆炸。作為組合優化中 研究最多的問題之一，旅行商問題吸引了許多不同領域的研究工作者，包括數 學、運籌學、物理、生物和人工智慧等領域，它是目前優化領域裡的研究熱點。
蟻群優化算法(也稱"蟻群算法"或"螞蟻算法")是一種最新發展的模擬 昆蟲王國中螞蟻群體覓食行為的仿生優化算法，該算法採用了正反饋並行自催 化機制，具有較強的魯棒性、優良的分布式計算機制、易於與其他方法結合等 優點，在解決許多複雜優化問題方面己經展現出其優異的性能和巨大的發展潛 力。
蟻群算法是由螞蟻覓食行為演化來的優化算法，螞蟻個體之間是通過一種 稱之為信息素(Pheromone)的物質進行信息傳遞，從而能相互協作，完成複雜的 任務。螞蟻在運動過程中，在它所經過的路徑上會留下一定量的信息素，信息 素的強度與路徑長度有關。並且螞蟻在運動過程中能夠感知路徑上信息素的存 在及其強度，並以此指導自己的對路徑的選擇，螞蟻傾向於朝著信息素強度較 高的方向移動。因此，由大量螞蟻組成的蟻群的集體行為便表現出一種信息正 反饋現象某一路徑上走過的螞蟻越多，則後來者選擇該路徑的概率就越大。 螞蟻個體之間就是通過這種信息的交流達到搜索食物的目的。蟻群算法採用了 正反饋並行自催化機制，該算法具有較強的魯棒性、優良的分布式計算機制、易於與其他方法結合等優點。蟻群算法由義大利學者M.Dorigo提出之後最早用 於求解旅行商問題以及工件排序問題，顯示出了比其他算寧更好的效果，此外， 該算法在解決其他許多複雜優化問題方面也已經展現出了優異的性能和巨大的 發展潛力。
作為一種新興的啟發式仿生智能優化算法，目前人們對蟻群優化算法的研究已 經由當初單一的旅行商問題領域滲透到了多個應用領域，由解決一維靜態優化 問題發展到解決多維動態組合優化問題，由離散域範圍內的研究逐漸拓展到了 連續域範圍內的研究，而且在蟻群優化算法的硬體實現上也取得了很多突破性 進展，從而使這種新興的仿生優化算法展現出勃勃生機和廣闊的發展前景。
微分進化算法是由Storn和Price在1995年提出來的一種新的進化算法， 和其它的進化算法相比，微分進化算法的性能更加突出，它的過程簡單，幾乎 每次運行都能找到最優解，而且微分進化算法只有很少的參數需要設置，並且 同樣的參數設置可以用到許多的不同的問題中。已有研究指出，在大多數的數 值Benchmark問題中微分進化算法表現的比粒子群算法等其它進化算法都要 好。微分進化算法首先在搜索空間內隨機產生初始的解群體，然後通過將群體 中兩個成員間的差向量增加到第三個成員的方法來生成新的個體，如果新個體 的適應度值更好，那麼新產生的個體將代替原個體。其它的進化算法相比，這 種新穎的搜索算法過程簡單，魯棒性好，它更容易理解、易於實現，有很強的 空間搜索能力，且收斂速度快。
實踐證明，單純依賴一種算法求解複雜問題，有時效果並不好，將兩種進 行有機的融合，是一種很好的思路。蟻群算法採用的正反饋機制是其不同於其 它算法最為顯著的特點，但其在實際應用中也有著一些不足，比如，基本蟻群 算法一般需要較長的搜索時間，且容易出現停滯現象，同時，蟻群算法的收斂 性能對對初始化參數的設置比較敏感。而對於微分進化算法，收斂速度快、搜 索能力強的特點使它可以對蟻群算法有一個有力的補充。同時，微分進化算法 只有很少的參數需要設置，並且同樣的參數設置可以用到許多的不同的問題中。
發明內容
本發明的目的是針對著名的旅行商問題，利用融入了微分進化思想的改進 型蟻群優化算法尋找最優解。與傳統的蟻群算法相比，該發明所提出的算法具 有更好的收斂性，以及更強的尋優能力。該方法是解決諸如旅行商問題等大規 模複雜優化問題的有效途徑，同時，本發明也可應用於其它複雜的智能優化問 題。自然界中，像螞蟻這類社會性動物，單只螞蟻的能力和智力非常簡單，但 它們通過相互協調、分工、合作完成不論工蟻還是蟻后都不可能有足夠能力來 指揮完成的築巢、覓食、遷徙、清掃蟻穴等複雜行為。螞蟻的食物源總是隨機 散布於蟻巢周圍，我們只要仔細觀察就可以發現，經過一段時間後，螞蟻總能 找到一條從蟻巢到食物源的最短路徑。科學家曾經通過"雙橋實驗"對蟻群的覓 食行為進行了研究。發現除了能找到巢穴和食物源之間的最短路徑之外，蟻群 對環境有著極強的適應能力。例如當原有的最短路徑由於一個新的障礙物的出 現而變得不可行時，蟻群能迅速找到一條新的最短路徑。
在現實生活中，我們總可以觀察到大量螞蟻在巢穴與食物源之間形成近乎
直線的路徑，而不是曲線或者圓等其它形狀，如圖l(a)所示。螞蟻群體不僅能 完成複雜的任務，而且還能適應環境的變化，如在蟻群運動路線上突然出現障 礙物時， 一開始各只螞蟻分布是均勻的，不管路徑是否長短，螞蟻總是先按同 等概率選擇各條路徑，如圖l(b)所示。螞蟻在運動過程中，能夠在其經過的路 徑上留下信息素，而且能感知這種物質的存在及其強度，並以此指導自己運動 的方向，螞蟻傾向於信息素濃度高的方向移動。相等時間內較短路徑上的信息 量就遺留得比較多，則選擇較短路徑的螞蟻也隨之增多，如圖l(c)所示。不難 看出，由於大量螞蟻組成的蟻群集體行為表現出了一種信息正反饋現象，即某 一路徑上走過的螞蟻越多，則後來者選擇該路徑的概率就越大，螞蟻個體之間 就是通過這種信息交流機制來搜索食物，並最終沿著最短路逕行進，如圖l(d) 所示。
蟻群是如何完成這些複雜任務的呢 仿生學家經過大量的觀察、研究發現， 螞蟻在尋找食物時，能在其經過的路徑上釋放一種螞蟻特有的信息素，使得一 定範圍內的其他螞蟻能夠感覺到這種物質，且傾向於朝該物質強度高的方向移
動。因此，蟻群的集體行為表現為一種信息正反饋現象某條路徑上經過的螞
蟻數越多，其上留下的信息素也就越多(當然，隨時間的推移會逐漸蒸發)，後 來螞蟻選擇該路徑的概率也越高，從而更增加了該路徑上信息素的強度。隨著 時間的推移，整個蟻群最終會收斂到最短的遍歷路徑上。
蟻群算法最初是用於解決旅行商問題，旅行商問題的簡單形象描述是給 定W個城市，有一個旅行商從某一城市出發，訪問各城市一次且僅有一次後再 回到原出發城市，要求找出一條最短的巡迴路徑。 1、基本蟻群算法的數學模型
設b々)表示n寸刻位於元素/的螞蟻數目，^(0為"寸刻路徑(/，力上的信息量，w表示TSP規模，即城市總數目，m為蟻群中螞蟻的總數自，則附=￡ ;
r =1 。ci C}是f時刻集合C中元素(城市)兩兩連接/y上殘留信息量的集
合。在初始時刻各條路徑上信息量相等，並設初始信息量為^(0) = 6^"對。
螞蟻^(&= 1,2，.....，附)在運動過程中，根據各條路徑上的信息量決定其轉移 方向。這裡用禁忌表^6^(^:=1，2,....,附)來記錄螞蟻^:當前所走過的城市，集合 to6^隨著進化過程作動態調整。在搜索過程中，螞蟻根據各條路徑上的信息量 及路徑的啟發信息來計算狀態轉移概率。/^G)表示在Z時刻螞蟻A:由元素(城 市)/轉移到元素(城市)/的狀態轉移概率
formula see original document page 8
式中，^/0>^4={<3-&6^}表示螞蟻^:下一步允許選擇的城市。ct為信息啟發 式因子，表示軌跡的相對重要性，反映了螞蟻在運動過程中所積累的信息在螞 蟻運動時所起的作用，其值越大，則該螞蟻越傾向於選擇其它螞蟻經過的路徑， 螞蟻之間協作性越強；P為期望啟發式因子，表示能見度的相對重要性，反映了 螞蟻在運動過程中啟發信息在螞蟻選擇路徑中的受重視程度，其值越大，則該 狀態轉移概率越接近於貪心規則。仏」(t)為啟發函數，其表達式如下
formula see original document page 8
式中，《表示相鄰兩個城市之間的距離。對螞蟻A:而言，^越小，則/7ij(t)越 大，/^G)也就越大。顯然，該啟發函數表示螞蟻從元素(城市)/轉移到元素(城 市X/的期望程度。
為了避免殘留信息素過多引起殘留信息淹沒啟發信息,在每隻螞蟻走完一 步或者完成對所有n個城市的遍歷(也即一個循環結束)後，要對殘留信息進行更 新處理。這種更新策略模仿了人類大腦記憶的特點，在新信息不斷存入大腦的 同時，存貯在大腦中的舊信息隨著時間的推移逐漸淡化，甚至忘記。由此， 時刻在路徑(z》)上的信息量可按如下規則進行調整
formula see original document page 8Ary(/) = SA《(,) (4)
式中，p表示信息素揮發係數，貝Ul-p表示信息素殘留因子，為了防止信息
的無限積累，；o的取值範圍為PC
,("l，…,A^)表示。對於任意一個目標向量^而言，按下面
公式生成變異向量V"
vf =xn+Fx(X2-、)， hl,2…，M5 (6)
其中，^ ，、2 ，^是群體中隨機選擇的三個個體，並且^ # r2 # r3 # / 。 F是一個介於
間的實型常量因子，用於控制差向量0,2-\)的影響，一 般稱為放縮因子。顯然，X。 ，S之間的差向量越小，擾動也就越小，這意味著 如果群體靠近優化值，擾動會自動減小。
微分算法的交叉操作的目的是通過變異向量"和目標二向量、的結合以提 高變異向量的多樣性。算法通過下面公式生成新的向量"''=[""'W''2'''''W'"]:
/二i，…，,d.，,
這裡，ra"W是
間的隨機數；C7 是範圍在
間的常數，稱為交叉常
9量，C7 的值越大，發生交叉的可能就越大，Ci =0表示沒有交叉raw^是在[1，D] 隨機選擇的整數，它保證A至少要從K中獲得一個元素，否則就不會有新的 向量生成，群體也就不會發生變化。
微分進化算法中的選擇操作，是一種"貪婪"選擇模式，若且唯若新的向 量個體、的適應度值比目標向量個體^的更好時，才會被保留到下一代群體
中。否則，目標向量個體A仍然保留在群體中，再一次作為下一代的父向量。
3、改進型蟻群優化-微分進化算法(DEACO)
在蟻群算法中，信息素對螞蟻探路活動起著重要的作用， 一個良好的信息 素分布將直接影響到蟻群對最優路徑的探索。為此，提出將微分進化算法的思 想融入到蟻群算法中，利用微分進化算法中的隨機偏差擾動產生新個體的方式， 對蟻群留下的信息素數量進行一些擾動，以期在各個城市之間達到更好的信息 素分布，從而得到最優的路徑。
在改進算法中，微分算法中的變異、交叉以及選擇操作的作用對象都將是 蟻群算法中螞蟻在路徑上留下的信息素。 '
首先對蟻群算法中的螞蟻群體略微做些調整，即是將螞蟻分為若干相互間 獨立的小分隊(Ant-team)，分隊數量記為reaw， (rea柳最好是螞蟻總數m的約 數)。每隊的城市間上的信息素記為7 = ^}, / = 1，...,7^W2，顯然，^是一個 "xw的矩陣。對於各隊螞蟻當前的信息素，按照下列公式產生變異後的信息 素分布
5 、+Fx(、-、)，hl,2，…，r謂 (8)
其中，、，、，、是在所有的螞蟻分隊中隨機選擇的三個信息素個體，並 且仍有G - W 。顯然，同樣、，、之間的差向量越小，擾動也就會越小，
這意味著當各個分隊的信息素收斂於最佳的信息素分布附近時，變異產生的擾 動會自動減小。
改進算法中利用微分進化算法的交叉操作，通過變異信息素分布、和當前 的目標信息素^的結合以提高城市間信息素的多樣性。算法通過下面公式生成
新的信息素矩陣巧,=
formula see original document page 102' ra"必〉C^orraw《^A;， (9)
這裡，r嚴代表變異操作前第/分隊螞蟻在城市力^之間的信息素，rf代 表經變異操作後，第/分隊螞蟻在城市y,A:之間的中間信息素分布矩陣，r^代 表對r嚴和rf實行選擇操作後，第/分隊螞蟻在城市力t之間的信息素；m"必 是
間的隨機數；O 是範圍在
間的常數，稱為交叉常量，O 的值越大， 發生交叉的可能性就越大，C7 =0表示沒有交叉，意味著各螞蟻分隊之間沒有 信息素的交流；ra"^:是在[1， n]上隨機選擇的整數，它保證了新生成的信息素 矩陣匸2,至少要從經變異後的信息素、中獲得一個元素，否則就信息素就不會 產生變化，不利於螞蟻分隊間的信息交流。
在旅行商問題中，各分隊的螞蟻按照其信息素矩陣^計算來的轉移概率 P^構建路徑，得到的最優路徑的長度i^&A即為信息素r,.的適應度值。對新 生成的信息素，以及螞蟻在其基礎上的探路活動的認可與否，需要對原始目標 信息素分布5與新的信息素個體^^進行適應度值的評價，執行一種"貪婪" 選擇模式。若且唯若新個體的適應度值比原始個體的更好時，才會被接受並保 留到下一代的信息素分布矩陣中；否則，目標信息素分布A仍將留在該螞蟻分 隊的城市信息素分布中。所以，信息素的選擇操作可用下式表示為
[r2 ,, ^Z^—6esf2 <Z^—6esf0 '，—1, ^丄—6eW2 2 —6es^ (10)
其中，巧,t為第/螞蟻分隊進行到第f次迭代時，在城市路徑上遺留的信息 素；為第/螞蟻分隊在第^次迭代時，城市路徑上的信息素經變異、交叉 操作後得到的新的信息素矩陣；n,t等於^t和^^中具有較高適應度的信息素 矩陣。丄—^A,為螞蟻按照信息素、t構建出的最短路徑長度，即信息素、t的
適應度；丄—Z)M^為螞蟻按照信息素&^構建出的最短路徑長度。
選擇操作結束後，以信息素矩陣、t或T2,，,構建路徑的第z'蟻群分隊，按照
其隊內各螞蟻個體走過路徑的長度，依照蟻周(Ant-Cycle)模型的信息素公式 (5)釋放出各自的信息素，並對被選中的信息素r、t進行信息素的更新，得到 新的信息素分布、t+1 ，並將各分隊的信息矩陣傳給下一代的蟻群。
4、蟻群優化-微分進化算法解決旅行商問題的具體實現步步驟一參數初始化。令當前的迭代次數iVC=l，設置最大循環迭代次數
A^max，設置城市坐標集合C，城市總數為"，令連接城市7'、 A的路徑上的初始 化信息素—4=常數，螞蟻總數m，與蟻群算法有關的參數"，"，P， g,與 微分算法有關的參數F, C7 ，設置螞蟻分隊的數量7^m。'
步驟二初始化螞蟻群體。將所有螞蟻分為總數為7fe"m的螞蟻分隊，.各 分隊螞蟻數量記為71rn(^;對於第/個分隊，將其中的所有r—m0隻螞蟻隨機 置於m個城市上。
步驟三進行第一次迭代。令片l，對第/分隊中的71m0隻螞蟻個體按照 狀態轉移概率公式(1)計算的概率P^選擇城市A:並前進，直至將所有城市遍 歷完，然後根據公式(3)、 (4)以及(5)更新路徑上的信息素，得到、2;令 /=/+1，重複執行步驟三，直到/>7^附。
步驟四迭代次數7VC=A^+1。按照公式(8)執行變異操作，產生中間信 息素矩陣、.，再按照公式(9)執行交叉操作，產生新的信息素矩陣&,;令 /=/+1，重複執行步驟四，直到^ream。
步驟五螞蟻分隊數目/=1。
步驟六第/分隊的所有螞蟻個體按照矩陣^所給的信息素，利用狀態轉 移概率公式(1)得來的概率完成對所有城市的遍歷，計算出每隻螞蟻遍歷路徑 的長度，選出最短路徑的，其長度記為丄—^W。,.。
步驟七第/分隊的所有螞蟻個體按照矩陣、,所給的信息素，利用狀態轉 移概率公式(1)計算的概率完成對所有城市的遍歷，計算出每隻螞蟻遍歷路徑 的長度，選出最短的路徑，其長度記為丄—&W2i。
步驟八比較丄—6M^和丄—&W2i，按照公式(10)執行選擇操作，將7,或 ^賦予r/,並將丄—b^與丄—Z^;較小的賦予丄—6W,，並將其對應的城市 遍歷路徑記入i Jje聘。
步驟九對信息素進行更新。若在步驟八中選擇了^賦予^'，則依照步驟 六中各螞蟻個體的遍歷路徑，利用公式(3)、 (4)、 (5)進行信息素的更新；若 在步驟八中選擇了^,賦予<，則依照步驟七中各螞蟻個體的遍歷路徑，利用 公式(3)、 (4)、 (5)進行信息素的更新。
步驟十螞蟻分隊數目/=/+1，返回執行步驟六，直到/>7^附。
步驟十一在丄一6e^中選出最小的，即為本次迭代最短路徑長度L&, 其對應的遍歷路徑記為i &。
步驟十二返回執行步驟四，直到iVc》^皿時，結束循環。
12步驟十三在Lwc (Wc = l,...， WC皿)中選出最小者，記為幼0故^_>"-/2，
其在及&中對應的遍歷路徑記為幼0WeW—raw決，即得旅行商問題的最終解。
本發明提出了一種求解旅行商問題的蟻群優化-微分進化融合方法，其優點
及功效在於與傳統的蟻群算法相比，該融合算法使得整個蟻群集體既有各個 螞蟻個體之間的信息素交流，又有各螞蟻分隊之間的信息素交流，從而提高了 螞蟻信息素的多樣性，使蟻群具有了更強的全局搜索能力，並具有更好的收斂 性。該方法在解決旅行商問題方面有著優異表現，同時，本發明也可應用於解 決其它複雜的組合優化問題。

圖1現實中蟻群尋找食物的過程
圖2微分算法中的變異操作
圖3微分算法中的交叉操作
圖4蟻群優化-微分進化算法的流程圖
圖5基本蟻群算法解決Att48TSP的最優路徑
圖6蟻群優化-微分進化算法解決Att48TSP的最優路徑
圖7最優路徑進化曲線對比圖
圖8平均路徑進化曲線對比圖 、
圖中標號及符號說明如下
7^"——城市間的信息素分布矩陣
%的——經變異、交叉操作後的信息素矩陣
7>^——第z'分隊的螞蟻數
丄—&叫(/)——第/分隊的螞蟻由信息素矩陣&W得到的最優路徑長度 ￡一&^2(/)——第z'分隊的螞蟻由信息素矩陣r"&得到的最優路徑長度 ——算法循環次數
iVc一mox-算法最大循環次數
7kwa-隊列
Y——是 N^否
57zorfe^丄e"g^-最短路徑長度
Average Ze"gf/z-平均路徑長度
basic—ACO——基本蟻群算法
13DEACO——蟻群優化-微分進化算法 Att48TSP——城市數目為48的旅行商問題
具體實施例方式
為了驗證改進的蟻群優化-微分進化優化算法在在解決旅行商問題時的優 越性，本發明利用48城市旅行商問題(Att48TSP)進行了實驗，其具體實現步 驟如下
步驟一參數初始化令當前的迭代次數7VC=1，設置最大循環迭代次數 7\^畫=100，參數賦值附=30， a=2, "=4,=0.7， g=10， F=2，Ci =0.5，7kw2=5o
步驟二輸入要解決的48城市旅行商問題中的城市坐標集合C，城市總數 為"=48，計算城市y與城市A:之間的路徑長度4k，以及 =%令連接城市y
與城市A:的路徑上的初始化信息素=1 ，將所有螞蟻分配到各個螞蟻分隊中， 每個分隊螞蟻數為71m^=m/7^m=6;將各分隊的螞蟻隨機置於各個城市上。
步驟三進行第一次迭代。令/=1，對第/分隊中的7Lm"只螞蟻個體按照 下列狀態轉移概率公式計算的概率P^選擇城市t並前進，直至將所有城市遍 歷完；
0 o^ni^e
每隻螞蟻遍歷路徑長度記為^_—);然後根據下列公式更新路徑上的信息
素，得到下一代的信息素矩陣；2;
10
"葉——、
丄,
,若第t只螞蟻在本次循環中經過oy)
T一w(/)
o 否則
、2=a — 0.7).r,+Ar,.
令/=/+1，重複執行步驟三，直到^7kwr步驟四令迭代次數A^=A^+1 。按照下列公式執行變異操作，產生中間信 息素矩陣、，
巧，二、+2x(、-、)，/ = 1，2，'"，5
再按照下式執行交叉操作，產生新的信息素矩陣&,;
2' V,, z/raw必〉0.5orraw《d， 令/=/+1，重複執行步驟四，直到P5。
步驟五螞蟻分隊數目/=1。
步驟六第/分隊的所有螞蟻個體按照矩陣^所給的信息素，利用狀態轉 移概率公式 -
巧,* =
0 oz72mW化
得來的概率完成對所有城市的遍歷，計算出每隻螞蟻遍歷路徑的長度，選 出最短路徑的，其長度記為丄_6"^.。
步驟七第/分隊的所有螞蟻個體按照矩陣、,所給的信息素，利用狀態轉 移概率公式
'2,.
0 c^/2mv^
計算的概率完成對所有城市的遍歷，計算出每隻螞蟻遍歷路徑的長度，選
出最短的路徑，其長度記為丄—6"/2i。
步驟八比較Z —6W。i和Z—&W2i，按照公式formula see original document page 15
執行選擇操作，將^或t"2,賦予r,.'，並將丄—6e^與丄—6e^較小的賦予
，並將其對應的城市遍歷路徑記入及J^A。 步驟九對信息素進行更新。若在步驟八中選擇了^賦予r/，則依照步驟
15六中各螞蟻個體的遍歷路徑，利用下列公式
formula see original document page 16
進行信息素的更新；若在步驟八中選擇了匸2,賦予r/，則依照步驟七中各螞蟻 個體的遍歷路徑，利用上述三個公式進行信息素的更新。最終得到傳給下一代 的信息素5。
步驟十螞蟻分隊數目/=&1,返回執行步驟六，直到/>5。
步驟十一在1 —^A中選出最小的，即為本次迭代最短路徑長度L&,其
對應的遍歷路徑記為及&。
步驟十二返回執行步驟四，直到A^2100時，結束循環。
步驟十三在L&(M^1,…，A^ax)中選出最小者，記為幼w的L/e"gA,
其在及化中對應的遍歷路徑記為幼o^eW—raw//2，即得到48城市旅行商問題的最終解。
圖5~圖8即為利用基本蟻群算法(basic一ACO)和本發明提出的蟻群優化-微 分進化算銜DEACO)解決48城市旅行商問題時，得到的最優路徑圖，以及最 短路徑長度與平均路徑長度的進化曲線對比圖。
在路徑長度對比圖中，實線為利用基本蟻群算法得到的進化曲線，虛線是 利用蟻群優化-微分進化算法得到的進化曲線。
由實際應用結果可見，與傳統的蟻群算法相比，該發明所提出的蟻群優化-微分進化融合方法具有更好的收斂性，並具有更強的全局尋優能力。該方法是 解決諸如旅行商問題等大規模複雜優化問題的有效途徑，同時，本發明也可應 用於解決其它複雜的組合優化問題(如機器人路徑規劃、作業調度、圖著色、網 絡路由等)。
權利要求
1、一種求解旅行商問題的蟻群優化-微分進化融合方法，其特徵在於它的具體實現步驟如下步驟一參數初始化令當前的迭代次數Nc＝1，設置最大循環迭代次數Ncmax，設置城市坐標集合C，城市總數為n，令連接城市j與城市k的路徑上的初始化信息素τj，k＝常數，螞蟻總數m，與蟻群算法有關的參數α、β、ρ、Q，以及與微分算法有關的參數F、CR，設置螞蟻分隊的數目Team；步驟二初始化螞蟻群體將所有螞蟻分為總數為Team的螞蟻分隊，各分隊螞蟻數量記為T_m(i)；對於第i個分隊，將其中的所有T_m(i)只螞蟻隨機置於n個城市上；步驟三進行第一次迭代令i＝1，對第i分隊中的T_m(i)只螞蟻個體按照下列狀態轉移概率公式計算的概率pj，k選擇城市k並前進，直至將所有城市遍歷完；其中，allowedT-m(i)是第i隊中的第T_m(i)只螞蟻可以選擇的城市的集合；然後根據下列公式τi，2＝(1-ρ)·τi+Δτi更新路徑上的信息素，得到第二代的信息素τi，2；令i＝i+1，重複執行步驟三，直到i>Team；步驟四迭代次數Nc＝Nc+1按照下列公式執行變異操作，產生中間信息素矩陣再按照下述公式執行交叉操作，產生新的信息素矩陣令i＝i+1，重複執行步驟四，直到i>Team；步驟五令螞蟻分隊數目i＝1；步驟六第i分隊的所有螞蟻個體按照矩陣τi所給的信息素，利用狀態轉移概率公式得來的概率完成對所有城市的遍歷，計算出每隻螞蟻遍歷路徑的長度，選出最短路徑的，其長度記為L_best0i；步驟七第i分隊的所有螞蟻個體按照矩陣所給的信息素，利用狀態轉移概率公式計算的概率完成對所有城市的遍歷，計算出每隻螞蟻遍歷路徑的長度，選出最短的路徑，其長度記為L_best2i；步驟八比較L_best0i和L_best2i，按照下述公式執行選擇操作，將τi或賦予將L_best0i與L_best2i中較小的賦予L_besti，並將其對應的城市遍歷路徑記入R_besti；步驟九對信息素進行更新若在步驟八中選擇了τi賦予則依照步驟六中各螞蟻個體的遍歷路徑，利用下列三個公式進行信息素的更新；若在步驟八中選擇了賦予則依照步驟七中各螞蟻個體的遍歷路徑，利用上面三個公式進行信息素的更新；步驟十螞蟻分隊數目i＝i+1，返回執行步驟六，直到i>Team；步驟十一在L_besti中選出最小的，即為本次迭代最短路徑長度LNc，其對應的遍歷路徑記為RNc；步驟十二返回執行步驟四，直到Nc≥Ncmax時，結束循環；步驟十三在LNc(Nc＝1，…，Ncmax)中選出最小者，記為Shortest_length，其在RNc中對應的遍歷路徑記為Shortest_routh，即得旅行商問題的最終解。
全文摘要
一種求解旅行商問題的蟻群優化-微分進化融合方法，實施步驟為(1)初始化算法參數；(2)初始化螞蟻群體；(3)進行第一次迭代；(4)從第二代起，對各分隊信息素執行變異、交叉操作，產生新的信息素；(5)選中第一分隊；(6)各分隊螞蟻按原始信息素構建各自最優路徑；(7)各分隊螞蟻按新信息素構建各自最優路徑；(8)比較兩個最優路徑，選出路徑優化結果更好的信息素；(9)更新螞蟻分隊信息素，並傳給下一代；(10)返回第六步，直至所有分隊完成計算；(11)確定本代最優路徑及長度；(12)返回第四步，進行下一代計算，直到滿足結束條件；(13)確定全局最優路徑及長度。該方法具有更好的收斂性，並具有更強的全局尋優能力，是解決諸如旅行商問題等大規模複雜優化問題的有效途徑。
文檔編號G06Q10/00GK101520858SQ20081010108
公開日2009年9月2日 申請日期2008年2月28日 優先權日2008年2月28日
發明者張祥銀, 段海濱, 金季強 申請人:北京航空航天大學