智能決策支持系統(tǒng)和智能技術(shù)的決策支持

《智能決策支持系統(tǒng)和智能技術(shù)的決策支持》由會員分享，可在線閱讀，更多相關(guān)《智能決策支持系統(tǒng)和智能技術(shù)的決策支持（216頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 人 工 智 能 的 決 策 支 持 和 智 能 決 策 支 持 系 統(tǒng) 第 4章 目 錄n 4.1 人 工 智 能 基 本 原 理 n 4.2 專 家 系 統(tǒng) 與 智 能 決 策 支 持 系 統(tǒng)n 4.3 神 經(jīng) 網(wǎng) 絡(luò) 的 決 策 支 持 n 4.4 遺 傳 算 法 的 決 策 支 持n 4.5 機(jī) 器 學(xué) 習(xí) 的 決 策 支 持 4.1 人 工 智 能 基 本 原 理n 1、 人 工 智 能 的 決 策 支 持 技 術(shù) 4.1 人 工 智 能 基 本 原 理 4.1 人 工 智 能 基 本 原 理 問 題 綜 合 與 交 互 系 統(tǒng) 數(shù) 據(jù) 庫管 理 系 統(tǒng)模 型 庫管 理 系 統(tǒng)模 型

2、 庫 數(shù) 據(jù) 庫人 工 智 能 技 術(shù)專 家系 統(tǒng) 神 經(jīng)網(wǎng) 絡(luò) 遺 傳算 法 機(jī) 器學(xué) 習(xí) 自 然 語言 理 解圖 4.1 智 能 決 策 支 持 系 統(tǒng) 的 基 本 結(jié) 構(gòu) 圖 4.2 智 能 決 策 支 持 系 統(tǒng) 結(jié) 構(gòu)問 題 綜 合 與 交 互 系 統(tǒng)模 型 庫 管 理 系 統(tǒng) 數(shù) 據(jù) 庫 管 理 系 統(tǒng)知 識 庫管 理 系 統(tǒng) 推 理 機(jī) 用 戶模 型 庫 知 識 庫 數(shù) 據(jù) 庫 4.2 人 工 智 能 基 本 原 理n 4.2.1 邏 輯 推 理n 4.2.2 知 識 表 示 與 知 識 推 理n 4.2.3 搜 索 技 術(shù) 4.2.1 邏 輯 推 理1.形 式 邏 輯 (人 的

3、 思 維 形 式 、 規(guī) 律 )（ 1） 概 念 ： 反 映 事 物 的 特 有 屬 性 和 屬 性 的 取 值 。（ 2） 判 斷 ： 對 概 念 的 肯 定 或 否 定 ； 判 斷 本 身 有 對 有 錯 ； 判 斷 有 全 稱 的 肯 定 （ 或 否 定 ） 判 斷 和 存 在 的 肯定 （ 或 否 定 ） 判 斷 。（ 3） 推 理 ： 從 一 個 或 多 個 判 斷 推 出 一 個 新 判 斷 的 過 程 。 4.2.1 邏 輯 推 理2.推 理 的 種 類 演 繹 推 理歸 納 推 理類 比 推 理 假 言 推 理三 段 論 推 理數(shù) 學(xué) 歸 納 法假 言 易 位 推 理枚 舉 歸

4、 納 推 理 1） 演 繹 推 理 專 家 系 統(tǒng) 的 研 究 基 本 上 屬 于 演 繹 推 理 范 疇 。 演 繹 推 理 的核 心 是 假 言 推 理 。 假 言 推 理 ： 以 假 言 判 斷 為 前 提 ， 對 該 假 言 判 斷 的 前 件 或后 件 的 推 理 。 1） 假 言 推 理 ： pq， p q 2） 三 段 論 推 理 ： pq， qr pr 3） 假 言 易 位 推 理 （ 拒 取 式 ） ： pq， q p 符 號 “ ” 表 示 推 出4.2.1 邏 輯 推 理 2） 歸 納 推 理 (個 別 一 般 )（ 1） 數(shù) 學(xué) 歸 納 法 這 種 推 導(dǎo) 是 嚴(yán) 格

5、的 ， 結(jié) 論 是 確 實 可 靠 的 。（ 2） 枚 舉 歸 納 推 理 S1是 P ， S2是 P ， Sn是 P S1Sn是 S類 事 物 中 的 部 分 分 子 ， 沒 有 相 反 事 例 。 所 以 ， S類 事 物 都 是 P。 枚 舉 歸 納 推 理 的 結(jié) 論 是 或 然 的 (并 非 必 然 地 )，它 的 可 靠 性 和 事 例 數(shù) 量 相 關(guān) 。4.2.1 邏 輯 推 理 枚 舉 歸 納 推 理 實 例 如 觀 察 到 鐵 受 熱 膨 脹 、 銅 受 熱 膨 脹 等 事 實 而不 知 其 所 以 然 ， 由 此 推 出 “ 所 有 金 屬 受 熱 膨 脹 ”的 結(jié) 論 就

6、 是 簡 單 枚 舉 歸 納 推 理 。 3） 類 比 推 理它 是 由 兩 個 （ 或 兩 類 ） 事 物 在 某 些 屬 性 上 相 同 ，進(jìn) 而 推 斷 它 們 在 另 一 個 屬 性 上 也 可 能 相 同 的 推 理 。A事 物 有 abcd屬 性 ,B事 物 有 abc屬 性 （ 或 a,b,c相 似 屬性 ） 所 以 ， B事 物 也 可 能 有 d屬 性 （ 或 d相 似 屬 性 ） 類 比 推 理 的 結(jié) 論 帶 有 或 然 性 ， 它 的 可 靠 性 和 相 類比 事 物 屬 性 之 間 的 聯(lián) 系 程 度 有 關(guān) 。4.2.1 邏 輯 推 理 類 比 推 理 實 例 一

7、1816年 的 一 天 ， 法 國 醫(yī) 生 雷 奈 克 出 診 為 一 位 年 輕的 女 性 看 病 ， 一 見 病 人 ， 雷 奈 克 犯 起 愁 來 ： 她 身 體非 常 肥 胖 ， 要 診 斷 她 的 心 臟 和 肺 部 是 否 正 常 ， 按 當(dāng)時 醫(yī) 生 慣 用 的 方 法 ， 把 耳 朵 貼 近 病 人 的 胸 部 來 聽 ，肯 定 聽 不 清 楚 ， 更 何 況 她 是 一 位 年 輕 的 女 性 。 雷 奈克 抬 頭 看 了 看 院 子 里 正 在 玩 耍 的 小 孩 ， 腦 子 里 突 然浮 現(xiàn) 出 幾 年 前 看 到 一 個 孩 子 們 玩 的 游 戲 ： 一 個 孩 子用

8、 釘 子 敲 打 木 板 的 一 頭 ， 另 外 的 孩 子 爭 先 恐 后 地 抱著 把 耳 朵 貼 近 木 板 的 另 一 頭 ， 興 致 勃 勃 地 傾 聽 著 。 為 什 么 木 頭 能 夠 把 聲 音 清 晰 地 傳 過 來 呢 ？ 雷 奈克 稍 微 想 了 想 ， 只 見 他 很 很 地 拍 了 一 下 手 說 ： “ 就是 這 樣 ！ 就 是 這 樣 ！ ” 雷 奈 克 要 來 一 疊 紙 ， 緊 緊 地卷 成 一 個 卷 ， 然 后 把 紙 卷 的 一 端 放 在 姑 娘 的 胸 部 ，另 一 端 放 在 自 己 的 耳 朵 上 ， 側(cè) 著 臉 聽 了 起 來 。 “ 真是 一

