《《群集智能算法》PPT課件》由會員分享，可在線閱讀，更多相關(guān)《《群集智能算法》PPT課件（55頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第 7章 群 集 智 能 算 法 第 7章 群 集 智 能 算 法 7.1群 集 智 能 算 法 的 研 究 背 景 7.1群 集 智 能 算 法 的 研 究 背 景對 群 集 智 能 的 研 究 是 受 社 會 性 昆 蟲 行 為 的 啟 發(fā) ，從 事 計(jì) 算 研 究 的 學(xué) 者 通 過 對 社 會 性 昆 蟲 的 模 擬 產(chǎn) 生了 一 系 列 對 傳 統(tǒng) 問 題 的 新 的 解 決 方 法 ， 這 些 研 究 就是 群 集 智 能 的 研 究 。群 體 (Swarm)指 的 是 “ 一 組 相 互 之 間 可 以 進(jìn) 行 直接 通 信 或 者 間 接 通 信 (通 過 改 變 局 部 環(huán)

2、境 )的 主 體 ，這 組 主 體 能 夠 合 作 進(jìn) 行 分 布 問 題 求 解 ” ；群 集 智 能 (Swarm Intelligence)指 的 是 “ 無 智 能 的主 體 通 過 合 作 表 現(xiàn) 出 智 能 行 為 的 特 性 ” 。 7.2群 集 智 能 的 基 本 算 法 介 紹 蟻 群 算 法 是 受 到 上 世 紀(jì) 五 十 年 代 仿 生 學(xué) 的 啟 發(fā) ，由 意 大 利 學(xué) 者 M.Dorigo等 人 首 先 提 出 的 一 種 新 型 的模 擬 進(jìn) 化 算 法 ， 該 算 法 在 求 解 組 合 優(yōu) 化 問 題 中 體 現(xiàn)出 優(yōu) 良 的 特 性 。作 為 一 種 基 于

3、 種 群 的 啟 發(fā) 式 搜 索 算 法 ， 它 能 很 好的 利 用 蟻 群 的 集 體 尋 優(yōu) 特 征 來 尋 找 蟻 穴 和 食 物 之 間的 最 短 路 徑 。 因 此 ， 被 廣 泛 應(yīng) 用 于 旅 行 商 問 題（ TSP） 、 Job-shop調(diào) 度 問 題 、 指 派 問 題 等 等 ， 都取 得 了 良 好 的 仿 真 試 驗(yàn) 結(jié) 果 。 7.2.1蟻 群 算 法蟻 群 算 法 的 模 擬 試 驗(yàn)l該 試 驗(yàn) 在 各 個 螞 蟻 在 沒 有 事 先 告 訴 它 們 食 物 在 什 么地 方 的 前 提 下 開 始 尋 找 食 物 。 當(dāng) 一 只 找 到 食 物 以 后 ，它

4、會 向 環(huán) 境 釋 放 一 種 信 息 素 ， 吸 引 其 他 的 螞 蟻 過 來 ，這 樣 越 來 越 多 的 螞 蟻 會 找 到 食 物 ！l但 有 些 螞 蟻 并 沒 有 像 其 它 螞 蟻 一 樣 總 重 復(fù) 同 樣 的 路 ，它 們 會 另 辟 蹊 徑 ， 如 果 令 開 辟 的 道 路 比 原 來 的 其 他道 路 更 短 ， 那 么 更 多 的 螞 蟻 被 吸 引 到 這 條 較 短 的 路上 來 。 最 后 ， 經(jīng) 過 一 段 時(shí) 間 運(yùn) 行 ， 可 能 會 出 現(xiàn) 一 條最 短 的 路 徑 被 大 多 數(shù) 螞 蟻 重 復(fù) 著 。 這 個 試 驗(yàn) 程 序 的 每 個 螞 蟻 的

5、 核 心 程 序 編 碼 不 過 100多 行 。 為 什 么 這 么 簡 單 的 程 序 會 讓 螞 蟻 干 這 樣 復(fù) 雜的 事 情 ？答 案 是 ： 巧 妙 地 利 用 簡 單 規(guī) 則 來 實(shí) 現(xiàn) 集 體 智 慧 。 每 只 螞 蟻 并 不 是 像 我 們 想 象 的 需 要 知 道 整 個 世 界 的信 息 ， 它 們 其 實(shí) 只 關(guān) 心 很 小 范 圍 內(nèi) 的 眼 前 信 息 ， 而且 根 據(jù) 這 些 局 部 信 息 利 用 幾 條 簡 單 的 規(guī) 則 進(jìn) 行 決 策 ，這 樣 在 蟻 群 這 個 集 體 里 ， 復(fù) 雜 性 的 行 為 就 會 凸 現(xiàn) 出來 。 這 些 規(guī) 則 就

