針對幾種元啟發式算法的應用性能對比研究

尚正陽，顧寄南，唐仕喜，孫曉紅

（1.安徽工程大學機械與汽車工程學院，安徽 蕪湖 241000；2.江蘇大學制造業信息化研究中心，江蘇 鎮江 212000）

1 引言

啟發式算法（heuristic algorithm）是一種根據人為經驗或者自然規律所構造的算法，它能夠在可接受的計算花費下給出一個較優的可行解。現階段，由于元啟發式算法（meta-heuristic）具有較少依賴算法本身組織結構的特點，其通用性強、泛化性好，已經被廣泛應用在了實際生產和生活的各個領域。特別是針對工業中大量存在的NP-hard 問題，元啟發式算法已成為求解此類問題的主要途徑。在此，將針對具有代表性的四種算法：遺傳算法（Genetic Algorithm，簡稱GA）、模擬退火算法（Simulated annealing algorithm，簡稱SA）、禁忌搜索算法（Tabu Search，簡稱TS）和蟻群算法（Ant Colony Optimization，簡稱ACO）進行基于其應用性能的對比分析。其中，遺傳算法于1975 年被文獻[1]提出，它借鑒了生物的進化過程，能夠按照優勝略汰的原則對群體目標進行逐代演化；模擬退火算法于1953 年被文獻[2]提出，它模擬了固體退火原理，能夠通過對新解的動態概率接收來獲得一個較優解；禁忌搜索算法于1986 年被文獻[3]提出，它模擬了人類記憶過程，通過引入禁忌表來避免迂回搜索實現全局優化；蟻群算法于1992 年被文獻[4]提出，該算法模擬了螞蟻尋食過程中的路徑發現行為，能夠在正反饋機制的作用下逐漸增加對較優解的獲得概率。以上四種元啟發式算法，由于具有較好的適應性和求解效果，已經在路徑規劃[5-6]，資源調度[7-8]和參數優化[9-10]等多個方面得到了普遍應用。除此之外，為提高針對特定對象的優化能力，算法之間也能夠通過模塊耦合來實現其功能上的互補，例如混合遺傳模擬退火算法[11-12]，遺傳蟻群算法[13-14]，模擬退火蟻群算法[15-16]等。所以對于相關算法求解過程和求解效果的研究就尤為重要，它是實現具體工程問題高效求解的關鍵。然而，正是由于啟發式算法的“仿生”特性，對其求解性能的描述往往停留在認知層面，缺少具體的對比和論證。特別是在實際應用中，相關算法的選擇往往依靠人為經驗，同一問題能夠被不同學者結合不同算法進行求解。所以，對于以上四種算法的對比分析，不僅能夠明確其各自的特點屬性，還能夠為相關算法的合理選擇和性能改進提供基礎與參考。

2 算法解析

通常，實際問題被轉化為序列的組合優化問題進行求解，而元啟發式算法就是要在有限的計算消耗中，找到一個較優的可行解。其中，這個排列組合被稱為解，由排列組合代入實際問題所計算出的結果被稱為適應度。總的來看，元啟發式算法的優化機理，如圖1 所示。

圖1 元啟發式算法優化機理Fig.1 Optimization Mechanism of the Meta-Heuristic Algorithm

算法通過不斷的對單個或者多個解（包括初始解）的鄰域結構改變來形成新解，并進一步的通過對新解的接受與篩選生成更優解。在這個循環迭代過程中，最核心的內容是新解的產生方法和更優解的接受原則（分別如圖1 中的方形虛線和圓形虛線所示），它們決定了整個算法的工作原理與操作方式。值得注意的是，雖然針對不同問題，同一算法的新解產生方法和更優解接受原則不盡相同，但是其整體的求解特性并未改變。所以為了便于分析，以最為基礎且通用的組織方式來構建算法，旨在實現對以上四種元啟發式算法求解性能的直觀比較。

2.1 遺傳算法

遺傳算法主要包括交叉操作、變異操作和選擇操作三個部分。其中，變異和交叉是種群產生新解的具體方法，而選擇則包含了更優解的接受原則。在執行過程中，變異為選擇提供資料，交叉用于鞏固選擇結果，選擇則能夠引導變異和交叉朝著適應“環境”的方向發展。

在實驗中，交叉操作，如圖2 所示。兩個父代的第3 到第5號位置需要進行交換，在此采用循環的方式進行逐個改變。特別的，每當兩個位置的數值交換后，還應對數列中的重復數字進行調整。變異操作，如圖3 所示。突變發生在單個父代序列的3 號和6 號位置，這兩個位置中的數值進行交換。而選擇操作則設置為常規的賭輪盤方式。

圖2 交叉操作Fig.2 Cross Operation

圖3 變異操作Fig.3 Mutation Operation

2.2 模擬退火算法

