基于漢明距離與免疫思想的粒子群算法

叢培強，李 梁，陳亞茹

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

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

1 粒子群算法

1.1 標(biāo)準(zhǔn)粒子群算法

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

步驟1初始化粒子群參數(shù)。設(shè)種群規(guī)模為m，即定義m個粒子，為每個粒子初始化相應(yīng)位置zid(t)={zi1,zi2,…,zim}和速度vid(t)={vi1,vi2,…,vin}，并計算適應(yīng)度。其中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表示慣性權(quán)重；η1、η2為加速系數(shù)；rand()為[0,1]范圍的隨機數(shù)。

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

1.2 漢明距離

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

在TSP問題中，用1維數(shù)組表示每個可行解，不同解數(shù)組之間長度相同，數(shù)組內(nèi)序號排列順序不同。如存在8個城市的TSP問題，設(shè)t時刻有2個可行解數(shù)組：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個解序列長度相同，雖然解中城市序列不同，但是當(dāng)2個解數(shù)組歸一到同一城市起點時，容易發(fā)現(xiàn)這2個解序列代表同一城市路徑。因此，運用漢明距離概念求解TSP問題時，需要對每個粒子的解進(jìn)行預(yù)處理，即調(diào)整每個解的城市序列，將所有解序列的起始城市節(jié)點歸一為相同節(jié)點后再計算漢明距離。

2 免疫思想

2.1 算法思想

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

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

2.2 相關(guān)定義

2.2.1親和度

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

(1)

2.2.2濃度

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

2.2.3選擇概率

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

(2)

(3)

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

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

0

(4)

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

2.2.4免疫疫苗

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

2.2.5免疫疫苗接種

免疫疫苗接種即按照一定比例選取適應(yīng)度小的n個抗體，使用免疫疫苗對其進(jì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é)點做相應(yīng)變換，保持原城市節(jié)點總數(shù)不變。

}

}

3 改進(jìn)型粒子群算法

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

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

圖1 算法流程

步驟2初始化粒子群相關(guān)參數(shù)，即初始化粒子的速度與位置。

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果與分析

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

采用基于漢明粒子群算法(HPSO)、基于漢明距離與免疫思想的粒子群算法(IHPSO)以及文獻(xiàn)[15]中自適應(yīng)離散粒子群算法(SADPSO)，在測試集上進(jìn)行200次迭代實驗，對比實驗結(jié)果驗證本算法的性能?；谏鲜?種方法在以下數(shù)據(jù)集上進(jìn)行的實驗結(jié)果如表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)解表示相應(yīng)類別TSP問題的真實情況下的最優(yōu)路徑長度。計算最優(yōu)解與計算平均值為表中各算法在數(shù)據(jù)集上運行30次后的最短路徑與平均路徑長度。在不同數(shù)據(jù)集使用HPSO、IHPSO與SADPSO算法，發(fā)現(xiàn)本文提出的IHPSO算法的最優(yōu)解更接近真實最優(yōu)解，并且標(biāo)準(zhǔn)差更小，平均值更接近最優(yōu)值。說明本文方法能較好地求解TSP問題，計算出的結(jié)果較平穩(wěn)，波動小。由表1中數(shù)據(jù)可得，本文提出的對策IHPSO算法明顯優(yōu)于HPSO算法與SADPSO算法。

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

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

圖2 IHPSO與AIA在Eil51測試數(shù)據(jù)上的收斂過程

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

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

5 結(jié)束語

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