免疫克隆选择算法的改进及其应用

邱亚龙,张 昕,范妙炳,叶奕纯,陈 婷

(华南农业大学 数学与信息学院,广州 510642)



免疫克隆选择算法的改进及其应用

邱亚龙,张 昕,范妙炳,叶奕纯,陈 婷

(华南农业大学 数学与信息学院,广州 510642)

摘 要:基于生物免疫系统原理,提出了改进的免疫克隆选择算法.引入网割预处理,获得进化终止次数并使初始抗体集的多样性得到控制; 采取震荡变异法提高算法的局部搜索精度; 引入记忆机制,提高二次免疫收敛速度.本文应用此算法针对大气污染损害率普适公式进行参数优化,结果显示改进算法在全局与局部范围内搜索更为细腻,提高了求解精度.

关键词:免疫克隆选择算法; 抗原预处理; 震荡变异; 大气污染损害率普适公式; 参数优化

1　免疫克隆选择算法

关于免疫克隆选择算法(以下称“ICSA”)在国内的研究,刘若辰[1]提出了多种克隆选择改进方法,如借助生物免疫系统的抗体克隆选择机理,构造适用于人工智能的克隆算子,并系统探讨了基于该算子的免疫克隆策略算法的性能,借鉴免疫学克隆选择和免疫记忆机理,提出新的人工免疫系统算法,称为免疫记忆动态克隆策略.

ICSA主要包括选择、克隆、变异和消亡四个步骤,强调基于抗体与抗原的亲和度大小及比例进行抗体选择和克隆; 每次迭代后保留优良抗体群; 并采取随机方式产生新抗体以替代旧抗体,扩大搜索区域,在一定程度上避免陷入局部峰值[2].

传统ICSA存在局部搜索精度不高,初始抗体集多样性不足,多峰搜索能力效果不佳等缺点[3].针对这些不足,诸多学者进行了改进研究.例如: 采取免疫记忆的动态克隆策略方法[1]、基于克隆选择算法的改进[4]、基于混合免疫克隆选择算法与差分进化的优化方法[5]、基于Parzen密度估计的多目标免疫克隆聚类方法[6]和基于克隆变异启发的克隆选择算法[7]等,这些改进的算法都在一定程度上优化了传统ICSA算法的不足.

本文针对传统ICSA存在的初始抗体集多样性不确定、进化终止次数不好控制、局部搜索能力不佳和二进制编码面临的“维数灾”等不足[2],对ICSA算法进行改进.

2　改进的免疫克隆选择算法

本文改进的免疫克隆选择算法在继承传统ICSA大体框架的基础上引入网割预处理、震荡变异策略以及免疫记忆机制,以下是该改进算法核心思想.

(1)引入抗原预处理.首先在首次免疫时,对抗原(即待优化的问题)进行解析,创建抗体进化所需环境.首先,分析问题参数个数、参数取值范围与精度等信息; 其次,根据相应公式计算抗体的网割空间(即问题的解空间)所需的网割因子(即控制网割空间数量的一组参数)以及进化终止次数; 第三,在网割后各个细小空间中产生一定数量的初始抗体,解决初始抗体集的多样性不确定性问题; 并且动态获取进化终止次数,解决了进化次数不好控制的问题.

(2)自适应变异空间.抗体的变异空间由组成抗体的基因变异半径(即单个变量的增量范围)确定; 基因的变异半径由进化次数、抗体—抗原亲和度(即抗体优良性指标)与抗原决定簇确定; 抗原决定簇的内容由基因值可行域(即变量定义范围)、变量精度控制组成.经试验,自适应变异空间有效解决了搜索空间难以确定的问题,提高了变异操作的效率,是震荡变异法的基础.

(3)震荡变异法.震荡变异法先在自适应变异空间内产生一个变异增量,随机转化为正值或负值再与原始抗体相加得到变异抗体,据此提高抗体基因的变异效率.

2.1 网割预处理