6、是 下 面 所 述 的 簡 單 的 6條 規(guī) 則 ACO 基 本 規(guī) 則 （ 一 、 二 ）l 范 圍 ： 螞 蟻 觀 察 到 的 范 圍 是 一 個 方 格 世 界 ， 螞 蟻 有 一 個 參 數(shù)為 速 度 半 徑 （ 一 般 是 3） ， 那 么 它 能 觀 察 到 的 范 圍 就是 3*3個 方 格 世 界 。l 環(huán) 境 ： 螞 蟻 所 在 的 環(huán) 境 是 一 個 虛 擬 的 世 界 ， 其 中 有 障 礙 物 ，有 別 的 螞 蟻 ， 還 有 信 息 素 ， 信 息 素 有 兩 種 ， 一 種 是 找到 食 物 的 螞 蟻 灑 下 的 食 物 信 息 素 ， 一 種 是 找 到 窩 的

7、 螞蟻 灑 下 的 窩 的 信 息 素 。 環(huán) 境 以 一 定 的 速 率 讓 信 息 素 消失 。 ACO 基 本 規(guī) 則 （ 三 ） ACO 基 本 規(guī) 則 （ 四 ） ACO 基 本 規(guī) 則 （ 五 、 六 ） 有 兩 條 路 徑 通 向 食 物 螞 蟻 聚 集 到 較 短 的 路 徑 l 其 次 ， 螞 蟻 要 有 一 定 的 隨 機(jī) 性 ， 雖 然 有 了 固 定 的方 向 ， 但 它 也 不 能 像 一 個 小 球 一 樣 直 線 運(yùn) 動 下 去 ，而 是 有 一 個 隨 機(jī) 的 干 擾 。 這 樣 就 使 得 螞 蟻 運(yùn) 動 起來 具 有 了 一 定 的 目 的 性 ， 盡 量

8、保 持 原 來 的 方 向 ，但 又 有 新 的 試 探 ， 尤 其 當(dāng) 碰 到 障 礙 物 的 時(shí) 候 它 會立 即 改 變 方 向 。l 這 可 以 看 成 一 種 選 擇 的 過 程 ， 也 就 是 環(huán) 境 的 障 礙物 讓 螞 蟻 沿 著 是 某 個 方 向 正 確 ， 而 其 他 方 向 則 不正 確 。 在 有 一 只 螞 蟻 找 到 了 食 物 后 ， 其 他 螞 蟻 會沿 著 信 息 素 很 快 找 到 食 物 。 蟻 群 算 法 過 程 模 擬 用 蟻 群 算 法 解 決 問 題 的 步 驟1. 能 夠 把 待 解 決 的 問 題 用 圖 的 形 式 抽 象 表 達(dá) 出 來

9、；2. 具 體 定 義 各 種 參 數(shù) ， 如 范 圍 、 信 息 素 消 逝 函 數(shù) 等 ；3. 為 算 法 中 的 螞 蟻 制 定 相 應(yīng) 的 移 動 規(guī) 則 ；4. 選 擇 一 種 適 應(yīng) 的 蟻 群 優(yōu) 化 算 法 并 將 其 合 理 地 應(yīng) 用到 自 己 的 問 題 解 決 方 案 中 去 ；5. 適 當(dāng) 調(diào) 整 所 應(yīng) 用 的 蟻 群 算 法 中 的 對 應(yīng) 參 數(shù) 以 達(dá) 到較 好 的 實(shí) 驗(yàn) 效 果 . 2. 應(yīng) 用 蟻 群 算 法 求 解 TSP問 題 1 ( ) ( ) ij ij ijt n t 1 m ki j i jk , k ij 0,k kij QL 若 第 只

