Optimizing Hierarchical Menus by Genetic Algorithm andSimulated Annealing
Shouichi Matsui

Seiji Yamada

SERL, CRIEPI
2-11-1 Iwado-kita, Komae
Tokyo 201-8511, Japan

National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda
Tokyo 101-8430, Japanmatsui@criepi.denken.or.jp

seiji@nii.ac.jp

ABSTRACT
Hierarchical menus are now ubiquitous. The performance of themenu depends on many factors: structure, layout, colors and soon. There has been extensive research on novel menus, but there
has been little work on improving performance by optimizing themenu’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 areassumed. We will also show performance comparison of the GAbased algorithm and the SA-based one by using wide varieties ofusage patterns.
Figure 1: Example of hierarchical menu for a web browser.

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

work on improving the performance of a menu by changing its
structure [1, 6, 11, 12]. Since a very simple search method gave
a fairly good improvement [1], we proposed an algorithm based on
the genetic algorithm (GA) for minimizing the average selection
time [12].
There have been many studies on menu-design and menu-layout
from the standpoint of the user interface. Francis et al. were thefirst to optimize a multi-function display that is very similar to ahierarchical menu using the simulated annealing (SA) [6]. Quiroz
et al. proposed an interactive evolution of a non-hierarchical menu
using an interactive evolutionary computation (IEC) approach [14].
Liu et al. applied a visual search model to menu design [11].
They used the Guided Search (GS) model to develop menu designs.
They defined a GS simulation model for a menu search task, andestimated the model parameters that would provide the best fit between model predictions and experimental data. Then they used an
optimization algorithm to identify the menu design that minimized
the predicted search times according to predefined search frequencies of different menu items, and they tested the design. Their results indicate that the GS model has the potential to be part of asystem for predicting or automating the design of menus.
Amant et al. showed the concepts to support the analysis of cellular phone menu hierarchies [1]. They proposed a model-based
evaluation of cellular phone menu interaction, gathered data andevaluated 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 selection timeby using a simple best-first search algorithm and got over 30% savings in selection time.

General Terms
Human Factors, Design, Algorithms

Keywords
Hierarchical menu, optimization, genetic algorithm, simulated annealing.

1.

INTRODUCTION

Hierarchical menus are one of the primary controls for issuingcommands in GUIs. These menus have submenus as menu items
and display submenus off to the side when they are selected asshown in Figure 1. The performance of the menu, i.e., the average selection time of menu items, depends on many factors, including its structure, layout, and colors. There have been manystudies on novel menus (e.g., [2, 3, 7]), but there has been little

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, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
GECCO’08, July 12–16, 2008, Atlanta, Georgia, USA.
Copyright 2008 ACM 978-1-60558-130-9/08/07…$5.00.

1587

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 movements and search/decision time.
We will show the experimental results on a static hierarchicalmenu of a cellular phone as an example where a small screen andlimited input device are assumed. We will also show performancecomparison of GA-based algorithm and the SA-based one by using
wide variety of the usage patterns.

level 02.

levelm0
V0

Search/Decisontime t sd
0
1
V
1

1
V
0

level 1....
Pointing
time t p0

FORMULATION OF THE PROBLEM

2.1 Overview

m
V
0

....

Up to Wchildren
1
V
W -2

....
....

....
t

tp
1
m
V
1

1
V
W -1

....

p
W-1
m
V
W -2

m
V
W -1

Figure 2: Tree structure of a hierarchical menu.

