Meta-Heuristic 次經驗法則
過去在求解最佳化問題時常用數學規劃(Mathematical Programming)法來求出問題的最佳解，但隨著現實世界中的需求增加（像是工業上的機器排列問題、運輸業的車輛路徑問題等），已經無法再用數學規劃法來求得最佳解，取而代之的改用經驗法則(Heuristic)的方法來求解，才能在合理的時間範圍內求出近似最佳解，但這些經驗法則只在目標值有改善時才進行交換，所以常會陷入局部最佳解，而無法進一步找到更好的解，次經驗法則(Meta-heuristics)常以生物界的自然現象為基礎，並結合一些搜尋策略，以避免陷入局部最佳解，因此次經驗法則最常被運用在求解複雜度極高的問題。
為什麼有最佳解的方式不用而要用Meta-Heuristic
我們可以想像，如果今天要投資股票若透過數學規劃求的最佳的股票，假設需花費三天的時間，那三天過後就算我拿到的最佳解，股票市場早就已經不是三天前的狀態的，那最佳解對我們來說也就沒有意義了，因此我們需要的是一個不管在任何時間中斷程式，都可以得到一個解答（當然，算越久得到的解答會越好），重要的是，它可以在有限資源內得到一個近似最佳解，這就是我們使用Meta-Heuristic的原因。
什麼是經驗法則(Heuristic)
經驗法則就是當我們對面問題，腦子裡第一個想到的辦法，在國外會說作RULE OF THUMB，中譯為大拇指法則，假設今天要解決旅行者問題(travel salesman problem, TSP)，通常第一個想法一定是走離我目前的點最近的其他點作為下一個點，這種方法為貪婪法(greedy algorithm)，貪婪法是經驗法則的一種，由於經驗法則的作法為當解的品質有改善的時候才進行交換，但也因如此較容易陷入區域解。
什麼是次經驗法則(Meta-Heuristic)
為什麼有最佳解的方式不用而要用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)等多種以生物界為基底的演算法。
參考
http://pipiyapipi.blogspot.com/2012/10/meta-heuristic.html
沒有留言:
張貼留言