交通流優(yōu)化膨脹控制遺傳規(guī)劃算法

摘 要：針對(duì)遺傳規(guī)劃（GP）算法在大規(guī)模動(dòng)態(tài)交通流分配中訓(xùn)練超啟發(fā)式策略時(shí)，算法迭代次數(shù)的增加而個(gè)體平均大小不斷膨脹的問題，提出應(yīng)用不同GP控制膨脹方法來限制種群中大尺寸個(gè)體的遺傳，讓算法能夠在訓(xùn)練過程中找到更小且性能更優(yōu)的超啟發(fā)式策略?？紤]到超啟發(fā)式策略在如網(wǎng)格式、環(huán)形放射式、自由式的不同結(jié)構(gòu)路網(wǎng)上可能存在性能差異，會(huì)影響算法在訓(xùn)練過程中對(duì)個(gè)體的選擇，采用不同結(jié)構(gòu)的路網(wǎng)訓(xùn)練出超啟發(fā)式策略以進(jìn)行分析比較。訓(xùn)練后的超啟發(fā)式策略在不同規(guī)模和車流量的大城市路網(wǎng)上進(jìn)行模擬測(cè)試。結(jié)論是基于雙錦標(biāo)賽的膨脹控制方法對(duì)不同結(jié)構(gòu)路網(wǎng)的效果最優(yōu)，得到的GP算法對(duì)比現(xiàn)有調(diào)度方法能獲得路網(wǎng)整體更短的平均旅行時(shí)間，更精簡(jiǎn)有效的超啟發(fā)式策略，提高決策效率。

關(guān)鍵詞：遺傳規(guī)劃；動(dòng)態(tài)交通流優(yōu)化；控制膨脹；超啟發(fā)式策略；雙錦標(biāo)賽法

中圖分類號(hào)：TP18"" 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2025）01-024-0171-06

doi： 10.19734/j.issn.1001-3695.2024.05.0177

Traffic flow optimization bloat control genetic programming algorithm

Abstract：In addressing the issue of increasing individual average size with iterations of the GP algorithm for training hyper-heuristic strategies in dynamic traffic assignment， this paper proposed various methods for bloat control in GP to constrain the genetic inheritance of large-sized individuals within the population. This enabled the algorithm to discover smaller-sized yet higher-performing hyper-heuristic strategies during the training process. Considering the potential performance differences of hyper-heuristic strategies on various structured road networks such as grid， ring radial， and free style networks， this paper adopted different structured road networks to train hyper-heuristic strategies for analysis and comparison. The trained hyper-heuristic strategies underwent simulation testing on urban road networks of varying scales and traffic volumes. The conclusion is that the double tournament bloat control method performs the best for different structured road networks. The GP algorithm obtained from this study demonstrates its ability to achieve shorter overall average travel times for road networks compared to existing dispatch methods. Consequently， more concise and effective hyper-heuristic strategies are derived， leading to enhanced decision-making efficiency.

Key words：genetic programming（GP）; dynamic traffic flow optimization; bloat control; hyper-heuristic strategies; double tournament

0 引言

隨著經(jīng)濟(jì)水平的提高和工業(yè)的發(fā)展，許多大城市的交通道路承受能力受到挑戰(zhàn)，上下班高峰期面臨嚴(yán)重的道路擁堵問題。 交通流分配問題是智能交通領(lǐng)域一個(gè)研究焦點(diǎn)，目的在于為路網(wǎng)上每個(gè)出行需求分配合適的路線，減少擁堵，提高出行效率[1]。最早Wardrop[2]設(shè)計(jì)了兩個(gè)交通流分配原則，分別為用戶均衡原理和系統(tǒng)最優(yōu)原理。在用戶均衡原理下，每個(gè)車輛出行都選擇對(duì)自己有利的路線。在系統(tǒng)最優(yōu)原理下，車輛聽從系統(tǒng)的安排達(dá)到整體旅行成本最低。

交通流分配模型可分為靜態(tài)和動(dòng)態(tài)模型[3，4]。靜態(tài)模型提前分配路網(wǎng)上的交通量，即起點(diǎn)到終點(diǎn)的交通需求，代表有容量受限的路徑規(guī)劃[5]、靜態(tài)多路徑[6]和疏散路徑優(yōu)化[7]。動(dòng)態(tài)模型又分為基于分析的動(dòng)態(tài)模型和基于仿真的動(dòng)態(tài)模型兩大類。第一種可以細(xì)分為數(shù)學(xué)規(guī)劃模型[8]，最優(yōu)控制模型[9]與變分不等式模型[10]。在仿真模型中[11～15]，通過使用交通仿真軟件來模擬交通流在交通網(wǎng)絡(luò)中的運(yùn)行狀態(tài)。