The optimization problem of hierarchical menus can be considered as one dealing with placing menu items on the nodes of a tree.
Let us assume a tree where the maximum depth is D, 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 Figure 2. As shown in the figure, some menu items
have children; i.e. some menu items have submenus. The time toselect the target item is the time to traverse from the root to thetarget node. The problem is to minimize the average traversal timewith respect to the given search frequencies of menu items.
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” category rather than viceversa for good reason. To cope with the difficulties of representing
and reasoning about menu item semantics we introduce two metrics: functional similarity and menu granularity.
Functional similarity is a metric that represents the similarity of
two menu items in terms of their functions. We assume that thefunctional similarity takes a value between 0 and 1; 0 means thatthe two items have no similarity and 1 means that the two items
have very high similarity. For example it is very natural to assume
that “Create New Mail” and “Favorite Web Site” have low similarity and that “Create New Mail” and “Inbox of Mail” have highsimilarity. 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, then it becomes difficult for a user
to recognize and memorize the menu layout. The formal definition
will be given later.
Menu granularity is a metric that reflects the number of submenus a node has as its descendants. We introduce this metric toavoid placing an item that has many children and an item that has
no child as children of the same node. The formal definition will
be given later.
The problem of minimizing the average traversal time is a very
difficult one because of the following constraints;

denotes the edges. We call the leaf nodes that correspond to genericfunctions “terminal nodes.”There are two kinds of menu item or node in M . One type isterminal nodes that correspond to generic functions, and the otheris intermediate nodes. The terminal nodes cannot have children.
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 correspondto generic functions are less than N , and some items/nodes are intermediate items/nodes that have submenu(s) as a child or children.
We assume that a menu item Ii is assigned to a node vil , therefore
we use Ii and vil interchangeably.
We also assume that the selection probability of the terminal
node/generic function is represented by P ri .

2.2.1 Selection Time
The selection time tli of a menu item/node vil on the hierarchicallevel l can be expressed using the search/decision time tsd
i and theppointing time tpi as tli = tsd
i + ti [5]. We also consider the time toreach level l; therefore, the wholeP
selection time Ti of a node vil onjllevel l can be expressed as Ti = l−1
j=0 tij + ti . Thus the average
selection time Tavg is as follows:
Tavg =NX

P r i Ti .

(1)

i=1

2.2.2 Pointing TimeAs Silfverberg et al. [15] and Cockburn [5] reported, the pointing time tpi can be expressed by using Fitts’ law as tpi = ap +bp log2 (Ai /Wi + 1), where the coefficients ap and bp are determined empirically by regressing the observed pointing time, Ai is
the distance moved, and Wi is the width of the target.
Fitts’ law describes the time taken to acquire, or point to, a visual target. It is based on the amount of information that a person
must transmit through his/her motor system to move to an item
– small, distant targets demand more information than large close
ones, and consequently they take longer to acquire. Therefore, theterm log2 (Ai /Wi + 1) is called the index of difficulty (ID).

• The traversal time from a node to its children is not constant;it varies depending on the starting and ending nodes.
• Menu items usually belong to groups, and they have hierarchical constraints.

2.2.3 Search/Decision Time

• We should consider the functional similarity and the menu
granularity of each item from the standpoint of usability.

We assume that the search/ decision time tsd
i can be expressed
as follows [5].
• For an unexperienced user, the time required for a linear
search is tsd= bsd nl + asd , where nl is the number ofiitems that a level l node has, and the coefficients asd and bsd
are determined empirically by regressing the observed searchtime.

2.2 Formulation
Let l be the level number, i is the ordering number in siblings,
and vil be a node of a tree (Figure 2). Moreover, let M = (V, E)
be a tree where V = {vil } denotes the nodes, and E = {eij }1588

• For an expert, we can assume that the time tsd
i obeys HickHyman’s law and can be expressed as. tsd= bsd Hi +isdla , Hi = log2 (1/P ri ), where the coefficients asd and bsd
are determined empirically by regressing the observed searchtime. If we can assume that all items are equally probable,
H = log2 (nl ) iﬀ ∀P ril = 1/nl .

is minimized as follows:
1. Sort Ii using P ri as the sort key in descending order, and let
the result be Ii (i = 0, · · · , n − 1),
2. Sort vil+1 using tli as the sort key in ascending order, and let
(l+1)(i = 0, · · · , n − 1)
the results be vi

2.2.4 Functional Similarity

