一種改進的多目標量子免疫克隆算法

葉燕杰，胡震云，b，c，陳志明

(河海大學 a.商學院;b.水文水資源與水利工程科學國家重點實驗室;c.管理科學研究所，南京 210098)

自20世紀80年代開始，進化算法逐步發(fā)展成為能有效解決多目標優(yōu)化問題的重要方法。1985年出現(xiàn)的基于向量評估的VEGA算法［1］是第一個多目標算法，但本質(zhì)上VEGA算法仍然是加權和方法?，F(xiàn)代智能的多目標優(yōu)化算法源于20世紀90年代之后，由于計算機的普及，通過機器學習，進化算法的并行性得到廣泛的利用，相繼出現(xiàn)了由Deb等提出的非支配排序遺傳算法(NSGA)［2］，Zitzler和 Thiele 提出的強度 Pareto 進化算法(SPEA)［3］，Horn 和 Nafpliotis提出的基于小生境的 Pareto遺傳算法(NPGA)，F(xiàn)onseca和Fleming提出的多目標遺傳算法(MOGA)。這些算法為今后的多目標優(yōu)化方法研究打下了堅實的基礎。國內(nèi)學者對多目標問題進行了大量有價值的研究，吳勇等［4］將NSGA-Ⅱ用于催化裂化加工裝置優(yōu)化設計中，并引入多目標綜合評價優(yōu)化函數(shù)。張宇獻等［5］將免疫遺傳算法框架與量子計算思想相結合，并提出基于量子位實數(shù)編碼的熱連軋軋制規(guī)程多目標優(yōu)化算法，均取得了良好的效果。

量子免疫克隆算法(quantum-inspired immune clone algorithm，QICA)是一種新穎的智能優(yōu)化算法，由李陽陽和焦李成于2005年提出［6］。量子免疫克隆算法結合量子搜索機制和人工免疫系統(tǒng)的克隆選擇原理，利用量子編碼的疊加性和隨機性構造抗體;利用克隆操作產(chǎn)生克隆種群從而實現(xiàn)種群擴張，提高了局部搜索能力;采用通用的量子門旋轉操作，同時引入旋轉角度動態(tài)調(diào)整機制和量子交叉策略［7］。李陽陽等［8］結合免疫系統(tǒng)的免疫優(yōu)勢理論和抗體克隆選擇學說，提出了量子免疫克隆多目標優(yōu)化算法。對于量子免疫克隆算法的改進，文獻［9］采用量子旋轉門進行演進，同時借助全干擾交叉操作，避免陷入局部最優(yōu);文獻［10］提出一種基于實數(shù)編碼的量子免疫克隆算法，算法利用量子位的概率幅直接編碼，并對旋轉角度和角度大小進行改進。杜振華等［11］提出了免疫克隆選擇多目標優(yōu)化算法，該算法通過變異算子實現(xiàn)對優(yōu)異抗體的克隆。

量子免疫克隆算法在組合優(yōu)化問題中有良好的表現(xiàn)，但在多目標優(yōu)化領域的研究卻較為少見，且QICA算法的編碼復雜，計算精度受編碼位數(shù)限制，需要進行頻繁的編、解碼操作，增加了算法的計算量，降低了算法效率和尋優(yōu)速度。本文在量子免疫克隆多目標優(yōu)化算法的基礎上提出了一種改進的量子免疫克隆多目標優(yōu)化算法(improved multi-objective quantum-inspired immune clone algorithm，IMOQICA)。該算法將快速非支配排序策略應用于QICA，從而降低了算法的復雜度;提出一種改進的克隆規(guī)模計算方式，從而有效地增大優(yōu)良個體的比例，減少不良個體的影響;在確定量子旋轉角度大小方面，提出了改進的混沌旋轉角度策略，加速了算法收斂;并對錦標賽選擇的規(guī)則進行了改進，提高了算法的搜索效率。

1 改進的多目標量子免疫克隆算法

1.1 算法流程

改進的多目標量子免疫克隆算法流程見圖1。

1.2 算法實施步驟

步驟1 設置進化代數(shù)計數(shù)器t=1，通過量子計算生成含有2m個抗體的初始種群Q(t)(t=0);

步驟2 量子態(tài)觀測，將量子抗體觀測成二進制抗體P(t);

步驟3 分別計算每個抗體對應的親和度值、抗體濃度和擁擠距離;

