《《智能算法初步》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《智能算法初步》PPT課件.ppt（104頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 2 2021-4-21l 蒙 特 卡 羅 算 法l 數(shù) 據(jù) 擬 合 、 參 數(shù) 估 計 、 插 值 等 數(shù) 據(jù) 處 理 算 法l 線 性 規(guī) 劃 等 規(guī) 劃 類 問 題l 圖 論 算 法l 動 態(tài) 規(guī) 劃 、 回 溯 搜 索 、 分 支 定 界 等 計 算 機 算 法l 模 擬 退 火 、 神 經(jīng) 網(wǎng) 絡(luò) 、 遺 傳 算 法 等 最 優(yōu) 化 理 論 算 法l 網(wǎng) 格 算 法 和 窮 舉 法l 一 些 連 續(xù) 離 散 化 方 法l 數(shù) 值 分 析 算 法l 圖 像 處 理 算 法 3 2021-4-213 人 工 智 能 優(yōu) 化 算 法l 遺 傳 算 法l 模 擬 退 火l 人 工 神 經(jīng) 網(wǎng)

2、 絡(luò) 算 法l 粒 子 群 算 法l 蟻 群 算 法 4 2021-4-21l 人 工 智 能 (Artificial Intelligence, AI) 概念 是 John McCarthy（ 約 翰 .麥 克 斯 ） 于1956年 在 Dartmouth學(xué) 會 上 提 出 的 。l 美 國 計 算 機 科 學(xué) 家 ， 因 在 人 工 智 能 領(lǐng) 域的 重 大 貢 獻(xiàn) ， 被 稱 為 “ 人 工 智 能 之 父 ”， 并 因 此 獲 得 圖 靈 獎l 他 于 1948年 獲 得 加 州 理 工 學(xué) 院 數(shù) 學(xué) 學(xué) 士學(xué) 位 ， 1951年 獲 得 普 林 斯 頓 大 學(xué) 數(shù) 學(xué) 博士 學(xué) 位

3、 John McCarthy 5 2021-4-21l 人 工 智 能 讓 機 器 像 人 一 樣 思 考l 人 工 智 能 是 計 算 機 科 學(xué) 的 前 沿 學(xué) 科 ， 是 研 究 、 開 發(fā) 用 于 模 擬 、 延伸 和 擴 展 人 的 智 能 的 理 論 、 方 法 、 技 術(shù) 及 應(yīng) 用 系 統(tǒng) 的 一 門 新 的 技術(shù) 科 學(xué) .計 算 機 編 程 語 言 和 其 它 計 算 機 軟 件 都 因 為 有 了 人 工 智 能 的進(jìn) 展 而 得 以 存 在 。l 人 工 智 能 涉 及 學(xué) 科 ： 哲 學(xué) 和 認(rèn) 知 科 學(xué) ， 數(shù) 學(xué) ， 神 經(jīng) 生 理 學(xué) ， 心 理學(xué) ， 計 算

4、 機 科 學(xué) ， 信 息 論 ， 控 制 論 ， 不 定 性 論 ， 仿 生 學(xué) 等 6 2021-4-21l 人 工 智 能 的 目 的 ： 通 過 研 究 人 腦 的 組 成 機 理 和 思 維 方 式 ， 企 圖 了解 智 能 的 實 質(zhì) ， 并 生 產(chǎn) 出 一 種 能 以 人 類 智 能 相 似 的 方 式 做 出 反 應(yīng)的 智 能 機 器 讓 機 器 具 有 智 慧 ， 像 人 一 樣 思 考 .l 計 算 機 的 出 現(xiàn) 人 類 開 始 真 正 有 了 一 個 可 以 模 擬 人 類 思 維 的 工具l 人 工 智 能 的 領(lǐng) 域 研 究 ： 包 括 機 器 人 、 語 言 識 別

5、 、 圖 像 識 別 、 自 然語 言 處 理 和 專 家 系 統(tǒng) 等 . 7 2021-4-21意 識 和 人 工 智 能 的 區(qū) 別l 人 工 智 能 就 其 本 質(zhì) 而 言 ， 是 對 人 的 思 維 的 信 息 過 程 的 模 擬 .l 對 于 人 的 思 維 模 擬 可 以 從 兩 條 道 路 進(jìn) 行 ： 結(jié) 構(gòu) 模 擬 ： 仿 照 人 腦 的 結(jié) 構(gòu) 機 制 ， 制 造 出 “ 類 人 腦 ” 的 機 器 ； 功 能 模 擬 ： 暫 時 撇 開 人 腦 的 內(nèi) 部 結(jié) 構(gòu) ， 而 從 其 功 能 過 程 進(jìn) 行 模 擬 。 現(xiàn) 代 電 子 計 算 機 的 產(chǎn) 生 便 是 對 人 腦

6、 思 維 功 能 的 模 擬 ， 是 對 人 腦思 維 的 信 息 過 程 的 模 擬 .l 人 工 智 能 不 是 人 的 智 能 ， 更 不 會 超 過 人 的 智 能 . 8 2021-4-21“機 器 思 維 ” 同 “ 人 類 思 維 ” 的 本 質(zhì) 區(qū) 別 ： 1. 人 工 智 能 純 系 無 意 識 的 機 械 的 物 理 的 過 程 ， 人 類 智 能 主 要 是 生理 和 心 理 的 過 程 . 2. 人 工 智 能 沒 有 社 會 性 . 3. 人 工 智 能 沒 有 人 類 的 意 識 所 特 有 的 能 動 的 創(chuàng) 造 能 力 . 4. 兩 者 總 是 人 腦 的 思

7、維 在 前 ， 電 腦 的 功 能 在 后 . 9 2021-4-21 * 1996年 2月 10-17日 , Garry Kasparov以 4:2戰(zhàn) 勝 “ 深 藍(lán) ” (Deep Blue) * 1997年 5月 3-11日 , Garry Kasparov以 3.5:2.5輸 于 改 進(jìn) 后 的 “ 深 藍(lán) ” * 2003年 2月 Garry Kasparov 3:3戰(zhàn) 平 “ 小 深 ” (Deep Junior) * 2003年 11月 Garry Kasparov 2:2戰(zhàn) 平 “ X3D德 國 人 ” (X3D-Fritz ) 指 紋 識 別 、 人 臉 識 別 、 語 音

8、識 別 、 文 字 識 別 、 圖 像 識 別 、 車 牌 識 別 等 10 2021-4-21 中 文 名 ： 人 工 智 能 片 名 ： AI 年 代 ： 2001 國 家 ： 美 國 視 讀 人 工 智 能 、 人 工 智 能 的 未 來 、 人 工 智 能 哲 學(xué) 、 人工 智 能 ： 一 種 現(xiàn) 代 的 方 法 11 2021-4-21l 遺 傳 算 法 (Genetic Algorithm， GA)l 人 工 神 經(jīng) 網(wǎng) 絡(luò) 算 法 (Artificical Neural Network , ANN)l 模 擬 退 火 (Simulated Annealing, SA)l 粒 子

