武慧虹,錢淑渠,王海英

(安順學(xué)院 數(shù)理學(xué)院,貴州 安順 561000)

0 引言

實(shí)際工程中，常常涉及高維的多目標(biāo)優(yōu)化問題(MOPs:Multiobjective Optimization Problems)，高維MOPs需要同時優(yōu)化多個相互沖突的目標(biāo)且變量空間的維數(shù)非常高，該類問題對算法的優(yōu)化能力要求極高．已有的數(shù)學(xué)優(yōu)化算法極難獲得理想的優(yōu)化效果[1]，故借鑒新的優(yōu)化理論設(shè)計高級優(yōu)化算法對MOPs的求解已成為當(dāng)今優(yōu)化領(lǐng)域的研究熱點(diǎn)[4-5]．

近年，大量基于群體智能的多目標(biāo)優(yōu)化算法(MOEA:Multiobjective Optimization Evolutionanry Algorithms)被提出:如文[6]基于生物進(jìn)化理論設(shè)計遺傳算法(GA:Genetic Algorithm)用于求解MOPs，仿真結(jié)果表明其具有一定的優(yōu)越性,但該算法僅適應(yīng)于低維的MOPs的求解[4]．另一方面，研究者希望通過改進(jìn)GA，提高算法求解MOPs的能力，Deb在2002年提出一種著名的MOEA (即NSGAII)[7],該算法的提出推動了進(jìn)化算法在多目標(biāo)優(yōu)化領(lǐng)域中的應(yīng)用，凸顯智能算法求解MOPs的優(yōu)越性，致使NSGAII成為很多新設(shè)計MOEA的比較對象．Hsieh等[6]基于GA設(shè)計一種分享突變算子提高M(jìn)OEA對Pareto有效解的搜索能力．Guo等[7]根據(jù)個體性能排列次序及個體濃度設(shè)計MOEA的適應(yīng)度，以其引導(dǎo)算法快速搜索Pareto有效面，并將算法用于三目標(biāo)問題的求解．縱觀已有MOEA知，學(xué)者們設(shè)計的重點(diǎn)是設(shè)計新算子提高算法的(1)群體多樣性(2)開采和探索能力．

但MOEA是一種隨機(jī)搜索算法，在有限的迭代數(shù)下對復(fù)雜MOPs易于出現(xiàn)早熟，難于獲得分布均勻的Pareto有效面．而基于人工免疫系統(tǒng)的免疫優(yōu)化算法具有高度的并行性及抗體多樣性等特征，算法開采和探索能力強(qiáng)．2002年，Castro和Fernando基于免疫系統(tǒng)克隆選擇原理提出一種著名的克隆選擇算法(CSA:Clonal Selection Algorithm)用于MOPs，實(shí)驗(yàn)表明CSA用于MOPs的求解具有較大的優(yōu)勢[8]，該研究推動了人工免疫算法在MOPs中的應(yīng)用．繼后，Castro和 Zuben基于免疫網(wǎng)絡(luò)思想提出免疫網(wǎng)絡(luò)優(yōu)化算法[11],通過抑制冗余抗體增強(qiáng)群體多樣性，實(shí)驗(yàn)表明算法對復(fù)雜的多模態(tài)問題表現(xiàn)較強(qiáng)的優(yōu)化能力．

近來，設(shè)計免疫優(yōu)化算法求解MOPs已成為人工智能領(lǐng)域的研究熱點(diǎn)，特別對復(fù)雜的高維MOPs表現(xiàn)出較好的優(yōu)化效果[12]．為此，本文基于混沌規(guī)律，借鑒生物免疫系統(tǒng)自適應(yīng)性和并行性，設(shè)計免疫算子模塊，提出一種混雜多目標(biāo)免疫優(yōu)化算法(HMIOA:Hybrid Multiobjective Immune Optimization Algorithm)．本算法(1)抗體的親和力設(shè)計突出其被控度和抗體擁擠程度，提高算法的收斂速度及所獲Pareto有效面的分布均勻性;(2)對優(yōu)秀抗體采取混沌克隆的方式，提高克隆群的多樣性;(3)對不同的群體采取不同的突變方式，提高算法的搜索和開采能力等．?dāng)?shù)值實(shí)驗(yàn)將HMIOA與NSGAII的兩種提高算法(NSGAII-A、 NSGAII-B)[11]及CSA用于4類MOPs測試算法的性能，比較結(jié)果表明:HMIOA較參與比較的算法具有更強(qiáng)的搜索能力，克服已有算法的早熟現(xiàn)象，能獲得分布均勻的非控Pareto有效面．

