论文遗传算法的研究和改进 - 图文

统主要由骨髓、B细胞网络、抗原和抗体等组成。人工免疫系统的许多处理包含在B细胞和它们的抗体里。B细胞网络是由一组B细胞实现，且这些B细胞之间相互连接。骨髓节点用于运行骨髓的功能却决定在免疫网络哪儿插入一个给定的抗原、哪个B细胞死亡激发一些新的细胞添加到免疫网络中。

该免疫算法的主要算法下所示： 调入抗原个体代

随机初始化初始B细胞个体代 直到满足终止条件do{

从抗原个体代中随机选择一个抗原

在B细胞网络中随机选择一点来插入抗原 选择B细胞地点/插入点的百分比 对于选择的每个B细胞

显现抗原给每个B细胞且要求免疫反应 若没有B细胞能结合抗原

产生一个新的能结合抗原的B细胞 按刺激水平来排序这些B细胞 删除B细胞个体代中最坏的5％

产生n个新的B细胞（n＝B细胞个体代的5％）

选择m个B细胞添加到免疫网络（m＝B细胞个体代的5%）}

骨髓节点通过显现抗原给B细胞，用于初始化免疫响应。在算法主循环的每次迭代以后，免疫系统节点也随即地产生新的B细胞，并被插入到免疫网络。B细胞是人工免疫系统中最复杂地概念，每个B细胞具有一个模式匹配元件，它是模拟自然免疫系统中抗体形成地机理来产生的。它允许复杂记忆和促使模式匹配文件的多样化。遗传机理采用一个基因库，这些基因用于形成许多表达（对应于DNA转换成蛋白质的过程），并最终形成抗体。B细胞也记录它的刺激水平且保持于网络中与之相连的其它B细胞的联系。当一个新的B细胞创建时，它以产生一个抗体的方式尝试映像基因选择、折叠、传输和翻译等步骤（这些步骤在自然免疫系统中B细胞里发生）。

3） 免疫遗传算法

遗传算法是一种多点搜索和采用交叉操作的技术，具有良好的全局搜索能力，但对于局部空间的搜索问题不是很有效，个体的多样性减少的很快。为了克服以上缺点，Chun等基于体细胞理论和免疫网络理论提出了一种免疫遗传算法。在这个算法中，将抗原作为目标函数、抗体作为解答、抗原和抗体之间的亲和力作为解答的联合强度。另外，一种结合免疫系统与遗传特性的免疫遗传算法也被提出。

4）免疫Agent算法

Ishida等基于免疫系统的局部记忆学说和免疫网络学说提出了基于Agent结构的人工免疫系统（B细胞可看作Agent），从而借助Agent的技术设计人工免疫系统及其免疫Agent算法。该算法分三步进行：（a）多样性产生；（b）自忍耐建立；（c）记忆非己。满意Agent算法可用于计算机病毒Agent的进化和网络防御系统，还被用于噪声的自适应控制。 5.2.4 人工免疫系统的应用

人工免疫系统正引起人们的极大重视，基于免疫系统机理的模型在科学和工程上将会取得越来

[53]

越多的应用。目前人工免疫系统的应用如下表5.1所示：

表5.1 人工免疫系统主要应用领域

应用领域 控制 规划 设计 组合优化 图象处理 数据处理 知识发掘 机器人 故障监测和诊断

人工免疫系统还被用于其它方面，如遥感图像特征分割、时间序列数据的异常检测、建筑材料的管理决策系统和工厂装货计划等。近两年来，人工免疫系统引起了国际上许多学者的极大兴趣，1997和1998年IEEE System，Man and

Cybernetics国际会议还组织了专题讨论人工免疫系统，掀起了智能系统中继神经网络、模糊系统和进化计算等研究之后的又一个研究热点。

§5.3 基于免疫的小生境遗传算法

5.3.1 引言

遗传算法（GA, Genetic Algorithms）是模拟自然界生物进化过程的一种随机优化方法，GA具有全局并行搜索的特点，但是早熟收敛与局部搜索能力差也是其明显的缺点。目前，针对这些缺点，人们不断地提出新的方法来改善种群的多样性，提高其全局收敛性。这一方面，小生境技术效果尤为明显。其中有：Cavicchio的基于预选择机制的小生境技术; Goldberg 和 Richardson 的基于共享机制的小生境技术; Beasley的序列小生境技术;但是，以上方法由于较大的附加计算开销而牺牲了算法的收敛速度，本文借鉴人体免疫机制，将免疫原理与小生境技术相结合，提高了小生境遗传算法的全局和局部搜索能力。 5.3.2 生物体免疫机制简介

生物体是一个复杂的大系统，其信息处理功能是由时间和空间尺寸相异的三个子系统完成的，即：脑神经系统、免疫系统和内分泌系统。免疫系统是一个由细胞、分子和器官组成的复杂系统，主要用于限制异物对肌体的侵害，并由此产生抗体，引发免疫响应。一般而言，能刺激机体免疫系统引发免疫应答而产生抗体和(或)致敏淋巴细胞，并与之产生特异性结合的物质(主要是肌体异物)被成为被称为抗原(Antigen，简称Ag)，抗体与抗原结合后，会发生一系列的反应，通过吞噬作用或者特殊酶的作用而毁坏抗原。生物的免疫细胞主要由巨噬细胞、抗体和淋巴细胞等组成，淋巴细胞又由胸腺产生的T细胞和骨髓产生的B细胞组成。根据Burnet的细胞克隆选择学说和Jerne免疫网络学说：抗原入侵机体后，在T细胞的识别和控制下，选择并刺激相应的B细胞系，使之活化、增殖并产生特异性抗体结合抗原；同时抗原与抗体、抗体与抗体之间的刺激与抑制关系形成的网络调节结构维持着免疫平衡。其抽象示意图如图5.1所示：