9、 個 妙 法 ！ ” 雷 奈 克 高 興 地 喊 了 一 句 。 回 到 家 里 ，雷 奈 克 找 到 一 根 木 棒 ， 造 成 了 歷 史 上 第 一 個 “ 聽 診器 ” 。類 比 推 理 實 例 一 類 比 推 理 實 例 二 19世 紀(jì) 30年 代 ， 英 國 商 人 威 爾 斯 以 與 馮 燦 的 茂 隆 皮 箱 商 行訂 購 的 皮 箱 中 有 不 是 皮 的 木 料 為 由 ， 向 香 港 法 院 起 訴 ， 蓄 意敲 詐 馮 燦 。 針 對 這 種 情 況 ， 馮 燦 的 律 師 羅 文 錦 取 出 口 袋 的 金懷 表 ， 高 聲 問 法 官 ： “ 請 問 這 是 什 么

10、 表 ？ ” 法 官 答 道 ： “ 這是 金 表 ， 可 是 這 與 本 案 有 什 么 關(guān) 系 ？ ” 羅 文 錦 高 舉 金 表 ， 面對 法 庭 上 所 有 的 人 說 ： “ 有 關(guān) 系 。 這 是 金 表 ， 沒 有 人 懷 疑 是吧 ？ 但 是 ， 請 問 ， 這 塊 金 表 除 表 面 鍍 金 之 外 ， 內(nèi) 部 的 機(jī) 制 都是 金 制 嗎 ？ ” 旁 聽 者 同 聲 議 論 ： “ 當(dāng) 然 不 是 。 ” 羅 文 錦 繼 續(xù)說 ： “ 那 么 人 們 為 什 么 又 叫 它 金 表 呢 ？ ” 稍 作 停 頓 又 高 聲 說 ：“ 由 此 可 見 ， 茂 隆 行 的 皮 箱

11、 案 不 過 是 原 告 無 理 取 鬧 、 存 心 敲詐 而 已 ” 原 告 理 屈 詞 窮 ， 法 庭 最 后 以 威 爾 斯 誣 告 ， 罰 款 5000元 結(jié) 案 皮 箱 訴 訟 案 的 法 庭 辯 論 中 ， 賣 方 律 師 在 反 駁中 所 使 用 的 就 是 類 比 推 理 ： 表 的 外 表 有 金 ， 內(nèi) 部 含 有 不 是 金 的 材 料 ， 但卻 是 金 表 ； 箱 的 外 表 有 皮 ， 但 也 含 有 不 是 皮 的 材 料 ；所 以 ， 箱 仍 是 皮 箱 。類 比 推 理 實 例 二 3. 總 結(jié) 1） 演 繹 推 理 的 結(jié) 論 沒 有 超 出 已 知 的 知

12、識 范 圍 。而 歸 納 推 理 和 類 比 推 理 的 結(jié) 論 超 出 已 知 的 知 識 范 圍 。 演繹推理只能解釋一般規(guī)律中的個別現(xiàn)象 而歸納推理和類比推理創(chuàng)造了新的知識，使科學(xué)得到新發(fā)展，是一種創(chuàng)造思維方式 2） 演 繹 推 理 中 由 于 前 提 和 結(jié) 論 有 必 然 聯(lián) 系 ， 只要 前 提 為 真 ， 結(jié) 論 一 定 為 真 。 歸納推理和類比推理中前提和結(jié)論，不能保證有必然聯(lián)系，具有或然性。這樣推理的結(jié)論未必是可靠的。需要經(jīng)過嚴(yán)格的驗證和證明，使之形成新的理論。4.2.1 邏 輯 推 理 4.2.2 知 識 表 示 與 知 識 推 理n 4.2.2.1 數(shù) 理 邏 輯 表

13、示 法 (自 學(xué) )n 4.2.2.1 產(chǎn) 生 式 規(guī) 則n 4.2.2.3 語 義 網(wǎng) 絡(luò)n 4.2.2.4 框 架n 4.2.2.5 劇 本 (自 學(xué) ) 4.2.2.2 產(chǎn) 生 式 規(guī) 則 （ if A then B）n 1. 正 向 推 理 1.A BG2.C DA3.ED B,C,E4.2.2.2 產(chǎn) 生 式 規(guī) 則事 實 庫 的 最 后 狀 態(tài) 為 ：B， C， E， D， A， G產(chǎn) 生 式 規(guī) 則 庫 事 實 庫產(chǎn) 生 式 規(guī) 則 庫 和 事 實 庫 的 初 始 狀 態(tài) 為 ： 4.2.2.2 產(chǎn) 生 式 規(guī) 則n 逆 (反 )向 推 理 G A D EB C4.2.2.2 產(chǎn)

14、 生 式 規(guī) 則逆 向 推 理 中 ， 目 標(biāo) 改 變 過 程 ：1.A BG2.C DA3.ED B,C,E產(chǎn) 生 式 規(guī) 則 庫 事 實 庫 4.2.3 搜 索 技 術(shù)n 搜 索 技 術(shù) 是 人 工 智 能 的 一 個 重 要 研 究 內(nèi) 容 。 智 能 技術(shù) 體 現(xiàn) 在 減 少 搜 索 樹 中 的 盲 目 搜 索 。按 多 項 式 時 間 執(zhí) 行 的 算 法 ， 計 算 機(jī) 是 可 以 實 現(xiàn) 的 。按 指 數(shù) 時 間 執(zhí) 行 的 算 法 ， 計 算 機(jī) 是 不 可 能 實 現(xiàn) 的 。 4.2.3 搜 索 技 術(shù)n 人 工 智 能 中 發(fā) 展 了 一 種 稱 為 啟 發(fā) 式 搜 索 方

15、法 ， 基 本 思 想 可 用一 個 實 例 來 說 明 ：n 一 個 外 地 人 到 某 城 市 出 差 ， 他 想 到 書 店 看 看 ， 又 不 知 書 店在 何 處 ， 如 果 采 取 盲 目 搜 索 ， 從 住 地 出 發(fā) 沿 任 一 方 向 走 ，在 分 叉 路 口 又 任 選 一 分 支 走 ， 他 可 能 走 幾 天 幾 夜 也 找 不 到 n 如 果 采 用 啟 發(fā) 式 方 法 ， 他 會 問 路 上 的 人 ， 到 書 店 怎 樣 走 。城 市 中 的 大 部 分 人 對 書 店 不 知 道 ， 問 不 出 來 。 4.2.3 搜 索 技 術(shù)問 該 城 市 最 熱 鬧 的

16、地 方 在 哪 兒 ？n 但 書 店 在 哪 兒 ， 仍 然 不 知 道 。 如 果 盲 目 搜 索 ， 可 能 仍 然找 不 到 。 如 果 采 用 啟 發(fā) 式 方 法 ， 他 會 問 路 上 的 人 ， 賣 畫的 地 方 在 哪 兒 ， 他 可 以 通 過 畫 店 再 問 書 店 在 哪 兒 ？ n 啟 發(fā) 式 方 法 能 減 少 大 量 盲 目 無 效 的 搜 索 ， 能 有 效 克 服 按指 數(shù) 時 間 執(zhí) 行 的 組 合 爆 炸 現(xiàn) 象 4.2.3 搜 索 技 術(shù)n 搜 索 方 法 分 類 ： （ 1） 極 小 極 大 搜 索 法 。 （ 2） 剪 枝 算 法 。 4.2.3.1 廣

