免疫克隆選擇多目標優化算法與MATLAB實現

收稿日期：2014－05－14

基金項目：四川省教育廳重點科研項目（12ZA193）。

作者簡介：杜振華(1987-)，男，四川南充人，碩士，助理工程師，主要研究方向: 智能計算、最優控制；

閆肅(1972-)，男，甘肅靜寧人，碩士，高級工程師，主要研究方向: 控制工程、儀器儀表工程；

諶海云(1967-)，男，四川射洪人，碩士，教授，主要研究方向: 控制理論與控制工程、信號檢測與信息處理。

摘要：本文闡述了用人工免疫算法實現多目標優化的基本原理，深入探討了在MATLAB環境下如何實現抗體群的克隆、進化、選擇以及種群修剪。算法中采用實數編碼，每個基因位對應一個目標函數值，由于克隆不存在交叉，本文算法的進化動力完全依靠高頻變異。最后，選取了經典測試函數對算法進行了測試，結果表明：Pareto最優解的分布范圍廣、分布均勻，用MATLAB實現該算法時計算效率高。

關鍵詞：免疫克隆選擇多目標優化； MATLAB； 高頻變異

中圖分類號：TP311文獻標識碼：A文章編號：2095-2163（2014）03-0045-04

Immune Clonal Selection Algorithm for Multi-objecvtive Optimization

and Matlab Implementation

Du Zhenhua1，2， Yan Su1，2， Chen Haiyun2， Zeng Huan2

（1 School of Electrical Engineering and Information， Southwest petroleum university， Chengdu 610500，China;

2 CNOOC Energy Conservation Environmental Protection Service CO.，Ltd， Tianjin 300457，China）

Abstract：This paper expounds the basic principle of artificial immune algorithm to achieve multi-objective optimization， thoroughly discusses how to realize the antibody population clone， evolution， selection and trim in the MATLAB environment. Real-coded is adopted in the algorithm， each bit of gene corresponds to a objective function value， and the algorithm evolutionary force is totally depend on hypermutation， due to there is no cross in clone process.Finally， the classic test function is selected to test the algorithm， the results show that: Pareto optimal solutions widely and uniformly distributed， and it has a high computation efficiency to achieve the algorithm with MATLAB.

Key words：Immune Clonal Selection of Multi-objective Optimization;MATLAB; Hypermutation

0引言

啟發式隨機搜索在解決單目標的優化計算中取得了優異的成果，這種方法不依賴于問題的連續性和可導性，可以解決非線性、多峰函數的尋優計算，且計算的難度也要遠遠小于傳統方法。然而，在工程實際中，往往很難僅憑借單項指標來衡量某項決策的好壞，因此即需引入多項指標來更為全面地評價相應決策。但是若使用多個性能泛函來評價一個事物時，多個性能指標往往相互制約、且相互矛盾，也就是一方的收益多會導致另一方的利益受損。我國以崔遜學、鄭金華為代表的多目標進化算法學者，于2006年先后發表了相關理論研究成果，算法的進化方式則是依靠交叉和變異的有性生殖。隨著免疫學的進步，脊椎動物的免疫機理正逐步引入到進化計算的思想中，本文即借鑒免疫機理，模仿脊椎動物的免疫應答過程來實現多性能泛函的尋優計算。

1多目標優化算法

1.1多目標優化問題描述

多目標優化問題（MOP）可用如下數學表達式描述：

給定決策向量X=（x1，x2，…，xn）∈Ω，且滿足下列約束：

gi(X)≥0(i=1，2，…，k)

hi(X)≥0(i=1，2，…，k)（1）

設有r個優化目標，但這r個優化目標卻相互矛盾，一方的增益會導致另一方的利益受損，則該優化目標可以表示為：

F(X)=(f1(X)， f2(X)，…， fr(X))（2）

尋求X*=（x*1，x*2，…，x*n）使得F(X*)最優，且滿足式（1）的兩個約束條件。

1.2生物免疫

免疫是復雜生物的一種生理機能，生物通過這種機能來保護自己不受外來物（細菌、病毒、致敏源）或本身有害細胞（腫瘤細胞）的侵襲。1920年之后，免疫學的理論研究進入到了免疫化學的研究階段，在這之后生物免疫系統誕生了兩個重要學說。其中，一個是1960年Burnet和Medawar的克隆選擇學說，這一學說解釋了當抗原進入生物體后，生物體如何對其進行識別，并產生免疫應答和免疫記憶的過程；另一個則是Jerne提出的免疫網絡學說［1］。這兩種學說清晰闡明了免疫過程作用機理，具體如圖1所示。

