CHI 2008 Proceedings · Menu and Command Selection

April 5-10, 2008 · Florence, Italy

Genetic Algorithm Can Optimize Hierarchical Menus
Shouichi Matsui
SERL, CRIEPI
2-11-1 Iwado-kita, Komae
Tokyo 201-8511, Japanmatsui@criepi.denken.or.jp

Seiji Yamada
National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda
Tokyo 101-8430, Japanseiji@nii.ac.jp
menu items. Amant et al. showed the concepts to support
the analysis of cell phone menu hierarchies [1]. They proposed a model-based evaluation of cell phone menu interaction, gathered data and evaluated three models, Fitts’ law
model, GOMS, and ACT-R. They concluded that the prediction by GOMS was the best among the three models. They
also tried to improve menu traversal time by using a simple best-first search algorithm, and got over 30% savings intraversal time. These very simple search methods gave fairly
good improvements [1, 11], therefore, we can expect further
performance improvements by optimizing the structure witha better algorithm.

ABSTRACT

Hierarchical menus are now ubiquitous. The performanceof 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 the performance by optimizing the menu’s structure. This paper
proposes an algorithm based on the genetic algorithm (GA)for optimizing the performance of menus. The algorithm
aims to minimize the average selection time of menu items
by considering movement and decision time. We show results on a static hierarchical menu of a cellular phone wherea small screen and limited input device are assumed. Our
work makes several contributions: a novel mathematical optimization model for hierarchical menus; novel optimization
method based on the genetic algorithm (GA).

ACM Classification Keywords

This paper proposes an algorithm based on the Genetic Algorithm (GA) [7] for optimizing the performance of menus.
The algorithm aims to minimize the average selection timeof menu items by considering movement and search/decision
time. We will show results on a static hierarchical menu of acellular phone where a small screen and limited input device
are assumed.

H.5.2 [Information Interfaces and Presentation]: User Interfaces — Interaction styles, Screen design.

FORMULATION OF THE PROBLEM

Author Keywords

Hierarchical menu, optimization, genetic algorithm.

Overview

INTRODUCTION

The optimization problem of hierarchical menus can be considered as one dealing with placing menu items on the nodesof a tree. Let us assume a tree where the maximum depth isD, the maximum number of children that a node has is W ,the root is the initial state, and menu items are on nodes. An
example of a hierarchical menu is shown in Fig. 1. As shownin the figure some menu items have children; i.e., some menu
items have submenus. The time to select the target item is thetime to traverse from the root to the target node. The problem is to minimize the average traversal time with respect tothe given search frequencies of different menu items.

Hierarchical menus are one of the primary controls for issuing commands in GUIs. The performance of the menu
depends on many factors: structure, layout, colors and soon. There has been many studies on novel menus (e.g., [2,3, 8]), but there has been little work on improving the performance of a menu by changing its structure [1, 6, 11].
There have been many studies on menu-design and menulayout from the standpoint of the user interface. Francis etal. were the first to optimize a multi-function display, thatwas essentially the same as the hierarchical menu by using
Simulated Annealing (SA) [6]. Liu et al. applied a visual
search model to menu design [11]. They used the Guided
Search (GS) model to develop menu designs. They also used
an optimization algorithm to minimize the predicted searchtimes according to predefined search frequencies of different

We cannot arbitrarily arrange the menu purely for efficiency.
We must respect the semantic relationships between the items.
That is, “Ringer Volume” is under the “Settings” categoryrather than vice versa for good reason. To cope with thedifficulties of representing and reasoning about menu item
semantics we introduce two metrics: functional similarityand menu granularity. Functional similarity is a metric that
represents the similarity of two menu items in terms of theirfunctions. We assume that the functional similarity takes avalue between 0 and 1; 0 means that the two items have nosimilarity and 1 means that the two items have very high similarity. For example it is very natural to assume that “Create

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, or
republish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
CHI 2008, April 5 - 10, 2008, Florence, Italy.
Copyright 2008 ACM 978-1-60558-011-1/08/04…$5.00

1385

CHI 2008 Proceedings · Menu and Command Selectionlevel 0

1
V
1

1
V
0

level 1....
Pointing
time t p0levelmm
V
0

Pointing Time and Search/Decision Time

0V
0

Search/Decisontime t sd
0....

As Silfverberg et al. [12] and Cockburn [4] reported, thepointing time tpi can be expressed as tpi = a+b log2 (Ai /Wi +1) by using the Fitts’ law.