9、群 優(yōu) 化 算 法 (Partical Swam Optimization Algorithm, PSOA)l 蟻 群 優(yōu) 化 算 法 (Ant Colony Optimization Algorithm, ACOA) 12 2021-4-21 97年 A 題 用 模 擬 退 火 算 法 00年 B 題 用 神 經(jīng) 網(wǎng) 絡(luò) 分 類 算 法 01年 B 題 這 種 難 題 也 可 以 使 用 神 經(jīng) 網(wǎng) 絡(luò) 美 國 89年 A 題 也 和 BP 算 法 有 關(guān) 系 美 國 03年 B 題 伽 馬 刀 問 題 也 是 目 前 研 究 的 課 題 ， 目 前算 法 最 佳 的 是 遺 傳 算 法 。

10、遺 傳 算 法 (GA)、 模 擬 退 火 法 (SA)、 神 經(jīng) 網(wǎng) 絡(luò) (NN)、 近 幾 年 的 賽 題 越 來 越 復(fù) 雜 ， 很 多 問 題 沒 有 什 么 很 好 的模 型 可 以 借 鑒 ， 于 是 這 三 類 算 法 很 多 時 候 可 以 派 上 用 場 。 13 2021-4-21l 遺 傳 算 法 (Genetic Algorithm， GA)l 人 工 神 經(jīng) 網(wǎng) 絡(luò) 算 法 (Artificical Neural Network , ANN)l 模 擬 退 火 (Simulated Annealing, SA)l 粒 子 群 優(yōu) 化 算 法 (Partical Swa

11、m Optimization Algorithm, PSOA)l 蟻 群 優(yōu) 化 算 法 (Ant Colony Optimization Algorithm, ACOA) 14 2021-4-21進(jìn) 化 算 法 (Evolutionary Algorithm) 15 2021-4-21l 遺 傳 算 法 是 一 類 模 擬 達(dá) 爾 文 生 物 進(jìn) 化 論 的 自 然 選 擇 和 遺 傳 算 法 機理 的 生 物 進(jìn) 化 過 程 的 計 算 模 型 ， 借 鑒 生 物 界 的 進(jìn) 化 規(guī) 律 （ 適 者 生存 ， 優(yōu) 勝 劣 汰 遺 傳 機 制 ） 演 化 而 來 的 隨 機 化 搜 索 最

12、優(yōu) 化 方 法 。l 遺 傳 算 法 最 初 由 美 國 密 歇 根 大 學(xué) J. Holland（ 霍 蘭 德 ） 教 授 于 1975年 首 先 提 出 來 的 ， 并 出 版 了 頗 有 影 響 的 專 著 Adaptation in Natural and Artificial Systems , 遺 傳 算 法 這 個 名 稱 才 逐 漸 為 人 所知 ， 通 常 稱 為 “ 簡 單 遺 傳 算 法 ” 。 16 2021-4-21l 直 接 對 結(jié) 構(gòu) 對 象 進(jìn) 行 操 作 ， 不 存 在 求 導(dǎo) 和 函 數(shù) 連 續(xù) 性 的 限 定 ； 具 有 內(nèi) 在 的 隱 并 行 性 和 更

13、 好 的 全 局 尋 優(yōu) 能 力 ； 采 用 概 率 化 的 尋 優(yōu) 方 法 ， 能 自 動 獲 取 和 指 導(dǎo) 優(yōu) 化 的 搜 索 空 間 ， 自適 應(yīng) 地 調(diào) 整 搜 索 方 向 ， 不 需 要 確 定 的 規(guī) 則 。l 遺 傳 算 法 的 這 些 性 質(zhì) ， 已 被 人 們 廣 泛 地 應(yīng) 用 于 組 合 優(yōu) 化 、 機 器 學(xué)習(xí) 、 信 號 處 理 、 自 適 應(yīng) 控 制 和 人 工 生 命 等 領(lǐng) 域 。 它 是 現(xiàn) 代 有 關(guān) 智能 計 算 中 的 關(guān) 鍵 技 術(shù) 。 遺 傳 算 法 的 主 要 特 點 17 2021-4-21l 遺 傳 算 法 是 從 代 表 問 題 可 能 潛

14、 在 的 解 集 的 一 個 種 群 （ population）開 始 的 ， 而 一 個 種 群 則 由 經(jīng) 過 基 因 （ gene） 編 碼 的 一 定 數(shù) 目 的 個體 (individual)組 成 。l 每 個 個 體 實 際 上 是 染 色 體 (chromosome)帶 有 特 征 的 實 體 。l 染 色 體 作 為 遺 傳 物 質(zhì) 的 主 要 載 體 ， 即 多 個 基 因 的 集 合 ， 其 內(nèi) 部 表現(xiàn) （ 即 基 因 型 ） 是 某 種 基 因 組 合 ， 它 決 定 了 個 體 的 形 狀 的 外 部 表現(xiàn) ， 如 黑 頭 發(fā) 的 特 征 是 由 染 色 體 中 控

15、 制 這 一 特 征 的 某 種 基 因 組 合決 定 的 。 因 此 ， 在 一 開 始 需 要 實 現(xiàn) 從 表 現(xiàn) 型 到 基 因 型 的 映 射 即 編碼 工 作 。 18 2021-4-21l 由 于 仿 照 基 因 編 碼 的 工 作 很 復(fù) 雜 ， 我 們 往 往 進(jìn) 行 簡 化 ， 如 二 進(jìn) 制編 碼 ， 初 代 種 群 產(chǎn) 生 之 后 ， 按 照 適 者 生 存 和 優(yōu) 勝 劣 汰 的 原 理 ， 逐代 （ generation） 演 化 產(chǎn) 生 出 越 來 越 好 的 近 似 解 。l 在 每 一 代 ， 根 據(jù) 問 題 域 中 個 體 的 適 應(yīng) 度 （ fitness）

16、 大 小 選 擇 （selection） 個 體 ， 并 借 助 于 自 然 遺 傳 學(xué) 的 遺 傳 算 子 （ genetic operators） 進(jìn) 行 組 合 交 叉 （ crossover） 和 變 異 （ mutation） ， 產(chǎn)生 出 代 表 新 的 解 集 的 種 群 。 這 個 過 程 將 導(dǎo) 致 種 群 像 自 然 進(jìn) 化 一 樣的 后 生 代 種 群 比 前 代 更 加 適 應(yīng) 于 環(huán) 境 ， 末 代 種 群 中 的 最 優(yōu) 個 體 經(jīng)過 解 碼 （ decoding） ， 可 以 作 為 問 題 近 似 最 優(yōu) 解 。 19 2021-4-21l 由 于 遺 傳 算

