白蕓 高玉淵

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

旅行商路線規(guī)劃問題實(shí)際上是一個(gè)較為經(jīng)典的多項(xiàng)式復(fù)雜程度非確定性問題，自身具有帶權(quán)完全無向圖中特征，所設(shè)定的節(jié)點(diǎn)依據(jù)全排列的方式布設(shè)，隨著覆蓋作用范圍的擴(kuò)大，會(huì)產(chǎn)生組合爆炸的現(xiàn)象，形成一個(gè)NP 完全問題[1-2]。但近幾年來，隨著應(yīng)用背景及社會(huì)環(huán)境的復(fù)雜化、多元化，傳統(tǒng)旅行商單一、固化的應(yīng)用模式無法再滿足需求及標(biāo)準(zhǔn)，對(duì)于過程中啟發(fā)引導(dǎo)信息的獲取定義以及最優(yōu)解的收斂也逐漸暴露出不同程度的問題和缺陷[3]。

因此，對(duì)差分進(jìn)化算法在旅行商問題中的應(yīng)用作出分析以及研究。通過差分進(jìn)化法來進(jìn)行多層級(jí)、多目標(biāo)的雙向旅行商計(jì)算，得出精準(zhǔn)的基礎(chǔ)數(shù)值。與此同時(shí)，營(yíng)造穩(wěn)定的收斂測(cè)定環(huán)境，采用SGA 求解形式，定位存在的缺點(diǎn)因子，采用差分離散處理的方式，排除存在的誤差，提升旅行商的并行性以及穩(wěn)定性，以MapReduce 框架作為測(cè)定的基準(zhǔn)，聯(lián)合迭代計(jì)算計(jì)算出最終處理結(jié)果，全面系統(tǒng)地解決存在的問題，實(shí)現(xiàn)高效互補(bǔ)應(yīng)用。

1 差分進(jìn)化算法在旅行商問題中的應(yīng)用

1.1 差分粗粒度并行預(yù)處理

粗粒度的并行預(yù)處理實(shí)際上是對(duì)旅行商問題測(cè)定核算環(huán)境的一種搭建。首先，構(gòu)建初始的差分規(guī)則，在算法運(yùn)行初期，將整個(gè)地區(qū)以種群劃定的形式分為若干個(gè)子群，對(duì)每一個(gè)區(qū)域分別進(jìn)行進(jìn)化處理。旅行商值以及動(dòng)態(tài)代數(shù)達(dá)到預(yù)設(shè)的標(biāo)準(zhǔn)時(shí)，計(jì)算出單元粗粒度的覆蓋距離。在標(biāo)定的旅行商范圍之內(nèi)，結(jié)合并行處理標(biāo)準(zhǔn)，設(shè)定對(duì)應(yīng)的并行預(yù)處理模式，融入齊次馬爾可夫鏈，增加預(yù)處理的層級(jí)和目標(biāo)，擴(kuò)大對(duì)應(yīng)的范圍，確?；A(chǔ)收斂程度，營(yíng)造對(duì)應(yīng)的差分粗粒度運(yùn)動(dòng)結(jié)構(gòu)。與此同時(shí)，隨著單元粗粒度的變化以及預(yù)設(shè)旅行商測(cè)定區(qū)域的延伸，控制每分鐘的迭代次數(shù)，降低整體的收斂速度，完成對(duì)差分粗粒度并行預(yù)處理。

1.2 構(gòu)建交叉進(jìn)化運(yùn)算層級(jí)

匯總整合基礎(chǔ)數(shù)據(jù)之后，可以依據(jù)相關(guān)的數(shù)值信息，設(shè)定最優(yōu)旅行商核定結(jié)構(gòu)。從路線規(guī)劃現(xiàn)狀中可以得知，旅行商算子的群體分布情況，計(jì)算出并行路徑距離。根據(jù)旅行商的變動(dòng)情況，劃定區(qū)域性的進(jìn)化范圍。與此同時(shí)，隨著進(jìn)化個(gè)體的變化，針對(duì)于交叉效率，計(jì)算出路徑的重疊系數(shù)，具體如下：

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

