我正在尋找算法來查找「最佳」參數值集。有問題的功能有很多局部最小值,並且變化很快。更糟的是,測試一組參數非常慢 - 大約1分鐘 - 我無法直接計算梯度。使用大量本地最小值進行多參數優化
有沒有這種優化的任何衆所周知的算法?
我剛剛嘗試隨機值時取得了中等成功。我想知道是否可以通過使隨機參數選擇器選擇參數的機會接近過去產生不良結果的參數,從而提高性能。有沒有這個方法的名稱,以便我可以搜索具體的建議?
更多信息:
- 參數是連續
- 有5-10參數的順序。當然不會超過10個。
我正在尋找算法來查找「最佳」參數值集。有問題的功能有很多局部最小值,並且變化很快。更糟的是,測試一組參數非常慢 - 大約1分鐘 - 我無法直接計算梯度。使用大量本地最小值進行多參數優化
有沒有這種優化的任何衆所周知的算法?
我剛剛嘗試隨機值時取得了中等成功。我想知道是否可以通過使隨機參數選擇器選擇參數的機會接近過去產生不良結果的參數,從而提高性能。有沒有這個方法的名稱,以便我可以搜索具體的建議?
更多信息:
我已經試過模擬退火和粒子羣算法。 (作爲提醒,我不能使用梯度下降,因爲無法計算梯度)。
我也嘗試了一種算法,執行以下操作:
該「正交方向」是由創建與尺寸的必要數目的隨機正交矩陣(適於this code)生成。
如果沿正交方向移動改善了結果,算法只是繼續該方向。如果沒有方向改善結果,則跳躍距離減半,並嘗試一組新的正交方向。最終算法得出結論,它必須在本地最小值,記住它並重新開始一個新的隨機點。
這種方法比模擬退火和粒子羣執行效果要好得多:它需要較少的(很慢)函數評估才能達到相同質量的結果。
當然,我的S.A.和P.S.O的實現。很可能有缺陷 - 這些都是棘手的算法,有很多調整參數的空間。但我只是想我會提到最適合我的東西。
我真的無法幫助您找到適合您的特定問題的算法。
但是,在隨機選擇參數方面,我認爲你要找的是genetic algorithms。遺傳算法通常基於選擇一些隨機輸入,選擇那些對於該問題來說最適合(迄今)的那些輸入,並隨機地對它們進行變異/組合以產生下一代,再次選擇最佳。
如果函數或多或少是連續的(即良好輸入的小突變通常不會產生不良輸入(小是有點泛化的)),這對您的問題會非常有效。
有多少個參數 - 例如,搜索空間有多少維?它們是連續的還是離散的 - 例如,實數,整數還是隻有幾個可能的值?
我見過的用於這類問題的方法有一個相似的整體結構 - 取大量的採樣點,並將它們全部調整到具有某種「好」答案的區域。既然你有很多的分數,他們的相對差異可以作爲臨時的梯度。
維基百科的鏈接有前兩個的僞代碼; GA方法有很多種,很難列出一種算法,但可以從那裏跟蹤鏈接。請注意,上述所有的實現都可以用作起點。
請注意,所有這些 - 實際上這種大規模搜索算法的任何方法 - 都是啓發式算法,這意味着它們的參數必須根據您的特定問題進行調整。這可能很乏味。
順便說一句,功能評估如此昂貴的事實可以使你爲你工作一點;由於以上所有方法都涉及大量獨立函數評估,因此可以使用OpenMP或類似方法對該算法進行平行並行處理,以便使用與計算機上一樣多的核心。
有至少4-5和至多10參數,並且它們是連續的。感謝您的鏈接,將採取好看!遺傳算法可能不適合,因爲參數太少了,我真的懷疑在我的情況下,結合使用兩套好套件會產生更好的結果。評估已經平行,每個參數集使用我所有的4個核心,時間爲30-60秒。 – 2010-10-10 15:31:57
+1,我用模擬退火處理類似的問題。 – FogleBird 2010-10-11 00:32:35
你的情況似乎是相似的Software to Tune/Calibrate Properties for Heuristic Algorithms的海報,我會給你同樣的忠告I gave there:考慮Metropolis-Hastings像多步行者和步長的模擬退火算法。
在您的案例中使用蒙特卡羅方法的困難是對每個候選人進行昂貴的評估。 與您手頭上的時間相比,如何?如果你在幾分鐘內需要一個好的答案,這個速度還不夠快。如果你可以讓它在一夜之間運行,它會很好地工作。
給定一個複雜的搜索空間,我建議隨機初始分佈式。您的最終答案可能僅僅是整個運行過程中記錄的最好的單個結果,或者是具有最佳結果的步行者的平均位置。
不要被推遲,我正在討論的最大化,你想最小化:優點值可以否定或倒置。
沒有通用的方法來回答你的問題。關於這個主題有很多書/論文,但你必須根據你的需要選擇你的路徑,這裏沒有清楚說出。
有些事情要知道,但是 - 1分鐘/測試對於任何算法來說都太過於處理。我猜你的情況,你必須真正執行下列操作之一:
我想我必須在一個點上得到100臺電腦一兩天,但我必須相當肯定我在做這些之前充分利用它們...... :) – 2010-10-11 00:19:42
你可以發佈你的功能模型嗎?如果可能的話,請給出你想要建模的暗示... – 2010-10-10 21:43:06
@belisarius這些參數是設計用於玩特定遊戲的AI中的調整因子。例如,像調整評估給定位置的「威脅級別」的函數一樣。我優化中的「評估」步驟會產生AI正在開發的AI在固定的一組地圖上贏得一組固定的其他AI的次數。 (我知道這確實在這些特定地圖上針對這些特定對手進行了優化,但希望調整因素太少以至於沒有適合的範圍) – 2010-10-11 00:18:04