基于解空間定向優(yōu)化的改進(jìn)免疫算法研究及應(yīng)用*

王 波，胡軍臺(tái)，張克勇，李曉航，張逸群，孫世勇

（國(guó)網(wǎng)河南省電力公司平頂山供電公司，河南 平頂山 467001）

0 引言

生物免疫系統(tǒng)是由免疫細(xì)胞、免疫活性分子和免疫器官等多個(gè)子系統(tǒng)組成的復(fù)雜系統(tǒng)。免疫系統(tǒng)所屬的子系統(tǒng)之間具備著相當(dāng)復(fù)雜的依附關(guān)系、競(jìng)爭(zhēng)關(guān)系等，它們具有識(shí)別、消除異物的功能［1］，動(dòng)態(tài)控制生物體內(nèi)的各項(xiàng)指標(biāo)處于正常狀態(tài)。人工免疫算法（IA）就是結(jié)合生物的免疫系統(tǒng)建立起來(lái)的一種有效的優(yōu)化控制方法，其主要思想是在免疫系統(tǒng)中尋找最佳的抗體來(lái)對(duì)抗生物體內(nèi)的異物或病原體。IA 作為現(xiàn)代基本的控制算法已經(jīng)在系統(tǒng)優(yōu)化設(shè)計(jì)［2-3］、系統(tǒng)智能控制［4］、模式識(shí)別［5］、故障診斷［6］、網(wǎng)絡(luò)安全［7］等領(lǐng)域中得到了廣泛的應(yīng)用。但是在實(shí)際應(yīng)用過(guò)程中，IA 也存在著搜索效率低、陷入極值等問(wèn)題，限制了IA 在一些大型信號(hào)處理項(xiàng)目中的應(yīng)用。

如今，對(duì)于IA 的改進(jìn)算法也層出不窮，許多專(zhuān)家學(xué)者基于傳統(tǒng)IA 的局限性問(wèn)題，結(jié)合現(xiàn)代主流控制算法進(jìn)行改進(jìn)，文獻(xiàn)［8］中，將人工蜂群算法與IA 相結(jié)合，并結(jié)合兩者優(yōu)勢(shì)提出基于蜂群算法與免疫算法的融合控制算法，有效提升了傳統(tǒng)單一算法搜索精度不高的問(wèn)題，提升了算法的收斂速度與全局搜索能力。文獻(xiàn)［9］中，將混沌理論引入免疫算法之中，提出了基于混沌理論的新型免疫算法，同樣也是提升了IA 的尋優(yōu)精度以及全局搜索能力，使得新型算法能夠有效避免陷入部分極值。

另一些改進(jìn)思想主要集中在IA 本身，傳統(tǒng)的IA 中包含了諸多不定參數(shù)，需要進(jìn)行預(yù)先設(shè)定，這些參數(shù)控制著算法的最終收斂精度、迭代次數(shù)、搜索步長(zhǎng)等。為提升算法的適用范圍，對(duì)這些參數(shù)的設(shè)置提出了相關(guān)改進(jìn)措施。文獻(xiàn)［10］中，對(duì)免疫算法的變異率進(jìn)行了詳細(xì)研究，利用周期變異率替代傳統(tǒng)IA 中的固定變異率。文獻(xiàn)［11］中，分析了變異率、濃度閾值、記憶庫(kù)規(guī)模的影響程度，利用仿真實(shí)驗(yàn)確定了最佳參數(shù)設(shè)置范圍。

本文針對(duì)傳統(tǒng)IA 在搜索階段的效率不高問(wèn)題，提出依靠解空間定向優(yōu)化的改進(jìn)IA。相比于其他已有的改進(jìn)思路，本文從計(jì)算量的角度考慮，參考人體免疫系統(tǒng)識(shí)別、消滅外來(lái)異物、抗原的全部過(guò)程，結(jié)合藥物輔助的手段加快人體免疫系統(tǒng)消滅外來(lái)抗原，使得機(jī)體能夠更快的恢復(fù)健康的方法，本文提出一種基于解空間定向優(yōu)化的改進(jìn)免疫算法，以獲得較高效率的算法搜索過(guò)程，以及更高的算法收斂速度。

