Re: [問題] 基因演算法收斂

看板Programming作者ddavid (謊言接線生)時間10年前 (2014/11/02 01:29)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/3 (看更多)

※ 引述《KJFC (KJFC)》之銘言： : 基因演算法收斂的時候 : 如果收斂在局部最佳解 : 那要怎麼跳脫比較好 : 我有試過調高突變率 : 但是效果不太好 : 在收斂前上下震盪 : 但是又不知道如何判斷是否接近收斂 : 如果在收斂後才震盪 : 有時又會收斂回局部解 : 請問這個問題應該怎麼解決? 首先你要知道，這不是一個可以100%解決的問題，我們做的事頂多是「嘗試」提升它掉到最佳解的機會，可是這只是機率上的，運氣不好或解的分佈很奇特的話，會掉到局部解就是會掉下去，沒法完全避免。回到你的問題，其實你的描述不太精確，你的說法意思是你過程中「曾經」碰到那個最佳解，但是後來又跳走？既然如此你的評估函式看到它的話應該會把它留下來才對呀？或者說是因為你的評估函式為了加速或某些特定原因所以並非100%準確，因此最佳解不一定得到最高分，所以有可能放走？如果是這樣，除了修正評估函式以外，頂多就是留下更多組讓最佳解留下來的機會更大吧。如果你的問題其實不是這樣，而是跳來跳去都不會跳到最佳解，一直在局部解跳，那就是調高突變讓它有機會跳出來跳到最佳解去，然後你可以嘗試使用如模擬退火（Simulated annealing）的方式慢慢把突變機率降下來，讓它慢慢地不亂跳。但這只是增加一些可能性而已，如你的描述，可能問題一開始就很容易落入局部解，不管大跳多少次孔明都挖好洞，你只能像曹操一樣每笑一次就逃一次，這樣的情況也沒什麼辦法。以下引用中文wiki，你提到的也正在基因演算法的最大問題之中，而我講的可能解法在最後一行：儘管遺傳演算法有許多優點，也有許多專家學者對遺傳演算法進行不斷研究，但目前存在的問題依然很多，如： (1)適應度值標定方式多種多樣，沒有一個簡潔、通用的方法，不利於對遺傳演算法的使用。 (2)遺傳演算法的早熟現象(即很快收斂到局部最優解而不是全局最優解)是迄今為止最難處理的關鍵問題，但可考慮自適應跟蹤成熟度[1]。 (3)快要接近最優解時在最優解附近左右擺動，收斂較慢。遺傳演算法通常需要解決以下問題，如確定編碼方案，適應度函數標定，選擇遺傳操作方式及相關控制參數，停止準則確定等。相應地，為改進簡單遺傳演算法的實際計算性能，很多學者的改進工作也是分別從參數編碼、初始群體設定、適應度函數標定、遺傳操作算子、控制參數的選擇以及遺傳演算法的結構等方面提出的。其基本途徑概括起來主要有下面幾個方面： (1)改進遺傳演算法的組成成分或使用技術，如選用優化控制參數、適合問題特性的編碼技術等。 (2)採用混合遺傳演算法(Hybrid Genetic Alogrithm)，比如混用簡單明了的粒子群演算法[2]。 (3)採用動態自適應技術，在進化過程中調整演算法控制參數和編碼精度，比如使用模糊自適應法[1]。 (4)採用非標準的遺傳操作算子。 (5)採用並行演算法。幾種常見的改進遺傳演算法： (1)分層遺傳演算法(Hierachic Genetic Alogrithm); (2)CHC演算法; (3)Messy遺傳演算法; (4)自適應遺傳演算法(Adaptive Genetic Alogrithm); (5)基於小生境技術的遺傳演算法(Niched Genetic Alorithm); (6)並行遺傳演算法(Parallel Genetic Algorithm); (7)混合遺傳演算法: ①遺傳演算法與最速下降法相結合的混合遺傳演算法； ②遺傳演算法與模擬退火法相結合的混合遺傳演算法。 -- 「如果你沒法給我個解釋的話，死一萬次也不能彌補你的過錯！」「我沒辦法死一萬次賠妳啊。」「可是你有辦法半死兩萬次，知道嗎，嗯？」－－蓮．席斯塔 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.175.125 ※ 文章網址: http://www.ptt.cc/bbs/Programming/M.1414862996.A.35A.html