基于改進遺傳算法的冷鏈物流路徑優(yōu)化

袁紫微

摘 要：現(xiàn)階段，我國生鮮食品電商依然處于初級發(fā)展階段，該領(lǐng)域多數(shù)電商企業(yè)尚未盈利，要想盈利就必須降低成本。而生鮮食品電商成本攀高的主要原因是冷鏈設(shè)備落后以及冷鏈物流路徑設(shè)計不合理。因此，本文針對采用基于遺傳算法優(yōu)化冷鏈物流路徑的基礎(chǔ)算法，對算法進行相應(yīng)的優(yōu)化獲得改進遺傳算法，以降低冷鏈物流運輸成本，提高冷鏈物流運輸效率。

關(guān)鍵詞：遺傳算法；冷鏈物流；路徑優(yōu)化

DOI：10.16640/j.cnki.37-1222/t.2019.10.201

1 引言

基于改進的遺傳算法選擇最佳的冷鏈物流路徑，可有效減少冷鏈物流運輸成本，提升冷鏈物流配送效率和服務(wù)水平，從而增加冷鏈物流企業(yè)的經(jīng)濟效益。冷鏈物流企業(yè)基本運作流程如圖1所示。

2 冷鏈物流路徑優(yōu)化的遺傳算法分析與改進

（1）編碼。編碼是指為了能夠用計算機處理遺傳算法的相關(guān)數(shù)據(jù)需要將其轉(zhuǎn)換成計算機可以識別的數(shù)據(jù)?；谶z傳算法的編碼設(shè)計應(yīng)該遵循完整性、非冗余性等原則。常用物流路徑優(yōu)化編碼方式主要包括二進制編碼、符號編碼、實數(shù)編碼三種。其中符號編碼、實數(shù)編碼是主流編碼方式。因為冷鏈物流運輸涉及單一配送中心向若干個需求點提供物流配送服務(wù)，節(jié)點之間存在連續(xù)性。因此，可以采用自然數(shù)編碼方式進行編碼。用0表示配送中心，車輛數(shù)量用m表示，客戶用n表示，就可以用數(shù)學(xué)模型中解向量編制長度為m+n+1的染色體表示可選的冷鏈物流運輸路徑。如染色體“036790251408100”表示以下幾條冷鏈物流運輸路徑：（1）配送中心0——客戶3——客戶6——客戶7——客戶9——配送中心0；車輛路徑；（2）配送中心0——客戶2——客戶5——客戶1——客戶4——配送中心0；（3）配送中心0——客戶8——客戶10——配送中心0。

（2）初始化種群。和其他算法相比，遺傳算法最明顯的不同在于其搜索對象的不同，遺傳算法的搜索對象是種群?；谶z傳算法的初始種群產(chǎn)生方式：設(shè)種群大小為N，隨機形成N個初始解，每一個初始解都與一個個體對應(yīng)，然后從初始代開始迭代，進化代數(shù)為T，當前迭代代數(shù)為t，按照一定規(guī)則進行搜索迭代，最終在滿足特定條件或達到最大迭代次數(shù)時停止迭代。在冷鏈物流路徑優(yōu)化中可以利用混沌遺傳算法（CGA），該算法不容易陷入局部最優(yōu)，更接近真實生物進化過程，使初始種群個體更優(yōu)良，算法效率更高，有效改善傳統(tǒng)遺傳算法局部尋優(yōu)效率低、容易出現(xiàn)早熟的問題。

（3）適應(yīng)度函數(shù)。在遺傳算法中采用適應(yīng)度來衡量一個個體或解的優(yōu)劣，適應(yīng)度值與遺傳可能性成正比。而適應(yīng)度值由適應(yīng)度函數(shù)確定。適應(yīng)度函數(shù)需要結(jié)合實際問題進行定義，通常它可以通過目標函數(shù)經(jīng)過相應(yīng)轉(zhuǎn)換得到。

