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.
Mots-clés : Combinatorial optimization, dynamic environments, multidimensional knapsack problem, partheno-genetic algorithm
@article{RO_2016__50_1_47_0, author = {\"Unal, Ali Nadi and Kayakutlu, G\"ulg\"un}, title = {A {Partheno-Genetic} {Algorithm} for {Dynamic} 0-1 {Multidimensional} {Knapsack} {Problem}}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {47--66}, publisher = {EDP-Sciences}, volume = {50}, number = {1}, year = {2016}, doi = {10.1051/ro/2015011}, mrnumber = {3460662}, zbl = {1333.90112}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro/2015011/} }
TY - JOUR AU - Ünal, Ali Nadi AU - Kayakutlu, Gülgün TI - A Partheno-Genetic Algorithm for Dynamic 0-1 Multidimensional Knapsack Problem JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2016 SP - 47 EP - 66 VL - 50 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2015011/ DO - 10.1051/ro/2015011 LA - en ID - RO_2016__50_1_47_0 ER -
%0 Journal Article %A Ünal, Ali Nadi %A Kayakutlu, Gülgün %T A Partheno-Genetic Algorithm for Dynamic 0-1 Multidimensional Knapsack Problem %J RAIRO - Operations Research - Recherche Opérationnelle %D 2016 %P 47-66 %V 50 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2015011/ %R 10.1051/ro/2015011 %G en %F RO_2016__50_1_47_0
Ünal, Ali Nadi; Kayakutlu, Gülgün. A Partheno-Genetic Algorithm for Dynamic 0-1 Multidimensional Knapsack Problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 47-66. doi : 10.1051/ro/2015011. http://www.numdam.org/articles/10.1051/ro/2015011/
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.
and ,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.
An improved firefly algorithm for solving dynamic multidimensional knapsack problems. Expert Syst. Appl. 41 (2014) 3712–3725. | DOI
and ,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).
Metaheuristics in combinatorial optimization. ACM Comput. Surveys 35 (2003) 268–308. | DOI
and ,A survey on optimization metaheuristics. Inform. Sci. 237 (2013) 82–117. | DOI | MR | Zbl
, and ,A multi-level search strategy for the 0–1 Multidimensional Knapsack Problem. Discrete Appl. Math. 158 (2010) 97–109. | DOI | MR | Zbl
, , , and ,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.
The development of a sub-population genetic algorithm II (SPGA II) for multi-objective combinatorial problems. Appl. Soft Comput. 9 (2009) 173–181. | DOI
and ,A Genetic Algorithm for the Multidimensional Knapsack Problem. J. Heuristics 4 (1998) 63–86. | DOI | Zbl
and ,A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing. SpringerVerlag (2003). | MR | Zbl
Solution of multidimensional knapsack problems via cooperation of dynamic programming and branch and bound. Eur. J. Ind. Eng. 4 (2010) 434–449. | DOI
, and ,M. Ersen Berberler, A genetic algorithm to solve the multidimensional knapsack problem. Math. Comput. Appl. 18 (2013) 486–494. | MR | Zbl
and ,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).
Scatter Search for the 0–1 Multidimensional Knapsack Problem. J. Math. Model. Algorithms 7 (2008) 143–159. | DOI | MR | Zbl
and ,Improved convergent heuristics for the 0-1 multidimensional knapsack problem. Ann. Oper. Res. 183 (2011) 125–142. | DOI | MR | Zbl
and ,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.
Overview of the Algorithms for Solving the Multidimensional Knapsack Problems. Adv. Stud. Biol. 4 (2012) 37–47.
,Evolutionary Optimization in Uncertain Environments – A Survey. IEEE Trans. Evol. Comput. 9 (2005) 303–317. | DOI
and ,MOTGA: A multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem. Comput. Oper. Res. 34 (2007) 3458–3470. | DOI | MR | Zbl
and ,Virus coevolution partheno-genetic algorithms for optimal sensor placement. Adv. Eng. Inform. 22 (2008) 362–370. | DOI
, and ,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.
Set-based particle swarm optimization applied to the multidimensional knapsack problem. Swarm Intelligence 6 (2012) 297–342. | DOI
and ,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.
Metaheuristics for optimization problems in computer communications. Comput. Commun. 30 (2007) 656–669. | DOI
, and ,Genetic algorithms with double strings for 0–1 programming problems. Eur. J. Oper. Res. 144 (2003) 581–597. | DOI | Zbl
and ,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
Evolutionary dynamic optimization: A survey of the state of the art. Swarm Evol. Comput. 6 (2012) 1–24. | DOI
, and ,Iterative patching and the asymmetric traveling salesman problem. The Traveling Salesman Problem. Discrete Optimization 3 (2006) 63–77. | DOI | Zbl
, , and ,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.
Improved results on the 0–1 multidimensional knapsack problem. Eur. J. Oper. Res. 165 (2005) 70–81. | DOI | Zbl
and ,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.
A parthenogenetic algorithm for the founder sequence reconstruction problem. J. Comput. 8 (2013) 2934–2941.
and ,A parthenogenetic algorithm for single individual {SNP} haplotyping. Eng. Appl. Artif. Intell. 22 (2009) 401–406. | DOI
, and ,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.
On the performance of a hybrid genetic algorithm in dynamic environments. Appl. Math. Comput. 219 (2013) 11408–11413. | DOI | Zbl
and ,Cité par Sources :