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

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

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

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

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

1 改進(jìn)的多目標(biāo)量子免疫克隆算法

1.1 算法流程

改進(jìn)的多目標(biāo)量子免疫克隆算法流程見圖1。

1.2 算法實(shí)施步驟

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

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

步驟3 分別計(jì)算每個(gè)抗體對(duì)應(yīng)的親和度值、抗體濃度和擁擠距離;

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

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

步驟6 重新測(cè)量Qclone.rotation(t)，得到二進(jìn)制編碼Pclone.rotation(t)，并計(jì)算適應(yīng)度值;

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

步驟8 快速非支配排序;

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

步驟10 錦標(biāo)賽選擇;

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

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

步驟13 計(jì)算新種群Nt中各抗體對(duì)應(yīng)的親和度值;

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

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

圖1 改進(jìn)的IMOQICA算法流程

1.3 量子免疫克隆算子設(shè)計(jì)

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

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

2)改進(jìn)的混沌量子旋轉(zhuǎn)角

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

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

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

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

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

3)改進(jìn)的錦標(biāo)賽選擇策略

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

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

步驟2 若2個(gè)個(gè)體在同一非劣等級(jí)，則按照以下公式進(jìn)行選擇:

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

2 算法性能測(cè)試

2.1 參數(shù)設(shè)置和性能指標(biāo)

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

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

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

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

2.2 測(cè)試函數(shù)

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

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

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

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

2.3 算法性能對(duì)比

2.3.1 解集分布圖對(duì)比

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

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

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

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

2.3.2 指標(biāo)性能對(duì)比

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

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

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

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

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

表2 性能評(píng)價(jià)指標(biāo)Spacing的測(cè)試結(jié)果

表3 性能評(píng)價(jià)指標(biāo)S測(cè)度的測(cè)試結(jié)果

3 結(jié)束語

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

［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］吳勇，程明，項(xiàng)敏建.基于NSGA-Ⅱ的催化裂化分餾塔的多目標(biāo)優(yōu)化［J］.計(jì)算機(jī)測(cè)量與控制，2015(1):70-72.

［5］張宇獻(xiàn)，李松，李勇，等.基于量子位實(shí)數(shù)編碼的優(yōu)化算法及軋制規(guī)程多目標(biāo)優(yōu)化［J］.儀器儀表學(xué)報(bào)，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)絡(luò)優(yōu)化方法［J］.計(jì)算機(jī)應(yīng)用，2014(2):496-500.

［8］李陽陽，焦李成.量子免疫克隆多目標(biāo)優(yōu)化算法［J］.電子與信息學(xué)報(bào)，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í)數(shù)編碼的量子免疫克隆算法［J］.計(jì)算機(jī)工程，2012，18:133-136.

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

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

［13］韓春艷，禹思敏.改進(jìn)的Logistic映射及其動(dòng)力學(xué)特性［J］.中國海洋大學(xué)學(xué)報(bào):自然科學(xué)版，2015(5):120-125.

［14］鄧富民，梁學(xué)棟，劉愛軍，等.多資源約束下改進(jìn)NSGA-Ⅱ算法的手術(shù)調(diào)度［J］.系統(tǒng)工程理論與實(shí)踐，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.