粒子群優(yōu)化算法應(yīng)用分析

《粒子群優(yōu)化算法應(yīng)用分析》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、粒子群優(yōu)化算法應(yīng)用研究第一章緒論本章簡要介紹了粒子群優(yōu)化算法的起源及研究意義，說明了本文的主要工作及論文結(jié)構(gòu)。1．1粒子群優(yōu)化算法研究意義粒子群優(yōu)化算法(ParticleSwarmOptimization，PSO)是由美國的Kennedy和Eberhart在1995年提出的【1】。在粒子群優(yōu)化算法中，每個(gè)粒子作為優(yōu)化問題的一個(gè)可行解，并由目標(biāo)函數(shù)為其確定一個(gè)適應(yīng)值，粒子在搜索空間中以一定的速度飛行。每個(gè)粒子在搜索時(shí)，追隨自己搜索到的歷史最優(yōu)值和群體歷史最優(yōu)值，在此基礎(chǔ)上進(jìn)行速度和位置的更新。PSO基本

2、模型與遺傳算法類似，是一種基于迭代的優(yōu)化工具。但是在算法實(shí)現(xiàn)過程中沒有交叉、變異操作，而是以粒子對解空間中最優(yōu)粒子的追隨進(jìn)行解空間的搜索。同遺傳算法相比，PSO的優(yōu)點(diǎn)在于流程簡單，容易實(shí)現(xiàn)，算法參數(shù)簡潔，無需復(fù)雜的調(diào)整。因此，粒子群優(yōu)化算法一提出，立刻引起了進(jìn)化計(jì)算等領(lǐng)域?qū)W者們的廣泛關(guān)注，在短短幾年時(shí)間里出現(xiàn)大量的研究成果，成為進(jìn)化計(jì)算領(lǐng)域內(nèi)的一個(gè)研究熱點(diǎn)。粒子群優(yōu)化算法最早應(yīng)用于連續(xù)函數(shù)優(yōu)化和人工神經(jīng)網(wǎng)絡(luò)訓(xùn)練【2】。隨后，PSO算法在約束優(yōu)化、數(shù)據(jù)聚類、模式識別、電力系統(tǒng)等問題中均得到了成功的應(yīng)用。

3、隨著對PSO研究地不斷深入，學(xué)者們提出了多種改進(jìn)的PSO算法，廣泛應(yīng)用于函數(shù)優(yōu)化、集成電路設(shè)計(jì)、模糊系統(tǒng)控制等多個(gè)領(lǐng)域。當(dāng)然，PSO還是一種新興的智能優(yōu)化算法，研究粒子群優(yōu)化算法與其他元啟發(fā)算法的融合，進(jìn)一步拓展其應(yīng)用領(lǐng)域是值得關(guān)注的熱點(diǎn)，更是一項(xiàng)非常有意義的工作。1．2本文主要工作及論文結(jié)構(gòu)1．2．1本文主要工作學(xué)習(xí)了粒子群優(yōu)化算法、模擬退火算法、遺傳算法、禁忌搜索算法等常用元啟發(fā)算法，研究了粒子群優(yōu)化算法與其他元啟發(fā)算法的融合技術(shù)，拓展了粒子群優(yōu)化算法的應(yīng)用。第一章緒論粒子群優(yōu)化算法應(yīng)用研究對蛋白