17、 度 優(yōu) 先 搜 索 （ 寬 度 優(yōu) 先 搜 索 ）1、 廣 度 優(yōu) 先 搜 索 思 想 圖 4.7 廣 度 優(yōu) 先 搜 索 示 意 圖 （ 2） 算 法1) 把 初 始 節(jié) 點 S0故 入 OPEN表 。2) 如 果 OPEN表 為 空 ， 則 問 題 無 解 ， 退 出 。 3) 把 OPEN表 的 第 一 個 節(jié) 點 (記 為 節(jié) 點 n)取 出 放 入CLOSED表 。4)考 察 節(jié) 點 n是 否 為 目 標(biāo) 節(jié) 點 。 若 是 ， 則 求 得 了問 題 的 解 ， 退 出 。 5)若 節(jié) 點 n不 可 擴(kuò) 展 ， 則 轉(zhuǎn) 第 2)步 。 6) 擴(kuò) 展 節(jié) 點 n， 將 其 子 節(jié) 點

18、 放 入 OPEN表 的 尾 部 ， 并為 每 一 個 子 節(jié) 點 都 配 置 指 向 父 節(jié) 點 的 指 針 ， 然 后轉(zhuǎn) 第 2)步 。 廣度優(yōu)先搜索過程 開 始 把 n的 后 繼 節(jié) 點 放 入 OPEN表 的 末端 ， 提 供 返 回 節(jié) 點 n的 指 針把 S放 入 OPEN表OPEN表 為 空 表 ？ 是 失 敗否把 第 一 個 節(jié) 點 （ n） 從 OPEN移 至 CLOSED表n為 目 標(biāo) 節(jié) 點 ？ 是 成 功否n能 否 擴(kuò) 展 是 否 有 任 何 后 繼節(jié) 點 為 目 標(biāo) 節(jié) 點否 是是否 例 子 1(八 數(shù) 碼 難 題 )重 排 九 宮 問 題 ， 在 3x3的 方 格

19、棋 盤 上 放 置 分 別 標(biāo) 有 數(shù)字 1、 2、 3、 4、 5、 6、 7、 8共 8個 棋 子 ， 初 始 狀 態(tài)為 S0， 目 標(biāo) 狀 態(tài) 為 Sg， 如 圖 1所 示 ?？?使 用 的 算 符 有 ： 空 格 左 移 ， 空 格 上 移 ， 空 格 右 移 ， 空 格 下 移 。 即只 允 許 把 位 于 空 格 左 、 上 、 右 、 下 的 鄰 近 棋 子 移 入空 格 。 要 求 尋 找 從 初 始 狀 態(tài) 到 目 標(biāo) 狀 態(tài) 的 路 徑 。 該 路 徑 使 用 的 算 符 序 列 ： 空 格 上 移 ， 空 格 左 移 ， 空 格 下 移 ，空 格 右 移 。 廣 度 優(yōu)

20、先 搜 索 的 盲 目 性 較 大 ， 當(dāng) 目 標(biāo) 節(jié) 點 距 離初 始 節(jié) 點 較 遠(yuǎn) 時 將 會 產(chǎn) 生 許 多 無 用 節(jié) 點 ， 因 此 搜 索效 率 低 ， 但 是 ， 只 要 問 題 有 解 ， 用 廣 度 優(yōu) 先 搜 索 總可 以 得 到 解 ， 而 且 得 到 的 是 路 徑 最 短 的 路 徑 。 由 圖 2可 以 看 出 ， 解 的 路 徑 是 ： S0381626廣 度 優(yōu) 先 法 適 合 于 搜 索 樹 的 寬 度 較 小 的 問 題 。 1、 深 度 優(yōu) 先 搜 索 法 思 想 4.2.3.2 深 度 優(yōu) 先 搜 索 法 圖 4.8 深 度 優(yōu) 先 搜 索 示 意 圖

21、 （ 2） 算 法1) 把 初 始 節(jié) 點 S0故 入 OPEN表 。2)如 果 OPEN表 為 空 ， 則 問 題 無 解 ， 退 出 。 3)把 OPEN表 的 第 一 個 節(jié) 點 (記 為 節(jié) 點 n)取 出 放 入 CLOSED表 。 4)考 察 節(jié) 點 n是 否 為 目 標(biāo) 節(jié) 點 。 若 是 ， 則 求 得 了 問題 的 解 ， 退 出 。 5)若 節(jié) 點 n不 可 擴(kuò) 展 ， 則 轉(zhuǎn) 第 2)步 。 6)擴(kuò) 展 節(jié) 點 n， 將 其 全 部 子 節(jié) 點 放 入 到 OPEN表 的 首 部 ，并 為 其 配 置 指 向 父 節(jié) 點 的 指 針 ， 然 后 轉(zhuǎn) 第 2)步 。 開 始

22、把 S放 入 OPEN表OPEN表 為 空 表 ？ 是 失 敗否把 第 一 個 節(jié) 點 （ n） 從 OPEN移 至 CLOSED表 是 否 有 任 何 后 繼節(jié) 點 為 目 標(biāo) 節(jié) 點 是 成 功否擴(kuò) 展 n,把 n的 后 繼 節(jié) 點 放 入 OPEN表 的前 頭 ， 提 供 返 回 節(jié) 點 n的 指 針s為 目 標(biāo) 節(jié) 點 ？否 是深度優(yōu)先搜索 例 子 2： 對 圖 1所 示 的 重 排 九 宮 問 題 進(jìn) 行 深 度 優(yōu) 先 搜 索 ， 可 得 到 圖 3所 示 的 搜 索 樹 這 只 是 搜 索 樹 的 一 部 分 ， 尚 未 到 達(dá) 目 標(biāo) 節(jié) 點 ， 仍需 繼 續(xù) 往 下 搜 索

23、。 在 深 度 優(yōu) 先 搜 索 中 ， 搜 索 一 旦 進(jìn) 入 某 個 分 支 ， 就將 沿 著 該 分 支 一 直 向 下 搜 索 。 如 果 目 標(biāo) 節(jié) 點 恰 好 在 此分 支 上 ， 則 可 較 快 地 得 到 解 。 但 是 ， 如 果 目 標(biāo) 節(jié) 點 不在 此 分 支 上 ， 而 該 分 支 又 是 一 個 無 窮 分 支 ， 則 就 不 能得 到 解 。 所 以 深 度 優(yōu) 先 搜 索 是 不 完 備 的 ， 即 使 問 題 有解 ， 它 也 不 一 定 能 求 得 解 。 顯 然 ， 用 深 度 優(yōu) 先 求 得 的解 ， 也 不 一 定 是 路 徑 最 短 的 解 。 深 度

24、優(yōu) 先 法 適 合 于 搜 索 樹 的 深 度 較 小 的 問 題 4.2.3.3 生 成 測 試 法n 生 成 測 試 法 算 法 是 ： 4.2.3.3 生 成 測 試 法 4.2.3.4 爬 山 法 (生 成 測 試 法 的 變 種 ) n 爬 山 算 法 ： (測 試 函 數(shù) )n 對該狀態(tài)測試，檢查是否為目標(biāo)，是則停止。 n 計算該狀態(tài)的好壞，或者比較各狀態(tài)的好壞。 在 爬 山 法 中 可 能 出 現(xiàn) 以 下 幾 種 情 況 ： 局 部 極 大 點 ： 它 比 周 圍 鄰 居 狀 態(tài) 都 好 ， 但 不 是 目 標(biāo) 。 圖 4.9局 部 極 大 點 示 意 圖 在 爬 山 法 中 可

