告別復雜計算！用進化計算高效破解路徑優化難題（上）

導語

外賣派送、物流規劃、滅火救災等機器人調度，本質上都離不開路徑優化這類組合優化問題?，F實場景中的這類問題規模大、約束多、變化快。計算智能已成為主流工具，其中進化計算等群體智能方法擅長全局搜索，強化學習等個體智能方法更適合從交互中學策略。在集智俱樂部《》上，賈亞暉老師做了《強化學習路徑優化：群體、個體智能協同算法》的主題報告，詳細介紹了相關方法。本文我們將先介紹進化計算，以及其在電動車路徑優化，多機器人任務分配以及動態交通分問題中的應用。梳理算法的設計思路，并探討其求解質量與適應性。

關鍵詞：組合優化（Combinatorial Optimization）、車輛路徑優化（Vehicle Routing Problems）、進化計算（Evolutionary Computation）、蟻群算法（Ant Colony Optimization）

劉向宇丨作者

目錄

1. 從組合優化說起

2. 從計算智能到進化計算

3. 蟻群優化算法求解電動車路徑優化問題

4. 粒子群算法求解多機器人任務分配問題

5. 遺傳編程算法求解動態交通規劃的問題

6. 未來的工作方向

1. 從組合優化說起

我們在高中階段都接觸過線性規劃問題，其目標是在線性約束下求一個線性目標函數的最大值或最小值，決策變量通常是連續的。線性規劃是類似的，組合優化的目標也是尋找最值。但其研究如何從有限個離散對象的組合中尋找滿足條件的最優方案，決策變量是離散的，典型的問題包括旅行商問題、背包問題與車間調度問題。

在解決這類問題時，我們最初想到的通常是精確的求解方法。如分支定界法，割平面法等精確的求解方法。這些方法通常適用于小規模問題或要求證明最優性的場景。當問題規模大、結構復雜或需要快速求解時，啟發式算法是更實用的選擇。啟發式方法通常分為兩種類型。第一種是解構造方法，即按照某種策略直接構建出一個可行解。第二種是解改進方法，先產生一個質量較差的初始解，然后通過一系列簡單而有效的規則對其進行迭代優化。這類規則往往需要借助一定的專家知識來設計，雖然不能保證得到全局最優解，但通常能獲得易于理解且效果可接受的結果。

1. 從計算智能到進化計算

啟發式方法屬于計算智能（Computational Intelligence, CI）領域，IEEE計算智能官網對其介紹如下。計算智能是指受生物學和語言學啟發的計算范式的理論、設計、應用和開發[1]。計算智能包含三個方面如圖1。第一是進化計算（Evolutionary Computation，EC），第二類是神經網絡（Neural Networks，NNs），第三類是模糊系統（Fuzzy system，FS）。

圖1 計算智能領域知識框架

（1）進化計算方向：以生物進化，種群行為為靈感來源的進化計算通過生成、評估和修改可能解的群體來解決優化問題。該領域涵蓋遺傳算法、進化規劃、進化策略、遺傳編程、群體智能、差分進化、可進化硬件、多目標優化等多種方法。

（2）神經網絡方向：以人腦為靈感來源的人工神經網絡是大規模并行分布式網絡，具備從案例中學習并進行概括的能力。該研究領域涵蓋前饋神經網絡、遞歸神經網絡、自組織神經網絡、深度學習、卷積神經網絡等多種類型。

（3）模糊系統方向：以人類語言為靈感來源的模糊系統能夠對語言的不精確性進行建模，并基于傳統邏輯的泛化來解決不確定性問題，使我們能夠進行近似推理。該研究領域涵蓋模糊集合與系統、模糊聚類與分類、模糊控制器、語言概括、模糊神經網絡、二型模糊集合與系統等多種類型。

本文我們主要探討進化計算方法，這種方法可根據遺傳算法分為進化優化與進化學習算法。優化是指直接針對當前問題構建一個優化算法逐步求解。學習是指從多個問題實例中學習一個模型，然后利用模型去求解當前的問題。

