《人工智能第三章遺傳算法、蟻群算法、粒子群算法》由會(huì)員分享，可在線閱讀，更多相關(guān)《人工智能第三章遺傳算法、蟻群算法、粒子群算法（174頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、2021-4-24 1 第 三 章遺 傳 算 法 、 蟻 群 算 法 與粒 子 群 算 法 2021-4-24 2 3.1 遺 傳 算 法 2021-4-24 3 生 物 在 自 然 界 中 的 生 存 繁 衍 ， 顯 示 出 了 其 對(duì) 自 然 環(huán) 境 的 優(yōu) 異 自適 應(yīng) 能 力 。 受 其 啟 發(fā) ， 人 們 致 力 于 對(duì) 生 物 各 種 生 存 特 性 的 機(jī) 理研 究 和 行 為 模 擬 ， 為 人 工 自 適 應(yīng) 系 統(tǒng) 的 設(shè) 計(jì) 和 開(kāi) 發(fā) 提 供 了 廣 闊的 前 景 。遺 傳 算 法 (Genetic Algorithm， 簡(jiǎn) 稱 GA)就 是 這 種 生 物 行 為 的

2、 計(jì) 算機(jī) 模 擬 中 令 人 矚 目 的 重 要 成 果 ?；?于 對(duì) 生 物 遺 傳 和 進(jìn) 化 過(guò) 程 的 計(jì) 算 機(jī) 模 擬 ， 遺 傳 算 法 使 得 各 種人 工 系 統(tǒng) 具 有 優(yōu) 良 的 自 適 應(yīng) 能 力 和 優(yōu) 化 能 力 。遺 傳 算 法 所 借 鑒 的 生 物 學(xué) 基 礎(chǔ) 就 是 生 物 的 遺 傳 和 進(jìn) 化 。 2021-4-24 4 雖 然 人 們 還 未 完 全 揭 開(kāi) 遺 傳 與 進(jìn) 化 的 奧 秘 ， 既 沒(méi) 有 完 全 掌 握 其 機(jī)制 ， 也 不 完 全 清 楚 染 色 體 編 碼 和 譯 碼 過(guò) 程 的 細(xì) 節(jié) ， 更 不 完 全 了 解其 控 制 方

3、 式 ， 但 遺 傳 與 進(jìn) 化 的 以 下 幾 個(gè) 特 點(diǎn) 卻 為 人 們 所 共 識(shí) ：(1)生 物 的 所 有 遺 傳 信 息 都 包 含 在 其 染 色 休 中 ， 染 色 體 決 定 了 生物 的 性 狀 。(2)染 色 體 是 由 基 因 及 其 有 規(guī) 律 的 排 列 所 構(gòu) 成 的 ， 遺 傳 和 進(jìn) 化 過(guò)程 發(fā) 生 在 染 色 體 上 。(3)生 物 的 繁 殖 過(guò) 程 是 由 其 基 因 的 復(fù) 制 過(guò) 程 來(lái) 完 成 的 ：(4)通 過(guò) 同 源 染 色 體 之 間 的 交 叉 或 染 色 體 的 變 異 會(huì) 產(chǎn) 生 新 的 物 種 ，使 生 物 呈 現(xiàn) 新 的 性 狀

4、。(5)對(duì) 環(huán) 境 適 應(yīng) 性 好 的 基 因 或 染 色 體 經(jīng) 常 比 適 應(yīng) 性 差 的 基 因 或 染色 體 有 更 多 的 機(jī) 會(huì) 遺 傳 到 下 一 代 。 2021-4-24 5 遺 傳 算 法 是 模 擬 生 物 在 自 然 環(huán) 境 力 的 遺 傳 和 進(jìn) 化 過(guò) 程 而 形 成 的一 種 自 適 應(yīng) 全 局 優(yōu) 化 概 率 搜 索 算 法 。它 最 早 由 美 國(guó) 密 執(zhí) 安 大 學(xué) 的 Holland教 授 提 出 ， 起 源 于 60年 代 對(duì)自 然 和 人 工 自 適 應(yīng) 系 統(tǒng) 的 研 究 。70年 代 De Jong基 于 遺 傳 算 法 的 思 想 在 計(jì) 算 機(jī)

