非線性多目標概率約束規劃免疫優化算法

張仁崇，張著洪

（1.貴州商學院 計算機與信息工程學院，貴陽550014； 2.貴州大學 大數據與信息工程學院，貴陽550025）

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

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

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

1 問題描述與概率估計

1.1 問題描述

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

式中：

其中：I｛·｝為指示函數，其若條件為真，則取1，否則取0。顯然，當n（x）較大時，由大數定律可獲x的經驗目標值和概率估計值＾pj（x）。此時，若Γ（x）＝0，則稱x為經驗可信解，否則稱為經驗非可信解。借助文獻［34］，引入適用于經驗可信解之間比較的支配概念以及Pareto最優解的概念。

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

定義2 給定經驗可信解x*∈D，若在D中不存在經驗可信解x使得x?x*，則稱x*是MOPCP的經驗Pareto最優解。

1.2 概率估計

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

算法1 機會約束概率估計法。

步驟1 輸入參數：候選解x∈D，樣本大小Tn、M、m，置信水平βj，參數J、δ。

步驟2 置j←1。

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

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

式中：?1、?2、?3、?4、ξi為隨機變量；x1、x2為決策向量x的分量；N（μ，σ2）為正態分布；Φ-1（α）為正態分布函數的反函數；μ、σ和α分別為均值、標準差和置信水平。

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

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

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

問題2 BNH問題。

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

表1 不同算法在α＝0.9下求解問題1獲得的統計結果比較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

經由表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）可知，各算法均能穩定地獲得近似最優解?？傊?，所有算法均能以較高概率發現可信解，但它們的性能有明顯差異。綜合解質量、解分布和算法產生的約束違背量，MOIOA具有一定的優勢，而SPEA-Ⅱ求解以上問題的能力較弱。

此外，經由AR的均值可知，MOIOA的執行效率有明顯優勢且至少是參與比較的算法的

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

表2 不同算法在α＝0.9下求解問題2獲得的統計結果比較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 工程應用

問題3 盤式制動器設計問題。

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

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

問題4 焊接梁設計問題。

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

表3 不同算法在α＝0.6下求解問題3獲得的統計結果比較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

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

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

3.2.3 靈敏度分析

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

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

圖6 MOIOA的不同參數設置及統計結果比較Fig.6 Different parameter settings of MOIOA and comparison of statistical results

4 結 論

1）多目標概率約束規劃是一類具有廣泛工程應用背景且也是具有挑戰性的隨機規劃問題?；诖耍瑥拿庖邔W界極為關注的危險理論所蘊含的應答機理出發，設計適用于該類問題的MOIOA。

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

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

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