本文關(guān)鍵詞：改進螢火蟲算法求解0-1背包問題

  更多相關(guān)文章： 螢火蟲算法 0-1背包問題 收斂速度 優(yōu)化

【摘要】：0-1背包問題是組合優(yōu)化中經(jīng)典的NP難題之一,它是一個子集選取問題。學者們曾用回溯算法、動態(tài)規(guī)劃算法,以及多種群智能優(yōu)化算法來求解,但是都存在算法收斂速度過慢、時空復雜度高等問題。螢火蟲算法(GSO,Glowworm Swarm Optimization)是由Krishnanand提出的新型群智能優(yōu)化隨機算法,具有較強的通用性。本文將螢火蟲算法應用于解決0-1背包問題,并與動態(tài)規(guī)劃算法做比較。并且對螢火蟲優(yōu)化算法的理論基礎(chǔ)和實現(xiàn)方法等方面進行詳細介紹的同時分析螢火蟲算法存在的優(yōu)缺點,通過分析,雖然人工螢火蟲算法具有捕捉效率高等優(yōu)點,但也存在著易陷入局部最優(yōu),求解精度低等問題。在此基礎(chǔ)上,本文對螢火蟲優(yōu)化算法進行了兩點改進,首先是對于前期螢火蟲吸引度過小的歸一化處理:在傳統(tǒng)螢火蟲算法中,通過公式計算螢火蟲的吸引度,由于前期螢火蟲距離過大,導致吸引度趨于零。引入歸一化處理,對螢火蟲的距離進行統(tǒng)一規(guī)定使得計算螢火蟲吸引度更為合理,加強收斂度;其次是對螢火蟲算法后期迭代的改進:對螢火蟲算法后期的迭代次數(shù)中,由于螢火蟲之間的位置逐漸縮小,導致無法定位最優(yōu)位置,而在極值點附近震蕩。引入線性遞減的慣性權(quán)重,使得函數(shù)在迭代后期具有更高的精度,有更多的位置點在極值點附近。提出的改進改進的螢火蟲優(yōu)化算法,提高了基本螢火蟲算法的優(yōu)化能力。改進后的螢火蟲優(yōu)化算法根據(jù)基本螢火蟲算法的不足,對基本螢火蟲算法在前期吸引度和后期迭代上做了改進,并應用于0-1背包問題和一些連續(xù)函數(shù)。仿真實驗結(jié)果表明,改進后的螢火蟲算法在保證較快的收斂速度的同時,也實現(xiàn)了了算法的全局搜索和局部搜索能力,并表明螢火蟲算法在連續(xù)空間和離散空間優(yōu)化的可行性和有效性,具有良好的應用前景。
【關(guān)鍵詞】：螢火蟲算法 0-1背包問題 收斂速度 優(yōu)化
【學位授予單位】：西北師范大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP18
【目錄】：

• 摘要8-9
• ABSTRACT9-11
• 1.緒論11-16
• 1.1 課題背景及意義11-13
• 1.2 螢火蟲算法的國內(nèi)外研究現(xiàn)狀13-14
• 1.3 論文的創(chuàng)新工作14
• 1.4 本文的目標與組織結(jié)構(gòu)14-16
• 2.基本人工螢火蟲優(yōu)化算法16-25
• 2.1 螢火蟲優(yōu)化算法仿真原理及數(shù)學描述16-18
• 2.1.1 螢火蟲優(yōu)化算法仿真原理16-17
• 2.1.2 螢火蟲算法數(shù)學描述17-18
• 2.2 螢火蟲優(yōu)化算法實現(xiàn)步驟及流程圖18-20
• 2.3 螢火蟲優(yōu)化算法應用于 0-1 背包問題20
• 2.3.1 0-1 背包問題描述20
• 2.3.2 動態(tài)規(guī)劃算法等其他算法解 0-1 背包問題分析20
• 2.4 螢火蟲優(yōu)化算法收斂性分析20-22
• 2.5 螢火蟲優(yōu)化算法優(yōu)缺點22-24
• 2.6 小結(jié)24-25
• 3.改進的螢火蟲算法25-29
• 3.1 改進方法的描述25-26
• 3.2 改進后的算法步驟26-27
• 3.3 改進螢火蟲優(yōu)化算法實現(xiàn)流程圖27-28
• 3.4 小結(jié)28-29
• 4.仿真實驗結(jié)果29-33
• 4.1 螢火蟲算法實驗參數(shù)設(shè)置29
• 4.2 測試結(jié)果29-31
• 4.3 小結(jié)31-33
• 5.改進螢火蟲算法在其他問題上的尋優(yōu)分析33-39
• 5.1 IGSO與GSO在連續(xù)函數(shù)中測試33-37
• 5.2 小結(jié)37-39
• 6.總結(jié)與展望39-41
• 參考文獻41-46
• 攻讀學位期間發(fā)表的論文46-47
• 致謝47

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 何文明,朱起定;背包問題的循環(huán)及并行解[J];湘潭師范學院學報(社會科學版);2000年03期