25、 能 出 現(xiàn) 以 下 幾 種 情 況 ： 平 頂 ： 它 與 全 部 鄰 居 狀 態(tài) 都 有 同 一 個 值 ， 構(gòu) 成 一 個 平 面 。 圖 4.10 平 頂 示 意 圖 在 爬 山 法 中 可 能 出 現(xiàn) 以 下 幾 種 情 況 ： 山 脊 ： 它 與 線 狀 鄰 居 狀 態(tài) 有 相 同 值 ， 比 其 它 鄰 居 狀態(tài) 要 好 。 圖 4.11山 脊 示 意 圖 4.2.3.4 爬 山 法n 為 了 解 決 以 上 問 題 ， 需 要 采 用 如 下 策 略 ： 4.2.3.5 啟 發(fā) 式 搜 索 n 啟 發(fā) 式 搜 索 是 對 每 個 在 搜 索 過 程 中 遇 到 的 新 狀 態(tài)

26、，用 一 個 估 計 函 數(shù) （ 啟 發(fā) 式 函 數(shù) ） 并 計 算 其 值 的 大小 ， 確 定 下 一 步 將 從 哪 一 個 狀 態(tài) 開 始 繼 續(xù) 前 進(jìn) 。 4.2.3.5 啟 發(fā) 式 搜 索n 具 體 需 要 考 慮 以 下 問 題 ： 一 般 啟 發(fā) 式 函 數(shù) 法 用 如 下 公 式 表 示 ： f（ x） =g（ x） +h（ x） 4.2.3.5 啟 發(fā) 式 搜 索 啟 發(fā) 式 函 數(shù) 分 析 ：n 1. 當(dāng) h（ x） =0， 即 f（ x） =g（ x） 取 f（ x） 為 最 小 ， 即 取 g（ x） 為 最 小 。 這 要 求 在 已擴(kuò) 展 的 結(jié) 點 中 取 最

27、 佳 路 徑 。 g（ x） 能 保 證 找 到 最 好解 。 但 對 搜 索 速 度 沒 有 太 多 的 幫 助 。n 2. 當(dāng) g（ x） =0， 即 f（ x） =h（ x） h（ x） 是 從 當(dāng) 前 狀 態(tài) 到 目 標(biāo) 狀 態(tài) 的 耗 費 。 取 它 最 小 ，將 會 加 快 搜 索 速 度 ， 但 它 并 不 保 證 得 到 最 優(yōu) 解 。4.2.3.5 啟 發(fā) 式 搜 索 g（ x） 選 取 的 幾 種 特 例 ： f(x)一 般 表 示 估 計 值 ， 愈 接 近 精 確 值 ， 啟 發(fā) 式 效 果愈 好 。 如 果 是 精 確 值 ,就 不 是 啟 發(fā) 式 函 數(shù) 。4.2.

28、3.5 啟 發(fā) 式 搜 索 圖 -4啟 發(fā) 式 搜 索 2 8 31 6 47 52 8 31 47 6 5 1 38 2 47 6 5 2 8 31 47 6 5 2 31 8 47 6 5 2 8 31 47 6 58 32 1 47 6 5 2 8 37 1 46 5 2 31 8 47 6 5 2 31 8 47 6 58 3 2 1 47 6 5 1 38 2 4 7 6 5 1 2 38 47 6 58 1 3 2 6 47 5 8 1 32 47 6 5 1 2 37 8 46 58 32 1 47 6 5 8 1 32 47 6 58 1 32 47 6 5 1 2 38 47

29、 6 5 1 38 2 47 6 51 2 38 47 6 5*8 1 37 2 46 5 * 4 4 5 54 5 3 54 2 305 45 5 45 3 20 4h（ x） 可 以定 義 為 節(jié) 點x中 數(shù) 碼 位 置與 目 標(biāo) 節(jié) 點相 比 不 同 的個 數(shù) n 4.3 專 家 系 統(tǒng) 與 智 能 決 策 支 持 系 統(tǒng) 4.3.1專 家 系 統(tǒng) 原 理n 1. 專 家 系 統(tǒng) 概 念n 專 家 系 統(tǒng) 是 具 有 大 量 專 門 知 識 ， 并 能 運 用 這 些 知 識 解 決特 定 領(lǐng) 域 中 實 際 問 題 的 計 算 機(jī) 程 序 系 統(tǒng) 。 n 專 家 系 統(tǒng) 是 利 用 大

30、 量 的 專 家 知 識 ， 運 用 知 識 推 理 的 方 法來 解 決 各 特 定 領(lǐng) 域 中 的 實 際 問 題 。 計 算 機(jī) 專 家 系 統(tǒng) 這 樣的 軟 件 能 夠 達(dá) 到 人 類 專 家 解 決 問 題 的 水 平 。 4.3.1專 家 系 統(tǒng) 原 理n 2） 專 家 系 統(tǒng) 的 特 點 4.3.1專 家 系 統(tǒng) 原 理 例 如 ： 求 解 微 積 分 問 題 ， 是 利 用 30 40條 微 分 、 積 分 公式 來 求 解 千 變 萬 化 的 微 分 、 積 分 問 題 ， 得 出 各 自 的結(jié) 果 。其 中 微 積 分 公 式 就 是 規(guī) 律 性 知 識 ， 求 解 微 積

31、 分 問 題 就 是對 某 函 數(shù) 反 復(fù) 利 用 微 積 分 公 式 進(jìn) 行 推 導(dǎo) ， 最 后 得 出 該 問題 的 結(jié) 果 。這 個 推 理 過 程 是 一 個 不 固 定 形 式 的 推 理 ， 即 前 后 用 哪 個公 式 ， 調(diào) 用 多 少 次 這 些 公 式 都 隨 問 題 變 化 而 變 化 。 n 1） 專 家 系 統(tǒng) 對 比 數(shù) 據(jù) 庫 檢 索n （ A） 知 識 只 含 事 實 性 知 識 ， 不 包 含 規(guī) 律 性 知 識 。 n （ B） 推 理 是 對 已 有 記 錄 的 檢 索 ， 記 錄 不 存 在 ， 則 檢 索不 到 。 不 能 適 應(yīng) 變 化 的 事 實

32、， 推 理 不 出 新 事 實 。4.3.1專 家 系 統(tǒng) 原 理 4.3.1專 家 系 統(tǒng) 原 理n 2） 專 家 系 統(tǒng) 對 比 數(shù) 值 計 算 知 識 處 理 的 特 點從 上 面 分 析 可 見 ， 數(shù) 值 計 算 、 數(shù) 據(jù) 處 理 是 知 識 處 理的 特 定 情 況 ， 知 識 處 理 則 是 它 們 的 發(fā) 展 ! （ A） 知 識 包 括 事 實 和 規(guī) 則 （ 狀 態(tài) 轉(zhuǎn) 變 過 程 ） 。（ B） 適 合 于 符 號 處 理 （ 如 微 積 分 求 解 ） 。（ C） 推 理 過 程 是 不 固 定 形 式 的 （ 推 導(dǎo) 過 程 中 每次 選 用 的 規(guī) 則 知 識 是

33、 變 化 的 ） 。（ D） 能 得 出 未 知 的 事 實 （ 如 推 導(dǎo) 出 新 的 微 分 公式 ） 。 2.專 家 系 統(tǒng) 結(jié) 構(gòu) 專 家 系 統(tǒng) 的 核 心 是 知 識 庫 和 推 理 機(jī) 。 專 家 系 統(tǒng) 可 以 概 括 為 ： 專 家 系 統(tǒng) 知 識 庫 +推 理 機(jī)4.3.1專 家 系 統(tǒng) 原 理 知 識 獲 取 人 機(jī) 接 口知 識 庫 推 理 機(jī)專 家 用 戶咨 詢 建 議 專 家 系 統(tǒng) 核 心 專 家 系 統(tǒng) 結(jié) 構(gòu) 3.產(chǎn) 生 式 規(guī) 則 知 識 的 推 理 機(jī)產(chǎn) 生 式 規(guī) 則 的 推 理 機(jī) 搜 索 +匹 配 （ 假 言 推 理 ）n 在 推 理 過 程 中 ，

