牛永潔，馬亞玲

（1.延安大學 計算中心，陜西 延安 716000；2.河南中醫(yī)學院 圖書館，河南 鄭州 450008）

克隆選擇算法是人工免疫系統(tǒng)中一種經典的免疫算法模型，2002年由De Castro根據生物免疫系統(tǒng)理論中的克隆選擇學說而提出[1]，這種算法簡稱為CLONALG。由于克隆選擇算法具有并行性、自適應性、學習、識別和記憶等優(yōu)點，很快被應用到函數優(yōu)化[2-3]、特征選擇[4]、入侵檢測[5]、圖像分割[6-7]、機器學 習[8]等領域 。

但是CLONALG算法具有收斂速度慢、搜索能力弱、易陷入局部最優(yōu)的缺點，本文對CLONALG算法在4各方面進行了改進，改進后的算法在收斂速度、搜索能力等方面都有顯著的改善。通過實驗仿真，發(fā)現效果良好。

1 克隆選擇算法

克隆選擇算法主要經過初始化、選擇、克隆、變異、替換5個階段，在系統(tǒng)初始化階段隨機生成N個問題域的可能解，在算法中被稱為抗體，抗體被分為兩個部分，一部分為記憶細胞M和剩余群體P，按照抗體和抗原的結合程度衡量抗體的優(yōu)劣，結合度高的抗體表示能夠解決抗原帶來的問題，即結合度高的抗體更接近于問題的解，從種群中選擇n個結合度較高的抗體，然后進行克隆，對克隆后的抗體進行高頻變異，變異完成后將種群中C個抗體用重新隨機生成的抗體替換，然后重新進行選擇。這就是克隆選擇的基本思想。

標準的克隆選擇算法的運行步驟如下：

1）在問題的定義域中隨機生成候選抗體集合H，集合中有抗體N個，N為種群規(guī)模的大小。

2）將集合H中的每個個體帶入適應度函數計算親和度，從中選擇n個最佳的抗體組成集合Pn，n≤N。

3）對集合Pn中的抗體進行克隆操作，每個抗體復制c個，構成臨時的克隆集合C。

4）以一定的概率m對臨時的克隆集合C進行高頻變異，形成一個變異后的新集合Cn。

5）將集合Cn中的抗體計算親和度，選擇 n個最佳抗體，組成記憶細胞集合M，使用集合M代替集合H中的集合Pn。

6）對集合H中的d個低親和度的抗體使用新生成的抗體進行替換，用來保持抗體群體的多樣性，用來防止算法的“早熟”現象。

2 算法的改進

本文提出的新算法主要針對4個方面進行改進。

1）抗體克隆策略的改進

對抗體克隆策略的改進分為兩個方面，第一個方面是對集合Pn中的每個抗體不采用平均克隆的方法，而是根據抗體自身的親和度大小進行克隆，每個抗體的克隆數目與親和度成正比。即抗體t的克隆數目用公式（1）進行計算。

在公式（1）中，Ct表示抗體 t要克隆的數量，ft是抗體 t的親和度，fmax是當前抗體中最大親和度。N是群體規(guī)模，α為克隆調節(jié)系數。第二個方面是隨著算法的迭代進行，即使親和度相同的抗體，其克隆的數量也應遞減，這樣即能保證算法的收斂速度也能保證算法后期不出現震蕩。所以公式（1）應調整為公式（2）

公式（2）中Iter是算法的迭代次數，β是一個負值的調整系數，λ為算法開始時的克隆數目。改進后的算法在進行抗體克隆時，一方面與自身的親和度成正比關系，而且隨著算法的迭代運行，每個抗體的克隆數量是呈線性遞減的。

2）變異概率的自適應變化

抗體經過克隆后，需要進行高頻變異操作，隨著算法迭代進行，變異的概率應該逐漸線性遞減。以保證算法后期的收斂。變異概率的變化規(guī)律使用公式（3）進行。

其中mk是第k次迭代的變異概率，而mk+1是第k+1次迭代的變異概率，參數ρ是一個大于零小于1的調整參數。

3）替換策略的改進

標準的克隆選擇算法是完全隨機生成一定數量的抗體，然后將集合H中的d個低親和度的抗體替換掉。本算法對生成的新抗體進行限制，要求新生成抗體的平均親和度要大于等于集合Pn的平均親和度。

4）變異概率和克隆數量的突變

為了預防算法在運行過程中的局部收斂而造成的算法停滯，文中引入早熟檢測指標Dp，當Dp≤ξ時，則將變異的概率增大k倍，同時對替換的抗體采用完全隨機策略，不再要求抗體的平均親和度大于等于集合Pn的平均親和度。文中k的取值為1.4倍。當Dp>ξ，抗體的變異規(guī)律和替換策略恢復正常。文中ξ取值為1.2。Dp使用公式（4）計算。

