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.
Keywords
Fitness landscape analysis, heuristicbias, local improvement methods, representation.
Subject
Evolutionary Optimization
Journal
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
BOOSTING SIMULATED ANNEALING WITH FITNESS LANDSCAPE PARAMETERS FOR BETTER OPTIMALITY
S Gupta, S Arora - International Journal of Computing, 2015 - computingonline.net
A differential evolution algorithm with variable neighborhood search for multidimensional knapsack problem
MF Tasgetiren, QK Pan, D Kizilay… - … (CEC), 2015 IEEE …, 2015 - ieeexplore.ieee.org
Análise da aprendizagem de ligações em otimização evolutiva
JP Martins - teses.usp.br
Year 2014 : 12 citations
Multiple objective optimization and implications for single objective optimization
J Gorski - 2014 - elpub.bib.uni-wuppertal.de
On the landscape of combinatorial optimization problems
MH Tayarani-N, A Prugel-Bennett - … , IEEE Transactions on, 2014 - ieeexplore.ieee.org
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 - researchgate.net
On the effectiveness of genetic algorithms for the multidimensional knapsack problem
JP Martins, H Longo, ACB Delbem - Proceedings of the 2014 …, 2014 - dl.acm.org
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 - ieeexplore.ieee.org
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 - eprints.nottingham.ac.uk
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 - ieeexplore.ieee.org
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 - ieeexplore.ieee.org
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 - dl.acm.org
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 - ijicic.org
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 - eprints.soton.ac.uk
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 - palgrave-journals.com
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.
