Combinatorial optimization problems and corresponding (meta-)heuristics have received much attention in the literature. Especially, the structural or topological analysis of search landscapes is important for evaluating the applicability and the performance of search operators for a given problem. However, this analysis is often tedious and usually the focus is on one specific problem and only a few operators. We present a visual analysis method that can be applied to a wide variety of problems and search operators. The method is based on steepest descent walks and shortest distances in the search landscape. The visualization shows the search landscape as seen by the search algorithm. It supports the topological analysis as well as the comparison of search landscapes. We showcase the method by applying it to two different search operators on the TSP, the QAP, and the SMTTP. Our results show how differences between search operators manifest in the search landscapes and how conclusions about the suitability of the search operator for different optimizations can be drawn.
%0 Conference Paper
%1 10.1145/2739480.2754733
%A Volke, Sebastian
%A Zeckzer, Dirk
%A Scheuermann, Gerik
%A Middendorf, Martin
%B Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation
%C New York, NY, USA
%D 2015
%I Association for Computing Machinery
%K combinatorial empirical fitness landscapes, local optimization, search study,
%P 497–504
%R 10.1145/2739480.2754733
%T A Visual Method for Analysis and Comparison of Search Landscapes
%U https://doi.org/10.1145/2739480.2754733
%X Combinatorial optimization problems and corresponding (meta-)heuristics have received much attention in the literature. Especially, the structural or topological analysis of search landscapes is important for evaluating the applicability and the performance of search operators for a given problem. However, this analysis is often tedious and usually the focus is on one specific problem and only a few operators. We present a visual analysis method that can be applied to a wide variety of problems and search operators. The method is based on steepest descent walks and shortest distances in the search landscape. The visualization shows the search landscape as seen by the search algorithm. It supports the topological analysis as well as the comparison of search landscapes. We showcase the method by applying it to two different search operators on the TSP, the QAP, and the SMTTP. Our results show how differences between search operators manifest in the search landscapes and how conclusions about the suitability of the search operator for different optimizations can be drawn.
%@ 9781450334723
@inproceedings{10.1145/2739480.2754733,
abstract = {Combinatorial optimization problems and corresponding (meta-)heuristics have received much attention in the literature. Especially, the structural or topological analysis of search landscapes is important for evaluating the applicability and the performance of search operators for a given problem. However, this analysis is often tedious and usually the focus is on one specific problem and only a few operators. We present a visual analysis method that can be applied to a wide variety of problems and search operators. The method is based on steepest descent walks and shortest distances in the search landscape. The visualization shows the search landscape as seen by the search algorithm. It supports the topological analysis as well as the comparison of search landscapes. We showcase the method by applying it to two different search operators on the TSP, the QAP, and the SMTTP. Our results show how differences between search operators manifest in the search landscapes and how conclusions about the suitability of the search operator for different optimizations can be drawn.},
added-at = {2024-10-02T10:38:17.000+0200},
address = {New York, NY, USA},
author = {Volke, Sebastian and Zeckzer, Dirk and Scheuermann, Gerik and Middendorf, Martin},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/2e0ec413b2573c5ae9306b1f8c1bfb53c/scadsfct},
booktitle = {Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation},
doi = {10.1145/2739480.2754733},
interhash = {87b6d23e5f8b78dc2e73261118487f19},
intrahash = {e0ec413b2573c5ae9306b1f8c1bfb53c},
isbn = {9781450334723},
keywords = {combinatorial empirical fitness landscapes, local optimization, search study,},
location = {Madrid, Spain},
numpages = {8},
pages = {497–504},
publisher = {Association for Computing Machinery},
series = {GECCO '15},
timestamp = {2024-10-02T10:38:17.000+0200},
title = {A Visual Method for Analysis and Comparison of Search Landscapes},
url = {https://doi.org/10.1145/2739480.2754733},
year = 2015
}