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

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

0 引 言

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

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

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

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

1 相關(guān)基礎(chǔ)理論

1.1 動(dòng)態(tài)優(yōu)化問(wèn)題

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

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

(1)

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

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

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

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

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

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

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

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

算法1 克隆選擇算法

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

Step2：評(píng)價(jià)，計(jì)算抗體-抗原親合力，即抗體的適應(yīng)度值

Step3：選擇m個(gè)與抗原親和度高的抗體

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

Step5：對(duì)所選擇的抗體進(jìn)行克隆操作

Step6：對(duì)克隆個(gè)體實(shí)施變異操作

Step7：計(jì)算新產(chǎn)生個(gè)體的適應(yīng)度值

Step8：選擇適應(yīng)度值高的個(gè)體

Step9：k=k+1，返回Step4

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

2.1 種群初始化和種群劃分

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

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

(2)

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

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

2.2 固有免疫反應(yīng)

在生物學(xué)上，固有免疫反應(yīng)是一個(gè)非特異性反應(yīng)過(guò)程。固有免疫反應(yīng)的搜索方式被定義為

(3)

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

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

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

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

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

變異(mutation)：對(duì)每一個(gè)克隆，引入結(jié)合差分進(jìn)化策略中的DE/best/2[17]算子，進(jìn)行如下變異過(guò)程：

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

F×(abr3-abr4)，

(4)

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

交叉(crossover)：

(5)

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

選擇(selection)：

(6)

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

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

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

2.5 記憶跟蹤機(jī)制

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

2.6 算法框架

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

算法2 BPAIS算法

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

Step2： 評(píng)價(jià)每一個(gè)個(gè)體的適應(yīng)度值

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

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

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

重新初始化種群

種群劃分

重新評(píng)估記憶集合中個(gè)體的適應(yīng)度值

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

對(duì)記憶集合中的個(gè)體進(jìn)行局部搜索

End If

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

Step7：If 免疫集合不為空

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

刪除適應(yīng)性免疫種群

End If

End If

Step8：If 適應(yīng)性免疫種群收斂

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

刪除適應(yīng)性免疫種群

End If

Step9：If 適應(yīng)性免疫種群為空

固有免疫反應(yīng)

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

對(duì)初始種群進(jìn)行適應(yīng)度評(píng)估

種群劃分

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

3 仿真實(shí)驗(yàn)

3.1 測(cè)試函數(shù)

3.1.1 STCG函數(shù)

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

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

fij(x1，x2)=

(8)

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

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

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

3.1.2 移動(dòng)峰測(cè)試函數(shù)

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

(9)

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

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 的高斯隨機(jī)數(shù)；s為控制著峰變化的強(qiáng)度；r為在每一維選擇一個(gè)隨機(jī)數(shù)歸一化到s的向量；λ∈[0.0，1.0]，為控制著當(dāng)前峰的位置與上一次環(huán)境中峰的位置的相關(guān)性。

通過(guò)調(diào)整對(duì)應(yīng)參數(shù)的值，可以生成各種不同的移動(dòng)峰測(cè)試函數(shù)。

3.2 實(shí)驗(yàn)環(huán)境設(shè)置

3.2.1 測(cè)試方案

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

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

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

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

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

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

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

3.2.2 評(píng)價(jià)標(biāo)準(zhǔn)

在對(duì)算法進(jìn)行評(píng)價(jià)時(shí)，標(biāo)準(zhǔn)采用離線誤差oe，表示自上次環(huán)境變化以后評(píng)估的最佳個(gè)體與最優(yōu)值之間的平均偏差,定義為

(14)

簡(jiǎn)而言之，每次評(píng)估解的適應(yīng)度時(shí)，輔助變量值通過(guò)偏離實(shí)際評(píng)估的解最優(yōu)值更新，如果它比上次變化后的任何其他值都要好，或者因?yàn)樯洗巫兓x了最佳解的最優(yōu)值，那么每次當(dāng)景觀改變時(shí)，應(yīng)該重置自上次變化以來(lái)最優(yōu)解的值。當(dāng)實(shí)驗(yàn)結(jié)束時(shí)，變量中的總和除以評(píng)估總數(shù)。

3.3 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)分為2個(gè)部分。

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

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

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

3.3 結(jié)果和討論

3.3.1 BPAIS與基于免疫的算法實(shí)驗(yàn)比較

實(shí)驗(yàn)對(duì)比結(jié)果如表3所示，獨(dú)立運(yùn)行50次測(cè)試方案1，選擇獲得的最優(yōu)值進(jìn)行比較，其中參與比較的免疫算法的結(jié)果來(lái)自于文獻(xiàn)[9]中各種免疫算法與不同變異策略相結(jié)合的最好值。

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

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

3.3.2 BPAIS與其他進(jìn)化算法的實(shí)驗(yàn)比較

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

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

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

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

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

4 結(jié) 論

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