進化計算可大致分為如圖2所示三類，這與“群體智能”概念緊密相關。首先是受進化論啟發的進化算法涵蓋遺傳算法（Genetic Algorithm，GA）、進化策略（Evolution Strategy，ES）和遺傳編程（Genetic Programming，GP）等。其次，受自然界生物群體行為啟發的群體智能優化方法，如粒子群優化（Particle Swarm Optimization，PSO）、蟻群優化(Ant Colony Optimization，ACO)和人工蜂群算法(Artificial Bee Colony，ABC)，也屬于這一范疇。此外，進化計算還包括差分進化(Differential Evolution，DE)、分布估計算法（Estimation of Distribution Algorithm ，EDA）以及學習分類器（learning classify system，LCS）。其中，GP和LCS更偏向學習算法，其余則為優化算法。這些方法在運籌學中常被統稱為“基于種群的方法”。像蟻群優化、粒子群優化屬于此類，而遺傳編程等可視為“超啟發式”方法，旨在自動生成啟發式規則。

圖2 進化計算概念框架

3. 蟻群優化算法求解電動車路徑優化問題

自然界中螞蟻群體在覓食時總能沿著最短路徑到達食物源。經研究，螞蟻覓食時釋放信息素，蟻群感知并跟隨高濃度路徑行走，每只螞蟻也會留下信息素。這種正反饋機制使蟻群逐漸聚集到最短路徑，從而高效到達食物源。受到這一現象和機理的啟發。意大利學者Marco Dorigo于1992年在其博士論文中首次提出蟻群算法，將螞蟻覓食過程中依賴“信息素”進行路徑選擇的行為抽象為一種高效的啟發式優化算法。其中最關鍵的兩步，第一步是構造解。一只螞蟻將從節點i到節點j，其概率如下式（1）。

其中τij是邊i→j上的信息素總量，代表“過往經驗”的積累。

α：控制信息素影響力的參數。α越大，算法偏向利用已知優質路徑；α越小，算法更愛探索新路徑。

ηi,j：邊i→j的啟發式吸引力。

β：控制啟發式信息影響力的參數。β越大，算法更聚焦局部最優；β越小，算法更依賴全局經驗。

第二步為更新解。邊i→j的信息素更新如下式（2）。

其中τij：更新后，邊i→j的信息素總量。

ρ：信息素蒸發率(0 <ρ<1)< pan> ，表示信息素自然消散的比例。

Δτi,j：本輪迭代中，所有螞蟻在邊i→j上沉積的信息素量，其計算公式如下式(3)。

其中Lk是第k只螞蟻在本輪迭代路程。

圖3 電動車車輛路徑優化問題示意圖

車輛路徑問題（Vehicle Routing Problems，VRP）是組合優化中一個極其重要且應用廣泛的經典問題，也是供應鏈管理中最具代表性的實際難題之一。它旨在為一組車輛設計最優的行駛路線，以服務多個客戶點，在滿足各種約束（如載重、時間、距離）的前提下，優化總成本、車輛數或行駛距離等目標。復雜的模型還要考慮送貨時間，例如客戶要求只能在上午或下午送貨等約束條件。電動車車輛路徑優化問題（Electric Vehicle Routing Problem，EVRP）是VRP問題的子問題，載有一定量貨物的電動車從倉庫出發，服務所有客戶點。為一個電動車輛車隊規劃行駛路線，在滿足載重與電量雙重約束下，決定下一個客戶的目的地。最終的解是車輛尋找服務順序與充電規劃，以最小化總成本，其最基礎的目標仍是最小化總行駛路程。

將約束條件分開后，這個問題可以拆分為兩個子問題。第一個是傳統的容量限制車輛路徑問題（CVRP），它考慮了車輛的容量約束，但不涉及充電。另外一個是固定路線車輛充電問題（FRVCP），在給定路線的情況下，選擇最佳的充電策略。 可以簡單地認為這兩個問題是相加的。然而，如果按照加法的方式，先解決CVRP再解決FRVCP，無法保證得到最優解。

圖4 BACO算法結構

