《幾種智能算法概述及其應用》由會員分享，可在線閱讀，更多相關《幾種智能算法概述及其應用（20頁珍藏版）》請在裝配圖網上搜索。

1、幾種智能算法概述及其應用 匯報內容幾種智能算法概述1. 遺傳算法 2. 粒子群算法3. 模擬退火算法 4. 蟻群算法 智能算法概述1、遺傳算法遺 傳 算 法 （ GeneticAlgorithm， GA） 是 一 種 進 化 算 法 ， 其 基 本原 理 是 仿 效 生 物 界 中 的 “ 物 競 天 擇 、 適 者 生 存 ” 的 演 化 法 則 。 遺 傳算 法 的 做 法 是 把 問 題 參 數(shù) 編 碼 為 染 色 體 ，再 利 用 迭 代 的 方 式 進 行 選 擇 、 交 叉 以 及變 異 等 運 算 來 交 換 種 群 中 染 色 體 的 信 息 ，最 終 生 成 符 合 優(yōu) 化

2、目 標 的 染 色 體 。 智能算法概述染 色 體 ： 生 物 遺 傳 物 質 主 要 載 體 ?；?因 ： 擴 展 生 物 性 狀 的 遺 傳 物 質的 功 能 單 元 和 結 構 單 位 ?；?因 座 ： 染 色 體 中 基 因 的 位 置 。等 位 基 因 ： 基 因 所 取 的 值 。 生 物 遺 傳 概 念 遺 產 算 法 中 的 應 用適 者 生 存 目 標 值 比 較 大 的 解 被 選 擇 的 可 能 性 大個 體 可 能 解染 色 體 解 的 編 碼 （ 字 符 串 、 向 量 等 ）基 因 解 中 每 一 分 量 的 特 征適 應 性 適 應 函 數(shù) 值群 體 根 據 適

3、應 函 數(shù) 值 選 定 的 一 組 解 （ 解 的 個 數(shù) 為 群 體 的 規(guī) 模 ）婚 配 交 叉 選 擇 兩 個 染 色 體 進 行 交 叉 產 生 一 組 新 的 染色 體 的 過 程變 異 編 碼 的 某 一 分 量 發(fā) 生 變 化 的 過 程1、遺傳算法 智能算法概述遺 傳 算 法 流 程遺 傳 算 法 改 進 方 向 1、 遺 傳 算 法 與 非 線 性 規(guī) 劃 結 合 2、 與 BP神 經 網 絡 結 合 3、 基 于 量 子 遺 傳 算法 尋 優(yōu) 4、 多 種 群 遺 傳 算 法 5、 多 層 編 碼 遺 傳 算 法1、遺傳算法 智能算法概述TSP（ 旅 行 商 問 題 ） 問

4、題 描 述 與 結 果 ：已 知 n個 城 市 互 相 之間 距 離 ， 某 人 從 某 城 市出 發(fā) 訪 問 每 個 城 市 且 僅一 次 ， 如 何 安 排 才 能 使其 所 走 路 線 最 短1、遺傳算法 智能算法概述制 孔 路 徑 優(yōu) 化在 飛 機 裝 配 線 上 用 機 器人 帶 動 末 端 執(zhí) 行 器 進 行 制孔 ， 執(zhí) 行 器 由 初 始 位 置 依次 移 動 到 每 一 孔 位 ， 最 后返 回 初 始 位 置 ， 目 標 為 所走 路 徑 最 短 ， 時 間 最 少 產 品 生 產 安 排一 個 周 期 內 生 產 n種產 品 ， 開 銷 包 括 制 造 成本 以 及 產

5、品 轉 換 開 支 ，因 此 生 產 成 本 與 生 產 順序 有 關 ， 目 標 為 使 轉 換成 本 最 低1、遺傳算法 智能算法概述2、粒子群算法產生背景粒 子 群 算 法 （ Particle Swarm Optimization， PSO） 源 于對 鳥 類 捕 食 行 為 的 研 究 ， 一 群 鳥 隨 機 分 布 在 一 個 區(qū) 域 中 ， 在 這片 區(qū) 域 只 有 一 塊 食 物 ， 鳥 類 捕 食 時 ， 所 有 鳥 都 不 知 道 食 物 在 哪里 ， 但 是 他 們 知 道 當 前 位 置 距 離 食 物還 有 多 遠 ， 那 么 找 到 食 物 最 簡 單 有 效的 策

6、 略 就 是 搜 尋 當 前 距 離 食 物 最 近 的鳥 的 周 圍 區(qū) 域 。 智能算法概述2、粒子群算法基本思想每 個 潛 在 解 都 是 搜 索 空 間 的 一 只 鳥 ， 稱 之 為 “ 粒 子 ” ， 所 有 粒 子都 有 一 個 由 被 優(yōu) 化 函 數(shù) 決 定 的 適 應 值 ， 還 有 一 個 速 度 決 定 其 飛 行 方向 及 距 離 。 粒 子 們 追 隨 當 前 最 優(yōu) 粒 子 在 解 空 間 搜 索 ， 然 后 通 過 迭 代找 到 最 優(yōu) 解 。 在 每 一 次 的 迭 代 中 ， 粒 子 根 據 兩 個 極 值 來 更 新 自 己 ： 粒 子 本 身 變 化 過

