粒子群算法概述

粒子群算法(Particle Swarm Optimization)是由鳥(niǎo)群捕食得到啟發(fā)的一種算法，在鳥(niǎo)類(lèi)覓食過(guò)程中，每只鳥(niǎo)都會(huì)利用自身經(jīng)驗(yàn)和群體信息來(lái)尋找食物。在覓食過(guò)程中妹孙，每只鳥(niǎo)僅僅追蹤有限數(shù)量的鄰居诊胞，但是最終整個(gè)鳥(niǎo)群好像在某個(gè)中心的控制下飛行。這一現(xiàn)象說(shuō)明復(fù)雜的全局行為可以由簡(jiǎn)單規(guī)則的相互作用形成箩祥，其表現(xiàn)取決于群體搜索策略和群體之間的信息交換。

PSO基本原理

根據(jù)上面現(xiàn)象進(jìn)行抽象荆责，PSO算法是一種在維搜索空間中(搜索空間可能是解空間滥比，也可能是問(wèn)題空間，取決于如何對(duì)需要求解的問(wèn)題進(jìn)行編碼)做院，用由個(gè)粒子組成的種群通過(guò)一定的搜索策略進(jìn)行位置更新盲泛，從而尋找搜索空間中適應(yīng)度最佳值的算法。

在這個(gè)過(guò)程中键耕，每個(gè)粒子的位置代表優(yōu)化問(wèn)題的一個(gè)解(大多數(shù)情況下是可行解)寺滚。適應(yīng)度函數(shù)是和優(yōu)化問(wèn)題的目標(biāo)函數(shù)直接相關(guān)的，它通常是針對(duì)具體問(wèn)題進(jìn)行具體設(shè)計(jì)屈雄，從而幫助算法收斂到最優(yōu)解村视。

我們將上面所述的種群記做，其中第個(gè)粒子的位置為酒奶，速度為蚁孔。粒子的個(gè)體最佳適應(yīng)度值為，所屬鄰域的全局最佳適應(yīng)度為惋嚎。

粒子的位置和速度以迭代的方式進(jìn)行如下更新：

其中各參數(shù)說(shuō)明如下：

• 是粒子在第步迭代時(shí)的速度杠氢，是在第維的速度分量；
• 是粒子在第步迭代的位置另伍，是第維的位置分量鼻百；
• 是粒子在第步迭代時(shí)的個(gè)體最佳適應(yīng)度對(duì)應(yīng)位置；
• 是粒子在第步迭代時(shí)的所屬鄰域最佳適應(yīng)度對(duì)應(yīng)位置；
• 稱(chēng)為慣性權(quán)重温艇，它體現(xiàn)了粒子繼承原有速度的多少因悲，在一定范圍內(nèi)，慣性越大勺爱，則粒子受原有速度影響越大晃琳，受當(dāng)前環(huán)境影響越小，表現(xiàn)為粒子具有更多的發(fā)散性琐鲁，算法的全局搜索能力更好蝎土；慣性越小，則粒子受到當(dāng)前環(huán)境影響越大绣否，表現(xiàn)為粒子的收斂性強(qiáng)，局部搜索能力更佳挡毅；
• 為加速度常數(shù)，體現(xiàn)了粒子對(duì)于自身經(jīng)驗(yàn)的信任情況跪呈，體現(xiàn)了粒子對(duì)于鄰域內(nèi)其他個(gè)體傳遞信息的信任情況段磨；
• 是[0,1]之間的隨機(jī)數(shù)耗绿，服從均勻分布苹支；

需要注意的是速度更新的每一步中，對(duì)的每一個(gè)分量都會(huì)進(jìn)行一次取隨機(jī)數(shù)误阻，因此移動(dòng)的方向并非嚴(yán)格是自身速度债蜜、向自身最佳歷史位置和向鄰域最佳歷史位置的組合，而是在一個(gè)區(qū)域內(nèi)的近似究反，如下圖所示：

1-PSO searching move

上面的更新方程體現(xiàn)了粒子群算法的一些基本性質(zhì)：

