叢培強，李 梁，陳亞茹

(重慶理工大學 計算機科學與工程學院， 重慶 400054)

粒子群算法(particle swarm optimization,PSO)是Kennedy Eberhart受鳥群覓食啟發(fā)提出的一種并行群體智能算法[1]。該算法是基于種群的搜索算法，模擬鳥群的社會行為，可以解決多峰值、多目標、非線性問題，已廣泛應用于函數優(yōu)化、模糊控制等多個領域[2-5]。粒子群算法原理簡單，易于實現(xiàn)，但也存在諸多缺點，如易陷入局部最優(yōu)解、后期收斂速度慢、易早熟等。針對上述缺點，許多學者提出改進措施。文獻[6]中提出一種自適應小生鏡粒子群優(yōu)化算法，雖然解決了粒子群早收斂的缺點，但是存在易陷入局部最優(yōu)解問題。文獻[7]中提出了不需要參數的小生境粒子群算法，克服了標準粒子群算法在搜索后期易陷入局部最優(yōu)解等缺點。文獻[8]中提出粒子群動能的概念，解決了參數選擇的問題。文獻[9]中提出一種新的種群生成策略，通過遍歷種群中個體來選取適應值最優(yōu)的數值作為種子，然后將粒子群分為若干個相互獨立的種群。文獻[10]中提出改變粒子群慣性權重的定義方式，采用隨機權重和異步變化策略，提高了搜索速度和精度。以上方案雖然解決了粒子群算法的易早熟、后期收斂速度慢等問題，但是由于無法表示粒子位置與速度參數，不適合求解離散問題。針對以上問題，本文提出一種基于漢明距離與免疫思想的改進粒子群算法(IHPSO)，通過引入漢明距離、免疫疫苗以及免疫選擇等免疫思想來提高收斂精度。

1 粒子群算法

1.1 標準粒子群算法

粒子群算法(PSO)是一種基于群體的全局優(yōu)化算法。在粒子群算法中，每個粒子代表原始問題的一種可行解，群體中每個粒子都有相應的位置與速度。粒子群算法步驟如下：

步驟1初始化粒子群參數。設種群規(guī)模為m，即定義m個粒子，為每個粒子初始化相應位置zid(t)={zi1,zi2,…,zim}和速度vid(t)={vi1,vi2,…,vin}，并計算適應度。其中zid(t)和vid(t)分別表示第t代第i個粒子的位置和速度。

步驟2在解空間中粒子持續(xù)更新位置與速度信息搜索新的解。每一次迭代中的粒子更新條件是歷代中該粒子本身搜索到的最優(yōu)位置pid和整個粒子群歷代搜索到的最優(yōu)位置pgd。

步驟3計算vid(t+1)和zid(t+1)的速度更新公式。

vid(t+1)=wvid(t)+η1rand()[pid-zid(t)]+

η2rand()[pgd-zid(t)]

zid(t+1)=zid(t)+vid(t+1)

其中：vid(t+1)表示第t+1代中第i個粒子在第d維的速度；w表示慣性權重；η1、η2為加速系數；rand()為[0,1]范圍的隨機數。

步驟4尋找到最優(yōu)解或達到最大迭代次數時，算法結束。

1.2 漢明距離

漢明距離是一種距離的度量方式。若存在2個等長字符串，其相應位置上不同字符的個數即漢明距離。例如，2個二進制字符串a=[1,3,5,7,9]與b=[2,3,5,6,9]，則a與b間的漢明距離為3。漢明距離已實際應用。解決了眾多問題，如Rai等[10]將支持向量機和漢明距離相結合運用于虹膜識別系統(tǒng)，得到較高的識別率；Osaba等[11]引入漢明距離的概念，利用蝙蝠算法求解 TSP 時改進了該算法中對蝙蝠速度的定義。

在TSP問題中，用1維數組表示每個可行解，不同解數組之間長度相同，數組內序號排列順序不同。如存在8個城市的TSP問題，設t時刻有2個可行解數組：xt1=[2,6,4,3,1,5,7,8],xt2=[1,6,4,7,3,5,2,8],則xt1與xt2之間的漢明距離為4，記為HMD (xt1,xt2)=4。用這種城市序列表示解的方式會存在循環(huán)閉合回路，不同解序列可能會表示同一個解。如路徑[2,4,3,6,1,7,8,5],[8,5,2,4,3,6,1,7]，這2個解序列長度相同，雖然解中城市序列不同，但是當2個解數組歸一到同一城市起點時，容易發(fā)現(xiàn)這2個解序列代表同一城市路徑。因此，運用漢明距離概念求解TSP問題時，需要對每個粒子的解進行預處理，即調整每個解的城市序列，將所有解序列的起始城市節(jié)點歸一為相同節(jié)點后再計算漢明距離。

2 免疫思想

2.1 算法思想