10、螞 蟻 在 本 次 循 環(huán) 中 經(jīng) 過否 則 否 則 之 間 經(jīng) 過和只 螞 蟻 在 時(shí) 刻若 第,0 ij1ttk,ijkij dQ 否 則 之 間 經(jīng) 過和只 螞 蟻 在 時(shí) 刻若 第,0 ij1ttk,Qkij 7.2.2 flock算 法 7.2.2 flock算 法分 離 列 隊(duì) 聚 合 l 躲 避 規(guī) 則 的 作 用 是 為 主 體 提 供 了 使 它 繞 過 障 礙 和避 免 碰 撞 的 能 力 。 這 種 控 制 行 為 是 這 樣 完 成 的 ：通 過 賦 予 每 個 主 體 “ 向 前 看 ” 一 段 距 離 的 能 力 ，決 定 與 一 些 對 象 的 碰 撞 是 否 可

11、 能 ， 然 后 調(diào) 整 航 向以 避 免 碰 撞 。l Flock技 術(shù) 通 過 這 四 個 簡 單 的 規(guī) 則 最 終 模 擬 出 逼真 的 群 體 行 為 ， 更 有 意 思 的 是 這 種 移 動 算 法 本 身是 無 狀 態(tài) 的 ： 在 移 動 更 新 中 ， 不 記 錄 任 何 信 息 。 l 在 每 次 更 新 循 環(huán) 中 ， 每 只 boid都 將 重 新 評 估 其 環(huán)境 。 這 樣 不 但 降 低 了 內(nèi) 存 需 求 ， 同 時(shí) 讓 物 群 能 夠?qū)?不 斷 變 化 的 環(huán) 境 狀 況 做 出 實(shí) 時(shí) 的 反 應(yīng) 。 因 此 ，物 群 將 具 備 突 發(fā) 行 為 的 （ E

12、mergent Behavior） 特性 ， 即 物 群 中 的 所 有 成 員 都 對 要 前 往 何 方 一 無 所知 ， 但 作 為 一 個 整 體 行 動 ， 避 開 障 礙 物 和 天 敵 ，并 保 持 若 即 若 離 。 7.3 集 智 系 統(tǒng) 介 紹 7.3.1 人 工 魚人 工 魚 群 體 是 一 種 典 型 的 多 智 能 主 體 （ Multiple Intelligent Agent） 的 分 布 式 人 工 智 能 系 統(tǒng)（ distributive artificial intelligent system） 。中 國 青 年 學(xué) 者 涂 曉 媛 研 究 開 發(fā) 的

13、新 一 代 計(jì) 算 機(jī) 動 畫“ 人 工 魚 ” 被 學(xué) 術(shù) 界 稱 之 為 “ 曉 媛 魚 ” （ Xiaoyuans fish） ， 她 發(fā) 表 的 論 文 “ 人 工 動 物 的 計(jì) 算 機(jī) 動畫 ” (artificial animals for computer animation: biomechanics , locomotion, perception and behavior)，在 1996年 獲 國 際 計(jì) 算 學(xué) 會 ACM最 佳 博 士 論 文 獎 。 l 涂 曉 媛 研 究 開 發(fā) 的 “ 人 工 魚 ” 構(gòu) 成 了 棲 息 在 虛 擬海 底 世 界 中 人 工 魚

14、群 的 社 會 ， 其 中 ， 每 條 “ 人 工魚 ” 都 是 一 個 自 主 的 智 能 體 （ autonomous intelligent agent） ， 都 可 以 獨(dú) 立 地 活 動 ， 也 可 以相 互 交 往 。 每 條 魚 都 表 現(xiàn) 出 某 些 人 工 智 能 ， 如 ：自 激 發(fā) （ self-animating） 、 自 學(xué) 習(xí) （ self-learning） 、 自 適 應(yīng) （ self-adapting） 等 智 能 特 性 . l 會 產(chǎn) 生 相 應(yīng) 的 智 能 行 為 ， 如 ： 因 饑 餓 而 激 發(fā) 尋 食 、進(jìn) 食 行 為 ； 有 性 欲 而 激 發(fā)

15、求 愛 行 為 ； 能 吸 取 其 他魚 被 魚 鉤 釣 住 的 教 訓(xùn) ， 而 不 去 吞 食 有 鉤 的 魚 餌 ；能 適 應(yīng) 有 鯊 魚 的 社 會 環(huán) 境 ， 逃 避 被 捕 食 的 危 險(xiǎn) 等 。人 工 魚 群 的 社 會 具 有 某 些 自 組 織 （ self-organizing）能 力 和 智 能 集 群 行 為 ， 如 ： 人 工 魚 群 體 在 漫 游 中遇 到 障 礙 物 等 ， 會 識 別 障 礙 改 變 隊(duì) 形 ， 繞 過 障 礙后 ， 又 重 組 隊(duì) 列 ， 繼 續(xù) 前 進(jìn) 。 7.3.1 人 工 魚人 工 魚 與 動 畫 魚區(qū) 別 ：l “ 人 工 魚 ” 具