1 問題描述及相關(guān)定義

考慮如下多目標(biāo)極小化問題(P)

其中,x=(x1,x2，…，xn)∈Rn為決策向量，n為向量空間維數(shù)，fi(x)為子目標(biāo)函數(shù)，M為子目標(biāo)數(shù)目．

定義1：對于問題P,稱向量x控制向量y或y被x控制(記為:xy),如果

fi(x)≤fi(y)∧?k,st.fk(x)

定義2：對有限子集X?Rn及向量x*∈X,若不存在任何向量y∈X,使得yx*,則稱x*為Pareto有效解或非控解，所有非控解構(gòu)成的集合稱為Pareto有效集(記為POS),所有非控解對應(yīng)的目標(biāo)值構(gòu)成的面稱為Pareto有效面或非控面(記為POF)．

2 算法描述及算子設(shè)計

2.1 算法描述

基于免疫系統(tǒng)的特征,HMIOA算法流程如圖1,圖中為當(dāng)前迭代數(shù),G為最大迭代數(shù),步驟描述為：

步驟1:初始抗體群．隨機(jī)生成抗體p1,按2.2.1中式(1)生成N個抗體構(gòu)成初始抗體群A,置初始代數(shù)g=0,記憶集M=φ;

步驟2:抗體評價．根據(jù)2.2.2中式(2)及(3)計算抗體群A中各抗體的被控度及親和力;

步驟3:群體分離．按照被控度將群體A分成非控子群B和被控子群C;

步驟4:記憶集更新．記憶集M保存B中m個優(yōu)秀的非控抗體,若|M|>m,則執(zhí)行記憶集更新,否則轉(zhuǎn)步驟5;

步驟5:混沌克隆．混沌克隆算子作用于B，獲克隆群E;

步驟6:非均勻突變．克隆群E經(jīng)由非均勻突變,獲突變?nèi)篎;

步驟7:多項(xiàng)式突變．多項(xiàng)式突變作用于被控子群C,獲突變?nèi)篋;

步驟8:組合抑制．組合M、F及D,獲組合群

H=M⊕F⊕D．

若|H|>N,Average linkage[5]刪去冗余抗體,獲抗體群K;

步驟9:置n←n+1，A←K，轉(zhuǎn)入Step2．

2.2 算子設(shè)計

2.2.1 抗體及初始抗體群

抗體采用實(shí)數(shù)編碼，假設(shè)A是N×n矩陣，則

圖1 算法HMIOA流程圖

A表示N個抗體組成的抗體群

其中，pi表示抗體i，pij∈R表示抗體i的第j基因位的值，n為基因長度．初始抗體群采用混沌規(guī)律生成，首先隨機(jī)生成初始抗體pi，然后按式(1)生成p2，…，pN．

pi+1=μpi(1-pi),(i=1，…，N-1)

(1)

對應(yīng)于MOPs，即：抗體pi(i=1，2，…，N)對應(yīng)于MOPs的變量x，抗體群A對應(yīng)于MOPs的解集，基因長度n對應(yīng)于MOPs向量的維數(shù)．

2.2.2 抗體的親和力

抗體親和力的設(shè)計對算法的收斂速度及算法選擇壓具有重要的作用，在多目標(biāo)優(yōu)化問題中，既要求算法快速獲得近似Pareto有效面，又希望所獲的Pareto有效面具有均勻的分布．要使Pareto有效面分布均勻，親和力的設(shè)計對多樣性抗體的選擇具有重要的引導(dǎo)作用，如親和力引導(dǎo)算法朝Pareto面上稀疏抗體處搜索，我們可以簡單引進(jìn)抗體間的距離作為選擇的一個標(biāo)準(zhǔn)，故本文親和力設(shè)計如下：對于給定抗體群A={p1，p2，…，pN}，根據(jù)定義1,抗體pi的被控度定義為其被控的抗體數(shù)c(pi),表達(dá)式為：

