楊 凱， 張著洪，2

（1.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州貴陽550025；2.貴州大學(xué)電子信息學(xué)院，貴州貴陽550025）

基于免疫優(yōu)化的單目標(biāo)多模態(tài)期望值規(guī)劃

楊 凱1， 張著洪1，2

（1.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州貴陽550025；2.貴州大學(xué)電子信息學(xué)院，貴州貴陽550025）

為了求解未知隨機(jī)變量分布下單目標(biāo)多模態(tài)期望值規(guī)劃，通過引入檢測候選解是否為局部最優(yōu)解的隨機(jī)函數(shù)，將該期望值規(guī)劃問題轉(zhuǎn)化為多目標(biāo)期望值規(guī)劃問題，并進(jìn)一步探尋問題的轉(zhuǎn)化關(guān)系，獲得在一定條件下有效解是最優(yōu)解的結(jié)論；根據(jù)樣本平均近似化思想，將多目標(biāo)規(guī)劃轉(zhuǎn)化為非恒定樣本采樣的近似化模型，并基于克隆選擇和免疫記憶的機(jī)理，通過設(shè)計(jì)遞歸非支配分層、樣本自適應(yīng)采樣和自適應(yīng)繁殖與變異方案，引導(dǎo)進(jìn)化種群往優(yōu)質(zhì)個(gè)體所在區(qū)域轉(zhuǎn)移，提出了求解該近似化模型的免疫優(yōu)化算法.仿真結(jié)果表明：與參與比較的多目標(biāo)優(yōu)化算法相比，該算法搜索多個(gè)最優(yōu)解方面有明顯優(yōu)勢，搜索效果穩(wěn)定，噪聲抑制能力強(qiáng)；求解低、高維標(biāo)準(zhǔn)測試問題獲得最優(yōu)解的數(shù)量分別平均提高了20%和70%.

隨機(jī)規(guī)劃；多模態(tài)期望值規(guī)劃；多目標(biāo)優(yōu)化；免疫優(yōu)化；自適應(yīng)采樣

多模態(tài)期望值規(guī)劃（multi-modal expected value programming，MEVP）是一類含隨機(jī)變量和多個(gè)局部最優(yōu)解的期望值規(guī)劃.如何在未知隨機(jī)變量分布下，探討高效且具有強(qiáng)進(jìn)化能力的優(yōu)化算法，尋找噪聲環(huán)境下局部、全局最優(yōu)解（簡稱最優(yōu)解），是智能優(yōu)化研究要解決的難題［1-3］.關(guān)于一般期望值規(guī)劃的算法求解研究，主要集中在首先利用神經(jīng)網(wǎng)絡(luò)或樣本平均近似化處理方法，對優(yōu)化模型作近似化處理，然后借助已有靜態(tài)優(yōu)化方法尋找問題的近似解.例如，文獻(xiàn)［4］基于差分進(jìn)化，獲得靜態(tài)采樣下的智能優(yōu)化算法.樣本平均逼近法作為一種近似化處理方法，其采樣次數(shù)不受維數(shù)的影響，但難點(diǎn)是確定合適的樣本大小［5-6］.研究表明，自適應(yīng)采樣較適用于處理期望值規(guī)劃中的隨機(jī)變量［5］，可有效回避因樣本數(shù)過大導(dǎo)致算法尋優(yōu)效率低的問題.另一方面，多模態(tài)函數(shù)優(yōu)化是一類具有多個(gè)局部最優(yōu)解的靜態(tài)優(yōu)化問題，其作為極為困難的優(yōu)化對象已有較多進(jìn)化算法研究成果［7］，主要集中在探討能規(guī)避早熟現(xiàn)象，以及快速發(fā)現(xiàn)全局最優(yōu)解且具有足夠多樣性和強(qiáng)進(jìn)化能力的進(jìn)化算法.特別是將多模態(tài)優(yōu)化轉(zhuǎn)化成兩目標(biāo)優(yōu)化，然后設(shè)計(jì)多目標(biāo)優(yōu)化算法求解是一種較好的嘗試［8-9］.

