《《智能算法及應(yīng)用》PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《《智能算法及應(yīng)用》PPT課件（67頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、智能優(yōu)化算法及應(yīng)用Intelligent Optimization Algorithms西安工程大學(xué)賀興時(shí) 背 景 傳 統(tǒng) 實(shí) 際 問 題 的 特 點(diǎn) ： 連 續(xù) 性 問 題 主 要以 微 積 分 為 基 礎(chǔ) ， 且 問 題 規(guī) 模 較 小 傳 統(tǒng) 的 方 法 （ 運(yùn) 籌 學(xué) ） ： 線 性 與 非 線 性 規(guī) 劃 、動(dòng) 態(tài) 規(guī) 劃 、 多 目 標(biāo) 規(guī) 劃 、 整 數(shù) 規(guī) 劃 等 ； 排 隊(duì) 論 、庫(kù) 存 論 、 對(duì) 策 論 、 決 策 論 等 。 追 求 準(zhǔn) 確 精 確 解 理 論 的 完 美 結(jié) 果 漂 亮 傳 統(tǒng) 的 評(píng) 價(jià) 方 法 ： 算 法 收 斂 性 （ 從 極 限 角 度 考 慮

2、 ） 收 斂 速 度 （ 線 性 、 超 線 性 、 二 次 收 斂 等 ） 傳 統(tǒng) 方 法 面 臨 的 挑 戰(zhàn) 現(xiàn) 代 問 題 的 特 點(diǎn) 離 散 性 問 題 主 要 以 組 合 優(yōu) 化 理 論 為 基 礎(chǔ) 不 確 定 性 問 題 隨 機(jī) 性 數(shù) 學(xué) 模 型 半 結(jié) 構(gòu) 或 非 結(jié) 構(gòu) 化 的 問 題 計(jì) 算 機(jī) 模 擬 、決 策 支 持 系 統(tǒng) 大 規(guī) 模 問 題 并 行 計(jì) 算 、 大 型 分 解 理 論 、近 似 理 論 現(xiàn) 代 優(yōu) 化 方 法追 求 滿 意 近 似 解 ； 實(shí) 用 性 強(qiáng) 解 決 實(shí) 際 問 題 現(xiàn) 代 優(yōu) 化 算 法 的 評(píng) 價(jià) 方 法 算 法 復(fù) 雜 性 內(nèi) 容

3、簡(jiǎn) 介1、 組 合 優(yōu) 化 問 題 是 解 決 離 散 問 題 的 優(yōu) 化 問題 運(yùn) 籌 學(xué) 分 支 。 通 過 數(shù) 學(xué) 方 法 的 研 究 去尋 找 離 散 事 件 的 最 優(yōu) 編 排 、 分 組 、 次 序 或 篩選 等 ， 可 以 涉 及 信 息 技 術(shù) 、 經(jīng) 濟(jì) 管 理 、 工 業(yè)工 程 、 交 通 運(yùn) 輸 和 通 信 網(wǎng) 絡(luò) 等 許 多 方 面 。典 型 的 優(yōu) 化 問 題 ： 0-1背 包 問 題 ， 旅 行 商 問 題 ，機(jī) 器 排 序 問 題 等 內(nèi) 容 簡(jiǎn) 介2、 模 擬 退 火 算 法 （ simulated annealing ）退 火 是 一 種 物 理 過 程 ，

4、金 屬 物 體 在 加 熱 至 一定 的 溫 度 后 ， 它 的 所 有 分 子 在 狀 態(tài) 空 間 中 自由 運(yùn) 動(dòng) 。 隨 著 溫 度 的 下 降 ， 這 些 分 子 逐 漸 停留 在 不 同 的 狀 態(tài) 。 在 溫 度 最 低 時(shí) ， 分 子 重 新以 一 定 的 結(jié) 構(gòu) 排 列 。 模 擬 退 火 算 法 的 直 觀 理解 是 ： 在 一 個(gè) 給 定 的 溫 度 ， 搜 索 從 一 個(gè) 狀 態(tài)隨 機(jī) 的 變 化 到 另 一 個(gè) 狀 態(tài) ， 每 一 個(gè) 狀 態(tài) 到 達(dá)的 次 數(shù) 服 從 一 個(gè) 概 率 分 布 。 當(dāng) 溫 度 很 低 時(shí) ，以 概 率 1停 留 在 最 優(yōu) 解 。 內(nèi) 容