人工免疫算法(AIA)模擬生物免疫系統(tǒng)中免疫進化機理進行抗原識別和抗體繁殖過程，促進高親和度抗體，抑制高濃度抗體，保持抗體多樣性，是一種計算最優(yōu)解的智能優(yōu)化算法[12]?？乖碓紗栴}，即目標函數和約束條件，抗體代表原始問題的可行解。

抗體的親和度表示抗體與抗原間的匹配程度，即該抗體表示的可行解接近最優(yōu)解的程度。親和度越大則抗體越有可能是最優(yōu)解?？贵w的濃度表示抗體間的相似程度，濃度越大則抗體間表示的可行解越相似。遺傳的下一代應盡量保持高親和度、低濃度。保持高親和度能使求得的可行解盡快地接近最優(yōu)解，提高收斂速度。低濃度能增加解的分散性，提高解的多樣性,防止陷入局部最優(yōu)解，提高算法全局搜索能力。另外，粒子群算法引入生物免疫系統(tǒng)的免疫記憶細胞、免疫疫苗、免疫選擇等機理。記憶細胞為親和度較大的抗體組成的抗體群，免疫疫苗為抗體中優(yōu)秀的基因。在TSP問題中，免疫疫苗為最優(yōu)路徑中相鄰的幾個城市節(jié)點。

2.2 相關定義

2.2.1親和度

親和度表示抗體與抗原的相似程度，親和度越大表示當前粒子越接近最優(yōu)解。親和度記為affinity，計算公式如下：

(1)

2.2.2濃度

濃度表示抗體間的相似程度，間接表示種群的多樣性，濃度越大則種群多樣性越小。本文采用區(qū)間法表示抗體的濃度。設存在n個抗體，每個抗體的親和度為affinity1、affinity2、…、affinityn，將這些值按由大到小順序排列，等分為k個區(qū)間[affinity1,affinityi]、[affinityi+1,affinityj]、…、[affinitym,affinityn]，記為L1、L2、L3、…、Lk。統(tǒng)計每個區(qū)間的適應度之和sum(m)，m表示第m個區(qū)間，則第m個區(qū)間內的抗體濃度為sum(m)/k。定義某個區(qū)間的濃度為D(Lk)，每個抗體的濃度定義為individuali。由此，每個區(qū)間內的抗體濃度均相同，促使某些濃度太小但有很大潛力的抗體可以遺傳到下一代，從而保證群體多樣性。

2.2.3選擇概率

抗體在進化過程中，希望親和度高但密度小的抗體被促進，親和度小但密度大的抗體被抑制,因此，基于聯(lián)合親和度和密度的概率構建如下：

(2)

(3)

聯(lián)合親和度與濃度的統(tǒng)一選擇概率P為：

Pi=?Pa(i)+(1-?)Pb(i), ?>0

0

(4)

由式(4)可知：選擇概率統(tǒng)一考慮親和度與密度，由?調節(jié)親和度與密度對最終抗體選擇概率的影響程度。?越大，則抗體親和度對抗體選擇概率的影響程度越大，反之，則密度對抗體選擇概率的影響程度越大。

2.2.4免疫疫苗

免疫疫苗指抗體中一段優(yōu)秀的基因，很大程度上會存在于最優(yōu)解中的部分解中。免疫疫苗如果能代代遺傳則能大大提高粒子群的收斂速度。對于TSP問題，多條最短距離中很大程度會包含相同的相鄰城市節(jié)點，這是TSP問題本身具有的特征[13]，這些相同的相鄰城市節(jié)點即免疫疫苗。若存在2個最優(yōu)抗體都對應最優(yōu)解，則免疫疫苗的求解方式是求2個最優(yōu)抗體的交集。鄒鵬等[14]證明了全局最優(yōu)解包含局部最優(yōu)解的80%。因此，本文引入免疫疫苗能加快算法的收斂速度。

2.2.5免疫疫苗接種

免疫疫苗接種即按照一定比例選取適應度小的n個抗體，使用免疫疫苗對其進行更新操作。以TSP問題為例，更新過程如下：

若存在免疫疫苗V及需要接種的抗體A，疫苗長度為|V|，抗體A長度為|A|,s為V的第1個城市，e為V的最后1個城市。

i=1

j=i+|V|-1

while (i<|A|-|V|+1)

{

if (A(i)==s&&A(j)==e)

{

將A(i)～A(j)的城市節(jié)點替換為免疫疫苗中的城市節(jié)點，A(i)～A(j)外的城市節(jié)點做相應變換，保持原城市節(jié)點總數不變。

}

}

3 改進型粒子群算法

基于漢明距離與免疫思想的粒子群算法(IHPSO)在更新速度與距離時引入漢明距離的概念，并引入免疫疫苗、抗體選擇等概念，加快了粒子的收斂速度，提高了收斂精度。算法流程如圖1所示。

步驟1初始化城市間距矩陣。即在2維空間中設置每個城市坐標，計算城市間距離。

圖1 算法流程

步驟2初始化粒子群相關參數，即初始化粒子的速度與位置。

