Algorithms for randomized time-varying knapsack problems

被引：27

作者：

He, Yichao ^{[1
]}

Zhang, Xinlu ^{[2
]}

Li, Wenbin ^{[3
]}

Li, Xiang ^{[4
]}

Wu, Weili ^{[5
]}

Gao, Suogang ^{[2
]}

机构：

[1] Shijiazhuang Univ Econ, Coll Informat Engn, Shijiazhuang 050031, Peoples R China

[2] Hebei Normal Univ, Coll Math & Informat Sci, Shijiazhuang 050024, Peoples R China

[3] Shijiazhuang Univ Econ, Lab Network & Informat Secur, Shijiazhuang 050031, Peoples R China

[4] Univ Florida, Dept Ind & Syst Engn, Gainesville, FL 32611 USA

[5] Univ Texas Dallas, Dept Comp Sci, Richardson, TX 75080 USA

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2016年 / 31卷 / 01期

基金：

高等学校博士学科点专项科研基金;

关键词：

Knapsack problem; Exact algorithm; Approximations; Heuristics; PARTICLE SWARM OPTIMIZATION; EVOLUTIONARY ALGORITHM; GENETIC ALGORITHMS; DIFFERENTIAL EVOLUTION;

D O I：

10.1007/s10878-014-9717-1

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this paper, we first give the definition of randomized time-varying knapsack problems () and its mathematic model, and analyze the character about the various forms of . Next, we propose three algorithms for : (1) an exact algorithm with pseudo-polynomial time based on dynamic programming; (2) a 2-approximation algorithm for based on greedy algorithm; (3) a heuristic algorithm by using elitists model based on genetic algorithms. Finally, we advance an evaluation criterion for the algorithm which is used for solving dynamic combinational optimization problems, and analyze the virtue and shortage of three algorithms above by using the criterion. For the given three instances of , the simulation computation results coincide with the theory analysis.

引用

页码：95 / 117

页数：23

共 37 条

[1]

[Anonymous], 2013, Evolutionary Optimization Algorithms

[2]

[Anonymous], 2000, WIL INT S D

[3]

Ashlock D, 2006, Evolutionary Computation for Modeling and Optimization

[4] A Modified Binary Particle Swarm Optimization for Knapsack Problems [J].

Bansal, Jagdish Chand ;

Deep, Kusum .

APPLIED MATHEMATICS AND COMPUTATION, 2012, 218 (22) :11042-11061

[5]

Brassard G, 2003, FUNDAMENTALS ALGORIT

[6]

Cormen T.H., 2001, Introduction to Algorithms, VSecond, P370

[7] Differential Evolution: A Survey of the State-of-the-Art [J].

Das, Swagatam ;

Suganthan, Ponnuthurai Nagaratnam .

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2011, 15 (01) :4-31

[8]

Dorigo M, 1999, NEW IDEAS OPTIMIZATI, P11

[9]

Du DZ, 2012, SPRINGER OPTIM APPL, V62, P1, DOI 10.1007/978-1-4614-1701-9

[10]

Eiben A. E., 1991, Parallel Problem Solving from Nature. 1st Workshop, PPSN 1 Proceedings, P4

← 1 2 3 4 →