网割预处理是指在产生初始抗体集前先对目标函数的参数个数、参数精度与参数取值范围进行解析,从而确定进化终止次数T和网割因子Gj.根据网割因子将目标函数的解空间划分为一定数量的细小空间,在网割空间各个范围内的细小空间中产生一定数量的抗体,所有抗体组成初始抗体集,如此便达到控制初始抗体集多样性的目标.

终止次数T的计算公式为

网割因子Gj的计算公式为

其中n是变量个数,ΔRj是变量j定义范围大小的绝对值,Sj是变量j的精度,Tmax与Gmax为自定义值.

2.2 克隆

抗体克隆规模与抗体亲和度成正比.通过克隆可提高优良抗体浓度,加速提高变异后抗体群的平均亲和度,从而加快算法的收敛速度; 记克隆总规模的松弛上限为W ,则第i个抗体的克隆规模为

2.3震荡变异法

震荡变异法是先在变异空间内产生一个变异增量,接着随机转化为正值或者负值,再与原始基因值相加才得到变异基因值; 它是基于自适应伸缩的变异空间以及采用双重变异空间策略来提高变异效率的一种新型算法.

传统遗传算法有两种变异方式: 一种是适用于二进制编码的0、1变异法; 另外一种是适用于十进制编码的现行搜索法.而震荡变异法可有效地避免传统遗传算法由于这两种变异方式造成的随机漫游问题.

2.3.1自适应变异空间

变异半径是指变异前后单个基因值增量的取值范围,两个基因的变异半径构成变异平面,多个基因(3个以上)的变异半径构成变异空间.第i个抗体第j个基因的变异半径为

其中ΔRj是第j个参数定义范围大小的绝对值; Sj是第j个参数的精度要求位数; t是当前进化代数; T是终止迭代次数; p是变异半径调节因子,其值与亲和度有关; r是加速因子.

由正向变异半径计算公式可知,由此构成的变异空间具有基于抗体亲和度、基因值取值范围与进化次数的自适应伸缩特性; 当基因值与亲和度不变时,随着迭代次数的增加,正向变异空间的整体变化趋势呈S型递减.

传统ICSA虽然每次迭代次数较快,但求解精度不高; 而改进的算法在收敛后期,随着向最优解逐渐逼近,变异空间缓慢缩小,求解精度逐渐提高; 甚至可以通过改变最大、最小变异空间调节因子与迭代次数来调节变异空间,达到具体的精度要求.

2.3.2震荡变异效果

当抗体只有一个基因发生震荡变异时,该抗体会以自身为中心,在变异半径的方向上震荡,如图1所示; 当抗体有两个基因(若有)发生震荡变异时,该抗体就以自身为中心,在变异平面上震荡,如图2所示;当多个基因发生变异时,抗体将会以自身为中心,在变异空间上震荡; 若采用基于抗原—抗体亲和度的选择方式(亲和度较高的抗体被选择),随着迭代次数的增加,震荡变异后的抗体群就会快速向峰值靠拢,如图3所示.

图1 单个基因变异示意图　

图2 抗体变异的平面

图3 震荡变异三维效果图

2.4免疫记忆机制

免疫记忆机制模仿生物免疫系统的记忆功能,对首次感染,初始抗体集全部以网割的方式随机产生;而二次感染时,初始抗体集部分由记忆细胞分泌产生,部分以网割方式最优产生,即在网割随机产生的抗体集中选择亲和度较高的抗体.

2.5改进的免疫克隆选择算法流程

改进的免疫克隆选择算法流程如图4所示.

图4 改进的免疫克隆选择算法流程图

3　实际应用

3.1 应用背景

韩旭明、王丽敏[2]2013年根据评价大气质量的目标函数,采用引入疫苗接种策略和高斯变异算子的免疫克隆选择算法(ICSA-VSLGMO)对大气污染损害率普适公式进行参数优化,进而提出基于免疫克隆选择算法的大气质量评价模型和评价方法.在对吉林省某城市的大气进行评价时,结果与该城市利用API法得到的评价结果有微小出入; 这很有可能是ICSA-VSLGMO针对大气污染损害率公式参数优化结果的精度不高造成的.