步驟4 根據(jù)親和度、擁擠距離及抗體濃度的大小自適應調(diào)整的克隆規(guī)模進行克隆擴增，得到新的量子種群Qclone(t);

步驟5 將克隆后的量子抗體Qclone(t)進行量子旋轉門變異操作，得到新的量子種群Qclone.rotation(t);

步驟6 重新測量Qclone.rotation(t)，得到二進制編碼Pclone.rotation(t)，并計算適應度值;

步驟7 判斷序值分類和擁擠距離計算是否完成，若完成則轉到步驟10;否則，轉步驟8;

步驟8 快速非支配排序;

步驟9 計算同一非劣等級中抗體的擁擠密度;

步驟10 錦標賽選擇;

步驟11 采用自適應交叉、變異等操作，形成種群Qt;

步驟12 將Pt和Qt合并成新種群Nt;

步驟13 計算新種群Nt中各抗體對應的親和度值;

步驟14 采取與步驟3相同的方法，對新種群Nt進行非支配排序;選取前N個抗體產(chǎn)生新的種群NPt，并同時更新免疫記憶細胞;

步驟15 進化終止條件判定。若已經(jīng)達到最大迭代次數(shù)，運算結束并輸入計算結果;否則，進行下一次迭代，轉步驟3。

圖1 改進的IMOQICA算法流程

1.3 量子免疫克隆算子設計

1)改進的克隆規(guī)模算子

其中:Nc為與克隆規(guī)模相關的設定值，且滿足Nc＞n;F(x)為親和度函數(shù);idistance為擁擠距離;idensity為抗體濃度;?x」為小于x的最大整數(shù);α，β為常量，且α，β＞0。由此可見:對于單一抗體而言，其克隆規(guī)模是依據(jù)抗體適應度、擁擠距離和抗體濃度自適應地調(diào)整。具體來講，抗體適應度越大、擁擠距離越大、抗體濃度越小，其克隆規(guī)模越大，被搜索的機會就越多。

2)改進的混沌量子旋轉角

抗體的變異操作能夠提高算法的搜索能力，而變異策略多種多樣。文獻［12］使用在指導量子染色體的周圍隨機散布量子染色體的方式進行變異操作;文獻［10］采用最常見的量子旋轉門操作，量子旋轉門的角度通過查表得到。文獻［9］采用的量子旋轉門如下:

其中:θ為旋轉角度，一般地，θ∈(0.005π，0.1π)，量子門旋轉角度的大小直接影響算法的收斂速度。

本文采用混沌系統(tǒng)的原理來確定旋轉角度的大小?；煦缡欠蔷€性系統(tǒng)的本質(zhì)特征，它是一種自然界普遍存在的非線性現(xiàn)象，具有隨機性、遍歷性、規(guī)律性等特殊性質(zhì)。在混沌優(yōu)化中，對于產(chǎn)生混沌變量的系統(tǒng)一般選用 Logistic映射［13］，即蟲口模型，是指在確定的地域范圍內(nèi)昆蟲數(shù)目隨著時間變化的一種數(shù)學模型，表示如下:

其中:μ是混沌吸引子，一般地，當μ=4時，系統(tǒng)進入混沌狀態(tài)，產(chǎn)生混沌變量 Δn(n=1，2，…)，且Δn∈［0，1］。為此，本文將量子旋轉角度大小定義為

其中:k為調(diào)節(jié)因子，本文設定 k∈［0.01π，0.15π］;Δ通過式(3)獲得;t為當前進化代數(shù)。

3)改進的錦標賽選擇策略

傳統(tǒng)的錦標賽選擇，其實質(zhì)是在選擇時首先基于快速非支配排序策略，比較兩抗體的非劣前沿等級，取等級較低的抗體，否則在同一等級中取擁擠距離較大者作為選擇的對象。參數(shù)k為聯(lián)賽規(guī)模，一般取k=2。顯然，這種選擇方式也使得擁擠距離較大的抗體具有較大的“生存”機會。但是僅考慮擁擠距離出現(xiàn)過早收斂和停滯等現(xiàn)象，不利于抗體的多樣性，因而本文提出了基于擁擠密度和抗體濃度的組合賦權選擇策略，具體步驟如下:

步驟1 首先選擇2個個體，比較其非劣前沿等級，若非劣等級不同，則取等級級數(shù)較低的個體;否則轉步驟2;

步驟2 若2個個體在同一非劣等級，則按照以下公式進行選擇:

其中:CDil和DSil分別為在級別l中抗體qi的擁擠密度和抗體濃度;本文將ω定義為錦標賽選擇系數(shù)，且ω＞0;λil為抗體qi的組合選擇值。從表達式中可以看出:擁擠密度越小、抗體濃度越小，綜合選擇值也越小，因而選擇概率越大，故在同一級別中，綜合選擇值越小的抗體排序越靠前。

2 算法性能測試

2.1 參數(shù)設置和性能指標

為了說明算法的優(yōu)越性，將其與多目標算法NSGA-II進行比較。相關參數(shù)設置如下:

對NSGA-II算法，設定最大迭代次數(shù)為200，種群規(guī)模為100，適應度函數(shù)值偏差為1e-100;采用模擬二元交叉和多項式變異策略，設置交叉概率pc=0.8，變異概率pm=1/n，模擬二元交叉的分布指數(shù)為15，多項式變異的分布指數(shù)為20。

對改進的多目標量子免疫克隆算法(IMOQICA)，設定最大迭代次數(shù)為200，種群規(guī)模為100，克隆規(guī)模為50，錦標賽選擇規(guī)模為2，人工免疫記憶庫規(guī)模為50，適應度函數(shù)值偏差為1e-100;采用自適應交叉和變異策略，設置交叉概率pc∈［0.4，0.99］，變異概率 pm∈［0.000 1，0.1］［14］。

由于多目標優(yōu)化問題存在一系列的Pareto-最優(yōu)解，故目前對于多目標算法還沒有統(tǒng)一的性能評價準則。一般來說，多目標優(yōu)化算法的最優(yōu)解集與理想最優(yōu)Pareto-前端的距離越小越好，解分布越均勻越好，算法收斂性越大越好。本文選取4個性能度量指標定量地評價算法的性能，分別為算法平均運行時間(AVGTime)、算法收斂性(convergence capability)、兩個解集之間的覆蓋率(converage of two sets，CS)［15］和均勻性度量方法中的空間度量指標——分布度(spacing，SP)［16］。

2.2 測試函數(shù)

為了驗證改進的多目標量子免疫克隆算法在解決多目標優(yōu)化問題上的有效性，本文選取3維目標測試函數(shù) MOP5、經(jīng)典 kur測試函數(shù)以及DTLZ2測試函數(shù)，測試函數(shù)如下所示:

1)MOP5測試函數(shù)，該測試函數(shù)是2維3目標優(yōu)化問題。

2)kur測試函數(shù)，該函數(shù)問題是3維2目標問題，且其Pareto最優(yōu)前沿面是不連續(xù)的。

3)DTLZ2測試函數(shù)，該函數(shù)為3維目標問題，特征是高維目標函數(shù)空間，且其最優(yōu)Pareto-前端滿足，即第一象限內(nèi)的單位球面。

2.3 算法性能對比

2.3.1 解集分布圖對比

通過對圖2～4這3種不同類型的測試函數(shù)的Pareto解集分布圖的性能對比，可以看出采用改進的多目標量子免疫克隆算法所得的Pareto解集具有優(yōu)良的多樣性，尤其是種群收斂的穩(wěn)定性大幅提升，具有更快的全局尋優(yōu)能力，能有效地防止種群退化。

圖2 測試函數(shù)1的解集分布圖

圖3 測試函數(shù)2的解集分布圖

圖4 測試函數(shù)3的解集分布圖

2.3.2 指標性能對比

本文提出4個衡量算法性能的指標，分別是算法平均運行時間(AVGTime)、算法收斂性(convergence capability)、兩個解集之間的覆蓋率(converage of two sets，CS)［15］和均勻性度量方法中的空間度量指標——分布度(spacing，SP)［16］。

1)算法平均運行時間和算法收斂性。從表1中的指標可以看出:IMOQICA算法較NSGA-II算法在平均運行時間和算法收斂性上都有較大提高。特別是在三維目標問題上，IMOQICA算法收斂能力更強、收斂速度更快，具有更好、更快的全局搜索能力，能夠有效防止種群退化，這使得其能夠有效地解決高維、多目標優(yōu)化問題。

2)兩個解集之間的覆蓋率。表2指標S由4個子指標來衡量，分別是Min、Mean、Max以及Std。從4個指標來看，IMOQICA均優(yōu)于NSGA。特別是Std，它反映解的波動性大小，IMOQICA算法的波動性遠小于NSGA，說明本文算法解集分布更加均勻，這也與上圖結果相吻合。

