求解多目標(biāo)概率優(yōu)化問(wèn)題的免疫優(yōu)化算法

張仁崇　楊坤

【摘 要】探討求解隨機(jī)變量分布特征信息未知情形下多目標(biāo)概率優(yōu)化問(wèn)題的免疫優(yōu)化算法。在算法設(shè)計(jì)中，基于免疫理論的運(yùn)行機(jī)理，借助快速非支配排序法，將進(jìn)化種群分割為多個(gè)類型子群;利用模擬二進(jìn)制交叉加強(qiáng)各子群間的信息交流;采用多項(xiàng)式變異和均勻變異展開全局探索和局部開發(fā);設(shè)計(jì)樣本采樣方案使個(gè)體動(dòng)態(tài)獲取樣本大小。比較性的數(shù)值實(shí)驗(yàn)表明，所提算法的搜索效果、運(yùn)行效率等具有明顯優(yōu)勢(shì)，且對(duì)求解復(fù)雜多目標(biāo)概率優(yōu)化具有一定應(yīng)用潛力。

【關(guān)鍵詞】多目標(biāo)概率優(yōu)化;免疫優(yōu)化;動(dòng)態(tài)采樣

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 2095-2457（2019）16-0008-003

DOI：10.19694/j.cnki.issn2095-2457.2019.16.003

Immune Optimization Algorithm for Solving Multi-objective Probabilistic Optimization Problems

ZHANG Ren-chong YANG Kun

（Computer and Information Engineering College，Guizhou University of Commerce，

Guiyang Guizhou 551400，China）

【Abstract】The immune optimization algorithm for multi-objective probabilistic optimization problem with unknown distribution characteristic information of random variables is proposed. In the algorithm design， based on the operation mechanism of immune theory，the evolutionary population is divided into several sub-populations by means of fast nondominated sorting approach;information exchange among sub-populations is strengthened by simulated binary crossover; global exploration and local development are carried out by using polynomial mutation and uniform mutation;and sample sampling scheme is designed to dynamically acquire the sample size. The comparative numerical experiments show that the proposed algorithm has obvious advantages in search effect and operation efficiency， and has certain application potential for solving complex multi-objective probabilistic optimization.

【Key words】Multi-objective probabilistic optimization;Immune optimization;Immune theory;Dynamic sampling

多目標(biāo)機(jī)會(huì)約束規(guī)劃是多個(gè)性能指標(biāo)相互沖突的隨機(jī)規(guī)劃問(wèn)題，依據(jù)目標(biāo)函數(shù)表現(xiàn)的形式可分為，以期望值函數(shù)為目標(biāo)函數(shù)的多目標(biāo)E-模型，以及目標(biāo)函數(shù)為概率約束函數(shù)的多目標(biāo)P-模型。大量實(shí)際工程優(yōu)化問(wèn)題均可經(jīng)由多目標(biāo)P-模型加以描述和解決，例如，水資源調(diào)度[1-2]、空降作戰(zhàn)[3]、電網(wǎng)[4]、動(dòng)力配煤規(guī)劃、證券投資、項(xiàng)目管理以及醫(yī)療管理等問(wèn)題[5-6]。當(dāng)隨機(jī)變量（簡(jiǎn)稱噪聲）的概率分布信息已知時(shí)，少量特殊的多目標(biāo)P-模型能經(jīng)過(guò)復(fù)雜變換化為確定性多目標(biāo)優(yōu)化模型，進(jìn)而采用靜態(tài)優(yōu)化方法求解，但此類方法通常是難以實(shí)現(xiàn)。當(dāng)隨機(jī)變量的分布函數(shù)極為復(fù)雜或分布特征未知時(shí)，模型很難轉(zhuǎn)化為確定性優(yōu)化模型;針對(duì)此種情形，多目標(biāo)P-模型的目標(biāo)函數(shù)的估計(jì)值與隨機(jī)變量的樣本大小有關(guān)，因此，探討搜索速度快、解質(zhì)量高、極具應(yīng)用潛力的智能優(yōu)化方法是多目標(biāo)P-模型求解的關(guān)鍵。

然而，從智能優(yōu)化的角度研究求解多目標(biāo)P-模型的研究成果未見報(bào)道。但針對(duì)特定領(lǐng)域的可描述為多目標(biāo)P-模型的工程優(yōu)化問(wèn)題的研究已有部分成果，主要是在隨機(jī)變量的樣本大小固定（即靜態(tài)采樣）的情形下，采用單目標(biāo)、多目標(biāo)遺傳算法進(jìn)行有效求解，但由于運(yùn)行效率低、計(jì)算資源開銷大，致使其尚不能滿足工程領(lǐng)域的需求，較難被廣泛推廣。為此，本文針對(duì)無(wú)先驗(yàn)噪聲分布信息的多目標(biāo)P-模型，借助免疫應(yīng)答原理，嘗試研究求解此類模型的多目標(biāo)免疫優(yōu)化算法（MOIOA：Multi-Objective Immune Optimization Algorithm）。