智能優(yōu)化算法在求解NP難復(fù)雜組合優(yōu)化問題上有獨(dú)特優(yōu)勢(shì)，在交通流分配領(lǐng)域的應(yīng)用越來越受到重視。文獻(xiàn)[16]提出了下一代智能交通系統(tǒng)的模型，車輛能夠根據(jù)交通流動(dòng)態(tài)進(jìn)行自計(jì)算，作出自適應(yīng)路由決策。文獻(xiàn)[17]提出了基于隨機(jī)森林和遺傳算法的新型混合預(yù)測(cè)框架以實(shí)現(xiàn)交通流預(yù)測(cè)。文獻(xiàn)[18]使用遺傳規(guī)劃構(gòu)建超啟發(fā)式策略來解決不確定的容量受限的路徑規(guī)劃問題。文獻(xiàn)[19]使用超啟發(fā)式算法對(duì)多目標(biāo)路徑規(guī)劃問題進(jìn)行了研究。但它們大多數(shù)是解決靜態(tài)、小規(guī)模的交通流分配問題。文獻(xiàn)[20]提出了一個(gè)遺傳規(guī)劃超啟發(fā)式（genetic programming hyper-heuristic， GPHH）算法進(jìn)行交通流優(yōu)化方法，該方法通過對(duì)現(xiàn)有交通數(shù)據(jù)的學(xué)習(xí)與訓(xùn)練，生成指導(dǎo)流量分配和路徑規(guī)劃的自適應(yīng)策略，為每個(gè)出行需求提供面向全局優(yōu)化的路徑指引，并且擴(kuò)展到了更大規(guī)模的動(dòng)態(tài)交通流分配。

然而，GP傾向于不斷增加其個(gè)體的大小，這被稱為膨脹[21]。GP簡(jiǎn)化是通過從GP樹中移除多余分支來減少策略大小的一種方法。文獻(xiàn)[22]提出可以在搜索過程中簡(jiǎn)化GP樹。文獻(xiàn)[23，24]探索了使用哈希技術(shù)進(jìn)行代數(shù)樹簡(jiǎn)化，并將其應(yīng)用于回歸和分類問題。文獻(xiàn)[25，26]都提出了基于子樹的局部效應(yīng)數(shù)值樹簡(jiǎn)化方法。目前遺傳規(guī)劃方法應(yīng)用于交通流優(yōu)化問題上，存在決策樹過于復(fù)雜導(dǎo)致決策效率低的問題，因此本文將通過分析現(xiàn)有的多種膨脹控制方法，設(shè)計(jì)出更加高效控制交通流優(yōu)化決策樹規(guī)模的遺傳規(guī)劃算法。

本文在GPHH[20]算法的基礎(chǔ)上進(jìn)行改進(jìn)，研究動(dòng)態(tài)交通流分配模型的特性和現(xiàn)有交通流仿真模型的特點(diǎn)，通過現(xiàn)有的交通流仿真系統(tǒng)與現(xiàn)實(shí)路網(wǎng)相結(jié)合，設(shè)計(jì)出指導(dǎo)車輛路線規(guī)劃的策略，用于構(gòu)造基于GP的超啟發(fā)式指導(dǎo)路徑的生成。此外，還研究現(xiàn)有GP個(gè)體規(guī)模膨脹控制方法。GP中的個(gè)體往往在優(yōu)化過程中增大自身的樹狀結(jié)構(gòu)，但適應(yīng)性沒有相應(yīng)提高，反而造成個(gè)體評(píng)估用時(shí)的增加，需要加入一些策略引導(dǎo)和限制個(gè)體的膨脹。通過對(duì)四種膨脹控制方法的分析實(shí)驗(yàn)發(fā)現(xiàn)，本文GP算法在利用了基于線性參數(shù)簡(jiǎn)約壓力的膨脹控制方法下對(duì)交通流優(yōu)化問題的適應(yīng)性更佳。訓(xùn)練后的GP策略在不同規(guī)模和車流量的大城市路網(wǎng)上進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果表明，通過遺傳規(guī)劃不斷迭代訓(xùn)練出的策略對(duì)比現(xiàn)有調(diào)度方法能獲得路網(wǎng)整體的更短平均旅行時(shí)間，提高車輛的出行效率。

1 動(dòng)態(tài)交通流仿真模型

本文考慮的動(dòng)態(tài)交通流仿真模型為CBLab[27]，該模型能動(dòng)態(tài)生成路網(wǎng)中具有隨機(jī)出發(fā)地和目的地的車輛，通過遺傳規(guī)劃算法得到每輛車的最優(yōu)路線規(guī)劃決策，從而引導(dǎo)動(dòng)態(tài)生成的車輛在路網(wǎng)中移動(dòng)，獲得仿真時(shí)間內(nèi)路網(wǎng)車輛的整體平均旅行時(shí)間最短。下面將給出路網(wǎng)的定義和地圖數(shù)據(jù)來源，本文考慮不同路網(wǎng)形式和交通流仿真決策目標(biāo)的描述。

