求解多目標概率優化問題的免疫優化算法

張仁崇　楊坤

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

【關鍵詞】多目標概率優化;免疫優化;動態采樣

中圖分類號：TP301.6 文獻標識碼： A 文章編號： 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

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

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

1 問題描述

考慮如下多目標概率優化問題[7]（多目標P-模型）：

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

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

定義2 候選解x*∈D是問題（多目標P-模型）的Pareto最優解，若在D中不存在候選解x使得x？芻y。

2 算法描述

免疫應答原理[9-10]描述識別抗原能力強的免疫細胞被選擇參與應答，抑制或消滅抗原受體，以至于清除入侵的抗原的過程。借助免疫應答原理，設計免疫優化算法求解多目標P-模型。為便于算法描述，將此問題本身視為抗原，候選解被視為B細胞，MOIOA可描述如下：

步1輸入參數：群體規模N，最大迭代數Gmax，初始樣本大小m和M，記憶集合規模N0，募集新成員比例λ;

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

步3采用快速非支配排序法，將種群A排序為d個不同支配等級，相對應獲得d個子群B1，B2，...，Bd;其中，B1由A的所有經驗非支配B細胞構成;

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

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

步6依據步2，初步估計B*中B細胞的目標向量值;借助定義1，將B*劃分為經驗非支配子群C1和經驗支配子群C2;將C1與B1的B細胞組合構成群體C;步7依據m和如下式：

將式（2）中M用Mn取代，重新估計C中B細胞的目標向量值;

步8借助定義1，將群體C分割為經驗非支配子群D1和經驗支配子群D2;

步9清除記憶集合G中與D1相同的個體后，加入D1的B細胞;若|G|>N0，保留N0個優質B細胞;

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

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

3 數值實驗

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

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

測試問題[15]：

式中，α為置信水平，N（.，.）為正態分布。該測試問題是經標準函數KUR擴展獲得，目標函數具有多模態特性，且目標函數含有噪聲，致使問題求解非常困難。在置信水平α=0.1、0.9下，各算法對測試問題獨立運行100次獲得的統計結果和平均運行時間如表1所示。注：表中ACR（.，.）、CS、CS分別表示平均覆蓋率、平均覆蓋范圍、平均覆蓋寬度[6]，PN和AR分別表示非支配解集規模均值和平均執行時間。

經由表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所獲解質量最好，且略優于MOIOA和NNIA，AgMOPSO、MOEA/DD和NSGA-II的解質量相對較低。

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

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

4 結論

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

【參考文獻】

[1]李曉娜.不確定環境下城市需水量預測及多水源聯合供水調度研究[D].河北工程大學，2018.

[2]紀昌明，李克飛，張驗科，等.基于機會約束的水庫調度隨機多目標決策模型[J].電力系統保護與控制，2012（19）：36-40.

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

[4]謝仕煒，胡志堅，寧月.考慮最優負荷削減方向的電網多目標分層隨機機會約束規劃[J].電力自動化設備，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]于善謙，王洪海，朱乃碩，等.免疫學導論[M].北京：高等教育出版社，2006.

[10]黃席樾，張著洪，胡小兵，等.現代智能算法理論及應用[M].北京：科學出版社，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.