第14讲--计算机地质学---免疫遗传算法与地质应用

1、西安科技大学薛喜成 计算机地质学主要内容14.1 免疫遗传算法概述14.2 免疫遗传算法基本原理14.3 免疫遗传算法的算法设计14.4 免疫遗传算法地质应用14.1 免疫遗传算法概述 传统的BP神经网络，隐层结构至今没有一个完整的理论、公式确定，而BP神经网络的核心就在于隐层、隐单元数目及其连接权。其中隐单元不仅对建立的神经网络模型的性能影响很大，而且是训练时出现“过拟合”的直接原因，若隐单元数太少，网络可能根本不能训练或网络性能很差；若隐单元数太多，虽然可使网络的系统误差减小，但一方面使网络训练时间延长，另一方面，训练容易陷入局部极小点而得不到最优点，也是训练时出现“过拟合”的内在原因。

2、通常情况下BP神经网络的泛化能力随着网路的学习能力提高而提高，而过拟合是指随着学习能力的提高，网络的泛化能力反而下降的现象。通常隐单元采用修剪法或增长法来确定，采用这种方法常出现网络泛化能力差、收敛速度慢、易陷入局部极小，导致预测结果的误差增加。遗传算法较以往传统的搜索算法具有使用方便，鲁棒性强、便于并行处理等优点，因而广泛应用于组合算法、结构设计、人工智能等领域。 动物三大支柱系统中的神经网络系统、遗传进化系统已被人们广泛研究，这里还将引入第三大系统免疫系统，基于免疫原理的遗传算法可有效地改善遗传算法的未成熟收敛缺陷，提高遗传算法的全局和局部搜索能力。 名词 鲁棒性：鲁棒性（robustne

3、ss）就是系统的健壮性。它是在异常和危险情况下系统生存的关键。比如说，计算机软件在输入错误、磁盘故障、网络过载或有意攻击情况下，能否不死机、不崩溃，就是该软件的鲁棒性。所谓“鲁棒性”，是指控制系统在一定（结构，大小）的参数摄动下，维持某些性能的特性。根据对性能的不同定义，可分为稳定鲁棒性和性能鲁棒性。14.2 免疫遗传算法基本原理 （1）免疫遗传算法概述 基本遗传算法（Simple Genetic Algorithm，简称SGA）是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法，它是美国密执根大学的霍勒德（J.H.Holland）于1975年首先提出来的。遗传算法具有简单通用、鲁棒性强、

4、全局并发搜索等特点。它是一种全局化搜索算法，尤其适用于传统搜索算法难于解决的复杂和非线性问题。在理论上已经形成了一套较为完善的算法体系，然而在实际使用中，还有许多问题有待于进一步研究探讨。例如，对于单调函数或单峰函数，在初始时很快向最优值逼近，但是在最优值附近收敛较慢； 而对于多峰函数的优化问题，它往往会出现“早熟”，即收敛于局部极值。为此，人们正对基本遗传算法（SGA）作不断的改进和提高，生物体的免疫系统具有很强的自适应性，而实际问题的求解过程与生物免疫机制十分类似。基于免疫原理的遗传算法（Immunity Genetic Algorithm，简称IGA）就是一种对传统遗传算法的改进。通过对

5、TSP问题（又称商旅问题）求解的实验表明，基于免疫原理的遗传算法可有效改善未成熟收敛缺陷，提高遗传算法的全局和局部搜索能力。 （2）免疫遗传算法基本原理 免疫算法将实际求解问题的目标函数对应为抗原，而问题的解对应为抗体。由生物免疫原理可知，生物免疫系统对入侵生命体的抗原通过细胞的分裂和分化作用，自动产生相应的抗体来抵御，这一过程被称为免疫应答。在免疫应答过程中，部分抗体作为记忆细胞保存下来，当同类抗原再次侵入时，记忆细胞被激活并迅速产生大量抗体，使再次应答比初次应答更快更强烈，体现了免疫系统的记忆功能。抗体与抗原结合后，会通过一系列的反应而破坏抗原。同时，抗体与抗体之间也相互促进和抑制，以维持