5、 上 進(jìn) 行 了 大 量 的 純數(shù) 值 函 數(shù) 優(yōu) 化 計(jì) 算 實(shí) 驗(yàn) 。在 系 列 研 究 工 作 的 基 礎(chǔ) 上 ， 80年 代 由 Goldberg進(jìn) 行 歸 納 總 結(jié) ，形 成 了 遺 傳 算 法 的 基 本 框 架 。 2021-4-24 6 一 、 遺 傳 算 法 概 要 UR RX X. )(maxts f式 中 ， 為 決 策 變 量 ， f(X)為 目 標(biāo) 函 數(shù) ， 后 兩 個(gè)式 子 為 約 束 條 件 ， U是 基 本 空 間 ， R是 U的 一 個(gè) 子 集 。 Tnxxx 21X對(duì) 于 一 個(gè) 求 函 數(shù) 最 大 值 的 優(yōu) 化 問(wèn) 題 (求 函 數(shù) 最 小 值 也

6、類 同 )， 般 可 描 述 為 下 述 數(shù) 學(xué) 規(guī) 劃 模 型 ：滿 足 約 束 條 件 的 解 X稱 為 可 行 解 ， 集 合 R表 示 由 所 有 滿 足 約 束 條件 的 解 所 組 成 的 一 個(gè) 集 合 ， 叫 做 可 行 解 集 合 。 它 們 之 間 的 關(guān) 系如 圖 所 示 。 2021-4-24 7 U基 本 空 間R可 行 解 集 合X可 行 解 2021-4-24 8 對(duì) 于 上 述 最 優(yōu) 化 問(wèn) 題 ， 目 標(biāo) 函 數(shù) 和 約 束 條 件 種 類 繁 多 ， 有 的 是 線性 的 ， 有 的 是 非 線 性 的 ； 有 的 是 連 續(xù) 的 ， 有 的 是 離 散

7、的 ； 有 的 是單 峰 值 的 ， 有 的 是 多 峰 值 的 。隨 著 研 究 的 深 入 ， 人 們 逐 漸 認(rèn) 識(shí) 到 在 很 多 復(fù) 雜 情 況 下 要 想 完 全精 確 地 求 出 其 最 優(yōu) 解 既 不 可 能 ， 也 不 現(xiàn) 實(shí) ， 因 而 求 出 其 近 似 最優(yōu) 解 或 滿 意 解 是 人 們 的 主 要 著 眼 點(diǎn) 之 。 2021-4-24 9 求 最 優(yōu) 解 或 近 似 最 優(yōu) 解 的 方 法(1)枚 舉 法 。枚 舉 出 可 行 解 集 合 內(nèi) 的 所 有 可 行 解 ， 以 求 出 精 確 最 優(yōu) 解 。 對(duì) 于 連續(xù) 函 數(shù) ， 該 方 法 要 求 先 對(duì) 其

8、進(jìn) 行 離 散 化 處 理 ， 這 樣 就 有 可 能 產(chǎn) 生離 散 誤 差 而 永 遠(yuǎn) 達(dá) 不 到 最 優(yōu) 解 。 另 外 ， 當(dāng) 枚 舉 空 間 比 較 大 時(shí) ， 該方 法 的 求 解 效 率 比 較 低 ， 有 時(shí) 甚 至 在 目 前 最 先 進(jìn) 的 計(jì) 算 工 具 上 都無(wú) 法 求 解 。(2)啟 發(fā) 式 算 法 。尋 求 一 種 能 產(chǎn) 生 可 行 解 的 啟 發(fā) 式 規(guī) 則 ， 以 找 到 一 個(gè) 最 優(yōu) 解 或 近 似最 優(yōu) 解 。 該 方 法 的 求 解 效 率 雖 然 比 較 高 ， 但 對(duì) 每 個(gè) 需 要 求 解 的問(wèn) 題 都 必 須 找 出 其 特 有 的 啟 發(fā) 式

9、規(guī) 則 ， 這 個(gè) 啟 發(fā) 式 規(guī) 則 無(wú) 通 用 性 ，不 適 合 于 其 他 問(wèn) 題 。 2021-4-24 10 (3)搜 索 算 法 。 尋 求 一 種 搜 索 算 法 ， 該 算 法 在 可 行 解 集 合 的 一 個(gè)子 集 內(nèi) 進(jìn) 行 搜 索 操 作 ， 以 找 到 問(wèn) 題 的 最 優(yōu) 解 或 近 似 最 優(yōu) 解 。 該 方法 雖 然 保 證 不 了 一 定 能 夠 得 到 問(wèn) 題 的 最 優(yōu) 解 ， 但 若 適 當(dāng) 地 利 用 一些 啟 發(fā) 知 識(shí) ， 就 可 在 近 似 解 的 質(zhì) 量 和 求 解 效 率 上 達(dá) 到 種 較 好 的平 衡 。 而 遺 傳 算 法 為 解 決 這

10、 類 問(wèn) 題 提 供 了 一 個(gè) 有 效 的 途 徑 和 通 用 框 架 ，開(kāi) 創(chuàng) 了 一 種 新 的 全 局 優(yōu) 化 搜 索 算 法 。 2021-4-24 11 遺 傳 算 法 中 ， 將 n維 決 策 向 量 用 n個(gè) 記 號(hào) Xi (nl， 2， ， n)所 組 成 的 符 號(hào) 串 X來(lái) 表 示 ： Tnxxx 21X Tnn xxxXXXX 2121 X把 每 一 個(gè) Xi看 作 一 個(gè) 遺 傳 基 因 ， 它 的 所 有 可 能 取 值 稱 為 等 位 基 因 ，這 樣 ， X就 可 看 做 是 由 n個(gè) 遺 傳 基 因 所 組 成 的 一 個(gè) 染 色 體 。 般 情 況 下 ，

11、染 色 體 的 長(zhǎng) 度 n是 固 定 的 ， 但 對(duì) 一 些 問(wèn) 題 n也 可 以 是變 化 的 。根 據(jù) 不 同 的 情 況 ， 這 里 的 等 位 基 因 可 以 是 一 組 整 數(shù) ， 也 可 以 是某 一 范 圍 內(nèi) 的 實(shí) 數(shù) 值 ， 或 者 是 純 粹 的 一 個(gè) 記 號(hào) 。最 簡(jiǎn) 單 的 等 位 基 因 是 由 0和 l這 兩 個(gè) 整 數(shù) 組 成 的 。 相 應(yīng) 的 染 色 體就 可 表 示 為 一 個(gè) 二 進(jìn) 制 符 號(hào) 串 。 2021-4-24 12 這 種 編 碼 所 形 成 的 排 列 形 式 X是 個(gè) 體 的 基 因 型 ， 與 它 對(duì) 應(yīng) 的 x值 是個(gè) 體 的 表

12、 現(xiàn) 型 。通 常 個(gè) 體 的 表 現(xiàn) 型 和 其 基 因 型 是 一 一 對(duì) 應(yīng) 的 ， 但 有 時(shí) 也 允 許 基 因型 和 表 現(xiàn) 型 是 多 對(duì) 一 的 關(guān) 系 。染 色 休 X也 稱 為 個(gè) 體 X。對(duì) 于 每 一 個(gè) 個(gè) 體 X， 要 按 照 一 定 的 規(guī) 則 確 定 出 其 適 應(yīng) 度 ； 個(gè) 體的 適 應(yīng) 度 與 其 對(duì) 應(yīng) 的 個(gè) 體 表 現(xiàn) 型 X的 目 標(biāo) 函 數(shù) 值 相 關(guān) 聯(lián) ， X越接 近 于 目 標(biāo) 函 數(shù) 的 最 優(yōu) 點(diǎn) ， 其 適 應(yīng) 度 越 大 ； 反 之 ， 其 適 應(yīng) 度 越小 。遺 傳 算 法 中 ， 決 策 變 量 X組 成 了 問(wèn) 題 的 解 空

13、 間 。 對(duì) 問(wèn) 題 最 優(yōu) 解的 搜 索 是 通 過(guò) 對(duì) 染 色 體 X的 搜 索 過(guò) 程 來(lái) 進(jìn) 行 的 ， 從 而 由 所 有 的染 色 體 X就 組 成 了 問(wèn) 題 的 搜 索 空 間 。 2021-4-24 13 生 物 的 進(jìn) 化 是 以 集 團(tuán) 為 主 體 的 。 與 此 相 對(duì) 應(yīng) ， 遺 傳 算 法 的 運(yùn) 算 對(duì)象 是 由 M個(gè) 個(gè) 體 所 組 成 的 集 合 ， 稱 為 群 體 。與 生 物 一 代 一 代 的 自 然 進(jìn) 化 過(guò) 程 相 類 似 ， 遺 傳 算 法 的 運(yùn) 算 過(guò) 程 也是 一 個(gè) 反 復(fù) 迭 代 的 過(guò) 程 ， 第 t代 群 體 記 做 P(t)， 經(jīng)

14、 過(guò) 一 代 遺 傳 和 進(jìn)化 后 ， 得 到 第 t+l代 群 體 ， 它 們 也 是 由 多 個(gè) 個(gè) 體 組 成 的 集 合 ， 記 做P(t+1)。這 個(gè) 群 體 不 斷 地 經(jīng) 過(guò) 遺 傳 和 進(jìn) 化 操 作 ， 并 且 每 次 都 按 照 優(yōu) 勝 劣汰 的 規(guī) 則 將 適 應(yīng) 度 較 高 的 個(gè) 體 更 多 地 遺 傳 到 下 一 代 ， 這 樣 最 終在 群 體 中 將 會(huì) 得 到 一 個(gè) 優(yōu) 良 的 個(gè) 體 X， 它 所 對(duì) 應(yīng) 的 表 現(xiàn) 型 X將 達(dá)到 或 接 近 于 問(wèn) 題 的 最 優(yōu) 解 X*。生 物 的 進(jìn) 化 過(guò) 程 主 要 是 通 過(guò) 染 色 體 之 間 的 交 叉

15、 和 變 異 來(lái) 完 成 的 ，遺 傳 算 法 中 最 優(yōu) 解 的 搜 索 過(guò) 程 也 模 仿 生 物 的 這 個(gè) 進(jìn) 化 過(guò) 程 ， 使 用所 謂 的 遺 傳 算 子 (genetic operators)作 用 于 群 體 P(t)中 ， 進(jìn) 行 下 述 遺傳 操 作 ， 從 而 得 到 新 一 代 群 體 P(t+1)。 2021-4-24 14 選 擇 (selection)： 根 據(jù) 各 個(gè) 個(gè) 體 的 適 應(yīng) 度 ， 按 照 一 定 的 規(guī) 則 或 方 法 ，從 第 t代 群 體 P(t)中 選 擇 出 一 些 優(yōu) 良 的 個(gè) 體 遺 傳 到 下 一 代 群 體 P(t+1)中 。

16、交 叉 (crossover)： 將 群 體 P(t)內(nèi) 的 各 個(gè) 個(gè) 體 隨 機(jī) 搭 配 成 對(duì) ， 對(duì) 每 對(duì)個(gè) 體 ， 以 某 個(gè) 概 率 (稱 為 交 叉 概 率 ， crossover rate)交 換 它 們 之 間的 部 分 染 色 體 。變 異 (mutation)： 對(duì) 群 體 P(t)中 的 每 一 個(gè) 個(gè) 體 ， 以 某 一 概 率 (稱 為 變異 概 率 ， mutation rate)改 變 某 一 個(gè) 或 某 一 些 基 因 座 上 的 基 因 值 為其 他 的 等 位 基 因 。 2021-4-24 15 二 、 遺 傳 算 法 的 運(yùn) 算 過(guò) 程 使 用 上

17、述 三 種 遺 傳 算 子 (選 擇 算 子 、 交 叉 算 子 、 變 異 算 子 )的 遺傳 算 法 的 主 要 運(yùn) 算 過(guò) 程 如 下 所 述 ：步 驟 一 ： 初 始 化 。設(shè) 置 進(jìn) 化 代 數(shù) 計(jì) 數(shù) 器 t0； 設(shè) 置 最 大 進(jìn) 化 代 數(shù) T； 隨 機(jī) 生 成 M個(gè)個(gè) 體 作 為 初 始 群 體 P(0)。步 驟 二 ： 個(gè) 體 評(píng) 價(jià) 。計(jì) 算 群 體 P(t)中 各 個(gè) 個(gè) 體 的 適 應(yīng) 度 。步 驟 三 ： 選 擇 運(yùn) 算 。將 選 擇 算 子 作 用 于 群 體 。 2021-4-24 16 步 驟 四 ： 交 叉 運(yùn) 算 。將 交 叉 算 子 作 用 于 群 體

18、。步 驟 五 ： 變 異 運(yùn) 算 。將 變 異 算 于 作 用 于 群 體 。群 體 P(t)經(jīng) 過(guò) 選 擇 、 交 叉 、 變 異 運(yùn) 算 之 后 得 到 下 一 代 群 體 P(t+1)。步 驟 六 ： 終 止 條 件 判 斷 。若 tT， 則 ： tt+1， 轉(zhuǎn) 到 步 驟 二 。若 t T， 則 以 進(jìn) 化 過(guò) 程 中 所 得 到 的 具 有 最 大 適 應(yīng) 度 的 個(gè) 體 作 為 最優(yōu) 解 輸 出 ， 終 止 計(jì) 算 。 2021-4-24 17 三 、 遺 傳 算 法 的 特 點(diǎn) (1)遺 傳 算 法 以 決 策 變 量 的 編 碼 作 為 運(yùn) 算 對(duì) 象 。傳 統(tǒng) 的 優(yōu) 化 算

19、 法 往 往 直 接 利 用 決 策 變 量 的 實(shí) 際 值 本 身 來(lái) 進(jìn) 行 優(yōu)化 計(jì) 算 ， 但 遺 傳 算 法 不 是 直 接 以 決 策 變 量 的 值 ， 而 是 以 決 策 變量 的 某 種 形 式 的 編 碼 為 運(yùn) 算 對(duì) 象 。這 種 對(duì) 決 策 變 量 的 編 碼 處 理 方 式 ， 使 得 我 們 在 優(yōu) 化 計(jì) 算 過(guò) 程 中可 以 借 鑒 生 物 學(xué) 中 染 色 體 和 基 因 等 概 念 ， 可 以 模 仿 自 然 界 中 生物 的 遺 傳 和 進(jìn) 化 等 機(jī) 理 ， 也 使 得 我 們 可 以 方 便 地 應(yīng) 用 遺 傳 操 作算 子 。 特 別 是 對(duì) 一 些

20、 無(wú) 數(shù) 值 概 念 或 很 難 有 數(shù) 值 概 念 ， 而 只 有 代碼 概 念 的 優(yōu) 化 問(wèn) 題 ， 編 碼 處 理 方 式 更 顯 示 出 了 其 獨(dú) 持 的 優(yōu) 越 性 。 2021-4-24 18 (2)遺 傳 算 法 直 接 以 目 標(biāo) 函 數(shù) 值 作 為 搜 索 信 息 。傳 統(tǒng) 的 優(yōu) 化 算 法 不 僅 需 要 利 用 目 標(biāo) 函 數(shù) 值 ， 而 且 往 往 需 要 目 標(biāo)函 數(shù) 的 導(dǎo) 數(shù) 值 等 其 他 一 些 輔 助 信 息 才 能 確 定 搜 索 方 向 。而 遺 傳 算 法 僅 使 用 由 目 標(biāo) 函 數(shù) 值 變 換 來(lái) 的 適 應(yīng) 度 函 數(shù) 值 ， 就 可 確

21、定 進(jìn) 一 步 的 搜 索 方 向 和 搜 索 范 圍 ， 無(wú) 需 目 標(biāo) 函 數(shù) 的 導(dǎo) 數(shù) 值 等 其 他一 些 輔 助 信 息 。這 個(gè) 特 性 對(duì) 很 多 目 標(biāo) 函 數(shù) 無(wú) 法 或 是 很 難 求 導(dǎo) 數(shù) 的 函 數(shù) ， 或 導(dǎo) 數(shù)不 存 在 的 函 數(shù) 的 優(yōu) 化 問(wèn) 題 ， 以 及 組 合 優(yōu) 化 問(wèn) 題 等 ， 應(yīng) 用 遺 傳 算法 時(shí) 就 顯 得 比 較 方 便 ， 因 為 它 避 開(kāi) 了 函 數(shù) 求 導(dǎo) 這 個(gè) 障 礙 。再 者 ， 直 接 利 用 目 標(biāo) 函 數(shù) 值 或 個(gè) 體 適 應(yīng) 度 ， 也 可 使 得 我 們 可 以把 搜 索 范 圍 集 中 到 適 應(yīng) 度 較

22、高 的 部 分 搜 索 空 間 中 ， 從 而 提 高 了搜 索 效 率 。 2021-4-24 19 (3)遺 傳 算 法 同 時(shí) 使 用 多 個(gè) 搜 索 點(diǎn) 的 搜 索 信 息 。傳 統(tǒng) 的 優(yōu) 化 算 法 往 往 是 從 解 空 間 個(gè) 的 一 個(gè) 初 始 點(diǎn) 開(kāi) 始 最 優(yōu) 解 的 這代 搜 索 過(guò) 程 ， 單 個(gè) 搜 索 點(diǎn) 所 提 供 的 搜 索 信 息 畢 竟 不 多 ， 所 以 搜 索效 率 不 高 ， 有 時(shí) 其 至 使 搜 索 過(guò) 程 陷 入 局 部 最 優(yōu) 解 而 停 滯 不 前 。遺 傳 算 法 從 很 多 個(gè) 體 所 組 成 的 一 個(gè) 初 始 群 體 開(kāi) 始 最 優(yōu)

23、 解 的 搜 索 過(guò)程 ， 而 不 是 從 個(gè) 單 一 的 個(gè) 體 開(kāi) 始 搜 索 。 對(duì) 這 個(gè) 群 體 所 進(jìn) 行 的 選擇 、 交 叉 、 變 異 等 運(yùn) 算 ， 產(chǎn) 生 出 的 乃 是 新 一 代 的 群 體 ， 在 這 之 中包 括 了 很 多 群 體 信 息 。這 些 信 息 可 以 避 免 搜 索 一 些 不 必 搜 索 的 點(diǎn) ， 所 以 實(shí) 際 上 相 當(dāng) 于搜 索 了 更 多 的 點(diǎn) ， 這 是 遺 傳 算 法 所 特 有 的 一 種 隱 含 并 行 性 。 2021-4-24 20 (4)遺 傳 算 法 使 用 概 率 搜 索 技 術(shù) 。傳 統(tǒng) 的 優(yōu) 化 算 法 往 往

24、 使 用 的 是 確 定 性 的 搜 索 方 法 ， 一 個(gè) 搜 索 點(diǎn)到 另 一 個(gè) 搜 索 點(diǎn) 的 轉(zhuǎn) 移 有 確 定 的 轉(zhuǎn) 移 方 法 和 轉(zhuǎn) 移 關(guān) 系 ， 這 種 確定 性 往 往 也 有 可 能 使 得 搜 索 永 遠(yuǎn) 達(dá) 不 到 最 優(yōu) 點(diǎn) ， 因 而 也 限 制 了算 法 的 應(yīng) 用 范 圍 。遺 傳 算 法 屬 于 一 種 自 適 應(yīng) 概 率 搜 索 技 術(shù) ， 其 選 擇 、 交 叉 、 變 異等 運(yùn) 算 都 是 以 一 種 概 率 的 方 式 來(lái) 進(jìn) 行 的 ， 從 而 增 加 了 其 搜 索 過(guò)程 的 靈 活 性 。雖 然 這 種 概 率 特 性 也 會(huì) 使 群 體

25、中 產(chǎn) 生 些 適 應(yīng) 度 不 高 的 個(gè) 體 ， 但隨 著 進(jìn) 化 過(guò) 程 的 進(jìn) 行 ， 新 的 群 體 中 總 會(huì) 更 多 地 產(chǎn) 生 出 許 多 優(yōu) 良 的個(gè) 體 ， 實(shí) 踐 和 理 論 都 已 證 明 了 在 定 條 件 下 遺 傳 算 法 總 是 以 概 率1收 斂 于 問(wèn) 題 的 最 優(yōu) 解 。當(dāng) 然 ， 交 叉 概 率 和 變 異 概 率 等 參 數(shù) 也 會(huì) 影 響 算 法 的 搜 索 效 果 和搜 索 效 率 ， 所 以 如 何 選 擇 遺 傳 算 法 的 參 數(shù) 在 其 應(yīng) 用 中 是 一 個(gè) 比 較 重 要 的 問(wèn) 題 。 而 另 一 方 面 ， 與 其 他 一 些 算

26、法 相 比 遺 傳 算 法 的魯 棒 性 又 會(huì) 使 得 參 數(shù) 對(duì) 其 搜 索 效 果 的 影 響 會(huì) 盡 可 能 地 低 。 2021-4-24 21 四 、 遺 傳 算 法 的 發(fā) 展遺 傳 算 法 起 源 于 對(duì) 生 物 系 統(tǒng) 所 進(jìn) 行 的 計(jì) 算 機(jī) 模 擬 研 究 。早 在 上 世 紀(jì) 40年 代 ， 就 有 學(xué) 者 開(kāi) 始 研 究 如 何 利 用 計(jì) 算 機(jī) 進(jìn) 行 生 物模 擬 的 技 術(shù) ， 他 們 從 生 物 學(xué) 的 角 度 進(jìn) 行 了 生 物 的 進(jìn) 化 過(guò) 程 模 擬 、遺 傳 過(guò) 程 模 擬 等 研 究 工 作 。進(jìn) 入 60年 代 后 ， 美 國(guó) 密 執(zhí) 安 大

27、 學(xué) 的 Ho11and教 授 及 其 學(xué) 生 們 受 到這 種 生 物 模 擬 技 術(shù) 的 啟 發(fā) ， 創(chuàng) 造 出 了 一 種 基 于 生 物 遺 傳 和 進(jìn) 化機(jī) 制 的 適 合 于 復(fù) 雜 系 統(tǒng) 優(yōu) 化 計(jì) 算 的 自 適 應(yīng) 概 率 優(yōu) 化 技 術(shù) 遺傳 算 法 。下 面 是 在 遺 傳 算 法 的 發(fā) 展 進(jìn) 程 中 一 些 關(guān) 鍵 人 物 所 做 出 的 一 些 主要 貢 獻(xiàn) 。 2021-4-24 22 1、 J H Holland60年 代 ， Ho11and提 出 在 研 究 和 設(shè) 計(jì) 人 工 自 適 應(yīng) 系 統(tǒng) 時(shí) ， 可 以 借鑒 生 物 遺 傳 的 機(jī) 制 ， 以

28、群 體 的 方 法 進(jìn) 行 自 適 應(yīng) 搜 索 ， 并 且 充 分認(rèn) 識(shí) 到 了 交 叉 、 變 異 等 運(yùn) 算 策 略 在 自 適 應(yīng) 系 統(tǒng) 中 的 重 要 性 。70年 代 初 ， Ho11and教 授 提 出 了 遺 傳 算 法 的 基 本 定 理 模 式 定理 (schema Theorem)， 從 而 奠 定 了 遺 傳 算 法 的 理 論 基 礎(chǔ) 。 模 式 定理 揭 示 出 了 群 體 中 的 優(yōu) 良 個(gè) 體 (較 好 的 模 式 )的 樣 本 數(shù) 將 以 指 數(shù) 級(jí)規(guī) 律 增 長(zhǎng) ， 因 而 從 理 論 上 保 證 了 遺 傳 算 法 是 一 個(gè) 可 以 用 來(lái) 尋 求最 優(yōu)

29、 可 行 解 的 優(yōu) 化 過(guò) 程 。 1975年 ， Ho11and出 版 了 第 一 本 系 統(tǒng) 論述 遺 傳 算 法 和 人 工 自 適 應(yīng) 系 統(tǒng) 的 專 著 自 然 系 統(tǒng) 和 人 工 系 統(tǒng) 的自 適 應(yīng) 性 (Adaptation in natural and artificial system) 。80年 代 ， Holland教 授 實(shí) 現(xiàn) 了 第 一 個(gè) 基 于 遺 傳 算 法 的 機(jī) 器 學(xué) 習(xí) 系統(tǒng) 分 類 器 系 統(tǒng) (C1assifier system， 簡(jiǎn) 稱 CS)， 開(kāi) 創(chuàng) 了 基 于 遺傳 算 法 的 機(jī) 器 學(xué) 習(xí) 的 新 概 念 ， 為 分 類 器 系 統(tǒng)

30、 構(gòu) 造 出 了 一 個(gè) 完 整 的 框 架 。 2021-4-24 23 2、 J D Bagley1967年 ， Ho11and的 學(xué) 生 Bagley在 其 博 士 論 文 中 首 次 提 出 “ 遺 傳 算法 ” 一 詞 ， 并 發(fā) 表 了 遺 傳 算 法 應(yīng) 用 方 面 的 第 一 篇 論 文 。 他 發(fā) 展 了復(fù) 制 、 交 叉 、 變 異 、 顯 性 、 倒 位 等 遺 傳 算 子 ， 在 個(gè) 體 編 碼 上 使 用了 雙 倍 體 的 編 碼 方 法 。 這 些 都 與 目 前 遺 傳 算 法 中 所 使 用 的 算 子 和方 法 相 類 似 。 他 還 敏 銳 地 意 識(shí) 到

31、在 遺 傳 算 法 執(zhí) 行 的 不 向 階 段 可 以使 用 不 同 的 選 擇 率 ， 這 將 有 利 于 防 止 遺 傳 算 法 的 早 熟 現(xiàn) 象 ， 從 而創(chuàng) 立 了 自 適 應(yīng) 遺 傳 算 法 的 概 念 。 2021-4-24 24 3、 K A De Jong l975年 ， De Jong在 其 博 士 論 文 中 結(jié) 合 模 式 定 理 進(jìn) 行 了 大 量 的 純數(shù) 值 函 數(shù) 優(yōu) 化 計(jì) 算 實(shí) 驗(yàn) ， 樹(shù) 立 了 遺 傳 算 法 的 工 作 框 架 ， 得 到 了一 些 重 要 且 具 有 指 導(dǎo) 意 義 的 結(jié) 論 。 例 如 ， 對(duì) 于 規(guī) 模 在 50100的群 體

32、 ， 經(jīng) 過(guò) l020代 的 進(jìn) 化 ， 遺 傳 算 法 都 能 以 很 高 的 概 率 找 到 最優(yōu) 或 近 似 最 優(yōu) 解 。 他 推 薦 了 在 大 多 數(shù) 優(yōu) 化 問(wèn) 題 中 都 較 適 用 的 遺傳 算 法 的 參 數(shù) ， 還 建 立 了 著 名 的 De Jong五 函 數(shù) 測(cè) 試 平 臺(tái) ， 定 義了 評(píng) 價(jià) 遺 傳 算 法 性 能 的 在 線 指 標(biāo) 和 離 線 指 標(biāo) 。 4、 D J De Jong1989年 ， De Jong出 版 了 專 著 搜 索 、 優(yōu) 化 和 機(jī) 器 學(xué) 習(xí) 中 的 遺 傳沖 法 (Genetic Algorithms in Search， Op

33、timization and Machine Learning) 。 該 書 系 統(tǒng) 總 結(jié) 了 遺 傳 算 法 的 主 要 研 究 成 果 ，全 面 而 完 整 地 論 述 了 遺 傳 算 法 的 基 本 原 理 及 其 應(yīng) 用 。 可 以 說(shuō) 這 本 書 奠 定 了 現(xiàn) 代 遺 傳 算 法 的 科 學(xué) 基 礎(chǔ) ， 為 眾 多 研 究 和 發(fā) 展 遺 傳算 法 的 學(xué) 者 所 矚 目 。 2021-4-24 25 5、 L Davis1991年 ， Davis編 輯 出 版 了 遺 傳 算 法 手 冊(cè) (Handbook of Genetic Algorithms) 書 ， 書 中 包 括

34、了 遺 傳 算 法 在 科 學(xué) 計(jì) 算 、 工 程 技 術(shù)和 社 會(huì) 經(jīng) 濟(jì) 中 的 大 量 應(yīng) 用 實(shí) 例 。 這 本 書 為 推 廣 和 普 及 遺 傳 算 法 的應(yīng) 用 起 到 了 重 要 的 指 導(dǎo) 作 用 。6 J R Koza1992年 ， Koza將 遺 傳 算 法 應(yīng) 用 于 計(jì) 算 機(jī) 程 序 的 優(yōu) 化 設(shè) 計(jì) 及 自 動(dòng) 生成 ， 提 出 了 遺 傳 編 程 (Genetic Programming， 簡(jiǎn) 稱 GP)的 概 念 。 他將 一 段 LISP語(yǔ) 言 程 序 作 為 個(gè) 體 的 基 因 型 ， 把 問(wèn) 題 的 解 編 碼 作 為 一棵 樹(shù) ， 基 于 遺 傳 和

35、 進(jìn) 化 的 概 念 ， 對(duì) 由 樹(shù) 組 成 的 群 體 進(jìn) 行 遺 傳 運(yùn) 算 ，最 終 自 動(dòng) 生 成 性 能 較 好 的 計(jì) 算 機(jī) 程 序 。 Koza成 功 地 把 他 提 出 的 遺傳 編 程 的 方 法 應(yīng) 用 于 人 工 智 能 、 機(jī) 器 學(xué) 習(xí) 、 符 號(hào) 處 理 等 方 面 。 2021-4-24 26 五 、 遺 傳 算 法 的 應(yīng) 用 (1)函 數(shù) 優(yōu) 化 。函 數(shù) 優(yōu) 化 是 遺 傳 算 法 的 經(jīng) 典 應(yīng) 用 領(lǐng) 域 ， 也 是 對(duì) 遺 傳 算 法 進(jìn) 行 性 能評(píng) 價(jià) 的 常 用 算 例 。很 多 人 構(gòu) 造 出 了 各 種 各 樣 的 復(fù) 雜 形 式 的 測(cè)

36、試 函 數(shù) ， 有 連 續(xù) 函 數(shù) 也有 離 散 函 數(shù) ， 有 凸 函 數(shù) 也 有 凹 函 數(shù) ， 有 低 維 函 數(shù) 也 有 高 維 函 數(shù) ，有 確 定 函 數(shù) 也 有 隨 機(jī) 函 數(shù) ， 有 單 峰 值 函 數(shù) 也 有 多 峰 值 函 數(shù) 等 。用 這 些 幾 何 特 性 各 具 特 色 的 函 數(shù) 來(lái) 評(píng) 價(jià) 遺 傳 算 法 的 性 能 ， 更 能 反映 算 法 的 本 質(zhì) 效 果 。而 對(duì) 于 一 些 非 線 性 、 多 模 型 、 多 目 標(biāo) 的 函 數(shù) 優(yōu) 化 問(wèn) 題 ， 用 其 他 優(yōu)化 方 法 較 難 求 解 ， 而 遺 傳 算 法 卻 可 以 方 便 地 得 到 較 好

37、的 結(jié) 果 。 2021-4-24 27 (2)組 合 優(yōu) 化 。隨 著 問(wèn) 題 規(guī) 模 的 增 大 ， 組 合 優(yōu) 化 問(wèn) 題 的 搜 索 空 間 也 急 劇 擴(kuò) 大 ， 有時(shí) 在 目 前 的 計(jì) 算 機(jī) 上 用 枚 舉 法 很 難 或 甚 至 不 可 能 求 出 其 精 確 最 優(yōu)解 。 對(duì) 這 類 復(fù) 雜 問(wèn) 題 ， 人 們 已 意 識(shí) 到 應(yīng) 把 主 要 精 力 放 在 尋 求 其 滿意 解 上 ， 而 遺 傳 算 法 是 尋 求 這 種 滿 意 解 的 最 佳 工 具 之 一 。實(shí) 踐 證 明 ， 遺 傳 算 法 對(duì) 于 組 合 優(yōu) 化 中 的 NP完 全 問(wèn) 題 非 常 有 效 。

38、例 如 ， 遺 傳 算 法 已 經(jīng) 在 求 解 旅 行 商 問(wèn) 題 、 背 包 問(wèn) 題 、 裝 箱 問(wèn) 題 、圖 形 劃 分 問(wèn) 題 等 方 面 得 到 成 功 的 應(yīng) 用 。 2021-4-24 28 (3)生 產(chǎn) 調(diào) 度 問(wèn) 題 。生 產(chǎn) 調(diào) 度 問(wèn) 題 在 很 多 情 況 下 所 建 立 起 來(lái) 的 數(shù) 學(xué) 模 型 難 以 精 確 求 解 ，即 使 經(jīng) 過(guò) 一 些 簡(jiǎn) 化 之 后 可 以 進(jìn) 行 求 解 ， 也 會(huì) 因 簡(jiǎn) 化 得 太 多 而 使 得求 解 結(jié) 果 與 實(shí) 際 相 差 甚 遠(yuǎn) 。 目 前 在 現(xiàn) 實(shí) 生 產(chǎn) 中 也 主 要 是 靠 一 些 經(jīng)驗(yàn) 來(lái) 進(jìn) 行 調(diào) 度 ?，F(xiàn)

39、在 遺 傳 算 法 已 成 為 解 決 復(fù) 雜 調(diào) 度 問(wèn) 題 的 有 效 工 具 ， 在 單 件 生產(chǎn) 車 間 調(diào) 度 、 流 水 線 生 產(chǎn) 車 間 調(diào) 度 、 生 產(chǎn) 規(guī) 劃 、 任 務(wù) 分 配 等 方面 遺 傳 算 法 都 得 到 了 有 效 的 應(yīng) 用 。 2021-4-24 29 (4)自 動(dòng) 控 制 。在 自 動(dòng) 控 制 領(lǐng) 域 中 有 很 多 與 優(yōu) 化 相 關(guān) 的 問(wèn) 題 需 要 求 解 ， 遺 傳 算 法已 在 其 中 得 到 了 初 步 的 應(yīng) 用 ， 并 顯 示 出 了 良 好 的 效 果 。例 如 用 遺 傳 算 法 進(jìn) 行 航 空 控 制 系 統(tǒng) 的 優(yōu) 化 、 使

40、 用 遺 傳 算 法 設(shè) 計(jì) 空間 交 會(huì) 控 制 器 、 基 于 遺 傳 算 法 的 模 糊 控 制 器 的 優(yōu) 化 設(shè) 計(jì) 、 基 于 遺傳 算 法 的 參 數(shù) 辨 識(shí) 、 基 于 遺 傳 算 法 的 模 糊 控 制 規(guī) 則 的 學(xué) 習(xí) 、 利 用遺 傳 算 法 進(jìn) 行 人 工 種 經(jīng) 網(wǎng) 絡(luò) 的 結(jié) 構(gòu) 優(yōu) 化 設(shè) 計(jì) 和 權(quán) 值 學(xué) 習(xí) 等 ， 都 顯示 出 了 遺 傳 算 法 在 這 些 領(lǐng) 域 中 應(yīng) 用 的 可 能 性 。 2021-4-24 30 (5)機(jī) 器 人 學(xué) 。機(jī) 器 人 是 一 類 復(fù) 雜 的 難 以 精 確 建 模 的 人 工 系 統(tǒng) ， 而 遺 傳 算 法 的

41、起源 就 來(lái) 自 于 對(duì) 人 工 自 適 應(yīng) 系 統(tǒng) 的 研 究 ， 所 以 機(jī) 器 人 學(xué) 理 所 當(dāng) 然 地成 為 遺 傳 算 法 的 一 個(gè) 重 要 應(yīng) 用 領(lǐng) 域 。例 如 ， 遺 傳 算 法 已 經(jīng) 在 移 動(dòng) 機(jī) 器 人 路 徑 規(guī) 劃 、 關(guān) 節(jié) 機(jī) 器 人 運(yùn) 動(dòng)軌 跡 規(guī) 劃 、 機(jī) 器 人 逆 運(yùn) 動(dòng) 學(xué) 求 解 、 細(xì) 胞 機(jī) 器 人 的 結(jié) 構(gòu) 優(yōu) 化 和 行為 協(xié) 調(diào) 等 方 面 得 到 研 究 和 應(yīng) 用 。 2021-4-24 31 (6)圖 像 處 理 。圖 像 處 理 是 計(jì) 算 機(jī) 視 覺(jué) 中 的 一 個(gè) 重 要 研 究 領(lǐng) 域 。 在 圖 像 處 理過(guò) 程

42、 中 ， 如 掃 描 、 持 征 提 取 、 圖 像 分 割 等 不 可 避 免 地 會(huì) 存 在一 些 誤 差 ， 這 些 誤 差 會(huì) 影 響 圖 像 處 理 的 效 果 。 如 何 使 這 些 誤差 最 小 是 使 機(jī) 器 視 覺(jué) 達(dá) 到 實(shí) 用 化 的 重 要 要 求 。遺 傳 算 法 在 這 些 圖 像 處 理 中 的 優(yōu) 化 計(jì) 算 方 面 找 到 了 用 武 之 地 。目 前 已 在 模 式 識(shí) 別 、 圖 像 恢 復(fù) 、 圖 像 邊 緣 特 征 提 取 等 方 面 得 到了 應(yīng) 用 。 2021-4-24 32 人 工 生 命 與 遺 傳 算 法 有 著 密 切 的 關(guān) 系 ， 基

43、 于 遺 傳 算 法 的 進(jìn) 化 模 型是 研 究 人 工 生 命 現(xiàn) 象 的 重 要 基 礎(chǔ) 理 論 。 雖 然 人 工 生 命 的 研 究 尚 處于 啟 蒙 階 段 ， 但 遺 傳 算 法 已 在 其 進(jìn) 化 模 型 、 學(xué) 習(xí) 模 型 、 行 為 模 型 、自 組 織 模 型 等 方 面 顯 示 出 了 初 步 的 應(yīng) 用 能 力 ， 并 且 必 將 得 到 更 為深 入 的 應(yīng) 用 和 發(fā) 展 。 人 工 生 命 與 遺 傳 算 法 相 輔 相 成 ， 遺 傳 算 法 為人 工 生 命 的 研 究 提 供 了 一 個(gè) 有 效 的 工 具 ， 人 工 生 命 的 研 究 也 必 將促 進(jìn)

44、 遺 傳 算 法 的 進(jìn) 一 步 發(fā) 展 。 (7)人 工 生 命 。人 工 生 命 是 用 計(jì) 算 機(jī) 、 機(jī) 械 等 人 工 媒 體 模 擬 或 構(gòu) 造 出 的 具 有 自然 生 物 系 統(tǒng) 特 有 行 為 的 人 造 系 統(tǒng) 。 自 織 織 能 力 和 自 學(xué) 習(xí) 能 力 是人 工 生 命 的 兩 大 主 要 特 征 。 2021-4-24 33 (8)遺 傳 編 程 。Koza發(fā) 展 了 遺 傳 編 程 的 概 念 ， 他 使 用 了 以 LISP語(yǔ) 言 所 表 示 的 編碼 方 法 ， 基 于 對(duì) 一 種 樹(shù) 型 結(jié) 構(gòu) 所 進(jìn) 行 的 遺 傳 操 作 來(lái) 自 動(dòng) 生 成 計(jì)算 機(jī)

45、程 序 。 雖 然 遺 傳 編 程 的 理 論 尚 未 成 熟 ， 應(yīng) 用 也 有 一 些 限 制 ，但 它 已 成 功 地 應(yīng) 用 于 人 工 智 能 、 機(jī) 器 學(xué) 習(xí) 等 領(lǐng) 域 。 2021-4-24 34 (9)機(jī) 器 學(xué) 習(xí) 。學(xué) 習(xí) 能 力 是 高 級(jí) 自 適 應(yīng) 系 統(tǒng) 所 應(yīng) 具 備 的 能 力 之 一 。 基 于 遺 傳 算 法的 機(jī) 器 學(xué) 習(xí) ， 特 別 是 分 類 器 系 統(tǒng) ， 在 很 多 領(lǐng) 域 中 都 得 到 了 應(yīng) 用 。例 如 ， 遺 傳 算 法 被 用 于 學(xué) 習(xí) 模 糊 控 制 規(guī) 則 ， 利 用 遺 傳 算 法 來(lái) 學(xué)習(xí) 隸 屬 度 函 數(shù) ， 從 而

46、 更 好 地 改 進(jìn) 了 模 糊 系 統(tǒng) 的 性 能 ；基 于 遺 傳 算 法 的 機(jī) 器 學(xué) 習(xí) 可 用 來(lái) 調(diào) 整 人 工 神 經(jīng) 網(wǎng) 絡(luò) 的 連 接 權(quán) ，也 可 用 于 人 工 神 經(jīng) 網(wǎng) 絡(luò) 的 網(wǎng) 絡(luò) 結(jié) 構(gòu) 優(yōu) 化 設(shè) 計(jì) ；分 類 器 系 統(tǒng) 也 在 學(xué) 習(xí) 式 多 機(jī) 器 人 路 徑 規(guī) 劃 系 統(tǒng) 中 得 到 了 成 功 的 應(yīng)用 。 2021-4-24 35 3.2 基 本 遺 傳 算 法 2021-4-24 36 一 、 基 本 遺 傳 算 法 的 構(gòu) 成 要 素 基 于 對(duì) 自 然 界 中 生 物 遺 傳 與 進(jìn) 化 機(jī) 理 的 模 仿 ， 針 對(duì) 不 向 的 問(wèn) 題

47、 ，很 多 學(xué) 者 設(shè) 計(jì) 了 許 多 不 同 的 編 碼 方 法 來(lái) 表 示 問(wèn) 題 的 可 行 解 ， 開(kāi)發(fā) 出 了 許 多 種 不 同 的 遺 傳 算 子 來(lái) 模 仿 不 同 環(huán) 境 下 的 生 物 遺 傳 特 。這 樣 ， 由 不 同 的 編 碼 方 法 和 不 同 的 遺 傳 算 子 就 構(gòu) 成 了 各 種 不 同的 遺 傳 算 法 。但 這 些 遺 傳 算 法 都 有 共 同 的 特 點(diǎn) ， 即 通 過(guò) 對(duì) 生 物 遺 傳 和 進(jìn) 化 過(guò)程 中 選 擇 、 交 叉 、 變 異 機(jī) 理 的 模 仿 ， 來(lái) 完 成 對(duì) 問(wèn) 題 最 優(yōu) 解 的 自適 應(yīng) 搜 索 過(guò) 程 。 2021-4

48、-24 37 基 于 這 個(gè) 共 同 特 點(diǎn) ， Goldberg總 結(jié) 出 了 一 種 統(tǒng) 一 的 最 基 本 的 遺 傳算 法 基 本 遺 傳 算 法 (Simple Genetic Algorithms， 簡(jiǎn) 稱 SGA)?；?本 遺 傳 算 法 只 使 用 選 擇 算 子 、 交 叉 算 子 和 變 異 算 子 這 三 種 基 本遺 傳 算 子 ， 其 遺 傳 進(jìn) 化 操 作 過(guò) 程 簡(jiǎn) 單 ， 容 易 理 解 ， 是 其 他 一 些 遺傳 算 法 的 雛 形 和 基 礎(chǔ) ， 它 不 僅 給 各 種 遺 傳 算 法 提 供 了 一 個(gè) 基 本 框架 ， 同 時(shí) 也 具 有 一 定 的

49、應(yīng) 用 價(jià) 值 。 2021-4-24 38 1、 染 色 體 編 碼 方 法基 本 遺 傳 算 法 使 用 固 定 長(zhǎng) 度 的 二 進(jìn) 制 符 號(hào) 串 來(lái) 表 示 群 體 中 的 個(gè) 體 ，其 等 位 基 因 是 由 二 值 符 號(hào) 集 0， 1所 組 成 的 。 初 始 群 體 中 各 個(gè) 個(gè)體 的 基 因 值 可 用 均 勻 分 布 的 隨 機(jī) 數(shù) 來(lái) 生 成 ， 如 ：X 100111001000101101就 可 表 示 一 個(gè) 個(gè) 體 ， 該 個(gè) 體 的 染 色 體 長(zhǎng) 度 是 n 18。 2021-4-24 39 2、 個(gè) 體 適 應(yīng) 度 評(píng) 價(jià)基 本 遺 傳 算 法 按 與 個(gè)

50、 體 適 應(yīng) 度 成 正 比 的 概 率 來(lái) 決 定 當(dāng) 前 群 體 中每 個(gè) 個(gè) 體 遺 傳 到 下 一 代 群 體 中 的 機(jī) 會(huì) 多 少 。為 正 確 計(jì) 算 這 個(gè) 概 率 ， 這 里 要 求 所 有 個(gè) 體 的 適 應(yīng) 度 必 須 為 正 數(shù) 或零 。這 樣 ， 根 據(jù) 不 同 種 類 的 問(wèn) 題 ， 必 須 預(yù) 先 確 定 好 由 目 標(biāo) 函 數(shù) 值 到 個(gè)體 適 應(yīng) 度 之 間 的 轉(zhuǎn) 換 規(guī) 則 ， 特 別 是 要 領(lǐng) 先 確 定 好 當(dāng) 目 標(biāo) 函 數(shù) 值 為負(fù) 數(shù) 時(shí) 的 處 理 方 法 。 2021-4-24 40 3、 遺 傳 算 子選 擇 運(yùn) 算 使 用 比 例 選

51、則 算 子 ；交 叉 運(yùn) 算 使 用 單 點(diǎn) 交 叉 算 子 ；變 異 運(yùn) 算 使 用 基 本 位 變 異 算 子 或 均 勻 變 異 算 子 。 2021-4-24 41 4、 基 本 遺 傳 算 法 的 運(yùn) 行 參 數(shù)基 本 遺 傳 算 法 有 下 述 4個(gè) 運(yùn) 行 參 數(shù) 需 要 提 前 設(shè) 定 ：M： 群 體 大 小 ， 即 群 體 中 所 含 個(gè) 體 的 數(shù) 量 ， 一 般 取 為 201000T： 遺 傳 運(yùn) 算 的 終 止 進(jìn) 化 代 數(shù) ， 一 般 取 為 100500Pc： 交 叉 概 率 ， 般 取 為 0.40.99。Pm： 變 異 概 率 ， 一 般 取 為 0.000

52、10.1這 4個(gè) 運(yùn) 行 參 數(shù) 對(duì) 遺 傳 算 法 的 求 解 結(jié) 果 和 求 解 效 率 都 有 一 定 的影 響 ， 但 目 前 尚 無(wú) 合 理 選 擇 它 們 的 理 論 依 據(jù) 。 2021-4-24 42在 遺 傳 算 法 的 實(shí) 際 應(yīng) 用 中 ， 往 往 需 要 經(jīng) 過(guò) 多 次 試 算 后 才 能 確 定出 這 些 參 數(shù) 合 理 的 取 值 大 小 或 取 值 范 圍 。 一 般 來(lái) 說(shuō) ， 選 擇 較 大 數(shù) 目 的 初 始 種 群 可 以 同 時(shí) 處 理 更 多 的 解 ，因 而 容 易 找 到 全 局 的 最 優(yōu) 解 ， 其 缺 點(diǎn) 使 增 加 了 每 次 迭 代 所

53、需 要的 時(shí) 間 。交 叉 概 率 的 選 擇 決 定 了 交 叉 操 作 的 頻 率 。 頻 率 越 高 ， 可 以 越 快收 斂 到 最 有 希 望 的 最 優(yōu) 解 區(qū) 域 ； 但 是 太 高 的 頻 率 也 可 能 導(dǎo) 致 收斂 于 一 個(gè) 解 。變 異 概 率 通 常 只 取 較 小 的 數(shù) 值 。 若 選 取 高 的 變 異 率 ， 一 方 面 可以 增 加 樣 本 的 多 樣 性 ， 另 一 方 面 可 能 引 起 不 穩(wěn) 定 。 但 是 若 選 取太 小 的 變 異 概 率 ， 則 可 能 難 于 找 到 全 局 的 最 優(yōu) 解 。 2021-4-24 43 Procedure

54、SGAbegin initialize P(0);t=0;while (tT) dofor i=1 to M doEvaluate fitness of P(t);end for二 、 基 本 遺 傳 算 法 的 偽 代 碼 描 述 2021-4-24 44 for i=1 to M doSelect operation of P(t);end forfor i=1 to M/2 doCrossover operation of P(t);end forfor i=1 to M doMutation operation of P(t);end for 2021-4-24 45 for i=1

55、to M doP(t+1)=P(t);end fort=t+1; end whileend 2021-4-24 46 三 、 基 本 遺 傳 算 法 的 實(shí) 現(xiàn) 1、 個(gè) 體 適 應(yīng) 度 評(píng) 價(jià) 在 遺 傳 算 法 中 ， 以 個(gè) 體 適 應(yīng) 度 的 大 小 來(lái) 確 定 該 個(gè) 體 被 遺 傳 到 下 一代 群 體 中 的 概 率 。 個(gè) 體 的 適 應(yīng) 度 越 大 ， 該 個(gè) 體 被 遺 傳 到 下 一 代 的概 率 也 越 大 ； 反 之 ， 個(gè) 體 的 適 應(yīng) 度 越 小 ， 該 個(gè) 體 被 遺 傳 到 下 一 代的 概 率 也 越 小 ?；?本 遺 傳 算 法 使 用 比 例 選 擇

56、算 子 來(lái) 確 定 群 體 中 各 個(gè) 個(gè) 體 遺 傳 到下 一 代 群 體 中 的 數(shù) 量 。為 正 確 計(jì) 算 不 同 情 況 下 各 個(gè) 個(gè) 體 的 遺 傳 概 率 ， 要 求 所 有 個(gè) 體 的適 應(yīng) 度 必 須 為 正 數(shù) 或 零 ， 不 能 是 負(fù) 數(shù) 。 2021-4-24 47 對(duì) 于 求 目 標(biāo) 函 數(shù) 最 小 值 的 優(yōu) 化 問(wèn) 題 ， 理 論 上 只 需 簡(jiǎn) 單 地 對(duì) 其 增加 一 個(gè) 負(fù) 號(hào) 就 可 將 其 轉(zhuǎn) 化 為 求 目 標(biāo) 函 數(shù) 最 大 值 的 優(yōu) 化 問(wèn) 題 ， 即 ： minf (X) max( f (X)當(dāng) 優(yōu) 化 目 標(biāo) 是 求 函 數(shù) 最 大 值

57、， 并 且 目 標(biāo) 函 數(shù) 總 取 正 值 時(shí) ， 可 以直 接 設(shè) 定 個(gè) 體 的 適 應(yīng) 度 F(x)就 等 于 相 應(yīng) 的 目 標(biāo) 函 數(shù) 值 f (X)， 即 ：F(X) f (X)但 實(shí) 際 優(yōu) 化 問(wèn) 題 中 的 目 標(biāo) 函 數(shù) 值 有 正 也 有 負(fù) ， 優(yōu) 化 目 標(biāo) 有 求 函數(shù) 最 大 值 ， 也 有 求 函 數(shù) 最 小 值 。上 面 兩 式 保 證 不 了 所 有 情 況 下 個(gè) 體 的 適 應(yīng) 度 都 是 非 負(fù) 數(shù) 這 個(gè) 要求 。 所 以 必 須 尋 求 出 一 種 通 用 且 有 效 的 由 目 標(biāo) 函 數(shù) 值 到 個(gè) 體 適應(yīng) 度 之 間 的 轉(zhuǎn) 換 關(guān) 系 ，

58、 由 它 來(lái) 保 證 個(gè) 體 適 應(yīng) 度 總 取 非 負(fù) 值 。 2021-4-24 48 為 滿 足 適 應(yīng) 度 取 非 負(fù) 值 的 要 求 ， 基 本 遺 傳 算 法 一 般 采 用 下 面 兩 種方 法 之 一 將 目 標(biāo) 函 數(shù) 值 f (X)變 換 為 個(gè) 體 的 適 應(yīng) 度 F(x)。 0)(0 0)()()( minminmin CXfif CXfifCXfXF式 中 ， Cmin為 一 個(gè) 適 當(dāng) 地 相 對(duì) 比 較 小 的 數(shù) ， 它 可 以 用 下 面 幾 種 方法 之 一 來(lái) 選 擇 ： 方 法 一 ： 對(duì) 于 求 目 標(biāo) 函 數(shù) 最 大 值 的 優(yōu) 化 問(wèn) 題 ， 變

59、換 方 法 為 ： 預(yù) 先 指 定 的 一 個(gè) 較 小 的 數(shù) 。 進(jìn) 化 到 當(dāng) 前 代 為 止 的 最 小 目 標(biāo) 函 數(shù) 值 。 當(dāng) 前 代 或 最 近 幾 代 群 體 中 的 最 小 目 標(biāo) 函 數(shù) 值 。 2021-4-24 49 方 法 二 ： 對(duì) 于 求 目 標(biāo) 函 數(shù) 最 小 值 的 優(yōu) 化 問(wèn) 題 ， 變 換 方 法 為 ： maxmaxmax )(0 )()()( CXfif CXfifXfCXF式 中 ， Cmax為 一 個(gè) 適 當(dāng) 地 相 對(duì) 比 較 大 的 數(shù) ， 它 可 以 用 下 面 幾 種方 法 之 一 來(lái) 選 擇 ： 預(yù) 先 指 定 的 個(gè) 較 大 的 數(shù) 。

60、 進(jìn) 化 到 當(dāng) 前 代 為 止 的 最 大 目 標(biāo) 函 數(shù) 值 。 前 代 或 最 近 幾 代 群 體 中 的 最 大 目 標(biāo) 函 數(shù) 值 。 2021-4-24 50 2、 比 例 選 擇 算 子選 擇 算 子 或 復(fù) 制 算 子 的 作 用 是 從 當(dāng) 前 代 群 體 中 選 擇 出 一 些 比 較 優(yōu)良 的 個(gè) 體 ， 并 將 其 復(fù) 制 到 下 一 代 群 體 中 。 最 常 用 和 最 基 本 的 選 擇算 子 是 比 例 選 擇 算 子 。比 例 選 擇 實(shí) 際 上 是 一 種 有 退 還 隨 機(jī) 選 擇 ， 也 叫 做 賭 盤 (Roulette wheel)選 擇 ， 因 為

61、 這 種 選 擇 方 式 與 賭 博 中 的 賭 盤 操 作 原 理 頗 為 相似 。所 謂 比 例 選 擇 算 了 ， 是 指 個(gè) 體 被 選 中 并 遺 傳 到 下 一 代 群 體 中 的概 率 與 該 個(gè) 體 的 適 應(yīng) 度 大 小 成 正 比 。 2021-4-24 51 如 圖 所 示 為 一 賭 盤 示 意 圖 。整 個(gè) 賭 盤 被 分 為 大 小 不 同 的 一 些 扇 面 ， 分 別 對(duì) 應(yīng) 著 價(jià) 值 各 不 相 同的 一 些 賭 博 物 品 。 當(dāng) 旋 轉(zhuǎn) 著 的 賭 盤 自 然 停 下 來(lái) 時(shí) ， 其 指 針 所 指 扇面 上 的 物 品 就 歸 賭 博 者 所 有 。雖

62、 然 賭 盤 的 指 針 具 體 停 止 在 哪 一 個(gè) 扇 面 是 無(wú) 法 預(yù) 測(cè) 的 ， 但 指 針 指向 各 個(gè) 扇 面 的 概 率 卻 是 可 以 估 計(jì) 的 ， 它 與 各 個(gè) 扇 面 的 圓 心 角 大 小成 正 比 ： 圓 心 角 越 大 ， 停 在 該 扇 面 的 可 能 性 也 越 大 ； 圓 心 角 越 小 ，停 在 該 扇 面 的 可 能 性 也 越 小 。與 此 類 似 ， 在 遺 傳 算 法 中 ， 整 個(gè) 群 體 被 各 個(gè) 個(gè) 體 所 分 割 ， 各 個(gè)個(gè) 體 的 適 應(yīng) 度 在 全 部 個(gè) 體 的 適 應(yīng) 度 之 和 中 所 占 比 例 也 大 小 不 一 ，這

63、 個(gè) 比 例 值 瓜 分 了 整 個(gè) 賭 盤 盤 面 ， 它 們 也 決 定 了 各 個(gè) 個(gè) 體 被 遺傳 到 下 一 代 群 體 中 的 概 率 。 2021-4-24 52 金 銀 銅鐵1020 30 40 2021-4-24 53 比 例 選 擇 算 子 的 具 體 執(zhí) 行 過(guò) 程 是 ：(1)先 計(jì) 算 出 群 體 中 所 有 個(gè) 體 的 適 應(yīng) 度 的 總 和 。(2)其 次 計(jì) 算 出 每 個(gè) 個(gè) 體 的 相 對(duì) 適 應(yīng) 度 的 大 小 ， 它 即 為 各 個(gè) 個(gè) 體被 遺 傳 到 下 一 代 群 體 中 的 概 率 。(3)最 后 再 使 用 模 擬 賭 盤 操 作 (即 0到

64、1之 間 的 隨 機(jī) 數(shù) )來(lái) 確 定 各 個(gè)個(gè) 體 被 選 中 的 次 數(shù) 。 2021-4-24 54 3、 單 點(diǎn) 交 叉 算 子單 點(diǎn) 交 叉 算 子 是 最 常 用 和 最 基 本 的 交 叉 操 作 算 子 。算 子 的 具 體 執(zhí) 行 過(guò) 程 如 下 ：(1)對(duì) 群 體 中 的 個(gè) 體 進(jìn) 行 兩 兩 隨 機(jī) 配 對(duì) 。若 群 體 的 大 小 為 M， 則 共 有 M/2對(duì) 相 互 配 對(duì) 的 個(gè) 體 組 。 其 中 x表 示 不 大 于 x的 最 大 整 數(shù) 。(2)對(duì) 每 一 對(duì) 相 互 配 對(duì) 的 個(gè) 體 ， 隨 機(jī) 設(shè) 置 某 一 基 因 座 之 后 的 位 置 為交 叉

65、 點(diǎn) 。 若 染 色 體 的 長(zhǎng) 度 為 n， 則 共 有 (n-1)個(gè) 可 能 的 交 叉 點(diǎn) 位 置 。(3)對(duì) 每 一 對(duì) 相 互 配 對(duì) 的 個(gè) 體 ， 依 設(shè) 定 的 交 叉 概 率 pc在 其 交 叉 點(diǎn) 處相 互 交 換 兩 個(gè) 個(gè) 體 的 部 分 染 色 體 ， 從 而 產(chǎn) 生 出 兩 個(gè) 新 的 個(gè) 體 。 2021-4-24 55 單 點(diǎn) 交 叉 示 意 如 下 所 示 ： A： 1 0 1 1 0 1 1 1 0 0 A： 1 0 1 1 0 1 1 1 1 1 B： 0 0 0 1 1 1 0 0 1 1 B； 0 0 0 1 1 1 0 0 0 0 單 點(diǎn) 交 叉交

66、叉 點(diǎn) 2021-4-24 56 4、 基 本 位 變 異 算 子 對(duì) 于 基 本 遺 傳 算 法 中 用 二 進(jìn) 制 編 碼 符 號(hào) 串 所 表 示 的 個(gè) 體 ， 若 需 要進(jìn) 行 變 異 操 作 的 某 一 基 因 座 上 的 原 有 基 因 值 為 0， 則 變 異 操 作 將該 基 因 值 變 為 1； 反 之 ， 若 原 有 基 因 值 為 l， 則 變 異 操 作 將 其 變 為 0。A： 1 0 l 0 1 0 1 0 1 0 A： 1 0 l 0 0 0 1 0 1 0 基 本 位 變 異 變 異 點(diǎn) (1)對(duì) 個(gè) 體 的 每 一 個(gè) 基 因 座 ， 依 變 異 概 率 pm指 定 其 為 變 異 點(diǎn) 。(2)對(duì) 每 一 個(gè) 指 定 的 變 異 點(diǎn) ， 對(duì) 其 基 因 值 做 取 反 運(yùn) 算 或 用 其 它 等位 基 因 值 來(lái) 代 替 ， 從 而 產(chǎn) 生 出 一 個(gè) 新 的 個(gè) 體 。 2021-4-24 57 四 、 基 本 遺 傳 算 法 應(yīng) 用 舉 例1、 遺 傳 算 法 的 應(yīng) 用 步 驟 第 一 步 ： 確 定 決 策 變 量 及 其 各 種 約 束 條