（4）選擇。選擇遺傳算法中擇優(yōu)進化過程的關(guān)鍵一步。一般適應(yīng)度高的解或個體表示其適應(yīng)能力更強。從種群中選擇適應(yīng)度高的個體或解進行后續(xù)的交叉、變異操作，或者直接用于下一代新個體，構(gòu)建新的種群，充分體現(xiàn)出適者生存的進化規(guī)則。當前常用的選擇策略包括無回放隨機選擇、最優(yōu)保存策略、確定性選擇、輪盤賭等等，它們各有特點，各有利弊，應(yīng)該結(jié)合具體問題，具體情況進行開展靈活的選擇操作。按照適應(yīng)度大小選取前m-1個染色體進行混沌擾動，求解出擾動后染色體適應(yīng)度，可以讓選擇操作后的優(yōu)良個體進行再一次的混沌化，以增強種群的多樣性，有效避免早熟。

（5）交叉。在遺傳算法中，交叉操作是產(chǎn)生新個體的重要一步。交叉操作是指根據(jù)一定的規(guī)則交換兩條染色體的基因以得到新個體。這個新個體保有上一代的一部分特征，但無法完全確保上一代的優(yōu)秀基金被完全繼承。因此，為了得到更加優(yōu)質(zhì)的新一代個體，就必須在進行交叉操作的過程中盡量使新個體繼承上一代的優(yōu)良基因，以提高交叉操作效率，目前常用交叉操作方法主要包括單點交叉、多點交叉、均勻交叉等。本文選用循環(huán)交叉（CX）法，基本步驟如下：

第一步：依據(jù)交叉概率選擇一對父代染色體，從中找到循環(huán)點；

第二步：復(fù)制其中一個父代染色體的循環(huán)節(jié)點至子代對應(yīng)位置；

第三步：刪除另一個父代染色體循環(huán)節(jié)點，將余下的循環(huán)節(jié)點復(fù)制到子代上；

第四步：同樣的方法獲得另一個子代。

（6）變異。在遺傳算法中，和交叉操作一樣，變異操作的目的同樣是得到新個體。變異操作是指通過改變?nèi)旧w編碼串上的一部分基因以得到新個體。變異操作能有效增強種群的多樣性，可以保證遺傳算法的局部搜索能力，與交叉操作配合實用能夠有效確保遺傳算法的全局搜索能力。為了有效避免變異后新個體趨同，需要結(jié)合變異操作保持種群個體的隨機性。本文選用翻轉(zhuǎn)變異方法進行變異操作。

第一步：依據(jù)變異概率選擇父代變異個體；

第二步：隨機選取兩個變異點，實施翻轉(zhuǎn)操作；

第三步：獲得子代變異個體。

（7） 終止條件。在經(jīng)過多次迭代后，遺傳算法的解與最優(yōu)解趨近，但還不能真正得到最優(yōu)解。因此，需要合理設(shè)置一個終止條件。如迭代到一定次數(shù)之后，遺傳算法自動停止迭代；當?shù)^程中染色體適應(yīng)度停止變化或變化很微小時，就表示遺傳算法得到了近似最優(yōu)解，應(yīng)停止迭代。本文改進后的終止規(guī)則采用雙重終止條件，即如果連續(xù)幾代種群間之間的平均適應(yīng)度值變化小于某一標準值時；迭代次數(shù)達到要求，此時算法終止，提取最優(yōu)個體并解碼，得到冷鏈物流最優(yōu)路徑。

3 結(jié)束語

綜上所述，本文對傳統(tǒng)的冷鏈物流路徑優(yōu)化中應(yīng)用的遺傳算法進行了改進，旨在更好地發(fā)揮遺傳算法的作用，提高冷鏈物流路徑優(yōu)化效率。

參考文獻：

[1]陶云，張鵬程.基于改進遺傳算法的冷鏈物流路徑優(yōu)化研究[J].蚌埠學(xué)院學(xué)報，2016，5（03）：85-90.

[2]孔志周，官東.基于改進遺傳算法的車輛路徑優(yōu)化研究[J].統(tǒng)計與決策，2007（16）：163-165.