A Partheno-Genetic Algorithm for Dynamic 0-1 Multidimensional Knapsack Problem

Ünal, Ali Nadi; Kayakutlu, Gülgün

RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 47-66.

Multidimensional Knapsack problem (MKP) is a well-known, NP-hard combinatorial optimization problem. Several metaheuristics or exact algorithms have been proposed to solve stationary MKP. This study aims to solve this difficult problem with dynamic conditions, testing a new evolutionary algorithm. In the present study, the Partheno-genetic algorithm (PGA) is tested by evolving parameters in time. Originality of the study is based on comparing the performances in static and dynamic conditions. First the effectiveness of the PGA is tested on both the stationary, and the dynamic MKP. Then, the improvements with different random restarting schemes are observed. The PGA achievements are shown in statistical and graphical analysis.

Classification : 90C27, 68T20
Mots clés : Combinatorial optimization, dynamic environments, multidimensional knapsack problem, partheno-genetic algorithm

Z. Ahmed and I. Younas, A dynamic programming based ga for 0-1 modified knapsack problem. Published by Foundation of Computer Science. Int. J. Comput. Appl. 16 (2011) 1–6.

J.-C. Bai, H.-Y. Chang and Y. Yi, A partheno-genetic algorithm for multidimensional knapsack problem. In Vol. 5, Proc. of 2005 International Conference on Machine Learning and Cybernetics (2005), 2962–2965.

O. Basir, Abdunnaser Younes, S. Areibi and P. Calamai, Adapting genetic algorithms for combinatorial optimization problems in dynamic environments. In Chap. 11, Advances in Evolutionary Algorithms, edited by Witold Kosinski. I-Tech Education and Publishing, Vienna (2008) 207–230.

A. Baykasoǧlu and F. Burcin Ozsoydan, An improved firefly algorithm for solving dynamic multidimensional knapsack problems. Expert Syst. Appl. 41 (2014) 3712–3725. | DOI

T. Blickle and L. Thiele, A comparison of selection schemes used in genetic algorithms. Technical report, Computer Engineering and Communication Networks Lab (TIK), Swiss Federal Institute of Technology (ETH) (1995).

C. Blum and A. Roli, Metaheuristics in combinatorial optimization. ACM Comput. Surveys 35 (2003) 268–308. | DOI

I. Boussaïd, J. Lepagnot and P. Siarry, A survey on optimization metaheuristics. Inform. Sci. 237 (2013) 82–117. | DOI | MR | Zbl

S. Boussier, M. Vasquez, Y. Vimont, S. Hanafi and P. Michelon, A multi-level search strategy for the 0–1 Multidimensional Knapsack Problem. Discrete Appl. Math. 158 (2010) 97–109. | DOI | MR | Zbl

J. Branke, M. Orbayı andŞ. Uyar, The Role of Representations in Dynamic Knapsack Problems. In Applications of Evolutionary Computing SE - 74, edited by F. Rothlauf, J. Branke, S. Cagnoni, E. Costa, C. Cotta, R. Drechsler, E. Lutton, P. Machado, J.H. Moore, J. Romero, G.D. Smith, G. Squillero and H. Takagi. Vol. 3907 of Lect. Notes Comput. Sci. Springer, Berlin, Heidelberg (2006) 764–775.

P.-C. Chang and S.-H. Chen, The development of a sub-population genetic algorithm II (SPGA II) for multi-objective combinatorial problems. Appl. Soft Comput. 9 (2009) 173–181. | DOI

P.C. Chu and J.E. Beasley, A Genetic Algorithm for the Multidimensional Knapsack Problem. J. Heuristics 4 (1998) 63–86. | DOI | Zbl

A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing. SpringerVerlag (2003). | MR | Zbl

M. Elkihel, V. Boyer and D. El Baz, Solution of multidimensional knapsack problems via cooperation of dynamic programming and branch and bound. Eur. J. Ind. Eng. 4 (2010) 434–449. | DOI

M. Ersen Berberler, A. Guler and U.G. Nurıyev, A genetic algorithm to solve the multidimensional knapsack problem. Math. Comput. Appl. 18 (2013) 486–494. | MR | Zbl

M. Gen and R. Cheng, Genetic Algorithms and Engineering Optimization. John Wiley and Sons Inc., New York, USA (2000).

M. Haluk Akin, New heuristics for the 0-1 multi-dimensional knapsack problems. Ph.D. thesis, University of Central Florida, Ann Arbor (2009).

S. Hanafi and C. Wilbaut, Scatter Search for the 0–1 Multidimensional Knapsack Problem. J. Math. Model. Algorithms 7 (2008) 143–159. | DOI | MR | Zbl

S. Hanafi and C. Wilbaut, Improved convergent heuristics for the 0-1 multidimensional knapsack problem. Ann. Oper. Res. 183 (2011) 125–142. | DOI | MR | Zbl

D. Hu and Z. Yao, Stacker-reclaimer scheduling for raw material yard operation. In Third International Workshop on Advanced Computational Intelligence (IWACI) (2010) 432–436.

M. Jalali Varnamkhasti, Overview of the Algorithms for Solving the Multidimensional Knapsack Problems. Adv. Stud. Biol. 4 (2012) 37–47.