17、法 的 整 體 搜 索 策 略 和優(yōu) 化 搜 索 方 法 在 計 算 是 不 依 賴 于梯 度 信 息 或 其 它 輔 助 知 識 ， 而 只需 要 影 響 搜 索 方 向 的 目 標(biāo) 函 數(shù) 和相 應(yīng) 的 適 應(yīng) 度 函 數(shù) ， 所 以 遺 傳 算法 提 供 了 一 種 求 解 復(fù) 雜 系 統(tǒng) 問 題的 通 用 框 架 ， 它 不 依 賴 于 問 題 的具 體 領(lǐng) 域 ， 對 問 題 的 種 類 有 很 強的 魯 棒 性 。 20 2021-4-21l 遺 傳 算 法 是 由 進(jìn) 化 論 和 遺 傳 學(xué) 機 理 而 產(chǎn) 生 的 搜 索 算 法 。 1. 創(chuàng) 建 一 個 隨 機 的 初 始 狀

18、 態(tài) ： 初 始 群 是 從 解 中 隨 機 選 擇 出 來 的 ， 將這 些 解 比 喻 為 染 色 體 或 基 因 ， 該 種 群 被 稱 為 第 一 代 。 2. 評 估 適 應(yīng) 度 ： 對 每 一 個 解 (染 色 體 )指 定 一 個 適 應(yīng) 度 的 值 ， 根 據(jù) 問 題求 解 的 實 際 接 近 程 度 來 指 定 (以 便 逼 近 求 解 問 題 的 答 案 )。 不 要 把 這 些“ 解 ” 與 問 題 的 “ 答 案 ” 混 為 一 談 ， 可 以 把 它 理 解 成 為 要 得 到 答 案 ，系 統(tǒng) 可 能 需 要 利 用 的 那 些 特 性 。 21 2021-4-21

19、l 3. 繁 殖 (包 括 子 代 突 變 ) 帶 有 較 高 適 應(yīng) 度 值 的 那 些 染 色 體 更 可 能 產(chǎn) 生 后 代 (后 代 產(chǎn) 生 后 也 將 發(fā) 生突 變 )。 后 代 是 父 母 的 產(chǎn) 物 ， 他 們 由 來 自 父 母 的 基 因 結(jié) 合 而 成 ， 這 個 過程 被 稱 為 “ 雜 交 ” 。 4. 下 一 代 如 果 新 的 一 代 包 含 一 個 解 ， 能 產(chǎn) 生 一 個 充 分 接 近 或 等 于 期 望 答 案 的 輸 出， 那 么 問 題 就 已 經(jīng) 解 決 了 。 如 果 情 況 并 非 如 此 ， 新 的 一 代 將 重 復(fù) 他 們 父母 所 進(jìn) 行

20、 的 繁 衍 過 程 ， 一 代 一 代 演 化 下 去 ， 直 到 達(dá) 到 期 望 的 解 為 止 。 22 2021-4-21l 5. 并 行 計 算 * 非 常 容 易 將 遺 傳 算 法 用 到 并 行 計 算 和 群 集 環(huán) 境 中 。 * 一 種 方 法 是 直 接 把 每 個 節(jié) 點 當(dāng) 成 一 個 并 行 的 種 群 看 待 。 然 后 有 機 體根 據(jù) 不 同 的 繁 殖 方 法 從 一 個 節(jié) 點 遷 移 到 另 一 個 節(jié) 點 。 * 另 一 種 方 法 是 “ 農(nóng) 場 主 /勞 工 ” 體 系 結(jié) 構(gòu) ， 指 定 一 個 節(jié) 點 為 “ 農(nóng) 場主 ” 節(jié) 點 ， 負(fù) 責(zé)

21、 選 擇 有 機 體 和 分 派 適 應(yīng) 度 的 值 ， 另 外 的 節(jié) 點 作 為“ 勞 工 ” 節(jié) 點 ， 負(fù) 責(zé) 重 新 組 合 、 變 異 和 適 應(yīng) 度 函 數(shù) 的 評 估 。 23 2021-4-21 遺 傳 算 法 模 擬 自 然 選 擇 和 自 然 遺 傳 過 程 中 發(fā) 生的 繁 殖 、 交 叉 和 基 因 突 變 現(xiàn) 象 ， 在 每 次 迭 代 中都 保 留 一 組 候 選 解 ， 并 按 某 種 指 標(biāo) 從 解 群 中 選取 較 優(yōu) 的 個 體 ， 利 用 遺 傳 算 子 (選 擇 、 交 叉 和 變異 )對 這 些 個 體 進(jìn) 行 組 合 ， 產(chǎn) 生 新 一 代 的 候

22、 選 解群 ， 重 復(fù) 此 過 程 ， 直 到 滿 足 某 種 收 斂 指 標(biāo) 為 止 。 24 2021-4-21 25 2021-4-21GA-第 0代 26 2021-4-21GA-第 1代 27 2021-4-21GA-第 ?代 28 2021-4-21GA-第 N代 29 2021-4-21生 物 進(jìn) 化 遺 傳 算 法適 者 生 存 適 應(yīng) 函 數(shù) 值 最 大 的 解 被 保 留 的 概 率 最 大個 體 問 題 的 一 個 解染 色 體 解 的 編 碼基 因 編 碼 的 元 素群 體 被 選 定 的 一 組 解種 群 根 據(jù) 適 應(yīng) 函 數(shù) 選 擇 的 一 組 解交 叉 以 一

23、定 的 方 式 由 雙 親 產(chǎn) 生 后 代 的 過 程變 異 編 碼 的 某 些 分 量 發(fā) 生 變 化 的 過 程環(huán) 境 適 應(yīng) 函 數(shù) 30 2021-4-21 選 擇 (selection): 根 據(jù) 各 個 個 體 的 適 應(yīng) 值 ， 按 照 一 定 的 規(guī) 則 或 方 法 ，從 第 t代 群 體 P(t)中 選 擇 出 一 些 優(yōu) 良 的 個 體 遺 傳 到 下一 代 群 體 P(t+1)中 。 交 叉 (crossover): 將 群 體 P(t)內(nèi) 的 各 個 個 體 隨 機 搭 配 成 對 ， 對 每 一 個個 體 ， 以 某 個 概 率 Pc (稱 為 交 叉 概 率 ， c

24、rossvoer rate)交 換 它 們 之 間 的 部 分 染 色 體 。 變 異 (mutation): 對 群 體 P(t)中 的 每 一 個 個 體 ， 以 某 一 概 率 Pm(稱 為 變異 概 率 ， mutation rate)改 變 某 一 個 或 一 些 基 因 座上 基 因 值 為 其 它 的 等 位 基 因 。 31 2021-4-21 如 何 進(jìn) 行 編 碼 ？ 如 何 產(chǎn) 生 初 始 種 群 ？ 如 何 定 義 適 應(yīng) 函 數(shù) ？ 如 何 進(jìn) 行 遺 傳 操 作 (復(fù) 制 、 交 叉 、 變 異 )？ 如 何 產(chǎn) 生 下 一 代 種 群 ？ 如 何 定 義 停 止