• 在搜索過(guò)程中寻定，粒子有三種方式調(diào)整自身的速度：沿著之前的方向；根據(jù)自身經(jīng)驗(yàn)改變方向精耐；根據(jù)鄰域內(nèi)其他粒子傳遞的信息改變方向狼速；而三個(gè)參數(shù)反應(yīng)了對(duì)這三種方式的權(quán)重分配向胡；
• 粒子群中的粒子具有一定記憶特性和對(duì)環(huán)境的感知，這是通過(guò)記錄自身的最佳適應(yīng)度對(duì)應(yīng)位置和鄰域內(nèi)粒子的最佳適應(yīng)度對(duì)應(yīng)位置來(lái)實(shí)現(xiàn)的惊完，這種個(gè)體之間的記憶和信息的交流共享是群體智能算法的重要特性僵芹。

基本PSO的改進(jìn)

基本粒子群的一些問(wèn)題

標(biāo)準(zhǔn)的粒子群算法存在的主要問(wèn)題(大部分也是群體進(jìn)化計(jì)算的共性問(wèn)題)為：

• 初始化過(guò)程是隨機(jī)的，部分粒子位置不佳专执，在搜索過(guò)程中沒(méi)有有利作用淮捆。這樣雖然可以保證初始種群的粒子在搜索空間內(nèi)分布比較均勻，但是由于沒(méi)有利用問(wèn)題的先驗(yàn)信息，部分粒子遠(yuǎn)離最優(yōu)解所在區(qū)域攀痊，在一定程度上影響到算法效率和解的質(zhì)量桐腌；
• 在高維復(fù)雜問(wèn)題中，容易陷入“早熟”苟径。也就是由于搜索空間較大案站，種群在還未找到全局最優(yōu)解時(shí)便已經(jīng)聚集到一起，從而收斂棘街。早熟的收斂點(diǎn)有可能是局部最優(yōu)蟆盐，也有可能是局部最優(yōu)鄰域中的某個(gè)點(diǎn)。也就是說(shuō)遭殉，早熟的情況下石挂，算法甚至不能保證收斂到局部最優(yōu)，這極大影響了算法的實(shí)用性险污；
• 超參數(shù)的選定比較困難痹愚。例如對(duì)于速度的設(shè)定，如果速度過(guò)大蛔糯，前期搜索速度會(huì)很快拯腮，但是容易錯(cuò)過(guò)最優(yōu)解(類(lèi)似于梯度下降中步長(zhǎng)過(guò)大的情況)；而速度設(shè)定過(guò)小則會(huì)導(dǎo)致搜索效率低蚁飒，收斂慢动壤，同樣難以應(yīng)用；

收斂速度改進(jìn)

對(duì)于粒子群算法來(lái)說(shuō)淮逻，收斂速度主要由粒子的飛行速度決定琼懊，而飛行速度由三個(gè)超參數(shù)決定肩碟，因此對(duì)收斂速度的改進(jìn)也就集中在對(duì)這三個(gè)超參數(shù)的選擇和更新策略上。

對(duì)于凸椿，如前所述削祈，較大的有利于全局搜索，而較小值則對(duì)局部搜索有利脑漫，常用的慣性權(quán)重值介于0.8與1.2之間髓抑。在搜索前期，我們通常需要進(jìn)行大規(guī)模的全局搜索优幸，而在后期則是在最優(yōu)解鄰域內(nèi)對(duì)解進(jìn)行fine tune吨拍，根據(jù)這個(gè)特點(diǎn)，現(xiàn)在比較常用的更新策略是線性權(quán)值遞減策略(Linearly Decreasing Weight, LDW)网杆，即在搜索開(kāi)始時(shí)采用較大的權(quán)值羹饰，而隨著搜索過(guò)程進(jìn)行對(duì)權(quán)值進(jìn)行遞減伊滋，從而滿(mǎn)足我們前面說(shuō)的期望。

線性權(quán)值遞減的權(quán)值更新策略如下：

其中队秩，為權(quán)重初始值笑旺，為權(quán)重最終值。為最大迭代步數(shù)馍资，為當(dāng)前迭代步數(shù)筒主。一個(gè)比較常用的默認(rèn)參數(shù)是選擇。采用線性權(quán)值遞減默認(rèn)參數(shù)鸟蟹，得到的權(quán)值變化圖如下：

<img src="https://tva1.sinaimg.cn/large/007S8ZIlgy1ggrnm3hrg8j30nw0ggq42.jpg" alt="2-Linearly decreasing weight" style="zoom:50%;" />

對(duì)于加速度常數(shù)來(lái)說(shuō)乌妙，通常是對(duì)具體問(wèn)題進(jìn)行一系列的實(shí)驗(yàn)來(lái)選取最優(yōu)值。目前還沒(méi)有研究結(jié)果能在事先給出“最優(yōu)”的參數(shù)選取建钥。一種常用的經(jīng)驗(yàn)方法是在起始時(shí)先讓藤韵。

