全域最佳化（Global Optimization）

在之前深度學習系列文章中佔有重大地位的Gradient Descent，一種最佳化的方法，這篇則是會提到關於他的一些限制，還有其他方法來尋找最佳解。

以下的文章是皆取自課程內容。

Outline:

• Gradient Descent Optimization的缺點
• 尋找全域最佳解的方法(Global Optimization) — Particle Swarm Optimization(PSO) and Genetic Algorithm Optimization
• 群體智慧（Particle Swarm Optimization）
• 基因演算法（Genetic Algorithm Optimization）

Gradient Descent Optimization的缺點

Gradient Descent並不保證能找到global minima，在許多情況下Gradient Descent只能找到local minima。並且在以下兩個條件下，Gradient Descent更是無法幫助模型找到global minima。

• 當目標函數有多個local minima，請參考下圖。

• 目標函數(Objective Function)不可微分時，也可以想成是找不到斜率。

因此，這篇就要介紹相關的「最佳化方法」演算法來解決類似的問題。

為什麼需要Global Optimization？

• 實際應用場景：許多現實世界的問題，例如物流規劃、供應鏈管理、資源分配、機器學習超參數調整等，都具有高度的非凸性和多個局部最小值。這意味著全局最優解才是真正所需的，但通常難以確保找到。

尋找全域最佳解（Global Optimization）

當今天我們不知道目標函數(objective function)的導數時，是無法使用gradient descent optimization。這時候，我們只能依靠「評估objective function (Evaluation of the objective function)」像是Accuracy, recall等等比較直觀的方法，去更新模型。因此我們想要找一個方法，在給定的空間內訓找最佳解，但又不能用太暴力的去搜索（會太慢）。

一個好的最佳化方法應該滿足兩點：
第一點（exploratory）：可以充分的exploratory search space，這樣才可以找到最有可能的global minima。
第二點（exploitation）：可以善用找到的local minima或是那些找錯的訊息，來為之後的搜索提供更多資料，這步驟稱為exploitation。

在尋找Global optimization的過程中，經常會使用「Metaheuristic」相關演算法。名詞解釋，名稱Meta的由來是想要強調，他不保證會找到global minimum，也就是說，如果是「Global optimization algorithm」他保證可以找到global minimum，而「Metaheuristic」則沒有這個保證。可能會有人覺得，那為什麼要使用這種沒有保證的演算法，事實上Metaheruristic演算法，經常應用在「現實世界」的最佳化問題。也可想成比起那些「保證可以找到global optimization algorithm」，使用Metaheruristic的方法，相比之下效率還更好。

Methaheuristic之間有個重點是去找到 「探索（exploration）」 和 「利用（exploitation）」 之間的平衡，就和我們先前提到的相同。探索指的是廣泛地搜索解空間，而利用則指的是深入挖掘那些已知效果很好的解。好的 Metaheuristic 演算法能夠有效探索未知區域，同時也能專注於進一步優化已知的局部最優解。

受到大自然的啟發（Nature Inspired Metaheuristics）

從機器學習的角度來看，其實就是利用電腦去模擬人腦接受訊息的方式。而在Metaheruistics中也會從自然現象中，學習他的方法，來挪用成一個新的演算法。以下會介紹的兩個最佳化方法：群體智慧（Swarm Intelligence(SI) algorithm），以及Genetic Algorithm（偏向演化論，物競天擇）。

群體智慧（Particle Swarm Optimization, PSO）

先用幾個範例，來快速理解概念後，在轉換成數學表示。

範例一：10個人一起走迷宮，目標是找到出口，在這個過程中，大家都會彼此報告目前的進度，可能是遇到死路，找到通道等等的情況。而因為彼此之間會互相溝通，因此當有人先找到出口的時候，其他人也會試著去往那個人的方向前進。

範例二：萬能阿秋想要開一間店，所以他在進行市場調查某個國家的飲食習慣，大家比較喜歡美式、義式、日式、韓式、中式，現在我們有很多位受試者。那要怎麼決定市場比較喜歡哪一種呢？最簡單的方式就是投票，但是人的想法是會不斷的在改變，A可能今天想吃日式，明天吃韓式，因此這樣每位受試者之間的想法都會不斷在拉扯，而我們要在這之中，找到一個最佳解。這個就是Particel Swarm Optimization的想法！Reference:https://www.youtube.com/watch?v=jfoAYg-gk98

看完兩個範例之後，不知道有沒有感覺到，PSO演算法的精神就是，「每一個人都會彼此相互牽涉，影響對方在接下來的選擇，進而找到大家都可以認同的「最佳解」，也可以理解是一個平衡的方案」。

講解完比較抽象的概念過後，接下來就要說明偏向數學式表示法的部分。

步驟：

以範例一走迷宮來當作範例：（在前面有提到每一個人的任務都是找到最佳的出口，假設每一個人都可以視為粒子（particle），而大家都有以下三種屬性。

1. 目前位置(Current position)：

1. 最佳位置（目前找到最佳的點）：這個比較難想像，可以引入目標函數（objective function）的概念，也就是說紀錄中產生最小的目標函數（objective function）的位置。
2. 下一個更新的位置：
   在這裡面v_{t+1}代表的是：「方向」和「速度快慢」的綜合體。類似跑步，現在要往哪邊跑（方向）、跑多快（速度）。一次把兩個概念用一個變數給代替。

另外一個問題，要怎麼計算v_{t+1}

另一種寫法（包含不同的particle）