1 問(wèn)題描述

考慮如下多目標(biāo)概率優(yōu)化問(wèn)題[7]（多目標(biāo)P-模型）：

在此，x為決策向量，D∈Rp為有界閉區(qū)域，ξ∈Rq為分布信息未知的隨機(jī)向量，Pr{.}為概率算子，αi∈[0，1]是置信水平，fi（x，ξ）關(guān)于x的非線性隨機(jī)目標(biāo)函數(shù)。在點(diǎn)x處，當(dāng)ξ的樣本大小確定后，借助Monte Carlo 隨機(jī)模擬確定fi（x）的估計(jì)值[7]。引入候選解的支配概念及Pareto最優(yōu)解的概念[8]：

定義1對(duì)于任意候選解x，y∈D稱x支配y（即x？芻y），如果

定義2 候選解x*∈D是問(wèn)題（多目標(biāo)P-模型）的Pareto最優(yōu)解，若在D中不存在候選解x使得x？芻y。

2 算法描述

免疫應(yīng)答原理[9-10]描述識(shí)別抗原能力強(qiáng)的免疫細(xì)胞被選擇參與應(yīng)答，抑制或消滅抗原受體，以至于清除入侵的抗原的過(guò)程。借助免疫應(yīng)答原理，設(shè)計(jì)免疫優(yōu)化算法求解多目標(biāo)P-模型。為便于算法描述，將此問(wèn)題本身視為抗原，候選解被視為B細(xì)胞，MOIOA可描述如下：

步1輸入?yún)?shù)：群體規(guī)模N，最大迭代數(shù)Gmax，初始樣本大小m和M，記憶集合規(guī)模N0，募集新成員比例λ;

步2置n←1，G=？覫， 隨機(jī)產(chǎn)生規(guī)模為N的初始B細(xì)胞群A={x1，x2，…，xN};依據(jù)m、M及式（2）， 估計(jì)A中各B細(xì)胞x的目標(biāo)向量值

步3采用快速非支配排序法，將種群A排序?yàn)閐個(gè)不同支配等級(jí)，相對(duì)應(yīng)獲得d個(gè)子群B1，B2，...，Bd;其中，B1由A的所有經(jīng)驗(yàn)非支配B細(xì)胞構(gòu)成;

步4B1的B細(xì)胞繁殖3個(gè)克隆，B2的B細(xì)胞繁殖2個(gè)克隆;Bi中B細(xì)胞的變異概率pi如下：

步5G的經(jīng)驗(yàn)非支配B細(xì)胞指導(dǎo)B1中克隆實(shí)施模擬二進(jìn)制交叉（SBX），Bi-1的B細(xì)胞指導(dǎo)Bi中B細(xì)胞（或克?。?shí)施SBX，i=2，…，d;經(jīng)SBX后，B1和B2中B細(xì)胞的克隆實(shí)施多項(xiàng)式變異，變異分布指數(shù)取ηmlg（1+10n/Gmax）+1，B3，…，Bd的B細(xì)胞實(shí)施均勻變異，獲得交叉、變異后的群體B*;

步6依據(jù)步2，初步估計(jì)B*中B細(xì)胞的目標(biāo)向量值;借助定義1，將B*劃分為經(jīng)驗(yàn)非支配子群C1和經(jīng)驗(yàn)支配子群C2;將C1與B1的B細(xì)胞組合構(gòu)成群體C;步7依據(jù)m和如下式：

將式（2）中M用Mn取代，重新估計(jì)C中B細(xì)胞的目標(biāo)向量值;

步8借助定義1，將群體C分割為經(jīng)驗(yàn)非支配子群D1和經(jīng)驗(yàn)支配子群D2;

步9清除記憶集合G中與D1相同的個(gè)體后，加入D1的B細(xì)胞;若|G|>N0，保留N0個(gè)優(yōu)質(zhì)B細(xì)胞;

步10將G的經(jīng)驗(yàn)非支配B細(xì)胞構(gòu)成E，若|E|≥（1-λ）N，則基于擁擠距離采用輪盤選擇法隨機(jī)選取E中（1-λ）N個(gè)相異的B細(xì)胞與λN個(gè)隨機(jī)生成的B細(xì)胞組合成規(guī)模為N的新群體A;若|E|<（1-λ）N，E中B細(xì)胞、N-|E|個(gè)隨機(jī)生成的B細(xì)胞組合成規(guī)模為N的新群體A;此外，個(gè)體的擁擠距離越大，被選擇進(jìn)入下一代群體的概率也越大;

