差分進化算法在旅行商問題中的應用

白蕓 高玉淵

（1、西安外事學院，陜西西安 710077 2、陜汽通匯物流有限公司，陜西西安 710038）

旅行商路線規劃問題實際上是一個較為經典的多項式復雜程度非確定性問題，自身具有帶權完全無向圖中特征，所設定的節點依據全排列的方式布設，隨著覆蓋作用范圍的擴大，會產生組合爆炸的現象，形成一個NP 完全問題[1-2]。但近幾年來，隨著應用背景及社會環境的復雜化、多元化，傳統旅行商單一、固化的應用模式無法再滿足需求及標準，對于過程中啟發引導信息的獲取定義以及最優解的收斂也逐漸暴露出不同程度的問題和缺陷[3]。

因此，對差分進化算法在旅行商問題中的應用作出分析以及研究。通過差分進化法來進行多層級、多目標的雙向旅行商計算，得出精準的基礎數值。與此同時，營造穩定的收斂測定環境，采用SGA 求解形式，定位存在的缺點因子，采用差分離散處理的方式，排除存在的誤差，提升旅行商的并行性以及穩定性，以MapReduce 框架作為測定的基準，聯合迭代計算計算出最終處理結果，全面系統地解決存在的問題，實現高效互補應用。

1 差分進化算法在旅行商問題中的應用

1.1 差分粗粒度并行預處理

粗粒度的并行預處理實際上是對旅行商問題測定核算環境的一種搭建。首先，構建初始的差分規則，在算法運行初期，將整個地區以種群劃定的形式分為若干個子群，對每一個區域分別進行進化處理。旅行商值以及動態代數達到預設的標準時，計算出單元粗粒度的覆蓋距離。在標定的旅行商范圍之內，結合并行處理標準，設定對應的并行預處理模式，融入齊次馬爾可夫鏈，增加預處理的層級和目標，擴大對應的范圍，確保基礎收斂程度，營造對應的差分粗粒度運動結構。與此同時，隨著單元粗粒度的變化以及預設旅行商測定區域的延伸，控制每分鐘的迭代次數，降低整體的收斂速度，完成對差分粗粒度并行預處理。

1.2 構建交叉進化運算層級

匯總整合基礎數據之后，可以依據相關的數值信息，設定最優旅行商核定結構。從路線規劃現狀中可以得知，旅行商算子的群體分布情況，計算出并行路徑距離。根據旅行商的變動情況，劃定區域性的進化范圍。與此同時，隨著進化個體的變化，針對于交叉效率，計算出路徑的重疊系數，具體如下：

式中：G 表示路徑重疊系數，? 表示平面算子距離，φ 表示初始啟發參數，α 表示突變次數，β 表示突變向量，ν 表示遷移系數，λ 表示嘗試向量。

通過上述計算，最終可以得出實際的路徑重疊系數。此時，得出的路徑重疊系數可以設定為交叉進化運算極限標準，配合GA 框架，建立對應的旅行商的基礎算子處理結構，并根據商值的變動比率，設定相應的最優解執行目標，通過更改細粒度，提高計算效率。

1.3 建立迭代旅行商離散矩陣

在完成對交叉進化運算層級的構建之后，接下來，需要進行迭代旅行商控離散矩陣的建立。這部分首先需要結合差分粗粒度并行預處理情況以及獲取的基礎數值信息，編制TSP 執行編碼。在旅行商的基礎實數之中，首先進行四則運算，在連續域的背景之下，對傳統的旅行商標準作出優化處理，此時，根據基礎的迭代運行次數，測定商值的算子比例，具體如表1 所示。

表1 迭代旅行商控離散標定值設定表

根據表1，可以完成對迭代旅行商控離散標定值的設定。將每一個變動的離散節點關聯在一起，自由組合，根據需要，劃定對應的旅行商覆蓋范圍。需要注意的是，不同的位置，DE 變異算子與旅行商的關聯程度不同，存在差值，可以根據運動規律看，對矩陣內部的運算控制環節重新排布，由小到大找出原來的數列，確保迭代次數正常增長的同時，完成迭代旅行商離散矩陣的建立。

1.4 無線差分積累應用模型設計

在完成迭代旅行商離散矩陣的建立之后，接下來，需要設計無線差分積累應用模型。根據狀態轉移規則，設定基礎的運行計算應用程序，在標定的旅行商執行范圍之內，實現變動狀態的定向融合。與此同時，將對應的轉移路線依據特殊的格式導入應用結構之中，擴大最優路線的延伸范圍，隨著迭代次數的變化，計算出定向的差分單元值，具體如下：

式中：R 表示差分單元值，b 表示定向變化比，μ1表示交換比，h 表示最優解，? 表示擴大范圍，i 表示差分延遲距離，υ1表示基因數目。

通過上述計算，最終可以得出實際的差分單元值。在差分進化算法的輔助之下，測定測試的旅行商動態極限差值。設定其為極限值標準，根據所建立的迭代旅行商離散矩陣，構建對應的旅行商動態生成樹，具體的結構如圖1 所示。

圖1 旅行商動態生成樹環節圖示