模擬退火算法源于固體退火原理：高溫固體在冷卻過程中，所包含粒子在每個時刻都極力趨向平衡態，其能量隨溫度的降低而逐漸減少，直至常溫達到基態。在此過程中，新解的產生通常采用隨機的鄰域改變方法，而對更優解的接受則完全模擬了固體的退火過程，即算法執行前期以較大概率接受一個非更優解為更優解，從而保證算法的全局搜索能力，而在執行后期則以較小概率對非更優解進行接受，用以保留當前已獲得的相對較優解。其中，接受概率隨“退火溫度”的改變而逐漸變小。

2.3 禁忌搜索算法

禁忌搜索算法模擬了人類記憶過程，其中新解產生采用了隨機的鄰域結構改變方法，而對新解搜索則引入了禁忌表，禁忌表能夠記錄已搜索過的較好鄰域結構，從而在下次迭代中主動避開已記錄的鄰域移動，減少重復操作。對于更優解的接受原則則通常采取貪婪的擇優選取方法。從新解產生和更優解接受的角度上看，遺傳算法和模擬退火算法的主要操作來自于對更優解的接受，而禁忌搜索和蟻群算法的關鍵則在于對新解的產生和搜索，這是它們之間的最大不同。

圖4 禁忌搜索算法原理圖例Fig.4 Schematic Illustration of Tabu Search

在一次鄰域結構改變中，從位置1 到位置2 為已得到的最短距離，故而將其列入禁忌表暫時禁止（0 表示被禁止選擇，1 表示可以被選擇），以此來增加算法對其他路徑的搜索概率，如圖4所示。其中鄰域改變的受禁忌范圍影響著算法的全局搜索能力，受禁范圍小，則搜索范圍大收斂速度慢，受禁范圍大，則搜索范圍小求解精度低。

2.4 蟻群算法

蟻群算法模擬了螞蟻在尋食過程中的路徑發現行為。實際上，它與禁忌搜索算法具有一定的相似性，都能夠按照一定規則進行新解的搜索與接受。不同的是，蟻群算法中基于正反饋機制所建立起來的禁忌表，并不單純的代表著禁止與允許操作，而是能夠通過對每一個鄰域移動概率的動態更新，來趨向性的引導新解（更優解）產生。

在一次鄰域改變中，從位置1 到位置2 的選擇概率為1/2，從位置1 到位置3 的選擇概率為1/18，以此類推，如圖5 所示。這些選擇概率能夠在每一次迭代中不斷積累，從而實現最終較優解的獲得。特別的，禁忌搜索和蟻群算法都依賴于禁忌表的建立，故而其優化對象也就要求具有相對穩定且獨立的鄰域結構。

圖5 蟻群算法原理圖例Fig.5 Schematic Illustration of ACO Algorithm

3 實驗與分析

3.1 實驗設計

為對比分析遺傳、模擬退火、禁忌搜索和蟻群算法的求解性能，在此以典型的序列優化模型—旅行商問題（TSP）為對象，構建實驗。其中，TSP 問題是指旅行商人需要經過n個城市并最終回到原點，且每個城市僅能經過一次，其目標是求得一個最短的Hamilton 路徑回路。對于n個城市，一共有（n-1）! /2 條可能路徑，這是一個典型的NP-hard 問題。

其中，五個不同規模和類型的TSP 算例chn31、eil76、pr152、tsp225、lin318 被進行了測試，它們都來自于國際通用的TSP 測試庫[17]。基本參數，如表1 所示。為便于表達和對比，在實驗中用相對距離來表示算法的計算結果，相對距離為求解距離與最短距離的比值。

表1 TSP 算例參數Tab.1 Parameters of TSP Instances

在參數設置方面，為體現出不同算法在不同計算維度下的求解效果，在此按照普遍的工程應用經驗進行設置，其三種不同規模的參數被列出，如表2 所示。表中：n—目標函數的數列長度，遺傳算法發生變異的基因個數為0.05*n，模擬退火算法和禁忌搜索算法采用2-opt 的鄰域改變策略。

表2 GA、SA、TS 和ACO 算法的計算參數設置表Tab.2 Parameters Setting for GA，SA，TS and ACO Algorithms

3.2 遺傳算法與模擬退火算法

首先，對遺傳和模擬退火算法在小計算量、中計算量和大計算量參數下的五個TSP 算例進行測試。實驗結果為算法運行20次的平均值。隨著計算量的逐漸增大，五個算例的平均求解距離逐漸變小（求解效果逐漸變好），計算時間逐漸增大，說明GA 與SA 的計算精度和運行時間隨著計算量的增加而增加，如表3 所示。

表3 遺傳算法與模擬退火算法的計算結果Tab.3 Results of GA and SA

從不同規模的算例求解上看，在小計算量情況下GA 和SA都能對算例chn31 取得不錯的解，而對于大規模算例lin318 則需要較大的計算量。說明隨著對象規模的遞增，算法收斂所需要的計算量也隨之增加。特別的，針對不同規模的算例pr152 和tsp225，在中計算量和大計算量條件下，GA 對于pr152 的計算結果是優于tsp225 的，而SA 對于小規模算例pr152 的計算效果反而不如tsp225。這說明基于個體操作的SA 在求解效果上受對象特征影響較大。總的來看，在相同運算時間下SA 對TSP 問題的求解效果普遍優于GA。