Up to Wchildren
1
V
W -2

....
....

....

1
V
W -1

We assume that the search/decision time tsd
i at level l nodethat has nl items can be expressed as reported by Cockburn
et al. [4]

....

tp
W-1

tp
1
m
V
1

April 5-10, 2008 · Florence, Italy

m
V
W -2

• For an unexperienced user, the time required for a linear
sd l
sdsearch, tsd
i =b n +a .

m
V
W -1

• For an expert, we can assume that the time tsd
i obeys Hicksd
sd
Hyman’s law, tsd
where Hi = log2 (1/Pil )i = b Hi + a
and Pil is selection probability.

Figure 1. Tree structure of a hierarchical menu.

New Mail” and “Favorite Web Site” have low similarity andthat “Create New Mail” and “Inbox of Mail” have high similarity. We use this metric to avoid placing items with low
similarity on the same submenu of a node. If items with low
similarity are put on the same submenu, it becomes difficult
for a user to remember the menu layout. The formal definition will be given later. Menu granularity is a metric thatreflects the number of submenus a node has as its descendants. We introduce this metric to avoid placing an item thathas many children and an item that has no child as childrenof the same node. The formal definition will be given later.

Functional Similarity

Toms et al. reported the result of generating a menu hierarchy from functional descriptions using cluster analysis [13].
However, this approach is time consuming; therefore, wechose to use another one.
We represent the functional similarity of item Ix and Iy by
using a function s(Ix , Iy ) which takes a value between 0
and 1. Let us assume that a generic function of each item Ii
can be specified
 by some words wli = {w1 , w2 , · · · }, andlet WL = wli be the whole words. Let us also assumei

Formulationthat an intermediate node can be characterized by the words
by which the children are specified. Let x be a vector inwhich element xi = 1 iff the node x has the i-th word as
its specification, And let y be a vector of node y. Then,the functional similarity s(Ix , Iy ) is defined as s(Ix , Iy ) =x·yl|x||y| . Let us consider a node vi that has m children. The
penalty of functional similarity Pvsl of node vil is defined asim−1 m−1
(1
−
s(I
,
I
)). And the total penalty
Pvsl = x=0
x
y
y=0
i

s
s
s
P is defined as P = vl ∈V Pvl .

Notation

Let l be the level number, i is the ordering number in siblings, and vil be a node of a tree (Fig. 1). Moreover, let
M = (V, E) be a tree where V = {vil } denotes the nodes,
and E = {eij } denotes the edges. We call the leaf nodes
that correspond to generic functions “terminal nodes.” Wealso assume that the selection probability of the terminal
node/generic function is represented by Pi .
There are two kinds of menu item or node in the tree M .
One type is terminal nodes that corresponds to generic functions, and the other is intermediate nodes. The terminal
nodes cannot have children. We denote terminal nodes bygi and intermediate nodes by si . We also denote the set ofgi by G and the set of si by S. Let Ii represent a menu
item and the total number of items be N ; i.e., there are
Ii (i = 1, · · · , N ) menu items. Items that correspond to
generic functions are less than N , and some items/nodes areintermediate items/nodes that have submenu(s) as a child orchildren. We assume that a menu item Ii is assigned to anode vil ; therefore, we use Ii and vil interchangeably.

iiMenu Granularity

The menu granularity gvil of a node vil is defined as the total
number of descendants. If node vil is a terminal node, thengvil = 0. Moreover, if node vil has m children (vjl+1 , j =0, · · · , m − 1) whose menu granularities are gvl+1 , (j =j
m−10, · · · , m − 1), then gvil is defined as gvil = j=0 gvl+1 .
j

The penalty of menu granularity Pvgl of node vil is defined as im−1 m−1 Pvgl = i=0
gvil − gvjl  And the total penalty P g
j=0iis the sum over the whole nodes.

Selection Time

The selection time tli of a menu item/node vil on the hierarchical level l can be expressed using the search/decisionpplsd
time tsd
i and the pointing time ti as ti = ti + ti [4]. We
also consider the time to reach level l; therefore, the wholeselection time Ti of a node vil on level l can be the sum fromthe root node to the final node Thus, the average selection
Ntime Tavg is Tavg = i=1 Pi Ti .

Objective Function

The problem is to minimize the following objective function:
f = Tavg + αP s + βP g ,(1)

where α and β are constants that control the preference offunctional similarity and menu granularity.

1386

CHI 2008 Proceedings · Menu and Command Selection

