NUTC應用統計系-教師成長社群專區

11/23 於中商大樓7501教室所舉辦的『最佳化數量方法(一)、(二)』演講，系上邀請了台北商業技術學院-資訊與決策科學研究所的楊東育 助理教授來擔任講者，主要講解何謂最佳化、合謂演算法、最佳化問題和決策問題以及介紹幾種通用啟發式演算法。

何謂最佳化?

一個有許多限制和條件相互衝突的環境下，找尋一個最佳解決方式的過程。近年來，許多學者紛紛提出用來處理最佳解問題的演算法，求取最佳解的問題，即為最佳化問題。

根據數據所做出來的決策雖有好處，但缺點就是：

過於製式化、決策過程冗長，無法應付環境變化、過於重視數據，反而忽略了『人』的變因。

何謂演算法?

楊老師說：『演算法不是加減乘除，而是廣義的， 做任何事情的計算，而辦法或法則意味著使用他即可解決需要的問題。』

演算法是解決各種問題的方法，或者說是求解問題的步驟。

接受輸入， 產生輸出。將輸入轉變為輸出。解決精準定義的計算問題。

楊老師利用生活上常見的例子來跟同學解說何謂演算法。

舉例：

1. 起床

2. 吃早餐

3. 上早自習

4. 上課

5. 吃午餐…..

任何一步驟的序列都可視為一演算法。

  也提到自然語言和電腦語言，兩種語言缺陷的比較：

對於自然語言： 容易產生歧異。

對於電腦語言： 理解上稍感困難。

楊老師舉了一個關於旅行商問題來講解最佳化問題

有一個旅行商，得拜訪幾個在不同城市的客戶，他要怎麼走，才能最用短的路線拜訪所有客戶、再回到自己的家？

什麼樣的拜訪旅程會使該銷售員所花費的旅行距離(成本)最少？

一般人的想法是找出所有的走法，然後找出最短距離的路線。當城市是3 個時，還能寫出所有答案，但如果城市有10 個，甚至更多的城市那又會是如何呢？

舉例：

當有20個城市時，就有 19!/2 條可能路徑。

假設電腦每秒可計算 10^6 條路徑的成本，一年有 3.15 x 10^7 秒，需要約 1930 年方可算出所有可能路徑。

在下午的演講中，楊老師則針對幾種常見通用啟發演算法做舉例說明：

n  禁忌搜尋法 (tabu search; TS)

n  模擬退火演算法 (simulated annealing; SA)

n  基因演算法 (genetic algorithms; GA)

n  粒子群最佳化演算法 (particle swarm algorithm; PSO)

n  螞蟻最佳化演算法 (ant colony optimization; ACO)

n  蜂群最佳化演算法 (bee colony optimization; BCO)

對於通用啟發式演算法，楊老師提到

其優點：

n  其所能求解的問題十分廣泛

n  均有跳脫區域最佳解的機制

n  對於問題複雜度較高、問題規模較大時，經常可獲得良好的求解品質及求解效率

n  即使對問題特性不十分瞭解，仍可使用

其缺點：

n  經常需要針對問題而設計，因此較少現有套裝軟體

n  僅能求得近似最佳解，而無法保證為最佳解

n  僅是一種廣義的啟發法

n  相同的問題，可設計不同的通用啟發式演算法

n  必須設定一些（有時相當多）所需要的參數值

整場演講，楊老師使用貼近生活的例子來做範例，雖然演算法的過程有些繁瑣，可是內容生動活潑，讓同學們都留下深刻的印象，講者深入淺出的介紹，讓一般的聽眾也能有深刻的了解。也有老師們對楊老師所介紹的『塔布搜尋法』感到很有興趣，希望下次有機會能夠再對演算法做深入的了解。