基于雙種群的混合免疫動態(tài)優(yōu)化算法

張衛(wèi)正，張夢華，張偉偉，金保華，吳懷廣，王華，李國慶

(鄭州輕工業(yè)學院 計算機與通信工程學院，河南 鄭州 450000)

0 引 言

優(yōu)化問題在現(xiàn)實世界中廣泛存在于金融、工程、學術等各個領域，吸引了大批研究人員。演化機制和群智能算法憑借自適應、自組織、魯棒性和可并行性等優(yōu)點，成為求解優(yōu)化問題的主力軍[1]。在實際應用中，優(yōu)化問題往往具有動態(tài)特性，其決策變量、目標函數(shù)、約束條件等都有可能隨環(huán)境的變化而變化。當環(huán)境變化時，最直接的做法是將變化后的問題當做一個新的問題進行求解，但是，群智能優(yōu)化算法中的搜索種群在環(huán)境變化前往往已經(jīng)收斂于局部最優(yōu)了，當重新進行搜索時，因種群多樣性缺失，容易造成早熟收斂和探索性不足等問題，而重新對種群進行多樣性分布和再收斂需要消耗很多計算資源。更重要的是，環(huán)境變化前后優(yōu)化問題的適應度地貌(fitness landscape)可能具有一定的相似性，對其相似性的探索可以幫助及時高效地定位最優(yōu)解，而不必浪費計算資源進行整個搜索域的探索。

近年來，對動態(tài)優(yōu)化問題的研究掀起了一個熱潮，取得了大量的研究成果。這些研究主要可以歸為5個方面[2]：(1)當發(fā)生變化時，增加種群的多樣性；(2)在搜索過程中持續(xù)保持種群的多樣性；(3)基于預測的方法；(4)自適應的方法；(5)多種群的方法。種群多樣性缺失的問題是群智能算法在應對環(huán)境變化時的一個很大挑戰(zhàn)，因此，現(xiàn)有的大多數(shù)研究或多或少與多樣性控制有關?，F(xiàn)有的研究大都不只局限于其中一個方面，而是結合多個方面設計算法，提高性能。

在自然界中，生物免疫系統(tǒng)能夠保護機體對抗隨時入侵抗原的攻擊。為了實現(xiàn)這種功能，生物免疫系統(tǒng)裝備了很多優(yōu)良的特性，比如“自己”或“非己”的識別，自組織，自適應，分布式，記憶，忍耐性和魯棒性，等等[3]。這些優(yōu)良特性使生物免疫系統(tǒng)在求解動態(tài)優(yōu)化問題時具有其他啟發(fā)式算法所不具備的優(yōu)勢，從而引起了國內外學者的關注[4]。A.Sim?es等[5]提出了一種與免疫系統(tǒng)相結合的遺傳算法(ISGA);YANG S X[6]在ISGA基礎上進一步提出了ISGAa算法;動態(tài)dopt-aiNet[7]利用改進的黃金分割法加強局部搜索，引入了2種新的超變異機制和cell line壓縮機制，消除冗余和保持種群的多樣性。實驗驗證了dopt-aiNet在解決動態(tài)優(yōu)化問題時的有效性。F.O.de Franca[8]進一步對dop-aiNet進行適應性改進，并應用在6個具有挑戰(zhàn)性的基準測試函數(shù)上。K.Trojanowski等[9]測試了5種以免疫機制為基礎的算法在解決動態(tài)優(yōu)化問題時的表現(xiàn)，它們分別是：(1)人工免疫迭代算法(AIIA)[10]；(2)B細胞算法(BCA)[11]；(3)克隆選擇算法(CLONALG)[12]；(4)opt-aiNet算法[13]；(5)簡單人工免疫系統(tǒng)(SAIS)[14]。分別采用7種變異操作算子應用于這些算法,分析它們的性能。V.S.Aragon[15]根據(jù)T細胞反應機制提出的動態(tài)T細胞模型(DTC)，用來解決動態(tài)優(yōu)化問題。它模擬了T細胞的不同形態(tài),即VC，CD4，CD8和MC。然后分別對不同的種群應用Gray編碼和實數(shù)編碼實現(xiàn)全局和局部搜索。LI Z J等[4]將體細胞高突變和記憶B細胞克隆選擇的思想轉化為ITDGA的免疫算子，以適應動態(tài)環(huán)境。針對0～1動態(tài)優(yōu)化問題；LI L L等[16]提出了一種基于雙概率的原對偶遺傳算法(DPPDGA)，并引入了亞等位基因和優(yōu)等位基因，以保持較好的多樣性，但它們在所有位點上的重復計算帶來了較高的計算成本。