免疫優(yōu)化作為人工免疫系統(tǒng)的重要研究分支已取得優(yōu)于其它主要智能優(yōu)化算法的眾多研究成果［10-12］.例如，文獻(xiàn)［10］提出求解靜態(tài)多模態(tài)函數(shù)優(yōu)化的人工免疫網(wǎng)絡(luò)算法，該算法的突出特點(diǎn)是進(jìn)化種群中每個(gè)抗體均需繁殖，變異后的克隆群的平均親和力要求不低于當(dāng)前種群的平均親和力，以及利用網(wǎng)絡(luò)抑制清除冗余抗體.文獻(xiàn)［5］針對一般期望值規(guī)劃問題，探討自適應(yīng)采樣和噪聲抑制方案，獲得了免疫優(yōu)化算法.

綜上可知，盡管智能優(yōu)化在期望值規(guī)劃和靜態(tài)多模態(tài)函數(shù)優(yōu)化方面均已有大量研究，但仍然存在很多問題亟需解決，特別是未見探討二者結(jié)合的多模態(tài)期望值規(guī)劃的研究報(bào)道.因此，本文通過引入局部檢測隨機(jī)函數(shù)，將MEVP轉(zhuǎn)化為多目標(biāo)期望值規(guī)劃，探討問題轉(zhuǎn)化的理論基礎(chǔ)，借助克隆選擇和免疫記憶原理，設(shè)計(jì)具有自適應(yīng)采樣的多目標(biāo)免疫優(yōu)化算法（multi-objective immune optimization algorithm，MIOA）.該算法在以下4個(gè)方面不同于已有智能優(yōu)化算法：

（1）通過引入候選解的局部檢測隨機(jī)函數(shù)，將問題轉(zhuǎn)化為多目標(biāo)期望值規(guī)劃，并證明二者的等價(jià)關(guān)系；

（2）自適應(yīng)采樣有效抑制了隨機(jī)變量對尋優(yōu)質(zhì)量的影響；

（3）遞歸非支配分層提高了個(gè)體優(yōu)劣辨別速度；

（4）候選解的方向檢測方案增強(qiáng)了群體局部探測能力.

1 問題描述及轉(zhuǎn)化

考慮如下多模態(tài)期望值規(guī)劃問題

式中：D是Rp中有界閉區(qū)域；

x為決策向量；

ξ∈Rq為隨機(jī)向量；

E［·］是期望值算子；

f（x，ξ）關(guān)于x是多模態(tài)隨機(jī)函數(shù).

稱x*∈D為MEVP的局部最優(yōu)解，若存在x*的鄰域O（x*）?D，使得對于任意的x∈O（x*），均有E［f（x*，ξ）］≤E［f（x，ξ）］；若x*在D上使該不等式成立，則稱為全局最優(yōu)解.鑒于f（x，ξ）具有多模態(tài)和不確定的特性，在此用隨機(jī)函數(shù)g（x，ξ）作為局部檢測函數(shù)來檢測x在期望值意義下是否為局部最優(yōu)解，它滿足在x的鄰域內(nèi)E［g（x*，ξ）］≥0，且等號成立的充要條件是x*為MEVP的局部最優(yōu)解.將MEVP轉(zhuǎn)化為如下期望值多目標(biāo)規(guī)劃問題（expectedvaluemulti-objective programming，EMP）：

定義1 稱x*∈D為EMP的局部有效解，若存在x*的一個(gè)鄰域O（x*），使得不存在y∈O（x*）滿足y支配x*，在此，y支配x*是指

且至少有一個(gè)不等式的等號不成立.

以下理論研究中，不妨設(shè)MEVP有唯一最優(yōu)解，即MEVP僅有一個(gè)局部最優(yōu)解且為全局最優(yōu)解.

定理1x*∈D是MEVP的最優(yōu)解的充要條件是x*是EMP的有效解.