族群多樣性改進(jìn)

對(duì)于隨機(jī)優(yōu)化算法的性能來(lái)說(shuō)，族群的多樣性是非常重要的：

• 為了盡最大可能找到全局最優(yōu)解熊经，我們總是希望在計(jì)算開(kāi)始時(shí)荠察，粒子能夠在搜索空間內(nèi)盡可能均勻發(fā)散的分布；而隨著計(jì)算的進(jìn)行奈搜，粒子逐漸聚集，最終達(dá)到收斂盯荤；
• 在另一方面馋吗，族群多樣性會(huì)影響到收斂速度，如果族群非常分散秋秤，那么其收斂速度通常會(huì)比較慢宏粤。

對(duì)于族群多樣性的改進(jìn)一般有兩種方法：改進(jìn)拓?fù)浣Y(jié)構(gòu)（也就是粒子之間相互連接的方式）和設(shè)計(jì)保持種群多樣化策略。

拓?fù)浣Y(jié)構(gòu)的改進(jìn)

粒子群算法在鄰域中共享信息灼卢，而鄰域是由拓?fù)浣Y(jié)構(gòu)定義的绍哎，因此不同的拓?fù)浣Y(jié)構(gòu)決定了信息在粒子之間傳遞的速度。下圖展示了一些常見(jiàn)的鄰域拓?fù)浣Y(jié)構(gòu)：

3-Neighborhood topology

當(dāng)鄰域結(jié)構(gòu)是全連接(Fully connected)時(shí)鞋真，對(duì)于任意粒子來(lái)說(shuō)崇堰，整個(gè)種群都是它的鄰居，這種情況下的PSO也叫做全局版本涩咖；當(dāng)鄰域結(jié)構(gòu)是其他拓?fù)浣Y(jié)構(gòu)時(shí)海诲，對(duì)于一個(gè)粒子，只有在拓?fù)浣Y(jié)構(gòu)上與其直接相連的粒子才是它的鄰居檩互，這種情況下的PSO也叫做局部版本特幔。

除了固定的拓?fù)浣Y(jié)構(gòu)以外，也有學(xué)者提出用動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)來(lái)改變種群中信息的流動(dòng)速度闸昨；還可以引入聚類(lèi)的思想蚯斯，用聚類(lèi)后的簇中心粒子位置來(lái)替代粒子自身最優(yōu)解位置薄风，用全局的簇中心位置來(lái)替代全局最優(yōu)解位置。

種群多樣化策略

在粒子群算法中拍嵌，隨著迭代的進(jìn)行遭赂，種群逐漸收斂到一點(diǎn)，也就喪失了進(jìn)化的動(dòng)力撰茎，如果收斂時(shí)機(jī)過(guò)早嵌牺，就會(huì)影響到找到的解的質(zhì)量。為了保持種群的多樣性龄糊，研究者設(shè)計(jì)了一系列的策略逆粹，下面列出幾個(gè)比較有名的：

• Clerc提出了no-hope/re-hope策略，在迭代過(guò)程中對(duì)種群進(jìn)行no-hope檢驗(yàn)炫惩，如果發(fā)現(xiàn)種群進(jìn)化動(dòng)力喪失僻弹，就進(jìn)入re-hope過(guò)程，讓種群重新在搜索空間中分散開(kāi)他嚷，防止陷入局部最優(yōu)朗伶；
• Xie提出了一種耗散粒子群優(yōu)化算法，通過(guò)施加噪聲擾動(dòng)挽铁，為系統(tǒng)引入負(fù)熵澜搅，從而為種群保留不斷進(jìn)化的動(dòng)力；
• Thiemo等提出了一種粒子空間擴(kuò)展策略粘咖，為每個(gè)粒子賦予一個(gè)半徑值蚣抗，以檢測(cè)是否發(fā)生碰撞，當(dāng)兩個(gè)粒子發(fā)生碰撞時(shí)瓮下，讓它們彈開(kāi)翰铡，以保持種群的多樣性；
• ...

融合其他算法思想

單一算法的搜索策略和脫離局部最優(yōu)的能力是有限的讽坏，因此智能算法常常會(huì)選擇融合其他算法的機(jī)制來(lái)增加尋優(yōu)能力锭魔。