c(pi)=|{y|ypi,?y∈A}

(2)

其親和力設(shè)計為:

(3)

其中，d(pi)指抗體pi的擁擠距離，具體細(xì)節(jié)如[5]．從(3)式可看出，被控度越小，擁擠距離越大的抗體具有優(yōu)先的選擇機(jī)會．

注：根據(jù)(2)式，若c(pi)=0，抗體pi為非控抗體．

2.2.3 混雜突變

設(shè)pi為突變抗體,其突變概率設(shè)計為:

(4)

其中，λ、σ為調(diào)節(jié)參數(shù)，0<λ<0.5,σ≥1，F(xiàn)(pi)如式(3)，抗體的突變概率隨算法迭代數(shù)增加而減小，并且親和力大的抗體突變概率小，以期保證親和力大的抗體突變程度?。?/p>

本文對不同的抗體群采取不同的突變方式，克隆群為較好的抗體群，采樣微小的非均勻變異，達(dá)到精度搜索功能；對非控抗體群，采取多項(xiàng)式突變，抗體突變程度較大，達(dá)到大范圍的搜索功能，二者通過迭代達(dá)到有機(jī)結(jié)合，提高算法的局部和全局搜索能力：

(1)多項(xiàng)式突變

Step1 取一隨機(jī)數(shù)μi∈(0，1).

Step2 計算參數(shù)χi，如下

(5)

(2)非均勻突變

(6)

2.2.4 混沌克隆

克隆算子主要對優(yōu)秀抗體進(jìn)行復(fù)制，增加優(yōu)秀抗體的快速消除抗原能力，克隆體在免疫系統(tǒng)中經(jīng)受不同的突變，存現(xiàn)一種混沌現(xiàn)象，該算子僅作用于非控抗體，克隆方式如下．

={l(p1),l(p2)，…l(pη)}

2.2.5 記憶集更新

免疫系統(tǒng)中，記憶細(xì)胞是B細(xì)胞經(jīng)抗原被激活后而留存在體內(nèi)的細(xì)胞，當(dāng)其再次遇到類似抗原出現(xiàn)時其發(fā)出快速消除抗原的能力，對應(yīng)于優(yōu)化問題，其是優(yōu)秀的解，而在多目標(biāo)優(yōu)化問題中記憶細(xì)胞就是非控抗體，當(dāng)算法進(jìn)行下一次循環(huán)時，記憶細(xì)胞參與新抗體群的產(chǎn)生，以增強(qiáng)算法優(yōu)化速度．由于記憶集中的記憶細(xì)胞隨算法的迭代而劇增，為了控制細(xì)胞數(shù)目，首先刪去相同的非控記憶細(xì)胞，然后根據(jù)記憶細(xì)胞的親和力利用Average linkage[5]法消除冗余細(xì)胞，直到獲規(guī)模為預(yù)定大小為m的記憶細(xì)胞集．

3 測試問題及評價準(zhǔn)則

為了測試HMIOA的性能，本文選擇如下測試問題[11]1～4測試算法的性能．其中問題1～3為二目標(biāo)優(yōu)化問題，問題3為三目標(biāo)問題，在所有問題中向量的維數(shù)均為高維，問題難度逐漸增大，具體如下．

3.1 測試問題

問題1：

f(x)=(f1(x),f2(x))

問題2：

f(x)=(f1(x),f2(x))

問題3：

f(x)=(f1(x),f2(x))

問題4：

f(x)=(f1(x),f2(x),f3(x))

其中，維數(shù)n=12，該問題為3目標(biāo)問題．

3.2 評價準(zhǔn)則[10]

在MOPs中，評價算法的優(yōu)越關(guān)鍵是測試算法所獲POF的收斂性及分布性，又由于智能算法是一種隨機(jī)搜索法，具有一定的隨機(jī)性，為了減少隨機(jī)性對測試結(jié)果的影響，往往采取多次獨(dú)立執(zhí)行，從統(tǒng)計的角度分析算法的優(yōu)越性．假設(shè)算法X與Y對MOPs分別獨(dú)立執(zhí)行K次所獲的POS分別為Ai和Bi(i=1,2,…，K)．則平均控制率(ADR(.,.))定義為