以上表明，在g（x，ξ）的定義下，問題MEVP與EMP具有相同的解.根據(jù)該定義，檢測x是否為局部最優(yōu)解，不僅需要考慮x的鄰域O（x）中的所有點(diǎn)，而且需要考慮隨機(jī)向量ξ的樣本大小，這必然會增大檢測x是否為最優(yōu)解的計(jì)算量.在實(shí)際應(yīng)用中，僅需選擇x的鄰域中部分點(diǎn)進(jìn)行比較即可.為此，給定隨機(jī)向量的樣本ξ，定義

式中：μj（ξ）＝min｛f（x－δ，j，ξ），f（x＋δ，j，ξ）｝，x＋δ，j和x－δ，j分別為x中第j個(gè)分量xj變?yōu)閤j＋δ和xjδ，而其它分量不變時(shí)獲得的兩個(gè)向量；δ為預(yù)先設(shè)定的鄰域閾值.

利用式（2），通過Ij（x，ξ）檢測f（x，ξ）沿著x的第j個(gè)方向的兩個(gè)點(diǎn)是否比x更優(yōu)越.因此，用g（x，ξ）檢測中心為x、半徑為δ的超球面上2p個(gè)點(diǎn)中是否有優(yōu)于x的點(diǎn).可獲得如下結(jié)論：

定理2若x*∈D是MEVP的最優(yōu)解，且滿足對于?x∈D和?ξ∈Rq，均有f（x*，ξ）≤f（x，ξ），則x*∈D是EMP的有效解且滿足E［g（x*，ξ）］＝0.

證明設(shè)x*∈D是MEVP的最優(yōu)解，則對于?x∈D，有E［f（x*，ξ）］≤E［f（x，ξ）］.若x*不是EMP的有效解，則存在ˉx∈D，使得ˉx支配x*，即，

進(jìn)一步，由式（2）知，

又對于?x∈D，有f（x*，ξ）≤f（x，ξ），所以得

此導(dǎo)致矛盾，故結(jié)論成立.

2 樣本平均近似化

假定ξ1，ξ2，…，ξm為隨機(jī)向量ξ的樣本，m為樣本大小，則由大數(shù)定律知，當(dāng)m充分大后，下列多目標(biāo)規(guī)劃問題（sample approximation multiobjective programming，SMP），

的有效解必為EMP的有效解.為了克服計(jì)算代價(jià)過大和尋優(yōu)速度慢的困難，在每個(gè)候選解x處指派隨機(jī)向量的樣本大小為n（x），于是SMP被修改為為自適應(yīng)采樣多目標(biāo)規(guī)劃問題（adaptive sampling multi-objective programming，AMP），

式中：

顯然，若對于?x∈D，n（x）均等于同一常數(shù)，則AMP即為SMP.以下設(shè)計(jì)具有自適應(yīng)采樣特性的免疫優(yōu)化算法求解AMP，使得最終獲得的有效解能盡可能逼近MEVP的最優(yōu)解.

3 算法原理與描述

3.1 算法原理

MIOA由遞歸非支配分層、群體樣本分配、記憶集更新、自適應(yīng)繁殖與變異、群體更新構(gòu)成，其算法流程如圖1所示.

圖1中，n表示迭代次數(shù)，M表示記憶集，Gmax表示最大迭代，遞歸非支配分層是基于遞歸和群體隨機(jī)劃分思想，將群體劃分為若干互不支配的子群；群體樣本分配借助與迭代數(shù)有關(guān)的群體樣本規(guī)模和各抗體的重要程度，確定各抗體的樣本大小，目的在于提高估算優(yōu)質(zhì)抗體的準(zhǔn)確率；記憶集更新將當(dāng)前群體中優(yōu)質(zhì)抗體復(fù)制入記憶集，并清除受支配、相同或相似的記憶細(xì)胞；自適應(yīng)繁殖依據(jù)群體中各抗體的重要程度，按照特定的規(guī)則確定抗體的繁殖規(guī)模，重要程度越高的抗體將得到較大的克隆規(guī)模；克隆變異依據(jù)與抗體重要程度有關(guān)的變異概率執(zhí)行均勻變異；抗體群更新借助已變異的克隆群，對當(dāng)前群體中的抗體進(jìn)行取代或有指導(dǎo)性轉(zhuǎn)變，產(chǎn)生下一代群體.