April 5-10, 2008 · Florence, Italy

Optimization Problem

When menu items that are placed as the children of a node V
are given, the placement that minimizes the average pointing
time is straightforward. Therefore, the problem is to findthe best assignment of menu items to nodes of a tree thatminimizes Equation (1).
GENETIC ALGORITHM

Genetic Algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimizationand search problems. GA is a meta-heuristic algorithm thatuses techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover [7].
Basic Strategy and Chromosome Representation

Previous studies showed that breadth was preferable to depth[5, 10, 14]. Because the previous studies showed that breadth
was preferable to depth, we use a kind of breadth-first searchalgorithm as the core of the proposed GA.

Figure 2. The key layout of the target cellular phone.

We measured the pointing time of one-handed thumb users
for the above 28 groups by recording the tone produced byeach key press [1]. Unpaid volunteers participated in theexperiment. We prepared 28 tasks corresponding to the 28
groups. We got tpi = 192 + 63 log2 (Ai /Wi + 1) (ms) for
predicting the pointing time, and the equation is very similar
to the one reported by Silfvergerg et al.[12]1 Menu selections
are done by pressing keys, therefore we assume that moving
to the next level starts from the key that reached the current
node. Although the target phone has the ability to select amenu item by pressing a key that is prefixed to item title(shortcut key), we assumed that all selections were done bycursor movements.

An algorithm that places a menu items Ii one by one on a
usable node can find a good solution. For this reason, we
use an algorithm that assign Ii to a node as follows:
1. A chromosome of the GA is a sequence of Ii ; i.e., a chromosome can be represented as a permutation of numbers.
2. According to the permutation, assign a menu items Ii one
by one to a usable node that has the smallest node number.
3. If a generic function is assigned to a node then a node cannot have children, and the node below the assigned node
is marked as unusable.

The target of this experiments was an expert; therefore, wel2
used tsd
i = 80 log2 (n ) + 240 (ms) [4] ;Other Configurations of GA

We use a crossover operator that does not generate an invalid
chromosome. As described above, a chromosome is a permutation of numbers; therefore, we use crossover operatorsthat are developed for the representation. We use the swap
mutation as the mutation operator. Randomly chosen geneat position p and q are swapped. The crossover and mutation operators do not generate invalid chromosomes; i.e.,
offsprings are always valid permutations. We use a steadystate GA, the population size is 100, the mutation rate is one
swap per chromosome. The tournament selection of size two
is used as the selection method.

Usage Frequency Data

We gathered usage frequency data as follows. The first author recorded the daily usage of each function for two months,
and we generated the usage frequency data from the record.
There were 129 terminal nodes in the data.
Functional Similarity

We assigned three to five words to each generic function according to the users’ manual of the target phone [9].

NUMERICAL EXPERIMENTS

Results

The target is a cellular phone that is used by one of the authors. The phone [9] has 24 keys as shown in Fig. 2.

We conducted the following experiments. Because GA isa stochastic algorithm, we conducted 50 runs for every test
cases, and the results shown in Table 1 and Table 2 are averages over 50 runs. The two parameters for weights were set
to α = 10.0 and β = 1.0 in Table 1.

Experimental Data

Pointing Time and Decision TimeThe index of difficulty for 24 × 24 key pairs were calculated
as follows. We measured the relative coordinates of the center (x, y) of each key, and measured the width and height ofeach key. We calculated the index of difficulty to an accuracy of one digit after the decimal point. This gave us 28
groups of indexes of difficulty.

case 1 Typical Usage: This experiment was conducted toassess the typical improvement by the GA. The maximum
width W was 16.
1 p
ti = 176 + 64 log 2 (Ai /Wi + 1) (ms).
2

The equation is derived from experiments conducted for a computer display, and is not for a cellular phone.

1387

CHI 2008 Proceedings · Menu and Command Selection
Case
Original
Local Move
Case 1 (W = 16)Case 2 (W = 12)Case 2 (W = 9)Case 2 (W = 6)

Tave (ms)
3331
2813
2066
2034
1981
2224

(%)
0.0
15.6
38.0
38.9
40.5
33.2

Ps
454
454
721
539
392
274

Pg
793
793
1299
871
336
203

CONCLUSION

We proposed a GA-based algorithm for minimizing the average selection time of menu items that consider the movement
time and the decision time. The preliminary results showedthat the algorithm can generate a better menu structure. The
target of the proposed algorithm is not limited to cellular
phones, and can be applied to other kinds of menus.