(4)

其中，

若ADR(X，Y)>ADR(Y,X),則表明算法X所獲POS控制算法Y所獲POS，也即算法X收斂性優(yōu)越于算法Y;否則相反．

4 數(shù)值實(shí)驗(yàn)

選取參與比較的算法為NSGAII-A、 NSGAII-B和CSA．其中HMIOA中參數(shù)如表1．

表1 HMIOA各算子中的參數(shù)取值

各算法的初始群規(guī)模N=100,最大迭代數(shù)G=300,各算法對每個問題分別獨(dú)立執(zhí)行K=30次，實(shí)驗(yàn)統(tǒng)計結(jié)果如表2～5，各算法執(zhí)行一次所獲Pareto有效面比較如圖2～8．

表2為各算法對問題1獨(dú)立執(zhí)行30次所獲平均控制率比較．由表知，HMIOA所獲的Pareto有效面控制NSGAII-A所獲的Pareto有效面的比率為13.9%，而NSGAII-A控制HMIOA的比率僅為0.5%；HMIOA控制NSGAII-B的比率為13.6%，而NSGAII-A控制HMIOA的比率僅為0.8%；HMIOA控制CSA的比率為47.8%，而CSA控制HMIOA的比率為0.0%．由上分析知HMIOA所獲的Pareto有效面較大的控制其他算法所獲的Pareto有效面．由圖2知，雖NSGAII-A、NSGAII-B及HMIOA所獲Pareto有效面整體觀察均能接近理論P(yáng)areto有效面，但由圖3的小區(qū)域放大知，HMIOA所獲的Pareto有效面分布較均勻，非常接近理論P(yáng)areto有效面，NSGAII-A、NSGAII-B和CSA所獲Pareto有效面與理論P(yáng)areto有效面的接近程度較差，且分布不均勻，CSA效果最差．

表2 各算法對問題1獨(dú)立執(zhí)行30次所獲ADR比較

表3為各算法對問題2獨(dú)立執(zhí)行30次所獲平均控制率比較．由表知， HMIOA控制NSGAII-A的比率為20.2%，而NSGAII-A控制HMIOA的比率僅為0.9%；HMIOA控制NSGAII-B的比率為20.7%，而NSGAII-A控制HMIOA的比率僅為0.8%；HMIOA控制CSA的比率為21.9%，而CSA控制HMIOA的比率為1.7%．由圖4知，HMIOA所獲Pareto有效面均能接近理論P(yáng)areto有效面，且分布均勻，而NSGAII-A、NSGAII-B及CSA所獲非控面分布不均勻．由圖5區(qū)域放大知，NSGAII-A在區(qū)域端點(diǎn)未能獲Pareto有效解，其他兩算法接近理論P(yáng)areto有效面較差．

表3 各算法對問題2獨(dú)立執(zhí)行30次所獲ADR比較

表4為各算法對問題3獨(dú)立執(zhí)行30次所獲平均控制率比較．由表知，HMIOA控制NSGAII-A的比率為5.0%，而NSGAII-A控制HMIOA的比率僅為2.4%；HMIOA控制NSGAII-B的比率為4.2%，而NSGAII-A控制HMIOA的比率僅為2.7%；HMIOA控制CSA的比率為20.3%，而CSA控制HMIOA的比率為0.0%．由圖6～7知，HMIOA所獲非控面均

圖2 四算法對問題1所獲POF比較

圖3 問題1在區(qū)域(0.8,1.0)×(0,0.1)內(nèi)POF比較

圖4 四算法對問題2所獲POF比較

表5為各算法對問題4獨(dú)立執(zhí)行30次所獲平均控制率比較．由表知， HMIOA控制NSGAII-A的比率為8.6%，而NSGAII-A控制HMIOA的比率僅為1.8%；HMIOA控制NSGAII-B的比率為10.8%，而NSGAII-A控制HMIOA的比率僅為2.5%；HMIOA控制CSA的比率為26.2%，而CSA控制HMIOA的比率為10.5%．由圖8知，HMIOA所獲Pareto有效解較多，且分布均勻，而NSGAII-A、NSGAII-B及CSA所獲非控點(diǎn)非常少，效果非常差．

