用于函数优化的改进免疫克隆多样性算法

第25卷第1期　　　　　　　　　　哈　尔　滨　工　程　大　学　学　报　　　　　　　　　　　Vol. 25№. 12004年2月　　　　　　　　　　　Journal of Harbin Engineering University 　　　　　　　　　　　　Feb. 2004

用于函数优化的改进免疫克隆多样性算法

莫宏伟, 金鸿章

(哈尔滨工程大学自动化学院, 黑龙江哈尔滨　150001)

摘　要:免疫系统具有许多可以用于解决工程和科学问题的特性, 人工免疫系统是基于免疫系统特性而发展的新兴智能系统. 针对免疫算法的多样性, 利用免疫系统克隆选择和克隆抑制机制, 提出一种用于函数优化的改进免疫克隆多样性算法, 以达到简化复杂系统函数算法的目的. 多样性算法是一种基于免疫系统抗体多样性机制而开发的免疫算法, 这里给出了改进的算法步骤, 指出改进算法与原算法的主要区别以及所依据的免疫系统原理; 文章还对算法的复杂性进行了分析, 证明了改进免疫系统克隆多样性算法可以利用相对小的候选解群体解决复杂函数优化问题.

关键词:免疫系统; 人工免疫系统; 多样性算法; 函数优化

中图分类号:TP18　文献标识码:A　文章编号:1006-7043(2004) 01-0076-04

The modif ied immune diversity algorithm used in f unction

optimization

MO Hong 2wei ,J IN Hong 2zhang

(School of Automation ,Harbin Engineering University ,Harbin 150001,China )

Abstract :The immune system has many characteristics to solve engineering and science problems. An artificial immune system is a novel intelligence system based on the characteristics of a real 2life immune system. By using clone selection and clone suppression ,the modified immune clone diversity algorithm in accordance with diversi 2ty ,an algorithm used to solve the function optimization is presented to obtain a simplified algorithm for complex functions. The diversity algorithm is a developed algorithm based on the diversity of antibodies in the immune system. The concrete steps are presented ,and the main differences between them are identified. The dependence principles of immune systems are also pointed out and the complexity of computation is analyzed. The paper shows that the modified immune clone diversity algorithm can optimize the complex functions by using fewer candidate solution colonies.

K ey w ords :immune system ;artificial immune system ;diversity algorithm ;function optimization

　　自然免疫系统所使用的学习/自适应机制能够连续产生负责检测和破坏外部分子的新抗体种类. 研究表明, 虽然人类基因组含有大约105个基因(实为3万个左右) , 但它能产生识别至少1016个病原体的抗体指令系统. 免疫系统的抗体多样性是其病原体识别能力的关键.

基于免疫学原理而发展的新兴智能—人工免疫系统(A IS ) 已经用于处理计算机安全等多种工程和科学问题[1].

这里对免疫多样性算法进行改进, 利用免疫系统克隆选择和抑制机制提出简单而有效的算法, 解

收稿日期:2003-04-14.

基金项目:国家自然科学基金资助项目(60305007) . 作者简介:莫宏伟(1973-) , 男, 讲师.

金鸿章(1946-) , 男, 教授, 博士生导师.

决多模式优化问题. 根据所依据的免疫克隆原理将算法称为改进免疫克隆多样性算法. 与病原体和抗体表示为二进制字符串的二进制A IS 相对, 本算法用更自然的实数值表示, 减少算法参数转换的复杂性, 提高计算效率.

给出的算法结合了许多免疫系统的机制, 在集合上X ΑR n , 辨别一个具有n 个变量的函数的尽可能多的局部最优值, 其中X 是区间[x i , min , x i , max ], i =1, …, n 的Cartesian 积. 采用实数值候选解表示法, 给出算法的概念性框架.

1　多样性算法回顾

Forrest [2],Smith [3]提出一个与遗传算法结合的免疫系统模型, 用于进化一组识别多样病原体的抗

第1期　　　　　　　　　　　莫宏伟, 等:用于函数优化的改进免疫克隆多样性算法・77・

体. 模型使用二进制免疫系统, 抗原用固定长度的二进制字符串表示, 由此建立了多样性算法(DA ) . 同时指出了免疫系统的如下性质:

1) 免疫系统一般比较频繁地遇到病原体.

