[筆記] 最佳化演算法 (Optimization Algorithm) 的使用與誤用

(這篇的數學式有用到 javascript 來顯示，請不要檔掉 JS，不然顯示上會很奇怪 XD)

最佳化演算法簡單來說就是個搜尋演算法，這類演算法的再做的事情是給定一個問題，定義合法的解集合 (或是空間，英文是 solution space)，再給一個函數用以判別一個解的好壞 (objective function)，這類最佳化演算法就會在解集合中找出符合要求的一個解。

有點難懂？舉個例子：假設我想要再一個 2D 的平面座標中找到一個點使得 $f(x, y) = (x - 5)^2 + (y + 3)^2$ 得值最小，求 (x, y) 為？在這個例子中，solution space 就是 2D 平面上所有可能的點座標，而 objective function 就是 $f(x, y) = (x - 5)^2 + (y + 3)^2$。而最佳化演算法就是針對 "任何" 這樣的問題，找出一個盡可能滿足 objective function 也合法的解給你。沒錯，就是任何這類需要在一個 solution space 中找解的問題都行。所以這類演算法很萬用，但也因此容易被誤用。

 

常見的最佳化演算法包含：基因演算法 (Genetic Algorithm，簡稱 GA)、模擬退火法 (Simulated Annealing，簡稱 SA)、粒子群演算法 (Particle Swarm Optimization，簡稱 PSO) ... 等等，其實也還有一大堆我也沒聽過、或者是我曾經聽過但忘記的演算法。不過這類演算法都有一個特徵：都是作者觀察到自然界的現象，然後把他們應用在這類問題上 XD 舉個例子，GA 模擬的是生物的世代交替；SA 是模擬金屬冶鍊的過程；PSO 則是有點像蜜蜂或螞蟻一類的昆蟲找食物的方法 (有其他的最佳化演算法是直接把他們找食物的方法完整照抄變成演算法 XD) 至於這類演算法為何都有這類的特徵，我想原因有部分源自於這類最佳化演算法的萬用性：最佳化演算法要能處理的問題非常廣泛且沒有一致性，也因此演算法本身無法根據問題本身的特性與以特化，而自然界中的各種現象就是會逐步的往整體平衡的方向去走，所以依循著自然界中的現象去發展會比自創一套規則更容易有好結果，大概都是這種想法。

有沒有注意到我藍色字體的用詞？ "盡可能" 與 "平衡" 代表的是得到的結果或許以當下來看是個很好的解，但對整體來說卻不是一個最好的結果。所以雖然這類也算法很萬用，但是他們本質上都有一個問題：理論上可以找到最佳解，實質上幾乎不可能找到最佳解，所以這類演算法比的是誰的方法能找到比較好的解。所以剛接觸這類演算法的人看到最佳化演算法如此萬用，看別人的結果好像也都不錯，就很容易會誤以為只要想辦法把問題本身轉換成能用最佳化演算法來解就好了，不需要特別根據問題想一套方法來解。然後等到碰壁一段時間後才會發現這類演算法其實沒有想像中的那麼好用。以最一開始的那個例子來說，最佳解是 (5, -3)，最佳化演算法理論上也確實能找到這組解，但實際上能否找到、找不到的話能多接近這組解、要花多少時間才能找到 ... 等等，全部都是最佳化演算法可能會遇到的問題。(不過一開始的例子很簡單，所有的最佳化演算法要能找到最佳解應該都是沒有問題才對)

最佳化演算法要能做得好，首先必須要能清楚的了解每個最佳化演算法的特性。依循著演算法的特性就會知道什麼樣的問題用哪種最佳化演算法才適合 (老話一句：理論上沒差，實際上差得可多了)。再來，這類演算法都會說明要透過哪些操作以便找到最佳解，因此接下來就必須針對要解決的問題予以特化這些操作。最後，如果想要能得到更好的結果，演算法的各處細節與參數也都必須加以調整，甚至有可能要改變演算法的部分流程。以上這些流程所需時間可長可短，依人而定。

以我個人的想法來說，最佳化演算法確實有其優點，當今天的問題需要能夠在短時間內寫個程式得到一個堪用的結果，最佳化演算法確實是首選。然而當今天時間充裕，要解決的問題有明確的特性可依循使用時，針對問題的特性想一套方法來解決才是最好的，因為這時可能使用最簡單的貪婪法則都能比最佳化演算法得到的結果還要好。另一方面，這類最佳化演算法要能收斂得到結果往往相當費時 (你看自然界中的現象哪個不費時？)，所以在執行時間上有強烈限制的問題也都不適合使用最佳化演算法。以 EDA 中的問題來說，通常一個問題的第一篇論文有很高的可能性會是使用最佳化演算法 (畢竟動作太慢就會被別人給搶先了 XD) ，或者是使用貪婪法來解，但後續很快的就會有針對問題特性本身發展出來的演算法來解，而且時間又快、得到的解也好很多。