Visualization for Analyzing TrajectoryBased Metaheuristic Search Algorithms.pdf

Visualization for Analyzing Trajectory-Based Metaheuristic Search Algorithms Steven Halim, Roland H.C. Yap and Hoong Chuin Lau SICS Technical Report T2006:11 ISSN 1100-3154 ISRN:SICS-T–2006/11-SE Email: {stevenha,ryap}@.sg, hclau@.sg Keywords: visualisation, local search, metaheuristics, constraints May 12, 2006 Abstract Metaheuristic search algorithms due to their heuristic nature usually need tuning of parameters, components and/or strategies to achieve ac- ceptable performance on a particular problem. While there has been much work on tools and techniques to address this Tuning Problem, there has been relatively little work which takes advantage of putting humans in the metaheuristic analysis/evaluation loop. This paper proposes the use of a search trajectory visualization tool, Viz, which is meant to make it eas- ier for humans (e.g. the algorithm designer/programmer) to understand, evaluate and design metaheuristics for search. In particular, our visu- alization exploits the human’s capabilities for finding patterns in search trajectory by using a combination of spatial visualizations. We use the Travelling Salesman Problem to illustrate how Viz can be used to visualize the behavior of two local search algorithms with different heuristics. Visualization for Analyzing Trajectory-Based Metaheuristic Search Algorithms Steven HALIM and Roland H.C. YAP1 and Hoong Chuin LAU2 1 INTRODUCTION 2. Are there signs of cycling behavior?