快速收斂的克隆選擇算法

肖金科，王 剛，劉昌云，付 強

（空軍工程大學(xué) 防空反導(dǎo)學(xué)院，陜西 西安710051）

0 引 言

克 隆 選 擇 算 法 （clonal selection algorithm，CLONALG）是Burnet模擬免疫系統(tǒng)抗體生成提出的群智能優(yōu)化算法，該算法已經(jīng)廣泛應(yīng)用于模式識別、組合優(yōu)化、機器學(xué)習(xí)等領(lǐng)域。然而這種智能優(yōu)化算法很容易陷入局部最優(yōu)、收斂慢等缺陷，為此，一些學(xué)者對其進行了改進。文獻 ［1］以球面雜交方式對種群進行調(diào)整并動態(tài)修正每個抗體的變異概率的方法，加快了CLONALG的全局收斂速度；文獻 ［2］采用的3種變異算子以提高抗體群的多樣性，缺乏抗體間的協(xié)同進化；文獻 ［3］引入了周期變異算子，周期變化的變異率提高了抗體群的多樣性，但演化的后期容易破壞優(yōu)良抗體；文獻 ［4］采用多個子種群代替了原來單一的種群，每個子種群獨立地進化，在完成一次進化后每個子種群中最好的抗體將取代其它種群最壞的抗體，算法性能得到顯著提高。

本文通過深入研究CLONALG的機制，改進了克隆算子和提出云自適應(yīng)變異算子，引入抗體重組算子，提出了快速收斂于全局最優(yōu)解的快速收斂的克隆選擇算法 （fast convergence clonal selection algorithm，F(xiàn)CCSA）。新型克隆算子模擬了克隆抗體間的競爭和抑制機制，有效控制了相似抗體的數(shù)量；云自適應(yīng)變異，保證了算法先全局搜索，尋找峰值，然后在優(yōu)良抗體周圍局部搜索，尋找最優(yōu)值；抗體重組算子使得抗體之間信息交互、協(xié)同進化。優(yōu)化10個被廣泛應(yīng)用標(biāo)準(zhǔn)測試函數(shù)，與其它常見的優(yōu)化算法對比，結(jié)果表明，F(xiàn)CCSA的性能得到顯著提高。

1 CLONALG描述

CLONALG的核心在于增殖克隆算子和變異算子，前者與抗體親合力成正比，保證抗體群的親合力逐步增大；后者與抗體親合力成反比例關(guān)系，保留最佳抗體并改進較差抗體?？寺∵x擇策略在理論上保證了抗體群的多樣性［5－6］，但深入分析可知，CLONALG只是對復(fù)雜免疫系統(tǒng)的簡單模擬，算法只是抗體群的進化計算，沒有考慮抗體之間的競爭機理；克隆后抗體群的變異過于單一，抗體群多樣性有限，對處理復(fù)雜的多模態(tài)優(yōu)化問題能力有限，容易早熟［7－8］。

2 FCCSA

不失一般性，設(shè)函數(shù)優(yōu)化問題

式中：f（X）——n維解空間的連續(xù)實函數(shù)，其中L＝ （l1，l2，…，ln）≤X≤U ＝ （u1，u2，…，un），即li≤xi≤ui（i＝1，2，…，n）。設(shè)抗體群珡X＝｛X1，X2，X3，…Xq｝，q為抗體群中抗體的個數(shù)，抗體 Xi＝ ［x1，…xk－1，xk，…，xn］，i＝1，2，…，q，n為抗體中變量的個數(shù)，此抗體－抗原的親和力記為f（Xi）。

2.1 算法設(shè)計

為了提高算法的多模態(tài)優(yōu)化問題的求解能力，結(jié)合獨特性和抗獨型免疫網(wǎng)絡(luò)的特性，從以下幾個方面對CLONALG進行了改進。

（1）克隆算子