在前述研究成果的基礎上，本文提出了一種新的基于雙種群的混合免疫動態(tài)優(yōu)化算法BPAIS，通過種群多樣性保持、平衡全局性搜索和局部性搜索能力，提升算法的性能，最后在測試函數(shù)上進行仿真實驗,并與其他現(xiàn)有算法進行比較分析。

1 相關基礎理論

1.1 動態(tài)優(yōu)化問題

不失一般性，動態(tài)環(huán)境下的優(yōu)化問題可以描述為

最優(yōu)化f(X，t)=f(x1，x2，…，xq，t),

(1)

最優(yōu)化問題可以是最小化問題，也可以是最大化問題。

1.2 生物免疫系統(tǒng)

生物免疫系統(tǒng)主要功能是保護機體不受外來病原體等“非己”入侵，為了描述方便，這些“非己”在本文中一律被稱為“抗原”(antigen)。為了免受抗原入侵，免疫系統(tǒng)進化出了多層保護機制，如圖1所示。

圖1 生物免疫系統(tǒng)的多層防御機制Fig.1 Multi-layer defense mechanism of biological immune system

首先是物理層的阻隔，包括皮膚、黏膜等；其次是生化層，機體的分泌物，如唾液、胃酸等可以消滅大部分的抗原；最后是免疫系統(tǒng)的主要部分，分為固有免疫系統(tǒng)和適應性免疫系統(tǒng)。固有免疫系統(tǒng)又叫做非特異性免疫系統(tǒng)，由補體、噬菌細胞等固有免疫細胞組成，是機體先天性就具備的識別和消滅抗原的能力。固有免疫細胞遍布全身，隨血流移動，當遭遇抗原，一方面固有免疫細胞可以通過固有免疫反應消滅一部分抗原，另一方面它會激活T淋巴細胞，促使適應性免疫反應。適應性免疫系統(tǒng)是特異性免疫反應系統(tǒng)，主要由T淋巴細胞和B淋巴細胞組成。B淋巴細胞表面存在特異抗原的識別受體，稱為抗體(antibody)。每一種B淋巴細胞只能分泌一種抗體。抗體能夠與抗原相結合，其結合強度取決于抗體和抗原的模式匹配程度，又稱為親和度(affinity)。特定的抗體對不同的抗原具有不同的親和度，當親和度足夠高時，抗體可以綁定抗原，并通過調動免疫機制將其消滅。適應性免疫系統(tǒng)對抗原的識別具有專一性，可以識別并消滅固有免疫系統(tǒng)不能消滅的抗原?？寺∵x擇學說[3]是Burnet根據(jù)B淋巴細胞適應性免疫反應的機制而提出的最具有代表性的免疫學說之一。其基本思想是只有含有與抗原親和度高的抗體(B淋巴細胞)得到增殖，而不能識別抗原的則不被選擇?？贵w數(shù)量的增加通過B淋巴細胞自身的克隆?？寺〉募毎偻ㄟ^超變異產(chǎn)生新的抗體，通過不斷選擇，克隆，超變異最終產(chǎn)生與抗原最佳配體，將抗原消除。這些最佳配體還將被保存為記憶細胞，當再次遭遇相同或者相似抗原時，可以及時高效地消滅抗原。

1.3 人工免疫系統(tǒng)