34、 是 一 邊 搜 索 一 邊 匹 配 。 匹 配 需 要 找 事實 ,這 個 事 實 一 是 來 自 于 規(guī) 則 庫 中 別 的 規(guī) 則 ， 一 是 來 自向 用 戶 提 問 。n 在 匹 配 時 會 出 現(xiàn) 成 功 或 不 成 功 ， 對 于 不 成 功 的 將 引 起搜 索 中 的 回 溯 和 由 一 個 分 枝 向 另 一 個 分 枝 的 轉(zhuǎn) 移 ， 可見 在 搜 索 過 程 中 包 含 了 回 溯 。4.3.1 專 家 系 統(tǒng) 原 理 4.3.1 專 家 系 統(tǒng) 原 理4. 產(chǎn) 生 式 規(guī) 則 推 理 的 解 釋 4.3.2 產(chǎn) 生 式 規(guī) 則 專 家 系 統(tǒng)n 4.3.2.1 產(chǎn) 生

35、 式 規(guī) 則n 4.3.2.2 推 理 樹 (知 識 樹 )n 4.3.2.3 逆 向 推 理 過 程n 4.3.2.4 事 實 數(shù) 據(jù) 和 解 釋 機(jī) 制 4.3.2 產(chǎn) 生 式 規(guī) 則 專 家 系 統(tǒng)n 產(chǎn) 生 式 規(guī) 則 的 優(yōu) 點 4.3.2.1 產(chǎn) 生 式 規(guī) 則 ESn 產(chǎn) 生 式 規(guī) 則 知 識 一 般 表 示 為 :if A then B，或 ：如 果 A成 立 則 B成 立 ，或 ： AB 4.3.2.1 產(chǎn) 生 式 規(guī) 則n 產(chǎn) 生 式 規(guī) 則 知 識 表 示 允 許 有 如 下 的 特 點 ： 4.3.2.1 產(chǎn) 生 式 規(guī) 則 ESn 由 于 以 上 特 點 ， 規(guī) 則

36、 知 識 集 能 做 到 ： 4.3.2.2推 理 樹 （ 知 識 樹 ）n 規(guī) 則 庫 中 的 各 條 規(guī) 則 之 間 一 般 來 說 都 是 有 聯(lián) 系 的n 按 逆 向 推 理 思 想 把 知 識 庫 所 含 的 總 目 標(biāo) （ 它 是 某些 規(guī) 則 的 結(jié) 論 ） 作 為 根 結(jié) 點 ， 按 規(guī) 則 的 前 提 和 結(jié)論 展 開 成 一 棵 樹 的 形 式 。 這 棵 樹 一 般 稱 為 推 理 樹或 知 識 樹 ， 它 把 知 識 庫 中 的 所 有 規(guī) 則 都 連 結(jié) 起 來 XF GLMEC4.3.2.2推 理 樹 （ 知 識 樹 ）A BI J KW Z P Q 用 規(guī) 則 的

37、 前 提 和 結(jié) 論 形 式 畫 出 逆 向 推 理 樹 形 式 為 ： 4.3.2.2推 理 樹 （ 知 識 樹 ）前 提 I前 提 J前 提 L前 提 M前 提 E(結(jié) 論 )(結(jié) 論 )(結(jié) 論 )前 提 A前 提 B前 提 C（ 結(jié) 論 )（ 結(jié) 論 ） (結(jié) 論 )總 目 標(biāo) G（ 結(jié) 論 ) 前 提 X前 提 F前 提 W前 提 Z前 提 P前 提 Q? ? ? ? ? ? ? n 該 “ 與 或 ” 推 理 樹 的 特 點 是 ：4.3.2.2推 理 樹 （ 知 識 樹 ） 4.3.2.3 逆 向 推 理 過 程 推 理 樹 的 深 度優(yōu) 先 搜 索 N1 7 982 GA B

38、CJI K L M E4 5Y X F Z P Q1011 123 Y W Y Y YN6 4.3.2.3 逆 向 推 理 過 程在 計 算 機(jī) 中 實 現(xiàn) 時 ， 并 不 把 規(guī) 則 連 成 推 理 樹 ， 而 是 利 用規(guī) 則 棧 來 完 成 。 當(dāng) 調(diào) 用 此 規(guī) 則 時 ， 把 它 壓 入 棧 內(nèi) （ 相 當(dāng) 于對 樹 的 搜 索 ） ， 當(dāng) 此 規(guī) 則 的 結(jié) 論 已 求 出 （ yes或 no） 時 ， 需要 將 此 規(guī) 則 退 棧 （ 相 當(dāng) 于 對 樹 的 回 溯 ） 。 利 用 規(guī) 則 棧 的 壓 入 和 退 出 的 過 程 ， 相 當(dāng) 于 完 成 了 推 理樹 的 深 度

39、優(yōu) 先 搜 索 和 回 溯 過 程 。 4.3.2.3 逆 向 推 理 過 程 結(jié) 點 的 否 定 4.3.2.4 事 實 數(shù) 據(jù) 庫 和 解 釋 機(jī) 制 1. 事 實 數(shù) 據(jù) 庫 (動 態(tài) 數(shù) 據(jù) 庫 ) 事 實 Y,N值 規(guī) 則 號 可 信 度A11 N 0(提 問 ) 0A12 Y 0 0.9A 1 Y 4 0.8事 實 欄 放 入 命 題規(guī) 則 號 ： 事 實 取 Y或N的 理 由可 信 度 ： 事 實 的 可信 度 2. 解 釋 機(jī) 制4.3.2.4 事 實 數(shù) 據(jù) 庫 和 解 釋 機(jī) 制 4.3.3 專 家 系 統(tǒng) 與 決 策 支 持 系 統(tǒng) 集 成 數(shù) 據(jù) 庫DBDSS控 制系

40、統(tǒng)模 型 庫MB 問 題 綜 合與交 互 系 統(tǒng) 動 態(tài)DB推 理 機(jī)和解 釋 器知 識 庫KB 集 成 系 統(tǒng)DSS ES 圖 4.16智 能 決 策 支 持 系 統(tǒng) 集 成 結(jié) 構(gòu) 圖綜 合 系 統(tǒng) DSS與 ES集 成 形 式 一 ： DSS和 ES并 重 的 IDSS結(jié) 構(gòu) 集 成系 統(tǒng)DSS ES4.3.3 專 家 系 統(tǒng) 與 決 策 支 持 系 統(tǒng) 集 成 集 成 特 點1.具 有 綜 合 系 統(tǒng) ， 具 有 調(diào) 用 和 集 成 DSS和 ES的能 力 。2.擴(kuò) 充 DSS的 問 題 與 人 機(jī) 交 互 系 統(tǒng) 功 能 ， 增 加對 ES的 調(diào) 用 組 合 能 力DSS與 ES的