抗體受抗原的侵入刺激被激活，克隆增值；同時抗體之間的競爭抑制作用維持免疫平衡。傳統(tǒng)的比例克隆不能體現(xiàn)此機制，改進的克隆算子對其進行模擬，克隆規(guī)模依據(jù)抗體－抗原的親和力、抗體－抗體的親和度自適應(yīng)的調(diào)整。為此，先定義抗體i與其它抗體的親和度Φi見式 （1）

式中：· ——歐式距離，在計算Φi時，對 · 進行歸一化處理，即0≤ · ≤1。顯然抗體－抗體的親和度越大，相似度越高，則Φi的值越小，從而抗體間的抑制作用越強。第i個抗體的克隆規(guī)模ni，由式 （2）計算

式中：k——抗體群的克隆規(guī)模，k＝∑ki，符號Int（·）表示取上整函數(shù)。

（2）云自適應(yīng)變異算子

CLONALG用于求解多峰值問題，變異算子在該算法中顯得尤其重要［9］。對克隆擴增后的抗體群中每個抗體進行變異可以提高抗體的多樣性，擴大搜索的范圍，以用來尋找更優(yōu)秀的抗體。常見的非一致性變異和高斯變異，具體分別見文獻 ［10－11］。

分析非一致性變異和高斯變異可知，非一致性變異雖然隨著演化的推進，變異的范圍由大到小，由全局搜索得到局部搜索，但是每次只局限于抗體一個分量的微調(diào)，則變異操作的效果不明顯，群體的多樣性不能保證，因而難以收斂于全部峰值；高斯變異能較好地對多個分量實施變異，克服了非一致變異的一些不足，但是未考慮整個抗體群的全局情況，而只是針對樣本抗體的狀況進行調(diào)整。針對此不足，本文借鑒云模型的思想，提出云自適應(yīng)變異操作。

云模型用期望值Ex、熵En和超熵He表征定性概念，將概念的模糊性和隨機性集成在一起，為定性與定量相結(jié)合的信息處理提供了有力手段。期望值Ex反應(yīng)了云層的重心位置；En反應(yīng)了云層的陡峭程度，En越小越陡峭；超熵He反應(yīng)了云層的厚度，He越大云層越厚［12－13］，如圖1所示。當(dāng)x＞Ex時，確定度隨x的增大而減小，云模型中云滴集中在區(qū)間［Ex－3En，Ex＋3En］，具有隨機性和穩(wěn)定傾向。把云模型的這一特征應(yīng)用于抗體變異的控制。親和力小的抗體進行較大的變異，以求生成親和力大的抗體，反之，要求變異較小，以保護優(yōu)良抗體。云自適應(yīng)變異算子按照式 （3）操作。

圖1 正態(tài)云模型的3個數(shù)字特征

式中：e、h——控制參數(shù)，e用來控制云的陡峭程度，根據(jù)“3En”規(guī)則，一般去3，h用來控制云層的厚度，一般去10，αi、pc為特定的參數(shù)，實驗中根據(jù)具體情況調(diào)整。

（3）抗體重組算子

借鑒遺傳算法交叉的思想，引入抗體重組算子。設(shè)3個獨立的父代抗體s1、s2、s3雜交生成子代抗體sc，其中sc滿足式 （4）

式中：k1、k2、k3——隨機生成的3個不全為0的實數(shù)。

云自適應(yīng)變異算子、抗體重組算子的共同作用，既保證了優(yōu)良抗體基因的遺傳，又實現(xiàn)了抗體間的信息交流、協(xié)同進化，使得克隆后的抗體群在親和力高的抗體周圍分散開，大大增加了抗體群的多樣性，提高算法的收斂速度。

（4）精英抗體保存算子

為減少冗余計算，模擬遺傳算法的精英種子保存策略，建立記憶種群，將多個優(yōu)良抗體直接放在記憶種群中，啟發(fā)了抗體群收斂的方向，為快速收斂得到全局最優(yōu)解提供保障。

2.2 算法的步驟

結(jié)合FCCSA的設(shè)計，下面給出算法的具體執(zhí)行步驟：