傳統容量限制車輛路徑問題（CVRP）已有豐富研究，在此基礎上，文獻[2]提出一種如圖4所示的BACO雙層蟻群優化算法。對應兩個層級的子問題，BACO生成一個可行解需要兩個步驟。首先，通過移除電量約束和充電站，將CEVRP降級為對應的CVRP。僅考慮配送中心和客戶，應用OS-MMAS算法來生成對應CVRP的容量可行路徑。然后，在給定容量可行路徑的基礎上，將電量約束納入考慮。為固定路徑尋找最優充電調度的問題被稱為FRVCP。為了有效且高效地解決FRVCP，文章提出了移除啟發函數，RH算法。下層RH算法為上層OS-MMAS生成的路徑找到充電方案后，計算得到完整CEVRP解的目標值（總行駛距離），并用此反饋信息來更新上層ACO的信息素，從而引導蟻群在未來迭代中向更優的客戶服務順序搜索。算法在搜索結束后，采用一種限制性枚舉方法對全局最優解中的每條路徑進行精細化搜索，以進一步提升充電方案的質量，返回全局最優解。

圖5 移除啟發執行示意圖

移除啟發函數通過兩階段操作確定充電位置。在插入階段，為路徑中每一對連續節點插入帶來最小額外行駛距離的充電站，確保路徑滿足電量約束。隨后在移除階段，逐個檢查已插入的充電站，若移除后路徑仍滿足電量約束，則記錄其可節省的距離；最終移除可節省距離最大的充電站。重復此過程直至無充電站可移除，輸出電量可行的最終路徑。示例如圖5所示，假設從零號倉庫出發，經過一號、二號、三號和五號顧客，最后再返回倉庫。在每兩個點之間添加三角形充電站。在完成充電站的添加后，逐一刪除那些不必要的充電站，或者是距離太遠的充電站。這其中涉及到一些策略判斷。經過刪除后，得到了一個包含充電決策的最終路徑，這條路徑還包括服務這些顧客的順序。充電次數最多不會超過四次，問題規模較小時，直接進行窮舉實際上是可行的。

圖6 ACO算法結果

圖6是文中ACO算法的一些結果，已經取得了不錯的效果。然而，ACO算法存在一個致命的缺點：首先，它的參數調節非常困難；其次，它的運行速度極慢。單靠群體算法本身，如果不添加大量的局部搜索，算法的運行速度會非常緩慢。 因此，文中加入了許多局部搜索，這是一種在求解CVRP問題時表現優秀的優化算法，稱為HGS（Hybrid Genetic Search）。從結果來看，這個HGS算法的優化速度明顯快于文中ACO方法。

4. 粒子群算法求解多機器人任務分配問題

多機器人任務分配（Multiple Robot Task Allocation，MRTA）問題是為多種任務調配足夠數量的機器人。問題的目標是為每個機器人找到執行時間（完成時間）最短的最優計劃。約束有機器人隨時間變化的約束、機器人能力約束以及機器人間的協作方式約束等。

圖7 多機器人救火場景任務分配問題

如圖7所示，在救災場景中，如果某個地方發生火災，單個機器人可能無法撲滅大火，這時就需要一群機器人共同協作來完成救援任務。 在任務執行中，參與的機器人越多，任務完成的速度也會越快。我們的目標是調度一群機器人，完成分散在地圖上的動態任務。這里的“動態”指的是任務量會不斷增加。

PSO算法適用于上述問題。PSO算法的提出者是一位心理學家。他觀察到鳥類覓食時的行為，發現鳥類在尋找食物的過程中，會記住曾經找到食物的地方，并繼續探索其他區域。此外，鳥群之間會共享信息。這些觀察促使算法的設計者制定了簡單的更新公式。

圖8 粒子群算法示意圖與流程圖

PSO算法的框架步驟僅有三步。首先生成初始的粒子群，評價其適應度，不斷更新粒子群的速度與位置直到算法收斂。在PSO算法中，每個個體（或稱鳥）代表一個解，位于問題空間中的一個點。這只鳥的下一步探索方向是如公式（4），個體的速度向量由以下幾個部分組成：第一部分是原始速度和一個慣性權重的結合；第二部分是鳥之前發現的優質解的引導；第三部分則是整個種群曾經找到的最優解的引導。通過將這三個向量相加，便得到了新的速度向量。個體的新位置則是當前的位置加上更新后的速度，如公式（5）。PSO算法最初是為了求解連續優化問題而設計的，公式中主要是加、減、乘的運算。

