【正文】 多，比如可以使用改進的 BPS 來恢復(fù)配電網(wǎng)出現(xiàn)的故障；或者可以根據(jù)配輸電網(wǎng)的擴展規(guī)劃的問題與電網(wǎng)的重構(gòu)問題來設(shè)計適合的 DPSO；又或者可以用DPSO 處理電力系統(tǒng)中滿足發(fā)電機的約束的經(jīng)濟的調(diào)度問題；亦或是就給出的電力市場中盈利區(qū)間內(nèi)的約束問題改進我們的 DPSO；亦或者是關(guān)于熱備、停開機等約束的機組的調(diào)度問題與組合機組的等問題利用 DPSO 可以很好地將其解決。用重新總結(jié)定義的 PSO 來操作算式的方法得出了一種 TSPDPSO 的算法，于是根據(jù)這一改進和突破，更多的學(xué)者以典型性的組合型的優(yōu)化問題為基礎(chǔ)提出了解決 TSP 的問題 [2324]、 01 背包的問題 [2526]、工作的排序問題還有最小生成樹的問題等一系列的的算法。通過不斷的研究和應(yīng)用，算法將會被更加廣泛的應(yīng)用，給我們的生活、工業(yè)和科學(xué)帶來更多的便利和突破。 開 始初 始 化 粒 子 的 位 置和 速 度尋 找 個 體 最 優(yōu) 和 全局判 斷 是 否 滿 足 的約 束 條 件利 用 公 式 更 新 粒 子的 位 置 和 速 度尋 找 當(dāng) 前 個 體 最 優(yōu)和 全 局 最 優(yōu)計 算 粒 子 的 群 體 相似 度判 斷 群 體 相 似 度是 否 大 于 給 定 的伐 值啟 用 排 斥 算 子判 斷 是 否 滿 足 結(jié)束 條 件結(jié) 束是是否否否 圖 31 離散粒子群算法流程圖 算法應(yīng) 用 由于 PSO 的眾多的優(yōu)點，目前它已經(jīng)應(yīng)用在生活、工業(yè)和科學(xué)等的各個領(lǐng)域中，并且成為了解決實際的工程與科學(xué)問題熱門算法。雖然在算法中出現(xiàn)了近似的取整的情況，并利用這些近 第 12 頁 共 40 頁 似的解得可行的解，但是得到的可行解在高維的規(guī)劃問題中仍能式算法具有較高的穩(wěn)定性，并使得算法不會輕易地陷入停止的搜索狀態(tài)。其中 vid 的值的選著直接關(guān)系到 xid 的確切的值的大小，若 vid 的值偏大，粒子的 xid 則為 1 的概率非常的大，反之，粒子的 xid 則為 0 的概率非常大。由于此算法為二進制的空間中的算法因此以上的參數(shù)中的 xid、 pid 和 pgd 的值都只能為 0 或者是 1。 算法原理 二進制 PSO 利用粒子的速度作為粒子的位置的變化的概率，這個觀點由Kennedy和 Eberhart 兩位博士首次提出的，專門用于解決 0~1 類型的規(guī)劃的問題，在這個算法中，僅僅就是使用二進制的量來代表每個粒子并且利用二進制空間來代替超立方的空 間，然后用二進制的量之間的轉(zhuǎn)化來使得粒子在超空間中移動。例如旅行商問題 （ TSP） ，在以離散空間為基礎(chǔ)的前提下 DSPO 通過利 第 11 頁 共 40 頁 用 位運算，這樣雖然可能會增加一些計算的時間，但是這樣便不會產(chǎn)生多余的搜索的問題，這樣還能自然地描述離散的問題，并能和其他的演化算法緊密地結(jié)合起來，如此使得其有更好的發(fā)展前景。 但是現(xiàn)實生活中的問題不全是都能在連續(xù)型的模型上建立起來并得到解決，因此 BPSO 在一些離散化的情況中將不再是那么適用。 根據(jù)現(xiàn)實生活中遇到的各類型的問題而言，以 上的兩種方法可以分別應(yīng)用于在生活中的不同領(lǐng)域。利用離散空間上的位操作的獨特載體，以取代傳統(tǒng)的矢量的計算，從信息的流動的機制的角度上來計算，依然保存著 PSO 的具體的信息交換伴隨流動的機制。 在 DPSO 的問題中逐漸出現(xiàn)兩條主要的技術(shù)方法：一種方法是依據(jù)以往經(jīng)典的 連續(xù)的 PSO 算法，然后再將這個連續(xù)運動的粒子映射到離散空間中并適當(dāng)修改算法使之適應(yīng)能夠解決離散問題。在關(guān)注 DPSO 這個過程中，人們對 DPSO這個算法的了解也愈深刻，尤其是在我們中國有一些研究者對 DPSO 的研究特別重視。最后為了能更好的對 PSO 算的理解，畫出了 PSO 算法直觀的流程圖，使得算法便于理解和后面的實現(xiàn)。 開 始初 始 化 粒 子群計 算 粒 子 適應(yīng) 度 值求 解 p B e a t 和g B e s t是 否 滿 足輸 出 求 解g B e s t 值結(jié) 束是否 圖 21 粒子群算流程圖 本節(jié)小結(jié) 本章對 PSO 算法 (粒子群優(yōu)化算法 )進行了深入淺出的介紹，首先大概介紹了PSO 算法的來源、形成和發(fā)展。 然后再通過上述的迭代方法得出得出最優(yōu)的解再利用這個最優(yōu)的解來得出新的關(guān)于速度與位置的值。由以上的優(yōu)點可以顯然地得出目前解決全局的優(yōu)化的問題 PSO 是很有效果的。④、在算法應(yīng)用的整個過程中由于群體的規(guī)模相比較而言稍微小一點，并且較少次數(shù)的利用到評估的函數(shù)，由此一來收斂速度便快了。 通過上述對 PSO（粒子群算法）原理的分析和概述因而可以總結(jié)出 PS 的幾大顯著的優(yōu)點：①、由于 PSO 算法的來源貼 近人的慣性思維所以 PSO 是較容易便能進行描述的；②、因為 PSO 原理和內(nèi)容是簡潔易懂的所以將其實現(xiàn)的過程也是較為輕松的。 最 后 一 部 分 為)(*()*1 ii XN b estra ndc ?，而這一部分可以表示為粒子能在整個空間中的領(lǐng)域中以前遇到到過的那些最優(yōu)的解中再次進行搜索的可能方向，這個有可以類比于人類可以通過從他人的所學(xué)會的知識中而獲得一些經(jīng)驗。由之前提到的更新速度的公式可將其大致地分為三個部分，首先一部分是關(guān)于 Vi—— 一種粒子會按照原來的方向和形同的速度完成搜索過程的趨勢，而這可以轉(zhuǎn)換為用人的認(rèn)知習(xí)慣來解釋這一原理。算法設(shè)置這樣的一個 Vmax 的值的目的在于這樣能確保粒子在群體中能達到的全局的搜索能力，在算法的整個運算的過程中若將 Vmax 的值設(shè)置的越小就會越增加粒子在算法中的局部的搜索的能力。 第 8 頁 共 40 頁 Rand()函數(shù)能產(chǎn)生 0~1 的隨機數(shù)。這兩個常數(shù)不能太小也不能太大，如果它們的值太小則會使得粒子們遠離我們的目標(biāo)區(qū)域，但是如果太大便會使得粒子 突然就向目標(biāo)的區(qū)域飛過去或者甚至可能使得粒子飛出我們的目標(biāo)區(qū)域。最后粒子根據(jù)以下的兩個計算公式得到最后具體的關(guān)于粒子的速度與位置。在這個迭代的過程產(chǎn)生的個體極值用 )P,...,P,(PP bdb2b1bi ? 來表示。分別使用 )v,...,v,(vV idi2i11 ? 和 )x,...,x,(xX idi2i11 ? 來描述群體中的 i粒子在解空間中的速度與位置。以上便是 PSO（粒子群算法） 的原理內(nèi)容。 首先 PSO 算法 （粒子群算法）會對隨機的一群粒子進行初始化，再利用獲得的最優(yōu) 解進行迭代在找到解的空間的一過程中追蹤兩個所謂的極值 —— 個別的極端、全局的極值以此來不斷地更新自己的位置和速度等。由此便會產(chǎn)生一個最優(yōu)粒子，然后群體中的粒子們便會依據(jù)此最優(yōu)粒子開始在解空間里搜索最優(yōu)。 算法原理 第 7 頁 共 40 頁 在 PSO 算法（粒子群優(yōu)化算法）當(dāng)中，存在的每種需要優(yōu)化的問題都對應(yīng)著在搜索空間里存在的鳥，而在 DSPO（離散粒子群算法）中這些優(yōu)化問題被稱作粒子。 PSO 算法 （粒子群優(yōu)化算法） 作為新的智能的優(yōu)化技術(shù)，它是來自于人工的生命與演化計算的理論知識：對群體中的每一個都進行一次初始化，初始化后的粒子都將作為一個可能存在的解或預(yù)備方案，然后不斷地更新搜索迭代出空間里最優(yōu)的解空間。粒子群優(yōu)化算法作為啟發(fā)式的全局搜索的算法與此同時也是一個新的建立在群體基礎(chǔ)上的智能算法，只需要用過粒子群中的粒子在相互之間進行相互地競爭和相互的合作，這樣便能達到優(yōu)化的效果，并較快速地在一未知或特定的空間中尋找到最優(yōu)的一點從而達到空間全局最優(yōu)。在此 之后引進了 Shi 這個概念到慣性權(quán)重的算法中來平衡開發(fā)和挖掘的能力，才形成目前標(biāo)準(zhǔn)的版本。自然界中各種各類的生物體基本上都會有著一定的群體的行為，因此為人類生命的研究的領(lǐng)域的討論 ——群體生物行為所產(chǎn)生的生物學(xué)的特性提供了立體的直觀的模型，同時為在計算機上建立和模擬群體概念提供了模型。 第五章，對本論文的工作做了回顧和總結(jié)，歸納出了本論文的主要工作、取得的成果以及不足，并對本研究課題做了分析以及對今后的進一步研究工作做了展望。 第三章，介紹物流配送，由物流配送引入車輛路徑問題，深入地剖析車輛路徑問題。 首先，在本論文的第一章，對本課題的研究背景、目前國內(nèi)外的研究動態(tài)進行簡要地概述。 ④ 、最后在實際的物流配送任務(wù)中，對于城市的道路的同行狀況的了解和掌握，因此我們可以考慮在 VRP 的框架下更進一步的研究。 ③ 、還有用于求解動態(tài)的 VRP 的仿真環(huán)境仍然需要開發(fā)研究。因此必須對不確定的信息進行預(yù)先的處理，于是每次使用的智能算法都需要根據(jù)具體的問題進行變化。于是對 VRP 的求解研究快速的高效的智能算法是一個很有價值的研究方向。主要的問題有如下： ① 、 首先 VRP 的問題是一個 NP 的難題。同時為了解決 VRP 的各種確定性問題用了各類型的不同算法，如遺傳算法 [20]、混合算法 [21]等。到目前為止，可 第 4 頁 共 40 頁 以在國內(nèi)的各大期刊網(wǎng)站上都能搜索到有關(guān) VRP 的研究成果近千篇，同時著也說明了 VRP 這個問題的研究價值和重要性，同時還說明了國內(nèi)學(xué)者對不同類型的 VRP 的研究做出了不可磨滅的貢獻?？偨Y(jié)得出 VRP 擴展問題及關(guān)系圖如圖 所示。 將不同的擴寬元素再與標(biāo)準(zhǔn)的 VRP 相結(jié)合 ,然后可以構(gòu)造出不同的車輛路徑問題 ,比如： 有能力約束的 VRP(CVR)、有時間窗的約束的 VRP(VRPTW)、帶取送貨的 VRP(VRPPD)、周期性的 VRP(PVRP)、分散配送 VRP(SDVRI)和 帶回程載貨的 VRP(VRPB)等 [316]。通過調(diào)整標(biāo)準(zhǔn)的 VRP 的不同的建設(shè)條件，從而來擴寬 VRP 的研究。 按任務(wù) 的性質(zhì)，有確定信息的和不確定的；需求的動態(tài)性和靜態(tài)性等等。同時 VRP 也可以如此分類： 在研究目標(biāo)方面，可以最小化總的運輸成本；可以將顧客的等待時間最小化；可以最小化行駛的路程和將服務(wù)的效率最大化等。 標(biāo)準(zhǔn)的車輛路徑問題其實是指帶裝載限制的車輛路徑問題 (Capacitatied VRP， CVRP)，其他的各類型的問題都是從此問題延伸展開。從提出的改進版的模擬的退火算法到動態(tài)的蟻群算法再到改進的粒子群算法等算法來解決車輛路徑問題。 國內(nèi)外研究現(xiàn)狀 國外的研究現(xiàn)狀 1959 年的時候有學(xué)者 Dantzig 與 Ramser 二人第一次提出了車輛問題(Vechicle Routing Problem， VRP)[33],當(dāng)時提出該問題的背景是運輸汽油，然后給出了出數(shù)學(xué)模型和求解的具體方法。 應(yīng)用于車輛路徑問題中離散粒子群算法同時也克服了其他算法的不足和缺點，離散粒子群算法編碼比較簡單克服遺傳算法實現(xiàn)的復(fù)雜性，并且該算法具有一般的特性，適用于絕大多數(shù)的目標(biāo)優(yōu)化問題。然而影響運輸配送的成本的最主要的問題便是車輛路徑問題 (VRP)，以現(xiàn)代的物流產(chǎn)業(yè)的發(fā)展的重要性可見的車輛路徑問題的顯著，因此成功地合理地規(guī)劃處理車輛路徑問題會帶來可喜可贊的經(jīng)濟的效益和科學(xué) 第 2 頁 共 40 頁 的效益。簡而言之，深入對車輛路徑問題的研究，很具有工程和科學(xué)的應(yīng)用價值。 該問題自 1959 年被首先提出，到現(xiàn)在目前已經(jīng)有將近五十多年的的研究歷史，它已經(jīng)是組合優(yōu)化問題領(lǐng)域和運籌學(xué)研究的熱點和重點。 對于物流產(chǎn)業(yè)而言，物流配送是其中重要的環(huán)節(jié)，然而在這個環(huán)節(jié)中車輛路徑的選擇則會起著關(guān)鍵性的作用。從而在經(jīng)濟全球化的趨勢下，我國的經(jīng)濟得到了迅猛的發(fā)展，在高水平經(jīng)濟的平臺上科學(xué)技術(shù)同時也得到了進步。 Logistics Problem。 Discrete Particle Swarm Optimization。 關(guān)鍵詞： 粒子群算法、離散粒子群算法、車輛路徑問題、物流配送、路徑優(yōu)化問題、免疫算法 ii Discrete Particle Swarm Optimization for Vehicle Routing Problem Abstract: In this highspeed economic and social development, science and technology sectors of innovation requires increasingly strong, while producing increasingly broad impact on people39。粒子依據(jù)自身和群體經(jīng)驗進行優(yōu)化更新，具有記憶和學(xué)習(xí)能力，克服其他算法的眾多參數(shù)的問題。應(yīng)用離散粒子群算法 (DPSO)[22]這種群體智能算法能更好更快地解決這些多樣化的問題，該算法以快速收斂性而獲取最佳是通過 模擬鳥群覓食得到的。 物流配送中亟待解決的問題是怎樣得到一條費用最小的車輛路徑并將貨物配送給每個客戶，即車輛路徑問題 (VRP)[33]。 計算機科學(xué)與技術(shù)學(xué)院 畢業(yè)設(shè)計 (論文 ) 論文題目 離散粒子群算法在車輛路徑問題中的應(yīng)用 指導(dǎo)教師 職 稱 講師 學(xué)生姓名 學(xué) 號 專 業(yè) 班 級 系 主 任 院 長 起止時間 目錄 摘要 .................................................. i Abstract.