基本介紹
- 中文名：物流線路最佳化算法
- 外文名：Logistics route optimization algorithm
禁忌搜尋算法,模擬退火算法,遺傳算法,蟻群算法,
禁忌搜尋算法
禁忌搜尋法(Tabu Search，簡稱TS)是Glover於1986年所提出，它是對局部領域搜尋的一種擴展，是一種全局逐步尋優法，是對人類智力過程的一種模擬[11]。禁忌搜尋技術是一種亞啟發式搜尋技術，所謂禁忌就是禁止重複前面的工作.為了迴避局部鄰域搜尋陷入局部最優的主要不足，禁忌搜尋算法用一個禁忌表一記錄下己經到達過的局部最優點，在下一次的搜尋中，利用禁忌表中的信息不再搜尋這些點，以此來跳出局部最優點。就好比人的短時記憶，走過的路不再重複或有選擇地重複；同時“遺忘”又使得這些禁止是弱禁止，即在一定的時間之後這些禁止將失效，最終達到全局最佳化之目的。TS算法在組合最佳化、生產調度、機器學習、電路設計和神經網路等領域取得了很大的成功，又在函式全局最佳化方面得到很多的研究，並有較大的發展。
禁忌搜尋法的主要演算流程：可分為起始解的求取、鄰域的定義、禁忌名單的設計、與移動後的評估。首先以一起始解作為搜尋的起點，接著進行搜尋的程式。在搜尋的過程中，為避免產生循環的現象，故建立禁忌名單(TabuList)來記載搜尋的過程。禁忌名單的結構特性及其長度，可避免求解的過程之中，陷於區域解的現象。但禁忌名單可能會限制了求解的範圍，所以必須運用免禁準則來加以克服。其中禁忌對象、禁忌長度、鄰域結構、評價函式和候選集以及特赦準則的確定是禁忌搜尋算法設計的核心，此外還包括特赦規則和終止規則的確定。
缺點：禁忌搜尋算法對初始解的依賴性強，如果初始解較差，會使禁忌搜尋算法的收斂速度下降，另外由於疊代搜尋過程是串列的，僅是單一狀態的移動，不是並行搜尋，這樣影響了最佳化效率。
模擬退火算法
模擬退火算法(simulatedAnnealing，簡稱SA):是由Metropolis等人提出的，直到上世紀80年代才逐漸為人們所重視，並得到了廣泛的套用，是一種啟發式隨機最佳化方法，而且是啟發式最佳化方法中比較成熟的一種通用的最佳化方法[12]。模擬退火算法算是對局部搜尋算法的擴展。其區別在於:它是以一定的機率選擇鄰域中目標函式值差的狀態。退火是一種物理過程，一種金屬物體在加熱至一定的溫度後，它的所有分子在其狀態空間中自由運動。隨著溫度的下降，這些分子逐漸停留在不同的狀態。在溫度最低時，分子重新以一定的結構排列。統計力學的研究表明，在同一個溫度，分子停留在能量小的狀態的機率比停留在能量大的狀態的機率要大。當溫度相當高時，每個狀態的機率基本相同，都接近平均值。當溫度趨向O時，分子停留在最低能量狀態的機率趨向於1。
模擬退火算法是一種基於上述退火原理建立的隨機搜尋算法。組合最佳化問題與金屬物體的退火過程可進行如下類比：組合最佳化問題的解類似於金屬物體的狀態，組合最佳化問題的最優解類似於金屬物體的能量最低的狀態，組合最佳化問題的費用函式類似於金屬物體的能量。
為了克服局部搜尋算法極易陷入局部最優解的缺點，模擬退火算法使用基於機率的雙方向隨機搜尋技術:當基於鄰域的一次操作使當前解的質量提高時，模擬退火算法接受這個被改進的解作為新的當前解；在相反的情況下，算法以一定的機率exp(△c/T)接受相對於當前解來說質量較差的解作為新的當前解，其中△c為鄰域操作前後解的評價值的差，T為退火過程的控制參數(即溫度)。模擬退火算法已在理論上被證明是一種以機率1收斂於全局最優解的全局最佳化算法。
缺點：為了獲得全局最優解，要求較高的初始溫度，要求退火的速度足夠慢，要求較低的終止溫度和各種溫度下足夠多次的抽樣，這就使得最佳化過程長，特別是對於規模大的實際問題。因此，最佳化效率不高是標準模擬退火算法的主要缺點。其次最佳化的質量對初始溫度很敏感；參數的選擇也是套用該算法的難題之一。
遺傳算法
1975年J.Holland受生物進化論的啟示提出了遺傳算法(GeneticAlgorithms，簡稱GA)。GA是借鑑於達爾文的“適者生存”的理論，將最佳化問題的求解表示成“染色體”，通過“染色體”群的一代代複製、交叉、變異的進化，最終得到最適應環境的個體，從而得到了問題的最優解或滿意解[13]。這是一種高度並行、隨機和自適應的通用的最佳化算法。遺傳算法的一系列優點使它越來越受到重視，在解決眾多領域的機器學習、模式識別、最佳化控制、組合最佳化等最佳化問題中得到了廣泛的套用。
缺點：GA中算法的參數選擇比較困難，在避免“早熟”收斂方面和提高收斂速度方面沒有通用的好方法，只能針對具體問題進行具體設計
蟻群算法
蟻群算法（ACA）是一種模擬螞蟻覓食行為的啟發式搜尋算法，由義大利學者M.Dorigo提出，其主要特點是：正反饋、並行式搜尋。它尤其適用於處理傳統搜尋方法難於解決的複雜和非線性問題，可廣泛用於機器學習、組合最佳化、規劃設計、自適應控制和人工生命等領域，是21世紀有關計算智慧型中的關鍵技術之一。
對蟻群算法的研究，可以從算法和套用兩方面進行研究。不斷有學者提出對蟻群算法進行改進：有的將蟻群算法同遺傳算法相結合，有的給蟻群系統加入變異特徵，還有的提出所謂最大最小蟻群算法(MMAS)。應當指出，現階段對蟻群算法的研究還只是停留在仿真階段，還未能提出一個完善的理論分析，對它的有效性也沒有給出嚴格的數學解釋。
蟻群算法本身就是一個尋找最短路徑的模型，因此它在路徑最佳化方面有著天然的優勢，己經有不少蟻群算法在TSP問題中成功運用的例子。物流配送路徑最佳化問題和TSP問題相比有共同點——都是尋找遍歷所有客戶點的最短路徑的問題，也有其特性——有更多更複雜的約束條件和最佳化目標。本文就是要研究一種基於蟻群算法的最佳化路徑算法，使得其在物流配送路徑最佳化問題中有較好的實際效果。