7、程 中 的 最 優(yōu) 解 ， 稱 為 個 體 極 值 整 個 種 群 目 前 找 到 的 最 優(yōu) 解 ， 稱 為 全 局 極 值有 時 為 了 避 免 陷 入 局 部 最 優(yōu) ， 可 使 用 整 體 中 一 部 分 作 為 粒 子 鄰 居 ，則 所 有 鄰 居 中 的 極 值 就 是 局 部 極 值 。 智能算法概述2、粒子群算法基本模型設 群 體 規(guī) 模 為 N， 目 標 搜 索 空 間 為 D維 。 1 1, , , Ti i i iDX v v v 1,2, ,i i N 1 1, , , Ti i i iDV v v v1,2, ,i N 1 1, , , Ti i i iDP p p

8、p表 示 第 個 粒 子 的 位 置 。表 示 i的 飛 翔 速 度表 示 i自 身 搜 索 到 的 最 優(yōu) 點 1 1 1 2 21 1k k k k k kid id d id id d gd idk k kid id idv v c r p x c r p xx x v 智能算法概述2、粒子群算法基本模型 學 習 因 子 c1：c1=0， 則 只 有 社 會 ，沒 有 自 我學 習 因 子 c2：c2=0， 則 只 有 自 我 ，沒 有 社 會 智能算法概述2、粒子群算法改進加入慣性權重由 基 本 粒 子 群 算 法 模 型中 粒 子 位 置 進 化 方 程 可 看出 ， 不 同 時 刻

9、 位 置 由 飛 行速 度 決 定 ， 因 此 飛 行 速 度大 小 直 接 影 響 算 法 的 全 局收 斂 性 。 慣 性 權 重 分 類 ：1. 固 定 權 重 ， 種 群 規(guī) 模越 大 ， 所 需 權 重 越 小2. 時 變 權 重3. 隨 機 權 重 智能算法概述3、模擬退火算法背景退 火 是 指 將 固 體 加 熱 到 足 夠 高 的 溫 度 ， 使 分 子 呈 現(xiàn) 隨 機排 列 狀 態(tài) ， 然 后 逐 步 降 溫 使 之 冷 卻 ， 最 后 分 子 以 低 能 狀 態(tài) 排列 ， 固 體 達 到 某 種 穩(wěn) 定 狀 態(tài) 。 該 過程 屬 于 熱 力 學 范 疇 ， 主 要 由 三

10、部 分組 成 ： 加 溫 過 程 、 等 溫 過 程 以 及 冷卻 過 程 。 智能算法概述3、模擬退火算法由 統(tǒng) 計 力 學 研 究 表 明 ， 在 溫 度 T， 分 子 滯 留 在 狀 態(tài) r的 概 率滿 足 波 茲 曼 概 率 分 布其 中 ， 為 狀 態(tài) r的 能 量 ， 為 概 率 分 布 的 標 準 化 因 子當 時即 分 子 停 留 在 能 量 小 的 狀 態(tài) 概 率 大 1 2E E 1 2 11 2 BB E -E- = 1-exp - k TE1P E=E P E=E exp -Z T k T 智能算法概述3、模擬退火算法流程 初 始 化 ： 初 始 溫 度 T（ 充 分

11、大 ） ， 初 始 解 狀 態(tài) S（ 算 法 迭 代 的起 點 ） ， 每 個 T值 的 迭 代 次 數(shù) L 對 做 第 三 至 第 六 步 ： 對 當 前 解 隨 機 擾 動 ， 產 生 新 解 S 計 算 增 量 ， 其 中 為 評 價 函 數(shù) 若 0則 接 受 S為 新 的 當 前 解 ， 否 則 以 概 率 接受 S作 為 新 的 當 前 解 如 果 滿 足 終 止 條 件 則 輸 出 當 前 解 作 為 最 優(yōu) 解 ， 結 束 程 序 Sf 2 1S Sdf f f exp /df T1, ,k L 智能算法概述4、蟻群算法背景單 個 的 螞 蟻 為 了 避 免 自 己 迷 路 ，

12、它在 爬 行 時 ， 同 時 也 會 釋 放 一 種 特 殊 的 分泌 物 信 息 素 ， 信 息 素 濃 度 越 高 ， 表示 對 應 路 徑 越 短 。 當 一 條 路 上 的 信 息 素越 來 越 多 ， 后 來 的 螞 蟻 選 擇 這 條 路 徑 的概 率 也 就 越 來 越 大 ， 從 而 進 一 步 增 加 了該 路 徑 的 信 息 素 濃 度 。 智能算法概述4、蟻群算法模型蟻群轉移概率公式 信息更新公式Ant cycle system Ant quantity system Ant density system , , , , 0, k kk s J i i j i j if j J ii s i sp i j otherwise 11 1 ,0ijij ij ijn kij kt t / ,0, ij kk Q L 其 他 / ,0,ij ijk Q d 其 他 ,0,ijk Q 其 他 智能算法概述4、蟻群算法二維路徑規(guī)劃問題描述與流程二 維 空 間 中 存 在 4個 障 礙 物 ， 尋 求 一 條從 起 點 S到 終 點 T的 最 優(yōu) 路 徑 智能算法概述4、蟻群算法路徑規(guī)劃結果