人工免疫系統(tǒng)(artificial immune system)通過提取生物免疫隱喻，根據(jù)免疫細胞的行為和免疫反應的機制構造算法，尋找問題的最優(yōu)解。在求解優(yōu)化問題時，最具有代表性的人工免疫算法是基于克隆選擇學說的克隆選擇算法(clonal selection algorithm，CSA)。L.N.De Castro等[6]最早提出了克隆選擇算法CLONALG，并應用于字母識別、多模函數(shù)優(yōu)化、組合優(yōu)化和TSP問題等。隨后，研究學者根據(jù)不同的需求，陸續(xù)提出了不同的克隆選擇算法。

在克隆選擇算法中，需要解決的問題被映射為抗原，問題的解被映射為抗體?？寺∵x擇算法主要涉及的免疫機制為選擇、克隆和變異。免疫克隆選擇算法的主要流程如算法1所示。

算法1 克隆選擇算法

Step1：初始化，產(chǎn)生初始抗體種群，k=1

Step2：評價，計算抗體-抗原親合力，即抗體的適應度值

Step3：選擇m個與抗原親和度高的抗體

Step4：循環(huán)條件判斷。如果循環(huán)條件滿足則算法繼續(xù)，否則結束，輸出最優(yōu)抗體及其適應度值

Step5：對所選擇的抗體進行克隆操作

Step6：對克隆個體實施變異操作

Step7：計算新產(chǎn)生個體的適應度值

Step8：選擇適應度值高的個體

Step9：k=k+1，返回Step4

2 雙種群混合免疫動態(tài)優(yōu)化算法

2.1 種群初始化和種群劃分

初始種群由在可行域中隨機產(chǎn)生的,呈均勻分布的個體所組成，其產(chǎn)生方式為

Xi，j=LBj+α×(UBj-LBj)，

(2)

式中：i=1，…，Np，Np為種群的大小；j=1，…，D，D為決策變量的維數(shù)；UB和LB分別為可行域的上下邊界；α為在[0，1]中均勻分布的隨機數(shù)。

對產(chǎn)生的初始種群根據(jù)目標函數(shù)評估適應度值，并根據(jù)適應度值的高低進行排序，選擇p%的較優(yōu)的個體作為自適應免疫種群AB={ab1，…，abNb}，剩余的被當作固有免疫種群IAB={Iab1，…，IabNa}，Na+Nb=Np。這樣，根據(jù)適應度值，種群被劃分為固有種群和自適應種群。

2.2 固有免疫反應

在生物學上，固有免疫反應是一個非特異性反應過程。固有免疫反應的搜索方式被定義為

(3)

其中，i=1，…，Na，j=1，…，D，N(0，1)為均值0，方差1的高斯隨機數(shù)，randIab為在可行域內隨機產(chǎn)生的隨機數(shù)。

固有免疫種群負責全局檢測抗原，并保持種群的多樣性。因此，采用高斯隨機數(shù)增加擾動，并通過引入隨機數(shù)使其保持多樣性分布。

2.3 適應性免疫優(yōu)化反應

與固有免疫反應不同，適應性免疫反應是特異性免疫反應?；诳寺∵x擇學說，抗體要經(jīng)歷克隆、超變異和選擇的過程產(chǎn)生新的個體。在本文中，算法混合使用了差分進化算子，具體實施過程包括克隆、變異、交叉和選擇。

克隆(clone)：對每一個適應性免疫種群中的個體，產(chǎn)生Ncl個克隆，其中Ncl為克隆的個數(shù)。

變異(mutation)：對每一個克隆，引入結合差分進化策略中的DE/best/2[17]算子，進行如下變異過程：

Vi=abbest+F×(abr1-abr2)+

F×(abr3-abr4)，

(4)

其中，abbest為當前種群中適應度值最優(yōu)的個體，r1，r2，r3，r4為隨機產(chǎn)生的在[1，Nb]內的整數(shù)，而且r1≠r2≠r3≠r4≠i，F(xiàn)為一個正的參數(shù)，控制著差分向量。

交叉(crossover)：

(5)

式中：j=1，…，D，D為維數(shù)；rand為(0，1)區(qū)間的隨機數(shù)；CR∈[0，1]，為交叉率；jrand∈[1，D]，為確保至少有一維發(fā)生變化而隨機選擇的維數(shù)。

選擇(selection)：