而采用本文改进的免疫克隆选择算法优化参数后得到了精度更高、收敛更稳定的结果,从而得到了更准确的大气质量评价模型.

3.2 算法实现

3.2.1 大气污染损害率普适公式

钱莲文[8]等在L.D.詹姆斯、李祚泳等前人研究成果基础上,引入一个与污染物特性无关的普适参数c ,将原有公式进行改写,得到对多种大气污染物均适用的、具有更强普适性的大气污染损害率计算公式:

3.2.2构造目标函数

国家公布的《环境空气质量标准(GB3095—1996)》中列出了7种污染物的各项指标,见表1.

表1 国家《环境空气质量标准(GB3095—1996)》

根据5个级别的标准浓度与基准浓度值,大气污染的实际情况以及文[8],建立目标函数:

其中m为污染物种类数目; K为大气污染程度的分级数; Rik为i污染物k级污染损害率; Rke为k级标准的污染损害率的目标值.

3.2.3亲和度公式

根据目标函数可得第i个抗体—抗原亲和度公式:

其中fi∈(0,1); w、λ是灵敏度调节参数; fi(x)是第i个抗体的目标函数值.

3.2.4 编码

采用实数制编码.经多次实验,取待优化的参数a、b、c区间范围分别为(0,100),(0,1),(0,1),再加上目标函数值与亲和度,每个抗体的数据结构是一个1× 5的矩阵,如图5所示.

由此得相关抗体集的数据结构,见表2.

图5 抗体数据结构

表2 各抗体集数据结构

3.2.5算法具体步骤

步骤1 抗原预处理.将待优化参数a、b、c的取值范围分别划分为5个等长的小区间,然后进行全排列得到125个网割空间;

步骤2 抗原识别.检测记忆细胞M是否存在且完整(即检测存放抗体集的文件是否存在,以及文件内容是否完整),若存在转至步骤4,否则转至步骤3;

步骤3 首次感染.在步骤1中得到的每个网割空间内均产生一个抗体,组成初始抗体集iP ,并计算亲和度,在亲和度公式(8)中,令参数w =15 ,λ=0.06 ,转至步骤5;

步骤4 二次感染.初始候选解集iP中,30%的抗体集由记忆细胞M分泌产生,其余抗体由网割最优产生,分泌过程由克隆与变异操作组成;

步骤5 选择.从初始抗体集iP中选出亲和度较高的30个抗体组成临时记忆集tP ;

步骤6 克隆.克隆规模参数W设置为50,基于亲和度,将临时记忆集tP进行克隆,得到规模为50的克隆抗体集cP ;

步骤7 变异.对克隆抗体集Pc进行变异操作,得到变异抗体集Pm,其中加速因子r =0.168 ;

步骤8 消亡.在变异抗体集Pm中选择40%的亲和度较低的抗体重新初始化;

步骤9 再选择.从临时记忆集tP和变异抗体集Pm中选择较优的共30个抗体并更新临时记忆集tP ;

步骤10 判断是否达到迭代终止次数或平均亲和度是否达到理想值,是则转步骤11,否则转步骤5;

步骤11 向记忆细胞分化.①若首次感染则从临时记忆集tP中选择较优的20个抗体组成记忆细胞M ;②若为二次感染,则检测是否得到比上次感染更优的抗体,若得到更优的抗体就更新记忆细胞M ,否则不更新记忆细胞.完成分化后即转至步骤12;

步骤12 输出最终解.输出临时记忆集tP中亲和度较优的20个抗体;

3.3 试验结果比较

关于大气污染损害率公式参数优化问题,在4种已有的算法: 传统的ICSA,引入疫苗接种策略的免疫克隆选择算法(ICSA-VS),引入局部高斯变异算子的免疫克隆选择算法(ICSA-LGMO)以及引入疫苗接种策略和高斯变异算子的免疫克隆选择算法(ICSA-VSLGMO)之中,ICSA-VSLGMO算法的参数优化结果最佳,见表3[2]; 表4是采用本文改进的免疫克隆选择算法得到的优化结果; 图6～9是这两种算法针对大气普适公式的三个参数优化结果的对比.

