求解約束多目標區間優化問題的人工免疫算法

王小霞,王 丹,張再軍

(黔南民族師范學院 數學與統計學院，貴州 都勻 558000)

工程實際應用中，許多復雜問題最終被劃歸為一類含約束的多目標優化問題，而且由于在測量過程中本身存在一定的誤差或模型本身具有不確定等原因，這一類問題的系數可用區間值來表示，導致含區間約束的多目標區間值這類問題的誕生。求解此類問題，不僅需要考慮在區間約束條件下多個區間值目標函數之間的矛盾，還得考慮如何比較兩個區間數的大小。

對于不含約束的多目標區間值優化問題，已有多位學者給出了兩個區間數之間的比較方式。如Limbourg等[1]借助區間值上下界給出個體支配方法(IP支配)；鞏敦衛等[2]設計關于個體支配的可能度模型；張勇等[3]同樣依據區間值上下界設計出概率支配模型；章恩澤等[4]根據區間值的中點及半徑設計模糊支配關系。學者們將各自設計的支配方式與智能優化算法相結合，均各顯成效。對于含有區間約束的多目標區間值優化問題，Cheng等[5]利用區間可能度模型將區間約束轉換為確定性約束，根據區間序關系將目標函數轉化為優化中點及半徑的確定性雙目標模型，再結合NSGA-II進行求解。陳志旺等[6-7]通過泰勒展開將非線性函數轉化為線性函數，憑借占有支配關系及區間擁擠度結合改進的NSGA-II算法進行求解，能取得較好結果。

綜上可以明顯看出，在含區間約束的多目標區間優化方面的研究工作仍較少。該類問題求解困難、算法設計難，如何設計算法能夠獲得質量高，且分布均勻的解集一直是學者追求的目標。為此，本研究從生物免疫系統原理出發，設計一種適用于求解含區間約束的多目標區間值優化問題的人工免疫算法，旨在能夠獲得質量高且分布均勻的Pareto最優解集。

1 問題描述及基本概念

1.1 問題描述

不失一般性，考慮如下帶約束的多目標區間值規劃問題(P):

s.t.

其中：f(x,u)為m維目標函數向量，x為n維決策向量，x∈D，D為Rn中有界閉區域；u為不確定參數向量，u=(u1,u2,…,ul)。f(x,u) 是關于x的非線性區間值函數，fi(x,u)是區間值函數，gk(x,u)、hj(x,u)分別是區間值不等式約束的區間值函數和區間值等式約束的區間值函數。

1.2 相關定義

給定區間a、b,利用區間間的距離給出如下可能度模型[8]

(1)

(2)

對于可行解x和y，記

σi(x,y)=P(fi(x,u)≤fi(y,u))

σi(y,x)=P(fi(y,u)≤fi(x,u))

(3)

定義2(區間支配)若σi(x,y)≥σi(y,x)，i=1,2,…,m，且其中至少有一個不等式取不等號，則稱x區間支配y，記為xσy。

定義3(Pareto最優解)若x*∈X，且在X中不存在y，使得yσx*，則稱x*為問題(P)的Pareto最優解。

定義4(Pareto前沿)所有Pareto最優解對應的目標區間向量值構成的集合稱為Pareto前沿。

1.3 約束條件的處理

(4)

其中:δk為允許約束違背的置信水平。

定義5(約束允許解)若個體x的約束違背度V(x)<ε(t)，則稱x為約束允許解。其中，ε(t)為約束違背度的閾值，

ε(t)=0.2(1-t/T)

(5)

t為迭代次數，T為最大迭代次數。

通過該自適應調節約束違背度閾值，可在進化前期對個體放松約束，增強算法多樣性。在進化后期，約束違背度閾值逐漸減小，到最后一次迭代，約束違背度的閾值為0，還原到最初問題的要求。

1.4 區間擁擠度模型

采用文獻[9]中的區間擁擠度度量方式。給定個體x、y在目標空間中所對應的區間中點間的距離為

個體x、y的擁擠程度為

(6)

(7)

通過該擁擠度模型，可用于比較同為非支配個體的優劣，擁擠度越大的個體將被刪除，從而使Pareto解集更加均勻。

2 算法原理

2.1 免疫算法

生物免疫系統通過識別“自我”和“非自我”，運用防御手段消滅“非自我”細胞。人工免疫算法是基于生物免疫系統原理、運用仿生技術提出的一種智能優化算法。與其他算法比起來，人工免疫算法自適應性強，具有并行性和隨機性，能夠保持種群多樣性，獲得全局最優解，在諸多領域均得到廣泛應用。

2.2 算法描述

將待優化問題視為抗原，待優化問題的可行解視為抗體，用抗體的親和度比較可行解的優劣，并根據定義2、定義3和式(7)所給的區間支配和區間擁擠度的計算方式設計算法CMOIP-AIA (constrained multi-objective interval-valued programming artificial immune algorithm)。算法流程圖如圖1所示。算法具體步驟如下：