圖1 MIOA流程圖Fig.1 Flowchart of MIOA

3.2 算法描述

對應(yīng)于以上AMP，抗體由p個(gè)長度均為l的二進(jìn)制基因塊構(gòu)成，每個(gè)基因塊對應(yīng)AMP中決策向量的一個(gè)分量，記憶細(xì)胞視為算法進(jìn)化到當(dāng)前代獲得的較好抗體，抗原被視為問題AMP本身.抗體x的目標(biāo)向量值為給定時(shí)刻n的抗體群

式中：N為群體規(guī)模.

假定xi在該群體中的優(yōu)先等級為r（xi），1≤i≤N，r（xi）越小，xi越好.該群體在時(shí)刻n的采樣大小為

式中：m0為給定的正整數(shù).

在抗體x處的隨機(jī)變量的樣本大小為

式中：m（x）＝rmax－r（x）＋1，

式（7）用于確保群體A中不同等級的抗體獲得不同數(shù)目的樣本，鼓勵(lì)優(yōu)質(zhì)抗體參與進(jìn)化，較差抗體逐漸被淘汰.因此，抗體x的等級r（x）越小，則獲樣本越多；反之，則越少.式（6）和（7）構(gòu)成群體A的樣本分配方案.遞歸的思想最初由文獻(xiàn)［13］將其引入到群體中來尋找一個(gè)子群，使得該子群中任何個(gè)體均不受群體中任何個(gè)體支配.在此基礎(chǔ)上，本文通過引入隨機(jī)抽取的思想，將群體A劃分為若干子集（此方法簡記為遞歸非支配分層），并對A的抗體確定優(yōu)先級，等級越低的抗體，其重要程度越高.假定A中各抗體的目標(biāo)值已確定，首先在A中隨機(jī)選擇一個(gè)抗體x，將A＼｛x｝分為被x支配的抗體構(gòu)成的群體A1和不被x支配的抗體構(gòu)成的群體，獲得有序集合序列A1，｛x｝，；然后，分別對A1，采用同樣方式進(jìn)行劃分，如此繼續(xù)，最終獲得有序的抗體集合序列.

依據(jù)此序列，抗體的優(yōu)先等級確定規(guī)則是，若抗體x處于此序列中最后位置或不被其后面的所有抗體支配，則記其等級為1；否則，排在抗體x后面且支配該抗體的所有抗體中，距離此抗體最近的抗體的等級加1后定義為抗體x的等級.基于此設(shè)計(jì)和圖1，MIOA的具體描述如下：

步驟1輸入：種群規(guī)模N，抗體的各基因塊長度l，初始采樣數(shù)m0，局部檢測閾值δ，記憶集規(guī)模Mmax，抑制半徑σth，最大迭代次數(shù)Gmax.

步驟2置迭代數(shù)n＝0，記憶集M＝?.

步驟3隨機(jī)生成N個(gè)采樣次數(shù)均為m0的抗體構(gòu)成初始種群An＝｛x1，x2，…，xN｝，計(jì)算各抗體的目標(biāo)值

步驟4對An實(shí)施遞歸非支配分層，確定各抗體的優(yōu)先等級r（xi），1≤i≤N.

步驟5依據(jù)式（7）確定An中各抗體的樣本大小，重新計(jì)算各抗體的目標(biāo)值1≤i≤N；執(zhí)行抗體方向檢測，即對于給定抗體x∈An，若沿著x的第k基因塊對應(yīng)的分量方向xk，的偏差值是抗體x沿著各方向獲得的偏差值中的最大值，不妨設(shè)沿著x到xk＋δ的偏差最大，則記x的最大變化方向?yàn)镈k（x）.

步驟6對An再次實(shí)施遞歸非支配分層，確定各抗體的優(yōu)先等級r（x），x∈An.