依據差分進化算法，測定旅行商此時的收斂范圍，并通過矩陣核算出不同路線的收斂概率。根據得出的收斂概率，劃定此時旅行商的收斂范圍，結合路線的轉移規律，明確實際的應用環節，在無線迭代環境下，積累對應的離散單元。

1.5 C2Opt 算子重復排序

采用DE 算法測定實時收斂速度，將單元區域內易陷旅行商值去除，替換成標定的基準數值。通過TSP NP-hard 求解，在預設的范圍之內，布設對應數量的C2Opt 算子，摒棄傳統的單一、固化排序，采用重讀排序的方式，設定一個算子運行計算核心節點，同時，采用基礎的計算路徑，利用差分進化法，計算出重疊比，具體如下：

式中：T1表示重疊比，表示定向范圍內的算子重疊次數，u 表示極端重復差值，ξ 表示交叉重復單元，E 表示優化差值。

通過上述計算，最終可以得出實際的重疊比。根據重復排序，并遵循C2Opt 算子的測定核算框架，形成雙向的啟發環節，營造出更為穩定、精準的旅行商處理環境，在2-OPT 算子的執行下進行局部優化，以提高收斂速度和精度，進而完成對C2Opt 算子重復排序的處理。

1.6 逆向旅行域設定

采用巡回旅行的路線，對于城市的最佳路線作出標定。與此同時，根據定向的排序，制定運行編碼串。在編碼的過程中，針對于不同的覆蓋區域，設定第一個的旅行商約束條件，形成區域性的逆向區域，稱之為逆向旅行域。可以促使在測定的過程中，集中不形成回路。降低整體的測定誤差，采用設定，更改標定的坐標，設立對應的矩陣口，使用Ⅳ矩陣的形式，將逆向旅行域融入旅行商的覆蓋范圍之內，測定存在的基礎偏差，同時測定此時逆向旅行域中的最小路徑長度形成逆向旅行域設的變動狀態，具體如圖2 所示。

圖2 逆向旅行域設變動狀態圖示

根據圖2，可以完成對逆向旅行域設變動狀態的分析。依據適應度的變化狀態，在標定的區域之內，關聯相關的變異算子，與逆向旅行域形成反向覆蓋區域，以此來進一步優化無線差分積累應用模型，提升整體的應用效果。

1.7 迭代進化完成旅行商問題的應用

在完成對逆向旅行域的設定之后，接下來，還需要采用迭代進化完成旅行商問題的應用。根據上述獲取的實時偏差率，在標定的區域之內，劃定迭代進化的應用范圍。與此同時，采用差分進化算法進行連續域上的優化求解，結合DE 算法。

設定具體的離散路徑，根據變動的TSP 編碼，構建一種特殊的旅行商適應計算指令，以此來進一步強化局部優化的能力，從多個方向提升綜合收斂速度，結合2OPT 算子，在不同的規模之下，實現迭代進化處理，以此來進一步解決旅行商的誤差問題，提升整體的旅行商問題應用效果。

2 應用測試

選擇6 個城市作為測試的主要目標對象，將每一座城市的路線導入數據庫。將蟻群算法、遺傳算法以及本文所設定的差分進化法同時應用在旅行商的問題之中，對最終的測試結果對比探究。

2.1 測試準備

將城市按順序編號，同時設定對應的坐標，具體如表2 所示。

表2 旅行商測定城市編號及坐標表

根據表2，可以完成對旅行商測定城市編號及坐標的設定。根據上述的設定，結合基礎的旅行商測定數值，針對存在的調研的路線，進行TSP 編碼的編制與調整，設定起點城市和終止城市，可以先利用差分進化法計算出單個城市的環路總長度，具體如下：

式中：d（P1）表示單個城市的環路總長度，i 表示定向中環距離，n 表示是適應度函數。通過上述計算，最終可以得出實際的單個城市的環路總長度。根據特定的路徑程度，設定具體的路徑循環調整范圍。在初始化的種群之中，按照對應的比例，設定單元差分距離，并深化預設旅行商問題中的路線最優解。

2.2 測試過程及結果分析

在完成對上述測試環境的搭建之后，接下來，需要結合差分進化算法，對6 個標定城市中存在的旅行商業問題作出具體測定。根據最小生成樹的頂點變化情況，測定實時路線的耗時差別在相同的收斂范圍之內，依據運行狀態，計算出旅行商最終的規劃線路。最終得出的結果對比分析，如表3 所示。

表3 旅行商問題應用結果對比分析表

根據表3，可以完成對旅行商問題應用結果的對比分析：與蟻群算法應用測試組和遺傳算法應用測試組相對比，本文所設計的差分進化算法應用測試組最終得出的規劃線路數相對較多，可以達到21 條方案，表明在差分進化法的輔助下，旅行商問題得到了更優越的處理，對于6 個城市的路線規劃的最優解更加可靠、精準，具有實際的應用價值。

3 結論

針對于迭代次數的增加，差分進化算法的旅行商收斂解逐漸優化，最大程度排除旅行商內部存在的動態誤差，采用SFCPGA 的核定方式確保最終計算的實際精度，逐步加速旅行商的收斂效率，增強運算能力，實現最優處理。