本文關(guān)鍵詞：改進(jìn)螢火蟲(chóng)算法求解0-1背包問(wèn)題

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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

6 謝濤,陳火旺,康立山;二次背包問(wèn)題的一種快速解法[J];計(jì)算機(jī)學(xué)報(bào);2004年09期

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

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

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

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

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

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

2 高尚;;背包問(wèn)題的分布估計(jì)算法[A];2013年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（第五分冊(cè)）[C];2013年

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

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

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

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

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

1 TRUONG KHAC TUNG;[D];湖南大學(xué);2013年

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

1 史如意;帶流量約束的星型圖背包問(wèn)題[D];浙江大學(xué);2015年

2 孫飛;改進(jìn)螢火蟲(chóng)算法求解0-1背包問(wèn)題[D];西北師范大學(xué);2015年

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

4 朱閱岸;解0-1背包問(wèn)題的算法比較和改進(jìn)[D];暨南大學(xué);2011年

5 史今馳;背包問(wèn)題的實(shí)用求解算法研究[D];山東大學(xué);2005年

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

7 李其;有償在線背包問(wèn)題的研究[D];大連理工大學(xué);2012年

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

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

10 趙培怡;改進(jìn)群體智能算法及其在背包問(wèn)題中的應(yīng)用[D];山東大學(xué);2007年

，

本文編號(hào)：1118038