非線性多目標(biāo)概率約束規(guī)劃免疫優(yōu)化算法

張仁崇，張著洪

（1.貴州商學(xué)院 計算機(jī)與信息工程學(xué)院，貴陽550014； 2.貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴陽550025）

工程優(yōu)化設(shè)計中，諸如水資源調(diào)度［1］、再制造加工［2］、電 網(wǎng)［3］、養(yǎng) 分 負(fù) 荷 消 減［4］等 問 題 均 可通過性能指標(biāo)是相互沖突且滿足概率約束限制的多目標(biāo)概率約束規(guī)劃（Multi-Objective Probabilistic Constrained Programming，MOPCP）加以描述。當(dāng)隨機(jī)變量的概率分布信息已知時，可將此類問題轉(zhuǎn)化為等價的確定性多目標(biāo)約束規(guī)劃問題，進(jìn)而可利用數(shù)學(xué)規(guī)劃方法或靜態(tài)多目標(biāo)智能優(yōu)化算法求解［5］?？墒?，在應(yīng)用中，由于隨機(jī)變量或噪聲的分布常是未知的，導(dǎo)致模型的等價轉(zhuǎn)換變得不可能。一旦賦予隨機(jī)變量較大的樣本容量，可經(jīng)由靜態(tài)多目標(biāo)智能優(yōu)化算法求解問題的解，但計算開銷大，執(zhí)行效率低。當(dāng)隨機(jī)變量的概率分布已知時，如正態(tài)分布或指數(shù)分布，機(jī)會約束可通過復(fù)雜的轉(zhuǎn)換變?yōu)榇_定性的約束條件［6-10］；與此同時，重要采樣［11］、拉丁超立方采樣［12］能被用于估計機(jī)會約束的概率，但效率低，估計偏差大。蒙特卡羅（Monte Carlo，MC）隨機(jī)模擬是一種易于實現(xiàn)且不受限于噪聲先驗信息的期望值估計方法?；诖?，靜態(tài)采樣、動態(tài)采樣［13］、自適應(yīng)采樣［14-17］已作為隨機(jī)規(guī)劃中估計目標(biāo)函數(shù)值和處理機(jī)會約束的代表性方法。靜態(tài)采樣簡單且易于應(yīng)用，但計算開銷大；動態(tài)采樣使隨機(jī)變量的樣本大小隨迭代次數(shù)動態(tài)變化，但個體的優(yōu)劣辨析難；自適應(yīng)采樣要求個體的樣本大小由其優(yōu)劣程度決定，優(yōu)于動態(tài)采樣。

從智能優(yōu)化角度，極為罕見有一般類型MOPCP的成果報道，但源于特定領(lǐng)域的MOPCP的研究已取得一定進(jìn)展；主要研究集中于模型設(shè)計和基于權(quán)重系數(shù)法的智能優(yōu)化算法［2，18-21］。張國新等［18］針對空降突破點的決策或供應(yīng)商的選擇問題［19］，構(gòu)建MOPCP模型，并借助權(quán)重系數(shù)法轉(zhuǎn)化此模型為單目標(biāo)決策模型，進(jìn)而借助隨機(jī)模擬或雙重隨機(jī)模擬、神經(jīng)網(wǎng)絡(luò)獲得混合單目標(biāo)遺傳算法。另外，文獻(xiàn)［2，20-23］借助隸屬度函數(shù)設(shè)計工程問題的多目標(biāo)模糊機(jī)會約束規(guī)劃模型，并利用權(quán)重系數(shù)法或模糊模擬將模型轉(zhuǎn)化為單目標(biāo)規(guī)劃模型，進(jìn)而設(shè)計改進(jìn)型遺傳算法或蝙蝠優(yōu)化算法進(jìn)行求解。對于MOPCP的多目標(biāo)智能優(yōu)化研究，Virivinti和Mitra［24］針對含非線性相關(guān)不確定參數(shù)的工業(yè)磨削加工問題，提出一種基于非支配排序遺傳算法（NSGA-Ⅱ）的多目標(biāo)模糊機(jī)會約束規(guī)劃方法；謝仕煒等［3］針對電網(wǎng)最優(yōu)負(fù)荷削減問題設(shè)計多目標(biāo)多級機(jī)會約束規(guī)劃模型，進(jìn)而利用拉丁超立方采樣處理性能指標(biāo)和約束條件，并利用NSGA-Ⅱ進(jìn)行求解。Mehlawat和Gupta［25］基于可靠性理論，構(gòu)建表征COTS產(chǎn)品選擇問題的多目標(biāo)模糊機(jī)會約束規(guī)劃模型，進(jìn)而利用順序偏好近似解方法將該模型轉(zhuǎn)化為雙目標(biāo)規(guī)劃模型，并利用補(bǔ)償模糊方法求解此模型的有效解。