步11若滿足終止條件，則結(jié)束，輸出結(jié)果;否則，置n←n+1，轉(zhuǎn)步3。

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

在Windows 7系統(tǒng)配置為CPU/2.53 GHz、RAM/4.00GB的Visual C++平臺(tái)上進(jìn)行數(shù)值實(shí)驗(yàn)。將MOIOA與AgMOPSO[11]、MOEA/DD[12]、CMIGA[13]、NNIA[14]和NSGA-II[15]進(jìn)行性能比較。算法終止準(zhǔn)則均設(shè)置為進(jìn)化代數(shù)是300，比較算法的個(gè)體樣本大小設(shè)置為300[16]。為使得算法獲得的解集的目標(biāo)向量值逼近真實(shí)值，各算法所獲解集均需重新估計(jì)目標(biāo)向量值，樣本大小為104。

參與比較算法的參數(shù)設(shè)置如表1：群體規(guī)模N，克隆規(guī)模NC，交叉概率pc，變異概率pm，SBX分布指數(shù)ηc，多項(xiàng)式變異分布指數(shù)ηm，步長(zhǎng)參數(shù)F2，權(quán)重向量的領(lǐng)域集規(guī)模T，懲罰參數(shù)PBI，選擇概率δ，飛行速度慣性權(quán)重w，基因片段池規(guī)模nseg，基因片段長(zhǎng)度lseg，轉(zhuǎn)換概率ptra。經(jīng)調(diào)試后，MOIOA的參數(shù)設(shè)置為N=10，m=2，M=10，nm=23，λ=0.1。采用記憶集規(guī)模為50保存各算法所獲結(jié)果。此外，MOIOA算法執(zhí)行多項(xiàng)式變異參考文獻(xiàn)[17]。

測(cè)試問(wèn)題[15]：

式中，α為置信水平，N（.，.）為正態(tài)分布。該測(cè)試問(wèn)題是經(jīng)標(biāo)準(zhǔn)函數(shù)KUR擴(kuò)展獲得，目標(biāo)函數(shù)具有多模態(tài)特性，且目標(biāo)函數(shù)含有噪聲，致使問(wèn)題求解非常困難。在置信水平α=0.1、0.9下，各算法對(duì)測(cè)試問(wèn)題獨(dú)立運(yùn)行100次獲得的統(tǒng)計(jì)結(jié)果和平均運(yùn)行時(shí)間如表1所示。注：表中ACR（.，.）、CS、CS分別表示平均覆蓋率、平均覆蓋范圍、平均覆蓋寬度[6]，PN和AR分別表示非支配解集規(guī)模均值和平均執(zhí)行時(shí)間。

經(jīng)由表2的CR（.，.）值可知，在置信水平α=0.1下，CMIGA平均覆蓋率最高，MOIOA次之且略低于CMIGA，MOIOA高于NNIA，AgMOPSO和NSGA-II相近且高于MOEA/DD;在置信水平α=0.9下，CMIGA平均覆蓋率最高，MOIOA和NNIA相近且稍低于CMIGA，MOEA/DD和AgMOPSO較低但略高于NSGA-II;以上分析表明，算法CMIGA所獲解質(zhì)量最好，且略優(yōu)于MOIOA和NNIA，AgMOPSO、MOEA/DD和NSGA-II的解質(zhì)量相對(duì)較低。

經(jīng)由CD、CS的平均值、均方差可知，各算法所獲非支配解的覆蓋范圍、覆蓋寬度相近且較低，表明所有算法所獲解的分布情況較好且相貼近。進(jìn)一步，由PN的平均值得知，每種算法所獲非支配解的數(shù)量較多，其中AgMOPSO稍低于其他算法。此外，由表中AR值獲知，MOIOA的運(yùn)行效率最高，是AgMOPSO的5.53倍、MOEA/DD的4.37倍、CMIGA的4.46倍、NNIA 的3.09倍、NSGA-II的2.30倍。

以上綜合分析表明，MOIOA與比較算法均能有效求解具有多模態(tài)特性的多目標(biāo)P-模型，所獲非支配解集的分布性較好、解質(zhì)量較高，但MOIOA運(yùn)算速度最快，是比較算法的2.3倍以上。

4 結(jié)論

