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 条

[21] Solving 0-1 knapsack Problems via a hybrid Differential Evolution [J].

Jun, Shu ;

Jian, Li .

2009 THIRD INTERNATIONAL SYMPOSIUM ON INTELLIGENT INFORMATION TECHNOLOGY APPLICATION, VOL 3, PROCEEDINGS, 2009, :134-+

[22]

Kang L, 2004, C EV COMP PORTL OR

[23]

Kennedy J, 1995, 1995 IEEE INTERNATIONAL CONFERENCE ON NEURAL NETWORKS PROCEEDINGS, VOLS 1-6, P1942, DOI 10.1109/icnn.1995.488968

[24]

KRISHNAKUMAR K, 1990, P SOC PHOTO-OPT INS, V1196, P289, DOI 10.1117/12.969927

[25] Analysis of a Multiobjective Evolutionary Algorithm on the 0-1 knapsack problem [J].

Kumar, Rajeev ;

Banerjee, Nilanjan .

THEORETICAL COMPUTER SCIENCE, 2006, 358 (01) :104-120

[26]

Li CH, 2006, LECT NOTES COMPUT SC, V4247, P236

[27] Cooperatively Coevolving Particle Swarms for Large Scale Optimization [J].

Li, Xiaodong ;

Yao, Xin .

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2012, 16 (02) :210-224

[28] Evolutionary algorithm to traveling salesman problems [J].

Liao, Yen-Far ;

Yau, Dun-Han ;

Chen, Chieh-Li .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2012, 64 (05) :788-797

[29] Genetic algorithms: Concepts and applications [J].

Man, KF ;

Tang, KS ;

Kwong, S .

IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS, 1996, 43 (05) :519-534

[30]

Mori N., 1996, Parallel Problem Solving from Nature - PPSN IV. International Conference on Evolutionary Computation - The 4th International Conference on Parallel Problem Solving from Nature. Proceedings, P513, DOI 10.1007/3-540-61723-X_1015

← 1 2 3 4 →