表3 ICSA-VSLGMO 算法得到的目标值及参数a、b、c的值　

表4 本文改进的免疫克隆选择算法得到的目标值及参数a、b、c的值

图6 前20个抗体参数a的值 　

图7 前20个抗体参数b的值

图8 前20个抗体参数c的值 　

图9 两种算法前20个抗体目标值

比较结果可知,本文改进的免疫克隆选择算法在全局和局部范围内搜索更为细腻,求解精度进一步提高,并且更为稳定; 而且本算法引入免疫记忆机制,在二次运行算法时,收敛速度更快(迭代次数在20次以内)、更稳定,精度更高(达到小数点后8位).

4　结束语

本文改进的免疫克隆选择算法基于解析抗原决定簇,采用基于自适应伸缩变异空间的震荡变异法,有效地解决了传统ICSA存在的搜索精度不高、初始抗体集多样性不足和多峰搜索能力效果不佳等缺陷;并且引入免疫记忆机制,在二次感染时提高收敛速度和求解精度,从而丰富了传统免疫算法的内容.将改进算法针对大气污染损害率普适公式进行参数优化,实验结果表明,与当前韩旭明,王丽敏改进的ICSA-VSLGMO算法相比,本文改进的算法在全局和局部搜索能力上更细腻,求解精度更高,从而提高了大气质量评价模型的准确性.

参考文献

[1] 刘若辰.免疫克隆策略算法及其应用研究[D].西安: 西安电子科技大学智能信息研究所博士学位论文,2005

[2] 韩旭明,王丽敏.人工免疫算法改进及其应用[M].北京: 电子工业出版社,2013

[3] 徐 锐.人工免疫算法优化及其用研究[D].上海: 上海大学电子生物技术研究中心博士学位论文,2009

[4] 陈 林,姚宏亮.免疫克隆遗传算法在物流配送中的应用[J].河南科技学院学报,2012,40(5): 70～74

[5] 叶洪涛,罗文广,吴 艳.一种基于差分进化和免疫克隆选择算法的混合优化方法[J].计算机应用研究,2013,30(4): 2～3

[6] 秦 亮,张文广,史贤俊,等.基于免疫克隆算法的多目标聚类方法[J].信息与控制,2013,42(1)8～12

[7] 胡江强,郭 晨,李铁山.启发式自适应免疫克隆算法[J].哈尔滨工程大学学报,2007,28(1): 1～5

[8] 钱莲文,吴承祯,宏 伟,等.大气质量评价的污染危害指数的改进[J].福建林学院报,2003,23(3): 249～252

Application and Improvement of Immune Clonally Selection Algorithm

QIU Ya-long,ZHANG Xin,FAN Miao-bing,YE Yi-chun,CHEN Ting
(College of Mathematics and Information,South China Agricultural University,Guangzhou 510642,China)

Abstract:Based on the principle of biological immune system,an improved immune clonally selection algorithm(ICSA)was proposed.The algorithm introduced the analysis of antigenic determinant,calculated the network cut factor of antibody space and the end times of antibodies evolution,and created environment required to produce antibodies; shock variation method was adopted to make antibodies mutated; Innovative space adaptive mutation was proposed creatively; The improved ICSA was applied to analyze the parameters optimization problem of the atmospheric pollution harm rate universal formulaThe results show that the algorithm within the scope of the global and local search is more exquisite.Solution accuracy is significantly increased.

Key words:immune clonally selection algorithm,antigen pretreatment,concussion variation,damage rate universal formula of air pollution,parameter optimization

通讯作者:张 昕(1968−),男,湖南邵阳人,华南农业大学数学与信息学院副教授.主要研究方向: 数值计算

作者简介:邱亚龙(1988−),男,广东阳江人,华南农业大学数学与信息学院硕士研究生.主要研究方向: 智能计算

基金项目:广东省大学生创新创业项目(201410564201)

收稿日期:2016-01-05

中图分类号:TP301.6

文献标识码:A

文章编号:1672-5298(2016)01-0027-06