人工免疫算法.pdf

《人工免疫算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、人工免疫算法摘要：对免疫算法的研究现状作了介绍，并将人工免疫算法特性和应用情况进行了比较和总结，最后对算法的进一步研究方向提出了看法。关键词：免疫算法；多峰值函数1引言免疫系统是哺乳动物抵御外来病毒侵害的防御系统，动物的生命过程中会遇到各种伤害可能，免疫系统为其正常的活动起着重要的作用。免疫系统的一大特点就是用有限的资源有效地应对了数量庞大且种类多变的病毒入侵。受此特性的启发，人们设计了一种具有对多峰值函数进行多峰值搜索和全局寻优的新型算法。这种算法称为免疫算法（ImmuneAlgorithm---IA），本文给出了算法的基本原理，算法的特性、算法

2、的应用和展望。2免疫算法的基本原理2.1多样性和亲和性免疫系统能够产生很多种抗体，但实际系统会根据抗原的种类和数目产生适量的相关抗体。这里涉及了生物的多样性和亲和性。2.1.1多样性算法中为了表明全体中的抗体的多样性，引入信息熵的概念。如图1所示N个抗体，每个抗体有M个基因，等位基因k1,k2,...,kL。12...j...M-2M-1M抗体1k1...抗体iks...抗体NkL图1基因的信息熵第j个基因的信息熵为：NHj(N)(PijlogPij)（1）i1式中，P为第i个抗体的等位基因源于第j个基因的概率。ij如果在位置j上所有的抗体

3、的等位基因都相同，那么H(N)0。jMH(N)j系统的平均信息熵为H（N）（2）j1M免疫系统的多样性可用式（2）描述。2.1.2亲和性抗原和抗体之间、抗体和抗体之间的匹配程度可以用亲和性描述。抗原和抗体之间的亲和性：用于表明抗体对抗原的识别程度。亲和性A定义如下：v1A（3）v1Optv式中，Opt表示抗原和抗体V的匹配程度。vA的值介于0和1之间，当Opt=0时，A=1，这说明抗体和抗原非常匹配，也就vvv是抗体为最优的解。抗体间的亲和性：用于表明两抗体之间的相似度。1A，（4）v,w1H(2)H（2）是抗体V和抗体W的信息熵。

4、H（2）=0表明抗体V和抗体W的所有基因都相同。A的值介于0和1之间。v,w2.2免疫算法的基本步骤免疫算法由以下7个主要的步骤组成。1）抗原识别输入目标函数和各种约束作为免疫算法的抗原。2）产生初始抗体在解空间中用随机方法产生抗体。3）计算亲和性分别计算抗原和抗体V之间的亲和性及抗体V和抗体W之间的亲和性。4）记忆单元更新将与抗原亲和性高的抗体加入到记忆单元，并用新加入的抗体取代与其亲和性最高的原有抗体。5）促进和抑制抗体的产生计算抗体i的期望值Ex，期望值低的抗体将受到抑制。iExA/C（5）iii式中，C是抗体i的密度（即数目）。i由式（5

5、）可知，与抗原亲和性高的抗体或低密度的抗体生存机率较大。由于高亲和性的抗体得到促进，而高密度的抗体受到抑制，所以式（5）体现了免疫控制的多样性。6）产生抗体通过变异和交叉，产生进入下一代的抗体。重复执行步骤3和步骤6，直到收敛判据满足为止。7）终止条件终止条件满足后，优化过程结束。应用免疫算法求解实际问题时，常将抗原、抗体、抗原和抗体之间的亲和性分别对应于优化问题的目标函数、优化解、解与目标函数的匹配程度。2.3免疫算法的优点2.3.1多样性免疫算法的步骤5实现了对抗体的促进和抑制，自我调节能力。步骤6通过变异和交叉产生新的抗体，体现了生物的多样性

6、。所以免疫算法能够获得许多优化问题的最优解。2.3.2记忆训练对于以往出现过的抗原，免疫算法产生相应抗体的速度比以前更快，也就是说能非常快地收敛到最优解。这个优点使得免疫算法在求解TSP问题、函数优化、机器学习方面有较大的优势。3.免疫算法与其他算法的比较3.1性能和特点比较1）相似点都是搜索解空间的一系列点（种群）出发；处理的对象是表示待求解参数的染色体串，而不是参数本身；不需要其导数或其它附加信息。2）区别免疫算法在记忆单元基础上运行，确保了快速收敛于全局最优解；可以计算亲和性，反映了真实的免疫系统的多样性；采用基于浓度的选择机制，既鼓励适应度

7、高的抗体，又可抑制浓度高的抗体，体现了免疫系统的自我调节功能。3.2TSP问题示例为了比较免疫算法与其他随机优化算法的性能，采用N个城市的TSP问题检测。染色体按如下方式编码：每个基因表示一个城市，每个基因的元素取[1,N]中的整数，染色体中前后两个基因表示两个城市之间有通路关系。应用深度遍历算法形成初始群体。在交叉过程中，沿两个父代环游的顺序，选择与当前访问城市距离最近但在后代环游中没有被访问的城市。在变异操作中选择两点变异，将两个变异点的整数编号进行对换，这样可以保证每个阶段所有解的可行性。将文中的方法应用于31城市的TSP问题，几种方法的计算

8、结果见表1.表1随机优化搜索方法求解TSP问题的对比研究方法最优化结果/km10次平均结果10次中出现最平均计算时间/s优