6、抗体的多样性及免疫平衡，这种平衡是根据浓度机制进行的，即抗体的浓度越高，则越受抑制；浓度越低，则越受促进，体现了免疫系统的自我调节功能。 与生物免疫系统的功能相对应，基于免疫原理的遗传算法与标准遗传算法相比，具有如下显著特点：具有免疫记忆功能，该功能可以加快搜索速度，提高遗传算法的总体搜索能力；具有抗体的多样性保持功能，利用该功能可以提高遗传算法的局部搜索能力；具有自我调节功能，这种功能可用于提高遗传算法的全局搜索能力，避免陷入局部解。总之，免疫遗传算法既保留了遗传算法随机全局并行搜索的特点，又在相当大程度上避免未成熟收敛，确保快速收敛于全局最优解。14.3 免疫遗传算法的算法设计14.3.1

7、 免疫算子 免疫算子的设计思想：引入信息熵来判断抗体的多样性，即等位基因概率的变化过程。设免疫系统有N个抗体组成，每个抗体有M位基因。每个抗体的每位可供选择的字母表中共有s个字母：k1，k2，ks。其结构下图所示： 我们将抗原定义为BP神经网络的隐层结构，则此时的抗体为最优的隐层结构。为了从抗体群中找出适应度较优的抗体，并产生新的抗体群，须比较抗体与抗体之间、抗体与抗原的亲和力。 抗体间的亲和力：用于表明两抗体之间的相似度。任意两个抗体v和抗体w间的亲和力为： 上式中的H(2)为任意两个抗体v和抗体w的平均信息熵。H(2)可以通过下式计算获得。 抗原与抗体的亲和力：用于表明抗体对抗原的识别程度

8、，把它定义为该抗体的适应度。抗体v和抗原v的亲和力为： 其中表示抗原和抗体之间的适应度，其计算公式为： 计算上式中的网络总误差E时，先从种群中取一条染色体，恢复成相应的BP神经网络，将训练样本带入网络中进行迭代，并由下式计算出网络的总误差E，由上式计算出f1： 上式中Ti(x)和Oi(x)分别为第x个训练样本的第i个输出节点的期望输出和实际输出。M，N分别为训练样本总数和输出节点总数。 的适应度值越大，则表示该网络性能越好；适应度值越小，则表示该网络的性能越差。 通过上式可以看出，抗体适应度越大，则复制选择概率越大；抗体的浓度越高，则复制选择概率越小。 通过免疫算子既保留了遗传算法的全局搜索能

9、力，又有效地保持抗体的多样性，避免了未成熟收敛现象。 名词信息熵：1948年香农（Claude Elwood Shannon）长达数十页的论文“通信的数学理论”成了信息论正式诞生的里程碑。在他的通信数学模型中，清楚地提出信息的度量问题，他把哈特利的公式扩大到概率pi不同的情况，得到了著名的计算信息熵H的公式：H=-pi log pi。 名词抗体：早在一个世纪以前，就有人发现机体受外来抗原物质刺激后，能产生一种与该抗原发生特异性结合的物质，称为抗体。抗原是能使机体产生一系列免疫反应的物质，如细菌、病毒或其代谢产物。抗体有抵抗传染病的能力，是抗原进入人体后，刺激机体产生的一种与该抗原相结合的特异性

10、物质，如免疫球蛋白。14.3.2 染色体编码设计 传统遗传算法的染色体是单层的，当染色体编码较长时，染色体中短基因组的实际交叉、变异概率过小，容易导致抗体群缺乏多样性。其表现为：抗体群中个体的短基因组的相似性大，算法收敛速度慢。可以采用三层结构的染色体来设计BP神经网络的优化方案，其具体结构如下图所示： 第一层是隐层结构基因组，用二进制编码，用于表示BP神经网络中隐层的数目，此层的编码总长度表示网络隐层的最大值；编码上的某一位为1时表示该隐层激活，为0时表示该隐层未被激活，其下层的基因组也未被激活。上图中此层的编码为“1010”表示有2个隐层。 第二层是神经元基因组，采用二进制编码，表示某隐层

