《人工免疫算法》PPT课件

研 究 背 景 与 现 状 ； 免 疫 进 化 算 法 ； 免 疫 神 经 网 络 ； O 在 生 物 科 学 领 域 ， 人 们 对 进 化 、 遗 传 和 免 疫 等 自 然 现 象 已 经 进 行 了 广 泛 而 深 入 的 研 究 ；O 进 化 算 法 是 建 立 在 模 仿 生 物 遗 传 与 自 然 选 择 基 础 上的 一 种 并 行 优 化 算 法 ， 其 性 能 优 异 、 应 用 广 泛 ；O 进 化 算 子 在 为 每 个 个 体 提 供 了 进 化 机 会 的 同 时 ， 也无 可 避 免 地 产 生 了 退 化 的 可 能 ；O 大 多 数 待 求 问 题 有 可 以 利 用 的 先 验 知 识 或 特 征 信 息 ，故 可 以 利 用 这 些 信 息 来 抑 制 进 化 过 程 中 的 退 化 现 象 ；O 生 物 免 疫 理 论 为 改 进 原 有 算 法 的 性 能 ， 建 立 集 进 化与 免 疫 机 制 于 一 体 的 新 型 全 局 并 行 算 法 奠 定 了 基 础 。 脑 神 经 系 统 （ 神 经 网 络 ） ； 遗 传 系 统 （ 进 化 计 算 ） ； 免 疫 系 统 （ 人 工 免 疫 系 统 ） 。 O 一 门 新 兴 的 研 究 领 域 。 Farmer等 人 在 1986年 首 先 在 工 程 领域 提 出 免 疫 概 念 ； Varela等 人 受 免 疫 网 络 学 说 的 启 发 ，提 出 并 进 而 完 善 免 疫 网 络 模 型 。 O 人 工 免 疫 网 络 模 型 独 特 型 免 疫 网 络 （ Jerne） ； 互 联 耦 合 免 疫 网 络 （ Ishiguro） ； 免 疫 反 应 网 络 （ Mitsumoto） ； 对 称 网 络 （ Hoffmann） ； 多 值 免 疫 网 络 （ Tang） . O 免 疫 学 习 算 法 反 面 选 择 算 法 （ Forrest） ； 免 疫 学 习 算 法 （ Hunt else ； i = i +1； 退 火 选 择 ： ； k = k+1；End H h j mj , , , 1 2 a V a hH ki P ki jI, , a aH ki ki, 1 a aki ki 1a aki H ki , a aki H ki ,A S Ak k 1 ( ) 具 体 分 析 待 求 问 题 ， 搜 集 特 征 信 息 。以 TSP问 题 为 例 ， 通 过 具 体 分 析 可以 得 出 相 邻 两 两 城 市 之 间 的 最 短 路 径 即为 求 解 该 问 题 时 可 以 利 用 的 一 种 疫 苗 。 TSP问 题 是 旅行 商 问 题 的 简 称 。即 一 个 商 人 从 某一 城 市 出 发 ， 要遍 历 所 有 目 标 城市 ， 其 中 每 个 城市 必 须 而 且 只 须访 问 一 次 。 所 要研 究 的 问 题 是 在所 有 可 能 的 路 径中 寻 找 一 条 路 程 最 短 的 路 线 。 该 问 题 是 一 个 典 型 的 NP问 题 ，即 随 着 规 模 的 增 加 ， 可 行 解 的 数 目 将 做 指 数 级 增 长 。 Njk kjjj ik kiik k aaaaaaD 112111 Njk kj ik kik k alallaD c 13212111设 所 有 与 城 市 Ai距 离 最 近 的 城 市 为 Aj,进 行 一 次 如 虚 线 所 示 的 调 整 后 ,多 数 情 况 下 ， l3较 aj-1 + aj的 减 少 量 要 大 于 l1 + l2较 ai的 增 加 量 。 DDPDDP cc 故 ： Begin:while (Conditions = True) 统 计 父 代 群 体 ， 确 定 最 佳 个 体 ： ; 分 解 最 佳 个 体 ， 抽 取 免 疫 基 因 ： ; 执 行 遗 传 和 免 疫 算 子 操 作 ;end a Statistics a i nkoptimal ki ( | , , )1H h a j m j k joptimal , , , , 1 2 Begin:邻 近 城 市 序 列 初 始 化 ： Neighbor(i) = random(1, n) , i =1, , n;最 短 子 路 径 的 初 始 化 ： Sub_path(i) i =1, n;while (Conditions = True) for i = 1 to n 变 异 ： Neighbor(i) = Floor(Gauss(Neighbor(i), 1 ) ) ; 选 择 ： if Distance(City_ i, Neighbor(i) Min_distance(i) then Sub_path(i) = Neighbor(i); Min_distance(i) = Distance(City_ i, Neighbor(i); end endend 0 20 40 60 800 20 40 60 80a. 免 疫 抗 体 b. 最 优 化 路 径75城 市 的 TSP问 题 免 疫 优 化 仿 真 示 意 图 0 1000 2000 3000 40000 20 40 60 80 100 当 前 最 佳 适 应 度 当 前 平 均 适 应 度 适 应 度 进 化 子 代 0 200 400 600 800 1000 20 40 60 80 100 当 前 最 佳 适 应 度 当 前 平 均 适 应 度 适 应 度 进 化 子 代a 通 用 遗 传 算 法 计 算 曲 线 b 免 疫 算 法 计 算 曲 线 0 50 100 150 200 250 3000 50 100 150 200 250 300 350 400 0 50 100 150 200 250 3000 50 100 150 200 250 300 350 400a. 免 疫 疫 苗 示 意 图 b. 最 优 路 径 示 意 图442城 市 的 TSP问 题 免 疫 优 化 仿 真 示 意 图 0 0.5 1 1.5 2 2.5 3 x 10 4 0 20 40 60 80 100 120 140 最 佳 适 应 度 曲 线平 均 适 应 度 曲 线 0 500 1000 1500 2000 2500 3000 3500 400020 40 60 80 100 120 140 最 佳 适 应 度 曲 线平 均 适 应 度 曲 线a (,2 )-ES计 算 曲 线 b ( ,2 )-IS 计 算 曲 线 f x xx( ) sin. . 10 1016 012 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10 2 4 6 8 10 12 14 16 18 20问 题 : 在 (0,1)内 寻 找 xmax使 下 式 成 立 :f x f x x( ) ( ), ( , ) max 0 1 0 50 100 0 0.5 1 0 50 100 14 16 18 20 0 50 100 0 5 10 15 20 0 50 100 0 0.5 1 (a) (b) (c) (d) (a) 基 于 EP的 进 化 过 程中 个 体 分 布 图 ;(b) 基 于 IP的 进 化 过 程中 个 体 分 布 图(c) EP和 IP所 求 得 的最 佳 适 应 度 对 比 图(d) EP和 IP所 求 得 的 平均 适 应 度 对 比 图 xk1 5 0 50 100 0 0.5 1 0 50 100 14 16 18 20 0 50 100 0 5 10 15 20 0 50 100 0 0.5 1 (a) (b) (c) (d) (a) 基 于 EP的 进 化 过 程中 个 体 分 布 图 ;(b) 基 于 IP的 进 化 过 程中 个 体 分 布 图(c) EP和 IP所 求 得 的最 佳 适 应 度 对 比 图(d) EP和 IP所 求 得 的 平均 适 应 度 对 比 图