微分進(jìn)化思想、遺傳算法路呜、多種群協(xié)作和競(jìng)爭(zhēng)思想迷捧、混沌搜索、免疫算法和模擬退火等等算法和思想都可以融合進(jìn)PSO中胀葱。

PSO算法流程

標(biāo)準(zhǔn)PSO的流程可以用下面的流程圖表示：

4-PSO flowchart

離散粒子群算法(Discrete PSO)

在求解VRP類(lèi)問(wèn)題党涕，或者擴(kuò)大到離散優(yōu)化和組合優(yōu)化問(wèn)題時(shí)，我們首先需要注意PSO的編碼問(wèn)題巡社。

原始的PSO采用實(shí)數(shù)編碼膛堤，對(duì)于速度計(jì)算、位置更新等非常方便而自然晌该，但是對(duì)于離散優(yōu)化和組合優(yōu)化問(wèn)題肥荔，有時(shí)實(shí)數(shù)編碼難以直接應(yīng)用绿渣，這就需要應(yīng)用二進(jìn)制編碼(Binary encoding)或者排列編碼(Permutation encoding)，對(duì)于非實(shí)數(shù)編碼燕耿，需要重新定義距離中符、速度、位置的含義和相應(yīng)操作誉帅。

從連續(xù)到離散 -- 操作的重定義

粒子群算法中的抽象操作

回顧基本的粒子群算法淀散，在整個(gè)搜索過(guò)程中，我們涉及的抽象操作有以下幾種：

• 粒子的速度計(jì)算：位置-位置 -> 速度
• 速度的標(biāo)量乘：標(biāo)量*速度 -> 速度
• 速度和：速度+速度 -> 速度
• 粒子的位置更新： 位置+速度 -> 位置

此外還有粒子的評(píng)價(jià)蚜锨，但是由于評(píng)價(jià)涉及到粒子的解碼档插，是具體問(wèn)題具體設(shè)計(jì)的，并不具有通用性亚再，因此無(wú)法進(jìn)行抽象層面的定義郭膛。

PSO求解VRP問(wèn)題的排列編碼

對(duì)于有個(gè)顧客的VRP問(wèn)題，這里采用排列編碼氛悬，即粒子的位置用0到的整數(shù)排列來(lái)表示则剃。

例如對(duì)一個(gè)包含5個(gè)顧客的問(wèn)題來(lái)說(shuō)，一個(gè)可能的粒子位置為如捅。

操作的定義

這里參考Clerc在用PSO求解TSP問(wèn)題中定義的操作：

粒子速度的定義

對(duì)于排列編碼棍现，其搜索空間為所有可能的排列。為了進(jìn)行不同排列的探索镜遣，速度定義為對(duì)排列的一系列交換轴咱。

設(shè)為速度的長(zhǎng)度(即交換的次數(shù))，定義為對(duì)兩數(shù)進(jìn)行一次交換烈涮，那么速度可以定義為：

一個(gè)空的速度定義為，也就是空集窖剑。

定義坚洽，則負(fù)速度可以定義為：

粒子的位置更新

明確了位置和速度的含義之后，就可以很容易的對(duì)粒子的位置進(jìn)行更新了西土。

假設(shè)在某個(gè)時(shí)刻讶舰，一個(gè)長(zhǎng)度為5的粒子的位置為，速度為需了，那么可以得到：

需要注意的是跳昼，對(duì)于，我們可以得到同樣的肋乍，這也就是說(shuō)和是等效的鹅颊。

粒子的速度計(jì)算

粒子的速度通過(guò)兩個(gè)位置的差得到，也就是說(shuō)從兩個(gè)位置墓造，我們可以計(jì)算出使得堪伍。如前所述锚烦，給定的兩個(gè)位置并不能得到唯一的速度，因此我們需要設(shè)計(jì)一些算法來(lái)求得速度帝雇。

一個(gè)可行的算法是“換位減”涮俄，對(duì)于有個(gè)顧客的VRP問(wèn)題，“換位減”的步驟如下：

1. 初始化i=0尸闸，v為空集
2. 如果i=N彻亲，跳轉(zhuǎn)到步驟4，否則進(jìn)入步驟3
3. 比較X1和X2吮廉，如果在第i個(gè)位置上 X1[i] = X2[i]苞尝，設(shè)定i=i+1，跳轉(zhuǎn)到步驟2茧痕；如果 X1[i] != X2[i]野来，則交換X2中的元素X1[i]和X2[i]，設(shè)定i=i+1踪旷，將(X1[i],X2[i])加入v曼氛，轉(zhuǎn)入步驟2
4. 算法結(jié)束，輸出速度