11、下的神经元个数，其中一个位表示一个神经元，此位上的值为0时，表示此神经元处于休眠状态，其下层的基因组也处于休眠状态；为1表示此神经元处于激活状态，并能产生有效输出，其下层基因组也处于工作状态。上图中此层上的编码“1110”表示第1个隐层上有3个神经元。 第三层基因组采用十进制编码，表示上层神经元的所有阀值、权值。每一位代表一个权值（从左到右分别为该神经元的阈值、连接权值）。此层最后的W0基因片段为输出层的阀值及连接权值，这些权值的个数与当前染色体中最后隐层中激活的神经元个数有关，如果最后隐层中有n个激活的神经元，则输出层每个神经元必有1个阀值和n个权值。14.3.3 遗传操作 首先接受一个抗原

12、（对应特定问题），然后随机产生一组初始抗体（对应候选解）；接着计算每一代抗体的适应度，对抗体进行交叉和变异；再通过基于抗体浓度和亲和力的群体更新策略生成下一代抗体群；直到满足终止条件，算法结束。将结果代入BP神经网络中，进行网络训练、评估。具体过程如下图。 算法中的遗传操作主要有： （1）选择 淘汰适应度差的个体，选择适应度高的个体，按照“适者生存”的原则对个体进行复制。有时可采用“轮盘赌（Roulette Wheel）”的方法实现选择。其基本思想是：如下图所示，各个个体被选中的几率与其选择概率pv大小成正比，选择概率pv大的个体被选中的几率就越大；反之，选择概率pv越低的个体被选中的几率就越

13、小。 其具体执行过程是：首先，计算出每个个体的选择概率pv（各个个体选择概率之和等于1），然后使用模拟赌盘操作，即随机生成一个（0，1）之间的浮点数，表示赌盘指针的位置，由此来判断某个个体是否被选中。 （2）交叉 交叉是把两个父个体的部分结构加以替换重组而生成新个体的操作，它的目的是为了能够在下一代产生新的个体。实践中常用到两点交叉。 两点交叉（Two-point Crossover）是指在个体编码串中随机设置了两个交叉点，然后再进行部分基因交换。 其具体操作过程是：首先，在相互配对的两个个体编码串中随机设置两个交叉点。然后，交换两个个体在所设定的两个交叉点之间的部分染色体。如下图所示。 （3

14、）变异 对于编码中的任一位，以一定的概率进行变异。对染色体中第1、2层的二进制编码，变异操作只是简单地将基因取反，即将“1”变为“0”，将“0”变为“1”；对于第3层上的十进制的编码，则根据变异几率将某一位或某几位用 -0.5，0.5上的随机实数替换原来的十进制数。 （4）终止条件 终止条件根据具体的情况有很多种方法，较为常用的方法是将迭代次数作为终止条件，当达到某一预先设定的迭代次数后终止。采用判断个体的平均浓度趋于稳定作为终止条件也是将为常见的方法。通常多以最大迭代次数作为终止条件，即当网络达到最大迭代次数后停止迭代，同时将搜索到适应度最大的个体作为对BP神经网络优化的结果。 名词轮盘赌：俄罗斯轮盘赌（Russian roulette）是一种残忍的赌博游戏。与其他使用扑克、色子等赌具的赌博不同的是，俄罗斯轮盘赌的赌具是左轮手枪和人的性命。俄罗斯轮盘赌的规则很简单：在左轮手枪的六个弹槽中放入一颗或多颗子弹，任意旋转转轮之后，关上转轮。游戏的参加者轮流把手枪对着自己的头，扣动板机；中枪的当然是自动退出，怯场的也为输，坚持到最后的就是胜者。旁观的赌博者，则对参加者的性命压赌注。 据说，这种赌博始于第一次世界大战，战败的沙俄士兵在军营里借酒浇愁，用这种游戏助兴。于是这种赌博方式，就被称为“俄罗