圖1 生物免疫應答過程

Fig.1Biological immune response process圖1即為免疫應答過程的簡化流程示意圖。當抗原被識別后，效應T細胞和漿細胞進行克隆，產生抗體并殺死抗原，同時抗原數量又能反作用于抗體，并且限制抗體的數量［1］。而在免疫應答過程中，將會產生免疫B細胞，這樣就能在抗原再次刺激時快速發起殺死抗原的效應，這一過程則稱為免疫記憶。該過程也為算法提供了借鑒意義，即對于一個多目標問題，每一代進化均應保留一定數量的精英個體。第3期杜振華，等：免疫克隆選擇多目標優化算法與MATLAB實現智能計算機與應用第4卷

1.3多目標人工免疫

人工免疫系統（Artificial Immune Systems，AIS）是一種模仿生物體免疫系統的智能方法，這一過程主要包括免疫應答和免疫記憶［2］。AIS的研究最初起始于上世紀80年代，并伴隨著人們對生物免疫系統的深入研究而獲得了穩步發展。近年來，越來越多的學者團體投身免疫計算的研究，所取得的異體檢測與識別、未知異體學習與記憶、異體消除和系統修復等理論成果均已應用到了智能網絡、故障診斷以及智能機器人等一眾領域，并獲得了很好的效果。然而，針對多目標優化的免疫算法和單目標情況卻有著較大的區別，這也是多目標優化算法的發展滯后于單目標優化算法的原因之一。我國針對多目標免疫算法的研究起步于2005年，直至2010年焦李成、尚榮華等人發表了我國第一部擁有實際理論研究成果的多目標免疫算法著作。其算法的核心思想是對傳統免疫算法理念的一個挪用或參照。區別于單目標免疫優化算法，多目標免疫優化算法模仿的免疫過程及相關概念如下分別列示如下：

定義1抗體。同一抗原的表面有多個抗原表位，每一個表位就相當于一個性能泛函，只有多個表位被識別并產生免疫應答時才會產生抗體。因此，抗體在多目標算法中就是根據每個性能泛函所產生的Pareto最優解。

定義2克隆。克隆是生物的無性增殖過程，在算法中克隆是對抗體基因片段的簡單復制，在基因長度確定的情況下，不允許基因位的橫向擴展復制。

定義3變異。基因突變公認為是生物種群的進化方式之一，由于抗體的克隆增殖過程不存在基因交叉，因此，高頻變異是算法進化的主要動力。

定義4抗體—抗原親和力。抗原和抗體是一種非共價的結合，不形成共價鍵，因此需要四種分子間的引力（靜電引力、范德華力、氫鍵結合力、疏水作用力）來使其結合。在多目標優化中，不同的結合力度對應著不同的支配等級，所有非支配集合中的個體均認為是具備最強的結合力。

定義5選擇與修剪。抗體不僅能夠識別抗原，還能相互識別，這就使得抗體不會永遠增殖，算法通過計算抗體的聚集度來選擇聚集度小的抗體并修剪抗體規模以保持種群良好的分布性。

2算法的Matlab實現

染色體或基因片段的表達通常以矩陣的方式來描述，Matlab對矩陣計算具有較大優勢，而且以矩陣方式表述染色體更是降低了代碼的復雜度。除此之外，Matlab自帶的Simulink可以將仿真和優化計算相結合，為工程實際問題的高效解決提供了更加便捷的方式。因此，本文采用Matlab來實現免疫克隆選擇多目標優化算法的編程，算法步驟為：

Step1：根據抗原產生初始抗體群的基因片段，為與其他進化算法的表述一致，將這一基因片段當作是一條染色體；

Step2：根據免疫記憶原理，對初始的抗體群進行小規模的克隆（本文所用復制比為5）；

Step3：高頻變異（本文采用0.9）是本算法中種群的進化動力，各個抗體的每一基因位均采用按概率變異的方式；

Step4：構造non-dominated set，通過逐一比較的方式，可將抗體劃分為支配個體和非支配個體，再將受支配的個體從進化種群中刪除；