25、準(zhǔn) 則 ？ 32 2021-4-21表 現(xiàn) 型 空 間 編 碼 (Coding)解 碼 (Decoding)基 因 型 空 間 = 0,1L0111010010100010011001001010010001 33 2021-4-21編 碼 設(shè) 某 一 參 數(shù) 的 取 值 范 圍 為 （ L， U） ， 使 用 長 度 為 k 的 二 進(jìn) 制 編 碼表 示 該 數(shù) ， 則 共 有 種 不 同 的 編 碼 。k2 k 0000000000 00000000001 10000000010 20000000011 31111111111 2 1 34 2021-4-21解 碼 解 碼 的 目 的 是

26、 為 了 將 不 直 觀 的 二 進(jìn) 制 數(shù) 據(jù) 串 還 原 成 十 進(jìn) 制 。( )k ii ki U Lx L b 11 2 2 1設(shè) 某 一 個 體 的 二 進(jìn) 制 編 碼 為 ,k k kb b b b b b 1 2 3 2 1 則 對 應(yīng) 的 解 碼 公 式 為 ： 35 2021-4-21適 應(yīng) 函 數(shù) (Fitness Function) GA在 搜 索 中 不 依 靠 外 部 信 息 ， 僅 以 適 應(yīng) 函 數(shù) 為 依 據(jù) ， 利 用群 體 中 每 個 染 色 體 (個 體 )的 適 應(yīng) 值 來 進(jìn) 行 搜 索 。 以 染 色 體適 應(yīng) 值 的 大 小 來 確 定 該 染 色