5、 簡(jiǎn) 介3、 遺 傳 算 法 （ genetic algorithms）遺 傳 算 法 主 要 借 用 生 物 進(jìn) 化 中 “ 適 者 生 存 ”的 規(guī) 律 而 設(shè) 計(jì) 。 遺 傳 算 法 包 含 以 下 主 要 步驟 ： 第 一 是 對(duì) 優(yōu) 化 問 題 的 解 進(jìn) 行 編 碼 ； 第二 是 適 應(yīng) 函 數(shù) 的 構(gòu) 造 和 應(yīng) 用 ， 適 應(yīng) 函 數(shù) 基本 上 依 據(jù) 優(yōu) 化 問 題 的 目 標(biāo) 函 數(shù) 而 定 ； 第三 是 染 色 體 的 結(jié) 合 ； 最 后 是 變 異 。 內(nèi) 容 簡(jiǎn) 介3、 蟻 群 優(yōu) 化 算 法 （ Ant_Algorithm ） 的 基 本思 想 是 模 仿 螞 蟻

6、依 賴 信 息 素 進(jìn) 行 通 信 而 顯 示 出的 社 會(huì) 行 為 。 螞 蟻 在 行 動(dòng) 中 ， 會(huì) 在 他 們 經(jīng) 過 的地 方 留 下 一 些 化 學(xué) 物 質(zhì) ， 稱 之 為 “ 信 息 素 ” ，這 些 物 質(zhì) 能 被 同 一 蟻 群 中 后 來 的 螞 蟻 感 受 到 ，并 作 為 一 種 信 號(hào) 影 響 后 者 的 行 動(dòng) ， 螞 蟻 選 擇 這條 路 徑 的 可 能 性 比 選 擇 沒 有 這 些 物 質(zhì) 的 路 徑 的可 能 性 大 ， 后 到 者 留 下 的 信 息 素 會(huì) 對(duì) 原 有 的 信息 素 進(jìn) 行 加 強(qiáng) ， 這 樣 越 短 的 路 徑 會(huì) 被 越 多 的 螞蟻

7、訪 問 ， 這 個(gè) 過 程 一 直 持 續(xù) 到 所 有 的 螞 蟻 都 走最 短 的 那 一 條 路 徑 為 止 。 內(nèi) 容 簡(jiǎn) 介4、 粒 子 群 優(yōu) 化 算 法 (Particle Swarm optimization)是一 種 進(jìn) 化 計(jì) 算 技 術(shù) (Evolutionary Computation)，由 Eberhart博 士 和 K ennedy博 士 發(fā) 明 。 源 于 對(duì) 鳥群 捕 食 的 行 為 研 究 。 PSO中 ， 每 個(gè) 優(yōu) 化 問 題 的解 都 是 搜 索 空 間 中 的 一 只 鳥 。 我 們 稱 之 為 “ 粒子 ” 。 所 有 的 粒 子 都 有 一 個(gè) 由