鑒于多目標(biāo)P-模型頻繁出現(xiàn)于經(jīng)濟(jì)、軍工、水資源、工程等領(lǐng)域，已受到高度關(guān)注。本文從免疫應(yīng)答機(jī)理出發(fā)，嘗試性探討求解多目標(biāo)概率優(yōu)化問(wèn)題的免疫優(yōu)化算法。算法設(shè)計(jì)中，設(shè)計(jì)樣本分配方案使個(gè)體動(dòng)態(tài)獲取樣本大小，利用快速非支配排序法分割進(jìn)化種群為多個(gè)不同類型子群，采用SBX加強(qiáng)各子群間個(gè)體信息交流，設(shè)計(jì)動(dòng)態(tài)變異概率、變異指數(shù)動(dòng)態(tài)變化的多項(xiàng)式變異指導(dǎo)個(gè)體進(jìn)化，確保進(jìn)化種群具有全局搜索和局部開發(fā)能力。該算法運(yùn)行初期，個(gè)體樣本規(guī)模小、運(yùn)行速度快、搜索范圍寬;隨著算法運(yùn)行，個(gè)體樣本規(guī)模增大，局部開發(fā)能力增強(qiáng)，優(yōu)質(zhì)非支配解逐漸突顯。比較性的數(shù)值實(shí)驗(yàn)表明，相比較于其他算法，MOIOA的搜索效果和運(yùn)行效率均有明顯優(yōu)勢(shì)，是一種具有競(jìng)爭(zhēng)力的優(yōu)化方法。此外，算法進(jìn)化模塊、噪聲抑制效果以及樣本分配方案做下一步研究。

【參考文獻(xiàn)】

[1]李曉娜.不確定環(huán)境下城市需水量預(yù)測(cè)及多水源聯(lián)合供水調(diào)度研究[D].河北工程大學(xué)，2018.

[2]紀(jì)昌明，李克飛，張驗(yàn)科，等.基于機(jī)會(huì)約束的水庫(kù)調(diào)度隨機(jī)多目標(biāo)決策模型[J].電力系統(tǒng)保護(hù)與控制，2012（19）：36-40.

[3]張國(guó)新，王瑜，沈田雙.空降地面作戰(zhàn)突破點(diǎn)決策模型[J].火力與指揮控制，2010，35（11）：54-57.

[4]謝仕煒，胡志堅(jiān)，寧月.考慮最優(yōu)負(fù)荷削減方向的電網(wǎng)多目標(biāo)分層隨機(jī)機(jī)會(huì)約束規(guī)劃[J].電力自動(dòng)化設(shè)備，2017，37（8）：35-42.

[5]ZHANG Z， WANG L， LONG F. Immune optimization approach solving multi-objective chance-constrained programming[J].Evolving Systems，2013，6（1）：41-53.

[6]YANG K， ZHANG Z， LU J. Adaptive racing ranking-based immune optimization approach solving multi-objective expected value programming[J]. Soft Computing，2017：1-20.

[7]LIU B D. Theory and Practice of Uncertain Programming[M]. 2nd ed. Berlin： Springer-Varlag，2009.

[8]ZHANG Z，TU X.Probabilistic dominance-based multi-objective immune optimization algorithm in noisy environments[J].Journal of Computational and Theoretical Nanoscience，2007，4（7）：1380-1387.

[9]于善謙，王洪海，朱乃碩，等.免疫學(xué)導(dǎo)論[M].北京：高等教育出版社，2006.

[10]黃席樾，張著洪，胡小兵，等.現(xiàn)代智能算法理論及應(yīng)用[M].北京：科學(xué)出版社，2005.

[11]ZHU Q， LIN Q， CHEN W， et al. An external archive-guided multiobjective particle swarm optimization algorithm[J]. IEEE Transactions on Cybernetics，2017，47（9）：2794-2808.

[12]LI K， DEB K， ZHANG Q， et al. An evolutionary many-objective optimization algorithm based on dominance and decomposition[J].IEEE Transactions on Evolutionary Computation， 2015，19（5）：694-716.

[13]QIAN S， YE Y， JIANG B， et al. Constrained multiobjective optimization algorithm based on immune system model[J].IEEE Transactions on Cybernetics，2015，46（9）：2056-2069.

[14]GONG M， JIAO L， DU H， et al. Multiobjective immune algorithm with nondominated neighbor-based selection[J]. Evolutionary Computation，2008，16（2）：225-255.

[15]DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm：NSGA-II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

[16]POOJARI C A， VARGHESE B. Genetic algorithm based technique for solving chance constrained problems[J].European Journal of Operational Research，2008，185（3）：1128-1154.

[17]LIN Q， CHEN J， ZHAN Z H， et al. A hybrid evolutionary immune algorithm for multiobjective optimization problems[J].IEEE Transactions on Evolutionary Computation， 2016，20（5）：711-729.