【文章內(nèi)容簡(jiǎn)介】 局的最優(yōu)的位置。由于此算法為二進(jìn)制的空間中的算法因此以上的參數(shù)中的xid、pid和pgd的值都只能為0或者是1。于是根據(jù)速度的變化的公式可以得到粒子的位置的公式為：其中. 在上述公式中的sig(vid)表示的是用于限制轉(zhuǎn)換的函數(shù)，目的是為讓vid的值始終能保持在01之間的一個(gè)隨機(jī)的數(shù)。其中vid的值的選著直接關(guān)系到xid的確切的值的大小，若vid的值偏大，粒子的xid則為1的概率非常的大，反之，粒子的xid則為0的概率非常大。隨著DPSO在各個(gè)領(lǐng)域的廣泛的應(yīng)用，算法的不足之處也慢慢的不斷的涌現(xiàn)出來(lái)，比如在組合式的優(yōu)化問(wèn)題當(dāng)中表現(xiàn)的更為的突出，于是研究學(xué)家們便直接對(duì)連續(xù)的PSO離散化，將粒子的非整的位置近似的等于整數(shù)，其余的部分保持和連續(xù)的PSO中一致。雖然在算法中出現(xiàn)了近似的取整的情況，并利用這些近似的解得可行的解，但是得到的可行解在高維的規(guī)劃問(wèn)題中仍能式算法具有較高的穩(wěn)定性，并使得算法不會(huì)輕易地陷入停止的搜索狀態(tài)。因此可得離散粒子群算法（DPSO）的流程圖如圖31所示。圖31 離散粒子群算法流程圖 算法應(yīng)用由于PSO的眾多的優(yōu)點(diǎn)，目前它已經(jīng)應(yīng)用在生活、工業(yè)和科學(xué)等的各個(gè)領(lǐng)域中，并且成為了解決實(shí)際的工程與科學(xué)問(wèn)題熱門(mén)算法。同時(shí)DPSO也得到了廣泛的研究應(yīng)用，比如在組合性的優(yōu)化難題上，超大規(guī)模的集成電路上，電力系統(tǒng)上，無(wú)線的傳感器的網(wǎng)絡(luò)中和用于挖掘數(shù)據(jù)等等。通過(guò)不斷的研究和應(yīng)用，算法將會(huì)被更加廣泛的應(yīng)用，給我們的生活、工業(yè)和科學(xué)帶來(lái)更多的便利和突破。以下我們對(duì)常見(jiàn)的DPSO的應(yīng)用簡(jiǎn)單的分析與介紹： ①、典型性的組合型的優(yōu)化問(wèn)題——該問(wèn)題屬于運(yùn)籌學(xué)的一個(gè)重要的部分，其中主要包括了TSP的問(wèn)題、01背包的問(wèn)題、工作的排序問(wèn)題還有最小生成樹(shù)的問(wèn)題等。用重新總結(jié)定義的PSO來(lái)操作算式的方法得出了一種TSPDPSO的算法，于是根據(jù)這一改進(jìn)和突破，更多的學(xué)者以典型性的組合型的優(yōu)化問(wèn)題為基礎(chǔ)提出了解決TSP的問(wèn)題[2324]、01背包的問(wèn)題[2526]、工作的排序問(wèn)題還有最小生成樹(shù)的問(wèn)題等一系列的的算法。 ②、電力體統(tǒng)——在該領(lǐng)域中，需要解決的是在最低成本的情況下進(jìn)行發(fā)電擴(kuò)張的問(wèn)題，利用DPSO能很有效的處理該種有強(qiáng)約束力的組合型的優(yōu)化問(wèn)題。由于近幾年來(lái)DPSO算法得到了有力地發(fā)展，解決這一問(wèn)題的方法也隨之越來(lái)越多，比如可以使用改進(jìn)的BPS來(lái)恢復(fù)配電網(wǎng)出現(xiàn)的故障；或者可以根據(jù)配輸電網(wǎng)的擴(kuò)展規(guī)劃的問(wèn)題與電網(wǎng)的重構(gòu)問(wèn)題來(lái)設(shè)計(jì)適合的DPSO；又或者可以用DPSO處理電力系統(tǒng)中滿足發(fā)電機(jī)的約束的經(jīng)濟(jì)的調(diào)度問(wèn)題；亦或是就給出的電力市場(chǎng)中盈利區(qū)間內(nèi)的約束問(wèn)題改進(jìn)我們的DPSO；亦或者是關(guān)于熱備、停開(kāi)機(jī)等約束的機(jī)組的調(diào)度問(wèn)題與組合機(jī)組的等問(wèn)題利用DPSO可以很好地將其解決。 ③、VLSI——VLSI的設(shè)計(jì)中的布置線路、布值全局與布置圖形是整個(gè)VLSI設(shè)計(jì)的最重要的環(huán)節(jié)同時(shí)也是整個(gè)設(shè)計(jì)的核心關(guān)鍵所在。然而其中的布置線路、布值全局與布置圖形又是整個(gè)設(shè)計(jì)中最為復(fù)雜最為困難的，該問(wèn)題也以被證實(shí)為NP的難題。如若使用傳統(tǒng)的算法來(lái)優(yōu)化這個(gè)問(wèn)題要么會(huì)因?yàn)楸康挠?jì)算要么就會(huì)因?yàn)榈贸龅慕Y(jié)果是局部性的而非全局的，很顯然傳統(tǒng)的算法已經(jīng)是不能很好解決這些棘手的問(wèn)題了。于是為了解決這一抽象性的難題研究學(xué)者們想到了在集成的電路中間使用啟發(fā)式的算法來(lái)進(jìn)行優(yōu)化。但是PSO擁有更容易被實(shí)現(xiàn)的優(yōu)點(diǎn)和更厲害的全局性的優(yōu)化能力，學(xué)者們轉(zhuǎn)而開(kāi)始在VLSI的設(shè)計(jì)中使用PSO，于是辨得出了更多有效的關(guān)于解決布置線路[2728]、布值全局[2930]與布置圖形問(wèn)題的DPSO。 ④、WSN——WSN作為新的網(wǎng)絡(luò)出現(xiàn)，它不需要事先配置那些基礎(chǔ)的網(wǎng)絡(luò)的設(shè)施便能實(shí)現(xiàn)傳感器之間節(jié)點(diǎn)的自由組網(wǎng)間的通信，還擁有應(yīng)用空間的廣闊性。雖然WSN擁有很多的優(yōu)點(diǎn)，但是它同時(shí)也存在著不足之處，比如它自身帶有的電能是有限的，它的的通訊能力也存在很大的局限性，在節(jié)點(diǎn)之間的計(jì)算能力也略顯不足和它的存儲(chǔ)能力也十分的有限。以上WSN這些不足會(huì)使得無(wú)線的傳感器網(wǎng)絡(luò)之間的游泳資源相對(duì)的缺乏例如，因此要解決這些問(wèn)題就顯得有些迫不及待了。這幾年來(lái)，表示已經(jīng)有一些研究學(xué)者對(duì)WSN的各種問(wèn)題展開(kāi)了研究并且已經(jīng)抽離出了它的數(shù)學(xué)模型來(lái)進(jìn)行優(yōu)化了，同時(shí)還建立了對(duì)應(yīng)的PSO。很多的文獻(xiàn)都已分別提出了PSO在WSN領(lǐng)域中的應(yīng)用。還有一些學(xué)者將會(huì)深入的進(jìn)一步在WSN中的任務(wù)的調(diào)度中與WSN的容錯(cuò)拓?fù)涞目刂浦袘?yīng)用PSO來(lái)求解并得到最優(yōu)的結(jié)果。 ⑤、數(shù)據(jù)挖掘——它的屬性的選擇使用了BPSO得到了解決；并已有文獻(xiàn)提出在DPSO基礎(chǔ)之上的特征子集的選擇方法；還有文獻(xiàn)為傳統(tǒng)的特征的選擇的不足引入了粗超的簡(jiǎn)約的模型，同時(shí)還給了結(jié)合了PSO和領(lǐng)域粗超集的模型得出新的一種新的特征的選擇的算法。 ⑥、圖像處理——有文獻(xiàn)提出將PSO與模糊的理論相結(jié)合得出圖像匹配、識(shí)別的混合算法；有文獻(xiàn)提出使用混合的PSO與局部的搜索相結(jié)合可以對(duì)生物學(xué)中的圖像進(jìn)行標(biāo)準(zhǔn)匹配；有文獻(xiàn)利用了混沌的優(yōu)化的搜索得出以混沌搜索為基礎(chǔ)的PSO，而且使的它與圖像匹配的問(wèn)題有較好的求解效果；還有文獻(xiàn)表示可以在使用PSO的基礎(chǔ)上利用紅外的圖像的分割的技術(shù)得到另一種快速的二維的熵算法。 ⑦、VRP——雖然VRP是TSP的一種拓展的問(wèn)題，但是在利用PSO求解釋VRP時(shí)用到了全不一樣的的技術(shù)。現(xiàn)有文獻(xiàn)提出了可以通過(guò)將連續(xù)空間里的粒子進(jìn)行僅是的離散化然后再加粒子的位置映射到離散的排序空間中，這樣便能得到粒子在離散狀態(tài)下的變化情況。與其他的遺傳的算法相比較，在搜索的時(shí)候RPSO擁有更高的成功率，更高的最優(yōu)解的質(zhì)量與更優(yōu)的時(shí)間復(fù)雜度。 ⑧、Job2Shop——該問(wèn)題一直都是調(diào)度和柔韌性制造的系統(tǒng)中人們時(shí)刻關(guān)注的一個(gè)問(wèn)題之一。其用意在于利用現(xiàn)在擁有的資源來(lái)達(dá)到滿足任務(wù)需要的約束，并且使得所有的人物能盡量在規(guī)定的時(shí)間之內(nèi)較好的完成。Cagnina等研究學(xué)者曾在使用PSO處理單機(jī)的調(diào)度問(wèn)題時(shí)，邊用到了隨機(jī)的鍵來(lái)顯示粒子的具體的位置。然后再利用粒子的鍵值對(duì)作業(yè)排序，這需要先將粒子的具體位置影射到一種合法的調(diào)度上，只有這樣才能更為便捷地使用連續(xù)PSO來(lái)計(jì)算出粒子具體的速度和具體的位置。在各個(gè)領(lǐng)域還廣泛的存在很多關(guān)于PSO在Job2Shop的應(yīng)用。⑨、其他領(lǐng)域——綜合以上所敘述的關(guān)于DPSO的應(yīng)用，此外，DPSO在神經(jīng)元的網(wǎng)絡(luò)訓(xùn)練、一些有關(guān)機(jī)械的設(shè)計(jì)、通訊、化工業(yè)和經(jīng)濟(jì)生活等領(lǐng)域中都有獲得許多的研究性的成果。 本節(jié)小結(jié) 本章對(duì)DPSO算法(離散粒子群算法)進(jìn)行了深入淺出的介紹，首先大概介紹了DPSO算法的來(lái)源、形成和發(fā)展。然后展開(kāi)對(duì)DPSO算法詳細(xì)描述，對(duì)DPSO算法原理進(jìn)行深刻的剖析和認(rèn)識(shí)，最后為了能更好的對(duì)DPSO算的理解，詳細(xì)的例舉了DPSO在各個(gè)領(lǐng)域的應(yīng)用。第三章 車(chē)輛路徑問(wèn)題分析 物流配送由于互聯(lián)的發(fā)展和電子商務(wù)的迅猛的發(fā)展，因而觸發(fā)了物流產(chǎn)業(yè)的蓬勃發(fā)展，形成了物流熱效應(yīng)，于是對(duì)于物流管理技術(shù)的需求也日趨提高，傳統(tǒng)的物流管理的方法已經(jīng)不能滿足發(fā)展的要求，因此急需對(duì)這些傳統(tǒng)的方法進(jìn)行改進(jìn)，在這個(gè)改進(jìn)的環(huán)節(jié)中，物流配送中問(wèn)題顯得尤為的重要。物流中一個(gè)重要的直接與消費(fèi)者相連的環(huán)節(jié)便是物流配送。所謂的配送則是貨物從物流節(jié)點(diǎn)送達(dá)到收貨人的這一過(guò)程。配送路線的合理與否將直接影響到配送的速度、配送的成本和配送最后的效益，當(dāng)配送的過(guò)程是一個(gè)多用戶的配送時(shí)，一條合理的配送路線將會(huì)更加的重要和必要。因此我們需要采用十分科學(xué)和有效地方法來(lái)優(yōu)化配送的路線問(wèn)題。隨著物流產(chǎn)業(yè)一體化的發(fā)展，經(jīng)常會(huì)將配送中的各種問(wèn)題結(jié)合起來(lái)一起考慮，核心部分為配送車(chē)輛的集中貨物、貨物的裝配與送貨路線的優(yōu)化。于是對(duì)配送系統(tǒng)優(yōu)化的其實(shí)就是對(duì)車(chē)輛路徑的優(yōu)化。由現(xiàn)在的物流配送的流程圖（）顯然可知，配送環(huán)節(jié)成為了整個(gè)物流配送中最重要的，而存儲(chǔ)環(huán)節(jié)則相對(duì)顯得不再那么重要且趨于弱化。有數(shù)據(jù)顯示在各不相同的行業(yè)中，在物流運(yùn)輸?shù)娜^(guò)程中用于運(yùn)輸?shù)某杀举M(fèi)用竟都已超過(guò)了50%，有的甚至到了70%以上。由此可見(jiàn)，對(duì)物流配送優(yōu)化的過(guò)程最重要就是對(duì)配送時(shí)車(chē)輛調(diào)度的優(yōu)化，這其中又包括了運(yùn)貨路線的優(yōu)化，裝配貨物的優(yōu)化以及送貨到用戶的線路的優(yōu)化。 物流配送流程圖 車(chē)輛路徑問(wèn)題的概述在物流的配送的供應(yīng)中，經(jīng)常會(huì)存在一個(gè)這樣的問(wèn)題：目前有著一批顧客，當(dāng)前我們是知道它們的具體的位置的坐標(biāo)還知道關(guān)于貨物的具體的需求量，表示供應(yīng)商目前擁有者許多兩的車(chē)可以供派送使用，但是這些車(chē)輛具體的運(yùn)載能力是確定的，要求每一輛車(chē)都必須是從起點(diǎn)出發(fā)的，然后需要完成若干的客戶的點(diǎn)再回到起點(diǎn)的位置。現(xiàn)在供應(yīng)商要求使用最少的車(chē)輛和最小的行程完成整個(gè)配送的任務(wù)。上面所敘述的便是該課題所需研究的VRP，也就是配送中最為關(guān)鍵性的問(wèn)題之一，同時(shí)還被稱作為車(chē)輛計(jì)劃或貨車(chē)派送問(wèn)題等。VRP因此在一般的情況下可以被描述為：在一定問(wèn)題的約束的條件下，我們可以設(shè)計(jì)不同或者是相同的出發(fā)點(diǎn)，然后從這些出發(fā)點(diǎn)出發(fā)到多個(gè)不同的客戶目的點(diǎn)的最優(yōu)的送貨的巡回的路徑。即設(shè)計(jì)出一個(gè)消耗最小的路徑集，這些最優(yōu)的路徑集需要滿足一下幾個(gè)條件：首先是每個(gè)客戶目的點(diǎn)都只能被我們的車(chē)輛訪問(wèn)一次；其次我們配送的稱量斗必須是從出發(fā)點(diǎn)出發(fā)然后訪問(wèn)完所有的客戶目的點(diǎn)之后才能回到最初的出發(fā)點(diǎn)；最后還需要滿足具體情況下的一些具體的要求。 車(chē)輛路徑問(wèn)題的分析 VRP的研究要素關(guān)于VRP的分析如下：將服務(wù)的抽象對(duì)象具體成一位客戶，將滿足客戶需求表示為供應(yīng)點(diǎn)；相反的客戶所在地點(diǎn)則表示為需求點(diǎn)；連接供應(yīng)點(diǎn)和需求點(diǎn)并提供配送服務(wù)的車(chē)輛表示配送車(chē)輛，配送中心則為配送車(chē)輛出發(fā)的地點(diǎn)?，F(xiàn)在是在一定的約束條件下，比如配貨司機(jī)連續(xù)的行車(chē)時(shí)間、貨物的需求量、配送的時(shí)間以及載重的限制等,然后使用已有的配送車(chē)輛，并按照由不同需求確定的順序準(zhǔn)時(shí)地將物品配送至需求點(diǎn)，同時(shí)最達(dá)到滿足一個(gè)配送車(chē)輛使用最優(yōu)和車(chē)輛路徑最優(yōu)的狀態(tài),使得配送的整個(gè)過(guò)程的運(yùn)輸成本能夠達(dá)到最低。() VRP示意圖由以上的分析可得到關(guān)于VRP的核心問(wèn)題在于配送中心的選擇，其他的影響的因素有：有關(guān)相關(guān)函數(shù)的選擇；不確定的約束條件；配送的車(chē)輛、配送地點(diǎn)、配送的時(shí)間限制和道路情況等。 VRP的優(yōu)化目標(biāo)為了解決現(xiàn)實(shí)生活中對(duì)于VRP的不同的要求，歸納總結(jié)有以下幾點(diǎn)：①、最短的總行駛路徑最小化總的行駛路徑能在很大程度上避免一些不可預(yù)知的道路問(wèn)題。同時(shí)能減少車(chē)輛在途中的各種成本消耗。在物流配送中最常用的一種計(jì)量單位是噸位公里，其計(jì)算方法是：車(chē)輛所運(yùn)輸貨物的噸位量乘以行駛路徑的公里數(shù)。因此需要優(yōu)化總的行駛路徑。②、最少的配送車(chē)輛最少化配送車(chē)輛數(shù)能減小車(chē)輛的各種損耗比如油耗車(chē)輛的關(guān)卡費(fèi)。所以最少化車(chē)輛數(shù)根本上就是減少總的成本輸出。主要包括：車(chē)輛的折損費(fèi)、油耗、過(guò)路費(fèi)和人工成本等。所以再一定的目標(biāo)下，竟可能地減少車(chē)輛的使用，可以為企業(yè)節(jié)約成本。③、最少的用時(shí)在服務(wù)性的行業(yè)中，時(shí)間往往會(huì)騎著決定的作用，因此可以說(shuō)時(shí)間便是金錢(qián)。同時(shí)時(shí)間減少了，可以減少車(chē)輛的空載率，從而可以有效地降低運(yùn)輸?shù)某杀?。服?wù)一方面體現(xiàn)在人員的素質(zhì)上面，另一方面時(shí)間越少，顯示出企業(yè)的實(shí)力和管理水平越高。設(shè)計(jì)合理的行車(chē)路線可以減少車(chē)輛的空載率，從而有效的降低運(yùn)營(yíng)的成本。④、最大的客戶滿意度只有最高效的將貨物送至各戶手中才能得到更多的客戶的信賴的和肯定，從而提高企業(yè)的形象，以此來(lái)獲得更高的客戶，給企業(yè)帶來(lái)更多的利潤(rùn)的。顧客就是上帝，企業(yè)所做的一切商務(wù)活動(dòng)，都是圍繞著顧客進(jìn)行的，特別對(duì)于一些保存時(shí)間短的貨物，更是要求及時(shí)送達(dá)，以免給顧客造成一些不必要的損失，同時(shí)也損害了企業(yè)的形象。 VRP的實(shí)現(xiàn)算法 前面以提到說(shuō)明VRP屬于NP的難題，所以問(wèn)題的復(fù)雜度會(huì)隨著客戶的增加而呈現(xiàn)指數(shù)式的增長(zhǎng)。因此解決VRP這類(lèi)問(wèn)題常用的算法有啟發(fā)式，粒子群算法，還有包括本文介紹的DSPO(離散粒子群算法)，能更有效的解決VRP中存在的多目標(biāo)性。 本章小結(jié) 本章對(duì)VRP(車(chē)輛路徑問(wèn)題)進(jìn)行了深入淺出的介紹，首先大概介紹了物流配送形成和發(fā)展。然后展開(kāi)對(duì)VRP詳細(xì)描述，對(duì)VRP原理進(jìn)行深刻的剖析和認(rèn)識(shí)，同時(shí)對(duì)VRP的模型進(jìn)行了具體的描述。第四章 車(chē)輛路徑問(wèn)題的建模與實(shí)現(xiàn) 車(chē)輛路徑問(wèn)題的建模VRP因此在一般的情況下可以被描述為：在一定問(wèn)題的約束的條件下，我們可以設(shè)計(jì)不同或者是相同的出發(fā)點(diǎn)，然后從這些出發(fā)點(diǎn)出發(fā)到多個(gè)不