下圖給出了一個(gè)計(jì)算過(guò)程的示例：

5-position minus

最終我們得到速度

速度的標(biāo)量積

速度乘以一個(gè)標(biāo)量得到的仍然是速度令野。這里的標(biāo)量有幾種可能性：

• 舀患，此時(shí)；
• 气破，令聊浅，從中取前個(gè)分量；即现使；
• 低匙，那么可以拆分為一個(gè)不大于的整數(shù)和一個(gè)之間的小數(shù)，即碳锈，此時(shí)顽冶，第二部分的計(jì)算同上，第一部分則是對(duì)的重復(fù) -- 售碳，也即重復(fù)次强重；
• ，則贸人，也就是對(duì)常數(shù)取負(fù)间景，得到一個(gè)正系數(shù)，然后乘以負(fù)速度艺智；

這樣就完整定義了速度的數(shù)乘倘要。

速度和

兩個(gè)速度的和定義為兩個(gè)速度中交換操作的有順序的并集。例如十拣，那么有：

這里需要注意的是碗誉，也就是速度求和并不具備交換性召嘶。

時(shí)間復(fù)雜度分析

對(duì)于優(yōu)化算法來(lái)說(shuō)，時(shí)間復(fù)雜度是一個(gè)重要的問(wèn)題哮缺。如果時(shí)間復(fù)雜度過(guò)高弄跌，算法的可擴(kuò)展性就較差，對(duì)于大規(guī)模問(wèn)題很可能不能適用尝苇。

假設(shè)PSO算法的種群規(guī)模為铛只，迭代次數(shù)為，問(wèn)題規(guī)模為糠溜。我們可以先對(duì)單個(gè)粒子上的操作進(jìn)行時(shí)間復(fù)雜度分析淳玩，然后擴(kuò)展到整個(gè)種群。

對(duì)于單個(gè)粒子非竿，各個(gè)操作的復(fù)雜度如下：

• 適應(yīng)度評(píng)價(jià)：對(duì)于VRP問(wèn)題來(lái)說(shuō)蜕着，我們需要對(duì)每個(gè)個(gè)體的路徑長(zhǎng)度進(jìn)行加總，其復(fù)雜度為红柱；
• 選擇個(gè)體歷史最優(yōu)和鄰域歷史最優(yōu)位置：復(fù)雜度為承匣；
• 速度計(jì)算：采用換位減的方式，需要對(duì)編碼從左向右進(jìn)行一次線性?huà)呙璐盖模淦骄鶑?fù)雜度為韧骗；
• 位置更新：復(fù)雜度和速度的長(zhǎng)度相關(guān)，在最壞情況下速度的長(zhǎng)度也不會(huì)超過(guò)零聚，因此位置更新的復(fù)雜度也是袍暴；

因此對(duì)于單個(gè)粒子來(lái)說(shuō)，一次迭代的時(shí)間復(fù)雜度和問(wèn)題規(guī)模成正比隶症，為政模。

可以得到整體算法的復(fù)雜度為。

用離散粒子群算法求解CVRP問(wèn)題

算例介紹

本文采用的CVRP算例來(lái)自Augerat et al. 的數(shù)據(jù)集蚂会，可以到這里下載淋样。

下面就數(shù)據(jù)結(jié)構(gòu)進(jìn)行說(shuō)明，任意一個(gè)數(shù)據(jù)文件颂龙，例如A-n32-k5，都分為下面幾個(gè)部分:

數(shù)據(jù)信息

這部分形如：

NAME : A-n32-k5
COMMENT : (Augerat et al, Min no of trucks: 5, Optimal value: 784)
TYPE : CVRP
DIMENSION : 32
EDGE_WEIGHT_TYPE : EUC_2D 
CAPACITY : 100

給出了數(shù)據(jù)集的基本信息：

• 數(shù)據(jù)集名為 A-n32-k5
• 最小用車(chē)5輛纽什，最優(yōu)解路徑總長(zhǎng)度為784
• 類(lèi)型是CVRP問(wèn)題
• 維度措嵌，也就是節(jié)點(diǎn)數(shù)為32
• 邊的權(quán)重類(lèi)型為2D的歐幾里得距離
• 車(chē)輛最大載重為100單位