41、關(guān) 系 ：DSS中 DB與 ES中 的 動 態(tài) DB進(jìn) 行 數(shù) 據(jù) 交 換解 決 問 題 的 特 點體 現(xiàn) 定 性 分 析 和 定 量 分 析 并 重 解 決 問 題 的 特 點 。 DSS控 制 系統(tǒng)MB DB ESDSS與 ES集 成 形 式 二 ： DSS為 主 體 的 IDSS結(jié) 構(gòu) 4.3.3 專 家 系 統(tǒng) 與 決 策 支 持 系 統(tǒng) 集 成 集 成 特 點集 成 系 統(tǒng) 和 DSS控 制 系 統(tǒng) 合 為 一 體DSS與 ES的 關(guān) 系 ：ES被 DSS控 制 系 統(tǒng) 調(diào) 用解 決 問 題 的 特 點體 現(xiàn) 以 定 量 分 析 為 主 ， 結(jié) 果 定 性 分 析 解 決 問題 的

42、特 點 。 推 理 機(jī)（ 廣 義 ） DSS 動 態(tài)DB KB 推 理 機(jī) MB動 態(tài)DB KB圖 4.19 DSS作 為 推 理 形 式 的 IDSS 圖 4.20模 型 作 為 知 識 的 IDSSDSS與 ES集 成 形 式 三 ： ES為 主 體 的 IDSS結(jié) 構(gòu)4.3.3 專 家 系 統(tǒng) 與 決 策 支 持 系 統(tǒng) 集 成 集 成 特 點人 機(jī) 交 互 系 統(tǒng) 和 ES合 為 一 體 DSS與 ES的 關(guān) 系 ：圖 4.19 DSS作 為 推 理 機(jī) ， 受 ES的 推 理 機(jī) 控 制 ；圖 4.20數(shù) 據(jù) 模 型 作 為 知 識 出 現(xiàn)解 決 問 題 的 特 點 體 現(xiàn) 以 定

43、量 分 析 為 主 ， 結(jié) 果 定 性 分 析 解 決 問 題 的 特 點 。 4.3.4 建 模 專 家 系 統(tǒng) 專 家 系 統(tǒng) 實 現(xiàn) 模 型 選 擇 的 實 例 進(jìn) 行 說 明 。 R1： A B C M1R2： A1AR3： A11A1R4： A12A1R5： A B E F M2R6： C1CR7： E1ER8： A B E F GM3R9： A B C GM4R10： B1B R11： H1HR12： A2AR13： H B C M5R14： H B C GM6R15： H B E F M7R16： H B E F GM8R17： A B E I M9R18： A B I GM10

44、R19： H B E I M11R20： H B E I GM124.3.4 建 模 專 家 系 統(tǒng) A： 彈 簧 滿 足 胡 克 定 律B： 彈 簧 質(zhì) 量 可 以 忽 略C： 可 以 忽 略 摩 擦 力D： 沒 有 沖 力A1： 彈 簧 有 線 性 恢 復(fù) 力A11： 彈 力 與 位 移 成 正 比A12： 位 移 量 很 小E： 要 考 慮 摩 擦 力F： 摩 擦 力 與 速 度 之 間 為 線性 關(guān) 系C1： 若 振 動 為 自 發(fā) 時 振 幅為 常 數(shù) E1： 若 振 動 為 自 發(fā) 時 振 幅 是 遞減 的G： 有 沖 力 F（ T）B1： 彈 簧 具 有 質(zhì) 量 N并 且 N/M

45、遠(yuǎn)遠(yuǎn) 小 于 1H1： 彈 簧 勢 能 不 是 關(guān) 于 平 衡 位置 對 稱H： 彈 簧 不 潢 足 胡 克 定 律A2： 彈 簧 勢 能 與 函 數(shù) X（ T） 成正 比I： 摩 擦 力 與 速 度 之 間 為 非 線 性關(guān) 系各 項 英 文 字 母 含 義 為 ： M1： X+（ C2/M） X 0M2： X+（ C1/M） X+（ C2/M） X 0M3： X+（ C1/M） X+（ C2/M） X F（ T） /MM4： X+（ C2/M） X F（ T） /MM5： X+F（ X） /M 0M6： X+F（ X） /M F（ T） /MM7： X+（ C1/M） X+F（ X） /M

46、 0 M8： X+（ C1/M） X+F（ X）/M F（ T） /MM9： X+（ G/M） X+（ C2/M）X 0M10： X+（ G/M） X+（ C2/M）X F（ T） /MM11： X+（ G/M） X+F（ X）/M 0M12： X+（ G/M） X+F（ X）/M F（ T） /M其 中 X表 示 X對 的 二 階 導(dǎo) 數(shù) ，X表 示 一 階 導(dǎo) 數(shù) 。 3. 規(guī) 則 庫 的 推 理 樹 4.3.4 建 模 專 家 系 統(tǒng) A2A1B1C1？ E1？ ？ B1？A11A12？ ？ ？ ？DEFGHIA B C？ ？ M（ M1， M2， ， M12）圖 4.21彈 簧 振 動

47、 推 理 樹 的 標(biāo) 準(zhǔn) 形 式 專 家 系 統(tǒng) 應(yīng) 用現(xiàn) 有 一 個 彈 簧 ， 滿 足 如 下 特 性 ： H1（ 彈 簧 勢 能 不 是 關(guān) 于 平 衡 位 置 對 稱 ） B1（ 彈 簧 具 有 質(zhì) 量 N并 且 N/M遠(yuǎn) 遠(yuǎn) 小 于 1） C1（ 若 振 動 為 自 發(fā) 時 振 幅 為 常 數(shù) ） G（ 有 沖 力 F（ T） ）通 過 專 家 系 統(tǒng) 推 理 將 得 出 ： 該 彈 簧 滿 足 模 型 6（ M 6） 的 微 分 方 程 。 4.5 遺 傳 算 法 的 決 策 支 持 4.5.1 遺 傳 算 法 原 理n 遺 傳 算 法 (Genetic Algorithm， GA

48、) n 遺 傳 算 法 的 發(fā) 展 過 程 大 體 上 可 分 為 以 下 三 個 階 段 ： n 1975年 美 國 Michigan 大 學(xué) J.Holland首 次 系 統(tǒng) 地 闡 述 了 遺 傳 算法 的 基 本 理 論 和 方 法 。 n 在 這 一 時 期 的 大 部 分 研 究 都 處 于 理 論 研 究 和 建 立 實 驗 模 型 階 段n 1980年 Smith教 授 將 遺 傳 算 法 應(yīng) 用 于 機(jī) 器 學(xué) 習(xí) 領(lǐng) 域 ， 研 制 出 了 一個 著 名 的 分 類 器 (Classifier)系 統(tǒng) 。 n 這 期 間 許 多 學(xué) 者 對 遺 傳 算 法 進(jìn) 行 了 大

49、量 的 改 進(jìn) 和 發(fā) 展 ， 提 出 了許 多 成 功 的 遺 傳 算 法 模 型 ， 使 遺 傳 算 法 應(yīng) 用 于 更 廣 泛 的 領(lǐng) 域 。n 進(jìn) 入 90年 代 后 ， 遺 傳 算 法 作 為 一 種 實 用 、 高 效 的 優(yōu) 化 技 術(shù) ， 得到 了 極 為 迅 速 的 發(fā) 展 。4.5.1 遺 傳 算 法 原 理 4.5.1 遺 傳 算 法 原 理4.5.1.1 遺 傳 算 法 工 作 過 程4.5.1.2 遺 傳 算 法 的 理 論 基 礎(chǔ)4.5.1.3 遺 傳 算 法 的 基 本 特 征 4.5.1.1 遺 傳 算 法 的 工 作 過 程n 遺 傳 算 法 是 一 種 群

