Optimizing hierarchical menus by genetic algorithm and simulated annealing

ABSTRACT

Hierarchical menus are now ubiquitous. The performance of the menu depends on many factors: structure, layout, colors and so on. There has been extensive research on novel menus, but there has been little work on improving performance by optimizing the menu's structure. This paper proposes algorithms based on the genetic algorithm (GA) and the simulated annealing (SA) for optimizing the performance of menus. The algorithms aim to minimize the average selection time of menu items by considering the user's pointer movement and search/decision time. We will show the experimental results on a static hierarchical menu of a cellular phone as an example where a small screen and limited input device are assumed. We will also show performance comparison of the GA-based algorithm and the SA-based one by using wide varieties of usage patterns.

REFERENCES

• 1: Robert St. Amant , Thomas E. Horton , Frank E. Ritter, Model-based evaluation of cell phone menu interaction, Proceedings of the SIGCHI conference on Human factors in computing systems, p.343-350, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985736]
• 2: David Ahlström, Modeling and improving selection in cascading pull-down menus using Fitts' law, the steering law and force fields, Proceedings of the SIGCHI conference on Human factors in computing systems, April 02-07, 2005, Portland, Oregon, USA [doi>10.1145/1054972.1054982]
• 3: J. Beck, S.H. Han, and J. Park. Presenting a submenu window for menu search on a cellular phone. Int. J. of Human-Computer Interaction, 20(3):233--245, 2006.
• 4: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 5: Andy Cockburn , Carl Gutwin , Saul Greenberg, A predictive model of menu performance, Proceedings of the SIGCHI conference on Human factors in computing systems, April 28-May 03, 2007, San Jose, California, USA [doi>10.1145/1240624.1240723]
• 6: G. Francis. Designing multifunction displays: an optimization approach. Int. J. of Cognitive Ergonomics, 4(2):107--124, 2000.
• 7: Leah Findlater , Joanna McGrenere, A comparison of static, adaptive, and adaptable menus, Proceedings of the SIGCHI conference on Human factors in computing systems, p.89-96, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985704]
• 8: KDDI: Manual for CASIO W43CA, http://www.au.kddi.com/torisetsu/pdf/w43ca/w43ca_torisetsu.pdf, 2006.
• 9: John I. Kiger, The depth/breadth trade-off in the design of menu-driven user interfaces, International Journal of Man-Machine Studies, v.20 n.2, p.201-213, Feb. 1984 [doi>10.1016/S0020-7373(84)80018-8]
• 10: Kevin Larson , Mary Czerwinski, Web page design: implications of memory, structure and scent for information retrieval, Proceedings of the SIGCHI conference on Human factors in computing systems, p.25-32, April 18-23, 1998, Los Angeles, California, United States [doi>10.1145/274644.274649]
• 11: B. Liu, G. Francis, and G. Salvendy. Applying models of visual search to menu design. Int. J. Human-Computer Studies, 56:307--330, 2002.
• 12: Shouichi Matsui , Seiji Yamada, Genetic algorithm can optimize hierarchical menus, Proceeding of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, April 05-10, 2008, Florence, Italy [doi>10.1145/1357054.1357271]
• 13: Zbigniew Michalewicz , David B. Fogel, How to solve it: modern heuristics, Springer-Verlag New York, Inc., New York, NY, 2000
• 14: Juan C. Quiroz , Sushil J. Louis , Sergiu M. Dascalu, Interactive evolution of XUL user interfaces, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277373]
• 15: Miika Silfverberg , I. Scott MacKenzie , Panu Korhonen, Predicting text entry speed on mobile phones, Proceedings of the SIGCHI conference on Human factors in computing systems, p.9-16, April 01-06, 2000, The Hague, The Netherlands [doi>10.1145/332040.332044]
• 16: E. Eugene Schultz, Jr. , Patrick S. Curran, MENU STRUCTURE AND ORDERING OF MENU SELECTION: INDEPENDENT OR INTERACTIVE EFFECTS?, ACM SIGCHI Bulletin, v.18 n.2, p.69-71, Oct. 1986 [doi>10.1145/15683.1044100]
• 17: M.L. Toms, M.A. Cummings-Hill, D.G. Curry, and S.M. Cone. Using cluster analysis for deriving menu structures for automotive mobile multimedia applications. SAE Technical Paper Series 2001-01-0359, SAE, 2001.
• 18: P. Zaphiris. Depth vs breadth in the arrangement of web links. In Proc. 44th Annual Meeting of the Human Factors and Ergonomics Society, pages 139--144, 2000.
• 19: P. Zaphiris, S.H. Kurniawan, and R.D. Ellis. Age related difference and the depth vs. breadth tradeoffs in hierarchical online information systems. In Proc. User Interfaces for All, LNCS 2615, pages 23--42, 2003.
• 20: M. Ziefle and S. Bay. Mental models of a cellular phone menu. Comparing older and younger novice users. In Proc. MobileHCI 2004, LNCS 3160, pages 25--37, 2004.

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: Interaction styles (e.g., commands, menus, forms, direct manipulation)

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:
Algorithms, Design, Human Factors

Keywords:
genetic algorithm, hierarchical menu, optimization, simulated annealing