8、被 優(yōu) 化 的 函 數(shù) 決定 的 適 應(yīng) 值 (fitness value)， 每 個(gè) 粒 子 還 有 一 個(gè) 速度 決 定 他 們 飛 翔 的 方 向 和 距 離 。 然 后 粒 子 們 就追 隨 當(dāng) 前 的 最 優(yōu) 粒 子 在 解 空 間 中 搜 索 。 內(nèi) 容 簡(jiǎn) 介5、 人 工 神 經(jīng) 網(wǎng) 絡(luò) (ARTIFICIAL NEURAL NETWORK， 簡(jiǎn) 稱 ANN)是 在 對(duì) 人 腦 組 織 結(jié) 構(gòu) 和 運(yùn)行 機(jī) 制 的 認(rèn) 識(shí) 理 解 基 礎(chǔ) 之 上 模 擬 其 結(jié) 構(gòu) 和 智 能行 為 的 一 種 工 程 系 統(tǒng) 。 神 經(jīng) 網(wǎng) 絡(luò) 的 基 本 原 理 為 ：大 腦 皮 層 每 一

9、 點(diǎn) 的 活 力 是 由 其 他 點(diǎn) 勢(shì) 能 釋 放 的綜 合 效 能 產(chǎn) 生 。 這 一 勢(shì) 能 同 下 面 的 因 數(shù) 有 關(guān) ：相 關(guān) 其 他 點(diǎn) 的 興 奮 次 數(shù) ； 興 奮 的 強(qiáng) 度 ； 與 其 不相 連 的 其 他 點(diǎn) 所 接 受 的 能 量 。 人 工 神 經(jīng) 網(wǎng) 絡(luò) 的建 立 和 應(yīng) 用 可 以 歸 結(jié) 為 三 個(gè) 步 驟 ： 網(wǎng) 絡(luò) 結(jié) 構(gòu) 的確 定 ， 關(guān) 聯(lián) 權(quán) 的 確 定 和 工 作 階 段 。 參 考 資 料 參 考 資 料 參 考 資 料 參 考 資 料 決 策 變 量有 限 點(diǎn) 集約 束 函 數(shù)目 標(biāo) 函 數(shù) , . ,0)(. )( min Dx xgts

10、xf .|)(min)(,: : ,0)(,|: ),( FxxfxfFxx Fxf xgDxxFD fFD 最 優(yōu) 解 ， 如 果可 行 解 （ 點(diǎn) ）目 標(biāo) 函 數(shù) 有 限 點(diǎn) 集可 行 域決 策 變 量 定 義 域 裝 包 ？問 題 ： 如 何 以 最 大 價(jià) 值件 物 品 單 位 價(jià) 值 ，第 件 物 品 單 位 體 積 ，第背 包 容 積 .,1: .,1: niic niiabii .1,0 i0 i 1 (1.3) .,1,1,0 (1.2) ,as.t. (1.1) maxn1i i1i nii in iiD x nix bx xc 物 品， 不 裝 第 物 品裝 第，其 中

11、決 策 變 量包 容 量 限 制總 價(jià) 值數(shù) 學(xué) 模 型 ： ij1 ij1min (1.4) s.t. 1. 1,2, , , (1.5) i 1. 1,2, , , ij iji jnjni d xx i nx j n 數(shù) 學(xué) 模 型 ： 總 路 長(zhǎng)只 從 城 市 出 來 一 次 , (1.6) 1,2 1, 1,2, , , (1.7) 0,1 , , 1,2, , , . (1.8) : i j , s : s 1, iji j sij ij ij jx s s n s nx i j n i jd i jx 只 走 入 城 市 一 次在 任 意 城 市 子 集 中 不 形 成 回 路決

12、 策 變 量其 中 城 市 與 城 市 之 間 的 距 離 集 合 中 元 素 的 個(gè) 數(shù) ，走 城 市 和 城 市0 .: , ,: , ,ij jiij jii jTSP d d i jTSP d d i j 之 間 的 路 徑 ， 不 走 城 市 和 城 市 之 間 的 路 徑對(duì) 稱 距 離非 對(duì) 稱 距 離 1 2 , ,. na a a 11m in. . 1, 1, 2 , , , 1, 1, 2 , , , 0 ,1 , 1, 2 , , ; 1, 2 , , , B : 1, 0 .B ibb n i ibi ibibBs t x i na x b Bx i n b Bi bx

13、 i b 數(shù) 學(xué) 模 型 ：其 中 裝 下 全 部 物 品 需 要 的 箱 子 ，第 物 品 裝 在 第 個(gè) 箱 子 ， 第 物 品 不 裝 在 第 個(gè) 箱 子 隨 城 市 增 多 ， 計(jì) 算 時(shí) 間 增 加 很 快 。 到 31個(gè) 城 市 時(shí) ，要 計(jì) 算 325年 。 描 述 算 法 的 好 壞 計(jì) 算 復(fù) 雜 性 討 論 計(jì) 算 時(shí) 間 與 問 題 規(guī) 模 之 間 的 關(guān) 系 。 以 目 前 二進(jìn) 制 計(jì) 算 機(jī) 中 的 存 儲(chǔ) 和 計(jì) 算 為 基 礎(chǔ) ， 以 理 論 的 形 式系 統(tǒng) 描 述 ， 是 評(píng) 估 算 法 性 能 的 基 礎(chǔ) 。 啟 發(fā) 式 算 法 （ heuristic a

14、lgorithm）定 義 1. 基 于 直 觀 或 經(jīng) 驗(yàn) 構(gòu) 造 的 算 法 ， 在 可 接 受的 花 費(fèi) （ 時(shí) 間 、 空 間 ） 下 ， 給 出 待 解 組 合 優(yōu) 化問 題 的 每 個(gè) 實(shí) 例 的 一 個(gè) 可 行 解 ， 該 可 行 解 與 最優(yōu) 解 偏 差 事 先 不 一 定 可 以 預(yù) 計(jì) .定 義 2. 啟 發(fā) 式 算 法 是 一 種 技 術(shù) ， 在 可 接 受 的 計(jì)算 費(fèi) 用 內(nèi) 尋 找 最 好 解 ， 但 不 保 證 該 解 的 可 行 性與 最 優(yōu) 性 ， 無 法 描 述 該 解 與 最 優(yōu) 解 的 近 似 程 度 。特 點(diǎn) （ 與 傳 統(tǒng) 優(yōu) 化 方 法 不 同 ）

15、： 憑 直 觀 和 經(jīng) 驗(yàn)給 出 算 法 ； 不 考 慮 所 得 解 與 最 優(yōu) 解 的 偏 離 程 度 . 20世 紀(jì) 90年 代 意 大 利 學(xué) 者 M Dorigo， V Maniezzo，A Colorni等 從 生 物 進(jìn) 化 的 機(jī) 制 中 受 到 啟 發(fā) ， 通 過 模擬 自 然 界 螞 蟻 搜 索 路 徑 的 行 為 ， 提 出 來 一 種 新 型 的 模擬 進(jìn) 化 算 法 蟻 群 算 法 ， 是 群 智 能 理 論 研 究 領(lǐng) 域的 一 種 主 要 算 法 。 用 該 方 法 求 解 TSP問 題 、 分 配 問 題 、job-shop調(diào) 度 問 題 ， 取 得 了 較 好

16、的 試 驗(yàn) 結(jié) 果 特 別 蟻群 算 法 在 求 解 復(fù) 雜 優(yōu) 化 問 題 （ 特 別 是 離 散 優(yōu) 化 問 題 ）方 面 有 一 定 優(yōu) 勢(shì) ， 螞 蟻 從 A點(diǎn) 出 發(fā) ， 速 度 相 同 ， 食 物 在 D點(diǎn) ， 可 能 隨 機(jī) 選 擇 路 線ABD或 ACD。 假 設(shè) 初 始 時(shí) 每 條 分 配 路 線 一 只 螞 蟻 ， 每 個(gè) 時(shí)間 單 位 行 走 一 步 ， 本 圖 為 經(jīng) 過 9個(gè) 時(shí) 間 單 位 時(shí) 的 情 形 ： 走ABD的 螞 蟻 到 達(dá) 終 點(diǎn) ， 而 走 ACD的 螞 蟻 剛 好 走 到 C點(diǎn) ， 為 一半 路 程 。 本 圖 為 從 開 始 算 起 ， 經(jīng) 過

17、18個(gè) 時(shí) 間 單 位 時(shí) 的 情 形 ：走 ABD的 螞 蟻 到 達(dá) 終 點(diǎn) 后 得 到 食 物 又 返 回 了 起 點(diǎn) A， 而 走 ACD的 螞 蟻 剛 好 走 到 D點(diǎn) 。 , |j), (iA n1,2,.,N Nji nnijd )( nl ii lldwf 1 1)( ),( 21 niiiw 11 ii n 初 始 的 蟻 群 算 法 是 基 于 圖 的 蟻 群 算 法 ， graph-based ant system,簡(jiǎn) 稱 為 GBAS， 是 由 Gutjahr W J在2000年 的 Future Generation Computing Systems提 出 的 .算

18、法 步 驟 如 下 ：STEP 0 對(duì) n個(gè) 城 市 的 TSP問 題 ，城 市 間 的 距 離 矩 陣 為 ， 給 TSP圖 中 的每 一 條 弧 賦 信 息 素 初 值 ， 假設(shè) m只 螞 蟻 在 工 作 ， 所 有 螞 蟻 都 從 同 一 城 市 出 發(fā)。 當(dāng) 前 最 好 解 是 。 , |j), (iA n1,2,.,N Nji nnijd )(),( ji |1)0( Aij ),2,1( nw 0i STEP 1 （ 外 循 環(huán) ） 如 果 滿 足 算 法 的 停 止 規(guī) 則 ， 則 停 止 計(jì) 算并 輸 出 計(jì) 算 得 到 的 最 好 解 。 否 則 使 螞 蟻 s從 起 點(diǎn) 出

19、 發(fā) ， 用 表 示 螞 蟻 s行 走 的 城 市 集 合 ， 初 始 為 空 集 ， 。STEP 2 (內(nèi) 循 環(huán) ) 按 螞 蟻 的 順 序 分 別 計(jì) 算 。 當(dāng)螞 蟻 在 城 市 i， 若 完 成 第 s只 螞 蟻 的 計(jì) 算 。 否 則 ， 若， 則 以 概 率 ，到 達(dá) j， ； 若則 到 達(dá) 重 復(fù) STEP 2。 ms 1)(sL)(sL 0i1 s m ( ) |(, ) , ( )Ls N l i l Al Ls 或 0( ) | ( , ) , ( ) L s N T l i l A l L s i 且 ( 1) ,( 1)ijij ijl T kp j Tk 0,ijp

20、 j T ( ) ( ) , :Ls Ls j i j 0( ) |(, ) , ( ) Ls N T l il Al Ls i 且0 0 0, ( ) ( ) , : ;i Ls Ls i i i STRP 3 對(duì) ， 若 ， 按 中 城 市 的 順序 計(jì) 算 路 徑 程 度 ； 若 ， 路 徑 長(zhǎng) 度 置 為 一 個(gè)無 窮 大 值 （ 即 不 可 達(dá) ） 。 比 較 m只 螞 蟻 中 的 路 徑 長(zhǎng)度 ， 記 走 最 短 路 徑 的 螞 蟻 為 t。若 ， 則 。 用 如 下 公 式 對(duì)W路 徑 上 的 信 息 素 痕 跡 加 強(qiáng) ， 對(duì) 其 他 路 徑 上 的 信 息素 進(jìn) 行 揮 發(fā)

21、。 得 到 新 的 ， 重 復(fù) 步 驟 STEP 1。1 s m ( )L s N ( )L s( )L s N( ( ) ( ( )f L t f L W ( )W L t 111( ) (1 ) ( 1) ( , )( ) (1 ) ( 1) ( , )kij k ijij k ijk k i j WWk k i j W 為 上 的 一 條 弧不 是 上 的 一 條 弧( ), : 1ij k k k 在 STEP 3 中 ， 揮 發(fā) 因 子 對(duì) 于 一 個(gè) 固 定 的 ，滿 足并 且 經(jīng) 過 k次 揮 發(fā) ， 非 最 優(yōu) 路 徑 的 信 息 素 逐 漸 減 少 至 消 。ln1 ,ln(

22、 1)k k k Kk k 1K 1 kk 以 上 算 法 中 ， 在 螞 蟻 的 搜 尋 過 程 中 ， 以 信 息 素 的概 率 分 布 來 決 定 從 城 市 i到 城 市 j的 轉(zhuǎn) 移 。 算 法 中 包 括 信 息 素 更 新 的 過 程 1 信 息 素 揮 發(fā) （ evaporation): 信 息 素 痕 跡 的 揮 發(fā) 過程 是 每 個(gè) 連 接 上 的 信 息 素 痕 跡 的 濃 度 自 動(dòng) 逐 漸 減 弱 的過 程 ， 由 表 示 ， 這 個(gè) 揮 發(fā) 過 程 主 要用 于 避 免 算 法 過 快 地 向 局 部 最 優(yōu) 區(qū) 域 集 中 ， 有 助 于 搜索 區(qū) 域 的 擴(kuò) 展

23、 。(1 ) ( ) k ij k 2 信 息 素 增 強(qiáng) （ reinforcement):增 強(qiáng) 過 程 是 蟻 群 優(yōu)化 算 法 中 可 選 的 部 分 ， 稱 為 離 線 更 新 方 式 （ 還 有 在 線更 新 方 式 ） 。 這 種 方 式 可 以 實(shí) 現(xiàn) 由 單 個(gè) 螞 蟻 無 法 實(shí) 現(xiàn)的 集 中 行 動(dòng) 。 也 就 是 說 ， 增 強(qiáng) 過 程 體 現(xiàn) 在 觀 察 蟻 群 （m只 螞 蟻 ） 中 每 只 螞 蟻 所 找 到 的 路 徑 ， 并 選 擇 其 中 最優(yōu) 路 徑 上 的 弧 進(jìn) 行 信 息 素 的 增 強(qiáng) ， 揮 發(fā) 過 程 是 所 有 弧都 進(jìn) 行 的 ， 不 于

24、螞 蟻 數(shù) 量 相 關(guān) 。 這 種 增 強(qiáng) 過 程 中 進(jìn) 行的 信 息 素 更 新 稱 為 離 線 的 信 息 素 更 。在 STEP 3中 ， 蟻 群 永 遠(yuǎn) 記 憶 到 目 前 為 止 的 最 優(yōu) 解 。 可 以 驗(yàn) 證 ， 下 式 滿 足 ：即 是 一 個(gè) 隨 機(jī) 矩 陣 。四 個(gè) 城 市 的 非 對(duì) 稱 TSP問 題 ， 距 離 矩 陣 和 城 市 圖 示 如 下 ：( , ) ( ) 1, 0iji j A k k ( )k 0 1 0.5 11 0 1 1( ) 1.5 5 0 11 1 1 0 ijD d 假 設(shè) 共 4只 螞 蟻 ， 所 有 螞 蟻 都 從 城 市 A出 發(fā)

25、， 揮 發(fā) 因 子 。 此 時(shí) ， 觀 察 GBAS的 計(jì) 算 過 程 。 矩 陣 共 有 12條 弧 ， 初 始 信 息 素 記 憶 矩 陣 為 ：1 , 1,2,32k k 0 112 112 112112 0 112 112(0) ( (0) 112 112 0 112112 112 112 0 ij 執(zhí) 行 GBAS算 法 的 步 驟 2， 設(shè) 螞 蟻 的 行 走 路 線 分 別 為 ：當(dāng) 前 最 優(yōu) 解 為 ， 這 個(gè) 解 是 截 止 到 當(dāng) 前 的 最 優(yōu) 解 ， 碰 巧 是實(shí) 際 最 優(yōu) 解 1: , ( 1) 4;2: , ( 2) 3.5;3: , ( 3) 8;4: , (

26、 4) 4.5;W A B C D A f WW A C D B A f WW A D C B A f WW A B D C A f W 第 一 只第 二 只第 三 只第 四 只 按 算 法 步 驟 3的 信 息 素 更 新 規(guī) 則 ， 得 到 更 新 矩 陣這 是 第 一 次 外 循 環(huán) 結(jié) 束 的 狀 態(tài) 。0 1 24 1 6 1 241 6 0 1 24 1 24(1) ( (1) 1 24 1 12 0 1 61 24 1 6 1 24 0ij 重 復(fù) 外 循 環(huán) ， 由 于 上 一 次 得 到 的 W2已 經(jīng) 是 全 局最 優(yōu) 解 ， 因 此 按 算 法 步 驟 3的 信 息 素

27、更 新 規(guī) 則 ，無 論 螞 蟻 如 何 行 走 ， 都 只 是 對(duì) W2路 線 上 的 城 市信 息 素 進(jìn) 行 增 強(qiáng) ， 其 他 的 城 市 信 息 素 進(jìn) 行 揮 發(fā) 。得 到 更 新 矩 陣這 是 第 一 次 外 循 環(huán) 結(jié) 束 的 狀 態(tài) 。0 1 48 5 24 1 485 24 0 1 48 1 48(2) ( (2) 1 48 1 48 0 5 241 48 5 24 1 48 0 ij 重 復(fù) 外 循 環(huán) ， 由 于 W2全 局 最 優(yōu) 解 ， GBAS只 記錄 第 一 個(gè) 最 優(yōu) 解 ， 因 此 一 但 得 到 了 全 局 最 優(yōu) 解 ，信 息 素 的 更 新 將 不 再

28、 依 賴 于 以 群 的 行 走 路 線 ，而 只 是 不 斷 增 強(qiáng) 最 優(yōu) 路 線 的 信 息 素 ， 同 時(shí) 進(jìn) 行揮 發(fā) 。 第 三 次 外 循 環(huán) 后 得 到 的 信 息 素 矩 陣 為 ：0 1 96 11 48 1 9611 48 0 1 96 1 96(3) ( (3) 1 96 1 96 0 11 481 96 11 48 1 96 0 ij 螞 蟻 以 一 定 的 概 率 從 城 市 i到 城 市 j進(jìn) 行 轉(zhuǎn) 移 ， 信息 素 的 更 新 在 STEP 3 完 成 ， 并 隨 K而 變 化 。 假設(shè) 第 K次 外 循 環(huán) 后 得 到 信 息 素 矩 陣 ，得 到 當(dāng) 前

29、最 優(yōu) 解 。第 K次 循 環(huán) 前 的 信 息 素 和 最 優(yōu) 解 為 ，經(jīng) 過 第 K次 外 循 環(huán) 后 ， 得 到 。 由于 螞 蟻 的 一 步 轉(zhuǎn) 移 概 率 是 隨 機(jī) 的 ， 從 到 也 是 隨 機(jī) 的 ， 是 一 個(gè) 馬 爾 可 夫 過 程 。( ) ( ( )|(, ) )ijk k i j A ( )W k ( 1), ( 1)k W k ( ), ( )k W k ( 1), ( 1)k W k ( ), ( )k W k 一 般 蟻 群 算 法 的 框 架 和 GBAS基 本 相 同 ， 有 三 個(gè) 組 成部 分 ： 蟻 群 的 活 動(dòng) ； 信 息 素 的 揮 發(fā) ； 信 息 素 的 增 強(qiáng) ；主 要 體 現(xiàn) 在 前 面 的 算 法 中 步 驟 2和 步 驟 3中 的 轉(zhuǎn) 移 概 率公 式 和 信 息 素 更 新 公 式 。