發(fā)布時間：2020-03-31 06:28

【摘要】：背包問題作為運籌學中典型的NP難解問題,生活中許多問題都可以歸為此類,因此,對該問題的求解無論是在理論上,還是在實踐中都具有重要意義。目前隨著問題規(guī)模的增大,對此類問題的研究就有了更高的要求,而經(jīng)典的優(yōu)化方法更顯得無能為力。可喜的是,隨著群智能優(yōu)化算法的發(fā)展,也為解決此類問題開辟了新的思路。群智能優(yōu)化算法作為一種求解高維度和高復雜性優(yōu)化問題的有效方法,它是通過模擬生物群體間個體的相互作用及信息交流而衍生出的一種新型算法。煙花算法是通過模擬燃放煙花時煙花在空中的爆炸過程而實現(xiàn)的。因為該算法的參數(shù)較少,執(zhí)行過程簡單,尤其在解決高維復雜優(yōu)化問題上具有一定優(yōu)勢,所以目前已被廣泛關注。當然,也可以利用該算法求解背包問題。本論文主要做了如下的研究工作:1.給出了基于Logistic混沌映射和Sigmoid函數(shù)的煙花算法,并將其應用于求解經(jīng)典0-1背包問題。對于基本煙花算法來說,首先,煙花的初始化過程采用了有利于進行全局探索的隨機搜索方式,可是往往較難進行細致的局部開發(fā)。故這里采用被廣泛應用的Logistic混沌映射進行初始化,從而初始煙花的分布位置更加均勻,且搜索能力更強;其次,煙花的爆炸半徑不利于搜索速度與求解精度的平衡,故引入Sigmoid函數(shù)來構造遞減的爆炸半徑,使得在迭代前期,爆炸半徑保持更長時間的較大值,進行充分的全局探索,在迭代后期,爆炸半徑保持更長時間的較小值,進行細致的局部開發(fā),平衡了搜索速度與求解精度;最后,對標準測試函數(shù)進行測試,并與其它算法進行對比,實驗結果表明改進算法的性能更優(yōu);并且將其應用于求解經(jīng)典0-1背包問題,實驗結果證明改進算法在解決實際優(yōu)化問題上是有效的。2.提出利用Kent映射、余弦函數(shù)和交叉變異思想改進基本煙花算法,并將其應用于求解折扣0-1背包問題。首先,為了解決基本煙花算法的隨機搜索問題,采用了與Logistic混沌映射同構的Kent映射規(guī)則來提高搜索精度;其次,利用余弦函數(shù)設計了分段爆炸半徑,使得半徑在前1/2迭代過程中保持遞減,后1/2迭代過程中及時適當增大來避免煙花陷入局部最優(yōu),這樣就可以利用對爆炸半徑的計算方法達到有目的的對于爆炸方向進行引導,從而避免了盲目性,節(jié)省了搜索時間;接著,利用交叉變異思想對高斯變異過程進行了改進來優(yōu)化變異過程,從而進一步提升了算法尋優(yōu)性能。最后,對標準測試函數(shù)和折扣0-1背包進行了求解,仿真結果表明,所提算法比其它群智能算法的結果更優(yōu),達到了改進算法性能的目的。
【學位授予單位】：西安理工大學
【學位級別】：碩士
【學位授予年份】：2019
【分類號】：TP18

【相似文獻】

相關期刊論文 前10條

1 田秀芹;;求解0-1背包問題算法研究[J];現(xiàn)代經(jīng)濟信息;2017年07期

2 錢淑渠;武慧虹;林妤;;求解高維動態(tài)背包問題的克隆修復免疫算法[J];計算機工程;2017年09期

3 于洋;;淺析利用動態(tài)規(guī)劃法求解0-1背包問題[J];計算機光盤軟件與應用;2015年03期

4 史嵐;張義宏;呂建輝;;基于絕對貪心和預期效率的0-1背包問題優(yōu)化[J];計算機應用研究;2014年03期

5 趙學武;劉向嬌;王興;劉兵杰;;求解0-1背包問題的遺傳算法[J];南陽師范學院學報;2014年06期

6 劉朝霞;;求解0-1背包問題的兩種算法設計[J];陰山學刊(自然科學版);2014年03期

7 王杉林;楊雪絨;;解二次背包問題的一個線性化方法[J];蘭州文理學院學報(自然科學版);2014年05期

8 樂天;;遺傳算法求解0/1背包問題的綜述[J];浙江海洋學院學報(自然科學版);2013年01期

9 朱婷婷;陳偉;陳娟娟;孫文浩;;一類連續(xù)可分離背包問題的直接算法[J];運籌學學報;2013年01期

10 王志剛;夏慧明;王明剛;郭廣寒;;求解多維背包問題的改進二進制粒子群算法[J];數(shù)學的實踐與認識;2013年19期

相關會議論文 前10條

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

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

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

4 武繼剛;喬占科;;制定大型生產(chǎn)計劃的一個貪心算法[A];1996中國控制與決策學術年會論文集[C];1996年

5 王躍虎;周武藝;;基于背包序列的圖像加密算法[A];第十二屆全國圖象圖形學學術會議論文集[C];2005年

6 羅景峰;;均勻設計在魚群算法參數(shù)設定中的應用[A];第四屆中國智能計算大會論文集[C];2010年

7 馬雅凡;王海洋;隋琪;;基于QoS的服務選擇研究[A];2005通信理論與技術新進展——第十屆全國青年通信學術會議論文集[C];2005年

8 武聰;趙鑫;;基于遺傳算法的背包問題[A];2008'中國信息技術與應用學術論壇論文集（二）[C];2008年

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

10 何翠紅;區(qū)益善;;用結構遺傳算法進行非平穩(wěn)函數(shù)優(yōu)化[A];1997中國控制與決策學術年會論文集[C];1997年

相關博士學位論文 前9條

1 秦進;二次多背包問題及其擴展問題的啟發(fā)式算法研究[D];華中科技大學;2017年

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

3 黃斌超;限制性多重背包問題的研究[D];云南大學;2015年

4 李劍;微粒群算法及其在物流系統(tǒng)中的應用研究[D];華中科技大學;2008年

5 冀淑慧;基于SDP松弛的整數(shù)規(guī)劃凸化方法研究[D];復旦大學;2012年

6 李艷艷;0-1規(guī)劃問題的連續(xù)化方法研究及應用[D];大連理工大學;2009年

7 王鳳華;多路徑傳輸管理技術的研究[D];北京郵電大學;2014年

8 王煉紅;人工免疫優(yōu)化與分類算法及其應用研究[D];湖南大學;2009年

9 崔司千;STDMA多跳無線網(wǎng)絡分布式時隙共享策略研究[D];哈爾濱工業(yè)大學;2016年

相關碩士學位論文 前10條

1 龐潤娟;求解0-1背包問題的煙花算法[D];西安理工大學;2019年

2 劉夢佳;基于Memetic算法的多維背包問題研究[D];昆明理工大學;2018年

3 馬寧;凹函數(shù)下在線背包問題的研究[D];大連理工大學;2018年

4 林百川;求解動態(tài)約束背包問題的改進原對偶遺傳算法研究[D];東北大學;2017年

5 付源翼;一種動態(tài)多目標背包問題及其算法研究[D];東北大學;2017年

6 溫亞楠;L1范數(shù)正則化連續(xù)二次背包問題算法研究[D];沈陽航空航天大學;2018年

7 陳烏吉瑪;基于綜合背包問題的混合貪婪算法的研究[D];吉林大學;2017年

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

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

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

，

本文編號：2608704