柴夥說算法（9）-啓發式和演化算法

大自然的作品應該都稱得上是傑作。

--（古羅馬）西塞羅

啓發式算法廣泛地存在於求解NP難問題的數值求解算法中，它是根據目前的局部狀態下做出的一個決策，目的是爲了下一步的結果比當前的結果更加接近於理想的解。啓發式算法是一個基於直觀或經驗構造的算法，在可接受的花費下給出問題的一個可行解[1]。該類算法經常借鑑模擬自然界生物的覓食策略，如蟻羣算法，遺傳算法等。

演化算法也是模擬自然界生物的生存法則，它和啓發式算法的最主要的一點區別是，演化算法考慮多組解，然後從多組解中尋找合適的解；而啓發式算法只考慮一組解甚至是一組解的部分解（如禁忌搜索之於TSP問題）。當然，用於跳出局部最優的啓發式算法中的某些隨機性法則，同樣可以用到演化算法中。

和傳統算法確定性結果不同，由於在啓發式算法或者演化算法中使用了隨機策略，所以針對同一個問題，算法運行的結果一般不同。如果是最優問題，我們可以從多個結果中選取最好的那一個作爲問題的解。如果數值結果違反了約束條件的話，可以選取違反最小的那組解或者將解作平均（這是涉及到隨機或者概率方面經常使用的一種方法）。

後記：最近寫起東西來感覺力不從心，我把它理解成一個階段的瓶頸，堅持，堅持，再堅持……

參考資料：

[1]啓發式算法

https://baike.baidu.com/item/%E5%90%AF%E5%8F%91%E5%BC%8F%E7%AE%97%E6%B3%95/938987?fr=aladdin

[2] A*算法

https://www.gamedev.net/articles/programming/artificial-intelligence/a-pathfinding-for-beginners-r2003/

[3] How to solve it: Modern Heristics, (美)Zbigniew Michalewicz, David B.Fogel著，曹宏慶等譯，中國水利水電出版社，2003年