步驟7復(fù)制An中等級為1的抗體作為記憶細(xì)胞加入M中，清除受支配的記憶細(xì)胞；若則以σth為抑制半徑，清除M中相似的抗體.

步驟8An中各抗體進(jìn)行繁殖，即x繁殖mx個(gè)克隆構(gòu)成克隆群Bn（x），其中

式中：rmax為所有抗體的等級中的最高等級.

步驟9對每個(gè)克隆子群，Bn（x）中的克隆依據(jù)其變異概率px實(shí)施均勻變異，即該抗體的每一基因按概率進(jìn)行變異，

獲群體Cn（x），每個(gè)變異后的克隆被指派樣本大小為m0，計(jì)算Cn（x）中各克隆的目標(biāo)值

步驟10執(zhí)行群體更新：對于每個(gè)克隆群，首先找到Cn（x）中使在此子群中取最小值的所有克隆，這些克隆構(gòu)成群體在 E（x）中取最小的克?。蝗艋蛘?，則An中x被y取代；否則，x沿著最大變化方向Dk（x）的抗體取代x；如此繼續(xù)，對An中每個(gè)抗體更新后，獲得新群體An＋1.

步驟11若n＜Gmax，則n←n＋1，轉(zhuǎn)步驟4；否則，轉(zhuǎn)下一步.

步驟12輸出：M中滿足的所有記憶細(xì)胞.

4 計(jì)算復(fù)雜度與評價(jià)準(zhǔn)則

由算法描述可知，MIOA的計(jì)算復(fù)雜度由步驟4～5、步驟7及步驟9～10確定.在最壞情形下，步驟4、步驟5和步驟7的計(jì)算復(fù)雜度依次為O（Nlb N）、O（Np＋Mn）和O（（N＋Mmax）2）；通常m0取較小值，所以，步驟9的計(jì)算復(fù)雜度為O（Np）；另外，隨著n的增大，An中的抗體將互不支配，于是步驟10的計(jì)算復(fù)雜度為O（N）.故MIOA在最壞情形的復(fù)雜度為

特別當(dāng)Mmax?N時(shí)，

Oc＝O（N（N＋p＋lb（1＋n／10）））.

假定某算法求解MEVP獲的最好解集為A，理論最優(yōu)解集為A*.給出如下解集平均逼近度準(zhǔn)則：

式中：d（x，A）為x到集合A的距離；

D（A，A*）為A中所有成員逼近局部或全局最優(yōu)解的程度；

D（A*，A）度量A*逼近A的程度.

5 數(shù)值實(shí)驗(yàn)與分析

選擇5種可求解期望值規(guī)劃的智能優(yōu)化算法，在CPU／3.3 GHZ、RMB／4 GB的PC機(jī)和VC＋＋6.0環(huán)境下進(jìn)行比較分析，即3種單目標(biāo)優(yōu)化算法（PSO、DE［4］、CPSO［6］）和兩種多目標(biāo)算法（NSGA-Ⅱ［14］、PDMIOA［15］）.PSO、DE和CPSO求解MEVP的樣本平均近似化模型；NSGA-II和PDMIOA求解SMP；本文算法求解AMP.各算法對每個(gè)測試問題分別獨(dú)立運(yùn)行30次，且設(shè)定群體規(guī)模N均為80，終止準(zhǔn)則指定為個(gè)體的總評價(jià)次數(shù).

具體設(shè)置描述如下：參與比較的算法的單個(gè)個(gè)體的采樣大小均指定為300；DE和CPSO的其他參數(shù)設(shè)置與文獻(xiàn)［4，6］相同；NSGA-Ⅱ的交叉概率為0.6，變異概率為0.06；PDMIOA的變異概率為0.2，生命期為3，記憶集規(guī)模Mmax為200；設(shè)MIOA的初始采樣數(shù)m0為50，局部檢測閾值δ為0.05，記憶集規(guī)模Mmax為200，抑制半徑σth為0.05.

問題1 MMP（p）

式中：0≤xi≤1，1≤i≤p.