(6)

對新產(chǎn)生的試驗向量(trial vector)Ui進行適應度評估。如果它的適應度值優(yōu)于父代，則Ui被選擇，否則被丟棄。適應性免疫種群負責局部定位最優(yōu)值，利用差分進化算子加強算法的局部搜索能力。因為差分進化算子局部搜索能力較優(yōu)，種群在其作用下會很快收斂到局部最優(yōu)。這里，采用歐式距離計算種群中的個體與種群中最優(yōu)個體的距離，取平均值作為種群的半徑。如果種群的半徑小于預先給定的閾值δ，則認為適應性種群已經(jīng)收斂，將最優(yōu)個體保存在記憶集合中，刪除其他的個體，然后種群重新進行初始化。另外，在每一次迭代中，如果適應性免疫種群中的最優(yōu)個體與免疫集合中任意個體的距離小于δ，則適應性免疫種群將被刪除。

2.4 環(huán)境變化檢測

在每一次迭代時，種群中全局最優(yōu)的個體適應度值都要被重新評估，檢測是否與之前的一致。若不一致，則表明環(huán)境發(fā)生變化。如果環(huán)境發(fā)生變化被檢測到，合并固有種群和適應性種群，進行重新評估，并按照適應度值進行排序，再重新按照比例劃分為固有種群和適應性種群。另外，在變化時，記憶跟蹤機制將被啟動。

2.5 記憶跟蹤機制

記憶集合中存放的是變化前環(huán)境中已收斂的適應性種群的最優(yōu)個體。一般情況下，這些個體位于或接近適應度景觀的局部最優(yōu)點。環(huán)境變化會使優(yōu)化問題適應度景觀發(fā)生改變，進一步導致原本的最優(yōu)解發(fā)生改變。但變化后的環(huán)境往往與變化前的環(huán)境存在一定程度的相似相關性。變化前環(huán)境中的局部最優(yōu)解有可能是變化后環(huán)境的全局最優(yōu)解。對變化前環(huán)境的局部最優(yōu)的跟蹤被證明可以有效地提升求解的效率[2]。因此，本文提出了一種記憶跟蹤機制跟蹤局部最優(yōu)，提高尋優(yōu)的效率。當環(huán)境變化被檢測到，記憶集合中的個體的適應度將被重新評估，然后利用局部搜索算法對每一個記憶集合中的個體進行局部尋優(yōu)。局部搜索算法有很多，如爬山法，模擬退火法[18]等。本文借鑒單純直接搜索算法[19]進行局部搜索，跟蹤局部最優(yōu)。

2.6 算法框架

本文提出了一種基于雙種群的免疫動態(tài)優(yōu)化算法，初始種群根據(jù)適應度被劃分為固有免疫種群和適應度免疫種群，固有免疫種群負責全局探索，保持種群多樣性，而適應性免疫種群則負責局部定位最優(yōu)解，該算法步驟描述如下。

算法2 BPAIS算法

Step1：初始化,隨機生成規(guī)模大小為Np的初始種群

Step2： 評價每一個個體的適應度值

Step3：種群劃分，根據(jù)適應度值將初始種群劃分為固有免疫種群和適應性免疫種群

Step4：環(huán)境變化檢測

Step5：If環(huán)境變化發(fā)生

重新初始化種群

種群劃分

重新評估記憶集合中個體的適應度值

關于氣氛感，現(xiàn)象學拋棄了一比一比對的傳統(tǒng)理性二分法，認為在客觀對象、內意識、時間，乃至身體后面，總牽扯、勾連與墊襯著一個暈圈一樣的背景場域，所以諸多物事背景中的淡暈、氤氳的氣氛，自然得到呈現(xiàn)與關注。沿著這種思路，當今德國美學家吉爾諾特·伯梅(1937～)，提出了“氣氛美學”觀念，言明氣氛是審美中感知者與感知對象互相對話融合的場域氛圍，且依賴身體性在場的方式，感受到這種氣氛?，F(xiàn)象學美學家茵伽登論述文學作品在語音、意義、圖式與意象四個復合層次之上，有統(tǒng)攝四者的“形而上質”，此“質”即是一種彌漫一切照亮一切的氛圍;恰如本雅明所謂環(huán)繞藝術作品的“靈韻”。

