Multidimensional Knapsack Problem: A Fitness Landscape Analysis



Fitness landscape analysis techniques are used to better understand the influence of genetic representations and associated variation operators when solving a combinatorial optimization problem. Five representations are investigated for the multidimensional knapsack problem. Common mutation operators, such as bit-flip mutation, are employed to generate fitness landscapes. Measures such as fitness distance correlation and autocorrelation are applied to examine the landscapes associated with the tested genetic encodings. Furthermore, additional experiments are made to observe the effects of adding heuristics and local optimization to the representations. Encodings with a strong heuristic bias are more efficient, and the addition of local optimization techniques further enhances their performance.


Fitness landscape analysis, heuristicbias, local improvement methods, representation.


Evolutionary Optimization


IEEE Transactions on Systems, Man and Cybernetics - Part B, Vol. 38, #3, pp. 604-616, June 2008

Cited by

Year 2015 : 4 citations

 A case study of controlling crossover in a selection hyper-heuristic framework using the multidimensional knapsack problem
JH Drake, E Özcan, EK Burke - Evolutionary computation, 2015 - MIT Press

S Gupta, S Arora - International Journal of Computing, 2015 -

 A differential evolution algorithm with variable neighborhood search for multidimensional knapsack problem
MF Tasgetiren, QK Pan, D Kizilay… - … (CEC), 2015 IEEE …, 2015 -

 Análise da aprendizagem de ligações em otimização evolutiva
JP Martins -

Year 2014 : 12 citations

 Multiple objective optimization and implications for single objective optimization
J Gorski - 2014 -

 On the landscape of combinatorial optimization problems
MH Tayarani-N, A Prugel-Bennett - … , IEEE Transactions on, 2014 -

 Fitness distance analysis for parallel genetic algorithm in the test task scheduling problem
H Lu, J Liu, R Niu, Z Zhu - Soft Computing, 2014 - Springer

 Fitness landscapes that depend on time
H Richter - Recent Advances in the Theory and Application of …, 2014 - Springer

 Solving 0–1 knapsack problem using cohort intelligence algorithm
AJ Kulkarni, H Shabir - International Journal of Machine Learning and …, 2014 - Springer

 On the performance of linkage-tree genetic algorithms for the multidimensional knapsack problem
JP Martins, CM Fonseca, ACB Delbem - Neurocomputing, 2014 - Elsevier

 A Case Study of Controlling Crossover in a Selection Hyper-heuristic Framework with MKP
JH Drake, E Ozcan, EK Burke -

 On the effectiveness of genetic algorithms for the multidimensional knapsack problem
JP Martins, H Longo, ACB Delbem - Proceedings of the 2014 …, 2014 -

 Genetic algorithm-based testing scenarios selection for the performance evaluation of crash imminent braking systems for pedestrian safety
A Gholamjafari, L Li, S Chien… - … Systems (ITSC), 2014 …, 2014 -

 Zero duality gap in surrogate constraint optimization: A concise review of models
B Alidaee - European Journal of Operational Research, 2014 - Elsevier

 Crossover control in selection hyper-heuristics: case studies using MKP and HyFlex
JH Drake - 2014 -

 Fitness Landscapes: From Evolutionary Biology to Evolutionary Computation
H Richter - Recent Advances in the Theory and Application of …, 2014 - Springer

Year 2013 : 12 citations

 Solving 0-1 knapsack problems based on amoeboid organism algorithm
X Zhang, S Huang, Y Hu, Y Zhang… - Applied Mathematics …, 2013 - Elsevier

 The travelling thief problem: the first step in the transition from theoretical problems to realistic problems
MR Bonyadi, Z Michalewicz… - … (CEC), 2013 IEEE …, 2013 -

 Geometricity of genetic operators for real-coded representation
Y Yoon, YH Kim - Applied Mathematics and Computation, 2013 - Elsevier

 A comparison of linkage-learning-based genetic algorithms in multidimensional knapsack problems
JP Martins, C Bringel Neto, MK Crocomo… - … (CEC), 2013 IEEE …, 2013 -

 The influence of linkage-learning in the linkage-tree GA when solving multidimensional knapsack problems
JP Martins, ACB Delbem - Proceedings of the 15th annual conference …, 2013 -

 Predicting genetic algorithm performance on the vehicle routing problem using information theoretic landscape measures
M Ventresca, B Ombuki-Berman, A Runka - 2013 - Springer

 A hybrid of rough sets and genetic algorithms for solving the 0-1 multidimensional knapsack problem
H Yang, M Wang, C Yang - International Journal of Innovative Computing, …, 2013 -

 Dynamic fitness landscape analysis
H Richter - Evolutionary Computation for Dynamic Optimization …, 2013 - Springer

 Analysis of the fitness landscape for the class of combinatorial optimisation problems
MH Tayarani-Najaran - 2013 -

 A Study of Representations for Resource Constrained Project Scheduling Problems Using Fitness Distance Correlation
B Cai, J Liu - Intelligent Data Engineering and Automated Learning– …, 2013 - Springer

 Fitness Landscape-Based Characterisation of Nature-Inspired Algorithms