能接近Pareto有效面，且分布均勻，而NSGAII-A、NSGAII-B及CSA所獲非 控面的端點(diǎn)均未搜索到Pareto有效解．

圖5 問題2在區(qū)域(0.7,1.0)×(0,0.1)內(nèi)POF比較

圖6 四算法對問題3所獲POF比較

圖7 問題3在區(qū)域(4,5)×(-1.5,-0.5)內(nèi)POF比較

圖8 四算法對問題4所獲POF比較表4 各算法對問題3獨(dú)立執(zhí)行30次所獲ADR比較

ADR(.,.)NSGAII-ANSGAII-BCSAHMIOANSGAII-A00.0450.2190.024NSGAII-B0.04800.2160.027CSA0.0020.00300HMIOA0.0500.0420.2030

表5 各算法對問題4獨(dú)立執(zhí)行30次所獲ADR比較

5 結(jié)論及進(jìn)一步工作

本文基于生物免疫系統(tǒng)的主要機(jī)理及特征,提出一種混雜多目標(biāo)免疫優(yōu)化算法．利用不同類型的高維多目標(biāo)問題測試算法的性能,選取著名的多目標(biāo)進(jìn)化算法NSGAII-A及NSGAII-B和一種克隆選擇算法CSA參與比較,結(jié)果表明本文算法所獲非控面較大的控制其他算法所獲的非控面，Pareto有效面分布非常均勻，搜索范圍較廣，較接近理論P(yáng)areto有效面，而其他三算法所獲得Pareto有效面效果較差．接下來我們即將作更深入理論研究,探討其收斂性及算法復(fù)雜性．

[1]徐志丹,莫宏偉.生物地理信息優(yōu)化算法中遷移算子的改進(jìn)[J].模式識別與人工智能,2012,25(3):544-549.

[2]武慧虹，錢淑渠，李 ?。畡討B(tài)環(huán)境優(yōu)化問題及算法綜述[J]．吉林師范大學(xué)學(xué)報(自然科學(xué)版)，2013，34(2)：121～124．

[3]劉春英．粒子群融合蟻群算法多配送中心車輛路徑研究[J]．吉林師范大學(xué)學(xué)報(自然科學(xué)版)，2013，34(3)：88～91．

[4]Pilát M,Neruda R.An evolutionary strategy for surrogate-based multiobjective optimization[C]// IEEE Congress on Evolutionary Computation (CEC),2012:1-7.

[5]Kim J H,Han J H,Kim Y H,et al.Preference-Based Solution Selection Algorithm for Evolutionary Multiobjective Optimization[J].IEEE Transactions on Evolutionary Computation,2012,16(1):20-34.

[6]孔德劍.基于改進(jìn)的遺傳算法的多目標(biāo)優(yōu)化問題研究[J].計算機(jī)仿真,2012,29(2):213-215.

[7]Deb K,Agrawal S,Pratap A,et al.A Fast elitist nondominated sorting genetic algorithm for multiobjective optimization:NSGA-II.IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[8]Hsieh S T,Chiu S Y,Yen S J.An Improved Multi-Objective Genetic Algorithm for Solving Multi-objective Problems[J].Appl.Math,2013,7(5):1933-1941.

[9]Guo X,Wang Y.A Hybrid Simplex Multi-Objective Evolutionary Algorithm Based on A New Fitness Assignment Strategy[J].Journal of Computers,2013,8(2):284-289.

[10]de Castro L,Fernando J.Learning and optimizationusing the clonal selection principle[J].IEEE Transactions on Evolutionary Computation,2002,6(3):239～251.

[11]Freschi F,Coello C A C,Repetto M.Multiobjective optimization and artificial immune systems:a review[J].Handbook of Research on Artificial Immune Systems and Natural Computing:Applying Complex Adaptive Technologies,2009,4:1-21.

[12]Farina M,Deb K,Amato P.Dynamic Multiobjective Optimization Problems:Test Cases,Approximations,and Applications[J].IEEE Transactions on evolutionary computation,2004,8(5):425-442.