27、 體 被 遺 傳 到 下 一 代 群 體 中 的 概率 。 染 色 體 適 應(yīng) 值 越 大 ， 該 染 色 體 被 遺 傳 到 下 一 代 的 概 率也 越 大 ； 反 之 ， 染 色 體 的 適 應(yīng) 值 越 小 ， 該 染 色 體 被 遺 傳 到下 一 代 的 概 率 也 越 小 。 因 此 適 應(yīng) 函 數(shù) 的 選 取 至 關(guān) 重 要 ， 直接 影 響 到 GA的 收 斂 速 度 以 及 能 否 找 到 最 優(yōu) 解 。 群 體 中 的 每 個 染 色 體 都 需 要 計 算 適 應(yīng) 值 適 應(yīng) 函 數(shù) 一 般 由 目 標(biāo) 函 數(shù) 變 換 而 成 36 2021-4-21適 應(yīng) 函 數(shù) (Fi

28、tness Function) 適 應(yīng) 函 數(shù) 常 見 形 式 ： 直 接 將 目 標(biāo) 函 數(shù) 轉(zhuǎn) 化 為 適 應(yīng) 函 數(shù) 若 目 標(biāo) 函 數(shù) 為 最 大 化 問 題 ： Fitness(f(x) = f(x) 若 目 標(biāo) 函 數(shù) 為 最 小 化 問 題 ： Fitness(f(x) = -f(x) 37 2021-4-21適 應(yīng) 函 數(shù) (Fitness Function) 界 限 構(gòu) 造 法 min min( ) , ( )Fitness( ( ) 0f x C f x Cf x others ， 目 標(biāo) 函 數(shù) 為 最 大 化 問 題其 中 Cmin為 f(x)的 最 小 估 計 值ma

29、x max( ), ( )Fitness( ( ) 0C f x f x Cf x others ， 目 標(biāo) 函 數(shù) 為 最 小 化 問 題其 中 Cmaxn為 f(x)的 最 大 估 計 值 38 2021-4-21選 擇 (Selection) 選 擇 (復(fù) 制 )操 作 把 當(dāng) 前 種 群 的 染 色 體 按 與 適 應(yīng) 值 成 正 比例 的 概 率 復(fù) 制 到 新 的 種 群 中 主 要 思 想 : 適 應(yīng) 值 較 高 的 染 色 體 體 有 較 大 的 選 擇 (復(fù) 制 )機 會設(shè) 種 群 的 規(guī) 模 為 Nxi是 種 群 中 第 i個 染 色 體 1 ( )( ) ( ) is i

30、 N jj f xp x f x染 色 體 xi被 選 概 率 39 2021-4-21選 擇 (Selection) 實 現(xiàn) 1： ” 輪 盤 賭 ” 選 擇 (Roulette wheel selection) l產(chǎn) 生 一 個 在 0與 總 和 之 間 的 的 隨 機 數(shù) ml從 種 群 中 編 號 為 1的 染 色 體 開 始 ， 將 其 適 應(yīng) 值 與 后 續(xù) 染 色 體 的 適 應(yīng) 值 相加 ， 直 到 累 加 和 等 于 或 大 于 m 40 2021-4-21選 擇 (Selection)染 色 體 的 適 應(yīng) 值 和 所 占 的 比 例 輪 盤 賭 選 擇 41 2021-4

31、-21選 擇 (Selection)隨 機 數(shù) 23 49 13 38 6 27所 選 號 碼 2 6 2 5 1 4所 選 染 色 體 11000 00011 11000 01100 01110 10010染 色 體 編 號 1 2 3 4 5 6染 色 體 01110 11000 00100 10010 01100 00011適 應(yīng) 度 8 15 2 5 12 8被 選 概 率 0.16 0.3 0.04 0.1 0. 24 0.16適 應(yīng) 度 累 計 8 23 25 30 42 50染 色 體 被 選 的 概 率被 選 的 染 色 體 42 2021-4-21選 擇 (Selection

32、) 輪 盤 上 的 片 分 配 給 群 體 的 染 色 體 ， 使 得 每 一 個 片 的 大 小 與 對 于染 色 體 的 適 應(yīng) 值 成 比 例 從 群 體 中 選 擇 一 個 染 色 體 可 視 為 旋 轉(zhuǎn) 一 個 輪 盤 ， 當(dāng) 輪 盤 停 止 時 ，指 針 所 指 的 片 對 于 的 染 色 體 就 時 要 選 的 染 色 體 。 模 擬 “ 輪 盤 賭 ” 算 法 ：(1)r=rand(0, 1)， s=0， i=0；(2)如 果 sr， 則 轉(zhuǎn) (4)；(3)s=s+p(xi)， i=i+1, 轉(zhuǎn) (2)(4)xi即 為 被 選 中 的 染 色 體 ， 輸 出 I(5)結(jié) 束 4

33、3 2021-4-21選 擇 (Selection) 其 他 選 擇 法 ： 隨 機 遍 歷 抽 樣 (Stochastic universal sampling) 局 部 選 擇 (Local selection) 截 斷 選 擇 (Truncation selection) 競 標(biāo) 賽 選 擇 (Tournament selection) 特 點 ： 選 擇 操 作 得 到 的 新 的 群 體 稱 為 交 配 池 ， 交 配池 是 當(dāng) 前 代 和 下 一 代 之 間 的 中 間 群 體 ， 其 規(guī) 模 為 初始 群 體 規(guī) 模 。 選 擇 操 作 的 作 用 效 果 是 提 高 了 群 體

34、 的平 均 適 應(yīng) 值 (低 適 應(yīng) 值 個 體 趨 于 淘 汰 ， 高 適 應(yīng) 值 個體 趨 于 選 擇 )， 但 這 也 損 失 了 群 體 的 多 樣 性 。 選 擇操 作 沒 有 產(chǎn) 生 新 的 個 體 ， 群 體 中 最 好 個 體 的 適 應(yīng) 值不 會 改 變 。 44 2021-4-21 交 叉 (crossover, Recombination) 遺 傳 交 叉 (雜 交 、 交 配 、 有 性 重 組 )操 作 發(fā) 生 在 兩 個染 色 體 之 間 ， 由 兩 個 被 稱 之 為 雙 親 的 父 代 染 色 體 ，經(jīng) 雜 交 以 后 ， 產(chǎn) 生 兩 個 具 有 雙 親 的 部

35、 分 基 因 的 新 的染 色 體 ， 從 而 檢 測 搜 索 空 間 中 新 的 點 。 選 擇 (復(fù) 制 )操 作 每 次 作 用 在 一 個 染 色 體 上 ， 而 交 叉操 作 每 次 作 用 在 從 交 配 池 中 隨 機 選 取 的 兩 個 個 體 上(交 叉 概 率 Pc)。 交 叉 產(chǎn) 生 兩 個 子 染 色 體 ， 他 們 與 其 父 代 不 同 ， 且 彼此 不 同 , 每 個 子 染 色 體 都 帶 有 雙 親 染 色 體 的 遺 傳基 因 。 45 2021-4-21單 點 交 叉 (1-point crossover) 在 雙 親 的 父 代 染 色 體 中 隨 機

36、產(chǎn) 生 一 個 交 叉 點 位 置 在 交 叉 點 位 置 分 離 雙 親 染 色 體 互 換 交 叉 點 位 置 右 邊 的 基 因 碼 產(chǎn) 生 兩 個 子 代 染 色 體 交 叉 概 率 Pc 一 般 范 圍 為 (60%, 90%)， 平 均 約 80% 46 2021-4-21 單 點 交 叉 操 作 可 以 產(chǎn) 生 與 父 代 染 色 體 完 全 不 同 的子 代 染 色 體 ； 它 不 會 改 變 父 代 染 色 體 中 相 同 的 基因 。 但 當(dāng) 雙 親 染 色 體 相 同 時 ， 交 叉 操 作 是 不 起 作用 的 。假 如 交 叉 概 率 Pc 50%,則 交 配 池 中

37、 50%的 染 色 體 (一 半 染 色 體 )將 進(jìn) 行 交 叉 操 作 ， 余 下 的 50%的 染 色 體 進(jìn) 行 選 擇 (復(fù) 制 )操 作 。 GA利 用 選 擇 和 交 叉 操 作 可 以 產(chǎn) 生 具 有 更 高 平 均 適應(yīng) 值 和 更 好 染 色 體 的 群 體 47 2021-4-21 以 變 異 概 率 Pm改 變 染 色 體 的 某 一 個 基 因 ,當(dāng) 以 二 進(jìn) 制編 碼 時 ， 變 異 的 基 因 由 0變 成 1， 或 者 由 1變 成 0。 變 異 概 率 Pm 一 般 介 于 1/種 群 規(guī) 模 與 1/染 色 體 長 度 之間 ， 平 均 約 1-2% 48

38、 2021-4-21 比 起 選 擇 和 交 叉 操 作 ， 變 異 操 作 是 GA中 的 次 要 操 作 ，但 它 在 恢 復(fù) 群 體 中 失 去 的 多 樣 性 方 面 具 有 潛 在 的 作用 。 在 GA執(zhí) 行 的 開 始 階 段 ， 染 色 體 中 一 個 特 定 位 上 的 值 1可 能 與 好 的 性能 緊 密 聯(lián) 系 ， 即 搜 索 空 間 中 某 些 初 始 染 色 體 在 那 個 位 上 的 值 1可 能 一致 產(chǎn) 生 高 的 適 應(yīng) 值 。 因 為 越 高 的 適 應(yīng) 值 與 染 色 體 中 那 個 位 上 的 值 1相 聯(lián)系 ， 選 擇 操 作 就 越 會 使 群 體

39、 的 遺 傳 多 樣 性 損 失 。 等 到 達(dá) 一 定 程 度 時 ， 值 0會 從 整 個 群 體 中 那 個 位 上 消 失 ， 然 而 全 局 最優(yōu) 解 可 能 在 染 色 體 中 那 個 位 上 為 0。 如 果 搜 索 范 圍 縮 小 到 實 際 包 含 全 局最 優(yōu) 解 的 那 部 分 搜 索 空 間 ， 在 那 個 位 上 的 值 0就 可 能 正 好 是 到 達(dá) 全 局 最優(yōu) 解 所 需 要 的 。 49 2021-4-21 種 群 中 個 體 的 最 大 適 應(yīng) 值 超 過 預(yù) 設(shè) 定 值 種 群 中 個 體 的 平 均 適 應(yīng) 值 超 過 預(yù) 設(shè) 定 值 種 群 中 個

40、體 的 進(jìn) 化 代 數(shù) 超 過 預(yù) 設(shè) 定 值 50 2021-4-21(1) 隨 機 產(chǎn) 生 初 始 種 群 ;(2) 計 算 種 群 體 中 每 個 個 體 的 適 應(yīng) 度 值 ,判 斷 是 否 滿足 停 止 條 件 ， 若 不 滿 足 ， 則 轉(zhuǎn) 第 (3)步 ,否 則 轉(zhuǎn) 第(6)步 ;(3) 按 由 個 體 適 應(yīng) 值 所 決 定 的 某 個 規(guī) 則 選 擇 將 進(jìn) 入 下一 代 的 個 體 ;(4) 按 交 叉 概 率 Pc進(jìn) 行 交 叉 操 作 ,生 產(chǎn) 新 的 個 體 ;(5) 按 變 異 概 率 Pm進(jìn) 行 變 異 操 作 ,生 產(chǎn) 新 的 個 體 ;(6) 輸 出 種 群

41、中 適 應(yīng) 度 值 最 優(yōu) 的 染 色 體 作 為 問 題 的 滿意 解 或 最 優(yōu) 解 。 51 2021-4-21 52 2021-4-21基 本 遺 傳 算 法 （ Simple Genetic Algorithms,簡 稱 SGA） 是 一 種 統(tǒng) 一 的 最 基 本 的 遺 傳 算 法 ， 它 只使 用 選 擇 、 交 叉 、 變 異 這 三 種 基 本 遺 傳 算 子 ， 其 遺 傳進(jìn) 化 操 作 過 程 簡 單 ， 容 易 理 解 ， 是 其 他 一 些 遺 傳 算 法的 雛 形 和 基 礎(chǔ) ， 它 不 僅 給 各 種 遺 傳 算 法 提 供 了 一 個 基本 框 架 ， 同 時

42、 也 具 有 一 定 的 應(yīng) 用 價 值 。 53 2021-4-21Procedure Genetic Algorithm begint = 0 ; %遺 傳 代 數(shù)初 始 化 P(t) ; %初 始 化 種 群 或 染 色 體計 算 P(t) 的 適 應(yīng) 值 ;while (不 滿 足 停 止 準(zhǔn) 則 ) do begin t = t+1 ; 從 P(t-1)中 選 擇 P(t) ; % selection 重 組 P(t) ; % crossover and mutation 計 算 P(t) 的 適 應(yīng) 值 ; end end 54 2021-4-21 函 數(shù) 優(yōu) 化 函 數(shù) 優(yōu) 化

43、是 遺 傳 算 法 的 經(jīng) 典應(yīng) 用 領(lǐng) 域 ， 也 是 對 遺 傳 算 法 進(jìn) 行 性 能 測 試 評價 的 常 用 算 例 。 對 于 一 些 非 線 性 、 多 模 型 、多 目 標(biāo) 的 函 數(shù) 優(yōu) 化 問 題 ， 用 其 他 優(yōu) 化 方 法 較難 求 解 ， 而 遺 傳 算 法 卻 可 以 方 便 地 得 到 較 好的 結(jié) 果 。遺 傳 算 法 提 供 了 一 種 求 解 復(fù) 雜 系 統(tǒng) 優(yōu) 化 問 題 的 通 用 框架 ， 它 不 依 賴 于 問 題 的 具 體 領(lǐng) 域 ， 對 問 題 的 種 類 有 很強 的 魯 棒 性 ， 所 以 廣 泛 應(yīng) 用 于 很 多 學(xué) 科 。 下 面

44、列 舉 一些 遺 傳 算 法 的 主 要 應(yīng) 用 領(lǐng) 域 。 55 2021-4-21 組 合 優(yōu) 化 遺 傳 算 法 是 尋 求 組 合 優(yōu) 化 問 題 滿 意解 的 最 佳 工 具 之 一 ， 實 踐 證 明 ， 遺 傳 算 法 對 于 組 合優(yōu) 化 問 題 中 的 NP完 全 問 題 非 常 有 效 。 例 如 ， 遺 傳 算法 已 經(jīng) 在 求 解 旅 行 商 問 題 (Traveling Salesman Problem , TSP)、 背 包 問 題 (Knapsack Problem)、裝 箱 問 題 (Bin Packing Problem) 等 方 面 得 到 成 功的 應(yīng) 用

45、 。 生 產(chǎn) 調(diào) 度 問 題 生 產(chǎn) 調(diào) 度 問 題 在 很 多 情 況 下 所建 立 起 來 的 數(shù) 學(xué) 模 型 難 以 精 確 求 解 ， 即 使 經(jīng) 過 一 些簡 化 之 后 可 以 進(jìn) 行 求 解 也 會 因 簡 化 得 太 多 而 使 求 解結(jié) 果 與 實 際 相 差 太 遠(yuǎn) 。 現(xiàn) 在 遺 傳 算 法 已 經(jīng) 成 為 解 決復(fù) 雜 調(diào) 度 問 題 的 有 效 工 具 。 56 2021-4-21 自 動 控 制 遺 傳 算 法 已 經(jīng) 在 自 動 控 制 領(lǐng) 域 中 得到 了 很 好 的 應(yīng) 用 ， 例 如 基 于 遺 傳 算 法 的 模 糊 控 制 器的 優(yōu) 化 設(shè) 計 、 基

46、于 遺 傳 算 法 的 參 數(shù) 辨 識 、 基 于 遺 傳算 法 的 模 糊 控 制 規(guī) 則 的 學(xué) 習(xí) 、 利 用 遺 傳 算 法 進(jìn) 行 人工 神 經(jīng) 網(wǎng) 絡(luò) 的 結(jié) 構(gòu) 優(yōu) 化 設(shè) 計 和 權(quán) 值 學(xué) 習(xí) 等 。 機 器 人 智 能 控 制 機 器 人 是 一 類 復(fù) 雜 的 難 以 精確 建 模 的 人 工 系 統(tǒng) ， 而 遺 傳 算 法 的 起 源 就 來 自 于 對人 工 自 適 應(yīng) 系 統(tǒng) 的 研 究 ， 所 以 機 器 人 智 能 控 制 自 然成 為 遺 傳 算 法 的 一 個 重 要 應(yīng) 用 領(lǐng) 域 。 57 2021-4-21 圖 象 處 理 和 模 式 識 別 圖 像

47、處 理 和 模 式 識 別是 計 算 機 視 覺 中 的 一 個 重 要 研 究 領(lǐng) 域 。 在 圖 像 處理 過 程 中 ， 如 掃 描 、 特 征 提 取 、 圖 像 分 割 等 不 可避 免 地 存 在 一 些 誤 差 ， 這 些 誤 差 會 影 響 圖 像 處 理的 效 果 。 如 何 使 這 些 誤 差 最 小 是 使 計 算 機 視 覺 達(dá)到 實 用 化 的 重 要 要 求 ， 遺 傳 算 法 在 這 些 圖 像 處 理中 的 優(yōu) 化 計 算 方 面 得 到 了 很 好 的 應(yīng) 用 。 人 工 生 命 人 工 生 命 是 用 計 算 機 、 機 械 等 人工 媒 體 模 擬 或 構(gòu)

48、 造 出 的 具 有 自 然 生 物 系 統(tǒng) 特 有 行為 的 人 造 系 統(tǒng) 。 自 組 織 能 力 和 自 學(xué) 習(xí) 能 力 是 人 工生 命 的 兩 大 重 要 特 征 。 人 工 生 命 與 遺 傳 算 法 有 著密 切 的 關(guān) 系 ， 基 于 遺 傳 算 法 的 進(jìn) 化 模 型 是 研 究 人工 生 命 現(xiàn) 象 的 重 要 理 論 基 礎(chǔ) 。 58 2021-4-21 遺 傳 程 序 設(shè) 計 Koza發(fā) 展 了 遺 傳 程 序 設(shè) 計 的概 念 ， 他 使 用 了 以 LISP語 言 所 表 示 的 編 碼 方 法 ，基 于 對 一 種 樹 形 結(jié) 構(gòu) 所 進(jìn) 行 的 遺 傳 操 作

49、來 自 動 生成 計 算 機 程 序 。 機 器 學(xué) 習(xí) 基 于 遺 傳 算 法 的 機 器 學(xué) 習(xí) ， 在 很 多領(lǐng) 域 中 都 得 到 了 應(yīng) 用 。 例 如 基 于 遺 傳 算 法 的 機 器學(xué) 習(xí) 可 用 來 調(diào) 整 人 工 神 經(jīng) 網(wǎng) 絡(luò) 的 連 接 權(quán) ， 也 可 以用 于 人 工 神 經(jīng) 網(wǎng) 絡(luò) 的 網(wǎng) 絡(luò) 結(jié) 構(gòu) 優(yōu) 化 設(shè) 計 。 分 類 器系 統(tǒng) 在 多 機 器 人 路 徑 規(guī) 劃 系 統(tǒng) 中 得 到 了 成 功 的 應(yīng)用 。 59 2021-4-21SGA參 數(shù) : 編 碼 方 式 : 二 進(jìn) 制 碼 e.g. 000000; 01101 13; 1111131 種 群

50、規(guī) 模 : 4 隨 機 初 始 群 體 “ 轉(zhuǎn) 盤 賭 ” 選 擇 一 點 雜 交 , 二 進(jìn) 制 變 異 求 函 數(shù) f(x)=x2的 最 大 值 ， x為 自 然 數(shù) 且 0 x31.o 手 工 方 式 完 成 演 示 SGA過 程 60 2021-4-21 61 2021-4-21 62 2021-4-21 63 2021-4-21求 下 列 函 數(shù) 的 最 大 值 ：( ) sin(10 ) 2.0 1,2f x x x x 64 2021-4-21 高 精 度 10 0( ,., ) ( 2 ) , 2 1 L iL iL iy xb a x b x y 編 碼 x,y 0,1L 必

51、 須 可 逆 (一 個 表 現(xiàn) 型 對 應(yīng) 一 個 基 因 型 ) 解 碼 算 子 ： : 0,1L x,y 染 色 體 長 度 L決 定 可 行 解 的 最 大 精 度長 染 色 體 (慢 進(jìn) 化 ) 實 數(shù) 問 題 ： 變 量 z為 實 數(shù) ， 如 何 把 a1,aL 0,1Lz x,y 65 2021-4-21設(shè) 定 求 解 精 確 到 6位 小 數(shù) ， 因 區(qū) 間 長 度 位 2-(-1)=3,則 需 將 區(qū)間 分 為 3X106等 份 。 因 2097152 221 3X1062224194304。 故 編 碼 的 二 進(jìn) 制 串 長 L=22。2121 0 2 1002 ( 1)(

52、 ,., ) 1 ( 2 ) 1,22 1 iiL ib b b 將 一 個 二 進(jìn) 制 串 (b21b20b0)轉(zhuǎn) 化 為 10進(jìn) 制 數(shù) ：e.g. -1; 2 1.627 888 1.627888 = -1+3x(1110000000111111000101) 2 /(222-1) = -1+3x3674053/(222-1) 66 2021-4-21 隨 機 初 始 化 種 群 適 應(yīng) 函 數(shù) 本 實 例 目 標(biāo) 函 數(shù) 在 定 義 域 內(nèi) 均 大 于 0， 且 是 求 函 數(shù) 最大 值 ， 故 直 接 引 用 目 標(biāo) 函 數(shù) 作 為 適 應(yīng) 函 數(shù) ： f(s) = f(x) 其 中

53、 二 進(jìn) 制 串 s對 于 變 量 x的 值 。 e.g. s1 = x1= -0.958 973 適 應(yīng) 值 : f(s1) = f(x1) =1.078 878 s2= x2= 1.627 888 適 應(yīng) 值 : f(s2) = f(x2) = 3.250 650 67 2021-4-21 選 擇 操 作 (“ 輪 盤 賭 ” 選 擇 ) 交 叉 操 作 (單 點 交 叉 ) 交 叉 前 (父 ): s1= s2= 交 叉 后 (子 ): s1= s2= 適 應(yīng) 值 : f(s1) = f(-0.998 113) =1.940 865 f(s2) = f(1.666 028) = 3.45

54、9 245 s2的 適 應(yīng) 值 比 其 雙 親 個 體 的 適 應(yīng) 值 高 。 68 2021-4-21 變 異 操 作 變 異 前 (父 ): s2= 變 異 后 (子 ): s2= 適 應(yīng) 值 f(s2) = f(1.721 638) = 0.917 743 比 f(s2)小 變 異 前 (父 ): s2= 變 異 后 (子 ): s”2= 適 應(yīng) 值 f(s”2) = f(1.630 818) = 3.343 555 比 f(s2)大變 異 操 作 有 ” 擾 動 ” 作 用 ， 同 時 具 有 增 加 種 群多樣 性 的 效 果 。 69 2021-4-21遺 傳 算 法 的 參 數(shù)

55、: 種 群 規(guī) 模 : 50 染 色 體 長 度 : L=22 最 大 進(jìn) 化 代 數(shù) : 150 交 叉 概 率 : Pc=0.25 變 異 概 率 : Pm=0.01 70 2021-4-21世 代 數(shù) 染 色 體 編 碼 變 量 x 適 應(yīng) 值1411173440547189150 10001110000101100011110000011011000101001111011010101110011100111111101010111111010011111100001101111011001111110100100010001100111110001101101000110011110

56、10011011000101100111111010011111100110011111101001111110011001111 1.831 6241.842 4161.854 8601.847 5361.853 2901.848 4431.848 6991.850 8971.850 5491.850 549 3.534 8063.790 3623.833 2863.842 0043.843 4023.846 2323.847 1553.850 1623.850 2743.850 274 71 2021-4-21最 優(yōu) 化 問題 : 1 21 2( ) ( , , , )( , , , )

57、nnMinimize f x f x x xsubjectto x x x x S X 組 合 優(yōu) 化 問 題 (Combinatorial Optimization Problem ) :最 優(yōu) 化 問 題 中 的 解 空 間 X或 S由 離 散 集 合 構(gòu) 成 。 72 2021-4-21傳 統(tǒng) 的 優(yōu) 化 方 法 (局 部 優(yōu) 化 方 法 ) 共 軛 梯 度 法 、 牛 頓 法 、 單 純 形 方 法 等特 點 : 1)依 賴 于 初 始 條 件 。2)與 求 解 空 間 有 緊 密 關(guān) 系 ， 促 使 較 快 地 收 斂 到 局 部 解 ，但 同 時 對 解 域 有 約 束 ， 如 連

58、 續(xù) 性 或 可 微 性 。 利 用這 些 約 束 ， 收 斂 快 。 3)有 些 方 法 ， 如 Davison-Fletcher-Powell直 接 依 賴于 至 少 一 階 導(dǎo) 數(shù) ； 共 軛 梯 度 法 隱 含 地 依 賴 于 梯 度 。 73 2021-4-21全 局 優(yōu) 化 方 法 下 降 軌 線 法 、 Monte-Carlo隨 機 試 驗 法 、 模 擬退 火 法 、 GA等特 點 ：1)不 依 賴 于 初 始 條 件 ；2)不 與 求 解 空 間 有 緊 密 關(guān) 系 ,對 解 域 無 可 微 或 連 續(xù) 的 要 求 ;容 易 實 現(xiàn) ，求 解 穩(wěn) 健 。3)但 收 斂 速 度