看起來很複雜，先不用擔心，首先分別說明每一個參數所代表的意涵。再來一步一步拆開來說明。

x_t：目前particle的位置

v_t：原本的運動速度＋方向。

v_{t+1}：下一個時間點的「速度」＋「方向」

w：繼續朝原本慣性前進的權重。

c1, c2：權重。

r1, r2：隨機性，避免過早集中在某些點，就不再移動了。

x_{pb}：personal best，自己走過的路裡面，最佳的點。

x_{gb}：global best，全部particle中最佳的點。

這個公式我們可以拆成三個部分來看：（以A, B來舉例）

• 慣性（Inertia）：A繼續朝自己的原本習慣的方向前進。
• 個人最佳紀錄(Attraction toward the individual best)：朝過往最佳紀錄前進
• 他人的影響(Attraction toward the global best)：受到B影響往B的方向前進。

**Note**
隨機數的目的在於讓每個粒子有不同的嘗試路徑，這樣可以增加算法的探索能力，防止粒子群過早集中到某個區域，進而找到更好的全局最優解（Global Optimization）。

如果用比喻來說的話，問題是：「小琉在決定中午要吃什麼」，小琉一直以來都是吃樓下便當店（慣性），但是因為小琉之前吃過一家附近的日式料理店覺得很好吃（個人之前最佳紀錄），而小飛跟他說隔壁的韓式料理也很好吃（他人的影響）。因此A在腦中決定的過程中，就會不斷地去替換這三個權重(W, c1, c2)，另外r1, r2的隨機性可以理解是說，A對於每一種料理都還保有空間，沒有絕對一定要哪一家不可，讓他可以更全面的思考自己要吃哪一種料理。

相信看到這邊，大家可能眼睛都花了，記得我們目的是在「尋找Global Optimization」，也就是在眾多選擇或意見中最一個最佳解。

Genetic Algorithm Optimization (GAO)

概念：物競天擇！這個也是挪用自然界的原理來做比喻，而這個Optimization的方法有一個比較明確的步驟。

步驟：我們建立機器人來做說明

1. 初代機器人，隨機設定他的功能。
2. 制定一套評測標準（objective function）來評分這些機器人。
3. Selection：選擇比較優秀的機器人，也就是在考試中得到分數較高者。
4. Crossover（相互融合）：融合那些分數較高機器人的優點。
5. Mutation（突變）：讓機器人加入一些隨機性，隨機加入看似無用的小功能或是新工具。
6. 這樣不斷迭代的過程中，就可以找到綜合分數最高的機器人。

以上就是Genetic Algorithm Optimization的概念，接下來則是比較繁瑣的部分，介紹相關在實作時需要用到的參數。

• 染色體(chromosome)跟候選解(Candidate solution)之間的轉換:
  如果以基因合成的概念來理解，我們可以把基因中的「染色體」想像成是一個潛在的解（稱為候選解），可是染色體本身可能只是一些數據（例如二進制數、浮點數等）。首先要考慮，「如何將染色體轉換為問題中的實際解」。用範例來看會比較好理解。
  範例：如果問題是要「最小化一個人工神經網絡（ANN）的loss function J(x)」，染色體 ci​ 可以包含實數(ci=[0.1, 9, 4, …, 0.8]這樣的矩陣)，代表神經網絡中的權重和偏置。這樣，染色體中的數字就可以轉換為神經網絡的結構，然後用於計算性能。

小結論：每個染色體都可以視為一個潛在解，只是需要透過另一種方式映射到實際問題的參數中。

• 適應度函數（Fitness Function）: 評估每個染色體的能力，決定要選擇哪些染色體去繁衍下一代。適應度函數f(x)是 GAO 的核心，它決定了每個候選解的「分數」。
  例子：在神經網絡中，適應度可以是網絡的預測性能，也就是基於染色體（候選解）中的權重和偏置所訓練出來的神經網絡進行預測的準確度，像是accuracy, Recall等等的評估標準。
  Ex: A參數帶來的結果，acc是80%，B參數的結果則是70%。這是就要選擇A參數。

部分在實作會需要超參數（Hyperparameter）解釋:

• N_{pop}​：表示每一代的染色體數量（即候選解的數量），這也就是說每一疊代我們會處理多少潛在解。染色體數量越多，會有更多的多樣性，但也會增加計算成本。
• P_{mut}​：突變率（Mutation），決定染色體的每個基因（元素）被隨機變異的概率。跟之前PSO類似，引入隨機性，防止演算法太早就找到局不解，而不再移動。
• N_{top}：每一代中最好的染色體數量。這些最優染色體會被當作「父母」來生成下一代。更多的優秀染色體會幫助維持好的基因傳遞到下一代。
• m_{maxmut}​：這個參數控制了變異幅度的範圍。假設我們的染色體由實數組成，則變異會讓染色體中的數值在一定範圍內隨機變動。m_{maxmut}​ 定義了這些變動的最大值。更大的變異幅度意味著染色體有可能進行更大幅度的探索。

簡單回顧：

上面的演算法皆屬於Methaheuristic中，而Methaheuristic裡面有個重點，是想要找到 探索（exploration） 和 利用（exploitation） 之間的平衡。
探索（exploration）指的是廣泛地搜索解空間，
利用（exploitation）則指的是深入挖掘那些已知的不錯的解。
一個好的 Metaheuristic 演算法能夠有效探索未知區域，同時也能專注於進一步優化已知的局部最優解。

這邊文章應該只能當作一個簡單的科普知識來做吸收，希望這篇文章也可以幫助到有困惑的夥伴！