Meta-Heuristic 次經驗法則

過去在求解最佳化問題時常用數學規劃(Mathematical Programming)法來求出問題的最佳解，但隨著現實世界中的需求增加（像是工業上的機器排列問題、運輸業的車輛路徑問題等），已經無法再用數學規劃法來求得最佳解，取而代之的改用經驗法則(Heuristic)的方法來求解，才能在合理的時間範圍內求出近似最佳解，但這些經驗法則只在目標值有改善時才進行交換，所以常會陷入局部最佳解，而無法進一步找到更好的解，次經驗法則(Meta-heuristics)常以生物界的自然現象為基礎，並結合一些搜尋策略，以避免陷入局部最佳解，因此次經驗法則最常被運用在求解複雜度極高的問題。

為什麼有最佳解的方式不用而要用Meta-Heuristic
我們可以想像，如果今天要投資股票若透過數學規劃求的最佳的股票，假設需花費三天的時間，那三天過後就算我拿到的最佳解，股票市場早就已經不是三天前的狀態的，那最佳解對我們來說也就沒有意義了，因此我們需要的是一個不管在任何時間中斷程式，都可以得到一個解答（當然，算越久得到的解答會越好），重要的是，它可以在有限資源內得到一個近似最佳解，這就是我們使用Meta-Heuristic的原因。

什麼是經驗法則(Heuristic)
經驗法則就是當我們對面問題，腦子裡第一個想到的辦法，在國外會說作RULE OF THUMB，中譯為大拇指法則，假設今天要解決旅行者問題(travel salesman problem, TSP)，通常第一個想法一定是走離我目前的點最近的其他點作為下一個點，這種方法為貪婪法(greedy algorithm)，貪婪法是經驗法則的一種，由於經驗法則的作法為當解的品質有改善的時候才進行交換，但也因如此較容易陷入區域解。


什麼是次經驗法則(Meta-Heuristic)

Meta-data在資料庫裡面叫做描述資料的資料，因此Meta-Heuristic可稱作描述經驗法則的經驗法則，這樣子的說法很抽象，換個方式來說，我們利用外層的架構來控制內層的Heuristic，在特定的時機啟動Heuristic來增加搜尋的能力，通常外層的架構我們會以生物界的現象來作譬喻，像是基因演算法(genetic algorithm, GA)、鳥群演算法(particle swarm algorithm, PSO)、螞蟻演算法(ant colony algorithm, ACO)等多種以生物界為基底的演算法。

粒子群最佳化(Particle Swarm optimization,PSO)

原始概念：

PSO的起源是來自於鳥類群體捕食的行為研究對於一個最佳化問題的研究，像是一隻在空間中飛行的鳥一樣，稱作「粒子(Particle)」，在空間中移動的所有粒子都有一個由目標函數所映射的適應值。另外，每個粒子本身都會有一個向量跟速度，利用核心運用模式產生一個速度來決定他們移動的方向與距離，一群粒子靠著個體本身的成功經驗與目前族群中最佳粒子的位置求得最佳解。PSO中的每個粒子獨立搜尋，當粒子個體遇到目標函數最佳值時，其最佳搜尋變數將被記錄在個體記憶中，亦即每個粒子都擁有本身最佳(pbest)的搜尋變數記憶，依照此個體最佳搜尋變數記憶去修正下一次的搜尋方向。每次搜尋均以這些個體最佳適應值與群體中最佳適應值的最佳化程度做比較，修正群體最佳函數值的變數記憶，同時每個粒子也依照群體最佳變數(gbest)記憶來修正下一次粒子的搜尋速度，經過如此疊代計算後，PSO根據粒子群中最佳適應值計算出問題的最佳解。 

核心運作模式：

此部分則為大家說明有關PSO的執行步驟以及內部的核心運作模式：
1.初始化：將每個粒子的各個維度進行位置(positon)的初始化，最基本的就是以隨機(random)的方式初始。
2.計算適應值：利用目標函數計算每個粒子的適應値。
3.將粒子的適應值和pbest值作比較，假如優於pbest值，則更新pbest值及其位置。
4.將粒子的適應值和gbest值作比較，如果優於gbest值，則更新gbest值及其位置。
5.可依照以下兩個公式來更新粒子各個維度的速度(1)跟位置的移動(2)。

w：慣性權重 [0,1]
C1, C2：學習因子
Rand()：為[0,1]的亂數
i：第i個粒子
d：第d個維度
V：向量
X：位置
Pid：本身粒子最佳的位置
Pgd：群體最佳粒子的位置


6.是否達到停止準則條件，若是，則印出最佳適應值及粒子位置，否則，跳至第二步驟。

重點整理：

粒子群最佳化(Particle Swarm optimization,PSO)，他的概念來自於模擬社會的行為，是屬於群體智慧的其中一種，

群體智慧包括：螞蟻演算法、蜜蜂演算法、粒子群最佳化…等多種演算法。

而PSO本身還具有方向性和記憶性，利用粒子群具有探測與開發的特色，在問題空間中搜尋全域的最佳解。

每一個粒子都代表在最佳化問題中的解，各自負責區域中的最佳搜尋，再藉由族群間的記憶分享， 粒子將受到群體間的約束，最後完成最佳化問題的搜尋。