無論在文理商科的學研界或工商業界，上至國家型的重要決策，下至個人的瑣碎問題，「最佳化問題」一直在每個人身邊不斷出現。譬如：在個人日常生活裡，開車時規劃最省時的上下班路線、投資時思考如何優化股匯資產分配、上班族工作時研究最高效完成工作的方式、老闆們作決策時思考如何利用最小資源來獲得最大的收益等。因此，最佳化問題可說是各領域普遍都會面臨的共同問題之一。本文先回顧最佳化演算法的演進，接著介紹一套名為「群體智能為基礎（SIB）」方法的元啟發式最佳化演算法，最後以實際應用來說明 SIB 方法的實用性。
最佳化演算法的演進
傳統的最佳化演算法源遠流長。早在公元前 300 年的古希臘時代，幾何學之父歐幾里得就已經考慮了點和線之間的最小距離，芝諾多羅斯和海倫等數學家也在歐洲首個文明時期思考多個幾何裡的最佳化問題。來到歐洲文藝復興後科學重生的 17 世紀，牛頓和萊布尼茲分別獨立創建了在數學分析中舉足輕重的微積分，並開創了利用變分法來處理有限最佳化問題的黃金時代。在之後的兩個世紀裡，歐拉、拉格朗、勒壤得、傅里葉、柯西、吉布斯等大數學家們精進最佳化的方法並將其廣泛地應用在數學統計和自然科學等領域。二戰後隨著電腦的發明，在馮紐曼創新的運籌學和丹齊格著名的單形法加持下，線性規劃和類似的方法成為現化最佳化問題最普遍的解決之道。
這幾百年裡數學家們的努力目標都是追求一套既簡單高效又萬能的方法來得到唯一的最佳解。可是，現實世界的問題往往有著很多細緻的條件和限制，以致很多最佳化方法無法在不滿足特定假設下廣泛地使用，為了讓最佳化方法能夠處理多種類型的問題，方法本身不再簡單。隨著大數據時代的來臨，資訊量以幾何級數的速度增加，最佳化問題的解決方案數目也日趨龐大。即使現今電腦科技和能力快速地進步，使用傳統的最佳化演算法仍然需要花費難以想像的計算時間才能得到最佳解答。然而，除了在科研界少數的問題外，現實生活其實並不強求那個唯一的最佳解，只要解答足夠好即可。譬如一個學生花 3 小時溫習就能夠在考試中得到 95 分，但如果要拿到最佳的 100 分，他可能要花上 12 小時溫習，使之投資報酬率低落。因此，相較於傳統最佳化演算法這些精確方法，「近似方法（approximate method）」已經漸漸成為最佳化開發工具的主流方向。
元啟發式最佳化演算法是既簡單高效又萬能的最佳化近似方法，雖然無法保證得到最佳解，但能夠在合理的計算成本內找到一個接近最佳解的解。1975 年由美國工程師霍蘭德發表的遺傳演算法是第一個元啟發式最佳化演算法。自此之後的幾十年間，大量元啟發式最佳化演算法被提出。由於它們的設計靈感大部份源自大自然和生物的行為，因此它們大多以生物命名。譬如，遺傳演算法的靈感是來自基因複製和突變的生物現象，粒子群演算法的靈感是來自鳥群或魚群在獵食時的群體行為，蟻群演算法的靈感是來自螞蟻成隊釋放訊息探路以尋找食物時的行為，而模擬退火法的靈感則是來自金屬退火時粒子重新排列的物理現象。
在這些演算法裡，粒子群演算法近年來最常被應用如工程領域般的連續型問題上，但它甚少使用在其他需要離散型的最佳化問題上，如：數理統計、經濟、財經、人文和其它產業裡。然而，由於其源自基礎物理的步驟簡潔易明，卻又因著平行運算的普及而高效，因此本文介紹一套在 2016 年提出，靈感來自粒子群演算法和遺傳演算法的結合，專為離散型的最佳化問題設計的元啟發式最佳化演算法，名為群體智能為基礎（SIB）演算法。
群體智能為基礎（SIB）方法簡介
群體智能為基礎（SIB）演算法包含一個自定義的粒子群，且定義方式非常彈性，使用者可以根據欲解決的最佳化問題將粒子定義為任何透過目標函數計算出客觀價值的資料結構。如同粒子群演算法， SIB 會額外記錄每個粒子在歷史路徑中的已知最佳位置——個體最佳解，以及整個粒子群的已知最佳位置——群體最佳解。此外， SIB 主要由兩個運算子組成：「混合」和「移動」。每個粒子會在每次迭代中，透過「混合」目前位置及最佳解位置的資訊，從附近的位置挑選出三個候選方向，接著在「移動」中依據客觀價值決定移動方向，並更新其最佳解位置。在「混合」中，每個粒子則根據其個體及群體最佳解更新部分元素，以分別獲得兩個更新後的粒子。使用者可依此概念自行設計此運算子的實作細節，但須確保更新後的粒子不會違反任何目標問題的限制。
在「移動」中，每個粒子要和其在「混合」中得到的兩個新粒子比較。若任一新粒子表現優於原粒子，則將該原粒子移動至兩個新粒子中較佳的位置；若兩個新粒子都無法勝過原粒子，則該原粒子將「隨機跳躍」至附近任一個位置。「隨機跳躍」此機制可以確保演算法充分探索解空間，而不被困在局部最佳解。每一次迭代結束後，演算法將根據使用者定義的終止條件決定是否繼續進入下一輪的迭代，而常見的終止條件有：（1）在使用者定義的迭代數量中，群體最佳解都沒有進步，（2）到達指定的運算時間，（3）到達指定的迭代數量。在整個演算法結束後，群體最佳解即為最終輸出。
▲群體智能為基礎（SIB）演算法的標準流程圖
應用實例
本文將簡單介紹四個應用，並說明其「混合」運算子的運作方式及相關實驗結果：
實驗設計：實驗設計是統計學裡重要的一環，從科研至業界都需要做實驗，因此在最佳化的角度來看，一個好的實驗就是要以最少的資源得到最多而穩健的實驗成果。 SIB 演算法的一個著名的應用就是建構一種以最小 E(s2) 標準為目標的超飽和因子設計。超飽和因子設計本身是一個以低成本研究大量因子的實驗設計，其中的元素皆為二元，代表相對應的操縱變因設定。 E(s2) 標準是用來測量因子間在每個實驗裡設定的相似度，標準量越低代表一個因子的估計因著其他相似設定因子存在而出現偏差的程度越小。在傳統的實驗設計裡，除了利用代數論証外，只有變換設計裡的設定才能找尋最佳設計，即使設計的維度沒有很大但其最佳化的難度已經極高。在使用 SIB 演算法時，每個粒子被定義為一個二維矩陣，代表一種均衡的超飽和設計，其行數為該設計所含的實驗數量，列數為操縱變因數量。「混合」以列交換的方式進行，先從原粒子中以迴圈的方式剔除固定比例的列數，再從最佳解粒子中挑選相同數量的列，組合得到一個完整的新粒子。實驗結果展示 SIB 演算法可以在任何維度裡快速找到非常接近 E(s2) 標準理論下限的超飽和設計。除了超飽和設計外， SIB 演算法還應用在最低能量設計，循環哈達瑪設計（核磁共振實驗）等多個實驗設計的搜尋和建構上。
社群發現：網路分析是大數據分析不可或缺的一部份，而社群發現是網路分析裡重要的一部份，其理論可追溯回傳統數學的圖論，但其應用十分廣泛，從簡單的朋友網路分析到複雜的電商廣告推播，甚至可用於探討部落關係或國際交易分析等。 SIB 演算法的一個著名的應用就是以模組化或掃描統計量為原則從一個大型網路的資料和結構中找尋可能的社群。一個網路社群是指一群相互連結度比整個網路其他部份高很多的節點，譬如在人際網路中有一群要好的朋友，他們之間的連結比率比起整個網路其他人之間平均的連結比率高很多，那他們就是一個社群。無論是基於模組化或掃描統計量，傳統的網路分析需要不斷地計算不同的節點組合的標準量，在一般數百個節點的中小型網路裡，其計算量已經很可觀。在使用 SIB 演算法時，每個粒子被定義為一個大小可變的節點集合，而一個集合中的每個節點都被標記是否位於邊界。「混合」以交換邊界節點的方式進行，剔除和加入的數量不必相等，只需改善標準量即可。實驗結果展示 SIB 演算法成功對很多大小不同的著名網路進行分群，包括小如只有 34 個節點的美國空手道社關係網路，以及大至擁有數萬個節點的電郵網路，再利用平行運算的情況下甚至可以處理超過百萬節點的科學網科研合作網路分群。
路線規劃：路徑規劃是最佳化領域中非常經典的問題，目標為在每條路線都不得重複經過同一地點的情況下以找出最短路徑，其應用包括個人或旅行社的行程規劃，或是物流業裡貨運成本和路線優化等。不少元啟發式演算法也對此問題進行研究，其中蟻群演算法是最常被使用的經典方法。在使用 SIB 演算法時，每個粒子是一個向量，長度為問題中指定目的地的數量，其中每個元素為使用者事先定義好的地點編號。「混合」依然以迴圈的方式進行，而使用者必須事先決定此迴圈進行的次數。在每個迴圈中，先根據原粒子算出每一個地點和其在路線上前後兩點的距離總和，並從中找出總和最大的地點 a 。接著，找出最佳解粒子的路線中相同順序的地點，並在原粒子中找到相同編號的地點 b 。最後，交換原粒子中的 a 和 b 兩個點。此運算模式可以保證最後得到的路線依然不會重複經過相同地點。實驗結果展示 SIB 演算法在地點數為 10 到 25 之間的路徑規劃問題上，最佳化結果和蟻群演算法相近，且運算速度更快。此外，針對實務上可能出現的細緻限制，如：貨品材積、司機排班等， SIB 演算法經改良後都已經納入考量。
供應鏈管理：供應鏈管理是現代商務非常重視的一環。隨著科技的日新月異，傳統的中盤商模式和超市經營已經漸漸被網購採取的產地直銷模式所取代，但其中的多對多供應鏈管理最佳化策略因維度的大幅提升而變得相當複雜。 SIB 演算法將每個粒子定義為一個三維矩陣，代表一個可行的供應策略，其三維分別代表供應商數量、顧客數量、產品種類數量。此矩陣中，每一列代表特定供應商對特定顧客的產品供應策略，而每個元素則代表此供應策略中特定種類產品的數量。然而在此定義下，我們無法從單一行的資訊中檢查這個題目的兩個限制：最大供給量、最大需求量。針對此雙向限制的問題，「混合」被設計成逐行處理的模式，每次只處理原粒子及最佳解粒子中一組相對應的行，隨機選擇該行中固定比例的元素，並依照最佳解粒子中的元素更新。更重要的是，演算法會在「混合」整個粒子的過程中持續追蹤剩餘供給及剩餘需求。如此一來，每處理完一行就可以依此檢查是否遵守供給和需求的限制，若違反也可即時修正。根據實驗結果， SIB 的表現優於基因演算法及粒子群演算法，且收斂速度也較快。在使用 CPU 平行運算加速後，其運算時間縮短成原本的二十分之一。
結語
最佳化問題是所有學研工商界必然遇到的問題，從古希臘到現今的電腦和大數據時代，人類不斷地精進最佳化的方法和技術，冀望能夠提出一套簡單高效又萬能的方法，來搜尋問題的最佳解答。 隨著科技的進步，元啟發式最佳化演算法漸漸代表近似方法成為最佳化的主流工具。本文簡介的 SIB 演算法也在短短數年內被應用在多個領域的最佳化問題上，如實驗設計、資源調度、路徑規劃、供應鏈管理、社群發現、資料視覺化等。這些應用問題的共通點是擁有高維度且非連續的解空間，使用傳統的最佳化方法會耗費大量的運算時間及資源。除此之外，這些問題在真實的應用場景中，並不追求精準的最佳解，而是希望能在較短的時間內找到足夠好的解。此演算法中有許多使用者可以自行設計的部分，其中以「混合」運算子的設計最具彈性和創意。在大數據和平行運算等先進運算普及的現代， SIB 演算法和其他的元啟發式最佳化演算法在，很多領域裡都還有極大的應用潛力，等待各位讀者們來深究和開發。
參考文獻
1.Rao, S.S. (2009) Engineering Optimization: Theory and Practice (4th Edition), John Wiley & Sons, Inc.
2.Phoa, F.K.H., Chen, R.B., Wang, W.C. and Wong, W.K. (2016). Optimizing two-level supersaturated designs via swarm intelligence techniques. Technometrics 58, 43-49.
3.Lin, F.P.C. and Phoa, F.K.H. (2017a). A performance study of parallel programming via CPU and GPU on swarm intelligence based evolutionary algorithm. Proceedings of ISMSI 2017 1-5.
4.Lin, F.P.C. and Phoa, F.K.H. (2017b). An efficient construction of confidence regions via swarm intelligence and its application in target localization. IEEE Access 6, 8610-8618.
5.Phoa, F.K.H. (2017). A swarm intelligence based (SIB) method for optimization in designs of experiments. Natural Computing 16, 597-605.
6.Hsu, T.C. and Phoa, F.K.H. (2018). A smart initialization on the swarm intelligence based method for efficient search of optimal minimum energy design. Advances in Swarm Intelligence, LNCS volume 10941, 78-87.
7.Lin, F.P.C. and Phoa, F.K.H. (2019). Runtime estimation and scheduling on parallel processing supercomputers via instance-based learning and swarm intelligence. International Journal of Machine Learning and Computations 9, 592-598.
8.Phoa, F.K.H. and Tsai, T.C. (2020). A two-step approach to the search of minimum energy designs via swarm intelligence. Advances in Swarm Intelligence, LNCS volume 12145, 37-45.
9.Phoa, F.K.H., Liu, H.P., Chen-Burger, Y.H. and Lin, S.P. (2021). Metaheuristic optimization on tensortype solution via swarm intelligence and its application in the profit optimization in designing selling scheme. Advances in Swarm Intelligence, LNCS volume 12689, 72-82.
10.Singh, K., Lin, S.P., Phoa, F.K.H. and Chen-Burger, Y.H.J. (2021). Swarm intelligence optimization algorithms and their applications in a complex layer-egg supply chain. Agents and Multi-agent Systems: Technologies and Applications, SIST volume 241, 39-51.
11.Yen, P.C. and Phoa, F.K.H. (2021). Traveling salesman problem via swarm intelligence. Advances in Swarm Intelligence, LNCS volume 12689, 106-115.
12.Singh, K., Liu, H.P., Phoa, F.K.H., Lin, S.P. and Chen-Burger, Y.H.J. (2022). Decentralized supply chain optimization via swarm intelligence. Advances in Swarm Intelligence, LNCS volume 13344, 432-441.
13.Sun, W.H. and Phoa, F.K.H. (2022). Network community detection via an improved swarm intelligence approach. Advances in Swarm Intelligence, LNCS volume 13344, 419-431.