Toms et al. reported the result of generating a menu hierarchy
from functional descriptions using cluster analysis [17]. However,this approach is time consuming therefore, we chose to use anotherone. 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 canSbe specified
by some words wli = {w0 , w1 , · · · }, and let WL = i wli be thewhole words. Let us also assume that an intermediate node can becharacterized by the words by which the children are specified. Let
x be a vector in which element xi represents the frequency of thei-th word in its specification, and let y be a vector of node y. Then,x·ythe functional similarity s(Ix , Iy ) is defined as s(Ix , Iy ) =.
|x||y|
This similarity is widely utilized in information retrieval field [4].
penaltyPof
Let us consider a node vil that has m children. TheP
m−1
functional similarity Pvsl of node vil is defined as Pvsl = m−1
x=0
y=i+1
i
i
s
(1 − s(Ix , Iy )). And the total penalty P is defined as follows:X
Ps =Pvsl .
(2)0}vil ∈{V \v0iinumber of descendants. If node vil is a terminal node, then gvl = 0.
iMoreover, if node vil has m children (vjl+1 , j = 0, · · · , m − 1)
whose menu granularities are gvl+1 , (j = 0, · · · , m − 1), then gvl
ijP
is defined as gvl = m−1g.
The
penaltyofmenu
granularity
l+1
j=0
vj
i
˛
Pm−1 Pm−1 ˛˛˛Pvgl of node vil is defined as Pvgl =
i=0
j=i+1 ˛gvil − gvjl ˛.
ii
And the total penalty P g is defined as follows:
X
Pvgl .
(3)Pg =0}vil ∈{V \v0i

2.2.6 Objective Function
The problem is to minimize the following objective function:
f = Tavg + αP s + βP g ,(4)where α and β are constants that control the preference of functional similarity and menu granularity.

2.3 Local/Partial Optimization

When menu items that are placed as the children of a node V
are given, the placement that minimizes the average pointing timeis straightforward. Therefore, the problem is to find the best assignment of menu items to nodes of a tree that minimizes Equation (4), where nodes have a fixed capacity of W items. There
should be at least L = N/W  nodes in the tree and N items
placed on some node. The first node has W items chosen fromN items, and the second node has W items chosen from N − W
items, and so on, so the search space of the problem is roughly
L
N CW × N−W CW × · · · × N−LW CW = N !/(W !) , therefore
the problem is a difficult combinatorial optimization problem. For
instance, consider the case of N = 200, W = 10. The search
space is roughly 200!/((10!)20 ) ∼ 10243 .

3. ALGORITHMS BASED ON GA AND SA

3.2 GA-based Algorithm

2.3.1 Placing Items as Children of a Node3.2.1 Chromosome and Mapping from Genotype toPhenotypeLet us consider a node vil on level l that has n ≤ W children
l+1
vj (j = 0, · · · , n − 1), and represent the traversal time from vil
to vjl+1 , i.e., the pointing time for vjl+1 by tlj . When we want to

A simple way to represent a solution of the problem is a tree.
But there is a problem that genetic operators such as crossover ormutation may generate an infeasible solution; i.e., the tree does notcontain all the generic functions. There are two ways to cope withthis problem. The first way is to convert an infeasible solution into a
feasible one, and also modify the chromosome. The other way is touse a chromosome representation that does not generate infeasible
solutions. We based the proposed algorithm on the latter approach.

place Ij , (j = 0, · · · , n − 1) menu items whose selection probabilities are represented by P rj as the children of the vil , the average
pointing time Tvl ,ii

2.3.2 Optimization Problem

Previous studies showed that breadth was preferable to depth[9, 10, 16, 18, 19]. Schultz and Curran reported that menu breadth
was preferable to depth [16]. Larson and Czerwinski reported theresults of depth and breadth tradeoff issues in the design of GUIs[10]. Their results showed that, while increased depth did harm
search performance on the web, a medium condition of depth andbreadth outperformed the broadest shallow web structure overall.
Zaphiris studied the effect of depth and breadth in the arrangement of web link hierarchies on user preference, response time,and errors [18]. He showed that previous menu depth/breath tradeoff procedures were applicable to the web link domain. He also
showed that task completion time increased as the depth of the
web site structure increased. Zaphiris et al. also showed the resultsof the study investigating age related differences as they relate to
the depth versus breadth tradeoff in hierarchical online information
systems [19]. They showed that shallow hierarchies were preferred
to deep hierarchies, and seniors were slower but did not make moreerrors than their younger counterparts when browsing web pages.
Because the previous studies showed that breadth was preferable
to depth, we use a kind of breadth-first search algorithm (shown
later) as the core of the proposed GA.

The menu granularity gvl of a node vil is defined as the totaln−1
Xgives the minimum average

3.1 Basic Strategy

2.2.5 Menu Granularity

Tv l =(l+1)

3. Placing Ii on the node vi
pointing time from node vil .

P rj tlj ,

(5)

j=0

1589

!  

!  

           
 

 #        " !
 $ "

 

 STEP1: T ← Tmax
select a permutation Vc at random
STEP2: pick a point Vn from the neighborhood of Vc
if eval(Vn ) is better than eval(Vc )then select it (Vc ← Vn )Δevalelse select it with probability e− T
repeat this step kT times
STEP3: set T ← γT
if T ≥ Tmin then goto STEP2 else goto STEP1

Figure 4: Outline of SA-based algorithm.
Figure 3: Mapping from permutation to a tree structure.

func1

func1
func3

Since breadth is preferable to depth, an algorithm that places
menu items Ii one by one on a usable node that has the smallest
node number can find a good solution. We number each node fromroot to bottom, and from left to right. We use an algorithm thatassigns Ii to a node as follows:

func2
root

func4

func2
root

int1

func3

func4

int1

func5

func5
int2
func6

1. A chromosome of the GA is a sequence of Ii , i.e., a chromosome can be represented as a permutation of numbers.

left: before local search

2. According to the permutation, assign menu items Ii one by
one to vacant positions of the node that has the smallest node
number.

func6
right: after local search

Figure 5: Local search.
state GA, for which the population size is 100, and the mutation
rate was one swap per chromosome.

3. If a generic function is assigned to a node, then the numberof children that the node can have is decreased by 1.

3.3 SA-based Algorithm

If we have a sufficient number of intermediate nodes, we cansearch enough space to find the optimal solution.
Two examples of assignment according to permutation are depicted in Figure 3, where W is 4. In the figure, numbers in bold (1,2, 3) represent the intermediate node. Let us consider “Permutation
1”. In this case, we can assign “10”, “5”, and “11” to the root node.
But we cannot assign “7” to the root node, because the root nodecannot have any children if we did. Therefore, we should assign“7” to the next level node, and the remaining position of the root
node should be an intermediate node. Because there is an intermediate node in the root node, we can assign “1” to the root node.
In the case of “Permutation 2”, the mapping is straightforward.
The first number “1” is an intermediate node, so we assign it to
the root node, and the number of vacant positions in the tree isincremented by 4. The next number “10” can be assigned to theroot node, and “3” and “5” can be assigned to the root node. The
remaining numbers are assigned to the children of the root nodes.

We also developed an algorithm based on the simulated annealing (SA). The outline of the algorithm that is adopted from the bookby Michalewicz and Fogel [13] is shown in Figure 4. We used thesame representation and mapping of the GA; therefore, Vc and Vn
in Figure 4 represent permutations of numbers that correspond to
Ii . We also used the same local search in the SA-based algorithm.
The neighborhood is generated by using the swap mutation operator described above.
We used the following settings based on the preliminary experiments:

3.2.2 Crossover and Mutation

We used a local search method to improve the performance ofGA and SA. The method finds an unused node vil ; i.e., finds an intermediate node that has no child, and swaps vil with a node that is
the sibling’s child vjl+1 when swapping the two decreases the average selection time. Figure 5 shows an example of this procedure.
In the left tree, the intermediate node “int2” has no child, so it isswapped with “func3”, and the result is the right part.

Initial temperature: Tmax = 10
Minimum temperature: Tmin = 0.001
Cooling ratio: γ = 0.9
Cooling interval: kT = 100

3.4 Local Search

We used a crossover operator that does not generate an invalid
chromosome. As described above, a chromosome is a permutationof numbers; therefore, we used crossover operators that are developed for the representation. We used the CX (Cycle Crossover)[13], OX (Order Crossover) [13], PMX (Partially-Mapped Crossover)[13] for the crossover operators and compared the performance.
We use the swap mutation as the mutation operator. Randomly
chosen genes at position p and q are swapped.
The crossover and mutation operators do not generate invalid
chromosomes; i.e., offspring are always valid permutations.

3.2.3 Other GA Parameters
The selection of the GA is tournament selection of size 2. The
initial population is generated by random initialization; i.e., a chromosome is a random permutation of numbers. We used a steady1590

4. EXPERIMENTS
We conducted experiments to confirm the effectiveness of the
proposed algorithm, to compare the performance of GA-based andSA-based algorithms, to compare the performance of different crossover operators CX, OX, and PMX.
The target was a cellular phone that is used by one of the authors. The phone [8] has 24 keys as shown in Figure 6. The target
phone has hardware keys for “E-mail”, “EZweb”, “Phone book”,

4.2 Results for Original Frequency Data
We conducted the following experiments.
case 1 Typical Usage: This experiment was conducted to assess
the typical improvement by the GA and SA. The maximum
width W was 16.
case 2 Limited Breadth: Although breadth is preferable to depth,pressing “Down” key many times is sometimes tedious. This
experiment was conducted to see the effect of limiting thebreadth. In this case, we set W to 12, 9, and 6.
Because GA and SA are stochastic algorithms, we conducted 50
runs for every test case, and the results shown in Table 1 are averages over 50 runs. The two parameters for weights were set to
α = 10.0 and β = 1.0. The maximum number of fitness evaluations was 100,000.

Figure 6: Key layout of the target cellular phone.

and “Application”. Also there is a “Shortcut”key (cursor down).
The root menu thus has the four submenus corresponding to thehardware keys.

4.2.1 Performance Comparison
Table 1 shows the results (Tave ) of 4 algorithms, GA-based ones
with CX, OX, PMX, and SA-based one. Figures 7 and 8 show
the results of average selection time and the values of objectivefunction in box-plot format.
In Table 1, “Local Move” shows the results of a local modification that places menu items according to their frequency, i.e., themost frequently used item is placed as the top item, and so on.
“Imp(%)” means the improvement from the original menus that isdefined as Imp = (Torig − Topt )/Torig × 100, where Torig is theaverage traversal time of the original menu and Topt is the average
traversal time of optimized menu. The bold faces mean the best
among the algorithms. The “ave” means the average over 50 runs,“max” means the maximum and “min” means the minimum among
50 runs. As the table shows, the proposed algorithms can generatemenu with shorter average selection times. Moreover, limiting thenumber 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 the number of items increases, thesearch/decision time increase; therefore, the average selection timeincrease. Limiting the number of keys to 6 gave longer selection
times.
From Table 1, Figure 7, and Figure 8 we can conclude as follows:

4.1 Experimental Data
4.1.1 Pointing Time and Search/Decision TimeThe index of difficulty for 24 × 24 key pairs were calculated asfollows. We measured the relative coordinates of the center (x, y)of each key and measured width and height of each key. We calculated the index of difficulty to an accuracy of one digit after thedecimal point. This gave us 28 groups of indices of difficulty.
We measured the pointing time of one-handed thumb users forthe above 28 groups by recording the tone produced by each key
press [1]. Unpaid volunteers participated in the experiment. 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 etal. [15]1 Although the target phone has the ability to select a menu
item by pressing a key that is prefixed to item title, we assumed thatall selections were done by cursor movements.
The target of this experiments was an expert; therefore, we usedl2
tsd
i = 80 log 2 (n ) + 240 (ms) [5] ;4.1.2 Usage Frequency Data and Similarity• The SA-based algorithm performed best from the stand pointof average performance for W = 12, 9, 6. The GA-based
one using PMX performed best for W = 16. The SA-basedalgorithm found menus with smaller average value of objective function in all cases. It also found the minimum in allcases.

We gathered the 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 are 129
terminal nodes in the data. We call the data “Original.”
We also generated the following dataset from the “Original.” Weassumed a user who frequently used e-mail application (Mail2,
Mail3) and a user who frequently used Web application (Web2,
Web3).

• The variance of objective function is large in GA-based algorithms when compared with the SA-based one. There is no
significant difference among the GA-based algorithms.

Mail2 The frequencies of E-mail related items are multiplied by 2.

• The GA-based algorithm using CX found a menu structurewith the minimum average selection time for W = 12, 6.
The SA-based one found the best for W = 16 and the theGA-based one using OX found the best for W = 9.

Mail3 The frequencies of E-mail related items are multiplied by 3.
Web2 The frequencies of Web related items are multiplied by 2.
Web3 The frequencies of Web related items are multiplied by 3.

The original menu (Tave =3331 (ms)) and the best menu of Case
2 (W = 9), with the minimum objective function, (Tave =1953(ms)) that was found by the GA-based algorithm with OX are shownin Figure 11. In the figure, items and intermediate nodes are shownin boxes and the vertical ordering shows the placement in a single level menu. The box is omitted for low usage frequency items/
intermediate nodes for the sake of saving space.

We assigned three to five words to each generic function according to the users’ manual of the target phone [8].
1 pti = 176 + 64 log2 (Ai /Wi + 1) (ms).
2

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

1591

Table 1: Improvements in Average Selection Time.
CX
Tave (ms)Imp.(%)
avemin
ave max
3331
0.0
2812
15.0
2036 1949 38.9 41.5
1980 1886 40.6 43.4
1949 1915 41.5 42.5
2233 2004 33.0 39.9

CX

CX

W=12

PMX

SA

SA

5700

5900

Objective
CX

OX

PMX

SA

CX

W=6

OX

PMX

SA

W=9

7500

CX

OX

PMX

SA

CX

OX

PMX

SA

W=12

W=16

10200
9800

Objective

8100

2300
2100
1900

Average Selection Time (ms)

2300

PMX

OX

W=9

2100

OX

4700

Objective

4500

2100

SA

1900

Average Selection Time (ms)CX

SA
Tave (ms)Imp.(%)
avemin
ave max
1797 1784 46.1 46.4
1925 1885 42.2 43.4
1997 1922 40.1 42.3
2041 1922 38.7 42.3
2011 1901 39.6 42.9
2011 1923 39.6 42.3

Objective

PMX

W=6

7900

OX

1900

2100
CX

Table 2: Effect of Weights.
OX
PMX
Tave (ms)Imp.(%)Tave (ms)Imp.(%)
avemin
ave max
ave
min
ave max
1819 1749 45.4 47.5 1820 1788 45.4 46.3
1918 1873 42.4 43.8 1917 1876 42.4 43.7
2017 1921 39.4 42.3 1998 1935 40.0 41.92053 1939 38.4 41.8 1949 1920 41.5 42.3
2013 1927 39.6 42.1 2015 1927 39.5 42.1
2002 1910 39.9 42.7 1995 1917 40.1 42.5

SA
Tave (ms)Imp.(%)
avemin
ave max
3331
0.0
2812
15.0
2032 1917 39.0 42.4
1967 1931 41.0 42.0
1947 1893 41.5 43.2
2217 2014 33.4 39.5

2300

Imp.(%)
ave max45.3 46.2
42.4 43.8
39.6 42.2
37.8 42.5
39.4 41.8
39.8 42.9

Average Selection Time (ms)2300

Tave (ms)avemin1823 17931919 1871
2013 1925
2072 19162020 1940
2005 1902

1900

Average Selection Time (ms)weight
α
β
0
0
5
1
20
1
40
1
20
5
20 10

PMX
Tave (ms)Imp.(%)
avemin
ave max
3331
0.0
2812
15.0
2029 1979 39.1 40.6
1970 1930 40.9 42.1
1956 1924 41.3 42.2
2223 2015 33.3 39.5

7700

Case
Original
Local Move
Case 1 (W =16)
Case 2 (W =12)
Case 2 (W =9)
Case 2 (W =6)

OX
Tave (ms)Imp.(%)
avemin
ave max
3331
0.0
2812
15.0
2032 1972 39.0 40.8
1985 1918 40.4 42.4
1948 1887 41.5 43.4
2245 2015 32.6 39.5

CX

OX

PMX

SA

W=16

Figure 8: Comparison of objective function (Original).

Figure 7: Comparison of average selection time (Original).
In Figure 11, items with high usage frequency are placed on asmaller level and on an upper position. For example, the most frequently used “Inbox folder 2”, which is placed under the “Inbox”
menu in the original menu, is placed as a child of “E-Mail” in the
optimized menu. Note also that “Shortcut” is not used in the original menu, but it is fully utilized in the optimized menu; frequently
used URLs are placed in “Shortcut”.

4.2.2 Effects of Weights
We introduced two weights for the penalties of functional similarity and of menu granularity. Table 2 shows the results of different
weight settings for the case W = 9. Table 2 shows that the average selection time increased as we increased α. The effect of β is
not the same, the average selection time did not always increased
as we increased β. This is partly because there is the constraint of
maximum width W .
The SA-based algorithm performed well for wide varieties of

1592

PMX

SA

OX

PMX

6200
PMX

SA

CX

SA

OX

PMX

PMX

SA

SA

Web2

2200

Average Selection Time (ms)
CX

Mail3

OX

Web3

2200

Average Selection Time (ms)

2200
CX

OX

Web2

2000

SA

Mail2

5800
5400

CX

2000

PMX

1800

Average Selection Time (ms)

2200
2000

OX

OX

Mail3

1800

Average Selection Time (ms)

Mail2

CX

Objective

6200
5400
CX

1800

SA

2000

PMX

1800

OX

5800

Objective

6200
5400

5800

Objective

6200
5800

Objective

5400
CX

CX

OX

PMX

SA

Web3

Figure 9: Performance comparison (Mail2, Mail3).

Figure 10: Performance comparison (Web2, Web3).

weight settings from the stand point of average performance. However, from the stand point of minimum average selection time, theGA-based one with CX or OX performed better.

gather wider variety of usage data, and confirm the effectiveness ofthe proposed method.
We used CX, OX, and PMX as the crossover operators and there
were no significant performance difference among them and wemight have to develop a new crossover operator to improve the performance of GA-based algorithm.

4.3 Results for Other Dataset
Figures 9 and 10 depict the results of the average selection time
and the values of objective function in box-plot format for the “Mail2”,“Mail3”, “Web2”, and “Web3” datasets. We can conclude as follows:• The SA-based algorithm performed well for the four datasetsfrom the stand point of average performance. It found menus
with smaller objective function.
• The GA-based algorithm found a menu with the minimum
average selection time for “Mail2” and “Mail3” datasets.

5.

6. CONCLUSION
We proposed GA-based and SA-based algorithms for minimizing the average selection time of menu items that consider the user’s
pointer movement time and the decision time. The results showedthat the algorithms can generate a better menu structure. They
found over 40% reduction in the average selection time for wide
variety of usage patterns. The target of the proposed algorithms is
not limited to cellular phones, and the algorithms can be applied toother hierarchical menus.

7. REFERENCESDISCUSSION AND FUTURE WORK

[1] St. Amant, T.E. Horton, and F.E. Ritter. Model-based
evaluation of cell phone menu interaction. In Proc. CHI
2004, pages 343–350 2004.
[2] D. Ahlström. Modeling and improving selection in cascading
pull-down menus using Fitts’ law, the steering law and force
fields. In Proc. CHI 2005, pages 61–70, 2005.
[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] R. Baeza-Yates and B. Ribeiro-Neto. Modern Information
Retrieval, Addison-Wesley,1999.
[5] A. Cockburn, G. Gutwin, and S. Greenberg A predictivemodel of menu performance. In Proc. CHI 2007, pages
627–636, 2007.
[6] G. Francis. Designing multifunction displays: an
optimization approach. Int. J. of Cognitive Ergonomics,
4(2):107–124, 2000.
[7] L. Findlater and J. McGrenere. A comparison of static,
adaptive, and adaptable menus. In Proc. CHI 2004, pages
89–96, 2004.

The experiments show that the proposed algorithms can generate better menu hierarchies for the target phone. The proposed 4
algorithms found menus with nearly 40% reduction in the average
selection time. The SA-based algorithm performed best from thestandpoint of average performance.
Our model has four parameters (ap , bp ,asd , bsd ) that are determined empirically by regressing the observed data, and the average
selection time depends these parameters. However, we confirmedthat we could get nearly same improvements for wide ranges of theparameters’ settings.
Because the target of the proposed algorithm is not limited tocellular phones, and the preliminary results are promising, we will
apply the algorithm to wider varieties of targets including other hierarchical menus in office application and tree-structured data baselike bookmark of Web browser. In this paper we only focused on
the static menu as the target; adaptive/dynamic menu (e.g., [2,3,7])that changes menu contents in adapting to varying usage is a futuretarget.
The data that were used in the experiments, especially selection
frequency data, are limited, therefore it is also a future work to1593

Folder0
Folder4

Folder1

Folder2

Folder2

Folder3

Folder4

Folder5

Folder5
Inbox
Check,Mail,New

Folder1

Inbox

Folder3

E-MailCheck,E-Mail,Mail,New,

FUNC

Folder0

E-MailURL1-11

URL1-2

URL1-5

URL1-3

URL1-2

URL1-4

URL1-8

URL1-5

Folder1

URL1-6
Folder1

URL1-7

INT1

URL1-8

INT2

URL1-9
URL1-10
URL1-11EZWeb

URL1-12
URL1-13
Folder2

root

Application

Folder3

URL1-6
URL1-3
URL1-4
ShortcutFavorite Siteroot

URL1-13
URL1-9EZweb

URL1-7

Application

URL1-10

Shortcut

URL1-12

Optimized (W = 9)

Original
Figure 11: Comparison of menus.
[8] KDDI: Manual for CASIO W43CA,
http://www.au.kddi.com/torisetsu/pdf/w43ca/w43ca_torisetsu.pdf,
2006.
[9] J. I. Kiger. The depth/breadth trade-off in the design ofmenu-driven user interfaces. Int. J. Man-Mach. Stud.,20(2):201–213, 1984.
[10] K. Larson and M. Czerwinski. Web page design: implicationof memory, structure and scent for information retrieval. In
Proc. CHI 1998, pages 25–32, 1998.
[11] B. Liu, G. Francis, and G. Salvendy. Applying models ofvisual search to menu design. Int. J. Human-Computer
Studies, 56:307–330, 2002.
[12] S. Matsui and S. Yamada. Genetic algorithm can optimize
hierarchical menus, In Proc. of CHI 2008, 2008 (to appear).
[13] Z. Michalewicz and D.B. Fogel. How to solve it: modern
heuristics, Springer-Verlag, 2000.
[14] J.C. Quiroz, S.J. Louis, and S. M. Dascalu. Interactive
evolution of XUL user interfaces. In Proc. of GECCO 2007,
pages 2151–2158, 2007.
[15] M. Silfverberg, I.S. MacKenzie, and T. Kauppinen.

1594

Predicting text entry speed on mobile phones. In Proc. CHI
2000, pages 9–16, 2000.
[16] E.E. Schultz Jr. and P.S. Curran. Menu structure and orderingof menu selection: independent or interactive effects?
SIGCHI Bull., 18(2):69–71, 1986.
[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 relateddifference and the depth vs. breadth tradeoffs in hierarchicalonline 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 phonemenu. Comparing older and younger novice users. In Proc.
MobileHCI 2004, LNCS 3160, pages 25–37, 2004.