問題1是通過修改文獻(xiàn)［8］的測試函數(shù)為隨機(jī)函數(shù)獲得的，其中，ξ為隨機(jī)變量，ki為給定常數(shù).該問題在靜態(tài)情形下，當(dāng)ki取特定值時(shí)，其所有最優(yōu)解已有報(bào)道［8］，因此，本實(shí)驗(yàn)中假定ξ是服從方差為σ正態(tài)分布的隨機(jī)變量，即ξ～N（0，σ2），此有助于檢測算法是否獲得最優(yōu)解.在此，僅考慮維數(shù)取p＝2和8的情形，相應(yīng)的優(yōu)化問題記為MMP（2）和MMP（8）.

以上每種算法求解這兩問題的總評價(jià)次數(shù)分別為2.4×104和2.4×106.MMP（2）有12個(gè)解，其全局最優(yōu)解的理論目標(biāo)值為0.290 8；MMP（8）有48個(gè)解，其全局最優(yōu)解理論目標(biāo)值為2.768 2.取σ＝1，結(jié)合式（10）和（11），得到的統(tǒng)計(jì)結(jié)果見表1.

表1第3、4列表明，當(dāng)以上算法求解MMP（2）時(shí)，MIOA始終能獲所有最優(yōu)解，其它算法僅能獲得少量的最優(yōu)解；當(dāng)求解MMP（8）時(shí)，MIOA平均每次能獲得約45個(gè)最優(yōu)解，獲所有最優(yōu)解的次數(shù)占3.33%，而其它算法每次獨(dú)立運(yùn)行均不能獲得所有最優(yōu)解，特別是因算法設(shè)計(jì)不同，PSO、DE和CPSO每次僅能獲得1個(gè)最優(yōu)解.

表1第7、10列表明，MIOA獲得的解集質(zhì)量最好，它每次獲得的解集與理論上的最優(yōu)解集非常接近，NSGA-Ⅱ和PDMIOA獲得的解集質(zhì)量次之，其它算法獲得的解質(zhì)量較差.這說明將多模態(tài)期望值優(yōu)化問題轉(zhuǎn)化成多目標(biāo)問題求解，有利于求解全局最優(yōu)解.

由表1第8、11列可知，MIOA搜索效果較為穩(wěn)定，PDMIOA次之；因PSO、DE和CPSO在每次運(yùn)行中僅獲1個(gè)最優(yōu)解，而求解的問題包含多個(gè)最優(yōu)解，所以它們獲得的D（A*，A）值較大，得到D（A，A*）的標(biāo)準(zhǔn)差為0.

表1中最后1列表明，MIOA的執(zhí)行效率比NSGA-Ⅱ和PDMIOA的效率均高，這說明自適應(yīng)采樣和遞歸非支配分層能極大提高M(jìn)IOA的執(zhí)行效率，而固定采樣和常規(guī)的非支配分層方法會導(dǎo)致算法搜索效率低；另一方面，PSO、DE和CPSO作為單目標(biāo)優(yōu)化算法，其設(shè)計(jì)模塊比多目標(biāo)優(yōu)化算法的要簡單，因此效率較高是自然的，但在搜索多個(gè)解方面要比多目標(biāo)優(yōu)化算法差.

表1 逼近程度統(tǒng)計(jì)結(jié)果比較Tab.1 Statistical comparison of approximation degrees

問題2硬盤隨機(jī)控制系統(tǒng)參數(shù)辨識［5］磁頭臂控制系統(tǒng)的數(shù)學(xué)模型如下：

式中：uc為參考信號；

y為輸出信號；

Nd服從正態(tài)分布N（0，σ2）；

a、b、Kv、K、J為待定參數(shù).

取采樣步數(shù)為L，采樣周期為T，將系統(tǒng)（式（12））離散化可得

式中：yd為參考輸出，

θ為決策向量，

θ＝（a，b，Kv，K，J）；

ξ為隨機(jī)向量，

ξ＝（ξ1，ξ2，…，ξL），ξi與Nd具有相同的分布.

設(shè)置a，b∈［0.1，10］，Kv，K∈［－10，10］，J∈［0.01，2］，

