Abstract
Combinatorial landscape analysis (CLA) is an essential tool for understanding problem difficulty in combinatorial optimization and to get a more fundamental understanding for the behavior of search heuristics. Within CLA, Barrier trees are an efficient tool to visualize essential topographical features of a landscape. They capture the fitness of local optima and how they are separated by fitness barriers from other local optima. The contribution of this study is two-fold: Firstly, the Barrier tree will be extended by a visualization of the size of fitness basins (valleys below saddle points) using expandable node sizes for saddle points and a graded dual-color scheme will be used to distinguish between penalized infeasible and non-penalized feasible solutions of different fitness. Secondly, fitness landscapes of two important NP hard problems with practical relevance will be studied: These are the NK landscapes and Vehicle Routing Problems (with time window constraints). Here the goal is to use EBT to study the influence of problem parameters on the landscape structure: for NK landscapes the number of interacting genes K and for Vehicle Routing Problems the influence of the number of vehicles, the capacity and time window constraints.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Altenberg, L.: Nk-fitness landscapes. In: Bäck, T., et al. (eds.) Handbook of Evolutionary Computation. Oxford University Press (1997)
Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Management Science 6(1), 80–91 (1959)
Flamm, C., Hofacker, I.L., Stadler, P.F., Wolfinger, M.T.: Barrier trees of degenerate landscapes. Zeitschrift für Physikalische Chemie 216, 155 (2002)
Gambardella, L.M., Taillard, É., Agazzi, G.: MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In: New Ideas in Optimization, ch. 5, pp. 63–76. McGraw-Hill (1999)
Kallehauge, B., Larsen, J., Madsen, O.B.G., Solomon, M.M.: Vehicle routing problem with time windows. Column Generation, 67–98 (2005)
Kauffman, S.A.: The origins of order: Self-organization and selection in evolution. Oxford University Press, USA (1993)
Li, R., Emmerich, M.T.M., Eggermont, J., Bovenkamp, E.G.P., Bäck, T., Dijkstra, J., Reiber, J.H.C.: Mixed-integer nk landscapes. In: Runarsson, T.P., Beyer, H.-G., Burke, E.K., Merelo-Guervós, J.J., Whitley, L.D., Yao, X. (eds.) PPSN 2006. LNCS, vol. 4193, pp. 42–51. Springer, Heidelberg (2006)
Ochoa, G., Tomassini, M., Vérel, S., Darabos, C.: A study of nk landscapes’ basins and local optima networks. In: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, pp. 555–562. ACM (2008)
Prusinkiewicz, P., Lindenmayer, A.: The algorithmic beauty of plants. Springer (1996)
Rammal, R., Toulouse, G., Virasoro, M.A.: Ultrametricity for physicists. Reviews of Modern Physics 58(3), 765 (1986)
Stadler, P.: Towards a theory of landscapes. In: Complex Systems and Binary Networks. Lecture Notes in Physics, vol. 461, pp. 78–163. Springer, Heidelberg (1995)
Strahler, A.N.: Quantitative analysis of watershed geomorphology. Transactions of the American Geophysical Union 38(6), 913–920 (1957)
Tomassini, M., Daolio, F.: A complex-networks view of hard combinatorial search spaces. In: Tantar, E., Tantar, A.-A., Bouvry, P., Del Moral, P., Legrand, P., Coello Coello, C.A., Schütze, O. (eds.) EVOLVE- A Bridge between Probability, Set Oriented Numerics and Evolutionary Computation. SCI, vol. 447, pp. 221–244. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
van Stein, B., Emmerich, M., Yang, Z. (2013). Fitness Landscape Analysis of NK Landscapes and Vehicle Routing Problems by Expanded Barrier Trees. In: Emmerich, M., et al. EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation IV. Advances in Intelligent Systems and Computing, vol 227. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-01128-8_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-01128-8_6
Publisher Name: Springer, Heidelberg
Print ISBN: 978-3-319-01127-1
Online ISBN: 978-3-319-01128-8
eBook Packages: EngineeringEngineering (R0)