Top

Journal of Combinatorial Optimization

Published in:

01-01-2016

Algorithms for randomized time-varying knapsack problems

Authors: Yichao He, Xinlu Zhang, Wenbin Li, Xiang Li, Weili Wu, Suogang Gao

Published in: Journal of Combinatorial Optimization | Issue 1/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we first give the definition of randomized time-varying knapsack problems (\(\textit{RTVKP}\)) and its mathematic model, and analyze the character about the various forms of \(\textit{RTVKP}\). Next, we propose three algorithms for \(\textit{RTVKP}\): (1) an exact algorithm with pseudo-polynomial time based on dynamic programming; (2) a 2-approximation algorithm for \(\textit{RTVKP}\) 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 \(\textit{RTVKP}\), the simulation computation results coincide with the theory analysis.

previous article Minimax regret vertex 2-sink location problem in dynamic path networks

next article Information exchange with collision detection on multiple channels

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Ashlock D (2006) Evolutionary computation for modeling and optimization. Springer, BerlinMATH

Bansal JC, Deep K (2012) A modified binary particle swarm optimization for knapsack problems. Appl Math Comput 218(22):11042–11061MathSciNetCrossRefMATH

Brassard G, Bratley P (2003) Fundamentals of algorithmics. Prentice Hall, Inc., London

Cormen TH, Leiserson CE, Rivest RL et al (2001) Introduction to algorithms, 2nd edn. MIT Press, Cambridge, pp 370–399MATH

Das S, Suganthan PN (2011) Differential evolution: a survey of the state-of-the-art. IEEE Trans Evol Comput 15(1):4–31CrossRef

Dorigo M, Caro G (1999) The ant colony optimization meta-heuristic. In: Corne D, Dorigo M, Glover F (eds) New ideas in optimization. McGraw Hill, London, pp 11–32

Du D-Z, Ko K-I (2000) Theory of computational complexity. Wiley-Interscience, New YorkCrossRefMATH

Du D-Z, Ko K-I, Hu X (2012) Design and analysis of approximation algorithms. Springer Science Business Media LLC, Berlin

Eiben AE, Arts EH, Van Hee KM (1991) Global convergence of genetic algorithm: an infinite Markov chain analysis. In: Schwefel HP, Manner R (eds) Parallel solving from nature (PPSN1). Springer, Berlin, pp 4–12

Elsayed SM, Sarker RA, Essam DL (2014) A new genetic algorithm for solving optimization problems. Eng Appl Artif Intell 27:57–69CrossRef

Ezziane Z (2002) Solving the 0/1 knapsack problem using an adaptive genetic algorithm. Artif Intell Eng Des Anal Manuf 16(1):23–30CrossRef

Eusuff MM, Lansey KE (2003) Optimization of water distribution network design using the shuffled frog-leaping algorithm. J Water Resour Plan Manag 129(3):210–225CrossRef

Geem ZW, Kim JH, Loganathan GV (2001) A new heuristic optimization algorithm: harmony search. Simulation 76(2):60–68CrossRef

Goldberg DE, Smith RE (1987) Nonstationary function optimization using genetic algorithms with dominance and diploidy. In: International conference on genetic algorithms. L. Erlbaum Associates Inc, Hillsdale, pp 59–68

Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, BostonMATH

Gottlieb J, Marchiori E, Rossi C (2002) Evolutionary algorithms for the satisfiability problem. Evol Comput 10(1):35–50CrossRef

Hembecker F, Lopes HS (2007) Godoy Jr W (2007) Particle swarm optimization for the multidimensional knapsack problem. In: Adaptive and natural computing algorithms, lecture notes in computer science vol 4431, pp 358–365

Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor

Jun S, Jian L (2009) Solving 0-1 knapsack Problems via a hybrid differential evolution. In: Third international symposium on intelligent information technology application vol 3. IITA, pp 134–137

Kang L, Zhou A, Bob M et al. (2004) Benchmarking algorithms for dynamic travelling salesman problems. In: The congress on evolutionary computation. Portland, Oregon

Kennedy J, Eberhart RC (1995) Particle swarm optimization. In: Proceedings of the IEEE international conference on neural networks (Perth), vol IV. IEEE Service Center, Piscataway, NJ, pp 1942–1948

Krishnakumar K (1989) Micro-genetic algorithms for stationary and non-stationary function optimization. In: SPIE intelligent control and adaptive systems, pp 289–296

Kumar R, Banerjeec N (2006) Analysis of a multiobjective evolutionary algorithm on the 0-1 knapsack problem. Theor Comput Sci 358(1):104–120CrossRefMATH

Lee J, Shragowitz E, Sahni S (1988) A hypercube algorithm for the 0/1 knapsack problem. J Parallel Distrib Comput 5(4):438–456CrossRef

Li C, Yang M, Kang L (2006) A new approach to solving dynamic traveling salesman problems. In: Simulated evolution and learning, lecture notes in computer science vol 4247, pp 236–243

Li X, Yao X (2012) Cooperatively coevolving particle swarms for large scale optimization. IEEE Trans Evol Comput 16(2):210–224MathSciNetCrossRef

Liao Y-F, Yau D-H, Chen C-L (2012) Evolutionary algorithm to traveling salesman problems. Comput Math Appl 64(5):788–797CrossRef

Man KF, Tang KS, Kwong S (1996) Genetic algorithms: concepts and applications. IEEE Trans Ind Electron 43(5):519–534CrossRef

Mori N, Kita H, Nishikawa Y (1996) Adaptation to a changing environment by means of the thermodynamical genetic algorithm vol 1141 of LNCS. Springer, Berlin, pp 513–522

Rudolph G (1994) Convergence analysis of canonical genetic algorithms. IEEE Trans Neural Netw 5(1):86–101CrossRef

Ryan C (1997) Diploidy without dominance. In: Alander JT (ed) Third nordic workshop on genetic algorithms, pp 63–70

Simon D (2013) Evolutionary optimization algorithms. Wiley, New YorkMATH

Storn R, Price K (1997) Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim 11:341–359MathSciNetCrossRefMATH

Tsai H-K, Yang J-M, Tsai Y-F et al (2004) An evolutionary algorithm for large traveling salesman problems. IEEE Trans Syst Man Cybern Part B 34(4):1718–1729CrossRef

Uyar AS, Harmanci AE (2005) A new population based adaptive domination change mechanism for diploid genetic algorithms in dynamic environments. Soft Comput 9(11):803–814CrossRefMATH

Yao X, Liu Y, Lin G (1999) Evolutionary programming made faster. IEEE Trans Evol Comput 3(2):82–102CrossRef

Yuen SY, Chow CK (2009) A genetic algorithm that adaptively mutates and never revisits. IEEE Trans Evol Comput 13(2):454–472CrossRef

Title: Algorithms for randomized time-varying knapsack problems
Authors: Yichao He
Xinlu Zhang
Wenbin Li
Xiang Li
Weili Wu
Suogang Gao
Publication date: 01-01-2016
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2016
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-014-9717-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2016

Cacti with the smallest, second smallest, and third smallest Gutman index

Approximation for maximizing monotone non-decreasing set functions with a greedy method

On the complexity of the minimum outer-connected dominating set problem in graphs

L(2,1)-labelings of the edge-multiplicity-paths-replacement of a graph

The blocking job shop with rail-bound transportation

Information exchange with collision detection on multiple channels

Premium Partner