對記憶集合中的個體進行局部搜索

End If

Step6：適應性免疫優(yōu)化反應

Step7：If 免疫集合不為空

If適應性免疫種群中最優(yōu)值與免疫集合中任一個體的距離都小于δ

刪除適應性免疫種群

End If

End If

Step8：If 適應性免疫種群收斂

將最優(yōu)個體放入記憶集合

刪除適應性免疫種群

End If

Step9：If 適應性免疫種群為空

固有免疫反應

固有免疫種群和新產(chǎn)生的隨機個體一起構成初始種群

對初始種群進行適應度評估

種群劃分

Step10：循環(huán)條件判斷。如果終止條件滿足，則結束，否則，返回Step 4

3 仿真實驗

3.1 測試函數(shù)

3.1.1 STCG函數(shù)

STCG[9]測試函數(shù)定義了一個動態(tài)變化的適應度景觀f:X×t→R，其中，X=X1×X2,為可行解集，t為離散的時間。

將可行解集X分解成一系列不相交的子集Aij，即X=∪i∪jAij，對于每個子集Aij，定義了一個拋物面形狀的單峰函數(shù)fij，

fij(x1，x2)=

(8)

其中,Pij∈[0，pmax]，它控制適應度景觀中第ij個峰的高度，本文中pmax=100。如果pij(t)隨迭代而變化，將會獲得動態(tài)景觀：其峰值的高度可以周期性地或非周期性地改變。當模擬這些環(huán)境時，只有位于主對角線上(圖1)或棋盤上2條對角線上(圖2)的峰值高度才會發(fā)生變化。所有剩余峰的高度保持不變，而且它們的高度都小于變化峰的高度。

圖2 STCG主對角線上的峰發(fā)生變化

圖3 STCG 2條對角線上的峰發(fā)生變化

3.1.2 移動峰測試函數(shù)

移動峰測試函數(shù)是由Branke[20]提出的，針對動態(tài)最優(yōu)化問題的一個通用模型，是至今最為廣泛采用的測試函數(shù)集。它的適應性景觀由一系列峰組成，每一個峰由位置、高度、寬度和峰的形狀確定。一個D維的移動峰函數(shù)定義為

(9)

式中：Hi(t)和Wi(t)分別為t時刻第i個峰的高度和寬度；Xij(t)為第i個峰的第j維在t時刻的位置，一共有N個彼此相互獨立的峰通過最大化函數(shù)max結合，構造成移動峰函數(shù)。每一次發(fā)生變化，每一個峰的位置、高度和寬度的變化為

Hi(t)=Hi(t-1)+height_severityσh，

(10)

Wi(t)=Wi(t-1)+wight_severityσw，

(11)

Xi(t)=Xi(t-1)+vi(t)，

(12)

λvi(t-1))，

(13)

式中：σh和σw分別為均值0，方差1 的高斯隨機數(shù)；s為控制著峰變化的強度；r為在每一維選擇一個隨機數(shù)歸一化到s的向量；λ∈[0.0，1.0]，為控制著當前峰的位置與上一次環(huán)境中峰的位置的相關性。

通過調整對應參數(shù)的值，可以生成各種不同的移動峰測試函數(shù)。

3.2 實驗環(huán)境設置

3.2.1 測試方案

為了與其他算法進行公平比較，本文采用了以下2種環(huán)境測試方案。

測試方案1：如表1所示，采用STCG和MPB 2種測試函數(shù)。對于STCG問題，維度設定為2，“10×10”表示將搜索區(qū)劃分為100個方格，每一個格中有一個獨立的峰。c代表周期變化，nc代表非周期變化。

表1 STCG和MPB 2種測試函數(shù)的參數(shù)Tab.1 Parameters of STCG and MPB test functions