通過上述計(jì)算，最終可以得出實(shí)際的路徑重疊系數(shù)。此時(shí)，得出的路徑重疊系數(shù)可以設(shè)定為交叉進(jìn)化運(yùn)算極限標(biāo)準(zhǔn)，配合GA 框架，建立對(duì)應(yīng)的旅行商的基礎(chǔ)算子處理結(jié)構(gòu)，并根據(jù)商值的變動(dòng)比率，設(shè)定相應(yīng)的最優(yōu)解執(zhí)行目標(biāo)，通過更改細(xì)粒度，提高計(jì)算效率。

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

在完成對(duì)交叉進(jìn)化運(yùn)算層級(jí)的構(gòu)建之后，接下來，需要進(jìn)行迭代旅行商控離散矩陣的建立。這部分首先需要結(jié)合差分粗粒度并行預(yù)處理情況以及獲取的基礎(chǔ)數(shù)值信息，編制TSP 執(zhí)行編碼。在旅行商的基礎(chǔ)實(shí)數(shù)之中，首先進(jìn)行四則運(yùn)算，在連續(xù)域的背景之下，對(duì)傳統(tǒng)的旅行商標(biāo)準(zhǔn)作出優(yōu)化處理，此時(shí)，根據(jù)基礎(chǔ)的迭代運(yùn)行次數(shù)，測(cè)定商值的算子比例，具體如表1 所示。

表1 迭代旅行商控離散標(biāo)定值設(shè)定表

根據(jù)表1，可以完成對(duì)迭代旅行商控離散標(biāo)定值的設(shè)定。將每一個(gè)變動(dòng)的離散節(jié)點(diǎn)關(guān)聯(lián)在一起，自由組合，根據(jù)需要，劃定對(duì)應(yīng)的旅行商覆蓋范圍。需要注意的是，不同的位置，DE 變異算子與旅行商的關(guān)聯(lián)程度不同，存在差值，可以根據(jù)運(yùn)動(dòng)規(guī)律看，對(duì)矩陣內(nèi)部的運(yùn)算控制環(huán)節(jié)重新排布，由小到大找出原來的數(shù)列，確保迭代次數(shù)正常增長(zhǎng)的同時(shí)，完成迭代旅行商離散矩陣的建立。

1.4 無線差分積累應(yīng)用模型設(shè)計(jì)

在完成迭代旅行商離散矩陣的建立之后，接下來，需要設(shè)計(jì)無線差分積累應(yīng)用模型。根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則，設(shè)定基礎(chǔ)的運(yùn)行計(jì)算應(yīng)用程序，在標(biāo)定的旅行商執(zhí)行范圍之內(nèi)，實(shí)現(xiàn)變動(dòng)狀態(tài)的定向融合。與此同時(shí)，將對(duì)應(yīng)的轉(zhuǎn)移路線依據(jù)特殊的格式導(dǎo)入應(yīng)用結(jié)構(gòu)之中，擴(kuò)大最優(yōu)路線的延伸范圍，隨著迭代次數(shù)的變化，計(jì)算出定向的差分單元值，具體如下：

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

通過上述計(jì)算，最終可以得出實(shí)際的差分單元值。在差分進(jìn)化算法的輔助之下，測(cè)定測(cè)試的旅行商動(dòng)態(tài)極限差值。設(shè)定其為極限值標(biāo)準(zhǔn)，根據(jù)所建立的迭代旅行商離散矩陣，構(gòu)建對(duì)應(yīng)的旅行商動(dòng)態(tài)生成樹，具體的結(jié)構(gòu)如圖1 所示。

圖1 旅行商動(dòng)態(tài)生成樹環(huán)節(jié)圖示

依據(jù)差分進(jìn)化算法，測(cè)定旅行商此時(shí)的收斂范圍，并通過矩陣核算出不同路線的收斂概率。根據(jù)得出的收斂概率，劃定此時(shí)旅行商的收斂范圍，結(jié)合路線的轉(zhuǎn)移規(guī)律，明確實(shí)際的應(yīng)用環(huán)節(jié)，在無線迭代環(huán)境下，積累對(duì)應(yīng)的離散單元。