50、體 型 操 作 ， 該 操 作 以 群 體 中 的 所 有 個 體為 對 象 。n 個 體 就 是 模 擬 生 物 個 體 而 對 問 題 中 的 對 象 （ 一 般 就 是 問 題 的 解 ） 的一 種 稱 呼 ， 一 個 個 體 也 就 是 搜 索 空 間 中 的 一 個 點 。n 種 群 (population)就 是 模 擬 生 物 種 群 而 由 若 干 個 體 組 成 的 群 體 , 它 一般 是 整 個 搜 索 空 間 的 一 個 很 小 的 子 集 。 n 遺 傳 算 法 的 三 個 主 要 操 作 算 子 ： 選 擇 （ selecation） 、交 叉 （ crossove

51、r） 和 變 異 （ mutation） 構(gòu) 成 了 遺 傳操 作 （ G enetic operation） ， 使 遺 傳 算 法 具 有 了 其 他 傳統(tǒng) 方 法 所 沒 有 的 特 性 。 產(chǎn) 生 新 一 代 群 體 編 碼 和 初 始 群 體 形 成 輸 出 種 群個 體 適 應(yīng) 值 滿 意 否 ？4.5.1.1 遺 傳 算 法 的 工 作 過 程n 首 先 將 問 題 的 每 個 可 能 的 解 按 某種 形 式 編 碼 ， 編 碼 后 的 解 稱 作 染 色體 （ 個 體 ） 。n 隨 機(jī) 選 取 N個 染 色 體 構(gòu) 成 初 始 種 群 ，再 根 據(jù) 預(yù) 定 的 評 價 函 數(shù)

52、 對 每 個 染 色體 計 算 適 應(yīng) 值 ， 使 得 性 能 較 好 的 染色 體 具 有 較 高 的 適 應(yīng) 值 。n 選 擇 適 應(yīng) 值 高 的 染 色 體 進(jìn) 行 復(fù) 制 ，通 過 遺 傳 算 子 來 產(chǎn) 生 一 群 新 的 更 適應(yīng) 環(huán) 境 的 染 色 體 ， 形 成 新 的 種 群 。n 這 樣 一 代 一 代 不 斷 繁 殖 ， 最 后 收斂 到 一 個 最 適 應(yīng) 環(huán) 境 的 個 體 上 ， 求 得 問 題 的 最 優(yōu) 解 。遺傳算子選 擇交 叉變 異 1. 群 體 中 個 體 的 編 碼4.5.1.1 遺 傳 算 法 的 工 作 過 程 2. 適 應(yīng) 值 函 數(shù) 的 確 定

53、n 適 應(yīng) 值 函 數(shù) (即 評 價 函 數(shù) )是 根 據(jù) 目 標(biāo) 函 數(shù) 確 定 的 。 適 應(yīng) 值 總 是 非 負(fù) 的 ，任 何 情 況 下 總 是 希 望 越 大 越 好 。 如 果 目 標(biāo) 函 數(shù) 不 是 取 最 大 值 時 ， 需 要將 它 映 射 成 適 應(yīng) 值 函 數(shù) 。n 一 般 是 一 個 實 值 函 數(shù) 。 該 函 數(shù) 就 是 遺 傳 算 法 中 指 導(dǎo) 搜 索 的 評 價 函 數(shù) 。4.5.1.1 遺 傳 算 法 的 工 作 過 程 3.遺 傳 算 法 的 三 個 算 子4.5.1.1 遺 傳 算 法 的 工 作 過 程 n 它 又 稱 復(fù) 制 (reproduction

54、) 、 繁 殖 算 子 。n 選 擇 是 從 種 群 中 選 擇 生 命 力 強(qiáng) 的 染 色 體 產(chǎn) 生 新 種 群 的過 程 。 依 據(jù) 每 個 染 色 體 的 適 應(yīng) 值 大 小 ， 適 應(yīng) 值 越 大 ，被 選 中 的 概 率 就 越 大 ， 其 子 孫 在 下 一 代 產(chǎn) 生 的 個 數(shù) 就越 多 。n 選 擇 操 作 是 建 立 在 群 體 中 個 體 的 適 應(yīng) 值 估 評 基 礎(chǔ) 上 的 。4.5.1.1 遺 傳 算 法 的 工 作 過 程 通 常 做 法 是 ： 對 于 一 個 規(guī) 模 為 N的 種 群 S,按 每 個 染 色 體 xi S的 選擇 概 率 P(xi)所 決 定

55、 的 選 中 機(jī) 會 , 分 N次 從 S中 隨 機(jī) 選 定 N個 染 色 體 , 并 進(jìn) 行 復(fù) 制 。4.5.1.1 遺 傳 算 法 的 工 作 過 程 Nj jii xfxfxP 1 )( )()( 這 里 的 選 擇 概 率 P(xi)的 計 算 公 式 為 n 它 又 稱 重 組 (recombination) 、 配 對 (breeding)算 子 ， 在 遺 傳算 法 中 起 著 核 心 作 用 。n 染 色 體 重 組 是 分 兩 步 驟 進(jìn) 行 的 :n首先在新復(fù)制的群體中隨機(jī)選取兩個個體n然后，沿著這兩個個體(字符串)隨機(jī)地取一個位置，二者互換從該位置起的末尾部分。 n 交

56、 叉 率 (crossover rate)就 是 參 加 交 叉 運 算 的 染 色 體 個 數(shù) 占 全 體 染色 體 總 數(shù) 的 比 例 ， 記 為 Pc,取 值 范 圍 一 般 為 0.4 0.99。4.5.1.1 遺 傳 算 法 的 工 作 過 程 4.5.1.1 遺 傳 算 法 的 工 作 過 程例 1:有 兩 個 用 二 進(jìn) 制 編 碼 的 個 體 A和 B。 長 度 L=5， A=a1a2a3a4a5 ，B=b1b2b3b4b5隨 機(jī) 選 擇 一 整 數(shù) k 1， L-1 ， 設(shè) k=4， 經(jīng) 交 叉 后 變?yōu)?：A = a1a2a3|a4a5 B = b1b2b3|b4b5 A=

57、 a1a2a3 b4b5 B = b1b2b3 a4a5s 1=01000101, s2=10011011可 以 看 做 是 原 染 色 體 s1和 s2的 子 代 染 色 體 。 例 2,設(shè) 染 色 體 s1=01001011, s2=10010101,交 換 其 后 4位 基 因 ,即 n 變 異 就 是 以 很 小 的 概 率 ， 隨 機(jī) 地 改 變 字 符 串 某 個 位 置 上 的 值 。變 異 操 作 是 按 位 （ bit） 進(jìn) 行 的 ， 即 把 某 一 位 的 內(nèi) 容 進(jìn) 行 變 異 。在 二 進(jìn) 制 編 碼 中 ， 就 是 將 某 位 0變 成 1， 1變 成 0。n 選

58、擇 和 交 叉 算 子 基 本 上 完 成 了 遺 傳 算 法 的 大 部 分 搜 索 功 能 ， 而變 異 則 增 加 了 遺 傳 算 法 找 到 接 近 最 優(yōu) 解 的 能 力 。n 變 異 率 (mutation rate)是 指 發(fā) 生 變 異 的 基 因 位 數(shù) 所 占 全 體 染色 體 的 基 因 總 位 數(shù) 的 比 例 ， 記 為 Pm， 取 值 范 圍 一 般 為0.0001 0.02。 它 保 證 了 遺 傳 算 法 的 有 效 性 。4.5.1.1 遺 傳 算 法 的 工 作 過 程 4.5.1.1 遺 傳 算 法 的 工 作 過 程 4.控 制 參 數(shù) 設(shè) 定4.5.1.