對于MPB問題，維數(shù)設定為5，維度設定了2種場景，分別有5個峰和50個峰，每一維的搜索區(qū)間為[0，100]，對于環(huán)境類型為1的情況，峰的高度變化區(qū)間為[30，70]，寬度為[0.0001，0.2]，變化強度為1。而對于環(huán)境類型為2的情況，其峰的高度變化區(qū)間為[30，70]，寬度為[1，12]，變化強度為1。

測試方案2：采用移動峰測試函數(shù)，峰的個數(shù)有6種情況，為{5，10，20，30，50，100}，變化強度s有4種情況，為{1，2，3，5}，環(huán)境關聯(lián)系數(shù)λ為0，即不相關。高度的變化強度設定為7，寬度的變化強度設定為1。

表2 移動峰測試函數(shù)的參數(shù)Tab.2 Parameters of moving peak test function

環(huán)境變化的間隔為5 000次適應度函數(shù)評估，一共變化100次，共計500 000次適應度值評估。每次實驗，算法都采用不同的隨機種子點開始，一共運行30次，取離線誤差的方差和均值。

3.2.2 評價標準

在對算法進行評價時，標準采用離線誤差oe，表示自上次環(huán)境變化以后評估的最佳個體與最優(yōu)值之間的平均偏差,定義為

(14)

簡而言之，每次評估解的適應度時，輔助變量值通過偏離實際評估的解最優(yōu)值更新，如果它比上次變化后的任何其他值都要好，或者因為上次變化而偏離了最佳解的最優(yōu)值，那么每次當景觀改變時，應該重置自上次變化以來最優(yōu)解的值。當實驗結束時，變量中的總和除以評估總數(shù)。

3.3 實驗設置

實驗分為2個部分。

(1)測試方案1與基于人工免疫的算法進行比較，參與比較的算法有：人工免疫迭代算法(AIIA)[10]；B細胞算法(BCA)[11]；克隆選擇算法(CLONALG)[12]；opt-aiNet算法[13]；簡單人工免疫系統(tǒng)(SAIS)[14]；動態(tài)T細胞模型(DTC)[15]。

(2)測試方案2與其他進化算法進行比較，參與比較的算法有：多量子群優(yōu)化算法mQSO(5，5q)[21]； 適應性多量子群優(yōu)化算法AmQSO[22]；帶電粒子群優(yōu)化算法的多重優(yōu)化mCPSO[21]；基于種群的螢火蟲算法SFA[23]；基于物種的粒子群優(yōu)化算法SPSO[24]；通過記憶增強動態(tài)優(yōu)化的基于物種的粒子群優(yōu)化算法MSPSO[25]。

種群個體數(shù)目Np設置為50，種群劃分比例p設置為10，克隆個數(shù)設置為1，距離閾值δ設置為1，F(xiàn)設置為0.7，CR設置為0.9。為公平比較，其余實驗參數(shù)均與其他相比較的算法保持一致。

3.3 結果和討論

3.3.1 BPAIS與基于免疫的算法實驗比較

實驗對比結果如表3所示，獨立運行50次測試方案1，選擇獲得的最優(yōu)值進行比較，其中參與比較的免疫算法的結果來自于文獻[9]中各種免疫算法與不同變異策略相結合的最好值。

表3 BPAIS與其他免疫算法在測試方案1中的 離線誤差最好值Tab.3 Best values of offline error obtained by BPAIS and other immune algorithms in test case 1

表3 描述了 BPAIS與其他免疫算法在測試方案1中的STCG和MPB 2種測試函數(shù)的比較結果。在STCG函數(shù)上，測試了周期性變化的10個峰，20個峰和非周期變化的12個峰，20個峰的情況，在MPB函數(shù)上，測試了5個峰和50個峰的情況。結果表明，在所有測試情況下，BPAIS的離線誤差最小，性能最好。這是因為參與比較的除DTC以外的基于免疫的算法并沒有針對動態(tài)變化的處理機制，只是在原本處理靜態(tài)問題的基礎上調整了算子(特別是超變異算子)的構造。當環(huán)境變化時，雖然超變異能在一定程度上增加種群的多樣性，但從另一方面又削弱了種群的收斂性。因此，這些基于免疫算法的求解效果很差。DTC算法從T淋巴細胞的免疫機制出發(fā)，將種群分為4個子種群，包括原始細胞，效用細胞，CD4的效用細胞，CD8的效用細胞和記憶細胞，通過激活機制轉換種群中細胞的不同狀態(tài)處理動態(tài)優(yōu)化問題。DTC算法的機制比較復雜，涉及的參數(shù)也比較多，各個種群搜索機制和激活機制也各不相同，導致算法中有很多低效搜索，而且算法留存的記憶并沒有得到高效再利用。雖然比之前的基于免疫的算法效果好，但結果還是不盡如人意。而本文提出的BPAIS通過種群的劃分，對不同的種群側重于不同的搜索機制，再加上記憶跟蹤機制的配合，得到搜索效果比其他免疫算法更好。

