一种改进的免疫克隆选择算法

牛永洁，马亚玲

（1.延安大学 计算中心，陕西 延安 716000；2.河南中医学院 图书馆，河南 郑州 450008）

克隆选择算法是人工免疫系统中一种经典的免疫算法模型，2002年由De Castro根据生物免疫系统理论中的克隆选择学说而提出[1]，这种算法简称为CLONALG。由于克隆选择算法具有并行性、自适应性、学习、识别和记忆等优点，很快被应用到函数优化[2-3]、特征选择[4]、入侵检测[5]、图像分割[6-7]、机器学 习[8]等领域 。

但是CLONALG算法具有收敛速度慢、搜索能力弱、易陷入局部最优的缺点，本文对CLONALG算法在4各方面进行了改进，改进后的算法在收敛速度、搜索能力等方面都有显著的改善。通过实验仿真，发现效果良好。

1 克隆选择算法

克隆选择算法主要经过初始化、选择、克隆、变异、替换5个阶段，在系统初始化阶段随机生成N个问题域的可能解，在算法中被称为抗体，抗体被分为两个部分，一部分为记忆细胞M和剩余群体P，按照抗体和抗原的结合程度衡量抗体的优劣，结合度高的抗体表示能够解决抗原带来的问题，即结合度高的抗体更接近于问题的解，从种群中选择n个结合度较高的抗体，然后进行克隆，对克隆后的抗体进行高频变异，变异完成后将种群中C个抗体用重新随机生成的抗体替换，然后重新进行选择。这就是克隆选择的基本思想。

标准的克隆选择算法的运行步骤如下：

1）在问题的定义域中随机生成候选抗体集合H，集合中有抗体N个，N为种群规模的大小。

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是群体规模，α为克隆调节系数。第二个方面是随着算法的迭代进行，即使亲和度相同的抗体，其克隆的数量也应递减，这样即能保证算法的收敛速度也能保证算法后期不出现震荡。所以公式（1）应调整为公式（2）

公式（2）中Iter是算法的迭代次数，β是一个负值的调整系数，λ为算法开始时的克隆数目。改进后的算法在进行抗体克隆时，一方面与自身的亲和度成正比关系，而且随着算法的迭代运行，每个抗体的克隆数量是呈线性递减的。

2）变异概率的自适应变化

抗体经过克隆后，需要进行高频变异操作，随着算法迭代进行，变异的概率应该逐渐线性递减。以保证算法后期的收敛。变异概率的变化规律使用公式（3）进行。

其中mk是第k次迭代的变异概率，而mk+1是第k+1次迭代的变异概率，参数ρ是一个大于零小于1的调整参数。

3）替换策略的改进

标准的克隆选择算法是完全随机生成一定数量的抗体，然后将集合H中的d个低亲和度的抗体替换掉。本算法对生成的新抗体进行限制，要求新生成抗体的平均亲和度要大于等于集合Pn的平均亲和度。

4）变异概率和克隆数量的突变

为了预防算法在运行过程中的局部收敛而造成的算法停滞，文中引入早熟检测指标Dp，当Dp≤ξ时，则将变异的概率增大k倍，同时对替换的抗体采用完全随机策略，不再要求抗体的平均亲和度大于等于集合Pn的平均亲和度。文中k的取值为1.4倍。当Dp>ξ，抗体的变异规律和替换策略恢复正常。文中ξ取值为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）采用两种不同算法最优亲和度和抗体平均亲和度运行图。

4 结 论

图3 CLONALG算法运行时的最优、平均亲和度Fig.3 Optimal and average affinity of CLONALG

图4 新算法运行时的最优、平均亲和度Fig.4 Optimal and average affinity of new algorithm

通过对基本的克隆选择算法进行4个方面的改进，得到一种新的算法，使用两个多峰值函数对将新的算法进行了验证。新算法采用抗体克隆数和变异概率随着算法的运行线性递减的策略，同时对抗体的克隆数量采用与抗体本身亲和度成正比的方法，能够保证在算法运行初期充分的变异和对优秀抗体充分复制克隆，在全面搜索解空间的前提下，尽量保持优秀抗体的存在，算法后期为了减少算法运行的震荡，抗体克隆的数目逐渐减少，而且变异概率也变小，保证了算法向最优值收敛，同时也加快了算法的运行速度。另一方面，为了减少算法的局部最优化现象，引入了早熟检测指标，实行“灾变”，使算法能快速跳出局部最优点。

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

[2]罗印升，李人厚，张雷，等.人工免疫算法在函数优化中的应用[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]陈曦，贺建军，万力，等.基于改进克隆选择算法的函数优化问题[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]王俊，田玉玲.用于入侵检测的动态克隆选择算法的研究[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]徐佳，张卫.人工免疫系统中的抗体生成与匹配算法[J].计算机工程，2010，36（9）:181-183.XU Jia，ZHANG Wei.Antibody generation and matching algorithm inartificialimmunesystem[J].ComputerEngineering，2010，36（9）:181-183.