2) 免疫系统只用那些与抗原有反应的淋巴细胞子集产生应答.

3) 存在对抗原的竞争, 这样以最高亲和力结合抗原的细胞扩增得最快.

4) 抗体通过体细胞变异改进与抗原的结合能力.

对算法性能的仔细分析表明它有2个基本特征. 首先,DA 在一个给定的个体群体内保持子群体多样性. 从抗原的相似性(海明距离度量) 方面来看, 在一个群体内, 子群体的多样性难以区分. 对于规模较小的样本, 可以通过对一般模式辨别, 进化抗体使其泛化去匹配所有抗原. 对规模较大样本, 则产生专一抗体, 每一个专一抗体可以匹配多种抗原类型中的一种抗原. 其次, 多样性子群体形成机制类似G A 的适应度共享机制. 但是, 多样性算法不考虑峰值数和峰值之间的距离, 在动态地确定峰值数的意义上讲, 适应度共享机制在该算法中是隐含的.

Forrest 使用的DA 总结如下:1) 提呈抗原给系统;2) 发现与抗原具有最高亲和力的抗体;3) 进化抗体群体. 由于用G A 实现进化, 在步骤3) 之前, 要给每一个抗体分配适应度值.

4) 对每一对, 检查和的刺激程度. 根据设定的阈

值, 受刺激强烈的抗体在A b 中被保持. 而不受刺激的或较弱的抗体从A b 中被清除(克隆抑制) ;

5) 用克隆产生的新抗体替换A b 中受刺激较弱

的抗体(亚动力过程) ;

6) 重复2) ～5) 直到满足一定误差要求. 对步骤1) ～6) 详细说明如下:

每一步都与免疫系统中的免疫机制相对应. 在步骤1) 中, 放弃原多样性算法从A b 群体中选择一个抗体样本的做法, 这与解决的具体问题有关, 本文目的是使算法适用于优化问题. 固定抗体群体而不是随机产生, 就可以使用原算法的一些参数设置. 但是如果抗体群体不明确, 则这个过程无效.

原多样性算法采用变异算子对二进制抗体进行变异, 改进算法利用实数值表示. 通过对一个给定抗体加入来自某区间的随机数来产生变异. 产生一个抗体a =(x 1, …x n ) 的克隆变异c (a ) =(y 1, …y n ) 的最简单的方法是使用如下规则:

y i =x i +Δαi i max [0, 1) , i =1, …n.

(1)

式(1) 中:αi 是一个窄化搜索区域因子, i 是当前循环数, max [0, 1) 表示从0到1的均匀分布随机变

量. 其中

Δi =

x i , min -x i , if max [0, 1)

(2)

2　改进免疫克隆多样性算法

生物免疫系统获得多样性的主要机制是克隆选择即有选择地产生能够有效地与抗原反应的抗体克隆变异. 在抗体为了匹配抗原而快速变异进化期间, 没有抗体基因交叉现象, 而研究表明, 变异能够比交叉提供更高水平的基因分裂和开采

[4]

　　上式表示每次随机地选择一个Δi . 这样, 每一个y i 准确地位于一个对应区间[x i , min , x i , man ]内.

随着循环数增加, αi 减少, 搜索空间也逐渐减小. 这里采用均匀变异而不是高斯变异, 是因为后者只能产生位于原始抗体附近的变异, 而均匀变异则产生远离原始抗体的变异.

步骤3) 与独特型免疫网络理论[5]一致, 产生免疫记忆, 免疫记忆指在生物免疫系统中, 对入侵抗原初次应答后, 系统会保留一些受抗原刺激最强的免疫细胞做为记忆细胞, 其上有受抗原刺激最强的抗体记忆, 当同样的或者变异的抗原再次入侵时, 这些记忆细胞上的抗体会做出比初次应答更快更强的反应. 为了保持固定规模的抗体群体, 算法采用原多样性算法使用的最佳匹配策略, 也就是计算一个给定抗体a 的克隆c a 的受刺激程度S i =1-d (a , e ) , d (a , e ) 为克隆与抗原之间的Euclidean 距离, 确定其中受刺激最强的克隆, 也就是克隆与抗原之间的Euclidean 距离最小的克隆, 然后计算(a , c a ) 中哪一

