為什麼有最佳解的方式不用而要用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)等多種以生物界為基底的演算法。
沒有留言:
張貼留言