本文選題：動(dòng)態(tài)規(guī)劃　切入點(diǎn)：時(shí)間復(fù)雜度　出處：《軟件學(xué)報(bào)》2017年02期 　論文類型：期刊論文

【摘要】：隨機(jī)時(shí)變背包問題(randomized time-varying knapsack problem,簡(jiǎn)稱RTVKP)是一種動(dòng)態(tài)背包問題,也是一種動(dòng)態(tài)組合優(yōu)化問題,目前其求解算法主要是動(dòng)態(tài)規(guī)劃的精確算法、近似算法和遺傳算法.首先,利用動(dòng)態(tài)規(guī)劃提出了一種求解RTVKP問題的精確算法,對(duì)算法時(shí)間復(fù)雜度的比較結(jié)果表明,它比已有的精確算法更適于求解背包載重較大的一類RTVKP實(shí)例.然后,分別基于差分演化和粒子群優(yōu)化與貪心修正策略相結(jié)合,提出了求解RTVKP問題的兩種進(jìn)化算法.對(duì)5個(gè)RTVKP實(shí)例的數(shù)值計(jì)算結(jié)果比較表明,精確算法一般不宜求解大規(guī)模的RTVKP實(shí)例,而基于差分演化、粒子群優(yōu)化和遺傳算法與貪心修正策略相結(jié)合的進(jìn)化算法卻不受實(shí)例規(guī)模與數(shù)據(jù)大小的影響,對(duì)于振蕩頻率大且具有較大數(shù)據(jù)的大規(guī)模RTVKP實(shí)例均能求得一個(gè)極好的近似解.
[Abstract]:Random time-varying knapsack problem (RTVKP) is a dynamic knapsack problem and a dynamic combinatorial optimization problem. At present, its solving algorithms are mainly precise algorithm of dynamic programming, approximate algorithm and genetic algorithm. In this paper, an exact algorithm for solving RTVKP problem is proposed by using dynamic programming. The comparison of the time complexity of the algorithm shows that it is more suitable for solving a class of RTVKP cases with large backpack load than the existing exact algorithm. Based on the combination of differential evolution and particle swarm optimization (PSO) and greedy correction strategy, two evolutionary algorithms for solving RTVKP problem are proposed. The numerical results of five RTVKP examples show that the exact algorithm is generally not suitable for solving large-scale RTVKP cases. However, based on differential evolution, the evolutionary algorithm based on particle swarm optimization and genetic algorithm combined with greedy correction strategy is not affected by the size of the instance and the size of the data. An excellent approximate solution can be obtained for large scale RTVKP examples with large oscillation frequency and large data.
【作者單位】： 河北地質(zhì)大學(xué)信息工程學(xué)院;河北師范大學(xué)軟件學(xué)院;深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院;河北師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院;
【基金】：國家自然科學(xué)基金(71371063,61170040)~~
【分類號(hào)】：TP301.6

【相似文獻(xiàn)】

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

1 白生明,張洪波;在地圖上量算面積的精確算法[J];油氣田地面工程;2000年01期

2 朱志軍;熊偉;王超;陳宏盛;;地理柵格影像的時(shí)空聚集精確算法[J];計(jì)算機(jī)工程與科學(xué);2012年03期

3 楊雪萍,丁書文;一種基于富氏算法的交流采樣精確算法[J];華北電力技術(shù);2000年06期

4 熊軻;裘正定;郭宇春;張宏科;秦雅娟;;多約束最短鏈路分離路徑精確算法[J];軟件學(xué)報(bào);2010年07期

5 王建新;許小雙;馮啟龍;李敏;;一種基于鏈暗示技術(shù)的Min-CVCB問題的精確算法[J];計(jì)算機(jī)研究與發(fā)展;2008年09期

6 李紹華;王建新;馬振宇;陳建二;;基于加權(quán)分治技術(shù)的set packing精確算法[J];小型微型計(jì)算機(jī)系統(tǒng);2010年06期

7 鄭興華;濾除衰減直流分量的全周傅氏精確算法[J];浙江電力;1998年01期

8 支志兵;寧愛兵;熊小華;王永斐;陳吉珍;楊曉芳;;刪除頂點(diǎn)生成二分圖問題的精確算法[J];小型微型計(jì)算機(jī)系統(tǒng);2014年09期

9 王建新;江國紅;李文軍;陳建二;;反饋集問題的研究進(jìn)展[J];計(jì)算機(jī)科學(xué);2011年01期

10 周一放,劉正士;一個(gè)求最佳一致逼近直線的快速精確算法[J];儀器儀表學(xué)報(bào);1993年01期

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

1 唐加福;汪定偉;;一類Fuzzy目標(biāo)／資源約束二次規(guī)劃問題非精確算法研究[A];1996中國控制與決策學(xué)術(shù)年會(huì)論文集[C];1996年

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

1 李佳;多行程模式下機(jī)場(chǎng)接送服務(wù)車次分配與調(diào)度問題的精確算法研究[D];東北大學(xué);2013年

2 曹夏夏;機(jī)場(chǎng)接送服務(wù)中車輛調(diào)度問題均衡模型的精確算法研究[D];東北大學(xué);2012年

3 石磊;使用度量與分治方法分析和設(shè)計(jì)精確算法[D];上海交通大學(xué);2010年

，

本文編號(hào)：1595096