医学ppt课件免疫算法

免疫算法 组长:朱海军 成员:王智超 王炜华 雒 玲 刘 豹 免疫算法的生物学基础 免疫系统是哺乳动物抵御外来有害物质侵害的 防御系统，动物一生始终处于复杂多变的、充 满伤害的自然环境中，能够平安无事、进行正 常的生命活动，免疫系统在其中起着重要的作 用。免疫是生物体的特异性生理反应, 由具有免 疫功能的器官、组织、细胞、免疫效应分子及 基因等组成。 免疫系统通过分布在全身的不同 种类的淋巴细胞识别和清除侵入生物体的抗原 性异物。 当生物系统受到外界病毒侵害时, 便 激活自身的免疫系统,其目标是尽可能保证整个 生物系统的基本生理功能得到正常运转。 免疫算法的起源 在生物自然界中，免疫现象普遍存在，并对物种的生 存与繁衍 发挥着重要的作用； 生物的免疫功能主要是由参与免疫反应的细胞或由其 构成的器官来完成的； 生物免疫主要有两种类型： 特异性免疫反应（Specific Immunity） 非特异性免疫反应（Nonspecific Immunity）； 生物免疫系统是通过自我识别、相互刺激与制约而构 成了一个 动态平衡的网络结构 。 免疫算法的生物免疫机制 免疫算法的基本概念(1) 抗原：在生命科学中，是指能够刺激和诱导机 体的免疫系统使其产生免疫应答，并能与相应 的免疫应答产物在体内或体外发生特异性反应 的物质。在我们的算法中，是指所有可能错误 的基因，即非最佳个体的基因。 抗体：在生命科学中，是指免疫系统受抗原刺 激后，免疫细胞转化为浆细胞并产生能与抗原 发生特异性结合的免疫球蛋白，该免疫球蛋白 即为抗体。 免疫算法的基本概念(2) 免疫疫苗：根据进化环境或待求问题的先验知识 ，所得到的对最佳个体基因的估计。 免疫调节：在免疫反应过程中，大量的抗体的产 生降低了抗原对免疫细胞的刺激，从而抑制抗 体的分化和增殖，同时产生的抗体之间也存在 着相互刺激和抑制的关系，这种抗原与抗体、 抗体与抗体之间的相互制约关系使抗体免疫反 应维持一定的强度，保证机体的免疫平衡。 免疫算法的基本概念(2) 免疫记忆：指免疫系统将能与抗原发生反应的抗 体作为记忆细胞保存记忆下来，当同类抗原再 次侵入时，相应的记忆细胞被激活而产生大量 的抗体，缩短免疫反应时间。 抗原识别：通过表达在抗原表面的表位和抗体分 子表面的对位的化学基进行相互匹配选择完成 识别，这种匹配过程也是一个不断对抗原学习 的过程，最终能选择产生最适当的抗体与抗原 结合而排除抗原。 免疫算法的流程 免疫算法具体步骤(1) (1) 产生初始群体： 对初次应答，初始抗体随机产生;而对再次应答， 则借助免疫机制的记忆功能，部分初始抗体由记 忆单元获取。由于记忆单元中抗体具有较高的适 应度和较好的解群分布，因此可提高收敛速度。 (2) 根据先验知识抽取疫苗 免疫算法具体步骤(2) (3) 计算抗体适应度 (4) 收敛判断 若当前种群中包含了最佳个体或达到最大 进化代数，则结束算法;否则进行以下步骤 。 免疫算法具体步骤(3) (5) 产生新抗体 每一代新抗体主要通过两条途径产生： (a) 基于遗传操作生成新抗体:采用赌轮盘选择机制，当 群体相似度小于阂值A0时，多样性满足要求，则抗体 被选中的概率正比于适应度;反之，按下述(b)的方式产 生新抗体，交叉和变异操作均采用单点方式。 (b) 随机产生P个新抗体：为保证抗体多样性，模仿免 疫系统细胞的新陈代谢功能，随机产生P个新抗体，使 抗体总数为N+P，再根据群体更新，产生规模为N的下 一代群体。 免疫算法具体步骤(4) (6) 群体更新： 对种群进行接种疫苗和免疫选择操作，得 到新一代规模为N的父代种群，返回步骤3 免疫算法具体步骤之-免疫算子 免疫算子有两种类型： 全免疫 非特异性免疫 目标免疫 特异性免疫 即：群体中的每个个体在进化算子作用后，对其 每一环节都进行一次免疫操作的免疫类型； 即：在进行了进化操作后，经过一定的判断，个 体仅在作用点处发生免疫反应的一种类型。 TSP问题的描述 TSP问题描述 TSP问题是旅行商问题的简称。即一个 商人从某一城市出发，要遍历所有目标 城市，其中每个城市必须而且只须访问 一次。所要研究的问题是在所有可能的 路径中寻找一条路程最短的路线。该问 题是一个典型的NP问题，即随着规模的 增加，可行解的数目将呈指数级增长。 免疫算法求解TSP流程图 具体过程(1) (1) 个体编码和适应度函数 a.算法实现中，将TSP问题的目标函数对应于抗原，问 题的解对应于抗体。 b.抗体采用以遍历城市的次序排列进行编码，每一抗体 码串形如:V1，V2，Vn，其中，Vi表示遍历城市的 序号。适应度函数取路径长度Td倒数： 表示第i个抗体所表示的遍 历路径长度 具体过程(2) (2)交叉与变异算子 采用单点交叉，其中交叉点的位置随机确定。 算法中加入了对遗传个体基因型特征的继承性 和对进一步优化所需个体特征的多样性进行评 测的环节，在此基础上设计了一种部分路径变 异法。该方法每次选取全长路径的一段，路径 子段的起点与终点由评测的结果估算确定。具 体操作为采用连续n次的调换方式，其中n的大 小由遗传代数K决定。 具体过程(3) (3)免疫算子 由前面可知免疫算子包括全免疫和目标免疫两种。对于TSP 问题，要找到适用于整个抗原(即全局问题求解)的疫苗极为 困难，所以我们采用目标免疫。具体而言，在求解问题之前 先从每个城市点的周围各点中选取一个路径最近的点，以此 作为算法执行过程中对该城市点进行目标免疫操作时所注入 的疫苗。每次遗传操作后，随机抽取一些个体注射疫苗，然 后进行免疫检测，即对接种了疫苗的个体进行检测：若适应 度提高，则继续；反之，若其适应度仍