告別復(fù)雜計(jì)算！用進(jìn)化計(jì)算高效破解路徑優(yōu)化難題（上）

導(dǎo)語

外賣派送、物流規(guī)劃、滅火救災(zāi)等機(jī)器人調(diào)度，本質(zhì)上都離不開路徑優(yōu)化這類組合優(yōu)化問題?，F(xiàn)實(shí)場(chǎng)景中的這類問題規(guī)模大、約束多、變化快。計(jì)算智能已成為主流工具，其中進(jìn)化計(jì)算等群體智能方法擅長(zhǎng)全局搜索，強(qiáng)化學(xué)習(xí)等個(gè)體智能方法更適合從交互中學(xué)策略。在集智俱樂部《》上，賈亞暉老師做了《強(qiáng)化學(xué)習(xí)路徑優(yōu)化：群體、個(gè)體智能協(xié)同算法》的主題報(bào)告，詳細(xì)介紹了相關(guān)方法。本文我們將先介紹進(jìn)化計(jì)算，以及其在電動(dòng)車路徑優(yōu)化，多機(jī)器人任務(wù)分配以及動(dòng)態(tài)交通分問題中的應(yīng)用。梳理算法的設(shè)計(jì)思路，并探討其求解質(zhì)量與適應(yīng)性。

關(guān)鍵詞：組合優(yōu)化（Combinatorial Optimization）、車輛路徑優(yōu)化（Vehicle Routing Problems）、進(jìn)化計(jì)算（Evolutionary Computation）、蟻群算法（Ant Colony Optimization）

劉向宇丨作者

目錄

1. 從組合優(yōu)化說起

2. 從計(jì)算智能到進(jìn)化計(jì)算

3. 蟻群優(yōu)化算法求解電動(dòng)車路徑優(yōu)化問題

4. 粒子群算法求解多機(jī)器人任務(wù)分配問題

5. 遺傳編程算法求解動(dòng)態(tài)交通規(guī)劃的問題

6. 未來的工作方向

1. 從組合優(yōu)化說起

我們?cè)诟咧须A段都接觸過線性規(guī)劃問題，其目標(biāo)是在線性約束下求一個(gè)線性目標(biāo)函數(shù)的最大值或最小值，決策變量通常是連續(xù)的。線性規(guī)劃是類似的，組合優(yōu)化的目標(biāo)也是尋找最值。但其研究如何從有限個(gè)離散對(duì)象的組合中尋找滿足條件的最優(yōu)方案，決策變量是離散的，典型的問題包括旅行商問題、背包問題與車間調(diào)度問題。

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

1. 從計(jì)算智能到進(jìn)化計(jì)算

啟發(fā)式方法屬于計(jì)算智能（Computational Intelligence, CI）領(lǐng)域，IEEE計(jì)算智能官網(wǎng)對(duì)其介紹如下。計(jì)算智能是指受生物學(xué)和語言學(xué)啟發(fā)的計(jì)算范式的理論、設(shè)計(jì)、應(yīng)用和開發(fā)[1]。計(jì)算智能包含三個(gè)方面如圖1。第一是進(jìn)化計(jì)算（Evolutionary Computation，EC），第二類是神經(jīng)網(wǎng)絡(luò)（Neural Networks，NNs），第三類是模糊系統(tǒng)（Fuzzy system，F(xiàn)S）。

圖1 計(jì)算智能領(lǐng)域知識(shí)框架

（1）進(jìn)化計(jì)算方向：以生物進(jìn)化，種群行為為靈感來源的進(jìn)化計(jì)算通過生成、評(píng)估和修改可能解的群體來解決優(yōu)化問題。該領(lǐng)域涵蓋遺傳算法、進(jìn)化規(guī)劃、進(jìn)化策略、遺傳編程、群體智能、差分進(jìn)化、可進(jìn)化硬件、多目標(biāo)優(yōu)化等多種方法。