然而，PSO算法本身只是一個框架，并不局限于連續優化。文章[6]考慮每個解X都是一個集合。只需定義實數與集合的乘法、集合之間的減法和加法，便可實現組合優化的求解。 在多機器人任務分配的問題上，文章進一步增加了難度，引入了任務點之間的依賴關系。這使得問題變得更加復雜。

在完成一個進一步升級的任務后，文獻[5]提出了一個更加簡化且適用于路徑優化的算法，多階段粒子群優化算法（multi stage PSO，MSPSO），這種算法主要是基于減法。以排列問題為例，x1代表第一個機器人依次完成一號、二號、三號和四號任務，而x2則代表這個機器人完成三號、十三號任務后，再執行一號、二號和四號任務。這兩個序列的差異可以通過直接將它們視為實數進行減法運算。經過計算，得到的結果是-2，1，1，0。為了處理負數，將所有負值歸零，這就是文中定義的離散減法。文中將正數的元素向前移動。例如，原來的序列3124，經過x1減去x2的運算，得到的就是x2，能將2和3互換，再將1和2互換。會發現加法便是將元素向前調整。這樣，路徑就相應地改變了。 通過重新定義減法和加法，便得到了一個新的粒子群算法，可以用于路徑優化。

圖9 MSPSO算法加減法規則

下圖10是最終的優化結果。左邊顯示文中提出的這個多階段粒子群優化算法的效果非常顯著。右邊展示的是一個實例，12個機器人完成眾多任務。該圖展示每個機器人先執行幾號任務，再完成幾號任務。顯而易見，MSPSO算法最終得到的解比遺傳算法要短得多，整體安排更優。此外，MSPSO還展現了更豐富和合理的多機器人協作完成一個任務的情況。

圖10 MSPSO算法優化效果

5. 遺傳編程算法求解動態交通規劃的問題

前面提到的兩個優化算法可以視為元啟發算法的一種，而現在要提到的遺傳編程則是一種超啟發式方法。遺傳編程通常不用于求解信息完全已知的靜態問題，而是更適用于動態或不確定的環境，其目標是生成一種能夠實時調整的策略，而非一條固定路徑。例如，快遞員在取件時若遇到客戶提交信息與實際不符，原定路線可能不再最優。此時需要的是能即時響應變化的決策策略，而遺傳編程正是為了自動生成這類適應性策略而設計的算法。

圖11 任務樹形結構

如遺傳編程算法結構如圖11所示樹形結構來展示。下方是一個數學表達式，它代表了遺傳編程中一個解的調度規則。 在這個表達式中，X和Y可以視為某個任務的特定屬性。最終計算得出的值，可以理解為優先級。 輸出值通常是路由調度問題中候選者的優先級。值越大越大優先級越高，反之亦然。因此，這個過程就變成了一個學習任務。 我們可以使用一些生成的訓練實例，輸入到遺傳編程算法中，從而生成這樣的模型即調度規則。最終，我們可以把這個調度規則應用到其他相似的動態環境。

利用遺傳編程求解去求解中心化動態交通分配問題（Decentralized Dynamic Traffic Assignment，DDTA）以一個有關動態交通規劃的問題。在這個問題中，文獻[6]設想了一個分布式的場景。是一個去中心化的系統，每輛車根據自身所處的環境和后續路徑，自主決定應該選擇哪條路。在靜態路徑的交通分配中，交通流量是固定的，并且與時間無關。 這種情況可以通過一些靜態優化算法來求解，比如整數規劃、線性規劃或遺傳優化算法等。 然而，動態交通流則可能與時間相關，且往往是混亂的。 因此，這種情況下只能采用一些學習方法進行求解。

文獻中動態交通分配問題的目標是最大化在特定時間段內完成行程的車輛數。車輛在當前位置u，需要經過節點vi去到目的地。選擇使 “從u到vi的實時距離D” 加上 “從vi到目的地Ak的預估成本S” 總和最小的節點，如公式（6）。這不同于最小化單車旅行時間，而是強調路網的整體吞吐量和效率，是系統最優的體現。文章在公式（6）的基礎上增加了一個懲罰項，這個懲罰項可以通過除以或乘以某個值來實現，兩者效果相同。文章希望利用遺傳編程的方法來優化這個懲罰項。 因此，設計了這樣的一個Simulator，下圖12展示了一份標準的遺傳編程程序。 在最終的優化過程中，成功地將公式中懲罰項進行了優化。

