【文章內(nèi)容簡介】 于 PSO 算法的來源貼 近人的慣性思維所以 PSO 是較容易便能進(jìn)行描述的；②、因?yàn)?PSO 原理和內(nèi)容是簡潔易懂的所以將其實(shí)現(xiàn)的過程也是較為輕松的。③、在利用 PSO 來計(jì)算時(shí)用到的參數(shù)的數(shù)量也是較少的，并且這些參數(shù)都為常數(shù)，所以基本上不需要費(fèi)太多的心思在調(diào)整參數(shù)上。④、在算法應(yīng)用的整個(gè)過程中由于群體的規(guī)模相比較而言稍微小一點(diǎn)，并且較少次數(shù)的利用到評(píng)估的函數(shù)，由此一來收斂速度便快了。⑤、在該過程中由于用到的計(jì)算較少因此對(duì)設(shè)備的 CPU 與內(nèi)存的要求也不那么嚴(yán)格。由以上的優(yōu)點(diǎn)可以顯然地得出目前解決全局的優(yōu)化的問題 PSO 是很有效果的。 算法流程 算法的流程：首先，需要對(duì)群體中的所有的粒子進(jìn)行一個(gè)隨機(jī)的初始化，初 第 9 頁 共 40 頁 始化他們的位置和他們的速度，這樣便能使群體均勻地分布在解空間當(dāng)中。 然后再通過上述的迭代方法得出得出最優(yōu)的解再利用這個(gè)最優(yōu)的解來得出新的關(guān)于速度與位置的值。最后粒子根據(jù)以下的兩個(gè)計(jì)算公式得到最后具體的關(guān)于粒子的速度與位置（如圖 21 所示）。 開 始初 始 化 粒 子群計(jì) 算 粒 子 適應(yīng) 度 值求 解 p B e a t 和g B e s t是 否 滿 足輸 出 求 解g B e s t 值結(jié) 束是否 圖 21 粒子群算流程圖 本節(jié)小結(jié) 本章對(duì) PSO 算法 (粒子群優(yōu)化算法 )進(jìn)行了深入淺出的介紹，首先大概介紹了PSO 算法的來源、形成和發(fā)展。然后展開對(duì) PSO 算法詳細(xì)描述，對(duì) PSO 算法原理進(jìn)行深刻的剖析和認(rèn)識(shí)，同時(shí)對(duì) PSO 算法應(yīng)用的優(yōu)點(diǎn)進(jìn)行了具體的闡述。最后為了能更好的對(duì) PSO 算的理解，畫出了 PSO 算法直觀的流程圖，使得算法便于理解和后面的實(shí)現(xiàn)。 第 10 頁 共 40 頁 離散粒子群算法 算法引入 PSO 算法開始只是用于處理一些連續(xù)性的問題，然而隨著近些年的發(fā)展，此算法被越來越廣泛地使用在處理和完善離散問題中 ,從而逐漸地頻繁地出現(xiàn)在人們的視線中并開始得到關(guān)注，因此在離散問題中衍生出來的 PSO 算法被稱為離散粒子群算法 (discrete PSO, DPSO)[22]。在關(guān)注 DPSO 這個(gè)過程中，人們對(duì) DPSO這個(gè)算法的了解也愈深刻，尤其是在我們中國有一些研究者對(duì) DPSO 的研究特別重視。該課題先描述了 PSO 算法的原理和內(nèi)容，然后在基于離散化的情況對(duì) PSO算法進(jìn)行進(jìn)一步的說明和闡述并基于離散映射不同的方法 PSO 算法，將 DPSO算法的離散空間進(jìn)行劃分，再將衍生出來的 DPSO 算法應(yīng)用到 VRP 問題中，最后就該課題現(xiàn)狀的客觀分析以及討論發(fā)展趨勢(shì)和在該領(lǐng)域內(nèi)的前景展望。 在 DPSO 的問題中逐漸出現(xiàn)兩條主要的技術(shù)方法：一種方法是依據(jù)以往經(jīng)典的 連續(xù)的 PSO 算法，然后再將這個(gè)連續(xù)運(yùn)動(dòng)的粒子映射到離散空間中并適當(dāng)修改算法使之適應(yīng)能夠解決離散問題。另一種方法是離散優(yōu)化問題，用 PSO 為基礎(chǔ)來更新各種新信息，用經(jīng)典的算法的思想和框架重新定義 DPSO 中的粒子的表達(dá)和求解方式。利用離散空間上的位操作的獨(dú)特載體，以取代傳統(tǒng)的矢量的計(jì)算，從信息的流動(dòng)的機(jī)制的角度上來計(jì)算，依然保存著 PSO 的具體的信息交換伴隨流動(dòng)的機(jī)制。而這兩種方式的差別在于：第一種是在以連續(xù)空間的基礎(chǔ)上的DPSO，而第二種則是在以離散空間為基礎(chǔ)的 DPSO。 根據(jù)現(xiàn)實(shí)生活中遇到的各類型的問題而言，以 上的兩種方法可以分別應(yīng)用于在生活中的不同領(lǐng)域。就連續(xù)空間上研究的 DPSO 形成了二進(jìn)制的 PSO 主要被應(yīng)用在規(guī)劃類型的問題中，除此之外還建立了專屬于改算法的新的計(jì)算的模型還包括了些可能會(huì)被常用到的關(guān)于離散化的研究方法策略。 但是現(xiàn)實(shí)生活中的問題不全是都能在連續(xù)型的模型上建立起來并得到解決，因此 BPSO 在一些離散化的情況中將不再是那么適用。雖然現(xiàn)在急于離散化的PSO 的研究還是不多的，但是仍然存在著一些這樣的算法應(yīng)用與離散化的相關(guān)的問題中。例如旅行商問題 （ TSP） ，在以離散空間為基礎(chǔ)的前提下 DSPO 通過利 第 11 頁 共 40 頁 用 位運(yùn)算，這樣雖然可能會(huì)增加一些計(jì)算的時(shí)間，但是這樣便不會(huì)產(chǎn)生多余的搜索的問題，這樣還能自然地描述離散的問題，并能和其他的演化算法緊密地結(jié)合起來，如此使得其有更好的發(fā)展前景。但是由于研究還是不是特別的多，因此缺乏一個(gè)通用的、統(tǒng)一的和標(biāo)準(zhǔn)的模型。 算法原理 二進(jìn)制 PSO 利用粒子的速度作為粒子的位置的變化的概率，這個(gè)觀點(diǎn)由Kennedy和 Eberhart 兩位博士首次提出的，專門用于解決 0~1 類型的規(guī)劃的問題，在這個(gè)算法中，僅僅就是使用二進(jìn)制的量來代表每個(gè)粒子并且利用二進(jìn)制空間來代替超立方的空 間，然后用二進(jìn)制的量之間的轉(zhuǎn)化來使得粒子在超空間中移動(dòng)。于是得出更新速度的公式為： )()( idgdidididid xpxpvv ????? ?? 公式中的 vid 為粒子的位置的變化的概率； xid 代表了當(dāng)前粒子的確切的位置的值；φ則為常數(shù)因子，即為該粒子的學(xué)習(xí)因子；公式中的 pid 和 pgd 則分別代表了在空間中的粒子的局部的最優(yōu)的位置和全局的最優(yōu)的位置。由于此算法為二進(jìn)制的空間中的算法因此以上的參數(shù)中的 xid、 pid 和 pgd 的值都只能為 0 或者是 1。于是根據(jù)速度的變化的公式可以得到粒子的位置的 公式為： ??? ?? )(0 ( ) ) )()((1 e sle sigran difx id 其中)e x p(1 1)( idid vvsig ???. 在上述公式中的 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)出來，比如在組合式的優(yōu)化問題當(dāng)中表現(xiàn)的更為的突出，于是研究學(xué)家們便直接對(duì)連續(xù)的 PSO 離散化，將粒子的非整的位置近似的等于整數(shù)，其余的部分保持和連續(xù)的 PSO 中一致。雖然在算法中出現(xiàn)了近似的取整的情況，并利用這些近 第 12 頁 共 40 頁 似的解得可行的解，但是得到的可行解在高維的規(guī)劃問題中仍能式算法具有較高的穩(wěn)定性，并使得算法不會(huì)輕易地陷入停止的搜索狀態(tài)。因此可得離散粒子群算法（ DPSO）的流程圖如圖 31 所示。 開 始初 始 化 粒 子 的 位 置和 速 度尋 找 個(gè) 體 最 優(yōu) 和 全局判 斷 是 否 滿 足 的約 束 條 件利 用 公 式 更 新 粒 子的 位 置 和 速 度尋 找 當(dāng) 前 個(gè) 體 最 優(yōu)和 全 局 最 優(yōu)計(jì) 算 粒 子 的 群 體 相似 度判 斷 群 體 相 似 度是 否 大 于 給 定 的伐 值啟 用 排 斥 算 子判 斷 是 否 滿 足 結(jié)束 條 件結(jié) 束是是否否否 圖 31 離散粒子群算法流程圖 算法應(yīng) 用 由于 PSO 的眾多的優(yōu)點(diǎn)，目前它已經(jīng)應(yīng)用在生活、工業(yè)和科學(xué)等的各個(gè)領(lǐng)域中，并且成為了解決實(shí)際的工程與科學(xué)問題熱門算法。同時(shí) DPSO 也得到了廣泛的研究應(yīng)用，比如在組合性的優(yōu)化難題上，超大規(guī)模的集成電路上，電力系統(tǒng)上，無線的傳感器的網(wǎng)絡(luò)中和用于挖掘數(shù)據(jù)等等。通過不斷的研究和應(yīng)用，算法將會(huì)被更加廣泛的應(yīng)用，給我們的生活、工業(yè)和科學(xué)帶來更多的便利和突破。 以下我們對(duì)常見的 DPSO 的應(yīng)用簡單的分析與介紹： 第 13 頁 共 40 頁 ①、典型性的組合型的優(yōu)化問題 —— 該問題屬于運(yùn)籌學(xué)的一個(gè)重要的部分，其中主要包括了 TSP 的問題、 01 背 包的問題、工作的排序問題還有最小生成樹的問題等。用重新總結(jié)定義的 PSO 來操作算式的方法得出了一種 TSPDPSO 的算法，于是根據(jù)這一改進(jìn)和突破，更多的學(xué)者以典型性的組合型的優(yōu)化問題為基礎(chǔ)提出了解決 TSP 的問題 [2324]、 01 背包的問題 [2526]、工作的排序問題還有最小生成樹的問題等一系列的的算法。 ②、電力體統(tǒng) —— 在該領(lǐng)域中，需要解決的是在最低成本的情況下進(jìn)行發(fā)電擴(kuò)張的問題，利用 DPSO 能很有效的處理該種有強(qiáng)約束力的組合型的優(yōu)化問題。由于近幾年來 DPSO 算法得到了有力地發(fā)展，解決這一問題的 方法也隨之越來越多，比如可以使用改進(jìn)的 BPS 來恢復(fù)配電網(wǎng)出現(xiàn)的故障；或者可以根據(jù)配輸電網(wǎng)的擴(kuò)展規(guī)劃的問題與電網(wǎng)的重構(gòu)問題來設(shè)計(jì)適合的 DPSO；又或者可以用DPSO 處理電力系統(tǒng)中滿足發(fā)電機(jī)的約束的經(jīng)濟(jì)的調(diào)度問題；亦或是就給出的電力市場(chǎng)中盈利區(qū)間內(nèi)的約束問題改進(jìn)我們的 DPSO；亦或者是關(guān)于熱備、停開機(jī)等約束的機(jī)組的調(diào)度問題與組合機(jī)組的等問題利用 DPSO 可以很好地將其解決。 ③、 VLSI—— VLSI 的設(shè)計(jì)中的布置線路、布值全局與布置圖形是整個(gè) VLSI設(shè)計(jì)的最重要的環(huán)節(jié)同時(shí)也是整個(gè)設(shè)計(jì)的核心關(guān)鍵所在。然而其 中的 布置線路、布值全局與布置圖形又是整個(gè)設(shè)計(jì)中最為復(fù)雜最為困難的，該問題也以被證實(shí)為NP 的難題。如若使用傳統(tǒng)的算法來優(yōu)化這個(gè)問題要么會(huì)因?yàn)楸康挠?jì)算要么就會(huì)因?yàn)榈贸龅慕Y(jié)果是局部性的而非全局的，很顯然傳統(tǒng)的算法已經(jīng)是不能很好解決這些棘手的問題了。于是為了解決這一抽象性的難題研究學(xué)者們想到了在集成的電路中間使用啟發(fā)式的算法來進(jìn)行優(yōu)化。但是 PSO 擁有更容易被實(shí)現(xiàn)的優(yōu)點(diǎn)和更厲害的全局性的優(yōu)化能力，學(xué)者們轉(zhuǎn)而開始在 VLSI 的設(shè)計(jì)中使用 PSO，于是辨得出了更多有效的關(guān)于解決布置線路 [2728]、布值全局 [2930]與布置圖形問題的 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ì)使得無線的 第 14 頁 共 40 頁 傳感器網(wǎng)絡(luò)之間的游泳資源相對(duì)的缺乏例如，因此要解決這些問題就顯得有些迫不及待了。這幾年來，表示已經(jīng)有一些研究學(xué)者對(duì) WSN 的各種問 題展開了研究并且已經(jīng)抽離出了它的數(shù)學(xué)模型來進(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 來求解并得到最優(yōu)的結(jié)果。 ⑤、數(shù)據(jù)挖掘 —— 它的屬性的選擇使用了 BPSO 得到了解決；并已有文獻(xiàn)提出在 DPSO 基礎(chǔ)之上的特征子集的選擇方法；還有文獻(xiàn)為傳統(tǒng)的特征的選擇的不足引入了粗超的簡約的模型，同時(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，而且使的它與圖像匹配的問題有較好的求解效果；還有文獻(xiàn)表示可以在使用 PSO 的基礎(chǔ)上利用紅外的圖像的分割的技術(shù)得到另一種快速的二維的熵算法。 ⑦、 VRP—— 雖然 VRP 是 TSP 的一種拓展的問題，但是在利用 PSO 求解釋VRP 時(shí)用到了全不一樣的的技術(shù)?，F(xiàn)有文獻(xiàn)提出了可以通過將連續(xù)空間里的粒子進(jìn)行僅是的離 散化然后再加粒子的位置映射到離散的排序空間中，這樣便能得到粒子在離散狀態(tài)下的變化情況。與其他的遺傳的算法相比較，在搜索的時(shí)候RPSO 擁有更高的成功率，更高的最優(yōu)解的質(zhì)量與更優(yōu)的時(shí)間復(fù)雜度。 ⑧、 Job2Shop—— 該問題一直都是調(diào)度和柔韌性制造的系統(tǒng)中人們時(shí)刻關(guān)注的一個(gè)問題之一。其用意在于利用現(xiàn)在擁有的資源來達(dá)到滿足任務(wù)需要的約束，并且使得所有的人物能盡量在規(guī)定的時(shí)間之內(nèi)較好的完成。 Cagnina 等研究學(xué)者曾在使用 PSO 處理單機(jī)的調(diào)度問題時(shí)，邊用到了隨機(jī)的鍵來顯示粒子的具體的位置。然后再利用粒子的鍵 值對(duì)作業(yè)排序，這需要先將粒子的具體位置影射到一種合法的調(diào)度上，只有這樣才能更為便捷地使用連續(xù) PSO 來計(jì)算出粒子具體的速度和具體的位置。在各個(gè)領(lǐng)域還廣泛的存在很多關(guān)于 PSO 在 Job2Shop 的應(yīng)用。 ⑨、其他領(lǐng)域 —— 綜合以上所敘述的關(guān)于 DPSO 的應(yīng)用，此外， DPSO 在神經(jīng)元 第 15 頁 共 40 頁 的網(wǎng)絡(luò)訓(xùn)練、一些有關(guān)機(jī)械的設(shè)計(jì)、通訊、化工業(yè)和經(jīng)濟(jì)生活等領(lǐng)域中都有獲得許多的研究性的成果。 本節(jié)小結(jié) 本章對(duì) DPSO 算法 (離散粒子群算法 )進(jìn)行了深入淺出的介紹，首先大概介紹了 DPSO 算法的來源、形成和發(fā)展。然后展開對(duì) DPSO 算法詳細(xì)描述，對(duì) DPSO算法原理進(jìn)行深刻的剖析和認(rèn)識(shí)，最后為了能更好的對(duì) DPSO 算的理解，詳細(xì)的例舉了 DPSO 在各個(gè)領(lǐng)域的應(yīng)用 。 第 16 頁 共 40 頁 第三章 車輛路徑問題分析 物流配送 由于互聯(lián)的發(fā)展