M Crossley, A Nisbet, M Amos - Adaptive and Natural Computing …, 2013 - Springer

 Clustering of search trajectory and its application to parameter tuning
HC Lau, D Lo - Journal of the Operational Research …, 2013 -

Year 2012 : 6 citations

 Kate Smith-Miles, Leo Lopes, Measuring instance difficulty for combinatorial optimization problems, Computers & Operations Research, Volume 39, Issue 5, May 2012, Pages 875-889, ISSN 0305-0548, 10.1016/j.cor.2011.07.006.

 J Gorski, L Paquete, F Pedrosa. Greedy algorithms for a class of knapsack problems with binary weights. Computers & Operations Research, 2012 - Elsevier.

 J Liu, HA Abbass, DG Green, W Zhong. Motif difficulty (MD): a predictive measure of problem difficulty for evolutionary algorithms using network motifs. Evolutionary Computation, 2012 - MIT Press

 Z Ren, H Jiang, J Xuan, Z Luo. An Accelerated-Limit-Crossing-Based Multilevel Algorithm for the p-Median Problem. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2012.

 E Pitzer, M Affenzeller. A comprehensive survey on fitness landscape analysis. Recent Advances in Intelligent Engineering Systems, Studies in Computational Intelligence, 2012 - Springer.

 M Crossley, A Nisbet, M Amos. Fitness Landscape-Based Characterisation of Nature-Inspired Algorithms. arXiv:1210.3210, 2012.

Year 2011 : 6 citations

 H. Bouziri, K. Mellouli, E. Talbi (2011). The K-coloring fitness landscape. Journal of Combinatorial Optimization, 21, 3, 306-329.

 Jochen Gorski, Luís Paquete, Fábio Pedrosa, Greedy algorithms for a class of knapsack problems with binary weights, Computers & Operations Research, Volume 39, Issue 3, March 2012, Pages 498-511, ISSN 0305-0548, 10.1016/j.cor.2011.02.010.

 Moritz, R.; Ulrich, T.; Thiele, J.L.; Buerklen, S.; , "Mutation operator characterization: Exhaustiveness, locality, and bias," Evolutionary Computation (CEC), 2011 IEEE Congress on , vol., no., pp.1396-1403, 5-8 June 2011

 Jing Liu, Hussein A. Abbass, David G. Green, Weicai Zhong, "Motif Difficulty (MD): A Predictive Measure of Problem Difficulty for Evolutionary Algorithms Using Network Motif", Evolutionary Computation Journal, Posted Online August 4, 2011.(doi:10.1162/EVCO_a_00045)

 Pitzer, Erik, and Affenzeller, Michael, "A Comprehensive Survey on Fitness Landscape Analysis", Recent Advances in Intelligent Engineering Systems, Studies in Computational Intelligence, 2012, Springer Berlin / Heidelberg, Isbn: 978-3-642-23228-2, pp. 161-191, Volume: 378, Doi: 10.1007/978-3-642-23229-9_8

 Tayarani N., M. H. et. al, "Improvement of the Performance of QEA Using the History of Search Process and Backbone Structure of Landscape", Innovative Computing Technology, Communications in Computer and Information Science, 2011, Springer Berlin Heidelberg, Isbn: 978-3-642-27337-7, pp. 389-400, Volume: 241, Doi: 10.1007/978-3-642-27337-7_37

Year 2010 : 3 citations

 Jeff Riley and Vic Ciesielski (2010). Fitness Landscape Analysis for Evolutionary Non-Photorealistic Rendering. WCCI 2010 IEEE World Congress on Computational Intelligence - IEEE CEC, pp. 2537-2545, July, 18-23, 2010 - CCIB, Barcelona, Spain, IEEE, 2010.

 M Caserta, S Voß. Metaheuristics: intelligent problem solving. Matheuristics, 2010 - Springer.

 J Gorski . Multiple objective optimization and implications for single objective optimization. PhD. thesis, 2010.

Year 2009 : 5 citations

 Uludag, G., and Uyar, A.S., "Fitness landscape analysis of differential evolution algorithms", Fifth International Conference on Soft Computing, Computing with Words and Perceptions in System Analysis, Decision and Control, 2-4 Sept. 2009

 Minh Nghia Le, Yew-Soon Ong, Yaochu Jin, and Bernhard Sendhoff, extbf{Lamarckian memetic algorithms: local optimum and connectivity structure analysis}, Memetic Computing Journal, Vol. 1, No. 3, pp. 175-190, 2009

 M. Caserta and S. VoÃ?, extbf{Metaheuristics: Intelligent problem solving}, Chapter in:
V. Maniezzo, T. Stutzle and S. Vo� (eds.) Matheuristics: Hybridizing Metaheuristics and Mathematical Programming, Book Series "Annals of Information Systems,� 10, Springer, Berlin, 2009.

 Pereira, Paulo Alexandre da Silva, exbf{An Optimization-Based Decision Support System for Planning
Self-Promotion of a Television Station}, PhD. Thesis, School of Sciences, University of Minho, May, 2009.

 H. Bouziri, K. Mellouli, El-G. Talbi (2009). The k-coloring Fitness Landscape. Journal of Combinatorial Optimization.