在Haskell程序中從堆棧溢出或堆耗盡中恢復

Question

我目前正在Haskell中編寫遺傳算法，其中我的染色體是代表可執行系統的相當複雜的結構。

爲了讓我評估我的染色體的適應性，我必須運行一個evolution函數，它執行給定系統的一個計算週期。然後通過計算在系統沒有變化（在這種情況下系統終止）之前應用evolution多少次來計算適應度。

現在的問題如下：一些系統可以運行無限長，永遠不會終止 - 我想懲罰那些（通過給他們一點分數）。我可以簡單地對步數設定一定的限制，但它不能解決另一個問題。

我的一些系統執行指數計算（即使對於它們增長到巨大尺寸的evloution步驟的小值）並且它們導致ERROR - Control stack overflow。對於人類觀察者來說，很明顯，他們永遠不會終止，但算法無法知道，因此它運行和壓碎。

我的問題是：是否有可能從這樣的錯誤中恢復？我希望我的算法在遇到這個問題後繼續運行，並相應地調整染色體得分。

在我看來，最好的解決方案是告訴程序：「嘿，試試這個，但如果你失敗了，別擔心，我知道如何處理它」。但我甚至不確定這是否可能。如果沒有 - 是否有其他選擇？

Answer 1

這將很難從哈斯克爾內部可靠地完成 - 儘管在某些條件下GHC will raise exceptions for these conditions。 （你需要GHC 7）。

import Control.Exception 

如果你真的想抓住堆棧溢出，這是可能的，如下例所示：

> handle (\StackOverflow -> return Nothing) $ 
       return . Just $! foldr (+) 0 (replicate (2^25) 1) 
Nothing 

或捕捉任何異步異常（包括堆耗盡）：

> handle (\(e :: AsyncException) -> print e >> return Nothing) $ 
       return . Just $! foldr (+) 0 (replicate (2^25) 1) 
stack overflow 
Nothing 

但是，這是脆弱的。

或者，使用GHC flags，您可以在GHC編譯過程中強制執行最大堆棧（或堆）大小，如果它超過了這些限制（GHC似乎沒有最大堆棧限制），就會被終止。

如果編譯GHC您的Haskell程序（如推薦），運行它爲：

$ ghc -O --make A.hs -rtsopts 

低於低堆強制限制：

$ ./A +RTS -M1M -K1M 
Heap exhausted; 

這需要GHC。 （同樣，你不應該用Hugs來做這種工作）。最後，你應該確保你的程序不要首先使用過多的堆棧，通過profiling in GHC。

Answer 2

It seems to me like the best solution would be to tell the program: 
"Hey, try doing this, but if you fail don't worry. I know how to handle it" 

在大多數語言將是try/catch塊。我不確定haskell中的等價物是什麼，或者即使存在一些等價物。此外，我懷疑try/catch構造可以有效地捕獲/處理堆棧溢出情況。

但是有可能應用一些合理的約束來防止發生溢出嗎？例如，也許你可以設置一個系統大小的上限，並監視每個系統如何從一個迭代到下一個迭代接近邊界。然後，你可以執行一條規則，例如「如果在一個系統上超過其上限或消耗超過其先前分配與其上限之間剩餘空間的50％，則該系統終止並且遭受分數懲罰」。

Answer 3

我認爲這裏的一個通用解決方案是提供一種測量計算時間的方法，如果它花費太多時間，就會殺死它。如果它是遞歸的，您可以簡單地將計數器添加到您的評估函數中，如果它下降到零，則返回錯誤值 - 例如Nothing，否則它是Just result。

這種方法可以通過其他方式實現，而不是顯式計數參數，例如將此計數器放入評估使用的monad中（如果您的代碼是monadic），或者通過在單獨的線程中運行計算，時間到。

我寧願使用任何純粹的解決方案，因爲它會更可靠。

Answer 4

關於你的遺傳算法的思考：你的染色體的適應性的一部分是它們不消耗太多的計算資源。你問的問題定義了「太多資源」與運行時系統崩潰。這是一個相當隨意的，有些隨意的措施。

知道它會增加您的evolve函數的複雜性，我仍然會建議讓這個函數知道染色體消耗的計算資源。這可以讓你微調它何時「吃得太多」，過早死於「飢餓」。它也可能允許您根據染色體指數速度的快慢來調整您的懲罰，因爲只有幾乎指數的染色體更適合具有極高分支因子的染色體。