Algorithms for randomized time-varying knapsack problems

详细信息    查看全文

• 作者：Yichao He ; Xinlu Zhang ; Wenbin Li ; Xiang Li…
• 关键词：Knapsack problem ; Exact algorithm ; Approximations ; Heuristics
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：31
• 期：1
• 页码：95-117
• 全文大小：1,667 KB
• 参考文献：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–11061MathSciNet CrossRef MATH
  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 YorkCrossRef MATH
  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–120CrossRef MATH
  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–224MathSciNet CrossRef
  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–359MathSciNet CrossRef MATH
  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–814CrossRef MATH
  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
  
• 作者单位：Yichao He (1)
  Xinlu Zhang (2)
  Wenbin Li (3)
  Xiang Li (4)
  Weili Wu (5)
  Suogang Gao (2)
  
  1. College of Information Engineering, Shijiazhuang University of Economics, Shijiazhuang , 050031, China
  2. College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang , 050024, China
  3. Laboratory of Network and Information Security, Shijiazhuang University of Economics, Shijiazhuang , 050031, China
  4. Department of Industrial and System Engineering, University of Florida, Gainesville, FL , 32611, USA
  5. Department of Computer Science, University of Texas at Dallas, Richardson, TX , 75080, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

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.