Step5：計算擁擠距離，并判斷種群規模是否超過預設值。若種群規模過大，則刪除聚集度大的個體，以保持種群良好的分布特性；

Step6：克隆優異抗體；

Step7：判斷是否達到預設的進化代數，是則輸出Parto最優解，并繪制解的分布圖，否則跳轉Step3。

算法的流程圖如圖2所示。根據算法流程圖可以得到算法的主函數程序，其主要內容如算法1所示。

算法1

chrom=crtrp(NINI，FieldR);

chrom=rep(chrom，［5，1］);

wihle gen＜maxgen

selch=Gaussian_mut(chrom，pm，bound);

for i=1:size(selch，1)

objv(i，:)=test1(selch(1，:));

end

［objv，selch］=nondominate(objv，selch);

［objv，selch］=crowdingdistance1(objv，selch，nonex);

chrom=rep(selch，［15，1］);

gen=gen+1;

end

2.1變異算子

由于在二進制編碼中存在著“Hamming”懸崖，故本算法采用實數編碼方式，且實數編碼方式省卻了二進制數到十進制數的轉換計算，如此即能有效降低算法的時間復雜度。針對實數編碼的變異方式有多種，而每種變異方式對算法的局部搜索能力和全局搜索能力都會發生一定的影響，尤其是進化過程中不存在交叉算子的情況下，影響將更加突出。本文選取了常用的高斯變異方式，其實現代碼如算法2所示。算法中，chrom為抗體的基因片段，pm為變異概率（本文取0.9），bound則指明了每一基因位個體的變異取值范圍。

圖2 算法流程圖

Fig.2Algorithm flow chart

設xk為變異點，其取值范圍是［xkmin，xkmax］， 那么新的基因x′k為：

x′k=m+s*(∑12i=1ri-6)，r=rand(1，12)（3）

式中，m=xkmin+xkmax2， S=xkmax-xkmin6

算法2

function ret=gaissian_mut(chrom，pm，bound)

［m，n］=size(chrom)

for i=1:m

r=rand(1，12)

s=sum(r)

pick=round(rand*(n-1)+1)

u=(bound(1，pick)+bound(2，pick))/2

v=(bound(2，pick)-bound(1，pick))/6

q=u+v*(s-6)

if rand＜pm

chrom(i，pick)=q

end

end

ret=chrom;

2.2non-dominated set構造

非支配集的構造采用逐一比較的方式，非支配集的構造即需遵循如下的定義6。

定義6：設X和X*是多目標優化問題候選解集中的任意兩個非等值個體，假定X*是非支配的（Pareto-占優），則需要滿足如下條件：

（1）對于所有的子目標，X*不比X差，即fk(X*)≤fk(X)，(k=1，2，…，r)

（2）至少存在一個子目標，使得X*比X好，即q∈{1，2，…，r}至少有一個子目標使fq(X*)＜fq(X)

其中，r為子目標的數量，此時可用“”表示兩者的關系，即X*X。

算法設計時，對受支配的個體，將其賦值為Inf，然后查找出種群中目標值為Inf個體，刪除對應的解和抗體，具體實現如算法3所示。其中給出了部分代碼，輸入的objv為候選解集，selch為對應的抗體（變異后），相應的輸出則為非支配集及其對應的解。

算法3

function［objv，selch］=nondominate(objv，selch)

forq=1:size(objv，1)

forq=1:size(objv，1)

if objv(p，:)＞objv(q，:)

if objv(p，:)=inf;

end

end

end

2.3選擇與種群修剪

隨著迭代次數的增加，非支配集中抗體數量會不斷增殖，為了保持種群良好的分布性，避免局部抗體過于密集，就需要對種群進行修剪，選擇出聚集度小的個體，將其作為優秀抗體，送入到下一代的進化過程中。本文在算法設計時，首先對目標值進行排序，然后分別計算每個目標值的擁擠距離，對于兩端的個體，將其值取為Inf，即無條件保留邊界個體進入下一代。稍后，按照原有抗體對應的目標值順序將目標值相加并排序，最后，即按照種群的預設規模，刪除聚集度高的個體。擁擠距離的計算如公式（4）所示。

aj-1，i=sortdata(j，i)-sortdata(j-1，i)0.1+max(sortdata(:，i))-min(sortdata(:，i))

（4）