節(jié)點(diǎn)坐標(biāo)

NODE_COORD_SECTION 
 1 82 76
 2 96 44
 3 50 5
 4 49 8
 ...

給出了節(jié)點(diǎn)的編號(hào)和X，Y坐標(biāo)芦缰。根據(jù)這個(gè)信息我們就可以計(jì)算兩個(gè)節(jié)點(diǎn)之間的二維歐幾里得距離了企巢。

節(jié)點(diǎn)需求

DEMAND_SECTION 
1 0 
2 19 
3 21 
4 6 
5 19 
6 7 
...

給出了各個(gè)節(jié)點(diǎn)的需求量。

車(chē)庫(kù)

DEPOT_SECTION 
 1  
 -1  

表明這個(gè)問(wèn)題中只有一個(gè)車(chē)庫(kù)让蕾，也就是節(jié)點(diǎn)1浪规。要求每條路徑從車(chē)庫(kù)出發(fā)或听，到車(chē)庫(kù)結(jié)束。

代碼實(shí)現(xiàn)

在這里我們用代碼實(shí)現(xiàn)一個(gè)標(biāo)準(zhǔn)的整數(shù)編碼PSO笋婿，在前面提到的數(shù)據(jù)集里選擇幾個(gè)進(jìn)行測(cè)試誉裆，了解不額外增加局部搜索和脫出局部最優(yōu)機(jī)制的情況下，整數(shù)編碼PSO的性能表現(xiàn)缸濒。

代碼作為演示之用足丢，沒(méi)有經(jīng)過(guò)性能優(yōu)化，只能作為一個(gè)參考庇配。

速度類(lèi)

對(duì)于速度斩跌，按照之前所列，我們需要實(shí)現(xiàn)標(biāo)量乘捞慌、取反和加法操作耀鸦，這些可以通過(guò)運(yùn)算符重載做到。

# --------------------------------
# 速度類(lèi)
# --------------------------------
class Velocity(object):
    """
    整數(shù)編碼下PSO的速度形如[(1,3), (2,5)]啸澡，其含義為先對(duì)1, 3節(jié)點(diǎn)進(jìn)行交換袖订，然后對(duì)2, 5節(jié)點(diǎn)進(jìn)行交換
    """

    def __init__(self, exchange_list=None):
        if exchange_list is None:
            self._vel = list()  # 私有變量，保存交換對(duì)
        else:
            self._vel = exchange_list

    def __mul__(self, c: float):
        """
        重載乘法锻霎，允許浮點(diǎn)數(shù) c 和速度 v 相乘
        浮點(diǎn)數(shù)c有下面四種情況：
        1. c < 0著角， 此時(shí)對(duì)常數(shù)取負(fù)，得到一個(gè)正數(shù)旋恼，同時(shí)對(duì)速度也取負(fù)吏口，轉(zhuǎn)化為正數(shù)和速度的乘法
        2. c = 0，此時(shí)得到 cv = empty set
        3. c in (0,1]冰更，此時(shí)從v中提取前 int(c * len(v)) 個(gè)分量
        4. c > 1产徊，此時(shí)可以拆分為一個(gè)大于1的數(shù)
        :param c: float，一個(gè)浮點(diǎn)數(shù)
        :return: 處理之后的速度
        """
        # 數(shù)據(jù)類(lèi)型檢查
        try:
            c = float(c)
        except:
            raise ValueError('Velocity can only be multiplied with a float, not {}'.format(type(c)))
        # 進(jìn)行乘法
        if c < 0.0:  #
            return -c * (-Velocity(self._vel))
        elif c == 0.0:  # 返回空速度
            return Velocity()
        elif 0 < c <= 1:  # 從前向后取v中的部分分量
            vel_len = len(self._vel)
            cnt = int(c * vel_len)
            return Velocity([self._vel[i] for i in range(cnt)])
        else:  # c > 1的情況蜀细，分成整數(shù)和小數(shù)部分進(jìn)行處理
            int_part = int(c)  # 整數(shù)部分
            dec_part = c - int_part  # 小數(shù)部分
            return Velocity(int_part * self._vel) + dec_part * Velocity(self._vel)

    def __rmul__(self, c: float):
        return Velocity(self._vel) * c

    def __neg__(self):
        """
        重載取反操作
        對(duì)于Velocity([x,y],[y,z],...)來(lái)說(shuō)舟铜， -Velocity = ([y,x],[z,y],...)
        :return:
        """
        return Velocity([[elem[1], elem[0]] for elem in self._vel])

    def __add__(self, other):
        """
        重載速度加法
        對(duì)于兩個(gè)速度 vel1 = [[x,y], [y,z], [z,t]]和 vel2 = [[z, x]]
        vel1 + vel2 = [[x,y], [y,z], [z,t], [z,x]]
        :param other:
        :return:
        """
        return Velocity(self._vel + other.exchange_list)

    def __repr__(self):
        return "Velocity({})".format(str(self._vel))

    @property
    def exchange_list(self):
        """
        Getter函數(shù)，取出交換對(duì)
        :return:
        """
        return self._vel