, 从而产生多

样抗体. 本算法利用这些思想对上述多样性算法进行改进, 改进的算法与原多样性算法的第一个不同

. , 明确指定抗体集合, 与在原来的多样性算法中的随机产生抗体的方法相对. , 抗原对应一个函数的最优值, 抗体则对应寻优过程中的一系列数值. 2. 1　算法步骤分析

改进免疫克隆多样性算法步骤如下:1) 建立一个有限抗体集合A b ;

2) 对每一个抗体产生克隆变异集合C , 克隆数

目与a 的当前适应度成比例(细胞克隆) ;

3) 对每一个抗体选择一个对该抗原具有最高亲个受抗原刺激更大, 并将其保留下来, 即模拟免疫系

统中的免疫记忆机制, 这是算法模拟的第一个免疫机制.

和力的克隆(克隆选择) ;

之后计算f (a ) 和f (c a ) 的值, 其中f 表示优化的函数, 并选择其中的一个做为优化结果. 步骤3) 控制算法解空间开发过程, 步骤4) 体现算法的解空间勘探性质.

步骤5) 模拟免疫系统获得高度多样性的第二个机制, 即抗体之间的相互识别和被识别, 实现相互之间的促进或抑制. 实现方式很多, 最简单的是在

A b 集合中清除受刺激较弱的抗体; 另一个更好的

个函数测试算法的能力:

一个是修改后的10维Grievank 函数:

G (x 1, …, x 10) =

i =1

∑x 2/4000-i

i =1

cos (x /∏

i ) , x i ∈[-600, 600], i =1, …10;

另一个是20维Rastrigin 函数:

R (x 1, …x 20) =200+

方法是模拟免疫网络中抗体之间相互促进或抑制的机制, 引入网络抑制机制, 这样能防止抗体集合收敛到某单个抗体. 在解决多模式优化问题时, 这是很有用的. 从形式上看, 步骤5) 类似文献[6]提出的squashing 方法. 经验研究证明当一个算法利用适应

i =1

∑(x 2-i

πx i ) ) , 10cos (2

x i ∈[-5. 12, 5. 12], i =1, …, 20.

度机制搜索多峰值时, 对于有效保持不同子群体, squashing 是一种有用的方法. 但是,squashing 方法

不能单独辨别全部峰值. 这一步可以加强算法的收敛性, 因为不符合条件的值都被及时剔除; 6) 的终止条件是根据输出结果与被优化函数最优值之间的误差确定的. 满足误差范围, 则终止算法运行.

在步骤上与原算法比较, 第2步与原多样性算法有所不同, 就是变异整个抗体群体(原算法中是规

模为σ的随机样本) . 抗体变异后, 选择变异抗体用于下次循环. 第5步是对原多样性算法的进一步修正, 加速算法的收敛.

步骤1) ～6) 形成一个类似[7]的框架算法. 该算法模拟了Farmer 等人的描述的经典独特型免疫网络[8],De Castro 成功地应用过该原理设计出另一种免疫算法

[5]

　　这些函数是已知的、较难的全局优化测试函数. 比如Grievank 函数在[-600,600]10含有500个局部最小值, 集中在位于原点的全局最小值附近.

对这些情况, 用改进的免疫多样性算法发现全局最优值极为简单. 在实验中使用如下参数:记忆规模|A b |=20,10个测试抗体产生变异(最佳抗体产生20个变异, 剩下的9个每一个产生10个变异) , 用随机产生的新个体取代5个最差的抗体. 将算法步骤2) ～5) 重复400次. 将算法的单独运算称为周期. 得到的结果如表1.

表1　30个周期的平均结果

T able 1　The average results of 30epochs

优化函数

Grievank Rastrigin

最佳解

0. 003670. 00635

平均解最佳解

0. 04070. 0644

2. 2　算法复杂性分析

在第一步, 假设A b 集合规模为N ; 从第二步开始循环, 在第二步假设一个抗体每次产生n 个克隆; 第三步, 对每个抗体的克隆只选择一个与抗原亲和力最高的克隆, 也就是最接近最优值的数值, 所以计算频率为1, 之后将抗体与其产生的对抗原亲和力最高的克隆进行比较, 计算频率为1. 所以一次循环的计算频率为n +1+1, N 个抗体的总计算频率为N 3(n +1+1) , 所以算法计算复杂性=O (N 3

(n +2) ) =O (N 3n ) , 呈非线性复杂性. 这是算法