1.1 路網(wǎng)的定義和數(shù)據(jù)來源

交通流仿真模型的構(gòu)建是在現(xiàn)實(shí)路網(wǎng)的基礎(chǔ)上建立的。車輛行駛在道路上，道路的連接處形成路口。根據(jù)文獻(xiàn)[28]對(duì)路網(wǎng)的定義，路網(wǎng)可以表示為G（N，E），它是一個(gè)有向圖，其中變量N和E分別代表路口和道路的集合，每一條道路e=（u， v）∈E都有d（e）長(zhǎng)度這一個(gè)基本屬性，u代表道路e的起點(diǎn)，v代表道路e的終點(diǎn)。仿真模型的使用需要依賴于現(xiàn)實(shí)的路網(wǎng)數(shù)據(jù)，而路網(wǎng)的數(shù)據(jù)信息可以在OpenStreetMap[29]里獲取。

1.2 路網(wǎng)的分類與特點(diǎn)

道路布局網(wǎng)絡(luò)是城市的骨架，形成的道路系統(tǒng)通常可以歸納為網(wǎng)格式、環(huán)形放射式、自由式和復(fù)合式[30]四種典型形式，圖1給出了前三種例子，復(fù)合式是三種形式的復(fù)合形態(tài)。

1.3 交通流仿真的決策目標(biāo)

本文以仿真時(shí)間內(nèi)路網(wǎng)車輛的整體平均旅行時(shí)間最短為決策目標(biāo)，平均旅行時(shí)間的計(jì)算公式如下：

其中：t（e，v）表示車輛v在道路e上的行駛時(shí)間，即

te，v=toute，v－tine，v（2）

其中：tout（e，v）和tin（e，v）分別表示為車輛v進(jìn)入和離開道路e的時(shí)刻，兩個(gè)相減就是車輛在路網(wǎng)一共行駛的時(shí)間;V（e）代表在仿真時(shí)間內(nèi)經(jīng)過道路e的車輛集合。

2 交通流優(yōu)化膨脹控制GP算法

2.1 GP個(gè)體編碼

GP算法是學(xué)者Koza[31]提出的一種基于種群的進(jìn)化計(jì)算算法。該算法和遺傳算法類似，也是模擬自然世界中生物進(jìn)化的過程。不同的是，GP算法根據(jù)達(dá)爾文的“物競(jìng)天擇，適者生存”的理念自動(dòng)構(gòu)建出可以解決具體問題的計(jì)算機(jī)程序。GP個(gè)體一般的表現(xiàn)形式為樹型結(jié)構(gòu)，個(gè)體由葉子節(jié)點(diǎn)（終端節(jié)點(diǎn)）和非葉子節(jié)點(diǎn)（操作符或函數(shù)）組成。圖2為一個(gè)GP樹的例子。它的數(shù)學(xué)表達(dá)式為：F1+0.22×F2，其中F1、F2和0.22都為葉子節(jié)點(diǎn)，通常為輸入的變量或者是隨機(jī)生成的常量，“+”和“×”是非葉子節(jié)點(diǎn)，通常為函數(shù)或者是操作符。

2.2 個(gè)體評(píng)估

本文每一個(gè)超啟發(fā)式策略都可以表示為一個(gè)GP個(gè)體h?；谠摮瑔l(fā)式策略h，首先計(jì)算路網(wǎng)中所有道路的成本值，然后基于每輛車的起始和目的地，生成每輛車移動(dòng)總成本最小的路線。設(shè)每個(gè)道路e有成本C（e），路線r的總成本為它包含的所有道路e的成本總和，即

根據(jù)所有車輛的移動(dòng)路線，利用式（1）仿真計(jì)算得出整體平均旅行時(shí)間，作為該GP個(gè)體h的評(píng)價(jià)值，該評(píng)價(jià)值越小越好。

2.3 GPHH總體框架

GPHH的框架如圖3所示，首先隨機(jī)初始化GP種群，每個(gè)GP個(gè)體代表一個(gè)超啟發(fā)式策略，對(duì)每個(gè)超啟發(fā)式策略進(jìn)行評(píng)估，若沒有達(dá)到停止標(biāo)準(zhǔn)（例如最大迭代次數(shù)），則種群先通過錦標(biāo)賽選擇出候選種群，再通過遺傳操作對(duì)新種群進(jìn)行交叉、變異或復(fù)制，獲得新的個(gè)體組成新種群。算法1展示了GPHH的總體框架。

算法1 GPHH的總體框架

輸入：最大代數(shù)Gen；種群數(shù)量S。

輸出：最優(yōu)個(gè)體h。

1 根據(jù)種群數(shù)量S初始化種群pop，并且初始化初始代數(shù)Gen = 0；

2 評(píng)估pop中每一個(gè)GP個(gè)體；

3 while gen lt; Gen do