綜上，探討執(zhí)行效率高、尋優(yōu)效果好、噪聲抑制能力強(qiáng)、應(yīng)用潛力大的新型高性能智能優(yōu)化算法，是求解MOPCP的關(guān)鍵，但研究成果極為匱乏。免疫優(yōu)化作為人工免疫系統(tǒng)中極為重要的研究分支［26］，因其具有較好的群體多樣性且模塊設(shè)計靈活，使得與幾種經(jīng)典智能算法相比，在解決多模態(tài)優(yōu)化問題中具有獨特的優(yōu)勢，且已獲得一系列求解靜態(tài)或動態(tài)多目標(biāo)優(yōu)化問題的研究成果［27-29］，但很少觸及多目標(biāo)概率約束優(yōu)化問題。至于免疫理論是否有助于解決MOPCP仍需深入探討。危險理論作為不同于自我和非自我識別的免疫理論，解釋了免疫應(yīng)答如何被觸發(fā)的過程。雖然可借鑒其設(shè)計算法解決異常檢測、碰撞回避和動態(tài)規(guī)劃問題［30-32］，且求解不確定多目標(biāo)期望值規(guī)劃已呈現(xiàn)一定優(yōu)勢［14，33-34］，但是否有助于解決多目標(biāo)概率約束優(yōu)化問題仍是懸而未決的?；诖?，本文針對隨機(jī)變量的概率分布未知的一般MOPCP問題，依據(jù)危險理論蘊(yùn)涵的免疫應(yīng)答機(jī)理，探討多目標(biāo)免疫優(yōu)化算法（Multi-Objective Immune Optim ization A lgorithm，MOIOA）。

1 問題描述與概率估計

1.1 問題描述

式中：x為決策向量；D∈Rp為有界閉區(qū)域；ai和bi為解向量的分量區(qū)間的左右端點；ξ∈Rq為分布信息未知的隨機(jī)向量；Pr｛·｝為概率算子；αi∈［0，1］和βj∈［0，1］為置信水平；fi（x，ξ）和Gj（x，ξ）分別為關(guān)于x非線性且連續(xù)的隨機(jī)目標(biāo)和約束函數(shù)；gk（x）和hl（x）為確定性約束函數(shù)；I、J、K和L分別為目標(biāo)向量維數(shù)、概率約束個數(shù)、不等式約束個數(shù)和等式約束個數(shù)。在候選解x處，當(dāng)ξ的樣本大小n（x）（簡稱x的樣本大小）給定后，借助MC隨機(jī)模擬可確定子目標(biāo)函數(shù)的估計值［35］。滿足以上所有約束條件的候選解x∈D被稱為可信解。引入如下約束違背量函數(shù)Γ（x）：

式中：

其中：I｛·｝為指示函數(shù)，其若條件為真，則取1，否則取0。顯然，當(dāng)n（x）較大時，由大數(shù)定律可獲x的經(jīng)驗?zāi)繕?biāo)值和概率估計值＾pj（x）。此時，若Γ（x）＝0，則稱x為經(jīng)驗可信解，否則稱為經(jīng)驗非可信解。借助文獻(xiàn)［34］，引入適用于經(jīng)驗可信解之間比較的支配概念以及Pareto最優(yōu)解的概念。

定義1 對于任意經(jīng)驗可信解x，y∈D，稱x支配y（即x?y），如果：

定義2 給定經(jīng)驗可信解x*∈D，若在D中不存在經(jīng)驗可信解x使得x?x*，則稱x*是MOPCP的經(jīng)驗Pareto最優(yōu)解。

1.2 概率估計

機(jī)會約束概率估計法是借助候選解x的樣本下限M、樣本上限Tn及絕對誤差幅度［15］自適應(yīng)確定隨機(jī)變量的樣本大小，進(jìn)而估計約束條件中概率函數(shù)的值。算法描述如下：