示 例

电压调节器的控制，复杂动力学系统自适应控制 电网规划

设计人工神经网络

TSP问题，CDMA多用户检测 图象分割，立体匹配

多组分混合色谱信号的解析 数据库知识发现

多智能体决策系统，分布式自动机器人系统等 加工工具破损监测，旋转机械在线故障诊断

图5.1 生物免疫机制调节示意图

免疫系统具有如下特征： 1) 产生多样性抗体：在免疫系统中，抗体的种类要远大于已知抗原的种类。其抗体多样性

的主要原因可能是受基因片段多样性的联接以及重链和轻链配对时等复杂机制所控制。该机理可以对应于遗传算法中个体的多样性，提高遗传算法的全局搜索能力而不陷入局部最优。 2) 免疫调节机制：免疫系统具有维持免疫的平衡的能力，其主要是通过对抗体的抑制与促

进作用，自我产生适当数量的抗体，这可对应于遗传算法中个体浓度的抑制和促进，利用此功能可以提高遗传算法的局部搜索能力。 3) 免疫记忆机制：免疫细胞中的记忆T细胞和记忆B细胞可以被保存下来，对于以后侵入的

同类抗原，可以迅速产生大量的相应抗体，该机制应用于遗传算法中，可以加快搜索的速度，提高算法的总体搜索能力。

5.3.3 免疫的小生境遗传算法 1. 免疫的小生境遗传算法介绍

根据以上免疫机理的分析，我们把免疫与小生境技术相结合，提出了免疫的小生境遗传算法。其中原来遗传算法中的个体我们称为抗体，目标函数称为抗原。该算法的主要思想是：利用免疫机制的抗体浓度调节机制，构造初始群体，增加抗体的多样性，然后利用免疫系统的记忆机制，记忆保存每代的最优个体，加速其寻优的速度。算法的基本步骤如下：

1. 产生抗原：将抗原定义为目标函数及其约束。

2. 生成初始群体：首先随机的生成初始抗体，依据其约束条件和算法要求精度，确定编码

}，i=1,2,?.,N；N长度。这里，设生成的抗体群为P={P?{Pi?{0,11,P2,......,Pn}}, 其中P为种群大小，l为编码长度。

3：抗体亲合度计算：亲合度表示抗体之间的相似程度，计算抗体和抗体之间的亲和度。抗体和抗体亲合度的度量一般采用解空间中的距离sij?||pi?pj|| i?1,2?nt，j?1,2?nt特别地，对应于二进制编码，一般采用汉明距离表示。

l

4. 抗体浓度概率计算：抗体浓度C，即群体中相似抗体所占的比重，

计算公式为：

t?C?Ni

1t(1?) ，1

1t2(1?2)。 NN?Nt5. 抗体的适应度概率计算：每个抗体的适应度概率计算公式为：Pi?fi?fi?1N，其中fi为

i每个抗体的适应度。

6. 抗体的促进与抑制：抗体的选择概率p由两部分组成，即P??Pc?(1??)pf，其中0

7. 更新记忆库：选择m个适应度高的抗体加入到记忆单元M中。去除那些适应度低于mμ以及较大浓度的记忆单元(抗体的自然死亡)。定义evenf为抗体记忆矩阵与抗原的平均适应度：

1mevenf(M)??F(pi)

mi?1因此，在种群进化过程中，记忆库的平均适应度是一个非减序列evenf(M(t+1))?evenf(M(t))

8. 小生境算法：把整个群体依适应度划分为R个小生境，对每一个小生境进行交叉、变异和(λ+μ)选择，这样就是在彼此均匀分布的小种群内部进行快速局部寻优，而小种群之间保持了多样性，之后，对整个群体进行重构小生境，并更新记忆库。

9. 结束条件：如果进化代数超过最大代数T或者在规定的代数内记忆库没有更新，则终止算法。

2. 免疫小生境遗传算法收敛性证明

定义5.1 将每一代群体中具有最优适应度值的抗体直接保留到下一代群体中的操作称为最优个体保持操作。

引理 5.1 加入最优保持操作的简单遗传算法是全局收敛的。

定理5.1 设是由免疫小生境遗传算法产生的优化搜索序列，则收敛到f(x)的全局最优值

kf(x*)。

证明 设x=maxf(x)，对于所给出的解空间S，总存在S1?S，满足度对于任意的x?S1，以此x为初值进行(μ+λ)选择寻优操作，必能找到全局最优值X，记每次免疫小生境遗传算法搜索的末值构成的序列为x1,x2,...xk,...。其中xk落入S1的事件集合为Ak?{?|xk?S1}，显然，概率测度p(Ak)可表示为：

lll**ll