1.5 C2Opt 算子重復(fù)排序

采用DE 算法測(cè)定實(shí)時(shí)收斂速度，將單元區(qū)域內(nèi)易陷旅行商值去除，替換成標(biāo)定的基準(zhǔn)數(shù)值。通過TSP NP-hard 求解，在預(yù)設(shè)的范圍之內(nèi)，布設(shè)對(duì)應(yīng)數(shù)量的C2Opt 算子，摒棄傳統(tǒng)的單一、固化排序，采用重讀排序的方式，設(shè)定一個(gè)算子運(yùn)行計(jì)算核心節(jié)點(diǎn)，同時(shí)，采用基礎(chǔ)的計(jì)算路徑，利用差分進(jìn)化法，計(jì)算出重疊比，具體如下：

式中：T1表示重疊比，表示定向范圍內(nèi)的算子重疊次數(shù)，u 表示極端重復(fù)差值，ξ 表示交叉重復(fù)單元，E 表示優(yōu)化差值。

通過上述計(jì)算，最終可以得出實(shí)際的重疊比。根據(jù)重復(fù)排序，并遵循C2Opt 算子的測(cè)定核算框架，形成雙向的啟發(fā)環(huán)節(jié)，營(yíng)造出更為穩(wěn)定、精準(zhǔn)的旅行商處理環(huán)境，在2-OPT 算子的執(zhí)行下進(jìn)行局部?jī)?yōu)化，以提高收斂速度和精度，進(jìn)而完成對(duì)C2Opt 算子重復(fù)排序的處理。

1.6 逆向旅行域設(shè)定

采用巡回旅行的路線，對(duì)于城市的最佳路線作出標(biāo)定。與此同時(shí)，根據(jù)定向的排序，制定運(yùn)行編碼串。在編碼的過程中，針對(duì)于不同的覆蓋區(qū)域，設(shè)定第一個(gè)的旅行商約束條件，形成區(qū)域性的逆向區(qū)域，稱之為逆向旅行域?？梢源偈乖跍y(cè)定的過程中，集中不形成回路。降低整體的測(cè)定誤差，采用設(shè)定，更改標(biāo)定的坐標(biāo)，設(shè)立對(duì)應(yīng)的矩陣口，使用Ⅳ矩陣的形式，將逆向旅行域融入旅行商的覆蓋范圍之內(nèi)，測(cè)定存在的基礎(chǔ)偏差，同時(shí)測(cè)定此時(shí)逆向旅行域中的最小路徑長(zhǎng)度形成逆向旅行域設(shè)的變動(dòng)狀態(tài)，具體如圖2 所示。

圖2 逆向旅行域設(shè)變動(dòng)狀態(tài)圖示

根據(jù)圖2，可以完成對(duì)逆向旅行域設(shè)變動(dòng)狀態(tài)的分析。依據(jù)適應(yīng)度的變化狀態(tài)，在標(biāo)定的區(qū)域之內(nèi)，關(guān)聯(lián)相關(guān)的變異算子，與逆向旅行域形成反向覆蓋區(qū)域，以此來進(jìn)一步優(yōu)化無線差分積累應(yīng)用模型，提升整體的應(yīng)用效果。

1.7 迭代進(jìn)化完成旅行商問題的應(yīng)用

在完成對(duì)逆向旅行域的設(shè)定之后，接下來，還需要采用迭代進(jìn)化完成旅行商問題的應(yīng)用。根據(jù)上述獲取的實(shí)時(shí)偏差率，在標(biāo)定的區(qū)域之內(nèi)，劃定迭代進(jìn)化的應(yīng)用范圍。與此同時(shí)，采用差分進(jìn)化算法進(jìn)行連續(xù)域上的優(yōu)化求解，結(jié)合DE 算法。

設(shè)定具體的離散路徑，根據(jù)變動(dòng)的TSP 編碼，構(gòu)建一種特殊的旅行商適應(yīng)計(jì)算指令，以此來進(jìn)一步強(qiáng)化局部?jī)?yōu)化的能力，從多個(gè)方向提升綜合收斂速度，結(jié)合2OPT 算子，在不同的規(guī)模之下，實(shí)現(xiàn)迭代進(jìn)化處理，以此來進(jìn)一步解決旅行商的誤差問題，提升整體的旅行商問題應(yīng)用效果。

