人工免疫算法

人工免疫算法摘要：对免疫算法的研究现状作了介绍，并将人工免疫算法特性和应用情况进行了比较和总结，最后对算法的进一步研究方向提出了看法。关键词：免疫算法；多峰值函数1引言免疫系统是哺乳动物抵御外来病毒侵害的防御系统，动物的生命过程中会遇到各种伤害可能，免疫系统为其正常的活动起着重要的作用。免疫系统的一大特点就是用有限的资源有效地应对了数量庞大且种类多变的病毒入侵。受此特性的启发，人们设计了一种具有对多峰值函数进行多峰值搜索和全局寻优的新型算法。这种算法称为免疫算法（ImmuneAlgorithm---IA），本文给出了算法的基本原理，算法的特性、算法的应用和展望。2免疫算法的基本原理2.1多样性和亲和性免疫系统能够产生很多种抗体，但实际系统会根据抗原的种类和数目产生适量的相关抗体。这里涉及了生物的多样性和亲和性。2.1.1多样性算法中为了表明全体中的抗体的多样性，引入信息熵的概念。如图1所示N个抗体，每个抗体有M个基因，等位基因k1,k2,...,kL。图1基因的信息熵12...j...M-2M-1M抗体1k1...抗体iks...抗体NkL第j个基因的信息熵为：)log()(H1jijNiijPPN（1）式中，ijP为第i个抗体的等位基因源于第j个基因的概率。如果在位置j上所有的抗体的等位基因都相同，那么0)(HjN。系统的平均信息熵为MNHjMj)(NH1）（（2）免疫系统的多样性可用式（2）描述。2.1.2亲和性抗原和抗体之间、抗体和抗体之间的匹配程度可以用亲和性描述。抗原和抗体之间的亲和性：用于表明抗体对抗原的识别程度。亲和性vA定义如下：vOpt11Av（3）式中，vtOp表示抗原和抗体V的匹配程度。vA的值介于0和1之间，当vOpt=0时，vA=1，这说明抗体和抗原非常匹配，也就是抗体为最优的解。抗体间的亲和性：用于表明两抗体之间的相似度。)2(11A,vHw，（4）H（2）是抗体V和抗体W的信息熵。H（2）=0表明抗体V和抗体W的所有基因都相同。w,vA的值介于0和1之间。2.2免疫算法的基本步骤免疫算法由以下7个主要的步骤组成。1）抗原识别输入目标函数和各种约束作为免疫算法的抗原。2）产生初始抗体在解空间中用随机方法产生抗体。3）计算亲和性分别计算抗原和抗体V之间的亲和性及抗体V和抗体W之间的亲和性。4）记忆单元更新将与抗原亲和性高的抗体加入到记忆单元，并用新加入的抗体取代与其亲和性最高的原有抗体。5）促进和抑制抗体的产生计算抗体i的期望值iEx，期望值低的抗体将受到抑制。iiiCA/Ex（5）式中，iC是抗体i的密度（即数目）。由式（5）可知，与抗原亲和性高的抗体或低密度的抗体生存机率较大。由于高亲和性的抗体得到促进，而高密度的抗体受到抑制，所以式（5）体现了免疫控制的多样性。6）产生抗体通过变异和交叉，产生进入下一代的抗体。重复执行步骤3和步骤6，直到收敛判据满足为止。7）终止条件终止条件满足后，优化过程结束。应用免疫算法求解实际问题时，常将抗原、抗体、抗原和抗体之间的亲和性分别对应于优化问题的目标函数、优化解、解与目标函数的匹配程度。2.3免疫算法的优点2.3.1多样性免疫算法的步骤5实现了对抗体的促进和抑制，自我调节能力。步骤6通过变异和交叉产生新的抗体，体现了生物的多样性。所以免疫算法能够获得许多优化问题的最优解。2.3.2记忆训练对于以往出现过的抗原，免疫算法产生相应抗体的速度比以前更快，也就是说能非常快地收敛到最优解。这个优点使得免疫算法在求解TSP问题、函数优化、机器学习方面有较大的优势。3.免疫算法与其他算法的比较3.1性能和特点比较1）相似点都是搜索解空间的一系列点（种群）出发；处理的对象是表示待求解参数的染色体串，而不是参数本身；不需要其导数或其它附加信息。2）区别免疫算法在记忆单元基础上运行，确保了快速收敛于全局最优解；可以计算亲和性，反映了真实的免疫系统的多样性；采用基于浓度的选择机制，既鼓励适应度高的抗体，又可抑制浓度高的抗体，体现了免疫系统的自我调节功能。3.2TSP问题示例为了比较免疫算法与其他随机优化算法的性能，采用N个城市的TSP问题检测。染色体按如下方式编码：每个基因表示一个城市，每个基因的元素取[1,N]中的整数，染色体中前后两个基因表示两个城市之间有通路关系。应用深度遍历算法形成初始群体。在交叉过程中，沿两个父代环游的顺序，选择与当前访问城市距离最近但在后代环游中没有被访问的城市。在变异操作中选择两点变异，将两个变异点的整数编号进行对换，这样可以保证每个阶段所有解的可行性。将文中的方法应用于31城市的TSP问题，几种方法的计算结果见表1.表1随机优化搜索方法求解TSP问题的对比研究方法最优化结果/km10次平均结果10次中出现最优解次数平均计算时间/s模拟退火1588215900.7344进化规划1590415915.2250遗传算法1588215901.4248免疫算法1588215882.3431从上表可以看出，在求解TSP和函数优化问题时，免疫算法比遗传算法有更强收敛到全局最优的能力以及更快的收敛速度。4.人工免疫算法的改进4.1基于欧式距离的人工免疫算法标准人工免疫算法是采用信息熵的概念来描述抗体的多样性，在优化计算中，这种利用信息熵的概念计算抗体亲和性和抗体浓度的方法存在一定的问题。例如，对于由抗体u={0111111111}和抗体v={1000000000}构成的抗体群，其平均信息熵H（2）=0.6931，表明抗体u和抗体v是两个很不相同的抗体。但是在优化计算中，它们其实是两个很相近的解（通过解码后）。由此，可以看出标准的人工免疫算法具有一定的缺陷。为了防止这种缺陷的发生，提出了一种改进的基于欧氏距离求解抗体多样性的人工免疫算法。基于欧式距离的人工免疫算法的流程如图2所示。图2基于欧式距离的人工免疫算法的流程图两种算法性能比较结果如表3所示。表2两种人工免疫算法的比较算法运行次数每次搜索代数所耗时间收敛于全局最优次数基于信息熵的人工免疫算法4040020.535基于欧式距离的人工免疫算法404003.236其中，群体规模N为30。算法运行一次是指算法从最初的随机产生群体到最后得出问题的解为止，称作算法运行了一次，在此规定算法重复执行的次数为40次，而搜索代数是指在一次算法运行过程中产生新群体的代数为400代。所耗时间是算法运行40次所花费的总时间。在基于信息熵的人工免疫算法中，解抗体采用34位的二进制编码来表示，即每个自变量由17位基因组成。在基于欧氏距离的人工免疫算法中，解抗体采用10位十进制数编码来表示，即每个自变量由5位基因组成，这一方面能保证解的精度，同时也能减少算法运行时间。由表2可以看出，基于信息熵的人工免疫算法中，由于要计算每代抗体群中每个个体的问题识别产生初始抗体群并编码计算每个染色体的适应度，并以欧氏距离计算抗体浓度满足终止条件？根据适应度和浓度进行抗体选择（抑制、促进）抗体演变（交叉、变异）操作产生新抗体输出结果NY信息熵，算法的速度大大减缓，比改进了的基于欧式距离的人工免疫算法在该实例中慢了几乎6.8倍。同时，当问题中的自变量增加时，信息熵的计算将呈爆炸式增长，这样效率极大降低。4.2其他改进型的人工免疫算法现在常用的基于人工免疫算法的改进型算法还有免疫规划、免疫遗传算法和否定选择算法等。免疫遗传算法主要是利用免疫系统的多样性产生和维持机制，来保持解的多样性，克服“早熟”问题，最终求得全局最优解。免疫规划除利用免疫多样性特性之外，还引入疫苗接种机制，即利用先验知识来引导寻优过程，进一步提高算法的快速性和有效性。但是通过实例来看，“疫苗”获取是一个比较复杂的过程，并且问题的针对性很强，缺乏一般性的方法，影响这一方法的推广应用。否定选择算法是一种针对计算机安全保护问题的一种算法，应用范围基本局限于这个领域，但应用效果不错。4.3关于算法改进的想法下面谈谈对人工免疫算法进一步研究的设想。1）个体的表达：可尝试采用抗体的表现型和基因型分离的方法，通过表现型的选择来进化基因型；2）适当鼓励与最优抗体接近的抗体；3）合理设计记忆库，如记忆库中包含的问题特征和参数，以便在遇到类似问题时也可利用同一记忆库；4）重视个体评价指标的设计，充分体现抑制浓度与鼓励优良的个体相结合的算法特点，以获取更好的多峰值寻优的性能。参考文献：[1]王磊，潘进，焦李成.免疫算法[J].电子学报，2000,28(7)：74-78.[2]王磊，潘进，焦李成.免疫算法[J].计算机学报，2000,23(8)：806-812.[3]刘克胜，曹先彬，郑浩然.基于免疫进化规划的多层前馈网络设计[J].软件学报，1999,10(11)：1180-1184.[4]葛红.免疫算法综述[J].华南师范大学学报(自然科学版)，2002,3(8)：120-126.[5]施建刚，陈罡，高喆.人工免疫算法综述[J].软件导刊，2008,7(11)：68-69.[6]谢开贵，曾晓辉，李春燕，刘柏私，周家启.免疫算法与其他随机优化算法的比较分析[J].重庆大学学报，2003,26(11)：43-46.