步驟3根據式(1)計算每個抗體的親和度，并在此基礎上計算局部最優(yōu)解pbest與全局最優(yōu)解Gbest。

步驟4判斷是否滿足迭代終止條件，如果滿足則輸出結果；否則繼續(xù)執(zhí)行。

步驟5生成免疫記憶細胞。即篩選所有抗體，選擇親和度較大的n個抗體組成先進抗體群作為免疫細胞，根據具體問題人為確定免疫細胞包括抗體的數量。

步驟6生成免疫疫苗。免疫疫苗為問題本身具有的天然特征，任選2個最優(yōu)抗體進行相交操作，將交集單獨存儲作為免疫疫苗。

步驟7計算每個粒子與最優(yōu)粒子的漢明距離，并更新粒子的速度與位置。這種更新速度與位置的方法不同于傳統(tǒng)粒子群算法或改進算法，該方法不涉及慣性權重、隨機因子等，避免了調參過程。

步驟8步驟7對粒子進行更新操作，產生m個新的抗體，再從免疫細胞中選取q個抗體組成新的抗體群。

步驟9根據式(4)計算每個抗體的選擇概率，根據選擇概率大小選出x個抗體組成接種抗體群，x由人為指定。

步驟10免疫疫苗接種。按照一定比例，對親和度較低的抗體進行疫苗接種。計算接種后的抗體適應度，若該適應度小于接種前抗體的適應度值，則不對該抗體進行接種操作。

步驟11轉至步驟4，繼續(xù)執(zhí)行。

4 實驗結果與分析

選取TSPLIB測試庫中一些數據實例作為測試數據集，在處理器為Intel Core i5-5200U 2.2 GHz、內存為8G的計算機上使用Matlab進行仿真實驗，驗證本算法的可行性。

采用基于漢明粒子群算法(HPSO)、基于漢明距離與免疫思想的粒子群算法(IHPSO)以及文獻[15]中自適應離散粒子群算法(SADPSO)，在測試集上進行200次迭代實驗，對比實驗結果驗證本算法的性能。基于上述3種方法在以下數據集上進行的實驗結果如表1所示，其中：A1代表HPSO算法；A2代表SADPSO算法；A3代表IHPSO算法。TSP問題中Bumal14簡稱問題1；Oliver30簡稱問題2；Eil51簡稱問題3；St70簡稱問題4； Rat99簡稱問題5；Chl30簡稱問題6；Chl50簡稱問題7。

表1中,實際最優(yōu)解表示相應類別TSP問題的真實情況下的最優(yōu)路徑長度。計算最優(yōu)解與計算平均值為表中各算法在數據集上運行30次后的最短路徑與平均路徑長度。在不同數據集使用HPSO、IHPSO與SADPSO算法，發(fā)現(xiàn)本文提出的IHPSO算法的最優(yōu)解更接近真實最優(yōu)解，并且標準差更小，平均值更接近最優(yōu)值。說明本文方法能較好地求解TSP問題，計算出的結果較平穩(wěn)，波動小。由表1中數據可得，本文提出的對策IHPSO算法明顯優(yōu)于HPSO算法與SADPSO算法。

驗證本文算法迭代時的收斂過程，并對比IHPSO與人工免疫算法(AIA)在Eil51測試數據上的收斂過程，如圖2所示。IHPSO算法在Eil51數據集上的路徑優(yōu)化如圖3所示。

表1 HPSO、SADPSO、IHPSO算法求解TSP問題的結果對比

圖2 IHPSO與AIA在Eil51測試數據上的收斂過程

由圖2可知：IHPSO算法前100代收斂速度較快，由于前100代中每個粒子到最優(yōu)粒子的漢明距離較大，因此粒子速度大，位置更新的幅度大，收斂速度較快，約300代時算法獲得最優(yōu)解；而AIA受選擇、變異的影響，增大了粒子下一代遺傳的不確定性，導致收斂速度變慢，在500代左右才收斂到最優(yōu)解。IHPSO加入了免疫思想，在算法的收斂精度與收斂速度方面都有較大提高。

圖3 IHPSO在Eil51數據集上的規(guī)劃路徑

5 結束語

本文提出的算法引入漢明距離，改變了粒子位置和速度的更新方式，彌補了傳統(tǒng)粒子群算法不能求解離散問題的不足，并引入免疫疫苗、免疫選擇等免疫思想，加快粒子的收斂速度，得到了全局最優(yōu)解。算法實驗分2部分，第一部分比較了IHPSO算法與HPSO、SADPSO在TSPLIB測試集上的實驗效果，發(fā)現(xiàn)IHPSO算法能獲得最優(yōu)解，并且計算結果浮動范圍相比其他2種算法小。第二部分驗證IHPSO算法的收斂速度，對比AIA算法在Eil51測試集上的實驗效果，發(fā)現(xiàn)IHPSO算法較AIA算法提前100代得到最優(yōu)解，表明 IHPSO算法收斂速度較快。