与其他具有局部搜索优化方法的混合遗传算

法[9]相比较, 包括:1) G A +Solis -Wets 方法;2) G A +conjugate gradient.

这些算法采用不同概率:0. 0625,0. 25和1. 0(在每次循环) . [9]的结果如表2, 对应符号后的数字是使用L S 优化方法的概率. 比较表1和表2, 可看到免疫算法比G A 更好. 只有使用Grievank 函数, G A -CG 方法的性能才能超过改进的免疫多样性算法性能.

图1是步骤5) 实现没有细胞凋亡(不取代刺激较弱的抗体) 的多样性免疫算法收敛性, 表明用新个体取代刺激较弱的抗体能极大地改进了算法收敛性. 灰线表示只由步骤2) ～4) 组成的算法的收敛.

实验中还对算法αi 参数递减速率的敏感度进行测试. 在实验中假设参数在每T 次循环, 几何级

i/T α数递减, 也就是如果(t mod T ) =0. 1, αi =(r ) i .

图2是αi 在免疫算法收敛性上的影响. 速率越低, 收敛越好.

需要改进的地方.

下面给出例证算法效率的数字结果.

3　函数优化

3. 1　在给定区间上发现全局最优值

从免疫观点看, 在区间X 上发现最优值的问题等同于在进化抗体群体辨别单个抗原. 这里使用两

表2　G as 和G A -L S 混合算法的平均性能

T able 2　The average performance of G as and

G A -LS hybrid algorithms

4　结　论

提出一个受免疫系统细胞克隆机制启发的优化

函数的改进的算法, 当前的结果表明主要的免疫机制(克隆选择和抑制) 能成功的用于工程问题. 利用相对小的候选解的群体能解决复杂的函数优化问题. 对算法还需要进一步研究, 给出算法更多自由度. 需要研究如何控制参数, 或者如何定义步骤4) 要求的候选个体的相似度, 以及降低算法计算复杂性, 对算法进行进一步调整以应用于多模式函数优化.

方法

G A

(a ) 0. 0625(b ) 0. 25(a ) 1. 0(b ) 0. 0625(a ) 0. 25() Rastrigin Normal 166. 3102. 986. 875. 3103. 8117. 8Elitist 3. 618. 437. 950. 024. 240. 8Grievank Normal 0. 260. 220. 090. 130. 021. 2・10-9-19

Elitist 0. 07

0. 110. 040. 088. 6・10-41. 0・10-19-

参考文献:

[1]莫宏伟. 人工免疫系统原理与应用[M ].哈尔滨:哈尔滨

工业大学出版社,2002.

[2]FORREST S ,JAVORN IK B ,SMITH R ,etal. Using genetic algorithms to explore pattern recognition in the Immune System[J].Evolutionary Compuation , 1993, 1(3) :191-211.

[3]SMITHR , FORREST S , PEREL SON A S. Searchin g for diverse , cooperative populations with genetic algorithms[J].Evolutionary Compuation ,1993,1(2) :127-149.

[4]SPEARSW M. Proc. 2nd foundations of genetic algorithms workshop (Whitley D , Ed. ) [C].San Mateo , CA :Morgan K aufmann , 1992.

[5]CASTRO L N , ZUBEN F J. Data mining :A heuristic ap 2proach[M ].Hershey :Idea Group Publishing , 2001. [6]G OLDBER G D E. G enetic algorithms in search , optimiza 2tion and machine learning [M ].Boston :Addison -Wesley , 1989.

[7]WIERZCHOA S T. Function optimization by the immune metaphor[J].Task quarterly ,2002,6(3) :1-16.

[8]FARMER J D , PACK ARD N H , PEREL SON A S. The immune system , adaptation , and machine learning , physica [J].Physica ,1986, (22) :187-204.

[9]HART E W. Adaptive global optimization with local search

[D].San Diego :Universityof California ,1994.

　　图1　改进免疫克隆多样性算法对Grievank 函数的

收敛性

Fig. 1　The convergence of modified immune clone diversity

algorithm to Grievank

function