3.3.2 BPAIS與其他進化算法的實驗比較

為了進一步檢驗BPAIS算法的性能，采用移動峰函數(shù)進一步對算法進行了仿真和實驗，分析并與其他進化算法進行比較。實驗結果如表4～5所示，離線誤差以均值和標準差的形式展示，其中最好的值以下劃線顯示。

表4展示了測試方案2中移動峰函數(shù)峰的個數(shù)不同時算法的表現(xiàn)，可以看出，隨著峰個數(shù)的增加，大多數(shù)算法的離線誤差是先增后減的。這是因為當峰的數(shù)目較少時，峰個數(shù)的增加會加大種群陷入局部最優(yōu)的風險，從而增加算法尋優(yōu)的難度。而當峰個數(shù)較多時，算法雖然也容易陷入局部最優(yōu)，但是因為峰的密度較大，即使陷入后也很容易從峰值較低的峰跳到峰值較高的峰上，搜索結果反而會變好。從算法的對比分析可以看出，所提BPAIS算法要優(yōu)于mQSO(5，5q)，AmQSO，MSPSO，SFA，SPSO。而和MSPSO算法相比時，除了在峰個數(shù)為5和10時效果稍差，其余情況下，所提出的BPAIS算法尋優(yōu)結果都優(yōu)于算法MSPSO。

表5展示了測試方案2中移動峰函數(shù)的變化強度s不同時算法的結果。從結果可以看出，隨著變化強度s的增加，所有算法的性能都會變差。這是因為變化強度越大，環(huán)境變化的越劇烈，變化后的環(huán)境與變化前的環(huán)境差異也越大，算法搜索的難度也會不斷增加。從對比情況看，所提出的BPAIS算法優(yōu)于除MSPSO算法外的其他進化算法，而與MSPSO算法的結果在變化劇烈程度s為1，2，5時，所提BPAIS算法的搜索結果稍遜于MSPSO算法，而當s為3時，所提算法的精度略好于MSPSO算法?？傮w而言，BPAIS算法具有很強的競爭力。

表4 BPAIS和其他進化算法在測試方案2(移動峰函數(shù)峰的數(shù)目變化)中的離線誤差(均值和標準差)Tab.4 Offline errors(mean & std)of BPAIS and other evolutionary algorithms in test case 2 (MPB with number of peaks varying)

表5 BPAIS和其他進化算法在測試方案2(移動峰函數(shù)變化強度s改變)上的離線誤差(均值和標準差)Tab.5 Offline errors(mean & std)of BPAIS and other evolutionary algorithms in test case 2 (MPB with change severity s varying)

4 結 論

在傳統(tǒng)克隆選擇算法的基礎上，結合固有免疫反應、自適應免疫反應過程和記憶跟蹤機制，提出了一種基于雙種群的免疫動態(tài)優(yōu)化算法BPAIS。固有免疫反應用來保持種群的多樣性，適應性免疫反應用來提高算法的局部搜索能力，記憶跟蹤機制用來跟蹤局部最優(yōu)解。通過在移動峰測試函數(shù)和STCG測試函數(shù)中的仿真實驗，結果表明，BPAIS算法具有很好的動態(tài)優(yōu)化能力，能夠有效地跟蹤和定位全局最優(yōu)解，與其他算法相比，可以較好地解決早熟收斂和多樣性缺失的問題，顯示出很強的競爭力。