【文章內(nèi)容簡介】 遺傳算法用種群來表示一組解，通過對當(dāng)前群體進行選擇、交叉和變異等一系列遺傳操作，產(chǎn)生新一代的種群，并逐漸使種群進化到包含近似最優(yōu)解的狀態(tài)[6]。良好的收斂性；較高的魯棒性；不受函數(shù)約束條件的限制。搜索空間范圍大，搜索時間較長；易早熟收斂；對初始種群要求高，初始種群的取值常影響解的素質(zhì)和算法效率。蟻群算法運動方向根據(jù)釋放的信息素物質(zhì)的濃度來引導(dǎo)，濃度越高，選擇該路徑的幾率越大。當(dāng)一批螞蟻經(jīng)過同一路徑時，后面的螞蟻選擇該路徑的可能性也就越大。引入正反饋并行機制，加快了進化過程；優(yōu)良的分布式機制、易于與其他方法結(jié)合；不易陷入局部最優(yōu)；較強的魯棒性。每次解算法過程的計算量較大，搜索耗時很大，易于出現(xiàn)遲緩現(xiàn)象；算法收斂性能影響初始取值。粒子群優(yōu)化算法目標(biāo)解視為維搜索空間中的一個粒子，所有粒子都有一個由被目標(biāo)函數(shù)決定的適應(yīng)值，得出自己目前為止發(fā)現(xiàn)的最好位置，利用個體和全局最好位置更新位置和速度[7]。具有很強的魯棒性和并行分布性；優(yōu)化過程無需依賴具體問題的數(shù)學(xué)特性；執(zhí)行時間短。局部搜索能力差；搜索精度不高；缺少算法設(shè)計的指導(dǎo)原則。 本章小結(jié)本章主要介紹了動態(tài)交通流中的一些相關(guān)概念、相關(guān)符號和動態(tài)交通路網(wǎng)中的約束條件，對幾種常用的優(yōu)化算法進行詳細論述，并比較了這幾種算法各自的優(yōu)缺點。第3章 粒子群優(yōu)化算法 粒子群優(yōu)化算法簡介粒子群算法（Particle Swarm Optimization，簡稱 PSO）在1995年由Kennedy和Eberhart 首先提出，該算法模擬鳥群飛行尋找食物的行為，通過鳥與鳥之間的合作使群體達到最優(yōu)目的。PSO開始是為了形象化地模擬鳥類群體覓食時不可預(yù)測的飛行行為，通過對鳥類社會行為的研究，發(fā)現(xiàn)在群體中共享社會信息能在演化中獲得生存優(yōu)勢，并以此作為開發(fā) PSO 算法的根據(jù)。通過匹配附近粒子的速度，排除不需要用到的變量，并加入對多維搜索以及根據(jù)距離的加速的考慮，初步形成了PSO的原始版本[8]。后來，Shi等人通過增加慣性權(quán)重，使PSO能夠更好地用于調(diào)整探索（exploration）和開發(fā)（exploitation）的性能，形成了現(xiàn)在的標(biāo)準(zhǔn)版本。 算法的基本原理在特定的模型中，每個粒子都象征著求解空間中的一個可行解，粒子本身都有一個由被優(yōu)化的目標(biāo)函數(shù)所設(shè)定的適應(yīng)值，以及在解空間中當(dāng)前所處的位置和速度，位置和速度的值決定了它飛翔時跨越的距離和方向?；谌后w的行為繁亂多變，在搜索的過程中粒子應(yīng)遵守以下三個原則：（1）飛離最近的粒子，避免產(chǎn)生相撞；（2）飛向最終目標(biāo)；（3）飛向群體的中心。接下來具體的表述一下粒子群算法的原理，首先假設(shè)在一個維的目標(biāo)搜索領(lǐng)域中，有個粒子形成一個粒子群，其中：第個粒子表示為一個維的向量，也就是粒子的當(dāng)前位置： 第個粒子的速度也是一個維的向量，每個向量也即是粒子的的當(dāng)前飛行速度： 第個粒子搜索到的最優(yōu)位置，也即是粒子所發(fā)現(xiàn)過的具有最好適應(yīng)值的位置： 整個種群到一定程度時尋優(yōu)到的最優(yōu)位置為全局最好： 關(guān)于最小化求解，目標(biāo)函數(shù)值越小，相應(yīng)的適應(yīng)值越優(yōu)。PSO算法同其它進化算法相似，是一種迭代的優(yōu)化算法，速度和位置的更新公式為： （31） （32）式中 、——第、次迭代、——加速因子 、——[0，1]內(nèi)的隨機數(shù)——個體極值——全局極值在尋優(yōu)中粒子的和都要接受最大值[，]和最小值[，]的約束。在式（31）中，當(dāng) 時，取= ；當(dāng)時，取= 。當(dāng) 時，取= ；當(dāng)時，取= .如公式（31）所示，每個粒子的運動行為由三部分決定：第一部分體現(xiàn)粒子當(dāng)前速度的影響，結(jié)合粒子目前的情況，明確了局部搜索能力與全局搜索能力的均衡比重；第二部分為“認(rèn)知”部分，即與個體極值的距離（），表示粒子本身的權(quán)衡；第三部分為“社會”部分，即與全局極值的距離（），表示粒子間的信息傳播與合作。對PSO 算法的這些心理學(xué)假設(shè)的爭論是沒有意義的。在追尋一致的認(rèn)知過程中，個體通常牢記它們自身的最優(yōu)位置，并且兼顧到其它個體的最優(yōu)位置。當(dāng)個體發(fā)現(xiàn)其它個體的最優(yōu)位置較好時，它將選擇靈活性地調(diào)整。PSO粒子移動搜索的原理圖可用圖31描述。群體的影響微粒自我記憶的影響當(dāng)前速度的影響圖31粒子移動搜索原理圖 算法流程 PSO的算法步驟如下，流程圖如圖32所示。 Step1：初始化粒子群（設(shè)定群體規(guī)模為），初始化隨機位置和速度； Step2：由適應(yīng)度函數(shù)計算每個粒子的適應(yīng)度； Step3：對每個粒子，將其目前的適應(yīng)值與本身發(fā)現(xiàn)過的最好位置作對比，如果更好，則將其替換為當(dāng)前的最好位置； Step4：對每個粒子，將其目前的適應(yīng)值與全局所發(fā)現(xiàn)的最好位置作對比，如果較好，則重新更新； Step5：根據(jù)公式（31）和（32）更新粒子的速度和位置； Step6：滿足結(jié)束條件(誤差足夠小或達到最大迭代次數(shù))則退出，否則返回Step2。輸出結(jié)果是否滿足結(jié)束條件是否根據(jù)公式(32)對粒子的位置進行更新根據(jù)公式(31)對粒子的速度進行更新求出整個群體的全局最優(yōu)值求出每個粒子的個體最優(yōu)計算每個粒子的適應(yīng)值初始化每個粒子的速度和位置開 始圖32 PSO算法流程圖 算法的特點（1）整個算法更新過程中，慣性權(quán)重、加速因子和和最大速度一起保持對全局和局部尋優(yōu)能力的均衡；（2）在粒子群搜索初始階段，其解值隨迭代具有更明顯的隨機性，使其產(chǎn)生了下一代解群的較強的隨機性，以及后面全部解的“信息”的共享性，改善各個解的“自我素質(zhì)”等；（3）個體具有“記憶”和“學(xué)習(xí)”的品質(zhì)，它們通過“自我”學(xué)習(xí)和向“他人”學(xué)習(xí)，使其后來的解有針對性的從“先輩”那里接收到更多的信息，從而能快速找到最優(yōu)解；（4）在算法中，信息單向傳播，只能將信息傳給其余的粒子，使整個尋優(yōu)在更新過程中跟隨當(dāng)前解。 參數(shù)的意義PSO參數(shù)有：種群數(shù)量，慣性權(quán)重，加速因子及和最大速度，最大代數(shù)。 （1）最大速度決定了粒子在解空間的搜索精度，同時也決定了粒子在一個更新中能夠移動的最大距離，在每一維中，它們的速度都會被限定在中，如果某一維粒子更新后的速度超過了（或），那么這一速度就被設(shè)置為（或）。如果太大，粒子可能會錯過最好解；如果太小，粒子可能掉進局部最優(yōu)區(qū)域而不能進行全局搜索。 （2）慣性權(quán)重因子 慣性權(quán)重因子使粒子保持運動慣性，使其有能力搜索新的區(qū)域。取值大有利于搜索一個新的空間，而取值小則有利于粒子精確搜索當(dāng)前區(qū)域中的最優(yōu)值。于是在開始進行全局搜索時需要取較大的值，擴張搜索范圍（exploration），使搜索迅速收斂于某一范圍，然后取較小的值進行局部精確開發(fā)（exploitation）來獲得更加精確的解。 （3）學(xué)習(xí)因子和學(xué)習(xí)因子表示粒子的動作來自于自己經(jīng)驗的部分和其它粒子經(jīng)驗的部分。學(xué)習(xí)因子和代表將每個粒子推向和位置的學(xué)習(xí)權(quán)重，即表征粒子本身的思考的權(quán)重，則表示粒子間的信息傳播與相互協(xié)作的權(quán)重。低的取值能夠讓粒子在被拉回之前在目標(biāo)范圍外來回搜索，而高的值則容易使粒子失控地沖向或超出目標(biāo)區(qū)域，一般情況下取 。 算法的優(yōu)缺點主要的優(yōu)缺點如下：優(yōu)點：（1）PSO 算法實現(xiàn)方式簡單，主要是隨粒子的位置和速度來尋優(yōu)，收斂速度較快； （2）PSO 算法擁有高效的局部和全局尋優(yōu)的平衡能力，可以及時避開早熟； （3）PSO 算法存在本質(zhì)的并行性，利用批量處理粒子群中多個粒子的方式，可以同時對尋優(yōu)空間中的某個區(qū)域進行搜索； （4）PSO 算法利用實數(shù)編碼，可以在問題域上直接進行解值，需設(shè)定的變量較少，在工程上應(yīng)用方便。 缺點： （1）PSO 算法易取得局部最優(yōu)解； （2）PSO 算法搜索精度不高； （3）PSO 算法高效的信息共享機制可能致使粒子搜索時過度聚集在某一區(qū)域，使粒子都飛向某個全局極值點，一般不用于多模態(tài)模型的優(yōu)化研究； 粒子群優(yōu)化算法的改進粒子群算法作為一種仿生進化算法，采用建立在群體的全局搜索策略和簡單的位移—速度模式，避免了類似其他復(fù)雜的遺傳操作。由于它具有極快的計算速度以及算法具有的易實現(xiàn)性，吸引了社會上大量學(xué)者的密切關(guān)注和探究。 算法的研究方向根據(jù)粒子群算法研究的相關(guān)文獻以及進化算法領(lǐng)域的發(fā)展趨勢，目前粒子群算法主要有以下幾個研究方向[9]。（1）PSO的設(shè)計及改進研究兼顧到不同問題的特殊性，應(yīng)注重加強對高效混合PSO的開發(fā)，包括PSO與神經(jīng)網(wǎng)絡(luò)、PID邏輯、模擬退火、生物智能、禁忌搜索以及混沌等方法相結(jié)合，充分吸收其他算法的優(yōu)點，改進目前PSO存在的弊端。此外，由于PSO對參數(shù)具有很強的依賴性，選取參數(shù)時需要慎重考慮。（2）PSO的理論分析迄今為止，PSO的求解方法還不統(tǒng)一，存在許多待解決和未涉及到的問題，PSO的理論分析一直是PSO研究的難點。如何有效地利用數(shù)學(xué)模型對PSO的運動軌跡、收斂速度、參數(shù)選取、魯棒性及計算復(fù)雜性進行分析應(yīng)成為目前的研究熱點，包括PSO在多目標(biāo)、離散以及動態(tài)等環(huán)境下的相關(guān)理論研究。（3）PSO與其他進化算法的比較研究當(dāng)前存在有三種經(jīng)典的進化算法，遺傳算法，進化規(guī)劃和進化策略，這些算法有共通的特點，各自具有優(yōu)劣勢。粒子群算法與其他進化算法的共同之處在于都是基于“群體”、基于適應(yīng)度來進行隨機搜索，但都無法確保一定能尋到最優(yōu)解。其他進化算法在進化的過程中只是保留和采用位置的信息，但粒子群算法可以同時保留及提取速度和位置信息，適應(yīng)值低的粒子在尋優(yōu)中仍能生存，并且可能搜索到空間中的任何一個領(lǐng)域。相比較之下可以突出PSO的優(yōu)劣。 算法的改進（1）增加慣性權(quán)重和收斂因子為了能夠平衡全局搜索和局部搜索性能，得到質(zhì)量更好的種群后代，選取合適的算法參數(shù)是關(guān)鍵。Shi[10]等人提出了帶有慣性權(quán)重的PSO算法，通過在速度更新公式中加入慣性權(quán)重，極大地提高了算法的收斂性能。在文獻[10]中還提出慣性權(quán)重線性遞減權(quán)值（Linearly Decreasing Weight，簡稱LDW）策略，隨著對解空間的迭代，線性減小，算法在初期進行全局搜索而后期能夠進行局部精確的搜索。Eberhart[11]等人提出了一種帶收斂因子的PSO算法，與加入慣性權(quán)重的PSO算法相比較，帶收斂因子的PSO算法在運算中具有更好的收斂速度。（2）對粒子的特征量重新賦值粒子的特征量主要由粒子的位置和速度體現(xiàn)，為了減少PSO出現(xiàn)早熟收斂和停滯現(xiàn)象，需要對粒子的特征值重新賦值，使算法可持續(xù)更新并維持群體的多樣性。XiaoFeng Xie[12]提出了自適應(yīng)PSO算法，通過采用一種新粒子替換不活潑粒子使群體保持多樣性，在PSO中引入自然進化過程中的群體消亡現(xiàn)象，該算法在更新粒子位置和速度后，按預(yù)先設(shè)置的消亡間隔重新初始化每個粒子的狀態(tài)，實驗表明該方法能改善PSO算法的性能，但由于本身的限制，該算法會影響消亡間隔的設(shè)置。（3）混合方法將PSO與其他優(yōu)化算法混合，綜合利用其他優(yōu)化算法的優(yōu)勢來彌補PSO本身容易陷入局部最優(yōu)和搜索精度低的不足。Katare[13]等人提出基于PSO和LevenbergMarquardt的混合優(yōu)化算法，結(jié)合PSO的全局搜索能力與LevenbergMarquardt的局部改良能力，極大提高了PSO的搜索精度；后來外國研究者在算法中引入量子行為，放棄用牛頓力學(xué)而是利用量子測不準(zhǔn)原理來確定粒子的行為[14]，等等。 算法的拓?fù)浣Y(jié)構(gòu)研究粒子群拓?fù)浣Y(jié)構(gòu)分為全局版本（）和局部版本（）模型。在全局版本模型中，粒子同時追尋本身的歷史最優(yōu)值（）和群體全局最優(yōu)值（）在搜索領(lǐng)域中更新速度和位置。如果對粒子速度更新公式稍作變化，讓所有粒子更新速度時依據(jù)下面兩個要素進行：A、粒子本身歷史最優(yōu)值；B、粒子鄰域內(nèi)粒子的最優(yōu)值。其他不變，這個算法就變成局部版本的粒子群算法。在局部版本中，粒子的鄰域隨著迭代次數(shù)的增加而逐漸變大。實驗表明，全局版本的粒子群算法具有收斂速度快的優(yōu)點，但運算的同時易于落入