2 任瑞征,嚴蔚敏;整數(shù)背包問題的應用及其算法研究[J];小型微型計算機系統(tǒng);2001年02期

3 葉俊,劉賢德,韓露;基于博弈論的背包問題優(yōu)化算法[J];華中科技大學學報(自然科學版);2003年09期

4 羅小虎,趙雷;一個解決0/1背包問題的蟻群方法[J];蘇州大學學報(工科版);2004年01期

5 宋翔,聶義勇,儲誠斌;無限制背包問題的爬山算法[J];小型微型計算機系統(tǒng);2004年07期

6 謝濤,陳火旺,康立山;二次背包問題的一種快速解法[J];計算機學報;2004年09期

7 王喜鳳;淺析0/1背包問題[J];電腦知識與技術(shù);2004年29期

8 華中生,張斌;求解可分離連續(xù)凸二次背包問題的直接算法[J];系統(tǒng)工程與電子技術(shù);2005年02期

9 宋海洲;魏旭真;;求解0-1背包問題的混合遺傳算法[J];華僑大學學報(自然科學版);2006年01期

10 熊偉清;魏平;王小權(quán);;蟻群算法求解多維0/1背包問題[J];計算機工程與科學;2006年10期

中國重要會議論文全文數(shù)據(jù)庫 前6條

1 喬善平;朱波;趙玲;;基于移動Agent的0-1背包問題分布式求解[A];2008'中國信息技術(shù)與應用學術(shù)論壇論文集（一）[C];2008年

2 高尚;;背包問題的分布估計算法[A];2013年中國智能自動化學術(shù)會議論文集（第五分冊）[C];2013年

3 徐俊杰;忻展紅;;粒子群優(yōu)化在0/1背包問題中的應用[A];中國運籌學會第七屆學術(shù)交流會論文集（上卷）[C];2004年

4 姜宇;蘇中濱;鄭萍;;求解O/1背包問題的算法綜述[A];黑龍江省計算機學會2009年學術(shù)交流年會論文集[C];2010年

5 劉裴寰;姜青山;王備戰(zhàn);史亮;;基于K均值聚類求解多維背包問題的算法[A];第二十三屆中國數(shù)據(jù)庫學術(shù)會議論文集（技術(shù)報告篇）[C];2006年

6 李偉;呂克偉;;類背包DH問題的比特安全性研究[A];第28次全國計算機安全學術(shù)交流會論文集[C];2013年

中國博士學位論文全文數(shù)據(jù)庫 前1條

1 TRUONG KHAC TUNG;[D];湖南大學;2013年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 史如意;帶流量約束的星型圖背包問題[D];浙江大學;2015年

2 孫飛;改進螢火蟲算法求解0-1背包問題[D];西北師范大學;2015年

3 潘夏福;混合蟻群算法求解0-1背包問題[D];廈門大學;2008年

4 朱閱岸;解0-1背包問題的算法比較和改進[D];暨南大學;2011年

5 史今馳;背包問題的實用求解算法研究[D];山東大學;2005年

6 鄭楊凡;基于屬性論的0-1背包問題算法研究[D];上海海事大學;2005年

7 李其;有償在線背包問題的研究[D];大連理工大學;2012年

8 孟曉笑;并行環(huán)境下0-1背包問題的解決策略[D];湖北大學;2011年

9 鐘海林;背包問題的一種新算法：降維遞歸算法[D];江西師范大學;2008年

10 趙培怡;改進群體智能算法及其在背包問題中的應用[D];山東大學;2007年

，

本文編號：1118038