（2）神經(jīng)網(wǎng)絡(luò)方向：以人腦為靈感來源的人工神經(jīng)網(wǎng)絡(luò)是大規(guī)模并行分布式網(wǎng)絡(luò)，具備從案例中學(xué)習(xí)并進(jìn)行概括的能力。該研究領(lǐng)域涵蓋前饋神經(jīng)網(wǎng)絡(luò)、遞歸神經(jīng)網(wǎng)絡(luò)、自組織神經(jīng)網(wǎng)絡(luò)、深度學(xué)習(xí)、卷積神經(jīng)網(wǎng)絡(luò)等多種類型。

（3）模糊系統(tǒng)方向：以人類語言為靈感來源的模糊系統(tǒng)能夠?qū)φZ言的不精確性進(jìn)行建模，并基于傳統(tǒng)邏輯的泛化來解決不確定性問題，使我們能夠進(jìn)行近似推理。該研究領(lǐng)域涵蓋模糊集合與系統(tǒng)、模糊聚類與分類、模糊控制器、語言概括、模糊神經(jīng)網(wǎng)絡(luò)、二型模糊集合與系統(tǒng)等多種類型。

本文我們主要探討進(jìn)化計(jì)算方法，這種方法可根據(jù)遺傳算法分為進(jìn)化優(yōu)化與進(jìn)化學(xué)習(xí)算法。優(yōu)化是指直接針對(duì)當(dāng)前問題構(gòu)建一個(gè)優(yōu)化算法逐步求解。學(xué)習(xí)是指從多個(gè)問題實(shí)例中學(xué)習(xí)一個(gè)模型，然后利用模型去求解當(dāng)前的問題。

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

圖2 進(jìn)化計(jì)算概念框架

3. 蟻群優(yōu)化算法求解電動(dòng)車路徑優(yōu)化問題

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

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

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

ηi,j：邊i→j的啟發(fā)式吸引力。

β：控制啟發(fā)式信息影響力的參數(shù)。β越大，算法更聚焦局部最優(yōu)；β越小，算法更依賴全局經(jīng)驗(yàn)。

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

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

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

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

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

圖3 電動(dòng)車車輛路徑優(yōu)化問題示意圖

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

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

圖4 BACO算法結(jié)構(gòu)

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

圖5 移除啟發(fā)執(zhí)行示意圖

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

圖6 ACO算法結(jié)果

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

4. 粒子群算法求解多機(jī)器人任務(wù)分配問題

多機(jī)器人任務(wù)分配（Multiple Robot Task Allocation，MRTA）問題是為多種任務(wù)調(diào)配足夠數(shù)量的機(jī)器人。問題的目標(biāo)是為每個(gè)機(jī)器人找到執(zhí)行時(shí)間（完成時(shí)間）最短的最優(yōu)計(jì)劃。約束有機(jī)器人隨時(shí)間變化的約束、機(jī)器人能力約束以及機(jī)器人間的協(xié)作方式約束等。

圖7 多機(jī)器人救火場(chǎng)景任務(wù)分配問題

如圖7所示，在救災(zāi)場(chǎng)景中，如果某個(gè)地方發(fā)生火災(zāi)，單個(gè)機(jī)器人可能無法撲滅大火，這時(shí)就需要一群機(jī)器人共同協(xié)作來完成救援任務(wù)。 在任務(wù)執(zhí)行中，參與的機(jī)器人越多，任務(wù)完成的速度也會(huì)越快。我們的目標(biāo)是調(diào)度一群機(jī)器人，完成分散在地圖上的動(dòng)態(tài)任務(wù)。這里的“動(dòng)態(tài)”指的是任務(wù)量會(huì)不斷增加。

PSO算法適用于上述問題。PSO算法的提出者是一位心理學(xué)家。他觀察到鳥類覓食時(shí)的行為，發(fā)現(xiàn)鳥類在尋找食物的過程中，會(huì)記住曾經(jīng)找到食物的地方，并繼續(xù)探索其他區(qū)域。此外，鳥群之間會(huì)共享信息。這些觀察促使算法的設(shè)計(jì)者制定了簡(jiǎn)單的更新公式。

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

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

