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

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

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

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