張仁崇，張著洪

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

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

從智能優(yōu)化角度，極為罕見有一般類型MOPCP的成果報(bào)道，但源于特定領(lǐng)域的MOPCP的研究已取得一定進(jìn)展；主要研究集中于模型設(shè)計(jì)和基于權(quán)重系數(shù)法的智能優(yōu)化算法［2，18-21］。張國新等［18］針對(duì)空降突破點(diǎn)的決策或供應(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è)計(jì)工程問題的多目標(biāo)模糊機(jī)會(huì)約束規(guī)劃模型，并利用權(quán)重系數(shù)法或模糊模擬將模型轉(zhuǎn)化為單目標(biāo)規(guī)劃模型，進(jìn)而設(shè)計(jì)改進(jìn)型遺傳算法或蝙蝠優(yōu)化算法進(jìn)行求解。對(duì)于MOPCP的多目標(biāo)智能優(yōu)化研究，Virivinti和Mitra［24］針對(duì)含非線性相關(guān)不確定參數(shù)的工業(yè)磨削加工問題，提出一種基于非支配排序遺傳算法（NSGA-Ⅱ）的多目標(biāo)模糊機(jī)會(huì)約束規(guī)劃方法；謝仕煒等［3］針對(duì)電網(wǎng)最優(yōu)負(fù)荷削減問題設(shè)計(jì)多目標(biāo)多級(jí)機(jī)會(huì)約束規(guī)劃模型，進(jìn)而利用拉丁超立方采樣處理性能指標(biāo)和約束條件，并利用NSGA-Ⅱ進(jìn)行求解。Mehlawat和Gupta［25］基于可靠性理論，構(gòu)建表征COTS產(chǎn)品選擇問題的多目標(biāo)模糊機(jī)會(huì)約束規(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ì)靈活，使得與幾種經(jīng)典智能算法相比，在解決多模態(tài)優(yōu)化問題中具有獨(dú)特的優(yōu)勢(shì)，且已獲得一系列求解靜態(tài)或動(dòng)態(tài)多目標(biāo)優(yōu)化問題的研究成果［27-29］，但很少觸及多目標(biāo)概率約束優(yōu)化問題。至于免疫理論是否有助于解決MOPCP仍需深入探討。危險(xiǎn)理論作為不同于自我和非自我識(shí)別的免疫理論，解釋了免疫應(yīng)答如何被觸發(fā)的過程。雖然可借鑒其設(shè)計(jì)算法解決異常檢測(cè)、碰撞回避和動(dòng)態(tài)規(guī)劃問題［30-32］，且求解不確定多目標(biāo)期望值規(guī)劃已呈現(xiàn)一定優(yōu)勢(shì)［14，33-34］，但是否有助于解決多目標(biāo)概率約束優(yōu)化問題仍是懸而未決的?；诖耍疚尼槍?duì)隨機(jī)變量的概率分布未知的一般MOPCP問題，依據(jù)危險(xiǎn)理論蘊(yùn)涵的免疫應(yīng)答機(jī)理，探討多目標(biāo)免疫優(yōu)化算法（Multi-Objective Immune Optim ization A lgorithm，MOIOA）。

1 問題描述與概率估計(jì)

1.1 問題描述

式中：x為決策向量；D∈Rp為有界閉區(qū)域；ai和bi為解向量的分量區(qū)間的左右端點(diǎn)；ξ∈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ù)、概率約束個(gè)數(shù)、不等式約束個(gè)數(shù)和等式約束個(gè)數(shù)。在候選解x處，當(dāng)ξ的樣本大小n（x）（簡稱x的樣本大?。┙o定后，借助MC隨機(jī)模擬可確定子目標(biāo)函數(shù)的估計(jì)值［35］。滿足以上所有約束條件的候選解x∈D被稱為可信解。引入如下約束違背量函數(shù)Γ（x）：

式中：

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

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

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

1.2 概率估計(jì)

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