然而，PSO算法本身只是一個(gè)框架，并不局限于連續(xù)優(yōu)化。文章[6]考慮每個(gè)解X都是一個(gè)集合。只需定義實(shí)數(shù)與集合的乘法、集合之間的減法和加法，便可實(shí)現(xiàn)組合優(yōu)化的求解。 在多機(jī)器人任務(wù)分配的問題上，文章進(jìn)一步增加了難度，引入了任務(wù)點(diǎn)之間的依賴關(guān)系。這使得問題變得更加復(fù)雜。

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

圖9 MSPSO算法加減法規(guī)則

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

圖10 MSPSO算法優(yōu)化效果

5. 遺傳編程算法求解動(dòng)態(tài)交通規(guī)劃的問題

前面提到的兩個(gè)優(yōu)化算法可以視為元啟發(fā)算法的一種，而現(xiàn)在要提到的遺傳編程則是一種超啟發(fā)式方法。遺傳編程通常不用于求解信息完全已知的靜態(tài)問題，而是更適用于動(dòng)態(tài)或不確定的環(huán)境，其目標(biāo)是生成一種能夠?qū)崟r(shí)調(diào)整的策略，而非一條固定路徑。例如，快遞員在取件時(shí)若遇到客戶提交信息與實(shí)際不符，原定路線可能不再最優(yōu)。此時(shí)需要的是能即時(shí)響應(yīng)變化的決策策略，而遺傳編程正是為了自動(dòng)生成這類適應(yīng)性策略而設(shè)計(jì)的算法。

圖11 任務(wù)樹形結(jié)構(gòu)

如遺傳編程算法結(jié)構(gòu)如圖11所示樹形結(jié)構(gòu)來展示。下方是一個(gè)數(shù)學(xué)表達(dá)式，它代表了遺傳編程中一個(gè)解的調(diào)度規(guī)則。 在這個(gè)表達(dá)式中，X和Y可以視為某個(gè)任務(wù)的特定屬性。最終計(jì)算得出的值，可以理解為優(yōu)先級(jí)。 輸出值通常是路由調(diào)度問題中候選者的優(yōu)先級(jí)。值越大越大優(yōu)先級(jí)越高，反之亦然。因此，這個(gè)過程就變成了一個(gè)學(xué)習(xí)任務(wù)。 我們可以使用一些生成的訓(xùn)練實(shí)例，輸入到遺傳編程算法中，從而生成這樣的模型即調(diào)度規(guī)則。最終，我們可以把這個(gè)調(diào)度規(guī)則應(yīng)用到其他相似的動(dòng)態(tài)環(huán)境。

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

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

圖12 動(dòng)態(tài)交通分配問題

優(yōu)化完成后，就學(xué)習(xí)到最終的問題求解模型。將其與一些經(jīng)典算法進(jìn)行了多次對(duì)比。在不同的網(wǎng)絡(luò)和路網(wǎng)結(jié)構(gòu)上，包括人流和車流的模擬，文中進(jìn)行了系列實(shí)驗(yàn)。 結(jié)果顯示，利用遺傳編程算法優(yōu)化的調(diào)度規(guī)則，能夠使整個(gè)系統(tǒng)的運(yùn)行更加流暢。

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

6. 未來的工作方向

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

參考文獻(xiàn)

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.

群體智能讀書會(huì)

如果你對(duì)這些反直覺但極有用的現(xiàn)象感興趣——從蟻群搭橋、魚群同步、到無人機(jī)集群表演、集群機(jī)器人協(xié)作、群智優(yōu)化與多智能體系統(tǒng)、網(wǎng)絡(luò)輿論建模研究等——?dú)g迎加入「群體智能」讀書會(huì)：我們用動(dòng)物—人類—機(jī)器三條線，希望把群體智能的涌現(xiàn)這件事講清楚、講透徹；用物理學(xué)、數(shù)理邏輯、多主體建模、計(jì)算傳播等多學(xué)科視角，去追問同一個(gè)核心：集群何以比個(gè)體更聰明？群體智能又在何時(shí)涌現(xiàn)？

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

詳情請(qǐng)見：

1.

2.

3.

5.

6.

7.

8.