1 改進(jìn)免疫算法原理分析

傳統(tǒng)免疫算法是根據(jù)待測(cè)目標(biāo)函數(shù)產(chǎn)生相應(yīng)的初始解群，記為u0（t）。并且通過(guò)對(duì)比初始解群獲得的算法精度與預(yù)設(shè)精度進(jìn)行比較，若此時(shí)的候選解群已經(jīng)滿(mǎn)足人為要求，則算法停止對(duì)于目標(biāo)函數(shù)的進(jìn)一步搜索，同時(shí)認(rèn)為此時(shí)得到的解即為目標(biāo)函數(shù)最優(yōu)解；若不滿(mǎn)足人為要求，就類(lèi)似機(jī)體免疫系統(tǒng)根據(jù)外來(lái)病原體逐步形成有效抗體的過(guò)程，算法在搜索目標(biāo)函數(shù)區(qū)域的同時(shí)，逐步形成新的、更優(yōu)的解群體，不斷接近最優(yōu)解群。因此，定義親和力參數(shù)來(lái)衡量解群的優(yōu)劣，抗體（解群）與抗原（目標(biāo)函數(shù)）之間的親和度參數(shù)可以表示為：

式（1）中，Aappetency表示兩者之間的親和力參數(shù)，fit（u）表示抗原與抗體之間的匹配程度，該函數(shù)的值越大，說(shuō)明抗體與抗原之間的匹配度較高，抗體能夠有效消滅抗原，因此，更有利于算法的收斂。pra（u）表示獎(jiǎng)勵(lì)函數(shù)，調(diào)整獎(jiǎng)勵(lì)函數(shù)值來(lái)增加抗體抗原之間的親和力。在每一次迭代求解的過(guò)程中，利用親和力與預(yù)期閾值之間進(jìn)行比較，獲取最優(yōu)解群：

直到達(dá)到預(yù)設(shè)閾值。在傳統(tǒng)的免疫算法中，會(huì)產(chǎn)生較多的冗余計(jì)算，導(dǎo)致算法的收斂速度不高，且算法效率不高，這是由于傳統(tǒng)的免疫算法為了追求目標(biāo)函數(shù)搜索的完備性，對(duì)目標(biāo)函數(shù)的整體進(jìn)行搜索，因此，浪費(fèi)了較多不必要的搜索時(shí)間。為了降低算法在目標(biāo)函數(shù)搜索過(guò)程中的冗余過(guò)程，本文增加了定向搜索判定，在算法迭代的過(guò)程中，朝著目標(biāo)函數(shù)的優(yōu)化方向進(jìn)行搜索，排除掉較多的無(wú)效的搜索區(qū)域。能夠有效降低算法的搜索耗時(shí)，同時(shí)也會(huì)使得免疫算法不再因陷入極小值而停止搜索，提高了算法的收斂效率。并可針對(duì)新的目標(biāo)函數(shù)區(qū)域?qū)蜻x解群進(jìn)行相應(yīng)的變異和克隆步驟。

對(duì)于目標(biāo)函數(shù)的處理過(guò)程與機(jī)體對(duì)抗外來(lái)抗原類(lèi)似，在進(jìn)行多次判定后，集體會(huì)選取最優(yōu)抗體用于對(duì)抗抗原。體現(xiàn)在算法上，根據(jù)不斷迭代求解解群，結(jié)合親和力判斷，將親和力更高的解群進(jìn)行克隆。迭代算法保證逐步提升候選解群與目標(biāo)函數(shù)的親和力，解群的克隆規(guī)模應(yīng)根據(jù)人為要求進(jìn)行設(shè)置。