算法1 機(jī)會(huì)約束概率估計(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個(gè)機(jī)會(huì)約束函數(shù)的概率估計(jì)值＾pj（x）。

步驟4 計(jì)算pj（x）與＾pj（x）的絕對(duì)誤差幅度：

式中：?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é)的評(píng)價(jià)指標(biāo)下，各算法獲得的統(tǒng)計(jì)結(jié)果如表1所示，表中：IAE、FR和AR分別為平均約束違背量、可信解所占比例的均值和平均執(zhí)行時(shí)間。各執(zhí)行一次獲得的非支配面和箱線圖如圖2所示，其中，圖2（a）～2（d）為理論非支配面PFtrue和2個(gè)算法獲得的非支配面，圖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ì)個(gè)體獲得的樣本大小較大，差的個(gè)體獲得的樣本大小較??；②參與比較的算法均采用靜態(tài)采樣方法處理優(yōu)化問題的隨機(jī)因素，同時(shí)一個(gè)較大的樣本大小（300）能使個(gè)體的評(píng)價(jià)值接近理論值。由CD、CS的均值可知，各算法的覆蓋密度、覆蓋范圍的均值之間的差值較小，說明以上算法獲得的解分布的差異性較小。由表1中CR均值可知，以上算法獲得的解質(zhì)量視乎沒有明顯差異，但由平均約束違背量指標(biāo)IAE可知，MOIOA具有一定的優(yōu)勢(shì)。進(jìn)一步，由圖2（f）可知，NNIA、NSGA-Ⅱ、SPEA-Ⅱ的CS箱線圖出現(xiàn)異常值，且異常值較小，因此它們獲取的部分解屬于局部最優(yōu)解。

此外，經(jīng)由AR的均值可知，MOIOA的執(zhí)行效率具有明顯優(yōu)勢(shì)，且至少是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ù)的概率估計(jì)和優(yōu)質(zhì)解的辨析，求解難度較大。取置信水平α＝0.9。依據(jù)以上評(píng)價(jià)準(zhǔn)則，各算法獲得的統(tǒng)計(jì)結(jié)果和平均運(yùn)行時(shí)間如表2所示，箱線圖和一次運(yùn)行得到的非支配面如圖3所示。

表1 不同算法在α＝0.9下求解問題1獲得的統(tǒng)計(jì)結(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)勢(shì)，而SPEA-Ⅱ求解以上問題的能力較弱。

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

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

表2 不同算法在α＝0.9下求解問題2獲得的統(tǒng)計(jì)結(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 盤式制動(dòng)器設(shè)計(jì)問題。

該問題經(jīng)擴(kuò)展盤式制動(dòng)器設(shè)計(jì)問題［48］而獲之，其包含4個(gè)決策變量（內(nèi)徑、外徑、嚙合作用力、摩擦表面的個(gè)數(shù)），5個(gè)機(jī)會(huì)約束函數(shù)，目標(biāo)函數(shù)是制動(dòng)時(shí)間、盤式制動(dòng)器的質(zhì)量函數(shù)。由于此問題的目標(biāo)函數(shù)、約束函數(shù)均是高度非線性的，各決策變量的取值范圍較大，因此在噪聲環(huán)境下求解的難度極大。取置信水平α＝0.6。各算法獲得的統(tǒng)計(jì)結(jié)果和平均運(yùn)行時(shí)間如表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，以上算法獲得的解的覆蓋寬度與分布沒有明顯差異；相對(duì)而言，CMIGA的解分布相對(duì)較差且出現(xiàn)部分解明顯偏離Pareto面。由AR均值獲知，MOIOA 的搜索效率最高，其是MOEA／DD、MOPSO、NSGA-Ⅱ、SPEA-Ⅱ的3.7倍以上；NNIA的運(yùn)行速度較慢，但快于CMIGA；Ag-MOPSO的搜索效率最低。

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

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

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

經(jīng)由表4的IAE和FR值可知，以上算法均能以高概率獲得可信解；AgMOPSO獲得可信解的能力相對(duì)較弱。由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測(cè)試問題檢測(cè)MOIOA的搜索性能受參數(shù)設(shè)置的影響程度。該算法的主要參數(shù)包括N、M、λ、pc、ηm及δ。給定α＝0.1；N、M、λ、pc、ηm

及δ的取值的13種不同組合如折線圖6（a）所示。MOIOA 在此每種參數(shù)設(shè)置下，獨(dú)立運(yùn)行100次，獲得的統(tǒng)計(jì)結(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ì)量對(duì)參數(shù)設(shè)置的敏感度不高。當(dāng)群體規(guī)模N、樣本大小M 增大時(shí)，CM的均值略小，但運(yùn)行效率有所下降。算法平均執(zhí)行時(shí)間AR均值隨λ、pc的增大而減小，CD、IAE均值隨δ增大而減小。因此，盡管參數(shù)的設(shè)置發(fā)生變化，MOIOA也能得到滿意的搜索效果，且得到的解的質(zhì)量差異較小。但是，群體規(guī)模、樣本大小的設(shè)置影響算法的運(yùn)行效率；參數(shù)δ的取值影響算法搜索可信解的性能。

圖6 MOIOA的不同參數(shù)設(shè)置及統(tǒng)計(jì)結(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ī)劃問題?；诖耍瑥拿庖邔W(xué)界極為關(guān)注的危險(xiǎn)理論所蘊(yùn)含的應(yīng)答機(jī)理出發(fā)，設(shè)計(jì)適用于該類問題的MOIOA。

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

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

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