2 應(yīng)用測(cè)試

選擇6 個(gè)城市作為測(cè)試的主要目標(biāo)對(duì)象，將每一座城市的路線導(dǎo)入數(shù)據(jù)庫(kù)。將蟻群算法、遺傳算法以及本文所設(shè)定的差分進(jìn)化法同時(shí)應(yīng)用在旅行商的問題之中，對(duì)最終的測(cè)試結(jié)果對(duì)比探究。

2.1 測(cè)試準(zhǔn)備

將城市按順序編號(hào)，同時(shí)設(shè)定對(duì)應(yīng)的坐標(biāo)，具體如表2 所示。

表2 旅行商測(cè)定城市編號(hào)及坐標(biāo)表

根據(jù)表2，可以完成對(duì)旅行商測(cè)定城市編號(hào)及坐標(biāo)的設(shè)定。根據(jù)上述的設(shè)定，結(jié)合基礎(chǔ)的旅行商測(cè)定數(shù)值，針對(duì)存在的調(diào)研的路線，進(jìn)行TSP 編碼的編制與調(diào)整，設(shè)定起點(diǎn)城市和終止城市，可以先利用差分進(jìn)化法計(jì)算出單個(gè)城市的環(huán)路總長(zhǎng)度，具體如下：

式中：d（P1）表示單個(gè)城市的環(huán)路總長(zhǎng)度，i 表示定向中環(huán)距離，n 表示是適應(yīng)度函數(shù)。通過上述計(jì)算，最終可以得出實(shí)際的單個(gè)城市的環(huán)路總長(zhǎng)度。根據(jù)特定的路徑程度，設(shè)定具體的路徑循環(huán)調(diào)整范圍。在初始化的種群之中，按照對(duì)應(yīng)的比例，設(shè)定單元差分距離，并深化預(yù)設(shè)旅行商問題中的路線最優(yōu)解。

2.2 測(cè)試過程及結(jié)果分析

在完成對(duì)上述測(cè)試環(huán)境的搭建之后，接下來，需要結(jié)合差分進(jìn)化算法，對(duì)6 個(gè)標(biāo)定城市中存在的旅行商業(yè)問題作出具體測(cè)定。根據(jù)最小生成樹的頂點(diǎn)變化情況，測(cè)定實(shí)時(shí)路線的耗時(shí)差別在相同的收斂范圍之內(nèi)，依據(jù)運(yùn)行狀態(tài)，計(jì)算出旅行商最終的規(guī)劃線路。最終得出的結(jié)果對(duì)比分析，如表3 所示。

表3 旅行商問題應(yīng)用結(jié)果對(duì)比分析表

根據(jù)表3，可以完成對(duì)旅行商問題應(yīng)用結(jié)果的對(duì)比分析：與蟻群算法應(yīng)用測(cè)試組和遺傳算法應(yīng)用測(cè)試組相對(duì)比，本文所設(shè)計(jì)的差分進(jìn)化算法應(yīng)用測(cè)試組最終得出的規(guī)劃線路數(shù)相對(duì)較多，可以達(dá)到21 條方案，表明在差分進(jìn)化法的輔助下，旅行商問題得到了更優(yōu)越的處理，對(duì)于6 個(gè)城市的路線規(guī)劃的最優(yōu)解更加可靠、精準(zhǔn)，具有實(shí)際的應(yīng)用價(jià)值。

3 結(jié)論

針對(duì)于迭代次數(shù)的增加，差分進(jìn)化算法的旅行商收斂解逐漸優(yōu)化，最大程度排除旅行商內(nèi)部存在的動(dòng)態(tài)誤差，采用SFCPGA 的核定方式確保最終計(jì)算的實(shí)際精度，逐步加速旅行商的收斂效率，增強(qiáng)運(yùn)算能力，實(shí)現(xiàn)最優(yōu)處理。