Table 1. Improvements in average selection time.

α
10.0
20.0
5.0
0.0

β
1.0
1.0
1.0
0.0

Tave (ms)
1981
2034
1957
1874

(%)
40.5
38.9
41.2
43.7

P
392
386
401
569
s

April 5-10, 2008 · Florence, Italy

REFERENCES

1. Amant, St., Horton,T.E. and Ritter, F.E. Model-based
evaluation of cell phone menu interaction, Proc. CHI
2004, ACM Press (2004), 343–350.

P
336
398
307
556
g

2. Ahlström, D. Modeling and improving selection incascading pull-down menus using Fitts’ law, thesteering law and force fields, Proc. CHI 2005, ACM
Press (2005), 61–70.

Table 2. Effect of weights.

3. Beck, J., Han, S.H., and Park, J. Presenting a submenu
window for menu search on a cellular phone, JHCI,
20,3 (2006), 233–245.

case 2 Limited Breadth: Although breadth is preferable todepth, pressing a far key or pressing a “Down” key manytimes is sometimes tedious. This experiment was conducted to see the effect of limiting the breadth. In thiscase, we set the breadth (W ) to 12, 9, and 6.

4. Cockburn, A., Gutwin, G., and Greenberg, S. A
predictive model of menu performance, Proc. CHI
2007, ACM Press (2007), 627–636.

In Table 1, “Local Move” shows the results of a local modification that places menu items according to their frequency;
i.e., the most frequently used item is placed as the top item,and so on. As the table shows, the proposed algorithm cangenerate menu with shorter average selection time. Moreover, limiting the number of usable keys gave us better menus.
This is partly because the search/decision time is proportional to log2 (n), where n is the number of items. As thenumber of items increases, the search/decision time increase;
therefore, the average selection time increase. Limiting thenumber of keys to 6 gave a longer selection time, and smaller
penalties.

5. Schultz Jr., E.E. and Curran, P.S. Menu structure andordering of menu selection: independent or interactive
effects?, SIGCHI Bull., 18,2 (1986), 69–71.
6. Francis, G. Designing multifunction displays: an
optimization approach, Int. J. of Cognitive Ergonomics,
4,2 (2000), 107–124.
7. Goldberg, D.E. Genetic algorithm, Addison-Wesley(1989).
8. Findlater, L. and McGrenere,J. A comparison of static,
adaptive, and adaptable menus, Proc. CHI 2004, ACM
Press (2004), 89–96.
9. KDDI. Manual for CASIO W43CA, http://www.au.
kddi.com/torisetsu/pdf/w43ca/w43ca torisetsu.pdf(2004).

Effects of weights

We introduced two weights for penalties of functional similarity and of menu granularity. Table 2 shows the resultsof different weight settings for the case W = 9. As Table 2
shows α and β to non-zero gave similar results. Setting themto zero gave a shorter selection time, but the penalties werelarger.

10. Kiger, J.I. The depth/breadth trade-off in the design ofmenu-driven user interfaces, Int. J. Man-Mach. Stud.,20,2 (1984), 201–213.
11. Liu, B. Francis, G., and Salvendy, G. Applying modelsof visual search to menu design, Int. J.
Human-Computer Studies, 56 (2002), 307–330.

DISCUSSION AND FUTURE WORKThe experiments show that the proposed algorithm can generate better menu hierarchies for the target phone. Because
our targets are not limited to cellular phones, and the preliminary results are promising, we will apply the algorithm towider varieties of targets.

12. Silfverberg, M., MacKenzie, I.S., and Kauppinen, T.
Predicting text entry speed on mobile phones, Proc.
CHI 2000, ACM Press (2000), 9–16.

In this paper, we focused on a static menu as the target; adaptive/dynamic menu (e.g., [2, 3, 8]) that changes menu contents depending on usage will be a future target.

13. Toms, M.L., Cummings-Hill, M.A., Curry, D.G., andCone, S.M. Using cluster analysis for deriving menu
structures for automotive mobile multimedia
applications, SAE Technical Paper Series,
2001-01-0359 (2001), SAE.

The data used in the experiments, especially selection frequency data, were limited. Therefore we should gather awider variety of usage data and use that to confirm the effectiveness of the proposed method.

14. Zaphiris, P., Kurniawan, S.H., and Ellis, R.D. Age
related difference and the depth vs. breadth tradeoffs inhierarchical online information systems, Proc. User
Interfaces for All, LNCS 2615, (2003), 23–42.

1388