4、質(zhì)折疊結(jié)構(gòu)的預(yù)測和研究在蛋白質(zhì)工程中有著極其重要的意義。傳統(tǒng)的蛋白質(zhì)結(jié)構(gòu)測定方法，如X射線晶體衍射方法、核磁共振技術(shù)的測定速度都比較緩慢，只能限于較短序列的蛋白質(zhì)結(jié)構(gòu)測定[3】。因而，利用計(jì)算機(jī)的高效計(jì)算能力來預(yù)測蛋白質(zhì)結(jié)構(gòu)已成為當(dāng)前的研究熱點(diǎn)，但其計(jì)算量卻非常驚人，折疊空間隨著蛋白質(zhì)序列的長度的增長呈指數(shù)級增長。為此，相關(guān)學(xué)者提出了各種簡化模型。Stillinger等提出的Toy模型比HP格點(diǎn)模型更接近真實(shí)蛋白質(zhì)。目前，已有學(xué)者采用元啟發(fā)式算法應(yīng)用到Toy模型中進(jìn)行蛋白質(zhì)折疊結(jié)構(gòu)預(yù)測。二次分配問題(

5、QuadraticAssignmentProblem，QAP)是一個(gè)經(jīng)典的組合優(yōu)化問題[4】，目的是尋找n個(gè)設(shè)備到n個(gè)位置的最優(yōu)布局。該問題具有重要的理論與實(shí)用價(jià)值，許多實(shí)際的問題，如：大學(xué)校園中建筑物的布局、醫(yī)院中科室的安排、鍵盤布局問題等都可以轉(zhuǎn)化為QnP來解決[5，6】。QAP是一個(gè)NP-Hard問題[7】，無法尋找求解QAV的多項(xiàng)式時(shí)間算法。一般來說，當(dāng)問題規(guī)模n>20時(shí)就很難找到最優(yōu)解。為了實(shí)際可行地解決二次分配問題，人們廣泛采用元啟發(fā)式算法，以便在較短的時(shí)間內(nèi)求得較優(yōu)解。本文對粒子群優(yōu)化算

6、法進(jìn)行改進(jìn)，并分別與爬山算法、模擬退火算法和遺傳算法、禁忌搜索算法進(jìn)行融合，形成了隨機(jī)擾動(dòng)粒子群．爬山算法和混合離散粒子群優(yōu)化算法，分別用于蛋白質(zhì)折疊結(jié)構(gòu)預(yù)測和求解二次分配問題，拓展了粒子群優(yōu)化算法的應(yīng)用，取得了良好的效果，并探討了混合離散粒子群優(yōu)化算法在OpenMP上的并行實(shí)現(xiàn)技術(shù)。1．2．2論文結(jié)構(gòu)全文共分為五章，各章的內(nèi)容安排如下：第一章首先介紹了粒子群優(yōu)化算法的研究意義，給出了本文主要工作和論文結(jié)構(gòu)。第二章詳細(xì)介紹了標(biāo)準(zhǔn)粒子群優(yōu)化算法的原理，分析了粒子群優(yōu)化算法的研究現(xiàn)狀，并簡要介紹了與本文相

7、關(guān)的其他元啟發(fā)算法。第三章采用粒子群優(yōu)化算法求解連續(xù)優(yōu)化問題——應(yīng)用到二維TOy模型中進(jìn)行蛋白質(zhì)折疊結(jié)構(gòu)預(yù)測。介紹了蛋白質(zhì)折疊結(jié)構(gòu)預(yù)測中的相關(guān)知識，其中包括蛋白質(zhì)結(jié)構(gòu)功能的關(guān)系、蛋白質(zhì)結(jié)構(gòu)預(yù)測問題的發(fā)展及其重要性、HP格點(diǎn)模型以及TOy模型。2粒了群優(yōu)化算法應(yīng)用研究第一章緒論提出了一種隨機(jī)擾動(dòng)粒子群優(yōu)化算法，并與爬山算法融合，應(yīng)用到二維Toy模型中進(jìn)行蛋白質(zhì)折疊結(jié)構(gòu)預(yù)測，并給出了在Fibonacci測試序列及真實(shí)蛋白質(zhì)序列上的測試結(jié)果。第四章針對目前PS0算法對離散優(yōu)化問題研究甚少的情況，嘗試了粒子群

8、優(yōu)化算法在離散優(yōu)化問題上的應(yīng)用——求解二次分配問題。對二次分配問題作了詳細(xì)介紹，對標(biāo)準(zhǔn)粒子群優(yōu)化算法進(jìn)行改進(jìn)，與遺傳算法、禁忌搜索算法進(jìn)行融合，提出了一種求解二次分配問題的混合離散粒子群優(yōu)化算法，并給出了在QAPLIB數(shù)據(jù)上的測試結(jié)果。為了進(jìn)一步驗(yàn)證本章算法的有效性及加速運(yùn)行，研究了基于OpenMP的并行算法及其實(shí)現(xiàn)。第五章是對本文的總結(jié)與展望。論文結(jié)構(gòu)如圖1．1所示。l經(jīng)典元啟發(fā)算法介紹(2．1節(jié))l旺!、．．■．’‘’I～’●．，?——11一上'’．