本文關(guān)鍵詞：求解多維背包問題的蟻群-拉格朗日松弛混合優(yōu)化算法

  更多相關(guān)文章： 多維背包問題 蟻群優(yōu)化 拉格朗日松弛 核問題

【摘要】：針對(duì)多維背包問題(MKP)NP-hard、約束強(qiáng)的特點(diǎn),提出一種高效的蟻群-拉格朗日松弛(LR)混合優(yōu)化算法.該算法以蟻群優(yōu)化(ACO)為基本框架,并基于LR對(duì)偶信息定義了一種MKP效用指標(biāo).ACO使得整體算法具有全局搜索能力,所設(shè)計(jì)的效用指標(biāo)將MKP的優(yōu)化目標(biāo)與約束條件有機(jī)地融合在一起.該指標(biāo)一方面可以用來定義MKP核問題,降低問題規(guī)模;另一方面,可以用作ACO的啟發(fā)因子,引導(dǎo)算法在有希望的解區(qū)域中強(qiáng)化搜索.在大量標(biāo)準(zhǔn)算例上的測(cè)試結(jié)果表明,所提出算法的魯棒性較好;與其他已有算法相比,在求解質(zhì)量和求解效率方面均具有很強(qiáng)的競(jìng)爭(zhēng)力.
【作者單位】： 西安交通大學(xué)電子與信息工程學(xué)院;
【基金】：國(guó)家自然科學(xué)基金項(xiàng)目(61105126) 中國(guó)博士后科學(xué)基金項(xiàng)目(2014M560784)
【分類號(hào)】：TP18
【正文快照】： 0引言多維背包問題(MKP)是運(yùn)籌學(xué)領(lǐng)域一經(jīng)典的組合優(yōu)化問題,被證明是一種NP-hard問題,其求解目標(biāo)是在滿足各項(xiàng)資源約束的前提下,從候選對(duì)象集中找出可以使目標(biāo)價(jià)值達(dá)到最大的對(duì)象子集[1].MKP具有廣泛的工程背景,可以用來描述資本預(yù)算、資源分配、分布式數(shù)據(jù)庫處理等實(shí)際問題[2

【參考文獻(xiàn)】

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

1 歐陽海濱;高立群;孔祥勇;劉宏志;;一種求解0-1背包問題的二進(jìn)制修正和聲搜索算法[J];控制與決策;2014年07期

2 王凌;王圣堯;方晨;;一種求解多維背包問題的混合分布估計(jì)算法[J];控制與決策;2011年08期

3 張曉霞;唐立新;;一種新的求解MMKP問題的ACO&PR算法[J];控制與決策;2009年05期

4 喻學(xué)才;張?zhí)镂?;多維背包問題的一個(gè)蟻群優(yōu)化算法[J];計(jì)算機(jī)學(xué)報(bào);2008年05期

【共引文獻(xiàn)】

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

1 李枝勇;馬良;張惠珍;;求解多維背包問題的改進(jìn)布谷鳥搜索算法[J];控制工程;2016年07期

2 戴永壽;李韶光;李立剛;于肖雯;;基于改進(jìn)k-means和遺傳算法的油田特種車輛優(yōu)化調(diào)度[J];計(jì)算機(jī)應(yīng)用;2016年S1期

3 劉靜宜;韓海燕;;求解帶有利用率懲罰背包問題的參數(shù)自適應(yīng)差分進(jìn)化算法[J];科技視界;2016年16期

4 任志剛;趙松云;黃姍姍;梁永勝;;求解多維背包問題的蟻群-拉格朗日松弛混合優(yōu)化算法[J];控制與決策;2016年07期

5 錢淑渠;葉永強(qiáng);武慧虹;;貪婪封裝二進(jìn)制差分進(jìn)化算法求解高維背包問題[J];控制與決策;2016年05期

6 Lin Zhang;Kaili Rao;Ruchuan Wang;;T-QoS-aware based parallel ant colony algorithm for services composition[J];Journal of Systems Engineering and Electronics;2015年05期

7 王小彤;侯立剛;蘇成利;;一種改進(jìn)的蟻群算法求解多維背包問題[J];遼寧石油化工大學(xué)學(xué)報(bào);2015年04期

8 王勇臻;陳燕;李桃迎;張金松;;元胞分布估計(jì)算法求解高維0/1背包問題[J];小型微型計(jì)算機(jī)系統(tǒng);2015年06期

9 吳虎勝;張鳳鳴;戰(zhàn)仁軍;李浩;梁曉龍;;利用改進(jìn)的二進(jìn)制狼群算法求解多維背包問題[J];系統(tǒng)工程與電子技術(shù);2015年05期

10 孟祥虎;胡蓉;錢斌;;求解帶時(shí)間窗車輛路徑問題的有效混合PBIL算法[J];系統(tǒng)工程理論與實(shí)踐;2014年10期

【二級(jí)參考文獻(xiàn)】

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

1 李若平;歐陽海濱;高立群;鄒德旋;;學(xué)習(xí)型和聲搜索算法及其在0-1背包問題中的應(yīng)用[J];控制與決策;2013年02期

2 覃朝勇;黃景文;鄭建國(guó);莫國(guó)莉;;求解背包問題的混合量子進(jìn)化算法[J];小型微型計(jì)算機(jī)系統(tǒng);2011年02期

3 賀毅朝;寇應(yīng)展;陳致明;;求解多選擇背包問題的改進(jìn)差分演化算法[J];小型微型計(jì)算機(jī)系統(tǒng);2007年09期

4 楊廣益;歐陽智敏;全惠云;;松馳互補(bǔ)的分布估計(jì)算法求解多維背包問題[J];計(jì)算機(jī)工程與應(yīng)用;2007年12期

5 周樹德;孫增圻;;分布估計(jì)算法綜述[J];自動(dòng)化學(xué)報(bào);2007年02期

6 劉華鎣,林玉娥,劉金月;基于蟻群算法求解0/1背包問題[J];大慶石油學(xué)院學(xué)報(bào);2005年03期

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

8 于永新,張新榮;基于蟻群系統(tǒng)的多選擇背包問題優(yōu)化算法[J];計(jì)算機(jī)工程;2003年20期

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：1284683