16、有 “ 人 工 生 命 ” 和 自 然 魚 的 某 些 生 命特 征 。 l 在 一 般 的 計(jì) 算 機(jī) 動 畫 中 ， 創(chuàng) 作 者 需 要 在 動 畫 設(shè) 計(jì) 和程 序 編 制 中 確 定 動 畫 魚 的 所 有 動 作 的 細(xì) 節(jié) ， 預(yù) 先 知道 動 畫 魚 的 全 部 動 作 過 程 。 然 而 ， 人 工 魚 的 創(chuàng) 作 者并 不 去 設(shè) 計(jì) 和 規(guī) 定 每 條 魚 的 動 作 和 行 為 的 細(xì) 節(jié) ， 也不 能 預(yù) 知 人 工 魚 群 中 可 能 發(fā) 生 的 各 種 具 體 動 作 和 實(shí)際 行 為 。 7.3.1 人 工 魚 7.3.1 人 工 魚“ 人 工 魚 ” 的 動 畫

17、 創(chuàng) 作 方 法 和 技 術(shù) ， 已 經(jīng) 突 破 了傳 統(tǒng) 的 計(jì) 算 機(jī) 動 畫 的 框 架 。 首 先 ， “ 人 工 魚 ” 不 僅 有 逼 真 于 “ 自 然 魚 ” 的 外形 和 彩 色 ， 而 且 具 有 類 似 于 “ 自 然 魚 ” 的 運(yùn) 動 和 姿態(tài) 。 其 次 ， “ 人 工 魚 ” 不 僅 具 有 “ 自 然 魚 ” 的 形 態(tài) ，而 且 具 有 “ 自 然 魚 ” 類 似 的 生 命 特 性 “活 性 ” 。 再 次 ， “ 人 工 魚 ” 是 具 有 人 工 智 能 的 “ 靈 巧 魚 ” ，而 傳 統(tǒng) 的 “ 動 畫 魚 ” 是 程 序 化 的 “ 木 偶 魚 ”

18、 。 最 后 ， “ 人 工 魚 ” 是 具 有 各 種 不 同 的 人 工 魚 的 魚群 社 會 。 “人 工 魚 ” 的 形 態(tài) （ 外 形 、 顏 色 、 姿 態(tài) ） 和 “ 自 然魚 ” 非 常 相 似 ， 幾 乎 達(dá) 到 了 “ 以 假 亂 真 ” 的 程 度 。在 一 次 國 際 會 議 上 ， 涂 曉 媛 演 示 了 “ 人 工 魚 ” 的錄 像 ， 人 們 看 到 屏 幕 上 一 群 色 彩 美 麗 、 活 潑 可 愛的 熱 帶 魚 ， 在 海 水 中 漫 游 ， 逼 真 的 外 形 、 生 動 的姿 態(tài) ， 伴 隨 著 水 流 的 運(yùn) 動 ， 還 以 為 是 在 水 族 館

19、中拍 攝 的 真 熱 帶 魚 的 錄 像 。 直 到 涂 曉 媛 把 “ 人 工 魚 ”的 彩 色 消 隱 ， 變 成 黑 白 的 魚 ， 再 把 “ 人 工 魚 ” 的肌 肉 剝 離 ， 剩 下 一 群 熱 帶 魚 的 骨 架 在 游 泳 ， 才 確信 這 是 計(jì) 算 機(jī) 動 畫 的 ” 人 工 魚 ” 。 “人 工 魚 ” 和 一 般 的 “ 動 畫 魚 ” 的 不 同 之 處 還 在 于 ：l “ 人 工 魚 ” 具 有 某 些 自 然 魚 的 “ 本 能 ” 性 。l “ 人 工 魚 ” 能 感 知 其 他 的 ” 人 工 魚 ” 和 海 底 環(huán) 境 ，有 “ 魚 肉 ” 、 “ 魚

