一種求解RTVKP問(wèn)題的精確算法
推薦 + 挑錯(cuò) + 收藏(0) + 用戶(hù)評(píng)論（0）
隨機(jī)時(shí)變背包問(wèn)題（randomized time-varying knapsack problem，簡(jiǎn)稱(chēng)RTVKP）是一種動(dòng)態(tài)背包問(wèn)題，也是一種動(dòng)態(tài)組合優(yōu)化問(wèn)題，目前其求解算法主要是動(dòng)態(tài)規(guī)劃的精確算法、近似算法和遺傳算法．首先，利用動(dòng)態(tài)規(guī)劃提出了一種求解RTVKP問(wèn)題的精確算法，對(duì)算法時(shí)間復(fù)雜度的比較結(jié)果表明，它比已有的精確算法更適于求解背包載重較大的一類(lèi)RTVKP實(shí)例．然后，分別基于差分演化和粒子群優(yōu)化與貪心修正策略相結(jié)合，提出了求解RTVKP問(wèn)題的兩種進(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è)極好的近似解．
非常好我支持^.^
(0) 0%
不好我反對(duì)
(0) 0%