步驟1 隨機生成規(guī)模為q的初始抗體群X（0）＝｛X1，X2，X3，…Xq｝；

步驟2 精英抗體保存算子：在抗體群X（t）中選擇m個適應(yīng)度最大的抗體，加入記憶種群Xm（t）；

步驟3 克隆算子：對記憶種群Xm（t）依據(jù)式 （2）實施克隆，克隆后的抗體群為Xc（t）＝ ｛Xc1，Xc2，Xc3，…Xcq｝，Xci為個體Xi的克隆子群；

步驟4 云自適應(yīng)變異算子：對抗體群Xc（t）依據(jù)式（3）對抗體的每個基因進行云自適應(yīng)變異，生成抗體群X＊（t）；

步驟5 抗體重組算子：從抗體群Xc（t）中依次選取3個父代抗體s1、s2、s3依據(jù)式 （4）進行重組生成子代sc，直到不夠選擇3個為止，最后生成抗體群Xr（t）。

步驟6 合并抗體群 X＊（t）和 Xr（t），生成抗體群Xl（t）；

步驟7 抗體群更新操作：隨機產(chǎn)生d個新抗體，替換抗體群Xl（t）中親和力較小的抗體；

步驟8 終止判斷。若不滿足迭代次數(shù)，則更新演化代數(shù)記數(shù)器t→t＋1，并選取抗體群Xl（t）的m個親和力較大的抗體組成下一代抗體群Xm（t），然后轉(zhuǎn)入到步驟3；否則，輸出結(jié)果，算法結(jié)束。

算法結(jié)束后，記憶種群中的抗體即為所求問題的解。

3 仿真分析

為了測試本文提出的FCCSA的效果，對文獻 ［14］中的測試函數(shù)進行仿真實驗，測試函數(shù)見表1。其中f1～f5為單峰函數(shù)，f6～f10為多峰函數(shù)。

表1 測試函數(shù)的相關(guān)參數(shù)

測 試 環(huán) 境：Pentium （R）Dual－Core CPU E5500 2.79GHZ，Windows XP操作系統(tǒng)，Matlab語言編程實現(xiàn)，F(xiàn)CCSA的參數(shù)設(shè)定如下fccsamax＝300，q＝20，m＝5，k＝60，e＝3，h＝10，pc＝0.8，d＝10，αi＝3，i＝1，2，…，n。與混 沌 克 隆 選 擇 算 法［15］（chaos clonal selection algorithm，CCSA）、粒子群克隆選擇算法［16］（PSO－CSA）進行比較。mean，std和t分別為算法獨立實驗20次的平均最優(yōu)適應(yīng)值、標(biāo)準(zhǔn)差和平均運行時間，mean顯示了在給定的函數(shù)評價次數(shù)下算法所能達到的精度，反映了算法的收斂速度；std反映了算法的穩(wěn)定性和魯棒性；t反映了算法的時間效率。結(jié)果見表2。

由表2數(shù)據(jù)對比可以看出，在10個標(biāo)準(zhǔn)測試函數(shù)中，無論算法的收斂精度，還是算法的穩(wěn)定性，F(xiàn)CCSA都比CCSA和PSO－CSA都有很大的提高；時間效率也較為理想，說明FCCSA尋優(yōu)能力提高的同時，時間復(fù)雜度沒有增加。

為了更直觀地反映算法的尋優(yōu)效果，引入文獻 ［17］中種群多樣性測量指標(biāo)。種群多樣性是指種群中個體的差異性，多樣性缺失的直接結(jié)果就是搜索就可能陷入一個不含全局最優(yōu)點的區(qū)域難以逃離，這就是早熟問題。種群多樣性定義見式 （5）

式中：f（Am，n）avg、f（Am，n）max——當(dāng)代種群個體的平均適應(yīng)度值、最大適應(yīng)度值。PDM ∈［0，1］，當(dāng)算法收斂時，其值趨于1。