20、骨 ” 、 “ 魚 嘴 ” 、 “ 魚 頭 ” 、“ 魚 尾 ” 、 “ 魚 鰭 ” 等 ， 能 產(chǎn) 生 類 似 于 自 然 魚 的隨 意 動 作 和 行 為 。 例 如 ： 人 工 魚 有 性 欲 ； 人 工 魚有 饑 餓 感 ； 人 工 魚 有 學(xué) 習(xí) 能 力 ， 若 一 條 魚 誤 吞 了魚 餌 ， 被 魚 鉤 鉤 上 ， 會 進(jìn) 行 掙 扎 ， 而 其 他 的 “ 人工 魚 ” ， 就 會 吸 取 教 訓(xùn) 不 再 上 當(dāng) ， 不 去 吞 食 帶 鉤的 魚 餌 ， 離 開 釣 魚 的 水 域 ； “ 人 工 魚 ” 有 恐 懼 感 ，如 果 發(fā) 現(xiàn) 兇 惡 的 鯊 魚 來 侵 犯 ， 都

21、 迅 速 散 開 ， 東 奔西 逃 ， 脫 離 危 險(xiǎn) ， 。 7.3.1 人 工 魚 圖 12.8 雄 魚 向 雌 魚 求 愛 圖 12.9 侵 略 者 鯊 魚 偷 襲 被 撲 食 的 小 魚 群 7.3.1 人 工 魚 飼 養(yǎng) 場 模 式 （ Terrarium Mode） ： 這 種 模 式 給 用戶 提 供 了 兩 種 選 擇 。l 用 戶 可 以 獨(dú) 立 運(yùn) 行 ， 無 須 與 其 他 節(jié) 點(diǎn) 連 接 。 在 這種 情 況 下 ， 屏 幕 上 顯 示 的 生 態(tài) 系 統(tǒng) 就 代 表 了 整 個生 態(tài) 環(huán) 境 。 這 種 模 式 最 適 合 于 對 我 們 開 發(fā) 出 來 的生 物 進(jìn)

22、 行 測 試 。l 用 戶 也 可 以 選 擇 加 入 到 一 組 特 定 的 節(jié) 點(diǎn) 環(huán) 境 中 ，所 有 連 入 此 環(huán) 境 的 計(jì) 算 機(jī) 共 同 組 成 一 個 小 型 生 態(tài)系 統(tǒng) 。 7.3.2 Terrarium世 界 加 入 特 定 節(jié) 點(diǎn) 組 的 方 法 非 常 簡 單 ， 每 個 用 戶 選 擇一 個 特 定 的 專 網(wǎng) ， 并 在 Terrarium控 制 臺 的“ Channel”一 項(xiàng) 中 輸 入 一 個 事 先 約 定 好 的 字 串 ，就 可 以 加 入 該 網(wǎng) 絡(luò) 了 。 輸 入 字 串 后 ， 用 戶 的 計(jì)算 機(jī) 只 與 那 些 輸 入 了 相 同 字 串

23、的 計(jì) 算 機(jī) 構(gòu) 成 一個 獨(dú) 立 的 對 等 網(wǎng) 絡(luò) ， 并 一 同 組 建 生 態(tài) 系 統(tǒng) 。 生 物 圈 模 式 （ Ecosystem Mode） ： 這 是 游 戲 的 標(biāo)準(zhǔn) 模 式 。 全 世 界 所 有 連 入 游 戲 的 計(jì) 算 機(jī) 共 同 構(gòu) 成 一 個完 整 的 生 態(tài) 系 統(tǒng) 。 每 個 參 與 者 的 計(jì) 算 機(jī) 只 是 該 生 態(tài) 系統(tǒng) 的 一 個 局 部 場 景 。 在 上 述 兩 種 模 式 下 ， 開 發(fā) 者 都 可 以 使 用 Terrarium類 庫 、 .NET框 架 開 發(fā) 包 和 Visual Studio .NET工 具 隨意 創(chuàng) 建 它 們 自 己 的 生 物 。 或 者 ， 可 以 簡 單 地 把Terrarium當(dāng) 作 一 個 獨(dú) 立 運(yùn) 行 的 應(yīng) 用 程 序 或 是 屏 幕 保護(hù) 程 序 運(yùn) 行 ， 并 通 過 Terrarium觀 看 其 他 開 發(fā) 者 創(chuàng) 建的 生 物 在 生 態(tài) 系 統(tǒng) 中 為 生 存 而 戰(zhàn) 。 7.4 群 集 智 能 的 優(yōu) 缺 點(diǎn) 7.4 群 集 智 能 的 優(yōu) 缺 點(diǎn) 7.4 群 集 智 能 的 優(yōu) 缺 點(diǎn)