算法1 機(jī)會約束概率估計法。

步驟1 輸入?yún)?shù)：候選解x∈D，樣本大小Tn、M、m，置信水平βj，參數(shù)J、δ。

步驟2 置j←1。

步驟3 置s←M（m＋1），依據(jù)樣本大小s，經(jīng)由式（2）計算第j個機(jī)會約束函數(shù)的概率估計值＾pj（x）。

步驟4 計算pj（x）與＾pj（x）的絕對誤差幅度：

式中：?1、?2、?3、?4、ξi為隨機(jī)變量；x1、x2為決策向量x的分量；N（μ，σ2）為正態(tài)分布；Φ-1（α）為正態(tài)分布函數(shù)的反函數(shù)；μ、σ和α分別為均值、標(biāo)準(zhǔn)差和置信水平。

問題1經(jīng)由TNK［47］擴(kuò)展獲之。TNK的目標(biāo)函數(shù)的取值范圍小，約束函數(shù)是非線性的，非支配面是分段連續(xù)的。取α＝0.9。在3.1節(jié)的評價指標(biāo)下，各算法獲得的統(tǒng)計結(jié)果如表1所示，表中：IAE、FR和AR分別為平均約束違背量、可信解所占比例的均值和平均執(zhí)行時間。各執(zhí)行一次獲得的非支配面和箱線圖如圖2所示，其中，圖2（a）～2（d）為理論非支配面PFtrue和2個算法獲得的非支配面，圖2（e）～2（f）為CD和CS值的箱線圖。

經(jīng)由表1的IAE、FR可知，以上8種算法均可找到可信解且平均約束違背量較小，其中MOIOA的平均約束違背量最小，獲得可信解的概率最高（80.21%）。這些算法均能處理以上問題的約束條件，但MOIOA的約束處理能力最強(qiáng)，原因在于：①M(fèi)OIOA利用自適應(yīng)采樣策略處理約束條件，這不僅能提高的搜索效率，而且能使優(yōu)質(zhì)個體獲得的樣本大小較大，差的個體獲得的樣本大小較??；②參與比較的算法均采用靜態(tài)采樣方法處理優(yōu)化問題的隨機(jī)因素，同時一個較大的樣本大小（300）能使個體的評價值接近理論值。由CD、CS的均值可知，各算法的覆蓋密度、覆蓋范圍的均值之間的差值較小，說明以上算法獲得的解分布的差異性較小。由表1中CR均值可知，以上算法獲得的解質(zhì)量視乎沒有明顯差異，但由平均約束違背量指標(biāo)IAE可知，MOIOA具有一定的優(yōu)勢。進(jìn)一步，由圖2（f）可知，NNIA、NSGA-Ⅱ、SPEA-Ⅱ的CS箱線圖出現(xiàn)異常值，且異常值較小，因此它們獲取的部分解屬于局部最優(yōu)解。

此外，經(jīng)由AR的均值可知，MOIOA的執(zhí)行效率具有明顯優(yōu)勢，且至少是MOEA／DD、MOPSO、NSGA-Ⅱ、SPEA-Ⅱ的6倍，NNIA 的8倍，CMIGA的8倍，以及是AgMOPSO的15倍。

問題2 BNH問題。

此問題是經(jīng)擴(kuò)展BNH問題［47］而獲之，其可信解存在的區(qū)域是非凸的，部分Pareto最優(yōu)解位于此區(qū)域的邊界上。加之，隨機(jī)變量影響概率約束函數(shù)的概率估計和優(yōu)質(zhì)解的辨析，求解難度較大。取置信水平α＝0.9。依據(jù)以上評價準(zhǔn)則，各算法獲得的統(tǒng)計結(jié)果和平均運(yùn)行時間如表2所示，箱線圖和一次運(yùn)行得到的非支配面如圖3所示。

表1 不同算法在α＝0.9下求解問題1獲得的統(tǒng)計結(jié)果比較Table 1 Com parison of statistical results of d ifferen t algorithm s for Problem 1 w ithα ＝0.9

圖2 問題1的非支配面比較與CD、CS值的箱線圖比較Fig.2 Comparison of Pareto fronts and comparison of box plots on CD and CS for Problem 1

