求解圓形Packing問題及模型蛋白結構預測問題的啟發(fā)式算法.pdf

1、求解NP難度問題是計算機科學技術的一個瓶頸任務。近年來研究表明,對于NP難度問題可能根本不存在既完整嚴格又不太慢的求解算法。研究者們試圖從生物進化過程、物理運動過程以及人類社會中等得到啟發(fā),以期得到關于該類問題的非絕對完整的,但是高效的近似的啟發(fā)式求解算法。于是,一些具有高效優(yōu)化性能,無需問題特殊信息等優(yōu)點的現(xiàn)代啟發(fā)式算法相繼出現(xiàn),如進化算法、模擬退火算法、禁忌搜索算法、蟻群算法等。這些計算方法大大豐富了現(xiàn)代優(yōu)化技術,也為傳統(tǒng)最優(yōu)化技術

2、難以處理的NP難度問題提供了切實可行的解決方案。本文對其中的貪心算法,局部搜索算法,模擬退火算法,禁忌搜索算法,遺傳算法,蒙特卡洛算法等進行了簡單的介紹,并重點研究了圓(球)形Packing問題以及模型蛋白結構預測問題的現(xiàn)代啟發(fā)式求解算法。
　　 首先,基于擬人化思想,為勢能曲面變平法提出了一種高效的構形更新策略。通過將改進的勢能曲面變平法(ELP+)與基于自適應步長的梯度法相結合,得到一種求解圓形Packing問題的混合算法。

3、
　　 其次,通過對禁忌搜索算法的鄰域解,禁忌對象和當前解的接受原則進行改進,得到改進的禁忌搜索算法,并將改進的禁忌搜索算法和基于自適應步長的梯度算法相結合,提出了一種求解球形Packing問題的基于禁忌搜索的啟發(fā)式算法。
　　 另外,考慮到改進的ELP(ELP+)方法的高效優(yōu)化性能,本文將ELP+方法應用到HP格點模型中去進行蛋白質(zhì)結構預測,提出了一種高效的啟發(fā)式算法。算法首先利用貪心策略產(chǎn)生初始構形,然后利用牽引移動