位置類(lèi)

對(duì)于位置類(lèi)奠衔，我們需要實(shí)現(xiàn)換位減以及和速度相加：

# --------------------------------
# 位置類(lèi)
# --------------------------------
class Position(object):
    """
    整數(shù)編碼下的位置類(lèi)形如[3,2,6,4,5]谆刨，它是 *所有節(jié)點(diǎn)* 的一個(gè)permutation
    """

    def __init__(self, seq=None):
        if seq is None:
            self._seq = list()  # 保存一個(gè)permutation，代表路徑上訪問(wèn)節(jié)點(diǎn)的次序
        else:
            self._seq = seq

    def __sub__(self, other):
        """
        兩個(gè)Position實(shí)例進(jìn)行 *換位減* 归斤，得到一個(gè)Velocity實(shí)例
        :param other: Position實(shí)例
        :return: Velocity實(shí)例
        """
        exchange_list = list()
        if len(self._seq) != len(other.visit_sequence):
            raise Exception("Cant perform calculation for Positions with different sequence length")
        pos2_seq = list(other.visit_sequence)
        for i in range(len(self._seq)):
            elem_seq1 = self._seq[i]
            elem_seq2 = pos2_seq[i]
            if elem_seq1 != elem_seq2:  # 如果兩個(gè)position對(duì)應(yīng)位置上的元素不相等
                # 找到pos2_seq中這兩個(gè)元素對(duì)應(yīng)的index
                idx1, idx2 = pos2_seq.index(elem_seq1), pos2_seq.index(elem_seq2)
                # 交換兩個(gè)元素并將該操作加入velocity
                pos2_seq[idx1], pos2_seq[idx2] = pos2_seq[idx2], pos2_seq[idx1]
                exchange_list.append([elem_seq1, elem_seq2])
        return Velocity(exchange_list)

    def __add__(self, other):
        """
        Position + Velocity = Position
        也即是在permutation上應(yīng)用Velocity所表示的變換
        例如Position = [1, 3, 2, 4, 5]痊夭， Velocity = [[1,3], [2,5], [3,4]]
        Position + Velocity = [4, 1, 5, 3, 2]
        :param other:
        :return: 一個(gè)Position實(shí)例
        """
        seq_new = list(self._seq)
        for elem in other.exchange_list:
            idx0, idx1 = seq_new.index(elem[0]), seq_new.index(elem[1])
            seq_new[idx0], seq_new[idx1] = seq_new[idx1], seq_new[idx0]
        return Position(seq_new)

    def __repr__(self):
        return "Position({})".format(str(self._seq))

    @property
    def visit_sequence(self):
        return self._seq

粒子類(lèi)

最終粒子類(lèi)除了包含一個(gè)速度實(shí)例和一個(gè)位置實(shí)例以外，還需要保存?zhèn)€體最佳位置和鄰域最佳位置：

