遺傳演算法相對於窮舉演算法可以減少多少計算量?

例如窮舉的話需要運行1000次,那一般設置種群數為多少,設置幾代才合適,所需的計算總次數有沒有經驗值,或是相關的文獻支持呢?或是通常做法是嘗試嗎?


遺傳演算法,剝去層層外皮,本質上就是靠蒙。只是人家蒙得有手段,調得一手好參數,於是出來的近似解也不錯。


所以說這個問題的答案就是【通常做法是嘗試】。等你試個十年八年,你也有感覺了,以後也蒙得准了。


這完全取決於問題本身,遺傳演算法也是一種基於先驗假設的優化,
當這種假設不成立時,反而對解題有害,
比如這種情況,最優秀的參數只分布在一群最糟糕的參數附近。


這兩天正好寫了些遺傳演算法相關的程序,下面只是個人經驗,沒有理論依據:
1、遺傳演算法的效果 通常 受 雜交方式 影響很大,有些問題 受 初始種群、適應度函數的影響也很大,選擇方式 的影響一般較小。雜交方式應該根據具體問題定製,而不能生搬硬套某個固定的方式;
2、如果自適應函數較為平滑(把染色體編碼當作自變數),則收斂效果很好;如果自適應函數有很多突變,則效果很差,甚至還不如窮舉;

種群必須足夠大,迭代次數隨問題的不同而不同。
可以通過精英判斷,如果一個精英,連續好幾代都沒被超越,則可以停止計算,這個精英作為近似解。
--------
以上純屬個人扯淡,沒有任何理論依據,也非引用前人結論。
本人也剛接觸遺傳演算法,所以上面說的很可能是錯的,僅僅作為參考。


還是那句話,取決於你要解決什麼問題,像破解密碼這類大海撈針的問題,遺傳演算法不可能有結果,例如,破解一個四位數的密碼0~9999,假定密碼是1234,密碼匹配為1,不匹配為0,當遺傳演算法生成第一代子代時,即使1235, 1233這類和1234很靠近的個體,與最優解的距離為1,對於第二代子代完全沒有任何指導意義,因為不知道那些個體屬於優勢個體。
所以,適用遺傳演算法的問題有一個基本的假設,即在最優解附近應是次優解(類似凸優化),這樣隨著代數的增加,才能趨近最優解,但只是趨近。一般會預設一些閾值,如1)新的最優解/上一次最優解接近1;2)生成代數不超過給定值;如果達到這些標準就停止或者增加變異跳出局部次優解。


無論你設置多少代,遺傳演算法都不保證有最優解,數據量小還是不要用遺傳演算法了。而且遺傳演算法還會有重複計算。


推薦閱讀:

圍棋有沒有必勝策略?
怎樣判斷平面上一個矩形和一個圓形是否有重疊?

TAG:演算法 | 遺傳演算法 | 計算機科學 | 演算法設計 |