4 "使用錦標(biāo)賽選擇從pop選出S個(gè)用于遺傳的親本npop；

5 "while size（newpop） lt; S do""" //newpop為這一代進(jìn)化后的新種群

6 """從npop隨機(jī)選擇親本進(jìn)行遺傳操作（交叉、變異、復(fù)制）產(chǎn)生一個(gè)新的后代并加入到新種群newpop；

7 "end

8 "評(píng)估新種群newpop里的每個(gè)個(gè)體；

9 "newpop中的個(gè)體取代原始種群pop中的個(gè)體；

10 "gen += 1；

11 end

12 從pop中找到一個(gè)適應(yīng)度值最好的個(gè)體h

13 返回個(gè)體h

錦標(biāo)賽選擇隨機(jī)選出S個(gè)個(gè)體，適應(yīng)度值好的個(gè)體獲勝被選中。種群遺傳的交叉、變異和復(fù)制，對(duì)應(yīng)于算法1中的第6行。每次遺傳時(shí)都會(huì)有三分之一的概率從三個(gè)操作選擇其中的一個(gè)執(zhí)行。具體如下：

交叉：在種群中選擇兩個(gè)個(gè)體，分別讓兩個(gè)個(gè)體的某子樹進(jìn)行交換，把交換后第一個(gè)新個(gè)體作為后代。

變異：利用隨機(jī)初始化的方法生成一個(gè)GP樹，接著在種群中選擇一個(gè)個(gè)體，用新生成的GP樹代替該個(gè)體的某一個(gè)子樹，成為新的個(gè)體。

復(fù)制：在種群中隨機(jī)選擇一個(gè)個(gè)體作為后代。

3 GP控制膨脹方法

現(xiàn)有膨脹方法都是通過在個(gè)體評(píng)價(jià)或選擇過程中加入決策樹的一些屬性，來提高節(jié)點(diǎn)數(shù)目少的個(gè)體被選入下一代的概率。下面將介紹本文使用的幾個(gè)膨脹控制方法[18，21]。

3.1 LPPP

線性參數(shù)簡(jiǎn)約壓力（linear parametric parsimony pressure，LPPP）將個(gè)體最終的適應(yīng)度值g利用公式重新計(jì)算，變成與個(gè)體的原始適應(yīng)度f及節(jié)點(diǎn)數(shù)目s有關(guān)。最常使用的方法是將個(gè)體的大小視為適應(yīng)度的線性因子，公式如下：

g=xf+ys（4）

其中：x和y是預(yù)設(shè)的參數(shù)。

3.2 DT

雙錦標(biāo)賽（double tournament，DT）使用兩場(chǎng)錦標(biāo)賽對(duì)個(gè)體進(jìn)行選擇，第一場(chǎng)為普通的錦標(biāo)賽選擇，第二場(chǎng)為基于簡(jiǎn)約的錦標(biāo)賽選擇。第一場(chǎng)根據(jù)適應(yīng)度值進(jìn)行k場(chǎng)普通的錦標(biāo)賽，選出k個(gè)勝者參加第二場(chǎng)錦標(biāo)賽。第二場(chǎng)時(shí)，從k個(gè)晉級(jí)個(gè)體中逐次兩兩比較，節(jié)點(diǎn)數(shù)目小的個(gè)體有D/2的概率獲勝，最終得到優(yōu)勝的一個(gè)個(gè)體。DT多次執(zhí)行獲得多個(gè)優(yōu)勝個(gè)體?？芍?dāng)D取值為2時(shí)，節(jié)點(diǎn)數(shù)目小的個(gè)體必勝。

DT的特點(diǎn)是增加第二次錦標(biāo)賽使尺寸小的個(gè)體有概率獲勝而不考慮適應(yīng)度值。采用DT控制膨脹時(shí)，本文算法用DT取代算法1第4行中的錦標(biāo)賽選擇。

3.3 Tarpeian

Tarpeian方法的工作原理是使具有高于平均體型的個(gè)體的一部分缺乏競(jìng)爭(zhēng)力。在評(píng)估過程之前，具有高于平均大小的GP個(gè)體有概率W被分配非常差的適應(yīng)度值，大大降低了個(gè)體被選中進(jìn)行遺傳的機(jī)會(huì)。

Tarpeian的特點(diǎn)是被賦予差適應(yīng)度值的個(gè)體幾乎不能在錦標(biāo)賽選擇中獲勝，除非錦標(biāo)賽中其他個(gè)體都是被賦予了差適應(yīng)度值。采用Tarpeian方法控制膨脹時(shí)，在算法1中的第2、8行會(huì)對(duì)種群中節(jié)點(diǎn)數(shù)量小于平均節(jié)點(diǎn)數(shù)量的個(gè)體進(jìn)行評(píng)估，沒被評(píng)估的個(gè)體適應(yīng)度值有W的概率直接被賦予一個(gè)非常大的數(shù)（本文賦予1030）。

3.4 Niche

基于小生境（Niche）的遺傳規(guī)劃算法是文獻(xiàn)[18]提出的一種控制GP膨脹的方法，它將種群在進(jìn)行遺傳之前進(jìn)行簡(jiǎn)化，為每一個(gè)生態(tài)位保留一個(gè)GP樹。具體做法是基于適應(yīng)度值的大小對(duì)每一個(gè)GP樹進(jìn)行分類，分出不同的生態(tài)位，在每一個(gè)生態(tài)位里不同的GP樹的適應(yīng)度值相同。然后每一個(gè)生態(tài)位都只保留一個(gè)GP樹節(jié)點(diǎn)最少的個(gè)體進(jìn)行遺傳。例如圖4為兩個(gè)GP樹個(gè)體，它們的適應(yīng)度值相同而節(jié)點(diǎn)數(shù)不同，其中樹a的節(jié)點(diǎn)數(shù)多于樹b，算法則會(huì)保留GP樹b，拋棄GP樹a。如果有多個(gè)個(gè)體節(jié)點(diǎn)最少，則保留第一個(gè)被發(fā)現(xiàn)的個(gè)體，然后使用簡(jiǎn)化之后的個(gè)體進(jìn)行遺傳。為了增加種群的多樣性，新種群中一半的個(gè)體是用簡(jiǎn)化后的種群進(jìn)行遺傳的，另一半使用原種群進(jìn)行遺傳。

進(jìn)行遺傳的GP個(gè)體從不同的生態(tài)位使用錦標(biāo)賽選擇出來。但是與傳統(tǒng)錦標(biāo)賽選擇不同，這里每個(gè)個(gè)體被選擇的概率和它所在的生態(tài)位的個(gè)體數(shù)目有關(guān)，個(gè)體被選擇的概率為

其中：N為生態(tài)位總數(shù)；H表示生態(tài)位i中的個(gè)體數(shù)目。式（5）通過α的值來影響每個(gè)個(gè)體被選中的概率。當(dāng)α的取值在0～1逐漸增大時(shí)，個(gè)體被選擇的概率受到它所在的生態(tài)位中個(gè)體數(shù)目的影響也越大。

Niche的特點(diǎn)在于讓尺寸大的個(gè)體被尺寸小且適應(yīng)度值相等的個(gè)體取代，精簡(jiǎn)了種群中的基因。使用基于小生境的方法控制膨脹時(shí)，對(duì)應(yīng)于算法1中的第4～8行，本文算法先對(duì)種群進(jìn)行簡(jiǎn)化得到種群ncpop，下一代的新種群有一半的個(gè)體是使用式（5）對(duì)種群ncpop遺傳得到，而另一半個(gè)體則使用普通的錦標(biāo)賽選擇進(jìn)行遺傳。

4 實(shí)驗(yàn)

本文采用動(dòng)態(tài)交通流仿真模型CBLab[27]作為交通流仿真平臺(tái)，共使用4個(gè)城市的不同規(guī)模路網(wǎng)進(jìn)行訓(xùn)練和測(cè)試。CBLab是一種高效的微觀交通模擬器。它支持對(duì)超過十萬個(gè)十字路口和一百萬輛車輛的交通系統(tǒng)進(jìn)行實(shí)時(shí)模擬，具體包括模型的屬性定義、調(diào)度策略的優(yōu)化目標(biāo)、模型定義的具體描述、約束條件的定義和車流量生成的策略。

在訓(xùn)練階段先使用小型路網(wǎng)訓(xùn)練出超啟發(fā)式策略，再使用更大規(guī)模的路網(wǎng)對(duì)超啟發(fā)式策略進(jìn)行測(cè)試。仿真結(jié)束時(shí)的平均旅行時(shí)間越小代表測(cè)試的性能越好。

本文的測(cè)試結(jié)果將對(duì)比普通GPHH和加了控制膨脹方法之后訓(xùn)練出來的策略，以及現(xiàn)有交通流調(diào)度策略。每次訓(xùn)練進(jìn)行5次獨(dú)立運(yùn)行，訓(xùn)練時(shí)的迭代圖為平均值。每個(gè)訓(xùn)練出的最優(yōu)超啟發(fā)式策略在測(cè)試中獨(dú)立運(yùn)行5次，策略的測(cè)試結(jié)果取平均值。

4.1 實(shí)驗(yàn)數(shù)據(jù)

本文使用了中國(guó)深圳、西安、成都和重慶四個(gè)不同結(jié)構(gòu)的城市道路數(shù)據(jù)進(jìn)行模擬仿真，其中深圳和西安的路網(wǎng)為網(wǎng)格式結(jié)構(gòu)，成都的路網(wǎng)為環(huán)形放射式結(jié)構(gòu)，重慶的路網(wǎng)為自由式結(jié)構(gòu)[30]。表1給出了本文測(cè)試的路網(wǎng)數(shù)據(jù)參數(shù)。

4.2 實(shí)驗(yàn)參數(shù)設(shè)置

本文交通仿真模擬的參數(shù)和GP訓(xùn)練時(shí)的函數(shù)集合和終端集合與文獻(xiàn)[20]的保持一致。GP的初始化方法為半生長(zhǎng)法（ramped half-and-half）。表2為GP訓(xùn)練時(shí)的參數(shù)。

4.3 四種控制膨脹的方法的參數(shù)分析

實(shí)驗(yàn)中發(fā)現(xiàn)對(duì)于不同路網(wǎng)，4種控制膨脹方法的最佳參數(shù)取值近似，下面只給出采用sz50深圳路網(wǎng)進(jìn)行訓(xùn)練得到的結(jié)果。

4.3.1 LPPP

本文LPPP的實(shí)驗(yàn)中y始終設(shè)置為1，通過改變式（4）中x的大小來改變節(jié)點(diǎn)數(shù)s帶來的影響。實(shí)驗(yàn)中x的取值為[0.5，32]，x的取值每一次增加1倍。x越大，s對(duì)種群遺傳的影響越小。圖5為GPHH使用LPPP之后的迭代過程。綜合平均旅行時(shí)間和平均節(jié)點(diǎn)數(shù)來看，x=16時(shí)表現(xiàn)最好。

4.3.2 DT

在本文的DT實(shí)驗(yàn)中，k的值始終為5。本文只考慮參數(shù)D的取值，在實(shí)驗(yàn)中取值為[1.0，2.0]，每一次取值加0.2。圖6為DT下的迭代過程。綜合平均旅行時(shí)間和平均節(jié)點(diǎn)數(shù)來看，D=1.4時(shí)最優(yōu)。

4.3.3 Tarpeian

測(cè)試Tarpeian的參數(shù)W的影響，取值為[0.1，0.5]，每次實(shí)驗(yàn)增加0.1。圖7為Tarpeian下GPHH的迭代過程，綜合平均旅行時(shí)間和平均節(jié)點(diǎn)數(shù)來看，W取值為0.2時(shí)最好。

4.3.4 Niche

根據(jù)式（5），每個(gè)個(gè)體被選擇進(jìn)行遺傳的概率與α有關(guān)，實(shí)驗(yàn)測(cè)試了α的值為0、0.5、1的情況。圖8為Niche下GPHH的迭代過程。綜合平均旅行時(shí)間和平均節(jié)點(diǎn)數(shù)來看，α取值為0時(shí)最好。

4.4 控制膨脹方法在不同路網(wǎng)的結(jié)果分析

本節(jié)分析使用網(wǎng)格式（西安）、環(huán)形放射式（成都）和自由式（重慶）路網(wǎng)，并采用算法最優(yōu)參數(shù)下的GPHH算法性能，其中用于訓(xùn)練的路網(wǎng)為xa50、cd50和cq50?；诰W(wǎng)格式路網(wǎng)（xa50），圖9在最優(yōu)平均旅行時(shí)間上，LPPP、Tarpeian和Niche方法都比普通GPHH小，最好的是Niche，最優(yōu)值為316.01。在平均節(jié)點(diǎn)數(shù)上，普通GPHH表現(xiàn)最差，DT表現(xiàn)最好，每代平均為14.66。從表3可見，LPPP方法下的超啟發(fā)式策略的指導(dǎo)能力最佳，有7組數(shù)據(jù)最好，15組數(shù)據(jù)的平均值也最小，為656.47。

基于環(huán)形放射式路網(wǎng)（cd50），圖10在最優(yōu)平均旅行時(shí)間上，LPPP、DT和Tarpeian都比普通的GPHH小，最好的為DT，最優(yōu)值為438.02。在平均節(jié)點(diǎn)數(shù)上，Niche表現(xiàn)最差，而LPPP、DT和Tarpeian表現(xiàn)比普通GPHH好，其中LPPP最好，每代平均值為15.72。表4可見DT下的超啟發(fā)式策略的指導(dǎo)能力最佳，有8組數(shù)據(jù)最好，15組數(shù)據(jù)的平均值也最小，為627.64。

基于自由式路網(wǎng)（cq50），圖11在最優(yōu)平均旅行時(shí)間上，普通GPHH表現(xiàn)最差，最好為Niche，最優(yōu)值為274.82。在平均節(jié)點(diǎn)數(shù)上，Niche表現(xiàn)最差，而LPPP、DT和Tarpeian表現(xiàn)比普通GPHH好，其中LPPP最好，每代平均值為18.68。從表5可見，DT下的超啟發(fā)式策略的指導(dǎo)能力最佳，有14組數(shù)據(jù)最好，15組數(shù)據(jù)的平均值也最小，為836.95。

綜上所述，結(jié)合訓(xùn)練和測(cè)試的結(jié)果，每個(gè)路網(wǎng)下表現(xiàn)最好的控制膨脹方法不相同。在網(wǎng)格式路網(wǎng)中，表現(xiàn)最好的為L(zhǎng)PPP和DT。在環(huán)形放射式路網(wǎng)和自由式路網(wǎng)中，表現(xiàn)最好的是DT。

5 結(jié)束語

本文在基于遺傳規(guī)劃的城市交通流分配方法上研究了不同的控制膨脹方法，包括LPPP、DT、Tarpeian和Niche。通過應(yīng)用于中國(guó)深圳、西安、成都和重慶四個(gè)不同結(jié)構(gòu)的城市道路仿真，添加了膨脹控制方法的遺傳規(guī)劃算法，有助于生成規(guī)模更小且性能更優(yōu)的超啟發(fā)式策略。研究了在不同結(jié)構(gòu)的路網(wǎng)下，控制膨脹方法的優(yōu)化性能，并總結(jié)出不同類型路網(wǎng)上的最佳膨脹控制方法。在未來的工作里，將進(jìn)一步研究控制膨脹方法在GPHH上的優(yōu)化，找到一個(gè)在不同路網(wǎng)的訓(xùn)練中都能擁有最佳優(yōu)化能力的方法。

參考文獻(xiàn)：

[1]邵政熙， 陳繼鋒. 城市智能交通系統(tǒng)發(fā)展模式探析[J]. 智能城市， 2023， 9（11）： 26-29. （Shao Zhengxi， Chen Jifeng. Analysis on the development mode of urban intelligent transportation system[J]. Intelligent City， 2023， 9（11）： 26-29.）

[2]Wardrop J G. Some theoretical aspects of road traffic research[J].Proceedings of the Institution of Civil Engineers， 1952，1（3）： 325-362.

[3]Merchant D K， Nemhauser G L. A model and an algorithm for the dynamic traffic assignment problems[J]. Transportation Science， 1978， 12（3）： 183-199.

[4]Al-Sahaf H， Bi Ying， Chen Qi，et al. A survey on evolutionary machine learning[J]. Journal of the Royal Society of New Zea-land， 2019， 49（2）： 205-228.

[5]Tsang Y P， Mo D Y， Chung K T， et al.Solving capacitated and time-constrained vehicle routing problems by deep reinforcement learning-based method[C]// Proc of IEEE International Conference on Industrial Engineering and Engineering Management. Piscataway， NJ： IEEE Press， 2023： 1578-1582.

[6]Min M， Lee J， Lim S. Effective evacuation route planning algorithms by updating earliest arrival time of multiple paths[C]// Proc of the 3rd ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems. New York： ACM Press， 2014： 8-17.

[7]Yang Xiaoxia， Zhang Rui， Li Yongxing， et al.Passenger evacuation path planning in subway station under multiple fires based on multiobjective robust optimization[J]. IEEE Trans on Intelligent Transportation Systems， 2022， 23（11）： 21915-21931.

[8]王清永， 曲偉強(qiáng). 基于線性規(guī)劃的城市軌道交通運(yùn)行調(diào)度優(yōu)化算法[J]. 吉林大學(xué)學(xué)報(bào)： 工學(xué)版， 2023， 53（12）： 3446-3451. （Wang Qingyong， Qu Weiqiang. Optimization algorithm of urban rail transit operation scheduling based on linear programming[J]. Journal of Jilin University： Engineering and Technology Edition， 2023， 53（12）： 3446-3451.）

[9]Pasquale C， Sacone S， Siri S，et al. Optimal control for reducing congestion and improving safety in freeway systems[J]. IEEE Trans on Intelligent Transportation Systems， 2018， 19（11）： 3613-3625

[10]謝仕煒， 陳鎧悅， 張亞超， 等. 考慮需求彈性的電力-交通網(wǎng)絡(luò)雙層博弈模型——基于擬變分不等式[J]. 中國(guó)電機(jī)工程學(xué)報(bào)， 2024， 44（6）： 2185-2197. （Xie Shiwei， Chen Kaiyue， Zhang Yachao， et al. A two-layer game model for power-transportation coupled networks considering demand elasticity—based on quasi-variational inequalities[J]. Proceedings of the CSEE， 2024， 44（6）： 2185-2197.）

[11]毛天露， 王華， 康星辰， 等. 復(fù)雜路網(wǎng)內(nèi)大規(guī)模車輛運(yùn)動(dòng)的仿真[J]. 計(jì)算機(jī)學(xué)報(bào)， 2017，40（11）： 2466-2477. （Mao Tianlu， Wan Hua， Kang Xingchen， et al. Simulating large-scale traffic in complex networks[J]. Chinese Journal of Computers， 2017，40（11）： 2466-2477.）

[12]Müller E R， Carlson R C， Kraus W，et al. Microsimulation analysis of practical aspects of traffic control with variable speed limits[J]. IEEE Trans on Intelligent Transportation Systems， 2015， 16（1）： 512-523.

[13]M. Van Aerde amp; Assoc.， Ltd. Integration release 2.30 for windows user’s guide， volume I： fundamental model features[EB/OL]. （2005-05）. http：//tis.unical.it/download/guide/manuale_int_1.pdf.

[14]夏英， 石梔琦. 面向交通流量預(yù)測(cè)的多頭注意力時(shí)空卷積圖網(wǎng)絡(luò)模型[J]. 計(jì)算機(jī)應(yīng)用研究， 2023， 40（3）： 766-770. （Xia Ying， Shi Zhiqi. Multi-head attention spatio-temporal convolutional graph network for traffic flow prediction[J]. Application Research of Computers， 2023， 40（3）： 766-770.）

[15]翟子洋， 郝茹茹， 董世浩. 大規(guī)模智慧交通信號(hào)控制中的強(qiáng)化學(xué)習(xí)和深度強(qiáng)化學(xué)習(xí)方法綜述[J]. 計(jì)算機(jī)應(yīng)用研究， 2024， 41（6）： 1618-1627. （Zhai Ziyang， Hao Ruru， Dong Shihao. Review of reinforcement learning and deep reinforcement learning methods in large-scale intelligent traffic signal control[J]. Application Research of Computers， 2024， 41（6）： 1618-1627.）

[16]Bui K H N， Jung J J.ACO-based dynamic decision making for connected vehicles in IoT system[J]. IEEE Trans on Industrial Informatics， 2019， 15（10）： 5648-5655.

[17]Zhang Lizong， Alharbe N R， Luo Guangchun， et al.A hybrid forecasting framework based on support vector regression with a modified genetic algorithm and a random forest for traffic flow prediction[J]. Tsinghua Science and Technology， 2018， 23（4）： 479-492.

[18]Wang Shaolin， Mei Yi， Zhang Mengjie， et al.Genetic programming with niching for uncertain capacitated arc routing problem [J]. IEEE Trans on Evolutionary Computation， 2022， 26（1）： 73-87.

[19]Yao Yuan， Peng Zhe， Xiao Bin. Parallel hyper-heuristic algorithm for multi-objective route planning in a smart city [J]. IEEE Trans on Vehicular Technology， 2018， 67（11）： 10307-10318.

[20]Hu X M， Duan Y H， Li Min， et al.Hyper-heuristic algorithm for urban traffic flow optimization [C]// Proc of the 15th International Conference on Advanced Computational Intelligence. Piscataway， NJ： IEEE Press， 2023： 1-7.

[21]Luke S， Panait L. A comparison of bloat control methods for genetic programming[J].Evolutionary Computation， 2006， 14（3）： 309-344.

[22]Javed N， Gobet F， Lane P. Simplification of genetic programs： a literature survey[J]. Data Mining and Knowledge Discovery， 2022， 36（4）： 1279-1300.

[23]Wang Shaolin， Mei Yi， Zhang Mengjie.A multi-objective genetic programming algorithm with α dominance and archive for uncertain capacitated arc routing problem [J]. IEEE Trans on Evolutionary Computation， 2023， 27（6）： 1633-1647.

[24]Raymond C， Chen Qi， Xue Bing， et al. Learning symbolic model-agnostic loss functions via meta-learning [J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 2023， 45（11）： 13699-13714.

[25]Javed N， Gobet F， Hung C，et al. On-the-fly simplification of genetic programming models[C]// Proc of the 36th Annual ACM Symposium on Applied Computing." New York： ACM Press， 2021： 464-471.

[26]Song A， Chen Dunhai， Zhang Mengjie. Contribution based bloat control in genetic programming[C]// Proc of IEEE Congress on Evolutionary Computation. Piscataway， NJ： IEEE Press， 2010： 1-8.

[27]CBLab. Welcome to the CBLab documentation [EB/OL]. （2022）. https：//cblab-documentation.readthedocs.io/en/latest/index.html.

[28]Du Lun， Song Guojie， Wang Yiming， et al.Traffic events oriented dynamic traffic assignment model for expressway network： a network flow approach[J]. IEEE Intelligent Transportation Systems Magazine， 2018， 10（1）： 107-120.

[29]Lu Jiawei， Zhou Xuesong. Virtual track networks： a hierarchical modeling framework and open-source tools for simplified and efficient connected and automated mobility （CAM） system design based on general modeling network specification （GMNS）[J]. Transportation Research Part C： Emerging Technologies， 2023， 153： 104223.

[30]Gao He， Feng Shumin， Guo Caixiang. Research on selection method of urban road network structure form[C]// Proc of WASE International Conference on Information Engineering. Piscataway， NJ： IEEE Press， 2010： 360-364.

[31]Koza J R. Genetic programming： on the programming of computers by means of natural selection[M]. Cambridge， MA： MIT Press， 1992.