【正文】 19 得其廣泛應(yīng)用在化工、電力、機(jī)械設(shè)計(jì)、交通以及通信等領(lǐng)域。 第一種方法是 對(duì)粒子編號(hào)，然后根據(jù) 編號(hào)來取粒子的 鄰域 ，一般取法主要有： a、環(huán)形取法； b、隨機(jī)環(huán)形取法； c、輪形取法； d、隨機(jī)輪形取法。在全局版本模型中，粒子同時(shí) 追尋 本身 的歷史最優(yōu)值 （ pbest ） 和群體全局最優(yōu)值 （ gbest ） 在搜索領(lǐng)域中更新速度和位置。 Shi[10]等人提出了帶有慣性權(quán)重 w 的 PSO 算法，通過在速度更新公式中加入慣性權(quán)重 w ，極大地提高了算法的收斂性能。此外，由于 PSO 對(duì)參數(shù)具有很強(qiáng)的依賴性，選取參數(shù) 時(shí) 需要 慎重 考慮 。 （ 3） 學(xué)習(xí)因子 1c 和 2c 學(xué)習(xí)因子 表示粒子的動(dòng)作來 自 于自己經(jīng)驗(yàn)的部分和其它粒子經(jīng)驗(yàn)的部分 。 Step1：初始化 粒子 群 （ 設(shè)定 群體規(guī)模為 m ） ，初始化 隨機(jī)位 置和速度； Step2： 由適應(yīng)度函數(shù) 計(jì)算 每個(gè)粒子的適應(yīng)度； ()idxt 群體的影響 ( 1)idxt? 微粒自我記憶的影響 ()gdpt ()idpt 當(dāng)前速度的影響 ( 1)idvt? ()idvt 五邑大學(xué)本科畢業(yè)設(shè)計(jì) 14 Step3：對(duì)每個(gè)粒子，將其 目前 的 適應(yīng)值與 本 身 發(fā)現(xiàn) 過的最好位置 pbest 作 對(duì)比 ，如果更好 ，則將其 替換為 當(dāng)前的最好位置 pbest ； Step4：對(duì)每個(gè)粒子，將其 目前 的 適應(yīng)值與全局所 發(fā)現(xiàn) 的最好位置 gbest 作 對(duì)比 ，如果較好，則重新 更新 gbest ； Step5：根據(jù)公式 （ 31） 和 （ 32） 更新粒子的速度和位置； Step6： 滿足結(jié)束條件 (誤差足夠 小 或 達(dá)到最大迭代 次數(shù) )則 退出，否則返回 Step2。 PSO算法同其它進(jìn)化算法相似 ，是 一種迭代的優(yōu)化算法，速度和位置的更新公式 為 ： k + 1 k 1 k 2 k* 1 * ( b e st ) * 2 * ( g b e st )v v c ra n d p x c ra n d x? ? ? ? ? （ 31） 五邑大學(xué)本科畢業(yè)設(shè)計(jì) 13 k 1 1kkx x v???? （ 32） 式中 k 、 1k? —— 第 k 、 1k? 次迭代 1c 、 2c —— 加速因子 1rand 、 2rand —— [0， 1]內(nèi) 的隨機(jī)數(shù) pbest —— 個(gè)體極值 gbest —— 全局極值 在 尋優(yōu) 中粒子的 iv 和 ix 都要 接受 最大值 [ maxv ， maxx ]和最小值 [ maxv? ， maxx? ]的約束 。 本 章小結(jié) 本章主要介紹了動(dòng)態(tài)交通流中的一些相關(guān)概念、相關(guān)符號(hào)和動(dòng)態(tài)交通路網(wǎng)中的約束條件，對(duì)幾種常用的優(yōu)化算法進(jìn)行詳細(xì)論述，并比較了這幾種算法各自的優(yōu)缺點(diǎn)。 搜索空間 范圍 大 ， 搜索時(shí)間 較長(zhǎng) ； 易早熟收斂 ； 對(duì)初始種群 要求高 ， 初始種群的 取值 常影響解的 素 質(zhì) 和算法效率。啟發(fā)式算法屬于優(yōu)化算法中的一種，該算法在狀態(tài)空間中 對(duì)每個(gè)搜索到的位置都會(huì)進(jìn)行評(píng)價(jià)，排除掉不合理的位置，得到最好的位置后 再對(duì)這個(gè) 位置進(jìn)行 精細(xì)的 搜索直到滿足 目標(biāo) 要求 。 路段容量限制 路段 容量 限制是指單位時(shí)間內(nèi)通過一條路徑或道路某一 截面 的最大車輛數(shù)，其單位通常為輛 /小時(shí)。在實(shí)際的交通網(wǎng)絡(luò)中，每一個(gè)路段上的車流量并非一成不變的，隨著時(shí)間的變化，在每個(gè)節(jié)點(diǎn)上都有可能產(chǎn)生 不同數(shù)量的新 車流量 [4]。動(dòng)態(tài)交通流分配模型能再現(xiàn)實(shí) 際交通狀態(tài)，在計(jì)算機(jī)上模擬網(wǎng)絡(luò)中車輛隨著實(shí)時(shí)車流量的變化而改變其行車路線的情況，而這種交通狀態(tài)是 出行者對(duì)路徑選擇的結(jié)果 [2]。 五邑大學(xué)本科畢業(yè)設(shè)計(jì) 7 第 2章 動(dòng)態(tài)交通 分配模型 動(dòng)態(tài)交通 分配 動(dòng)態(tài)分配是交通流理論發(fā)展、不斷完善的趨勢(shì)，是交通控制與管理實(shí)際應(yīng)用之需 。 （ 3） 可以對(duì)交通 流進(jìn)行最優(yōu)控制 。 （ 1） 可以對(duì)交通擁擠特性進(jìn)行全面分析。預(yù)測(cè)性模型指的是出行者根據(jù)某一段時(shí)間的交通狀況預(yù)先決定自己的最 優(yōu) 行駛路徑，這條最 優(yōu) 路徑是根據(jù)以往經(jīng)驗(yàn)中在該路段行駛花費(fèi)的實(shí)際成本得到的。 智能交通 信息 管理平臺(tái)是集成信息化、智能化的新型交通管理工具 ，可 對(duì)交通運(yùn)輸系統(tǒng)中的 信息資源 進(jìn)行整合 ， 并 具有 按一定標(biāo)準(zhǔn) 完成多源異構(gòu) 的大量 數(shù)據(jù)的接收 、存儲(chǔ)、處理、 發(fā)布等功能， 實(shí)現(xiàn) 管理部門間信息 傳輸 ， 為交通運(yùn)輸組織 在交通 控制方案 的制定、改進(jìn) 方面 提供數(shù)據(jù) 支撐 。 在公交 汽車 管理 方面 ， 可以 以 班車 的 運(yùn)行 狀態(tài) 為 依據(jù) 合理安排 首末班車時(shí)間、發(fā)車間隔 等計(jì)劃，提高工作效率和 候車者滿意度 。十二五計(jì)劃中將重點(diǎn)發(fā)展新一代城市智能交通控制系統(tǒng)，綜合交通運(yùn)輸和服務(wù)的 優(yōu)化技術(shù) ， 構(gòu)建智能評(píng)價(jià) 交通系統(tǒng) 的 平臺(tái) 標(biāo)準(zhǔn) 。目前美國(guó)已經(jīng)在 ITS的整體組織及規(guī)劃、開發(fā)、運(yùn)作實(shí)驗(yàn)等方面進(jìn)行的大量的 投資和 部署，其電子收費(fèi) 系統(tǒng) 、五邑大學(xué)本科畢業(yè)設(shè)計(jì) 2 軌道自動(dòng)駕駛 等 ITS 技術(shù)處于 世界 領(lǐng)先地位。 ITS 是社會(huì) 公認(rèn)的解決城市和高速公路交通擁 堵 和提高 駕駛員 行車安全的 主要措施 ，也是交通 管理 領(lǐng)域 學(xué)者們 研究的前沿問題。五邑大學(xué)本科畢業(yè)設(shè)計(jì) I 粒子群算法在動(dòng)態(tài)交通分配問題的應(yīng)用 摘 要 動(dòng)態(tài)交通分配在交通控制與誘導(dǎo)中起重要作用，因其能充分 考慮 交通路網(wǎng)中的 復(fù)雜性、 時(shí)變性 和 隨機(jī)性 等典型交通流特性 ，比靜態(tài)交通分配更有優(yōu) 勢(shì) 。 作為道路路網(wǎng)規(guī)劃的最后一個(gè)環(huán)節(jié)，交通分配具有不可替代的地位，它是方案設(shè)計(jì)的理論基礎(chǔ)，也是方案實(shí)施的最終目的。 自上個(gè)世紀(jì)八十年代 以來 ，西歐國(guó)家 在 “ 歐洲高效安全交通系統(tǒng)計(jì)劃（ PROMETHEUS） ” 和 “ 保障車輛安全的歐洲道路基礎(chǔ)設(shè)施計(jì)劃（ DRIVE） ” 兩大計(jì)劃 推進(jìn)下 進(jìn)行 交通 智能 化 項(xiàng)目 的 探討 、 研 發(fā)與應(yīng)用。 智能交通系統(tǒng)的組成 目前 社會(huì) 上 認(rèn)可 的 智能交通系統(tǒng) 主要 有 7 個(gè) 構(gòu)成 部分 。 （ 4） 先進(jìn)的車輛控制系統(tǒng) （ AVCS） AVCS 主要 通過 研發(fā)先進(jìn)的控制 技術(shù) 使 駕駛員駕駛 汽車 時(shí)能夠 在道路上 安全、 通暢 地行駛 。 圖 12 為城市智能交通控制與管理系統(tǒng)的結(jié)構(gòu)。反映型模型是指出行者根據(jù)實(shí)時(shí)的交通狀況來選擇 費(fèi)用 最低的路徑。 交通堵塞在不同的時(shí)間區(qū)間內(nèi)發(fā)生在不同的區(qū)域 ，交通擁擠在一定 范圍內(nèi) 限制 了城市交通流的分布 擴(kuò)張 。 動(dòng)態(tài)交通分配 集合 了交通需求隨時(shí)間變化的 路網(wǎng) 特性，可以檢測(cè) 某一時(shí)刻 的瞬時(shí) 的交通流分布 情況 ，因此， 它能及時(shí)預(yù)測(cè)交通堵塞 事件的發(fā)生 ，從而為信號(hào)燈的配時(shí)提供 精確的信息 ，讓車輛通暢 運(yùn)行 。在交通需求管理中，不僅要制定科學(xué)、合理的交通規(guī)劃設(shè)計(jì)服務(wù)，還要制定完善的交 通管理控制方案服務(wù) ，將其應(yīng)用到交通控制和誘導(dǎo)中 。從 Merchant 和 Memhauster[3]為動(dòng)態(tài)交通網(wǎng)絡(luò)模型相關(guān)問題所作出的具有開創(chuàng)性的研究工作以來，動(dòng)態(tài)交通流分配模型及其理論已經(jīng)歷了 30 余年的發(fā)展歷程。 假設(shè)車輛在任意時(shí)刻 t 路段 a 上的流量為： s 0( ) ( ) ( ) , , ,t ssa a aX t U t V t d t a s t??? ? ???? （ 28） 或 ? ?s 0( ) ( ) ( ) , ,ta a aX t U t V t d t a t? ? ?? （ 29） 那么，流量守恒約束條件為： ( ) ( ) ( ) , ,llls s saaa A b BV t g t U t l s s??? ? ? ??? （ 210） 式 中 iA —— 節(jié)點(diǎn) i 為目的地的所有路段的集合； iB —— 以節(jié)點(diǎn) i 為出發(fā)點(diǎn)的所有路段的集合； saV（ t） —— 車輛在 t 時(shí)刻進(jìn)入路段 a 并以節(jié)點(diǎn) s 作為目的地的交通量； ()saUt—— 車輛在 t 時(shí)刻駛?cè)肼范?a 并以節(jié)點(diǎn) s 作為目的地的車輛流入率。路段的 容量限制 是 反映 該道路 車輛 承載能力的一個(gè) 重要的物理量，體現(xiàn)了道路的一種 特性 。由于其具有 誤差小、 計(jì)算時(shí)間短 、 程序簡(jiǎn)單易于修改 等優(yōu)點(diǎn)，常用于研究動(dòng)態(tài)交通分配模型 。 蟻群算法 運(yùn)動(dòng)方向 根據(jù)釋放的信息素物質(zhì)的濃度 來 引導(dǎo) ， 濃度越高，選擇該路徑的幾率越大。 五邑大學(xué)本科畢業(yè)設(shè)計(jì) 12 第 3章 粒子群優(yōu)化算法 粒子群優(yōu)化算法簡(jiǎn)介 粒子群算法 （ Particle Swarm Optimization， 簡(jiǎn)稱 PSO） 在 1995 年 由 Kennedy和 Eberhart 首先 提出 ， 該算法模擬鳥 群飛行 尋找食物 的行為 ， 通過鳥與鳥之間的 合作 使群體達(dá)到最優(yōu)目的。在式（ 31）中， 當(dāng) 1kv? maxv 時(shí)，取 1kv? = maxv ； 當(dāng) 1kv? maxv 時(shí)，取 1kv? = maxv? 。 圖 32 PSO算法流程圖 算法的特點(diǎn) （ 1） 整個(gè) 算法 更新 過程中，慣性權(quán)重 w 、加速因子 1c 和 2c 和最大速度 maxv 一起 保持對(duì)全局和局部 尋優(yōu) 能力的 均衡 ； 輸出結(jié) 果 是否滿足結(jié)束條件 是 否 根據(jù) 公式 (32)對(duì)粒子的位置進(jìn)行 更新 根據(jù) 公式 (31)對(duì)粒子的速度 進(jìn)行 更新 求出整個(gè)群體的全局最優(yōu)值 求 出每個(gè)粒子 的個(gè)體最優(yōu) 計(jì)算每個(gè)粒子的適應(yīng)值 初始化每個(gè)粒子的速度和位置 開 始 五邑大學(xué)本科畢業(yè)設(shè)計(jì) 15 （ 2） 在粒子群 搜索 初始階段 ，其 解值 隨迭代具有更 明顯 的隨機(jī)性， 使 其產(chǎn)生了下一代解群的較 強(qiáng) 的隨機(jī)性，以及后面 全部 解的“信息”的共享性 ， 改善 各個(gè)解的“自我素質(zhì)”等 ； （ 3） 個(gè)體 具有“記憶” 和“學(xué)習(xí)”的 品質(zhì) ，它們通過“自我”學(xué)習(xí)和向“他人”學(xué)習(xí)，使其后來的解有針對(duì)性的從“先輩”那里接收到更多的信息，從而能快速 找到最優(yōu)解 ； （ 4） 在算法中， 信息單向 傳播 ， 只能 gbest 將信息 傳 給 其余 的粒子，使 整個(gè) 尋優(yōu) 在 更新過程 中 跟隨當(dāng)前解。 學(xué)習(xí) 因子 1c和 2c 代表將每個(gè)粒子推向 pbest 和 gbest 位置的學(xué)習(xí)權(quán)重，即 1c 表征粒子本身的思考的權(quán)重， 2c 則 表示粒子間的信息 傳播 與相互 協(xié)作 的權(quán)重。 （ 2） PSO 的理論分析 迄今 為止， PSO 的 求解 方法還不 統(tǒng)一，存在許多待解決 和未涉及到的問題 ， PSO 的理論分析 一直 是 PSO 研究的難點(diǎn) 。在文獻(xiàn) [10]中還提出 慣性權(quán)重 線性遞減權(quán)值（ Linearly Decreasing Weight， 簡(jiǎn)稱 LDW）策略， 隨著對(duì)解空間的 迭代 ， w 線性減小，算法在初期進(jìn)行全局搜索而后期 能夠 進(jìn)行局部精確的搜索。如果對(duì) 粒子速度更新公式 稍作 變化 ，讓 所有 粒子 更新速度時(shí)依據(jù) 下面 兩個(gè) 要 素 進(jìn)行 ： A、 粒子 本身 歷史最優(yōu)值 pbest ； B、 粒子鄰域內(nèi)粒子的最優(yōu)值 pnbest 。下圖 3圖 3圖 3圖五邑大學(xué)本科畢業(yè)設(shè)計(jì) 18 36 為四種取法的表示。 在粒子群研究的領(lǐng)域內(nèi)，無論是理論還是應(yīng)用效果都需要再進(jìn)一步的探討。 m a x m i nm a xm a x w tT ??? （ 43） 式中 maxw 、 minw —— 慣性權(quán)重的最大取值和最小取值 ； t —— 當(dāng)前迭代 數(shù) ； maxT —— 最大迭代 數(shù)。在本文中采用路段上行駛時(shí)間最少為阻抗最小原則 ，模型 采用高自友 [17]于 20xx 年提出 的 經(jīng)典模型做算例 ，并用 MATLAB 軟件 來 進(jìn)行仿真測(cè)試。五邑大學(xué)本科畢業(yè)設(shè)計(jì) 20 第 4章 粒子群算法在動(dòng)態(tài)交通分配問題的應(yīng)用 帶慣性權(quán)重因子的改進(jìn)算法 本文取用全局版本的粒子群算法。 在 上一 種方法中，可以通過 編號(hào)來 獲得 粒子的鄰域，但是 這種方法可能存在粒子 與粒子間 的 當(dāng)前 位置并不相