# --------------------------------
# 粒子類(lèi)
# --------------------------------
class Particle(object):
    def __init__(self, position=None, velocity=None):
        if position is None:
            self.pos = Position()
        else:
            self.pos = position  # 當(dāng)前位置脏里，一個(gè)Position實(shí)例
        if velocity is None:
            self.vel = Velocity()
        else:
            self.vel = velocity  # 當(dāng)前速度她我，一個(gè)Velocity實(shí)例
        self.fitness = 0.0  # 當(dāng)前位置對(duì)應(yīng)的適應(yīng)度
        self.pbest_pos = None  # 個(gè)體歷史最佳位置，Position實(shí)例
        self.pbest_fitness = float('Inf')  # 個(gè)體歷史最佳適應(yīng)度
        self.gbest_pos = None  # 鄰域最佳位置，Position實(shí)例
        self.gbest_fitness = float('Inf')  # 鄰域最佳適應(yīng)度
        self._dimension = utilities.problem_dimension  # 問(wèn)題維度

    def __repr__(self):
        return "Particle:\n\tPosition:({})\n\tVelocity({})\n\tFitness: {}".format(str(self.pos.visit_sequence),
                                                                                  str(self.vel.exchange_list),
                                                                                  self.fitness)

    def initialize_pos(self) -> None:
        """
        初始化粒子位置
        :return:
        """
        perm = [i for i in range(2, self._dimension + 1)]
        random.shuffle(perm)
        self.pos = Position(perm)

    def __update_velocity(self, omega: float, c1: float, c2: float) -> None:
        """
        根據(jù)gbest_pos和pbest_pos更新速度
        :return:
        """
        inertia = omega * (self.pbest_pos - self.pos)
        individual_experience = (c1 * random.random()) * (self.pbest_pos - self.pos)
        social_experience = (c2 * random.random()) * (self.gbest_pos - self.pos)
        self.vel = inertia + individual_experience + social_experience

    def update_pos(self, omega: float, c1: float, c2: float):
        """
        根據(jù)速度更新粒子的位置
        :param omega:
        :param c1:
        :param c2:
        :return:
        """
        self.__update_velocity(omega, c1, c2)
        self.pos = self.pos + self.vel

算法性能測(cè)試

超參數(shù)

作為簡(jiǎn)單測(cè)試番舆，并沒(méi)有對(duì)超參數(shù)進(jìn)行特別調(diào)優(yōu)酝碳，按照經(jīng)驗(yàn)選取超參數(shù)如下：

超參數(shù)	解釋	取值
popsize	種群規(guī)模	100
	初始權(quán)重	0.9
	最終權(quán)重	0.4
	加速度常數(shù)	0.4
	加速度常數(shù)	0.4
	迭代步數(shù)	500

測(cè)試結(jié)果

這里我選擇了4個(gè)不同點(diǎn)數(shù)的問(wèn)題進(jìn)行測(cè)試，對(duì)每個(gè)數(shù)據(jù)集恨狈，運(yùn)行5次算法疏哗，下表中列出了最佳值和平均值，計(jì)算gap時(shí)使用的是5次平均結(jié)果：

結(jié)果討論

在所有的計(jì)算中拴事，算法都已經(jīng)達(dá)到了收斂沃斤，對(duì)于A-32-k5數(shù)據(jù)集的一次計(jì)算中的迭代過(guò)程如下：

6-example_result_iteration_A32k5

對(duì)應(yīng)的路徑圖如下：

7-example_result_routes_A32k5

可以看到，即使對(duì)于這樣一個(gè)節(jié)點(diǎn)數(shù)比較少的問(wèn)題刃宵，從圖像上看得到的路徑也和最有路徑相去甚遠(yuǎn)衡瓶，可以看到不少的路徑交叉出現(xiàn)，這也是因?yàn)槲覀儧](méi)有在算法中加入opt這樣的local search機(jī)制牲证。

總結(jié)

• 整數(shù)編碼的PSO提供了一套對(duì)速度和位置以及其相關(guān)運(yùn)算的定義哮针，拓展了PSO的可用范圍，看著還是比較有意思的
• 雖然編碼方式比較簡(jiǎn)單坦袍，但是由于定義了一整套的相關(guān)運(yùn)算十厢，其實(shí)現(xiàn)還是相對(duì)復(fù)雜的，而且換位減的時(shí)間復(fù)雜度也比較高捂齐，從效率上并不是非常好的選擇
• 僅從編碼方式看蛮放，也存在一定的問(wèn)題，例如說(shuō)[3,2,1,4]和[4,1,2,3]奠宜，雖然在定義上是兩個(gè)不同的位置包颁，但是實(shí)際上代表的路徑的總距離是相同的(symmetric edge的情況下)；這可能會(huì)讓解在兩個(gè)局部最優(yōu)之間擺動(dòng)压真，盡管這兩個(gè)局部最優(yōu)實(shí)際上是同一回事
• 從結(jié)果上看娩嚼，總體上整數(shù)編碼的PSO在不添加額外搜索機(jī)制的情況下，只能說(shuō)可以用于求解滴肿，但是其相對(duì)于最優(yōu)結(jié)果的gap是較大的岳悟，也就是說(shuō)單獨(dú)這套方法的實(shí)用性并不高，甚至比不上一些簡(jiǎn)單的啟發(fā)式方法