經(jīng)由表2的IAE、FR均值可知，MOIOA和參與比較的算法均能高概率地找到可信解，且平均約束違背量均小，此表明以上算法都能處理該問題的約束條件。由CR的均值可知，AgMOPSO的平均覆蓋率最高，NNIA和MOIOA次之，而SPEA-Ⅱ獲得的解最差。由CD、CS的均值及圖3（e）～3（f）可知，AgMOPSO、CMIGA、NNIA、NSGA-Ⅱ、MOIOA獲得的解分布較好且覆蓋范圍較寬，SPEA-Ⅱ次之。由圖3（a）～3（d）可知，各算法均能穩(wěn)定地獲得近似最優(yōu)解?？傊?，所有算法均能以較高概率發(fā)現(xiàn)可信解，但它們的性能有明顯差異。綜合解質(zhì)量、解分布和算法產(chǎn)生的約束違背量，MOIOA具有一定的優(yōu)勢，而SPEA-Ⅱ求解以上問題的能力較弱。

此外，經(jīng)由AR的均值可知，MOIOA的執(zhí)行效率有明顯優(yōu)勢且至少是參與比較的算法的

5倍；MOEA／DD、MOPSO、NSGA-Ⅱ和SPEA-Ⅱ的效率相近且略高于NNIA和CMIGA的效率；Ag-MOPSO的求解所需時間最長。

表2 不同算法在α＝0.9下求解問題2獲得的統(tǒng)計結(jié)果比較Table 2 Com parison of statistical results of different algorithm s for Problem 2 w ithα＝0.9

圖3 問題2的非支配面比較與CD、CS值的箱線圖比較Fig.3 Comparison of Pareto fronts and comparison of box p lots on CD and CS for Problem 2

3.2.2 工程應(yīng)用

問題3 盤式制動器設(shè)計問題。

該問題經(jīng)擴(kuò)展盤式制動器設(shè)計問題［48］而獲之，其包含4個決策變量（內(nèi)徑、外徑、嚙合作用力、摩擦表面的個數(shù)），5個機(jī)會約束函數(shù)，目標(biāo)函數(shù)是制動時間、盤式制動器的質(zhì)量函數(shù)。由于此問題的目標(biāo)函數(shù)、約束函數(shù)均是高度非線性的，各決策變量的取值范圍較大，因此在噪聲環(huán)境下求解的難度極大。取置信水平α＝0.6。各算法獲得的統(tǒng)計結(jié)果和平均運(yùn)行時間如表3所示，得到的箱線圖和1次運(yùn)行生成的非支配面如下圖4所示，圖4（a）～4（d）為MOIOA和比較算法獲得的非支配面，圖4（e）～4（f）為CD和CS值的箱線圖。

經(jīng)由表3的IAE、FR均值可知，各算法均能高概率找到可信解，其中CMIGA和MOIOA的平均約束違背量較小。由CR的均值可知，CMIGA平均覆蓋率高，MOIOA 和MOEA／DD 次之。經(jīng)由CD、CS和圖4，以上算法獲得的解的覆蓋寬度與分布沒有明顯差異；相對而言，CMIGA的解分布相對較差且出現(xiàn)部分解明顯偏離Pareto面。由AR均值獲知，MOIOA 的搜索效率最高，其是MOEA／DD、MOPSO、NSGA-Ⅱ、SPEA-Ⅱ的3.7倍以上；NNIA的運(yùn)行速度較慢，但快于CMIGA；Ag-MOPSO的搜索效率最低。

問題4 焊接梁設(shè)計問題。

式中：焊縫長度l、焊縫厚度h、梁的寬度t、梁的厚度b為決策變量；Pc（x）為梁的容許屈曲荷載，其表達(dá)式為

表3 不同算法在α＝0.6下求解問題3獲得的統(tǒng)計結(jié)果比較Tab le 3 Com parison of statistical resu lts of different algorithm s for Prob lem 3 w ithα＝0.6

圖4 問題3的非支配面與CD、CS值的箱線圖比較Fig.4 Comparison of Pareto fronts and comparison of box plots on CD and CS for Problem 3