各算法的終止評價(jià)次數(shù)均設(shè)為2.4×104.類似于問題1的實(shí)驗(yàn)，各算法獨(dú)立運(yùn)行30次后，獲得的統(tǒng)計(jì)結(jié)果見表2.

由表2可知，NSGA-Ⅱ和PDMIOA獲得的目標(biāo)函數(shù)值的均值和標(biāo)準(zhǔn)差均較大，說明這兩種算法的解質(zhì)量已受到噪聲的嚴(yán)重干擾，搜索效果不穩(wěn)定；PSO、DE和CPSO的目標(biāo)均值和標(biāo)準(zhǔn)差比NSGA-Ⅱ和PDMIOA均較小，它們的搜索效果比后兩種多目標(biāo)優(yōu)化算法更為穩(wěn)定；MIOA獲得的目標(biāo)值的均值和標(biāo)準(zhǔn)差均最?。灰虼?，獲得的效果最好且最穩(wěn)定.

表2 解的目標(biāo)值統(tǒng)計(jì)結(jié)果比較Tab.2 Comparison of statistical results for objective values of solutions acquired

6 結(jié)束語

通過引入局部檢測隨機(jī)函數(shù)，將求解問題轉(zhuǎn)化為多目標(biāo)期望值規(guī)劃，并根據(jù)向量支配的概念，獲得一定的理論結(jié)果.在此基礎(chǔ)上，基于克隆選擇原理的簡化運(yùn)行機(jī)制，設(shè)計(jì)了多目標(biāo)免疫優(yōu)化算法.為克服隨機(jī)變量和群體中抗體的比較影響算法搜索效率的現(xiàn)象，設(shè)計(jì)遞歸非支配分層、樣本自適應(yīng)采樣方案和自適應(yīng)繁殖與變異方案，有引導(dǎo)性地使進(jìn)化群體沿著優(yōu)質(zhì)抗體所在區(qū)域轉(zhuǎn)移.實(shí)驗(yàn)結(jié)果表明，該算法求解理論測試問題時(shí)，能獲得滿意效果，且解的質(zhì)量基本不受隨機(jī)因素的干擾；在求解應(yīng)用測試問題時(shí)，能獲得最佳參數(shù)值.

［1］ JIN Y，BRANKEJ.Evolutionaryoptimizationin uncertain environments-a survey［J］.IEEE Transactions on Evolutionary Computation，2005，9（3）：303-317.

［2］ LIUB.Theoryandpracticeofuncertain programming［M］.Berlin：Springer，2009：25-53.

［3］ SHAPIRO A，DENTCHEVA D，RUSZCZYNSKI A.Lectures onstochasticprogramming：modelingand theory［M］.Philadelphia：SIAM，2009：157-195.

［4］ 孫瀅，高岳林.一種求解隨機(jī)期望值模型的改進(jìn)差分進(jìn)化算法［J］.微電子學(xué)與計(jì)算機(jī)，2012，29（4）：23-25.SUN Ying，GAO Yuelin.An improved differential evolutionalgorithmofstochasticexpectedvalue models［J］.Microelectronics＆Computer，2012，29（4）：23-25.

［5］ ZHANG Z H，TU X.Immune algorithm with adaptive sampling in noisy environments and its application to stochastic optimization problems［J］.IEEE Computational Intelligence Magazine，2007，2（4）：29-40.

［6］ MENDEL E，KROHLING R A，CAMPOS M.Swarm algorithmswithchaoticjumpsappliedtonoisy optimization problems［J］.Information Sciences，2011，181（20）：4494-4514.

［7］ DAS S，MAITY S，QU B Y，et al.Real-parameter evolutionary multimodal optimization：a survey of the state-of-the-art［J］.Swarm and Evolutionary Computation，2011，1（2）：71-88.

［8］ DEB K，SAHA A.Finding multiple solutions for multimodal optimization problems using a multi-objective evolutionary approach［C］∥Proceedings of the 12th AnnualConferenceonGeneticandEvolutionary Computation.New York：ACM，2010：447-454.

