基于改進遺傳算法的冷鏈物流路徑優化

袁紫微

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

關鍵詞：遺傳算法；冷鏈物流；路徑優化

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

1 引言

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

2 冷鏈物流路徑優化的遺傳算法分析與改進

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

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

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

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

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

第一步：依據交叉概率選擇一對父代染色體，從中找到循環點；

第二步：復制其中一個父代染色體的循環節點至子代對應位置；

第三步：刪除另一個父代染色體循環節點，將余下的循環節點復制到子代上；

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

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

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

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

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

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

3 結束語

綜上所述，本文對傳統的冷鏈物流路徑優化中應用的遺傳算法進行了改進，旨在更好地發揮遺傳算法的作用，提高冷鏈物流路徑優化效率。

參考文獻：

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

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