對相關(guān)測試函數(shù)的種群多樣性比較如圖2～圖5，其中橫坐標(biāo)表示迭代次數(shù)，縱坐標(biāo)表示種群多樣性指標(biāo)PDM。

表2 測試函數(shù)基于3種算法的計算結(jié)果比較

圖2 函數(shù)f2的種群多樣性比較

圖2、圖3可直觀看出，對于單峰函數(shù)，F(xiàn)CCSA的收斂速度明顯較CCSA和PSO－CSA快，尋優(yōu)能力與PSOCSA差不多；圖4、圖5可直觀看出，對于多峰函數(shù)，對比CCSA和PSO－CSA，F(xiàn)CCSA不僅收斂速度優(yōu)勢突出且全局尋優(yōu)能力有很大的提高，這是因為新型克隆算子、云自適應(yīng)變異算子和抗體重組算子大大增加了種群的多樣性，使得FCCSA具有很強的全局和局部搜索能力。

4 結(jié)束語

針對CLONALG種群多樣性少，容易早熟的缺陷，本文借鑒免疫調(diào)節(jié)機制，引入新型克隆算子，有效擴充優(yōu)良抗體和抑制相似抗體，維持了免疫平衡；結(jié)合云模型在“3En”區(qū)間的隨機性和穩(wěn)定傾向性，提出云自適應(yīng)變異，與抗體重組算子合作在克隆的基礎(chǔ)上實現(xiàn)了父代抗體周圍多個方向進行全局和局部進化。仿真實驗進一步表明，與CCSA和PSO－CSA相比，本文提出的FCCSA的尋優(yōu)能力、魯棒性性能顯著提高，同時時間復(fù)雜度不高，是一種解決函數(shù)優(yōu)化問題較優(yōu)秀的群智能優(yōu)化算法。下一步，重點研究FCCSA在特定實際問題中的應(yīng)用。

［1］MA Chunhua，ZHONG Yong.Dynamic adaptive immune clone selection algorithm by applying population division ［J］.Computer Engineering and Applications，2011，47 （30）：29－31 （in Chinese）.［馬春華，鐘勇.采用種群劃分的動態(tài)自適應(yīng)免疫克隆選擇算法 ［J］.計算機工程與應(yīng)用，2011，47 （30）：29－31.］

［2］TAO Xinmin，LIU Yu，F(xiàn)U Dandan，et al.Hybrid mutation clonal selection multiobjective optimization algorithm ［J］.Computer Simulation，2011，28 （10）：199－203 （in Chinese）.［陶新民，劉玉，付丹丹，等.混合變異克隆選擇多目標(biāo)優(yōu)化算法 ［J］.計算機仿真，2011，28 （10）：199－203.］

［3］YE Hongtao.Wastewater treatment system predicting and optimization control based on immune algorithm ［D］.Guangzhou：South China University of Technology，2011：44－46 （in Chinese）.［葉洪濤.基于免疫算法的污水處理系統(tǒng)預(yù)測及優(yōu)化控制研究 ［D］.廣州.華南理工大學(xué)，2011：44－46.］

［4］WU Zengwei，CHEN Sicheng，GU Jinguang.Paralleling clonal selection algorithm with OpenMP ［J］.Journal of Wuhan University of Technology （Information ＆ Management Engineering），2011，33 （6）：920－923 （in Chinese）. ［吳增偉，陳思成，顧進廣.基于OpenMP的并行克隆選擇算法 ［J］.武漢理 工 大 學(xué) 學(xué) 報－信 息 與 管 理 工 程 版，2011，33 （6）：920－923.］

［5］Dai Hongwei，Yang Yu，Li Cunhua.Improved quantum crossover based clonal selection algorithm ［C］／／3rd International Conference on Intelligent Networks and Intelligent Systems，2010：366－369.

［6］CHEN Lin，YAO Hongliang.Application of immune clonal genetic algorithm on logistics and distribution ［J］.Journal of Henan Institute of Science and Technology （Engneering Science），2012，40 （5）：70－74 （in Chinese）. ［陳林，姚宏亮.免疫克隆遺傳算法在物流配送中的應(yīng)用 ［J］.河南科技學(xué)院學(xué)報：自然科學(xué)版，2012，40 （5）：70－74.］