59、 慢 ,能 獲 得 全 局 最 優(yōu) ;適 合 于 求 解 空 間 不 知 的 情 況 。4)GA可 應(yīng) 用 于 大 規(guī) 模 、 多 峰 多 態(tài) 函 數(shù) 、 含 離 散 變 量 等 全 局 優(yōu) 化 問題 ;求 解 速 度 和 質(zhì) 量 遠(yuǎn) 超 過 常 規(guī) 方 法 。 74 2021-4-21GA編 碼 ：X=(x1,x2,xn)的 各 個 變 量 可 以 按 二 進(jìn) 制 編 碼 方 法 分 別 編 碼 。對 于 變 量 xi的 上 、 下 限 約 束 lixi ui(i=1,2,n)， 依 據(jù) 解的 精 度 要 求 (有 效 位 數(shù) )求 得 各 個 變 量 X=(x1,x2,xn)的 二 進(jìn) 制

60、碼 位 數(shù) (m1,m2,mn)(確 定 方 法 類 似 于 SGA實 例 2)， 因 此 將n個 二 進(jìn) 制 位 串 順 序 連 接 起 來 ， 構(gòu) 成 一 個 個 體 的 染 色 體 編 碼 ， 編碼 的 總 位 數(shù) m m1+m2+mn。1 2( , , ) 1,2, ,ni i iMinimize f x x xsubjectto l x u i n 無 約 束 最 優(yōu) 化 問 題 : 75 2021-4-21GA解 碼 ：解 碼 時 仍 按 各 個 變 量 的 編 碼 順 序 分 別 實 現(xiàn) 常 規(guī) 的 二 進(jìn) 制 編 碼解 碼 方 法 。二 進(jìn) 制 遺 傳 編 碼 示 意 圖 如