　　图2　参数的减少率对改进免疫克隆多样性算法的

收敛的影响

Fig. 2　The influence of the reduction rate ofto the conver 2

gence of modified diversity immune clone algorithm

[责任编辑:陈　峰]

用于函数优化的改进免疫克隆多样性算法

莫宏伟, 金鸿章

(哈尔滨工程大学自动化学院, 黑龙江哈尔滨　150001)

关键词:免疫系统; 人工免疫系统; 多样性算法; 函数优化

中图分类号:TP18　文献标识码:A　文章编号:1006-7043(2004) 01-0076-04

The modif ied immune diversity algorithm used in f unction

optimization

MO Hong 2wei ,J IN Hong 2zhang

(School of Automation ,Harbin Engineering University ,Harbin 150001,China )

K ey w ords :immune system ;artificial immune system ;diversity algorithm ;function optimization

基于免疫学原理而发展的新兴智能—人工免疫系统(A IS ) 已经用于处理计算机安全等多种工程和科学问题[1].

这里对免疫多样性算法进行改进, 利用免疫系统克隆选择和抑制机制提出简单而有效的算法, 解

收稿日期:2003-04-14.

基金项目:国家自然科学基金资助项目(60305007) . 作者简介:莫宏伟(1973-) , 男, 讲师.

金鸿章(1946-) , 男, 教授, 博士生导师.

1　多样性算法回顾

Forrest [2],Smith [3]提出一个与遗传算法结合的免疫系统模型, 用于进化一组识别多样病原体的抗

第1期　　　　　　　　　　　莫宏伟, 等:用于函数优化的改进免疫克隆多样性算法・77・

体. 模型使用二进制免疫系统, 抗原用固定长度的二进制字符串表示, 由此建立了多样性算法(DA ) . 同时指出了免疫系统的如下性质:

1) 免疫系统一般比较频繁地遇到病原体.

2) 免疫系统只用那些与抗原有反应的淋巴细胞子集产生应答.

3) 存在对抗原的竞争, 这样以最高亲和力结合抗原的细胞扩增得最快.

4) 抗体通过体细胞变异改进与抗原的结合能力.

4) 对每一对, 检查和的刺激程度. 根据设定的阈

值, 受刺激强烈的抗体在A b 中被保持. 而不受刺激的或较弱的抗体从A b 中被清除(克隆抑制) ;

5) 用克隆产生的新抗体替换A b 中受刺激较弱

的抗体(亚动力过程) ;

6) 重复2) ～5) 直到满足一定误差要求. 对步骤1) ～6) 详细说明如下:

y i =x i +Δαi i max [0, 1) , i =1, …n.

(1)

式(1) 中:αi 是一个窄化搜索区域因子, i 是当前循环数, max [0, 1) 表示从0到1的均匀分布随机变

量. 其中

Δi =

x i , min -x i , if max [0, 1)

(2)

2　改进免疫克隆多样性算法

[4]

　　上式表示每次随机地选择一个Δi . 这样, 每一个y i 准确地位于一个对应区间[x i , min , x i , man ]内.

, 从而产生多

样抗体. 本算法利用这些思想对上述多样性算法进行改进, 改进的算法与原多样性算法的第一个不同

改进免疫克隆多样性算法步骤如下:1) 建立一个有限抗体集合A b ;

2) 对每一个抗体产生克隆变异集合C , 克隆数

目与a 的当前适应度成比例(细胞克隆) ;

3) 对每一个抗体选择一个对该抗原具有最高亲个受抗原刺激更大, 并将其保留下来, 即模拟免疫系

统中的免疫记忆机制, 这是算法模拟的第一个免疫机制.

和力的克隆(克隆选择) ;

步骤5) 模拟免疫系统获得高度多样性的第二个机制, 即抗体之间的相互识别和被识别, 实现相互之间的促进或抑制. 实现方式很多, 最简单的是在

A b 集合中清除受刺激较弱的抗体; 另一个更好的

个函数测试算法的能力:

一个是修改后的10维Grievank 函数:

G (x 1, …, x 10) =

i =1

∑x 2/4000-i

i =1

cos (x /∏

i ) , x i ∈[-600, 600], i =1, …10;

另一个是20维Rastrigin 函数:

R (x 1, …x 20) =200+