［7］LIU Qiong，WU Xiaojun.An improved immune clonal selection algorithm ［J］.Journal of Shandong University （Engineering Science），2009，39 （6）：8－12 （in Chinese）. ［劉瓊，吳小俊.一種改進的免疫克隆選擇算法 ［J］.山東大學(xué)學(xué)報 （工學(xué)版），2009，39 （6）：8－12.］

［8］QIAN Hai，MA Jianhui，WANG Xufa.New artificial immune algorithm based on the clonal selection principle ［J］.Journal of University of Science and Technology of China，2008，38（12）：1397－1406 （in Chinese）. ［錢海，馬建輝，王煦法.一種新的基于克隆選擇原理的人工免疫算法 ［J］.中國科技大學(xué)學(xué)報，2008，38 （12）：1397－1406.］

［9］Paw J K S，Chong Kok Hen，Koo Wai Yan，et al.Improved combined mutation clonal selection algorithm ［C］／／IEEE Conference on Sustainable Utilization and Development in Engineering and Technology，2012：92－196.

［10］Dai Yugang，Liu Zhandong.An almost everywhere strong convergence analysis for clonal selection algorithm ［C］／／International Conference on Computer Design and Applications，2010：108－111.

［11］HAN Xuming.Some improved artificial immune algorithms and their applications in the field of atmospheric environment［D］.Changchun：Jilin University，2010：23－25 （in Chinese）.［韓旭明.若干改進的人工免疫算法及其在大氣環(huán)境領(lǐng)域中的應(yīng)用 ［D］.長春.吉林大學(xué)，2010：23－25.］

［12］WANG Hongli.Qualitative modeling of complex system based on cloud model using QSIM ［J］.Application Research of Computers，2012，29 （12）：4593－4597 （in Chinese）. ［王洪利.基于云模型以約束為中心的復(fù)雜系統(tǒng)定性建模 ［J］.計算機應(yīng)用研究，2012，29 （12）：4593－4597.］

［13］DONG Lili，GONG Guanghong，LI Ni，et al.Adaptive parallelh simulated annealing genetic algorithms based on cloud models ［J］.Journal of Beijing University of Aeronautics and Astronautics，2011，37 （9）：1132－1136 （in Chinese）. ［董麗麗，龔光紅，李妮，等.基于云模型的自適應(yīng)并行模擬退火遺傳算法 ［J］.北京航空航天大學(xué)學(xué)報，2011，37 （9）：1132－1136.］

［14］Yao X，Liu G.Evolutionary programming made faster ［J］.IEEE Trans on Evolutionary Computation，1999，3 （2）：82－102.

［15］HONG Lu，JI Zhicheng，GONG Chenglong.On convergence rate of chaos clonal selection algorithm ［J］.Journal of Sytem Simulation，2011，23 （10）：2060－2064 （in Chinese）. ［洪露，紀(jì)志成，龔成龍.混沌克隆選擇算法及其收斂速度分析［J］.系統(tǒng)仿真學(xué)報，2011，23 （10）：2060－2064.］

［16］WANG Qiaoling.Research of hybrid optimization algorithms based on swarm intelligence ［D］.Harbin：Harbin Institute of Technology Press，2010：23－25 （in Chinese）. ［王巧靈.基于群體智能混合優(yōu)化算法的研究 ［D］.哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2010：23－25.］

［17］WANG Guangyuan，JI Wanfeng，SUN Junzheng，et al.The fire distribution for shore－based missiles based on improved particle swarm optimization ［J］.Aerospace Control，2012，30 （5）：71－77 （in Chinese）. ［王光源，汲萬峰，孫鈞正，等.基于改進PSO算法的岸基導(dǎo)彈火力分配研究 ［J］.航天控制，2012，30 （5）：71－77.］