59、1 遺 傳 算 法 的 工 作 過 程 n 1.模 式 定 理4.5.1.2 遺 傳 算 法 的 理 論 基 礎(chǔ) n 1.模 式 定 理4.5.1.2 遺 傳 算 法 的 理 論 基 礎(chǔ) n 2 基 因 塊 假 設(shè)4.5.1.2 遺 傳 算 法 的 理 論 基 礎(chǔ) n 1. 遺 傳 算 法 的 處 理 對 象 是 問 題 參 數(shù) 的 編碼 個 體 （ 位 串 ）4.5.1.3 遺 傳 算 法 的 基 本 特 征 n 2. 遺 傳 算 法 的 搜 索 是 從 問 題 解 位 串 集 開 始 搜索 ， 而 不 是 從 單 個 解 開 始4.5.1.3 遺 傳 算 法 的 基 本 特 征 n 3.

60、遺 傳 算 法 只 使 用 目 標(biāo) 函 數(shù) (即 適 應(yīng) 值 )來 搜 索 ， 而 不 需 要 導(dǎo)數(shù) 等 其 他 輔 助 信 息n 4. 遺 傳 算 法 使 用 的 三 種 遺 傳 算 子 是 一 種 隨 機(jī) 操 作 ， 而 不 是 確定 性 規(guī) 則 n 5.隱 含 的 并 行 性n 6.易 介 入 到 已 有 的 模 型 中 ， 并 具 有 擴(kuò) 展 性 ； 易 于 同 別 的 技 術(shù) 結(jié)合 使 用4.5.1.3 遺 傳 算 法 的 基 本 特 征 4.5.2 優(yōu) 化 模 型 的 遺 傳 算 法 求 解 優(yōu) 化 模 型 的 計 算 是 遺 傳 算 法 最 基 本 的 也 是 最重 要 的 研

61、究 和 應(yīng) 用 領(lǐng) 域 之 一 。 一 般 說 來 ， 優(yōu) 化 計 算 問 題 通 常 帶 有 大 量 的 局部 極 值 點 ， 往 往 是 不 可 微 的 、 不 連 續(xù) 的 、 多 維的 、 有 約 束 條 件 的 、 高 度 非 線 性 的 NP完 全 問題 。 精 確 地 求 解 優(yōu) 化 問 題 的 全 局 最 優(yōu) 解 一 般 是 不可 能 的 。 4.5.2 優(yōu) 化 模 型 的 遺 傳 算 法 求 解4.5.2.1 優(yōu) 化 模 型 的 遺 傳 算 法 處 理4.5.2.2 實 例 1、 適 應(yīng) 值 函 數(shù) 優(yōu) 化4.5.2.1 優(yōu) 化 模 型 的 遺 傳 算 法 處 理 2、 約 束

62、 條 件 的 處 理4.5.2.1 優(yōu) 化 模 型 的 遺 傳 算 法 處 理 4.5.2.1 優(yōu) 化 模 型 的 遺 傳 算 法 處 理 3、 遺 傳 算 法 的 迭 代 終 止 條 件 步 1在 搜 索 空 間 U上 定 義 一 個 適 應(yīng) 度 函 數(shù) f(x)， 給 定 種 群 規(guī) 模 N， 交 叉 率 Pc和 變 異 率Pm， 代 數(shù) T；步 2隨 機(jī) 產(chǎn) 生 U中 的 N個 個 體 s1,s2,sN， 組 成 初 始 種 群 S=s1,s2,sN， 置 代 數(shù) 計數(shù) 器 t=1；步 3計 算 S中 每 個 個 體 的 適 應(yīng) 度 f()；步 4若 終 止 條 件 滿 足 ， 則 取

63、S中 適 應(yīng) 度 最 大 的 個 體 作 為 所 求 結(jié) 果 ， 算 法 結(jié) 束 。步 5按 選 擇 概 率 P(xi)所 決 定 的 選 中 機(jī) 會 ， 每 次 從 S中 隨 機(jī) 選 定 1個 個 體 并 將 其 染 色體 復(fù) 制 ， 共 做 N次 ， 然 后 將 復(fù) 制 所 得 的 N個 染 色 體 組 成 群 體 S1；步 6按 交 叉 率 Pc所 決 定 的 參 加 交 叉 的 染 色 體 數(shù) c， 從 S1中 隨 機(jī) 確 定 c個 染 色 體 ， 配對 進(jìn) 行 交 叉 操 作 ， 并 用 產(chǎn) 生 的 新 染 色 體 代 替 原 染 色 體 ， 得 群 體 S2； 步 7按 變 異 率

64、 Pm所 決 定 的 變 異 次 數(shù) m， 從 S2中 隨 機(jī) 確 定 m個 染 色 體 ， 分 別 進(jìn) 行 變異 操 作 ， 并 用 產(chǎn) 生 的 新 染 色 體 代 替 原 染 色 體 ， 得 群 體 S3；步 8將 群 體 S3作 為 新 一 代 種 群 ， 即 用 S3代 替 S， t=t+1， 轉(zhuǎn) 步 3； 基 本 遺 傳 算 法 步 聚 例 4.1利 用 遺 傳 算 法 求 解 區(qū) 間 0,31 上 的二 次 函 數(shù) y=x2的 最 大 值 。 y=x2 31 XY 分 析 原 問 題 可 轉(zhuǎn) 化 為 在 區(qū) 間 0, 31 中 搜 索 能 使 y取 最大 值 的 點 a的 問 題

65、。 那 么 ， 0, 31 中 的 點 x就 是 個 體 , 函 數(shù) 值 f(x)恰 好 就 可 以 作 為 x的 適 應(yīng) 度 ， 區(qū) 間 0, 31就 是 一 個 (解 )空 間 。 這 樣 , 只 要 能 給 出 個 體 x的 適 當(dāng) 染色 體 編 碼 , 該 問 題 就 可 以 用 遺 傳 算 法 來 解 決 。 解 (1) 設(shè) 定 種 群 規(guī) 模 ,編 碼 染 色 體 ， 產(chǎn) 生 初 始 種 群 。 將 種 群 規(guī) 模 設(shè) 定 為 4； 用 5位 二 進(jìn) 制 數(shù) 編 碼 染 色 體 ； 取下 列 個 體 組 成 初 始 種 群 S1: s1= 13 (01101), s2= 24 (1

66、1000) s3= 8 (01000), s4= 19 (10011) (2) 定 義 適 應(yīng) 度 函 數(shù) , 取 適 應(yīng) 度 函 數(shù) ： f (x)=x2 (3) 計 算 各 代 種 群 中 的 各 個 體 的 適 應(yīng) 度 , 并 對 其 染 色體 進(jìn) 行 遺 傳 操 作 ,直 到 適 應(yīng) 度 最 高 的 個 體 (即 31（ 11111） )出 現(xiàn) 為 止 。 再 計 算 種 群 S1中 各 個 體 的 選 擇 概 率 。 Nj jii xfxfxP 1 )()()(選 擇 概 率 的 計 算 公 式 為 由 此 可 求 得 P(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49 P(s 3) = P(8) = 0.06 P(s4) = P(19) = 0.31 賭 輪 選 擇 示 意s40.31s20.49 s10.14s30.06 賭輪選擇法 在 算 法 中 賭 輪 選 擇 法 可 用 下 面的 子 過 程 來 模 擬 : 在 0,1 區(qū) 間 內(nèi) 產(chǎn) 生 一 個均 勻 分 布 的 隨 機(jī) 數(shù) r。 若 rq1,則 染 色 體 x1被 選 中 。 若