變異是為了保證候選解群的多樣性，防止陷入局部最優(yōu)值。變異操作一直是免疫算法中十分重要的部分，對(duì)于變異率的設(shè)置對(duì)算法的影響明顯。根據(jù)文獻(xiàn)［16］作出的研究表明：變異率的取值既不能太大又不能太小，太小的話，變異操作的效果不明顯，群體多樣性不能保證；變異率也不能太大，會(huì)導(dǎo)致群體的穩(wěn)定性很差。為此，將變異率設(shè)置成為變化的參數(shù)，保證候選解群穩(wěn)定性的同時(shí)，也使候選解群具有一定的多樣性。為增加算法的收斂速度，每一次克隆過(guò)程中進(jìn)行親和力判定，同時(shí)進(jìn)一步更新候選解群。更新算法參數(shù)，重復(fù)步驟2 至步驟5，直至滿(mǎn)足人為要求，最終得到最優(yōu)解群uopt（t）。改進(jìn)的免疫算法實(shí)施的具體流程圖如下頁(yè)圖1 所示。

如圖1 所示，利用變異率Pm與閾值T 共同約束，每一次迭代求解候選解群的變異程度與算法的全局搜索能力，即決定了算法的收斂速度，提升變異率后，可以增加求解最優(yōu)解群的機(jī)會(huì)，但同時(shí)也會(huì)使整個(gè)算法的收斂速度降低，因此，定義算法的終止判據(jù)：

圖1 改進(jìn)的免疫算法流程圖

f（uopt）∈（min f（x）-△δ，min f（x）+△δ） （3）式（3）中，△δ 表示目標(biāo)函數(shù)的搜索區(qū)域。當(dāng)搜索出的解群uopt滿(mǎn)足人為要求，則停止搜索，即認(rèn)為此時(shí)得到的候選解群為最優(yōu)解群。如圖1 所示，算法步驟2～步驟5 是一個(gè)馬爾科夫過(guò)程，因此，任意初始狀態(tài)分布均有［17］：

式（4）中，s*表示滿(mǎn)足最大親和力式（1）的搜索空間集合，An表示初始狀態(tài)。根據(jù)馬爾科夫鏈的相關(guān)性質(zhì)：

2 仿真實(shí)驗(yàn)及結(jié)果分析

為驗(yàn)證基于解空間定向優(yōu)化的改進(jìn)免疫算法的可行性和優(yōu)越性，利用一系列一元測(cè)試函數(shù)對(duì)算法進(jìn)行仿真實(shí)驗(yàn)。仿真過(guò)程中的目標(biāo)函數(shù)設(shè)置如表1 所示，仿真主要考察算法的收斂效率，實(shí)驗(yàn)結(jié)果利用響應(yīng)耗時(shí)來(lái)表征。測(cè)試函數(shù)分為5 個(gè)，包括了單峰函數(shù)與多峰函數(shù)。

表1 目標(biāo)函數(shù)設(shè)置

表2 傳統(tǒng)免疫算法與本文算法測(cè)試結(jié)果比較

對(duì)比傳統(tǒng)的免疫算法與本文算法對(duì)于目標(biāo)函數(shù)的求解最優(yōu)解群的最終結(jié)果，可以看出：本文算法能夠在保證標(biāo)準(zhǔn)差的同時(shí)，縮短整體算法的運(yùn)算時(shí)間；在單峰函數(shù)搜索過(guò)程中，本文算法約為傳統(tǒng)免疫算法的1/3，其余的目標(biāo)函數(shù)搜索過(guò)程也可縮短傳統(tǒng)響應(yīng)耗時(shí)的一半左右，體現(xiàn)出了本文算法在響應(yīng)時(shí)間上的優(yōu)勢(shì)。

3 結(jié)論

本文提出基于解空間定向優(yōu)化的改進(jìn)免疫算法，從算法響應(yīng)耗時(shí)的角度出發(fā)，增加了定向搜索判別過(guò)程，在保證解群精度的條件下，算法響應(yīng)耗時(shí)最大降低至傳統(tǒng)免疫算法的1/3，體現(xiàn)出了改進(jìn)算法的優(yōu)越性。改進(jìn)的免疫算法針對(duì)多極值的函數(shù)尋優(yōu)時(shí)，耗時(shí)會(huì)逐步增加，因此，需要針對(duì)多極值函數(shù)的解空間優(yōu)化方向進(jìn)行改進(jìn)，可以在親和力與變異、克隆參數(shù)上進(jìn)一步優(yōu)化。