［9］ YAO J，KHARMA N，GROGONO P.Bi-objective multipopulationgeneticalgorithmformultimodal functionoptimization［J］.IEEETransactionson Evolutionary Computation，2010，14（1）：80-102.

［10］ TIMMIS J，EDMONDS C.A comment on opt-ainet：an immune network algorithm for optimization［C］∥Genetic and Evolutionary Computation-GECCO 2004.Berlin：Springer，2004：308-317.

［11］ DASGUPTA D，YU S，NINO F.Recent advances in artificial immune systems：models and applications［J］.Applied Soft Computing，2011，11（2）：1574-1587.

［12］ CHANG W W，YEH W C，HUANG P C.A hybrid immune-estimation distribution of algorithm for mining thyroidglanddata［J］.ExpertSystemswith Applications，2010，37（3）：2066-2071.

［13］ ZHENG J H，LING C，SHI Z，et al.A multi-objective genetic algorithm based on quick sort［C］∥Advances in Artificial Intelligence.Berlin：Springer，2004：175-186.

［14］ DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multiobjective genetic algorithm：NSGA-Ⅱ［J］.IEEETransactionsonEvolutionaryComputation，2002，6（2）：182-197.

［15］ ZHANG Z H，TU X.Probabilistic dominance based multi-objective immune optimization algorithm in noisy environments［J］.JournalofComputationaland Theoretical Nanoscience，2007，4（7／8）：1380-1387.

（中文編輯：秦萍玲 英文編輯：蘭俊思）

Single-Objective Multi-modal Expected Value Programming Based on Immune Optimization

YANG Kai1， ZHANG Zhuhong1，2
（1.College of Computer Science and Technology，Guizhou University，Guiyang 550025，China；2.College of Electronics and Information，Guizhou University，Guiyang 550025，China）

To solve the problem of single-objective multi-modal expected value programming with unknown noisy distribution，a multi-objective immune optimization algorithm based on immune response principles was proposed.By means of a random function used for checking whether a candidate solution was a locally optimal solution，the expected value problem was converted into a multi-objective expected value programming problem.Moreover，some relations between the original problem and the transformed problem were studied，and a conclusion that an efficient solution must be an optimal solution under certain conditions was developed.Relying upon the idea of sample average approximation，the multi-objective programming was further transformed into an approximate model with variable sampling sizes.Based on the metaphors of clonal selection and immune memory，one such optimization approach was obtained to deal with the approximation model.It searched high-quality individuals toward some regions which the optimal solutions existed，depending on several main modules：recursive non-dominated sorting，adaptive sampling，adaptive proliferation，and adaptive mutation.By comparison with the multi-objective optimization algorithms，the simulation results show that the proposed algorithm with strong noise suppression can achieve averagely about a seventy percent increase in the number of optimal solutions found for the high-dimensional benchmark problem and atwenty percent increase for the low-dimensional benchmark problem；it can gain the stable search effect and has the prominent advantage in solving multiple optimal solutions.

stochastic programming；multi-modal expected value programming；multi-objective optimization；immune optimization；adaptive sampling

TP301.6

：A

0258-2724（2014）06-1061-07

10.3969／j.issn.0258-2724.2014.06.018

2013-10-12

國家自然科學(xué)基金資助項(xiàng)目（61065010）；教育部博士點(diǎn)基金資助項(xiàng)目（20125201110003）

楊凱（1975－），男，博士研究生，研究方向?yàn)槊庖邇?yōu)化理論與應(yīng)用，E-mail：csc.kyang＠gzu.edu.cn

張著洪（1966－），男，教授，博士，博士生導(dǎo)師，研究方向?yàn)榭刂评碚撆c計(jì)算智能，E-mail：sci.zhzhang＠gzu.edu.cn

楊凱，張著洪.基于免疫優(yōu)化的單目標(biāo)多模態(tài)期望值規(guī)劃［J］.西南交通大學(xué)學(xué)報(bào)，2014，49（6）：1061-1067.