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

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

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

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

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

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

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

5 趙學(xué)武;劉向嬌;王興;劉兵杰;;求解0-1背包問(wèn)題的遺傳算法[J];南陽(yáng)師范學(xué)院學(xué)報(bào);2014年06期

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

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

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

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

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

相關(guān)會(huì)議論文 前10條

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

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

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

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

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

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

7 馬雅凡;王海洋;隋琪;;基于QoS的服務(wù)選擇研究[A];2005通信理論與技術(shù)新進(jìn)展——第十屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集[C];2005年

8 武聰;趙鑫;;基于遺傳算法的背包問(wèn)題[A];2008'中國(guó)信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（二）[C];2008年

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

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

相關(guān)博士學(xué)位論文 前9條

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

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

3 黃斌超;限制性多重背包問(wèn)題的研究[D];云南大學(xué);2015年

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

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

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

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

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

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

相關(guān)碩士學(xué)位論文 前10條

1 龐潤(rùn)娟;求解0-1背包問(wèn)題的煙花算法[D];西安理工大學(xué);2019年

2 劉夢(mèng)佳;基于Memetic算法的多維背包問(wèn)題研究[D];昆明理工大學(xué);2018年

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

4 林百川;求解動(dòng)態(tài)約束背包問(wèn)題的改進(jìn)原對(duì)偶遺傳算法研究[D];東北大學(xué);2017年

5 付源翼;一種動(dòng)態(tài)多目標(biāo)背包問(wèn)題及其算法研究[D];東北大學(xué);2017年

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

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

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

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

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

，

本文編號(hào)：2608704