步1參數確定：迭代次數T，種群規模N，精英種群規模M，克隆繁殖數目mc=1，多項式變異概率p1，高斯變異p2，置信水平δk；

步2種群初始化：隨機生成種群P(t)={x1,x2, … ,xN};

步3根據式(4)和(5)將種群劃分為約束允許群F，記規模為n1和非約束允許群H，規模為n2；

步4計算種群F中抗體的親和力f，計算方式如下：

f(xi)=n1/(1+r(xi))

其中：r(xi)為抗體xi的受支配數。

步5對種群F中抗體受支配數為0且親和力大于平均親和力的抗體進行克隆，得克隆種群G；

步6將種群G中的抗體添加至精英種群中并依據受支配數及擁擠度進行精英種群的更新；

步7判斷迭代次數是否達到最大迭代次數，若達到，則將精英種群中的抗體作為優化問題的最優解輸出；否則，進入下一步；

步8對種群G執行多項式變異，約束允許群F執行多項式變異，非約束允許群H執行高斯變異；

步9將3個變異后的群體中約束允許個體合并起來，得種群C，并計算種群C中抗體的親和力，依據親和力進行種群抑制，并募集新成員，得下一代種群P(t+1)。

圖1 算法CMOIP-AIA流程圖Fig.1 CMOIP-AIA algorithm flow chart

3 數值實驗與分析

3.1 性能測度

1)HV 測度

通過在目標空間選取參考點，計算參考點與算法所獲超體積中點之間所形成的超體積(hypervolume,HV)。對于最小化問題，HV越小則表明Pareto解集的質量越好，越接近真實的Pareto前沿。

2)ISP測度[10]

ISP測度用于刻畫解集的均勻度，ISP值越小，表明解集越均勻。

3.2 數值實驗

本實驗在Window 10/CPU 1.6GHz/RAM 8.0GB/VC++6.0環境下進行。選取文獻[6]中算法(記為CNSGA-II)作為比較算法。測試問題將4個含約束的多目標靜態優化問題(SRN、CONSTR、BNH、TNK1)通過引入不確定因子將其轉化為含區間約束的多目標區間優化問題(SRNI、CONSTRI、BNHI、TNK1I)[11]。為了實驗比較的公平性，迭代次數均為2 000，對每個測試問題均獨立運行50次。算法CMOIP-AIA種群規模N為30，精英規模M為30。算法CNSGA-II的規模也記為30，其余參數與原文獻保持一致。50次實驗所得的50個HV測度值和ISP測度值均用箱線圖(如圖2、圖3)表示出來。此外，從50次所得的Pareto前沿中隨機抽取1次實驗結果，將其中心所構成的Pareto前沿呈現出來作比較，可更為直觀地觀察算法的優劣。

由圖2可明顯看出，算法CMOIP-AIA在各個測試問題中所獲HV測度值均小于算法CNSGA-II所獲的HV值，即算法CMOIP-AIA所獲的Pareto前沿更接近真實的Pareto前沿。特別從箱線圖2(a)和(b)可看出，算法CMOIP-AIA在求解這兩個問題時所獲解集的HV測度值差異較小，即算法CMOIP-AIA更加穩定。

圖3為兩種算法分別求解4個測試問題所得的ISP測度箱線圖。從4個箱線圖可看出，兩種算法所得的ISP值相差不大，非常接近。如在求解測試問題SRNI時，其ISP值平均相差的數量級為10-4，其他問題相差的數量級為10-2，表明兩種算法所得的Pareto解集在均勻度方面相差不多，都能得到相對均勻的解集。

圖4為兩種算法求解各問題所得的Pareto非支配前沿中心比較圖。從圖4可以清晰地看出在求解問題SRNI時，算法CNSGA-II所獲解集的質量相對較低，這與圖2的箱線圖展示的相一致。在求解CONSTRI、BNHI時，兩種算法均能夠搜索到較優的Pareto最優解。

綜合以上實驗分析可以看出，基于生物免疫系統原理設計的CMOIP-AIA算法在求解含區間約束的多目標區間值優化問題時，所得解集質量較優，所獲解集均勻性好，搜索效果更加穩定。

圖2 HV測度箱線圖Fig.2 Boxplot of HV measurement

圖3 ISP測度箱線圖Fig.3 Boxplot of ISP measurement

圖4 非支配前沿中心圖Fig.4 Non-dominated front center diagram

4 結論

含區間約束的多目標區間值優化問題是一類應用背景廣泛、求解較難的不確定優化問題，探討優化算法對其進行求解具有非常重要的現實意義。本研究根據已報道的關于兩個區間數的比較以及擁擠度的模型，依托生物免疫學原理，設計適合求解含區間約束的多目標區間值優化問題的人工免疫算法。算法設計中，設計約束控制閾值，自適應調節約束的違背程度；根據每個個體的約束違背程度將種群劃分為約束允許群和約束不允許群，不同種群進行不同的進化方式，并及時添加新成員，保持種群的多樣性，加快種群收斂速度。比較性的實驗結果表明，該算法在求解該類問題時具有一定的有效性。