更 一般性 的 演算法 ， 稱為 模擬 退火 法 （ ５ ） 。 模擬 退火 法 之所以 被 視為 一般性 問題 解法 ， 是 因為 它 與 所 欲 處理 問題 的 詳細 機制 無關 ， 只要 找出 描述 問題 的 價值 函數 ， 再 將 整 個 問題 視為 一 熱力學 系統 ， 使用 統計 力學 及 蒙地卡羅 法 （ ＭｏｎｔｅｃａｒｌｏＭｅｔｈｏｄ ） （ ６ ） 模擬 的 技巧 ， 使 此 熱力學 系統 從 高溫 混亂 狀態 慢慢 降至 低溫 有 序 狀態 〔 註 ： 降溫 速度 不可 太 快 否則 會 造成 焠冷 （ ｑｕｅｎｃｈ ） 現象 ， 使 系統 陷 在 局部 極值 （ ｌｏｃａｌｍｉｎｉｍｕｍ ） 而 非 真正 的 全 域 極值 （ ｇｌｏｂａｌｍｉｎｉｍｕｍ ） 〕 ， 則 可以 找到 價值 函數 的 極值 所 對應 的 組態 。 雖然 模擬 退火 法 不 受 問題 的 限制 ， 但 其 效率 並 不 高 ， 若要 得到 接近 極值 ３％ 的 誤差 內 ， 費時 （ 也 就 是 複雜 程度 ） 約 （ ｎ３ｌｏｇｎ ） （ ７ ） 。 想 獲到 更 精準 的 極值 ， 就 必須 耗費 更 長 的 時間 。 五 、 混合型 演算法 （ ＨｙｂｒｉｄＡｌｇｏｒｉｔｈｍ ） （ ） 年 中心 同仁 發展出 混合型 演算法 。 這 種 演算法 基本 上 由 三 部份 組合 而 成 ， 首先 找到 一 個 全 域 結構 （ ｇｌｏｂａｌｓｔｒｕｃｔｕｒｅ ） 不錯 的 雛形 組態 〔 註 ： 因為 形成 此 組態 ， 可 用 許多 不同 方法 得到 ， 例如 空間 曲線 填充 法 （ ＳｐａｃｅＦｉｌｌｉｎｇＣｕｒｖｅ ） （ ８ ） ， 最 近鄰 法 （ ＮｅａｒｅｓｔＮｅｉｇｈｂｏｕｒ ） 等等 ， 此 組態 是 具有 可 學習 性質 ， 所以 稱 它 為 Ｈｅｕｒｉｓｔｉｃ 〕 ， 接著 將 雛形 組態 看做 一 熱力學 系統 ， 再 利用 微 正則 系綜 蒙地卡羅 法 （ ＭｉｃｒｏｃａｎｏｎｉｃａｌＥｎｓｅｍｂｌｅＭｏｎｔｅＣａｒｌｏｍｅｔｈｏｄ ） （ ９ ） 去 決定 雛形 組態 所 對應 之 溫度 ， 最後 用 低溫區 模擬 退火 法 （ ＬｏｗＴｅｍｐｅｒａｔｕｒｅＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇ ） （ １０ ） － （ １２ ） ， 使 雛形 組態 從 所 對應 之 溫度 開始 降溫 ， 其間 加入 參數 控制 在 低溫區 時 組態 變動 範圍 ， 如此 可 加速 求得 極值 。 使用 混合型 演算法 可 大幅 縮短 求 極值 的 時間 ， 藉著 參數 的 巧妙 選取 ， 甚至 可以 使 此 演算法 成為 線性 演算法 （ （ ｎ ） Ａｌｇｏｒｉｔｈｍ ） ， 其 精確度 也 可 達到 ３％－５％ 之內 。 目前 解 最 大 的 ＴＳＰ 問題 是 一百萬 個 均勻 分佈 的 城市 ， 費時 １ 秒 （ 若 用 傳統 模擬 退火 法 ， 至少 １０２２ 秒 以上 ） ， 而 所 得 之 最小值 也 在 理論值 的 ３％ 誤差 內 。 混合型 演算法 不僅 縮短 搜尋 極值 的 時間 ， 也 保留 了 類似 模擬 退火 法 的 一般性 ， 可以 讓 我們 將 此 演算法 應用到 不同 的 問題 上 。 另外 ， 混合型 演算法 也 可以 將 最佳化 問題 平行化 （ ｐａｒａｌｌｅｌｉｚｅｄ ） ， 得到 更 好 的 效率 。 六 、 最佳化 問題 的 應用 ‧ 不同 領域 的 專家 ， 發展出 許多 不同 的 演算法 來 解決 傳統 最佳化 問題 ， 甚至 將 這些 技術 應用 至 其他 方面 ， 例如 雷腦 晶片 、 元件 之 電路 設計 、 航空 公司 的 服務 人員 排班表 、 物理學 中 之 自旋 玻璃 （ ＳｐｉｎＧｌａｓｓｅｓ ） 問題 （ １３ ） 、 神經 網路 （ ＮｅｕｒａｌＮｅｔｗｏｒｋ ） 問題 、 圖形 及 影像 處理 等等 。 除此之外 ， 自然界 本身 也 會 採取 最佳化 的 策略 ， 例如 光 在 空間 中 選擇 最 短 的 路徑 。 最佳化 問題 的 發展 ， 已 有 二千 年 的 歷史 ， 近年 來 的 不同 範疇 上 ， 更 是 遍佈 它 的 蹤跡 。 因此 我們 了解 進而 解決 最佳化 問題 ， 不僅 可以 幫助 各 實業界 作 最 有利 之 規劃 ， 更 有 機會 讓 我們 一 窺 自然界 堂奧 之 妙 ！ 參考 資料 ： （ １ ） Ｍ ． Ｒ ． ＧａｒｅｙａｎｄＤ ． Ｓ ． Ｊｏｈｎｓｏｎ ， ， Ｗ ． Ｈ ． ＦｒｅｅｍａｎａｎｄＣｏｍｐａｎｙ ， ＮｅｗＹｏｒｋ ． （ １９７９ ） （ ２ ） Ｅ ． Ｌ ． Ｌａｗｌｅｒ ， Ｊ ． Ｋ ． Ｌｅｎｓｔｒａ ， Ａ ． Ｈ ． Ｇ ． ＲｉｎｎｏｏｙＫａｎａｎｄＤ ． Ｂ ． Ｓｈｍｏｙｓ ， ， ＪｏｈｎＷｉｌｅｙ ， （ １９８５ ） （ ３ ） Ｐ ． Ｊ ． Ｍ ． ｖａｎＬａａｒｈｏｖｅｎａｎｄＥ ． Ｈ ． Ｌ ． Ａａｒｔｓ ， ： ＴｈｅｏｒｙａｎｄＡｐｐｌｉｃａｔｉｏｎｓ ， Ｄ ． ＲｅｉｄｅｌＰｕｂｌｉｓｈｉｎｇＣｏｍｐａｎｙ ． （ １９８７ ） （ ４ ） Ｍ ． Ｍｅｚａｒｄ ， Ｇ ． ＰａｒｉｓｉａｎｄＭ ． Ａ ． Ｖｉｒａｓｏｒｏ ， ， ＷｏｒｌｄＳｃｉｅｎｔｉｆｉｃ ． （ １９８７ ） （ ５ ） Ｓ ． Ｋｉｒｋｐａｔｒｉｃｋ ， Ｃ ． Ｄ ． Ｇｅｌａｔｔ ， Ｊｒ ． ， ａｎｄＭ ． Ｐ ． Ｖｅｃｃｈｉ ， ， Ｓｃｉｅｎｃｅ２２０ｐｐ６７１－６８０ （ １９８３ ） （ ６ ） Ｈ ． ＧｏｕｌｄａｎｄＪ ． Ｔｏｂｏｃｈｎｉｋ ， ， Ａｄｄｉｓｏｎ－ＷｅｓｌｅｙＰｕｂｌｉｓｈｉｎｇＣｏｍｐａｎｙ ． （ １９８８ ） （ ７