Y. Jin and J. Branke, Evolutionary Optimization in Uncertain Environments – A Survey. IEEE Trans. Evol. Comput. 9 (2005) 303–317. | DOI

M. João Alves and M. Almeida, MOTGA: A multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem. Comput. Oper. Res. 34 (2007) 3458–3470. | DOI | MR | Zbl

F. Kang, J.-J. Li and Q. Xu, Virus coevolution partheno-genetic algorithms for optimal sensor placement. Adv. Eng. Inform. 22 (2008) 362–370. | DOI

H. Kellerer, U. Pferschy and D. Pisinger, Multidimensional Knapsack Problems. In Knapsack Problems SE - 9. Springer, Berlin, Heidelberg (2004) 235–283. | MR | Zbl

S. Khuri, T. Bäck and J. Heitkötter, The zero/one multiple knapsack problem and genetic algorithms. In Proc. of the 1994 ACM Symposium on Applied Computing. SAC ’94. ACM, New York, NY, USA (1994) 188–193.

J. Langeveld and A.P. Engelbrecht, Set-based particle swarm optimization applied to the multidimensional knapsack problem. Swarm Intelligence 6 (2012) 297–342. | DOI

M. Mitchell, An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA, USA (1998). | Zbl

D.C. Montgomery and G.C. Runger, Applied Statistics and Probability for Engineers. John Wiley and Sons (2003). | Zbl

N. Mori and H. Kita, Genetic algorithms for adaptation to dynamic environments-a survey. In the 26th Annual Conference of the IEEE Industrial Electronics Society (2000) 2947–2952.

G.R. Raidl, An improved genetic algorithm for the multiconstrained 0-1 knapsack problem. In Proc. of the 1998 IEEE International Conference on Evolutionary Computation. IEEE Press (1998) 207–211.

C.C. Ribeiro, S.L. Martins and I. Rosseti, Metaheuristics for optimization problems in computer communications. Comput. Commun. 30 (2007) 656–669. | DOI

Masatoshi Sakawa and Kosuke Kato, Genetic algorithms with double strings for 0–1 programming problems. Eur. J. Oper. Res. 144 (2003) 581–597. | DOI | Zbl

Wei Shih, A branch and bound method for the multiconstraint zero-one knapsack problem. J. Oper. Res. Soc. 30 (1979) 37–47. | Zbl

Ren Shuai, Wang Jing and Xuejun Zhang, Research on chaos partheno-genetic algorithm for TSP. In vol. 1, International Conference on Computer Application and System Modeling (ICCASM) (2010) V1–290–V1–293.

A. Simões and E. Costa, Using genetic algorithms to deal with dynamic environments: A comparative study of several approaches based on promoting diversity. In Proc. of the genetic and evolutionary computation conference GECCO’02. Morgan Kaufmann Publishers, New York, NY, USA (2002).

S.N. Sivanandam and S.N. Dipa, Introduction to Genetic Algorithms. Springer-Verlag, Berin (2008). | Zbl

Trung Thanh Nguyen, Shengxiang Yang and Juergen Branke, Evolutionary dynamic optimization: A survey of the state of the art. Swarm Evol. Comput. 6 (2012) 1–24. | DOI

M. Turkensteen, D. Ghosh, B. Goldengorin and G. Sierksma, Iterative patching and the asymmetric traveling salesman problem. The Traveling Salesman Problem. Discrete Optimization 3 (2006) 63–77. | DOI | Zbl

A.N. Ünal, A Genetic Algorithm for the Multiple Knapsack Problem in Dynamic Environment. In Proc. of the World Congress on Engineering and Computer Science 2013. IAENG, San Francicso, USA (2013) 1162.

Ş. Uyar and H. Turgut Uyar, A Critical Look at Dynamic Multi-dimensional Knapsack Problem Generation. In Applications of Evolutionary Computing SE - 86. Vol. 5484 of Lect. Notes Comput. Sci. Edited by M. Giacobini, A. Brabazon, S. Cagnoni, G.A. Caro, A. Ekárt, A. Esparcia-Alcázar, M. Farooq, A. Fink and P. Machado. Springer, Berlin, Heidelberg (2009) 762–767.

M. Vasquez and Yannick Vimont, Improved results on the 0–1 multidimensional knapsack problem. Eur. J. Oper. Res. 165 (2005) 70–81. | DOI | Zbl

J. Wu, A parthenogenetic algorithm for haplotyping a single individual based on WMLF model. In Eighth International Conference on Natural Computation (ICNC) (2012) 622–626.

J. Wu and H. Wang, A parthenogenetic algorithm for the founder sequence reconstruction problem. J. Comput. 8 (2013) 2934–2941.

J. Wu, J. Wang and J. Chen, A parthenogenetic algorithm for single individual {SNP} haplotyping. Eng. Appl. Artif. Intell. 22 (2009) 401–406. | DOI

Shengxiang Yang, Memory-based immigrants for genetic algorithms in dynamic environments. In Proc. of the 2005 conference on Genetic and evolutionary computation – GECCO ’05. ACM Press, New York, USA (2005) 1115.

Q. Yuan and Z. Yang, On the performance of a hybrid genetic algorithm in dynamic environments. Appl. Math. Comput. 219 (2013) 11408–11413. | DOI | Zbl