61、下 ： 76 2021-4-21常 規(guī) 解 法 ：(1)把 約 束 問 題 轉(zhuǎn) 化 為 無 約 束 問 題 ， 在 用 無 約 束 問 題方 法 求 解 ， 如 罰 函 數(shù) 法(2)改 進(jìn) 無 約 束 問 題 的 方 法 ， 再 用 于 約 束 問 題 ， 如 梯度 投 影 法 、 廣 義 簡 約 梯 度 法1 2( , , )( ) 0, 1, 2, ,( ) 0, 1, 2, , 1, 2, ,niii i iM inim ize f x x xg x i mh x i ll x u i n 約 束 最 優(yōu) 化 問 題 : 77 2021-4-21 遺 傳 算 法 求 解 關(guān) 鍵 : 約

62、束 條 件 的 處 理等 式 約 束 可 以 包 含 到 適 應(yīng) 函 數(shù) ， 僅 考 慮 不 等 式約 束 。 假 設(shè) 按 無 約 束 問 題 那 樣 求 解 ， 在 搜 索 過 程 中 計 算 目 標(biāo) 函數(shù) 值 ， 并 檢 查 是 否 有 約 束 違 反 。 如 果 沒 有 違 反 ， 則 表 明 是可 行 解 ， 就 根 據(jù) 目 標(biāo) 函 數(shù) 指 定 一 適 應(yīng) 值 ； 否 則 ， 就 是 不 可行 解 ， 因 而 沒 有 適 應(yīng) 值 (適 應(yīng) 值 為 0)。 這 樣 的 處 理 實 際 不 可行 ， 因 為 找 到 一 個 可 行 解 幾 乎 與 找 到 最 優(yōu) 解 一 樣 困 難 。 7