圖12 動態交通分配問題

優化完成后，就學習到最終的問題求解模型。將其與一些經典算法進行了多次對比。在不同的網絡和路網結構上，包括人流和車流的模擬，文中進行了系列實驗。 結果顯示，利用遺傳編程算法優化的調度規則，能夠使整個系統的運行更加流暢。

圖13 遺傳編程與其他方法效果

6. 未來的工作方向

使用進化計算來求解組合優化問題已經非常成熟，本文介紹了三種進化計算求解組合優化問題的實例。前兩個問題通過改進經典的進化優化算法求解，第三個問題則設計遺傳編程這類基于學習的算法求解。這些方法可以視為一個框架，即先使用群體智能算法作為求解架構，然后再設計一系列與問題相關的啟發式或局部搜索方法加入其中。 由于方法論已趨于成熟，大多數研究者的工作集中在尋找新的現實應用問題上。與強化學習結合形成的演化強化學習（ERL）也具有很大的潛力，下一章我們將進行強化學習求解方法，以及演化計算與強化學習結合方法的介紹。

參考文獻

1. What is Computational Intelligence？

2. Jia Y H , Mei Y , Zhang M .A Bilevel Ant Colony Optimization Algorithm for Capacitated Electric Vehicle Routing Problem[J].IEEE transactions on cybernetics, 2022.DOI:10.1109/TCYB.2021.3069942.

3. Jia Y H , Mei Y , Zhang M .Confidence-Based Ant Colony Optimization for Capacitated Electric Vehicle Routing Problem With Comparison of Different Encoding Schemes[J].IEEE Transactions on Evolutionary Computation, 2022, 26:1394-1408.DOI:10.1109/TEVC.2022.3144142.

4. Gao, Guanqiang, Yi Mei, Ya-Hui Jia, Will N. Browne, and Bin Xin. "Adaptive coordination ant colony optimization for multipoint dynamic aggregation." IEEE Transactions on Cybernetics 52, no. 8 (2021): 7362-7376.

5. Dai S H , Jia Y H , Chen W N ,et al.Multistage Particle Swarm Optimization for Heterogeneous Multipoint Dynamic Aggregation[J].Systems, Man, and Cybernetics: Systems, IEEE Transactions on, 2025, 55(7-Part1):4614-4628.DOI:10.1109/TSMC.2025.3553553.

6. Liao, Xiao-Cheng, Wei-Neng Chen, Ya-Hui Jia, and Wen-Jin Qiu."Towards scalable dynamic traffic assignment with streaming agents: A decentralized control approach using genetic programming."IEEE Transactions on Emerging Topics in Computational Intelligence8, no. 1 (2023): 942-955.

7. Citation: X. -C. Liao, Y. -H. Jia, X. -M. Hu and W. -N. Chen, "Uncertain Commuters Assignment Through Genetic Programming Hyper-Heuristic," in IEEE Transactions on Computational Social Systems, vol. 11, no. 2, pp. 2606-2619, April 2024.

群體智能讀書會

如果你對這些反直覺但極有用的現象感興趣——從蟻群搭橋、魚群同步、到無人機集群表演、集群機器人協作、群智優化與多智能體系統、網絡輿論建模研究等——歡迎加入「群體智能」讀書會：我們用動物—人類—機器三條線，希望把群體智能的涌現這件事講清楚、講透徹；用物理學、數理邏輯、多主體建模、計算傳播等多學科視角，去追問同一個核心：集群何以比個體更聰明？群體智能又在何時涌現？

集智俱樂部聯合北京師范大學系統科學學院韓戰鋼教授、暨南大學計算傳播研究中心趙甜芳副教授、新疆大學物理科學與技術學院玉素甫·艾比布拉副教授等來自11所高校的學者，共同發起本次，嘗試用一條普適的線索，把自然界的鳥群蟻群、人類社會的集群行為、以及人工智能時代的多智能體與群智優化，放在同一張地圖上重新理解。讀書會現已結束，歡迎所有對群體智能如何涌現、如何被理解、以及如何被設計，感興趣的朋友加入讀書會，查看回放。

詳情請見：

1.

2.

3.

5.

6.

7.

8.