Viz: a visual analysis suite for explaining local search behavior

ABSTRACT

NP-hard combinatorial optimization problems are common in real life. Due to their intractability, local search algorithms are often used to solve such problems. Since these algorithms are heuristic-based, it is hard to understand how to improve or tune them. We propose an interactive visualization tool, VIZ, meant for understanding the behavior of local search. VIZ uses animation of abstract search trajectories with other visualizations which are also animated in a VCR-like fashion to graphically playback the algorithm behavior. It combines generic visualizations applicable on arbitrary algorithms with algorithm and problem specific visualizations. We use a variety of techniques such as alpha blending to reduce visual clutter and to smooth animation, highlights and shading, automatically generated index points for playback, and visual comparison of two algorithms. The use of multiple viewpoints can be an effective way of understanding search behavior and highlight algorithm behavior which might otherwise be hidden.

REFERENCES

• 1: B. Adenso-Diaz and M. Laguna. Fine-tuning of Algorithms Using Fractional Experimental Designs and Local Search. Operations Research, 54(1):99--114, 2006.
• 2: R. Battiti and G. Tecchiolli. The Reactive Tabu Search. ORSA J. on Computing, 6(2):126--140, 1994.
• 3: M. Birattari. The Problem of Tuning Metaheuristics as seen from a machine learning perspective. PhD thesis, University Libre de Bruxelles, 2004.
• 4: M. R. Endsley. Theoretical Underpinnings of Situation Awareness: A Critical Review. Endsley and Garland (eds). Situation Awareness Analysis and Measurement. Lawrence Erlbaum Associates, Mahwah, NJ., 2000.
• 5: S. Halim and H. C. Lau. Tuning Tabu Search Strategies via Visual Diagnosis. To appear in MIC2005 Post-Conf. Volume. Kluwer Academic Press, 2007.
• 6: S. Halim, R. Yap, and H. C. Lau. Visualization for Analyzing Trajectory-Based Metaheuristic Search Algorithms. In Poster Paper of European Conf. on Artificial Intelligence (ECAI06), 2006.
• 7: Holger Hoos , Thomas Sttzle, Stochastic Local Search: Foundations & Applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 8: Dean F. Jerding , John T. Stasko , Thomas Ball, Visualizing interactions in program executions, Proceedings of the 19th international conference on Software engineering, p.360-370, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253356]
• 9: Marcin Kadluczka , Peter C. Nelson , Thomas M. Tirpak, N-to-2-Space Mapping for Visualization of Search Algorithm Performance, Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'04), p.508-513, November 15-17, 2004 [doi>10.1109/ICTAI.2004.92]
• 10: T. Kamada , S. Kawai, An algorithm for drawing general undirected graphs, Information Processing Letters, v.31 n.1, p.7-15, April 1989 [doi>10.1016/0020-0190(89)90102-6]
• 11: Gunnar W. Klau , Neal Lesh , Joe Marks , Michael Mitzenmacher, Human-guided tabu search, Eighteenth national conference on Artificial intelligence, p.41-47, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 12: Andrew J. Ko , Brad A. Myers, Designing the whyline: a debugging interface for asking questions about program behavior, Proceedings of the SIGCHI conference on Human factors in computing systems, p.151-158, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985712]
• 13: H. C. Lau, W. C. Wan, and S. Halim. Tuning Tabu Search Strategies via Visual Diagnosis. In Metaheuristics Intl. Conf., 2005.
• 14: H. C. Lau, W. C. Wan, S. Halim, and K. Toh. A Software Framework for Fast Proto-typing of Meta-heuristics Hybridization. To Appear in ITOR, 2006.
• 15: D. Michie, J. G. Fleming, and J. V. Oldfield. A Comparison of Heuristic, Interactive, and Unaided Methods of Solving a Shortest-route Problem, pages 245--256. Michie, D. (eds). Machine Intelligence series 3. Edinburgh University Press, 1968.
• 16: B. A. Myers, Visual programming, programming by example, and program visualization: a taxonomy, Proceedings of the SIGCHI conference on Human factors in computing systems, p.59-66, April 13-17, 1986, Boston, Massachusetts, United States
• 17: M. J. Oudshoorn, H. Widjaja, and S. K. Ellershaw. Aspects and Taxonomy of Program Visualisation. In P. D. Eades and K. Zhang, editors, Software Visualisation, volume 7, pages 3--26. World Scientific, 1996.
• 18: G. Reinelt. TSPLIB - A Traveling Salesman Problem Library. ORSA J. on Computing, 3:376--384, 1991.
• 19: Pascal Van Hentenryck , Laurent Michel, Constraint-Based Local Search, The MIT Press, 2005
• 20: J. Watson. On Metaheuristics "Failure Modes". In Metaheuristics Intl. Conf., 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Graphical user interfaces (GUI)

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Screen design (e.g., text, graphics, color)

General Terms:
Design, Human Factors

Keywords:
local search, program visualization