i =1

∑(x 2-i

πx i ) ) , 10cos (2

x i ∈[-5. 12, 5. 12], i =1, …, 20.

度机制搜索多峰值时, 对于有效保持不同子群体, squashing 是一种有用的方法. 但是,squashing 方法

在步骤上与原算法比较, 第2步与原多样性算法有所不同, 就是变异整个抗体群体(原算法中是规

模为σ的随机样本) . 抗体变异后, 选择变异抗体用于下次循环. 第5步是对原多样性算法的进一步修正, 加速算法的收敛.

步骤1) ～6) 形成一个类似[7]的框架算法. 该算法模拟了Farmer 等人的描述的经典独特型免疫网络[8],De Castro 成功地应用过该原理设计出另一种免疫算法

[5]

　　这些函数是已知的、较难的全局优化测试函数. 比如Grievank 函数在[-600,600]10含有500个局部最小值, 集中在位于原点的全局最小值附近.

表1　30个周期的平均结果

T able 1　The average results of 30epochs

优化函数

Grievank Rastrigin

最佳解

0. 003670. 00635

平均解最佳解

0. 04070. 0644

2. 2　算法复杂性分析

(n +2) ) =O (N 3n ) , 呈非线性复杂性. 这是算法

与其他具有局部搜索优化方法的混合遗传算

法[9]相比较, 包括:1) G A +Solis -Wets 方法;2) G A +conjugate gradient.

实验中还对算法αi 参数递减速率的敏感度进行测试. 在实验中假设参数在每T 次循环, 几何级

i/T α数递减, 也就是如果(t mod T ) =0. 1, αi =(r ) i .

图2是αi 在免疫算法收敛性上的影响. 速率越低, 收敛越好.

需要改进的地方.

下面给出例证算法效率的数字结果.

3　函数优化

3. 1　在给定区间上发现全局最优值

从免疫观点看, 在区间X 上发现最优值的问题等同于在进化抗体群体辨别单个抗原. 这里使用两

表2　G as 和G A -L S 混合算法的平均性能

T able 2　The average performance of G as and

G A -LS hybrid algorithms

4　结　论

提出一个受免疫系统细胞克隆机制启发的优化

方法

G A

(a ) 0. 0625(b ) 0. 25(a ) 1. 0(b ) 0. 0625(a ) 0. 25() Rastrigin Normal 166. 3102. 986. 875. 3103. 8117. 8Elitist 3. 618. 437. 950. 024. 240. 8Grievank Normal 0. 260. 220. 090. 130. 021. 2・10-9-19

Elitist 0. 07

0. 110. 040. 088. 6・10-41. 0・10-19-

参考文献:

[1]莫宏伟. 人工免疫系统原理与应用[M ].哈尔滨:哈尔滨

工业大学出版社,2002.

[2]FORREST S ,JAVORN IK B ,SMITH R ,etal. Using genetic algorithms to explore pattern recognition in the Immune System[J].Evolutionary Compuation , 1993, 1(3) :191-211.

[3]SMITHR , FORREST S , PEREL SON A S. Searchin g for diverse , cooperative populations with genetic algorithms[J].Evolutionary Compuation ,1993,1(2) :127-149.

[4]SPEARSW M. Proc. 2nd foundations of genetic algorithms workshop (Whitley D , Ed. ) [C].San Mateo , CA :Morgan K aufmann , 1992.

[7]WIERZCHOA S T. Function optimization by the immune metaphor[J].Task quarterly ,2002,6(3) :1-16.

[8]FARMER J D , PACK ARD N H , PEREL SON A S. The immune system , adaptation , and machine learning , physica [J].Physica ,1986, (22) :187-204.

[9]HART E W. Adaptive global optimization with local search

[D].San Diego :Universityof California ,1994.

　　图1　改进免疫克隆多样性算法对Grievank 函数的

收敛性

Fig. 1　The convergence of modified immune clone diversity

algorithm to Grievank

function

　　图2　参数的减少率对改进免疫克隆多样性算法的

收敛的影响

Fig. 2　The influence of the reduction rate ofto the conver 2

gence of modified diversity immune clone algorithm

[责任编辑:陈　峰]

用于函数优化的改进免疫克隆多样性算法

相关内容

热门内容

标签