63、8 2021-4-21一 般 解 法 ： 通 過 引 入 罰 函 數(shù) ， 從 不 可 行 解 中 得 到 一 些 信息 。 將 罰 函 數(shù) 包 含 到 適 應(yīng) 函 數(shù) 中 。 關(guān) 鍵 是 如 何 設(shè) 計 罰 函 數(shù) ； 不 同 問 題 需 要 設(shè) 計 不 同 的 罰 函 數(shù) ； 對 一 般 的 約 束 處 理 ， 通 常 很 困 難 。 79 2021-4-21典 型 問 題 ：巡 回 旅 行 商 問 題 (Traveling Salesman Problem)作 業(yè) 調(diào) 度 問 題 (Job Shop Scheduling Problem)背 包 問 題 (Knapsack Problem)

64、圖 著 色 問 題 很 多 組 合 最 優(yōu) 化 問 題 是 NP難 問 題 或 NP完 全 問 題 80 2021-4-21TSP， 也 稱 貨 郎 擔(dān) 問 題 ， 是 一 個 NP完 全 問 題 。TSP描 述 ： 圖 論 :設(shè) 圖 G=(V,E),其 中 V是 頂 點 集 ， E是 邊 集 。 設(shè)C=(cij)是 與 E相 聯(lián) 系 的 距 離 矩 陣 。 尋 找 一 條 通 過 所有 頂 點 且 每 個 頂 點 只 通 過 一 次 的 最 短 距 離 回 路(Hamilton回 路 )。 實 際 應(yīng) 用 中 ， C也 可 解 釋 為 費用 或 旅 行 時 間 矩 陣 。 實 際 :一 位

65、推 銷 員 從 自 己 所 在 城 市 出 發(fā) ， 必 須 遍 訪 所有 城 市 之 后 又 回 到 原 來 的 城 市 ， 求 使 其 旅 行 費 用 最少 的 路 徑 。 81 2021-4-21中 國 貨 郎 擔(dān) 問 題 : 城 市 數(shù) : 40 城 市 編 號1,2,40 尋 找 一 條 最 短 路 徑 82 2021-4-21搜 索 空 間 龐 大TSP涉 及 求 多 個 變 量 的 函 數(shù) 的 最 小 值 ， 求 解 很 困 難 。其 可 能 的 路 徑 條 數(shù) 隨 著 城 市 數(shù) 目 n成 指 數(shù) 增 長 ， 如 ，5個 城 市 對 應(yīng) 12條 路 徑 ； 10個 城 市 對 應(yīng)

66、 181 440條路 徑 ； 100個 城 市 對 應(yīng) 4.6663X10155條 路 徑 。 如 此龐 大 的 搜 索 空 間 ， 常 規(guī) 解 法 和 計 算 工 具 都 遇 到 計 算 上的 困 難 。 只 能 尋 找 近 似 解 法 ， 如 神 經(jīng) 網(wǎng) 絡(luò) 方 法 、 模 擬退 火 法 、 遺 傳 算 法 等 。 83 2021-4-21染 色 體 表 示 成 所 有 城 市 的 一 個 排 列 ， 若 有 n個 城 市 ， 一條 可 能 路 徑 編 碼 為 長 度 為 n的 整 數(shù) 向 量 (i1,i2,in),其 中ik表 示 第 ik個 城 市 。例 如 : 路 徑 編 碼 向 量 (5 1 7 8 9 4 6 2 3)直 接 表 示 一 條旅 行 路 程 (5-1-7-8-9-4-6-2-3)。此 向 量 是 1到 n的 一 個 排 列 ， 即 從 1到 n的 每 個 整 數(shù) 在 這個 向 量 中 正 好 出 現(xiàn) 一 次 ,不 能 有 重 復(fù) 。 這 樣 ， 基 本 遺 傳算 法 的 基 因 操 作 生 成 的 個 體 不 能 滿 足 這 一 約 束 條 件 ， 需尋 求