3)分布度。從表3中的指標可以看出，對于3種不同的測試函數(shù)，ζ(XI，XN)均要明顯大于ζ(XN，XI)，由此可說明IMOQICA算法尋找到的最優(yōu)解在很大程度上支配著NSGA-II算法找到的最優(yōu)解，表明算法具有較強的搜索尋優(yōu)能力。

表1 兩種算法在3種不同測試函數(shù)下的全局搜索能力比對

表2 性能評價指標Spacing的測試結果

表3 性能評價指標S測度的測試結果

3 結束語

針對量子免疫克隆算法在解決多目標優(yōu)化問題時存在編碼復雜、需要頻繁的解編碼操作以及計算量較大等缺陷，本文提出了一種改進的多目標量子免疫克隆算法。算法中，克隆規(guī)模大小由抗體適應度、擁擠距離和抗體濃度共同決定，采用混沌系統(tǒng)的原理來確定旋轉角度的大小，且采用了改進的錦標賽選擇模式。通過3個典型多目標函數(shù)優(yōu)化問題的性能測試結果表明:與NSGA-II算法相比較，該算法更適用于解決多目標優(yōu)化問題，并且收斂速度快，程序運行時間大大縮短，具有較強的全局搜索能力。

［1］SCHAFFER J D.Multiple objective optimization with vector evaluated genetic algorithms［C］//In the Proceedings of the International Conference on Genetic Algorithms and Their Applications，Pittsburgh.PA:［s.n.］，1985:93-100.

［2］SRINIVAS N，DEB K.Multi-objective optimization using non-dominated in genetic algorithms［J］.Evolutionary Computation，1994，2(3):221-248.

［3］ZITZLER E，THIELE L.Multiobjective Evolutionary Algorithms:A Comparative Case Study and the Strength Pareto Approach［J］.IEEE Transaction on Evolutionary Computation，1999(3):257-271.

［4］吳勇，程明，項敏建.基于NSGA-Ⅱ的催化裂化分餾塔的多目標優(yōu)化［J］.計算機測量與控制，2015(1):70-72.

［5］張宇獻，李松，李勇，等.基于量子位實數(shù)編碼的優(yōu)化算法及軋制規(guī)程多目標優(yōu)化［J］.儀器儀表學報，2014(11):2440-2447.

［6］JIAO LICHENG，LI YANGYANG.Quantum-inspired Immune Clonal Optimization［C］//Proc.of International Conference on Neural Networks and Brain.Beijing，China:［s.n.］，2005:461-466.

［7］祁浩，王福豹，鄧宏，等.基于量子免疫克隆算法的神經(jīng)網(wǎng)絡優(yōu)化方法［J］.計算機應用，2014(2):496-500.

［8］李陽陽，焦李成.量子免疫克隆多目標優(yōu)化算法［J］.電子與信息學報，2008(6):1367-1371.

［9］JIAO LICHENG，LI YANGYANG，GONG MAOGUO，et al.Quantum-imspired Immune Clonal Algorithm for Global Optimization［J］.IEEE Transactions on Systems，Man and Cybernetics，Part B:Cybernetics，2008，38(10):1234-1253.

［10］王娟，李飛.一種基于實數(shù)編碼的量子免疫克隆算法［J］.計算機工程，2012，18:133-136.

［11］杜振華，閆肅，諶海云，等.免疫克隆選擇多目標優(yōu)化算法與MATLAB實現(xiàn)［J］.智能計算機與應用，2014(3):45-48.

［12］於時才，馬寧，亢軍賢.基于免疫克隆選擇算法的神經(jīng)網(wǎng)絡規(guī)則抽?。跩］.計算機工程，2009，35(1):173-175.

［13］韓春艷，禹思敏.改進的Logistic映射及其動力學特性［J］.中國海洋大學學報:自然科學版，2015(5):120-125.

［14］鄧富民，梁學棟，劉愛軍，等.多資源約束下改進NSGA-Ⅱ算法的手術調(diào)度［J］.系統(tǒng)工程理論與實踐，2012，32(6):1337-1345.

［15］ZITZLER E，DEB K，THIELE L.Comparison of Multiobjective Evolutionary Algorithms:Empirical Results［J］.Evolutionary Computation，2000，8(2):173-195.

［16］SCHOTT J R.Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization［D］.Cambridge:Massachusetts Institute of Technology，1995.