式中，aj-1，i表示第j-1位個體在第i個目標值的擁擠距離，sortdata為目標值矩陣，分母中加上0.1是為了避免分母在特殊情況下為0狀況的發生。

3算法測試

為了驗證僅依靠高頻變異作為進化動力的免疫克隆選擇多目標優化算法在解決多目標優化問題上的有效性，本文選取了一個普通二維目標函數、一個經典kur測試函數以及三維目標測試函數MOP5和MOP7，測試函數如下所示：

（1）test1測試函數

min f1=x41-10x21+x1x2+x42-x21x22

min f2=x41+x1x2+x42-x21x22

-5≤x1≤5，-5≤x2≤5

（2）kur測試函數

min f1=∑n-1i=1(-10e-0.2x2i+x2i+1)

min f2=∑ni=1(|xi|0.8+5sinx3i)

-5≤xi≤5，n=3

（3）MOP5測試函數

min f1=0.5(x2+y2)+sin(x2+y2)

min f2=(3x-2y+4)28+(x-y+1)227+15

min f3=1(x2+y2+1)-1.1e-x2-y2

-30≤x，y≤30

（4）MOP7測試函數

min f1=(x-2)22+(y+1)213+3

min f2=(x+y-3)236+(-x+y+2)28-17

min f3=(x+2y-1)2175+(2y-x)217-13

-4≤x，y≤4

函數的測試結果如圖3所示。

圖3 免疫克隆選擇多目標優化算法測試結果

Fig.3The test results of immune clonal selection

algorithm for multi-objecvtive optimization圖3中，（a）和（b）分別為二維目標函數的測試結果，計算時設置最大進化次數Maxgen=100，抗體規模nonex=80，優異抗體克隆比例為20。（c）和（d）則為三維目標函數的測試結果，計算時設置最大進化次數Maxgen=100，抗體規模nonex=100，優異抗體克隆比例為20。由計算結果可知，解集分布均勻，經典測試函數與標準結果相比較，解集分布范圍廣闊且分布區域正確。

4結束語

本文介紹了一種用于多目標優化的免疫克隆選擇算法，該算法通過模仿生物的免疫應答過程來實現多個目標函數的尋優計算。算法中，抗體群的進化僅依靠變異算子來實現，對優異抗體進行大比例的克隆，且按概率進行免疫記憶，保留精英抗體。通過算法的測試，與文獻［3］中所提供分布圖的比較結果表明，本文在Matlab環境下設計的算法計算效率高、Pareto解集分布廣泛且均勻。本文算法可應用于經濟中的多目標決策、最優控制器設計、路徑優化、工程中的多目標優計算等諸多領域，為解決實際問題提供了有效、可靠的計算方法。

參考文獻：

［1］焦李成，尚榮華，馬文萍，等. 多目標優化免疫算法、理論和應用［M］. 北京:科學出版社，2010.

［2］雷德明，嚴新平.多目標智能優化算法及其應用［M］.北京:科學出版社，2009.

［3］鄭金華.多目標進化算法及其應用［M］.北京:科學出版社，2007.

［4］JIAO L C， GONG M G， SHANG R H， et al. Clonal selection with immune dominance and anergy based multi-objective optimization［C］//Proceedings of 3rd International Conference on Evolutionary Multi-criterion Optimization.Berlin:Springer，2005:474-489.

［5］SCHAFFER J D. Multiple objective optimization with vector evaluated genetic algorithms［C］//Proceedings of 1st International Conference on Genetic Algorithms and Their Applications. Hillsdale: Lawrence Erlbaum Associates， Inc.， 1985:93-100.

［6］DEB K， PRATAB A， AGARWAL S， et al. A fast and elitist multi-objective genetic algorithm:NSGA-II［J］. IEEE Transactions on Evolutionary Computation，2002，6(2):182-197.

［7］COELLO C A， CRUZ C N. An approach to solve multiobjective optimization problems based on an artificial immune system［C］//Proceedings of 1st International Conference on Artificial Immune Systems， Canterbury， 2002:212-221.

［8］崔遜學.多目標進化算法及其應用［M］. 北京：國防工業出版社，2006.

［9］JOSHUA K， CORNE D. Properties of an adaptive archiving algorithm for storing nondominated vectors［J］.IEEE Transactions on Evolutionary Computation，2003，7（2）：100-116.