此問題經(jīng)擴(kuò)展焊接梁設(shè)計問題［48］而獲之，其包含4個設(shè)計變量和4個非線性概率約束函數(shù)，且以建造費(fèi)用、端梁的擾度為目標(biāo)函數(shù)；加之第2個目標(biāo)函數(shù)的取值較小，對噪聲極其敏感，因此求解該問題較難。取置信水平α＝0.9。各算法獲得的統(tǒng)計結(jié)果和平均運(yùn)行時間如表4所示，算法獲得的CD、CS值箱線圖和一次運(yùn)行產(chǎn)生的非支配面如圖5所示。

經(jīng)由表4的IAE和FR值可知，以上算法均能以高概率獲得可信解；AgMOPSO獲得可信解的能力相對較弱。由CR均值得知，MOIOA的平均覆蓋率遠(yuǎn)高于其他算法的平均覆蓋率，CMIGA次之。經(jīng)CD、CS的均值及圖5可知，各算法獲得的解的分布相似；MOIOA的解分布較寬。因此，MOIOA獲得的解分布較好、覆蓋范圍較寬且解的質(zhì)量較好。由AR可知，MOIOA具有較高的運(yùn)算效率，且至少是參與比較的算法的5倍，MOEA／DD、MOPSO、NSGA-Ⅱ、SPEA-Ⅱ次之，AgMOPSO的效率最低。

3.2.3 靈敏度分析

選取TNK測試問題檢測MOIOA的搜索性能受參數(shù)設(shè)置的影響程度。該算法的主要參數(shù)包括N、M、λ、pc、ηm及δ。給定α＝0.1；N、M、λ、pc、ηm

及δ的取值的13種不同組合如折線圖6（a）所示。MOIOA 在此每種參數(shù)設(shè)置下，獨立運(yùn)行100次，獲得的統(tǒng)計結(jié)果如折線圖6（b）～6（c）所示。圖6（b）中CM 表示算法獲得的解的目標(biāo)值與Pareto面的距離的均值。

圖5 問題4的非支配面與CD、CS值的箱線圖比較Fig.5 Comparison of Pareto fronts and comparison of box p lots on CD and CS for Problem 4

由圖6可知，MOIOA的解質(zhì)量對參數(shù)設(shè)置的敏感度不高。當(dāng)群體規(guī)模N、樣本大小M 增大時，CM的均值略小，但運(yùn)行效率有所下降。算法平均執(zhí)行時間AR均值隨λ、pc的增大而減小，CD、IAE均值隨δ增大而減小。因此，盡管參數(shù)的設(shè)置發(fā)生變化，MOIOA也能得到滿意的搜索效果，且得到的解的質(zhì)量差異較小。但是，群體規(guī)模、樣本大小的設(shè)置影響算法的運(yùn)行效率；參數(shù)δ的取值影響算法搜索可信解的性能。

圖6 MOIOA的不同參數(shù)設(shè)置及統(tǒng)計結(jié)果比較Fig.6 Different parameter settings of MOIOA and comparison of statistical results

4 結(jié) 論

1）多目標(biāo)概率約束規(guī)劃是一類具有廣泛工程應(yīng)用背景且也是具有挑戰(zhàn)性的隨機(jī)規(guī)劃問題?；诖?，從免疫學(xué)界極為關(guān)注的危險理論所蘊(yùn)含的應(yīng)答機(jī)理出發(fā)，設(shè)計適用于該類問題的MOIOA。

2）MOIOA中，機(jī)會約束概率估計法和目標(biāo)值估計法通過自適應(yīng)獲取樣本大小，分別被用來檢測候選解是否為經(jīng)驗可信解以及估計經(jīng)驗可信解的目標(biāo)值；基于危險理論，設(shè)計算法的進(jìn)化框架，并借助SBX、多項式變異、均勻變異產(chǎn)生多樣且高質(zhì)量的解。

3）計算復(fù)雜度分析表明，算法進(jìn)化初期，個體采樣規(guī)模小，搜索速度快，此有助于快速獲取可信解所在的區(qū)域；算法進(jìn)化后期，通過使采樣大小逐漸增大，提高算法的噪聲抑制能力，進(jìn)而有助于獲取Pareto最優(yōu)解。

4）多種具有競爭性的算法參與比較的數(shù)值實驗表明，盡管MOIOA求解多目標(biāo)概率約束規(guī)劃問題在尋優(yōu)效果方面約占一定的優(yōu)勢，但搜索效率方面有明顯優(yōu)勢。