為進一步對GA 和SA 的優化性能進行分析，其在大計算量參數下的求解過程被給出，如圖6 所示。可見，對于基于種群進化的GA，大型算例pr152、tsp225 和lin318 的優化過程并沒有充分收斂，較大的目標算例往往需要較多的迭代次數才能達到較優的求解效果。而對于SA，不同算例的收斂曲線相差較大（多次實驗效果類似），這從也另一方面說明了其求解性能受對象特征的影響較大。除此之外，在SA 的求解過程中，無論是大規模算例還是小規模算例，主要優化行為都發生在退火的“高溫”和“中溫”區域，而在“低溫”區域則相對緩慢，所以合適的退火參數選擇就對SA 的優化效果至關重要。

圖6 在大計算量條件下的遺傳算法（a）和退火算法（b）的求解過程Fig.6 Solving Process of GA（a）and SA（b）in Large-Scale Computing

3.3 禁忌搜索與蟻群算法

在同等實驗條件下，禁忌搜索與蟻群算法的計算結果，如表4 所示。由于禁忌搜索和蟻群算法都是基于禁忌表的搜索算法，在此將其對比分析。從整體上看，無論是在小計算量、中計算量還是大計算量的參數設置下，ACO 都能夠獲得一個較好的求解效果。特別的，即使在小計算量條件下，ACO依然能夠針對大規模算例lin318 取得一個不錯的解，這是明顯優于其他算法的。而針對單個個體優化的Tabu 算法，對小規模算例pr152 的求解效果反而不如大規模算例tsp225，其受對象特征的影響較大。具體Tabu 和ACO 在大計算量參數下的求解過程，如圖7 所示。

表4 禁忌搜索算法與蟻群算法的計算結果Tab.4 Results of TS and ACO

Tabu 在迭代過程前期的優化速度較快，但是隨著算法的運行其尋優能力逐漸變緩，如圖7（a）所示。而對于ACO，它能夠快速的得到一個較優解，相對于其他三種算法，ACO 在第一步中就完成了整個優化過程的90%，進而能夠在較少的迭代次數下完成計算收斂，如圖7（b）所示。

圖7 在大計算量條件下的禁忌搜索和蟻群算法求解過程Fig.7 Solving Process of TS（a）and ACO（b）in Large-Scale Computing

3.4 總體實驗結果分析

為總體定量的對四種元啟發式算法進行對比分析，分別將其在三種不同計算量下的平均運算結果匯總，如表5 所示。

表5 四種算法的總體計算結果Tab.5 Comparative Results on the Algorithms

從求解效果上看，在運算時間相似的情況下，蟻群算法獲得了1.11 倍最優路徑距離的平均相對距離，優于其他三種算法。特別是在小計算量的參數設置下，其表現依然優秀。模擬退火算法和禁忌搜索算法都是基于單個對象的迭代操作，其在鄰域結構較為簡單的TSP 問題中也表現出了不錯的性能。而遺傳算法則表現最差，在平均120s 的時間里獲得了3.95 倍的平均相對距離。

4 結論

首先從新解產生方法和更優解接受原則兩個方面入手，對遺傳、模擬退火、禁忌搜索和蟻群算法進行了解構與分析，指出了其在原理與結構上的異同。之后結合不同規模的TSP 問題構建了多維度的對比實驗，通過對算法求解過程和求解效果的深入分析，得到如下結論：（1）GA 是一種基于種群進化的搜索算法，它具有較強的魯棒性且求解效果穩定。但是收斂速度緩慢，特別是對于大型算例，GA 往往需要更多的運算消耗才能得到一個較優的解。（2）SA 是一種基于單個個體不斷變異優選的搜索算法，求解效果受其對象特征的影響較大。所以為了得到更好的計算結果，通常需要根據具體對象進行針對性的鄰域結構（新解的產生方法）和退火參數（更優解的接受原則）設計。（3）Tabu 和ACO 都是基于禁忌表的搜索算法，適合應用在具有穩定領域結構（鄰域移動能夠受禁忌表控制）的優化問題中。實際上，ACO 可以看作是Tabu 算法的改進和擴展，一方面它更新了具有趨向性的概率新解產生方式，加強了算法的全局搜索能力，能夠準確并快速的進行求解；另一方面，它相較于Tabu 引入了基于種群的進化模式，有效降低了求解結果受初始解和隨機操作等因素的影響。雖然ACO 的構造及參數設置相對復雜，但是其能夠在第一次迭代中就找到一個不錯的解，執行高效。

所做工作實現了常見四種元啟發式算法的定量對比，為相關技術人員的選擇、應用和改進提供了基礎與參考，具有一定的工程應用價值。進一步的，將擴展算法對比目標，深化算法對比內容，實現更加全面和準確的算法性能解析。