免疫算法在最有PID控制设计器中的应用.doc

目 录第一章 绪论21.1引言21.2国内外研究现状31.2.1人工免疫算法31.2.2免疫遗传算法的应用与研究方向41.3研究动机与研究内容41.4论文安排5第一章 遗传算法概述72.1 遗传算法基本原理72.2遗传算法的构成要素72.2.1编码72.2.2适应度函数82.2.3遗传算子82.2.4 控制参数102.3 遗传算法步骤和流程112.3.1 遗传算法的应用步骤112.3.2遗传算法的基本流程112.4遗传算法的特点122.5遗传算法的早熟现象分析132.6本章小结14第三章 免疫系统与免疫遗传算法153.1生物免疫系统153.2免疫遗传算法基本原理163.3免疫遗传算法步骤和流程163.4免疫遗传算法特点173.5本章小结18第四章 免疫遗传算法的改进194.1基于信息熵的免疫遗传算法204.1.1抗体相似度和浓度计算方法204.1.2基于信息熵的免疫遗传算法的缺陷214.2基于欧式距离的免疫遗传算法214.3曼哈顿距离法224.4一种改进的免疫遗传算法234.4.1改进的遗传算法中几个重要定义234.4.2 精英保留策略254.4.3改进的免疫遗传算法254.4.4IGAE算法的全局收敛性分析264.5本章小结26第五章 基于免疫遗传算法的PID控制器设计275.1 PID控制器275.1.1 PID控制基本原理275.1.2 PID控制系统的性能指标285.2 基于免疫遗传算法的PID控制器优化设计295.2.1 免疫遗传算法的PID参数优化的基本思想295.2.2 优化问题描述和PID增益参数优化的仿真结构295.2.3 基于免疫遗传算法的PID控制器优化设计流程295.3 计算机仿真实验及结果分析305.3.1 实验对象选取和算法参数确定305.3.2 仿真结果325.4 本章小结34第六章 工作总结和展望35第一章 绪论1.1引言遗传算法（Genetic Algorithms，简称GA）模拟了自然界中生物进化的过程。在自然界中，由于受到外部条件造成的生存压力的影响，一些具有好的结构的生物就可以得到保存，而一些结构较差的生物就会被淘汰，从而生物进化向着产生最优个体的方向发展。这种优势劣汰的机制应用到了人工算法中便形成了遗传算法。遗传算法首先要做的工作是根据解空间的分布，随机产生一个具有一定数量个体的群体。群体中的每个个体都具有一定的基因型，该基因型代表了优化问题的每个解的数值。基因或者说染色体承担了携带个体基因型，表征个体独特性的任务。群体的进化过程是由群体中每一个个体完成的，每个个体经过选择、交叉、变异等遗传操作，形成新的一代具有新的基因型的个体，通过对遗传操作的合理设计，可以使新的一代具有比上一代更强的适应环境的能力。就这样，通过一代代的进化，最终群体进化成具有最强适应性的个体，也就是优化问题的最优解。遗传算法是由美国密歇根大学的John H.Holland教授在1975年创立的，从那之后，遗传算法在全世界范围内得到了广泛的应用和研究，使之成为一门日益成熟的学科。在诸如优化组合、自动控制、生产调度、机器人学、人工智能等领域，遗传算法都显现出其独特的实用价值。然而，经过大量的科学研究和实际应用之后，人们逐渐发现遗传算法也有其不足之处。这种不足主要集中在它容易早熟收敛(premature convergence)、陷入局部最优(sticks to local optimum)，而且局部搜索的能力较弱等2。根据达尔文的进化理论，生物群体能够在自然界的竞争中保存下来，其中重要的一个原因就在于较大群体的数量。只有具有一定规模的群体数量才能保证群体能偶在恶劣的环境中生存繁衍，从而保持自己群体的基因延续下去。因此，遗传算法模拟了自然界中生物群体的进化过程，为了能够使得自己的个体（解）能够存活下来，得到进化，在遗传算法的进化过程中必须满足下列四个条件3：(l)群体必须具有一定的数量的个体；(2)个体之间存在着差异，即群体具有多样性；(3)个体能够进行基因交流；(4)个体适应环境的能力不同，适应度较强的个体具有较大的繁殖机会，反之繁殖机会较小。很容易可以看出，遗传算法满足第(1)和第(3)个条件，通过设定合适的适应度函数，第(4)个条件也可以得到满足。由生物的进化原理可以知道，具有优良基因型的个体容易在进化中处于优势，从而使自己的基因型在群体中所占的比例也就越大，但是过于单一的基因型也会使得群体的适应性下降。因而为了保持群体抵抗风险的能力，需要增强群体基因型的多样性。如何把握较大比例的优良基因型以及群体多样性之间的平衡，是遗传算法亟需解决的问题之一3。经过研究发现，过于单一的群体基因型同遗传算法早熟收敛，容易陷入局部最优的问题有着密切的关系。往往在陷入局部最优之前，群体中每个个体都非常相似，不能生成有效的竞争模式。因此，如何保持群体的多样性，同时维持高适应度的个体数量，是遗传算法的关键问题之一。1.2国内外研究现状1.2.1人工免疫算法近年来，人工免疫算法的研究得到了很大的发展，国内外已经提出了许多免疫算法的理念。为了区别考察这些不同的免疫算法，对其主要从下面两个方面进行分析：(2)算法的免疫学原理；(1)数学分析量度。常用的免疫学的理论和方法主要有：进化学说、疫苗学说和反向选择理论。基于这些不同的免疫学理论和方法提出的免疫算法有以下3种：1、免疫遗传算法利用对高等脊椎动物的免疫系统的研究，Chun等将免疫原理引入了遗传算法中，从而提出了一种免疫遗传算法。通过在算法中引入抗体浓度的概念，提出抗体相似度的定义，并用信息熵来描述，表征了该抗体的基因型在群体中所占比例的大小。为了避免特定的基因型在群体中所占比例过大，因此对算法中的选择操作进行改进，适应度越高、浓度越小的抗体得到选择的概率越大，这样就保持了群体的多样性，提高了算法的全局搜索能力，避免了遗传算法陷入局部最优的问题；另一方面通过引入免疫记忆功能，提高了免疫算法收敛的速度。同遗传算法相比，免疫遗传算法的搜索能力和收敛速度都有很大的提升。2、基于疫苗的免疫算法根据疫苗在免疫系统所发挥的作用，焦李成等提出了一种基于疫苗的免疫算法。在遗传算法中算法中加入了免疫算子，经过仿真实验已经理论分析证明，该算法是收敛的而且有效的。3、反向选择算法在免疫系统中，所有的T细胞在胸腺中先要经历一个审查环节，与自身蛋白质产生免疫应答的未成熟的T细胞会被破坏掉，只有那些不与自身蛋白质组织发生免疫银弹的成熟的T细胞才能离开胸腺，由此来识别自己和非己，这就是T细胞成熟过程中所经历的反向选择过程，也就是所谓的反向选择原理。1.2.2免疫遗传算法的应用与研究方向对于免疫遗传算法的研究，国内的研究方向主要是入侵检测的免疫模型以及相关的算法的应用。国际上对“计算机免疫学”进行了广泛的研究，同时也有很多免疫遗传算法在工程上的应用，其中比较有代表性的有：1、美国新墨西哥大学的Forrest 等的研究在军方的支持下，取得了比较重大的进展，其主要的研究对象是入侵检测的免疫模型，而且其成果已经得到了应用。2、西安电子科技大学、武汉大学和中国科技大学等高校的研究小组的主要研究方向是计算机网络免疫、神经网络智能优化技术以及基于免疫原理的遗传算法等。其研究成果已经在立体匹配、TSP和机器人识别等方面得到了应用。3、浙江大学将免疫遗传算法运用于电力系统中，西北工业大学航空学院刘明辉等将改进的免疫遗传算法应用在桁架结构优化设计中。1.3研究动机与研究内容遗传算法适应度函数的设定需要同具体的问题相符合，所针对的问题不同，其适应度函数往往也不一样。因此标准遗传算法的通用性较差，很难找到一种在解决不同类型的问题时都能够提供有效的选择操作的方法。随着对高等脊椎动物免疫系统研究的深入，针对这一问题似乎提供了一种解决的可能。在生物体的免疫过程中，抗体能够针对“非己”物质做出免疫应答，常见的“非己”物质主要是外源性的细菌、病菌以及代谢异常的产物等。无论是生物体已经遇到过的，还是从未遇到过的“非己”物质，生物体都能够迅速产生相应的抗体做出应答，从而消除抗原物质。之所以免疫系统具有如此强大的识别抗原的能力，其原因就在于它很好地保持了抗体的多样性，而抗体在免疫系统中正是发挥着识别、清楚抗原的作用。针对免疫系统如何保持抗体多样性的问题，早在1957年奥地利的免疫学家N.K.Burnet便提出了细胞克隆选择学说。在他的理论当中，免疫系统在最初的胚胎期便发生了基因突变，这为后面的多样性的免疫细胞奠定了基础。不同的免疫细胞经过增殖分化，形成无性繁殖系。通过进一步的克隆繁殖，免疫细胞的多样性使机体在遇到多种不同的抗原时都能够迅速进行识别，并且产生相应的抗体消灭抗原。从信息处理的角度来看，免疫系统具有很强的自适应性、识别能力、学习能力以及鲁棒性的特点，因此，人们考虑将免疫系统的优秀特性引入遗传算法中，改善遗传算法容易早熟收敛的状况，从而形成了免疫遗传算法。同标准遗传算法相比，免疫遗传算法最大的不同之处在于算法中引入了免疫浓度调节机制，也就是模拟了自然免疫系统中抗体的繁殖策略。N.K.Jerne等人提出的免疫网络学说认为，每个抗体不仅有与抗原相结合的抗体结合部位（paratope），而且还有与别的抗体进行结合的抗体决定基（idiotope），当某种抗体的浓度过高的时候，它就会与别的与之相似的抗体进行匹配，从而使其停止增殖，进而浓度下降，系统各个抗体抗体的浓度达到平衡。同样的，在免疫遗传算法中，当某种抗体的浓度过高时，算法也会产生抑制这种抗体繁殖的操作，从而很好地调节了选择压力，保持了群体的多样性，避免了遗传算法出现早熟收敛的问题。不过免疫遗传算法也有其缺点，运算速度和收敛速度缓慢就是其中比较突出的问题。针对免疫遗传算法存在问题，本文提出了多种改进群体多样性的措施。根据不同的相应的抗体相似度定义方法，文中提出了三种不同的免疫遗传算法的改进型，包括：信息熵法（AIA），欧式距离法（DBAIA）以及曼哈顿距离法。信息熵法由于其运算速度缓慢以及抗体相似度定义存在的缺陷，故本文重点介绍了后面两种方法，这两种算法的运算速度和收敛性能都有了大幅的提高。为了进一步提高计算效率，本文设计了一种新的抗体相似度、期望繁殖率的定义方法，并结合精英策略提出了一种新的免疫遗传算法，简称IGAE。PID控制器具有良好的控制性能，应用范围极广。PID控制性能的好坏完全取决于其三个增益参数，因此本文根据免疫遗传算法具有很强的寻优能力的特点，将PID的三个增益参数视为免疫遗传算法中的抗体，即问题的解，通过设计合理的程序对抗体进行寻优，最终得到最优的增益参数，进而使PID控制器具有最优的控制性能，这就得到了IGAE-PID控制器。通过对工业中两种典型的控制对象进行仿真实验，并将结果同标准遗传算法优化的PID控制器，即GA-PID控制器的结果进行比较，可以看出IGAE-PID控制器具有很好的控制性能。1.4论文安排本论文共分为六章。第一章为绪论，引入了遗传算法，简要介绍了免疫遗传算法的国内外研究以及应用情况，同时说明了本论文的研究内容和目标。第二章介绍了遗传算法的工作原理，应用步骤及流程，分析了它的特点，并指出具有的早熟收敛的问题。第三者针对遗传算法的缺陷，引入免疫遗传算法。介绍了免疫遗传算法的工作原理和应用步骤及流程。第四章提出几种改进群体多样性的方法信息熵法、欧式距离法和曼哈顿距离法。并引入精英策略，提出了性能更好的免疫遗传算法。第五章分别将免疫遗传算法和标准遗传算法应用到PID控制器的参数优化中，并进行仿真实验，证明免疫遗传算法良好的寻优能力。第六章对本论文的工作进行总结，展望免疫遗传算法的改进。第一章 遗传算法概述2.1 遗传算法基本原理在遗传算法中，需要优化的问题的解称为个体或者染色体，一般来说，每一个个体都具有特定的基因型，基因型通过字符串的形式进行表达。若干个体的集合构成了群体，群体中的每一个个体都是在算法初始阶段随机生成的。群体的初始化完成之后，对于每一个个体，都需要按照一定的规则对其基因型进行评估，从而得到每个个体的适应度，这一评估规则就是适应度函数。适应度函数是用来考察群体中每一个个体同所需要优化的问题关联度的准则，个体的适应度越大，说明其基因型所代表的解在解空间中更加趋于优化问题的最优解。在生物进化过程中，基因型越优良的个体得到繁衍的机会也就越大，因此在遗传算法中，适应度越大的个体，在产生下一代的过程中，其被选择的概率也就越大。遗传算法产生下一代的过程是由遗传算子完成的，包括：选择算子、交叉算子和变异算子。通过设定合适的选择算子，可以实现越大的适应度个体被选中的概率越高这一目标。因此，选择算子保证了群体的下一代可以产生比上一代更优秀的个体。在个体被选中之后，接下来交叉算子开始起作用。交叉算子在每一对相互配对的个体的基因型中选定特定的位置作为交叉点，这一对个体就以此为中心使彼此的基因型相互交错，从而形成一对具有新的基因型的个体。变异算子常用于二进制编码字符串所表示的个体中，变异以一定的概率发生，一般变异概率在0.001到0.1之间。发生变异的个体，若其基因型字符串上某基因座原有值为1，则变异后的值为0；若原有值为1，则变异后的值为0。变异算子的作用是保证了解空间收敛到任一解的概率都不为零。经过遗传操作之后，群体中的个体得到了更新。因为在遗传的过程中，经过了有利于优良个体繁衍的选择操作，所以同上一代的群体相比，新一代的群体中具有较高适应度的个体所占的比例有所增加，而适应度较低的个体比例有所减少。就这样根据优胜劣汰的法则，群体通过一代代的进化，向着更优的方向发展，直到达到进化终止的条件。2.2遗传算法的构成要素2.2.1编码由于遗传算法具有较强的鲁棒性，因此它对于采用何种编码方式没有固定的要求，一般根据具体的情况来选择最合适的编码方法。本论文所研究的遗传算法和免疫遗传算法都是基于二进制编码的，因此下面主要说明二进制编码的遗传算法的操作过程。遗传算法中，优化问题的解的参数由二进制字符串来表示，若一个解有m个参数，那么这m个参数一共需要m个字符串来表示，将这些字符串连在一起，便组成了个体的基因型，它的意义类似于遗传学中的染色体。可见，编码可以让参数从实数空间映射到位串空间。在遗传算法中，遗传算子的操作包括选择、交叉、变异，经过编码之后，个体便由二进制的字符串表示，每个基因座上的数值要么为1，要么为0，因此算法可以非常方便地对个体进行操作，而且也有利于算法利用计算机进行运算。2.2.2适应度函数遗传算法利用适应度函数对个体进行评价，作为进行选择操作的依据，而不需要参照外部信息。由于遗传算法中，一个个体的适应度被定义为负值是没有意义的，故对适应度函数的唯一要求就是其计算结果必须为非负值。因此，适应度函数的定义常见于以下两种情况：1、求函数u(x)最大值时， (2.1)2、求函数g(x)最小值时， （2.2）式(2.1)中，Cmin 可以是合适的输入值，或是当前一代或前K代中的g(x) 的最小值，也可以是群体方差的函数。式(2.2)中，Cmax可以是一个合适的输入值，或是进化过程中g(x) 的最大值或当前群体中g(x) 的最大值。2.2.3遗传算子遗传操作包括三个基本遗传算子（genetic operator）：选择，交叉和变异。1、 选择算子在自然界的生物进化过程中，适应性越好的个体存活下来的几率也就越大，其基因遗传到下一代的几率也就越高；反之，适应性越差的个体，其基因遗传到下一代的几率也就越低，在群体中所占比例也就越小。遗传算法模拟了生物进化的这一过程，使用选择算子对群体进行优胜劣汰的操作。个体的适应度越高，在遗传中被选中进行复制的概率也就越大，反之越小。因此在下一代的群体中，优良个体所占的比例比上一代中更高。最常用的选择算子是比例选择算子，除此之外还有最优保存算子、排序选择算子、联赛选择算子等等。设群体规模为n，其中个体i 的适应度值为fi，则i被选择的概率Psi为: （2.3）由式（2.3）可见，个体适应度越大，其被选择的概率也就越高，反之亦然。2、 交叉算子在自然进化中，生物体通过交配进行基因重组，得到拥有新的基因型的个体。遗传算子中的交叉算子就是模拟了这个原理，将配对的两个个体按照某种方式将其基因型进行交叉，从而得到一对新的结构更为复杂的个体。通过交叉操作，群体既可以保持优良基因又能得到新个体的主要方法。最常用的交叉算子是单点交叉，除此还有一些不常用的方法，包括两点交叉、多点交叉以及一致交叉等等。本文只对前三种交叉算子进行介绍。 单点交叉（one-point crossover）单点交叉又称为简单交叉，是Holland教授提出的一种最基础的交叉方式。它是指在个体的字符串中随机选择一个点作为交叉点，然后配对的个体在这个交叉点的左右，相互交换部分染色体。位串A ：1 1 0 1| 1 0 1 0位串B ：1 0 1 1| 0 1 0 1位串A：1 1 0 1 0 1 0 1位串B：1 0 1 1 1 0 1 0 两点交叉（two-point crossover）位串A ：1 1| 0 1 1| 0 1 0位串B ：1 0| 1 1 0| 1 0 1位串A：1 1| 1 1 0| 0 1 0位串B：1 0| 0 1 1| 1 0 1 多点交叉（multi-point crossover）位串A ：1 1| 0 1| 1 0| 1 0位串B ：1 0| 1 1| 0 1| 0 1位串A：1 1| 1 1| 1 0| 0 1位串B：1 0| 0 1| 0 1| 1 0随着交叉点的数量增多，遗传算法的在线和离线被影响的概率就越大，个体好的基因型更容易被破坏，因此在工程应用中多点交叉的使用频率较少。3、变异算子变异算子的操作方法就是改变个体基因型中指定基因座上的基因值。对于二进制编码的个体来说，就是将基因座上的值取反，即从0变为1，或者从1变为0。变异操作是以一定的概率进行的。一般来说，变异概率。尽管的取值比较小，但是变异操作对于提高算法的局部搜索能力十分重要。变异算子同交叉算子相辅相成，提升了遗传算法的全局搜索能力。2.2.4 控制参数遗传算法的运行参数主要有个体编码串长度L，群体规模m，交叉概率 以及变异概率。遗传算法的性能同这些参数的选择有很大的关系。经过大量的实验研究，学者们总结出了一些对参数进行选取的方法。（1）编码串长度L：采用二进制编码时，L的大小要根据实际的问题来进行选取，所需要优化的问题对于精度的要求越高，L的取值就越大，运算的时间也就越长；优化问题对于精度的要求越低，L的取值就越小，运算时间也就越长。因此，在求解实际问题时，需要在运算效率和运算精度之间进行权衡取舍，以选取适当的L值。（2）群体规模m：群体规模是指群体所包含的个体的数量。群体中个体数量越多，其多样性就越好，算法就越不容易陷入早熟收敛，但同时需要进行适应度评价的次数也就越多，运算时间就越长，运算效率降低。一般群体规模控制在20到100之间。（3）交叉概率：交叉算子是群体中产生新个体的主要途径，因此交叉概率的值应该取较大一点，但是若值过大，会使得新旧个体更新太快，破坏群体中的许多优良的模式，因此的取值一般在0.4到0.99之间。其他的学者还提出一些具有自适应性的交叉概率，这将在第四章进行介绍。（4）变异概率：变异操作有利于群体进行更新。当的取值太大时，尽管可以产生很多新个体的，但是群体中原有的好的个体基因型会被破坏掉，使得遗传算法变得类似于随机搜索算法；当取值太小时，变异操作更新群体的能力以及抑制算法发生早熟收敛的能力就会被削弱。因此，的取值是0.0010.1。事实上，上述参数的选择要根据具体的问题类型而定，并没有一种普遍适应的参数选择方法，往往随着优化问题的复杂程度加深，参数的选择也变得更加困难。优化问题的特征不同，其有效参数的差异有时也会十分显著。因此，如何合理地选择有效参数，以提升遗传算法的性能，还需要进行进一步的研究。2.3 遗传算法步骤和流程2.3.1 遗传算法的应用步骤利用遗传算法对复杂问题进行优化的通用步骤如下：Step1：确定决策变量的解空间；Step2：确定目标函数；Step3：对可行解进行编码；Step4：确定解码方法；Step5：设计适应度函数，对个体品质进行评价；Step6：设计适当的选择、交叉、变异操作方法；Step7：选择合适的运行参数，即L、m、等参数。为了设计出合理的遗传算法，必须深刻把握优化问题的本质，选择合适的适应度函数以及遗传算子，对构造出有效的算法起着至关重要的作用。2.3.2遗传算法的基本流程遗传算法的基本流程如图2.1所示。开始解编码 计算适应度满足终止条件？终止输出结果随机产生N个初始个体YN根据适应度进行复制交叉变异 图2.1 遗传算法基本流程2.4遗传算法的特点1、遗传算法以决策变量的编码作为运算对象与传统的优化算法所不同的是，遗传算法以决策变量的编码作为操作对象，而不是决策变量的值。因此，根据实际优化问题的需要，可以灵活选择适合操作的编码方法。例如利用二进制编码，就可以使遗传算法在优化过程中很方便地使用遗传算子来模拟生物进化中染色的交叉和变异过程。特别的是对于一些很难用数值进行描述的概念，进行编码处理会有意想不到的效果。2、遗传算法同时使用多个搜索点的搜索信息在自然界中，群体的进化过程中由这个群体中每一个个体来承担完成的，个体的基因型的优化就代表着群体进化发展的过程。与之相似的，在模拟了这一过程的遗传算法中，其搜索过程是由很多个个体组成的群体开始的，并不像传统的优化算法那样，从单一的某一个点开始迭代搜索过程。对群体进行选择、交叉和变异操作，产生新一代的个体，实际上是对多个个体进行了更新，这是遗传算法特有的一种并行性，这样提升了搜索的效率。3、遗传算法使用概率搜索技术遗传算法具有很强的自适应性，在优化过程中，以分别以不用的概率进行选择、交叉、变异操作。这样做看上去似乎增加了算法的不确定性，会在群体中产生一些产生一些适应度较低的个体，但实际上它增加了搜索的灵活性，提升了算法全局搜索的能力，而且随着进化的深入，适应度较低的个体出现的概率会越来越小，逐渐被淘汰，最终留下的都是适应度很强的个体，从而算法基本上都能以1的概率收敛到问题最优解。2.5遗传算法的早熟现象分析“早熟”（Prematurity）是指在遗传算法进行的初期，群体中出现了适应度的值远远大于群体的平均适应度值的超级个体，由比例选择算子的原理可以知道，该个体被选择进行复制的概率会很大，因此该个体会在群体中迅速得到发展，占群体数量的绝大比例，而群体的多样性会因此急剧下降，因此基本失去进化的能力的现象。由上面的分析可知，遗传算法早熟收敛的特点是超级个体在群体中所占的比例过大，每个个体都具有相似的基因型，群体的多样性下降。特别是在算法的后期，用传统的交叉操作，基本上已经无法产生新的个体；而变异操作的概率又很小，对改善群体的多样性起到的效果微乎其微。由于利用遗传算子，无法形成高阶竞争模式，所以算法会很快收敛到局部最优解。具体地进行分析，导致遗传算法早熟的原因有以下几种：（1）群体规模：群体规模过小时，就算交叉概率很大，也很难产生高阶竞争模式，而且较大的交叉概率会对已有模式产生破坏。同时，群体规模过小，有效模式难以传播。（2）群体初始化：初始群体被局限在编码空间的局部区域，从而模式采样误差较大，GA无法全局搜索。（3）选择压力：选择压力是指在选择操作中，最优的个体被选中的概率同最差的个体被选中的概率之比。如果选择压力过大，则群体中的超级个体的数量会迅速提升，而较差的个体则会很快被淘汰，从而造成群体的多样性急剧下降，算法很快早熟收敛。（4）变异概率：当变异概率很小时，群体的多样性下降的趋势无法得到改善，有效基因丢失，从而算法很快收敛。通过对编码、适应度函数以及遗传算子的操作设计上进行一些改进，可以有效改善遗传算法的搜索能力，克服早熟收敛的缺陷。2.6本章小结本章主要介绍了遗传算法的基本原理，构成要素以及应用步骤和流程，同时还分析了遗传算法的主要特点和缺陷。通过本章的内容，我们可以了解到应用遗传算法求解优化问题时，应该着重注意可行解的编码方法、遗传算子的设计这两个方面，它决定了最终是否能够求出可靠的最优解。最后，针对遗传算法早熟收敛的缺陷，下一章将对这一问题提出改进。第三章 免疫系统与免疫遗传算法3.1生物免疫系统生物体内的免疫系统是保持生物免疫力，抵御外部细菌和病毒入侵的最重要的系统，其主要构成元素是淋巴细胞。淋巴细胞包括B细胞和T细胞。其中T细胞又称为抗原反应细胞，它收到抗原刺激后可以分化为淋巴母细胞，产生多种淋巴因子，引起细胞免疫反应。B细胞又称为抗体形成细胞，即可以产生抗体，主要原理是在抗原刺激下分化或增生成为浆细胞，产生特异性免疫球蛋白（抗体）。当有外来侵犯的抗原时，免疫系统就会产生相应的抗原与抗体结合并产生一系列的反应，经过吞噬细胞的作用来破坏抗原。抗体是具有专一性，而且免疫系统还具备识别能力和记忆能力，可以对相同抗原做出更快的反应。生物免疫系统的抽象模型如图3.1所示。 图3.1 生物免疫系统抽象模型 生物免疫系统可以针对各种不同的抗原都可以产生准确的抗体，这充分表现了其强大的自适应能力。如果我们将实际求解问题的目的函数与外来侵犯的抗原相对应，把问题的解与免疫系统产生的抗体相对应，就利用生物免疫系统自适应能力强的特点来进一步提高遗传算法的计算效果。免疫系统具有以下特征：（1）可以产生多种抗体；B细胞抗原刺激下分化或增生成为浆细胞，产生特异性免疫球蛋白（抗体）来抵抗抗原，这种机制可以提高遗传算法全局优化搜索能力（2）自我调节机制：免疫系统通过抑制或者促进抗体进行自我调节，因此总可以维持平衡。同样的方法可以用来抑制或者促进遗传算法的个体浓度从而提高遗传算法的局部搜索能力。（3）具有记忆功能： 当第一次抗原刺激后，免疫系统会将部分产生过相应抗体的细胞保留下来称为记忆细胞，如果同样的抗原再次刺激时便能迅速产生大量相应抗体。同样的方法可以用来加快遗传算法搜索的速度，使遗传算法反应更迅速、快捷。3.2免疫遗传算法基本原理免疫遗传算法解决了遗传算法的早熟收敛问题，这种问题一般出现在实际工程优化计算中。因为遗传算法的交叉和变异运算本身具有一定的盲目性，如果在最初的遗传算法中引入免疫的方法和概念，对遗传算法全局搜索的过程进行一定强度的干预，就可以避免很多重复无效的工作，从而提高算法效率。因为合理提取疫苗是算法的核心，为了更加稳定的提高群体适应度，算法可以针对群体进化过程中的一些推退化现象进行抑制。在生物免疫学的基础上我们发现，生物免疫系统的运行机制与遗传算法的求解是很类似的。在抵抗抗原时，相关细胞增殖分化进而产生大量抗体抵御。倘若将我们所求的目标函数及约束条件当做抗原，问题的解当做抗体，那么遗传算法求解的过程实际上就是生物免疫系统抵御抗原的过程。因为免疫系统具有辨识记忆的特点所以可以更快识别个体群体。而我们所说的基于疫苗接种的免疫遗传算法就是将遗传算法映射到生物免疫系统中，结合工程运算得到的一种更高级的优化算法。面对带求解问题时，相当于面对各种抗原，可以提前注射“疫苗”来抑制退化问题，从而更加保持优胜劣汰的特点，使算法一直优化下去，即达到免疫的目的。3.3免疫遗传算法步骤和流程免疫遗传算法流程见图3.2所示:图3.2 免疫遗传算法流程图1、抗原识别。将我们所求的目标函数及约束条件当做抗原进行识别，来判定是否曾经解决过该类问题。2、初始抗体的产生，对应遗传算法就是的到解的初始值。经过对抗原的识别，如果曾解决过此类问题，则直接寻找相应记忆细胞，从而产生初始抗。3、记忆单元更新。选择亲和度高的抗体进行存储记忆。4、抗体的抑制和促进。在免疫遗传算法中，由于亲和度高的抗体显然受到促进，传进下一代的概率更大，而亲和度低的就会受到抑制，这样很容易导致群体进化单一，导致局部优化。因此需要在算法中插入新的策略，保持群体的多样性。5、遗传操作。所谓的遗传操作，即经过交叉、变异产生下一代抗体的过程。免疫遗传算法通过考虑抗体亲和度以及群体多样性，选择抗体群体，进行交叉编译从而产生新一代抗体，保证种族向适应度高的方向进化。3.4免疫遗传算法特点免疫遗传算法具有很多普通遗传算法没有的特点包括：1、可以提高抗体的多样性：B细胞抗原刺激下分化或增生成为浆细胞，产生特异性免疫球蛋白（抗体）来抵抗抗原，这种机制可以提高遗传算法全局优化搜索能力2、可以自我调节：免疫系统通过抑制或者促进抗体进行自我调节，因此总可以维持平衡。同样的方法可以用来抑制或者促进遗传算法的个体浓度从而提高遗传算法的局部搜索能力。 3、具有记忆功能：当第一次抗原刺激后，免疫系统会将部分产生过相应抗体的细胞保留下来称为记忆细胞，如果同样的抗原再次刺激时便能迅速产生大量相应抗体。同样的方法可以用来加快遗传算法搜索的速度，使遗传算法反应更迅速、快捷。3.5本章小结本章首先介绍了生物免疫系统的机理，从生物免疫系统的抗体多样性、抗原多样性以及自适应性中得到了启发，得到了改进遗传算法早熟收敛缺陷的途径，从而提出了免疫遗传算法。最后，分析了免疫遗传算法的主要特点，大大提升了标准遗传算法的搜索性能。第四章 免疫遗传算法的改进免疫遗传算法和遗传算法的结构基本一致，最大的不同之处就在于，在免疫遗传算法中引入了浓度调节机制。进行选择操作时，遗传算法值只利用适应度值指标对个体进行评价；免疫遗传算法的选择策略变为：适应度越高，浓度越小，个体复制的概率越大；适应度越低，浓度越高的个体得到选择概率就越小。因此，免疫遗传算法可以有效地调节选择压力，具有更好的保持群体多样性的能力。在本章中，将介绍几种不同的考察抗体浓度的改进方法，但是几种改进方法的基本流程都基本一致，如图4.1所示： 图4.1 改进的免疫遗传算法流程图开始问题识别产生N个初始侯选解计算适应度、浓度根据适应度与浓度进行选择交叉变异存储局部最优解为记忆抗体满足终止条件结束YN本章将介绍几种改进群体多样性的免疫遗传算法：信息熵法、欧式距离法以及曼哈顿距离法。最后再提出一种新的抗体相似度定义，并结合精英策略提出一种新的免疫遗传算法。4.1基于信息熵的免疫遗传算法4.1.1抗体相似度和浓度计算方法抗体群的信息熵定义如图4.2所示。 图4.2抗体群信息熵的定义则抗体群在第j个基因座上的信息熵为： （4.1） 由式（4.1）可以知道，如果所有抗体在第j个基因座上的数值都相同，那么Hj(N) =0。抗体群的平均信息熵为： （4.2） 因此，抗体v ，w 之间的相似度为: （4.3）其中H(2) 是由抗体v ，w这两个抗体构成的抗体群的平均信息熵。当H(2)= 0，ayv,w= 1，这时抗体v 与w 完全相同。因此可以得到抗体相似和抗体浓度的定义。定义4-1根据式（4.3）计算出抗体v同w的相似度ayv,w。如果，则抗体v同抗体w相似；若，则抗体v同抗体w不相似。若抗体v同抗体w相似，则表征抗体是否相似的变量，否则。定义4-2抗体v的浓度为： （4.4）其中 （4.5）4.1.2基于信息熵的免疫遗传算法的缺陷该算法存在两个会对算法性能造成影响的缺陷：第一个缺陷：在一些特殊情况下，对二进制编码的个体计算平均信息熵时，定义4-1和定义4-2存在一些问题。例如，假设抗体群是由抗体v = (01111111和抗体w = (10000000组成的，则根据式（4.1）计算出的群体平均信息熵H(2)= 0.693147，亲和度ayv,w = 0.591。由计算结果看出，这两个抗体具有很大的差别，但是我们知道其实这两个抗体在实际问题的应用中，是两个很相近的解，两者应该被看做相似。第二个缺陷：涉及到抗体相似的定义。当目标函数是不连续的或者导函数的数值很大的时候，定义4-1和定义4-2中计算抗体浓度的方法在一些特殊的情况下可能会不准确。4.2基于欧式距离的免疫遗传算法郑日荣提出了一种基于欧式距离的免疫遗传算法，对其介绍如下：在n维空间中，欧氏距离的公式是: ， =1，2，n （4.6）由此得出，抗体v ，w 间的欧氏距离可以定义为: （4.7）定义4-3 在抗体群中，抗体v 和抗体w 的欧式距离记为d(v，w)；抗体v的适应度记为axv ，抗体w的适应度记为axw ，如果有下面两个式子成立： (4.8) (4.9)则称抗体w 与抗体v 相似。其中r，m为给定的常数，且有r>0，m>0。抗体v的浓度是指抗体群中满足与v 相似的条件的抗体的个数，记为cv。定义4-4 设抗体群的规模为 N，则表征群体多样性程度的指标 Idiv 定义如下： (4.10)