其中fmax表示本代抗體最大親和度值，fmin表示本代抗體最小親和度值，fave表示本代抗體平均適應度值。

3 仿真試驗

為了對新算法的有效性進行評價，選用兩個測試函數進行測試，并與CLONALG算法進行比較，選用的測試函數如下：

函數 f1（x，y）、f2（x，y）在定義域的圖像分別如圖 1 和圖 2所示。

圖 1 f1（x，y）的圖像Fig.1 Image of f1（x，y）

圖 2 的圖像 f2（x，y）Fig.2 Image of f2（x，y）

算法中參數的設置為 N為 100，n=50，α設置為 1，β為-0.001，λ 為 0.，3，ρ為 0.8， 算法初始的變異率為 0.01，d 為20，每次算法迭代100次，每種算法平均運行20次，取運行結果的平均值作為衡量的最終結果。表1列出了CLONALG算法和新算法的運行結果。

表1 CLONALG算法與新算法對比結果Tab.1 CLONALG algorithm comparing the results with the new algorithm

圖3、4顯示了函數 f2（x，y）采用兩種不同算法最優(yōu)親和度和抗體平均親和度運行圖。

4 結 論

圖3 CLONALG算法運行時的最優(yōu)、平均親和度Fig.3 Optimal and average affinity of CLONALG

圖4 新算法運行時的最優(yōu)、平均親和度Fig.4 Optimal and average affinity of new algorithm

通過對基本的克隆選擇算法進行4個方面的改進，得到一種新的算法，使用兩個多峰值函數對將新的算法進行了驗證。新算法采用抗體克隆數和變異概率隨著算法的運行線性遞減的策略，同時對抗體的克隆數量采用與抗體本身親和度成正比的方法，能夠保證在算法運行初期充分的變異和對優(yōu)秀抗體充分復制克隆，在全面搜索解空間的前提下，盡量保持優(yōu)秀抗體的存在，算法后期為了減少算法運行的震蕩，抗體克隆的數目逐漸減少，而且變異概率也變小，保證了算法向最優(yōu)值收斂，同時也加快了算法的運行速度。另一方面，為了減少算法的局部最優(yōu)化現象，引入了早熟檢測指標，實行“災變”，使算法能快速跳出局部最優(yōu)點。

[1]de Castro L N，Tmanis J．Artificial Immune Systems：A New Computational Intelligence Approach [M]．British：Springer Press，2002.

[2]羅印升，李人厚，張雷，等.人工免疫算法在函數優(yōu)化中的應用[J].西安交通大學學報，2003，37（8）:840-843.LUO Yin-sheng，LI Ren-hou，ZHANG Lei，et al.Application of artificial immune algorithm to function optimization[J].Journal of Xi’an Jiaotong University，2003，37（8）:840-843.

[3]陳曦，賀建軍，萬力，等.基于改進克隆選擇算法的函數優(yōu)化問題[J].湖南理工學院學報：自然科學版，2012，25（1）:34-37.CHEN Xi，HE Jian-jun，WAN Li，etal.The function optimization problem based on improved clonal selection algorithm[J].Journal of Human Institute of Science and Technology：Natural Sciences，2012，25（1）:34-37.

[4]張向榮，焦李成.基于免疫克隆選擇算法的特征選擇[J].復旦學報：自然科學版，2004，43（5）:926-929.ZHANG Xiang-rong，JIAO Li-cheng.Feature selection based on immune clonal selection algorithm[J].Journal of Fudan University：Natural Sciences，2004，43（5）:926-929.

[5]王俊，田玉玲.用于入侵檢測的動態(tài)克隆選擇算法的研究[J].計算機與數字工程，2010（6）:108-110.WANG Jun，TIAN Yu-ling.Study on dynamic clonal selection algorithm for intrusion detection[J].Computer& Digital Engineering， 2010（6）:108-110.

[6]劉倩，仇賓.基于克隆選擇算法的花卉圖像分割[J].計算機工程與應用，2012，48（14）:185-189.LIU Qian，QIU Bin.Flowers image segmentation based on clonal selection algorithm[J].Computer Engineering and Applications，2012，48（14）:185-189.

[7]叢琳，沙宇恒，焦李成.基于免疫克隆選擇算法的圖像分割[J].電子與信息學報，2006，28（7）:1169-1173.CONG Lin，SHA Yu-heng，JIAO Li-cheng.Application of immune clone selection algorithm to image segmentation[J].Journal of Electronics&Information Technology，2006，28（7）:1169-1173.

[8]徐佳，張衛(wèi).人工免疫系統(tǒng)中的抗體生成與匹配算法[J].計算機工程，2010，36（9）:181-183.XU Jia，ZHANG Wei.Antibody generation and matching algorithm inartificialimmunesystem[J].ComputerEngineering，2010，36（9）:181-183.