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 条

[11] A new genetic algorithm for solving optimization problems [J].

Elsayed, Saber M. ;

Sarker, Ruhul A. ;

Essam, Daryl L. .

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2014, 27 :57-69

[12] Optimization of water distribution network design using the Shuffled Frog Leaping Algorithm [J].

Eusuff, MM ;

Lansey, KE .

JOURNAL OF WATER RESOURCES PLANNING AND MANAGEMENT, 2003, 129 (03) :210-225

[13] Solving the 0/1 knapsack problem using an adaptive genetic algorithm [J].

Ezziane, Z .

AI EDAM-ARTIFICIAL INTELLIGENCE FOR ENGINEERING DESIGN ANALYSIS AND MANUFACTURING, 2002, 16 (01) :23-30

[14] A new heuristic optimization algorithm: Harmony search [J].

Geem, ZW ;

Kim, JH ;

Loganathan, GV .

SIMULATION, 2001, 76 (02) :60-68

[15]

Goldberg D. E., 1987, Genetic Algorithms and their Applications: Proceedings of the Second International Conference on Genetic Algorithms, P59

[16]

Goldberg D.E., 1989, Optimization, and machine learning

[17] Evolutionary algorithms for the satisfiability problem [J].

Gottlieb, J ;

Marchiori, E ;

Rossi, C .

EVOLUTIONARY COMPUTATION, 2002, 10 (01) :35-50

[18]

Hembecker F, 2007, LECT NOTES COMPUT SC, V4431, P358

[19]

Holland JH., 1992, ADAPTATION NATURAL A, DOI [10.7551/mitpress/1090.001.0001, DOI 10.7551/MITPRESS/1090.001.0001]

[20] A HYPERCUBE ALGORITHM FOR THE 0/1 KNAPSACK-PROBLEM [J].

JONG, L ;

SHRAGOWITZ, E ;

SAHNI, S .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1988, 5 (04) :438-456

← 1 2 3 4 →