A Genetic Algorithm for Optimizing Hierarchical Menus
Shouichi Matsui and Seiji Yamada

Abstract— Hierarchical menus are widely used as a standard
user interface in modern applications that use GUIs. 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) andthe simulated annealing (SA) for optimizing the performance ofmenus. 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 results on a static
hierarchical menu of a cellular phone as an example where asmall screen and limited input device are assumed. We will also
show performance comparison of GA-based algorithm and the
SA-based one by using wide variety of the useage patterns.

Mail

Top Menu
Mail
Web
...

Web

I. I NTRODUCTION
Hierarchical menus are one of the primary controls for
issuing commands in GUIs. These menus have submenus asmenu items and display submenus off to the side when they
are selected. Cellular phones that have only small displays
show submenus as new menus, as shown in Fig. 1. The
performance of the menu, i.e., the average selection time ofmenu items, depends on many factors, including its structure,layout, and colors.
There have been many studies on novel menus (e.g.,[2], [3], [7]), but there has been little work improving theperformance of a menu by changing its structure [1], [5],[6], [11], [12]. A very simple search method gave a fairly
good improvement [1]; therefore, we can expect further
performance improvements by optimizing the structure.
There have been many studies on menu design, menu
layout from the standpoint of the user interface. Francis etal. were the first to optimize a multi-function display thatwas essentially the same as a hierarchical menu by using
Simulated Annealing (SA) [5], [6]. Quiroz et al. proposed
an interactive evolution of a non-hierarchical menu using aninteractive evolutionary computation (IEC) approach.
Liu et al. applied a visual search model of to menu design[11]. They used the Guided Search (GS) model to develop
menu designs. They defined a GS simulation model for amenu search task, and estimated the model parameters thatwould provide the best fit between model predictions andexperimental data. Then they used an optimization algorithm
to identify the menu design that minimized the predicted
search times according to predefined search frequencies ofdifferent menu items, and they tested the design. Their results
S. Matsui is with the System Engineering Research Laboratory (SERL), Central Research Institute of Electric Power Industry(CRIEPI), 2-11-1 Iwado-kita, Komae, Tokyo 201-8511, Japan; email: matsui[at]criepi.denken.or.jp.
S. Yamada is with the National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda, Tokyo 101-8430, Japan; email: seiji[at]nii.ac.jp.

Fig. 1.

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 ofcellular phone menu hierarchies [1]. They proposed a modelbased evaluation of cellular phone menu interaction, gathereddata 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 selection time by using a simple best-firstsearch algorithm and got over 30% savings in selection time.
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 timeof menu items by considering the user’s pointer movement
and search/decision time.
We will show preliminary results on a static hierarchicalmenu of a cellular phone as an example for a device with asmall screen and limited input capability.
II. F ORMULATION OF THE P ROBLEM
A. Overview
The optimization problem of hierarchical menus can beconsidered as one dealing with placing menu items on thenodes 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 Fig. 2.

2856
c978-1-4244-1823-7/08/$25.002008
IEEE

Example of Hierarchical Menu for a Cellular Phone.

level 01V0level 1

1
V
1

....
Pointing
time t p0levelmB. Formulation0
V
0

Search/Decisontime t sd0m
V0Fig. 2.

....

Up to Wchildren
1
V
W -2

....
....

....

1
V
W -1

....

tp
W -1

tp
1
m
V
1

m
V
W -2

m
V
W -1

Tree Structure of a Hierarchical Menu

As shown in the figure, some menu items have children; i.e.
some menu items have submenus. The time to select thetarget item is the time to traverse from the root to the target
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 vice versa for good reason. To copewith 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 the functional similarity takes a value between
0 and 1; 0 means that the two items have no similarity, and1 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 high similarity. We use
this metric to avoid placing items with low similarity on thesame 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 begiven later.
Menu granularity is a metric that reflects the number ofsubmenus a node has as its descendants. We introduce thismetric to avoid placing an item that has many children andan 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 isa very difficult one because of the following constraints;
The traversal time from a node to its children is notconstant; it varies depending on the starting and ending
nodes.
• Menu items usually belong to groups, and they havehierarchical constraints.
• We should consider the functional similarity and themenu granularity of each item from the standpoint ofusability.
•

1) Notation: Let l be the level number, i is the ordering
number in siblings, and vil be a node of a tree (Fig. 2).
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.”There are two kinds of menu item or node in M . One typeis terminal nodes that correspond to generic functions, andthe other is 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 correspond to generic functions are less than N
and some items/nodes are intermediate items/nodes that havesubmenu(s) as a child or children. We assume that a menu
item Ii is assigned to a node vil ; therefore, we use Ii and vilinterchangeably.
We also assume that the selection probability of theterminal node/generic function is represented by P ri .
2) Selection Time: The selection time tli of a menu
item/node vil on the hierarchical level l can be expressedpusing the search/decision time tsd
i and the pointing time ti
as follows [4]:ptli = tsd
i + ti .

(1)

We also consider the time to reach level l; therefore, thewhole selection time Ti of a node vil on level l can be
expressed as follows:

Ti =

l−1

tjij + tli .

(2)

j=0

Thus, the average selection time Tavg is defined as follows:
Tavg =N

P ri Ti .

(3)

i=1

3) Pointing Time: As Silfverberg et al. [13] and Cockburn[4] reported, the pointing time tpi can be expressed by using
the Fitts’ law as follows:
tpi = a + b log2 (Ai /Wi + 1),(4)

where the coefficients a and b are determined empiricallyby 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, avisual target. It is based on the amount of information that aperson must transmit through his/her motor system to moveto an item – small, distant targets demand more information
than large close ones, and consequently they take longer toacquire. Therefore the term log2 (Ai /Wi + 1) is called theindex of difficulty (ID),2008 IEEE Congress on Evolutionary Computation (CEC 2008)

2857

4) Search/Decision Time: We assume that the search/decision time tsd
i can be expressed as follows [4].
•For an inexperienced user, the time required for a linear
search is as follows:6) Menu Granularity: The menu granularity gvil of a nodevil is defined as the total number of descendants. If node vil
is a terminal node, then gvil = 0. Moreover, if node vil has mchildren (vjl+1 , j = 0, · · · , m − 1) whose menu granularities
are gvl+1 , (j = 0, · · · , m − 1), then gvil is defined as follows:
j

sd l
sd
tsd
i =b n +a ,(5)

where nl is the number of items that a level l nodehas, and the coefficients asd and bsd are determined
empirically by regressing the observed search time.
sd• For an expert, we can assume that the time ti obeys
Hick-Hyman’s law.
sd
sd
tsd
i = b Hi + a ,(6)

Hi = log2 (1/P ril ),(7)

where the coefficients asd and bsd are determined empirically by regressing the observed search time.
If we can assume that all items are equally probable
H = log2 (nl )iﬀ∀P ril = 1/nl .

(8)5) Functional Similarity: Toms et al. reported the resultof generating a menu hierarchy from functional descriptions
using cluster analysis [15]. However, this approach is time
consuming; therefore, we choose 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 generic function of each item Ii
can be specified
 by some words wli = {w0 , w1 , · · · }, andlet WL = wli be the whole words. Let us also assumeithat an intermediate node can be characterized by the words
by which the children are specified. Let x be a vector inwhich element xi represents the frequency of the i-th wordin its specification, and let y be a vector of node y. Then,the functional similarity s(Ix , Iy ) is defined as follows:x·ys(Ix , Iy ) =|x||y|(9)

Let us consider a node vil that has m children. The penalty
of functional similarity Pvsl of node vil is defined as follows:i

Pvsl =
i

m−1
 m−1


(1 − s(Ii , Ij )).

(10)

i=0 j=0

And the total penalty P s is defined as follows:Ps =vil ∈{V \v00 }Pvsl .
iwhere S int represents the set of intermediate nodes.

2858

(11)

gvil =m−1
j=0

gvl+1 .

(12)j

The penalty of menu granularity Pvgl of node vil is definedi
as follows:
m−1
m−1


 

(13)
Pvgl =
gvil − gvjl .
i

i=0 j=0

And the total penalty P g is defined as follows:Pvgl .
Pg =vil ∈{V \v00 }

i

(14)

where S int represents the set of intermediate nodes.
7) Objective Function: The problem is to minimize thefollowing objective function:
f = Tavg + αP s + βP g ,(15)

where α and β are the constants that control the preferenceof functional similarity and menu granularity.
C. Local/Partial Optimization
1) Placing Items as Children of a Node: Let us consider
a node vil on level l that has n ≤ W children vjl+1 (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 place Ij , (j = 0, · · · , n − 1) menu items whose selection
probabilities are represented by P rj as the children of thevil , the average pointing time Tvil ,Tvil =n−1


P rj tlj ,

(16)

j=0

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,(l+1)(i = 0, · · · , n − 1)and let the results be vi

(l+1)

3) Placing Ii on the node vi
gives the minimum
average pointing time from node vil .
2) Optimization Problem: When menu items that areplaced as the children of a node V are given, the placementthat minimizes the average pointing time is straightforward.
Therefore, the problem is to find the best assignment of menu
items to nodes of a tree that minimizes Equation (15), where
nodes have a fixed capacity of W items. There should be atleast L = N/W  nodes in the tree, and N items placed onsome node. The first node has W items chosen from N 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

2008 IEEE Congress on Evolutionary Computation (CEC 2008)

L
N CW × N −W CW ×· · ·× N −LW CW = N !/(W !) ; therefore,

Permutation 1

Permutation 2

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 .

(10, 5, 11, 7, 1, 3, 2, 6, 4, 9, 8, 12)(1, 10, 3, 5, 11, 7, 2, 6, 4, 9, 8, 12)III. G ENETIC A LGORITHM

If we assign 7 to the root
node, then the root nodecannot have children, so
7 should be assign to anext level node.

7, 3, 2, 6

A. Basic Strategy
Previous studies showed that breadth was preferable todepth [9], [10], [14], [16], [17]. Schultz and Curran reported
that menu breadth was preferable to depth [14]. Larson andCzerwinski reported the results of depth and breadth tradeoff
issues in the design of GUIs [10]. Their results showed that,while increased depth did harm search performance on theweb, a medium condition of depth and breadth outperformed
the broadest shallow web structure overall.
Zaphiris studied the effect of depth and breadth in thearrangement of web link hierarchies on user preference,
response time, and errors [16]. He showed that previous
menu depth/breath tradeoff procedures applied to the web
link domain. He also showed that task completion timeincreased as the depth of the web site structure increased.
Zaphiris et al. also showed the results of the study investigating age-related differences as they relate to the depth
versus breadth tradeoff in hierarchical online information
systems [17]. They showed that shallow hierarchies werepreferred to deep hierarchies, and seniors were slower but
did not make more errors than their younger counterparts
when browsing web pages.
Because the previous studies showed that breadth waspreferable to depth, we use a kind of breadth-first searchalgorithm (shown later), as the core of the proposed GA.
B. Chromosome and Mapping from Genotype to Phenotype
A simple way to represent a solution of the problem is atree. But there is a problem that genetic operators such as
crossover or mutation may generate an infeasible solution;i.e., the tree does not contain all the generic functions. There
are two ways to cope with this problem. The first way is toconvert an infeasible solution into a feasible one and modify
the chromosome. The other way is to use a chromosome
representation that does not generate infeasible solutions. We
base the proposed algorithm on the latter approach.
Since breadth is preferable to depth, an algorithm thatplaces menu items Ii one by one on a usable node that has thesmallest node number can find a good solution. We number
each node from root to bottom, and from left to right. We
use an algorithm that assigns Ii to a node as follows:
1) A chromosome of the GA is a sequence of Ii ; i.e., achromosome can be represented as a permutation of
numbers.
2) According to the permutation, assign menu items Ii
one by one to vacant positions of the node that has thesmallest node number.
3) If a generic function is assigned to a node, then thenumber of children that the node can have is decreased
by 1.

1,10, 3, 5

10, 5, 11, 1

4, 9, 8, 12

Fig. 3.

11, 7, 2, 6

4, 9, 8, 12

Mapping a Permutation to a Tree Structure.

func1

func1
func3

func2

func2
root

root

func4
int1
func5
int2
func6

func4

int1

func5
func6

left: before local search
Fig. 4.

func3

right: after local search
Local Search.

If we have a sufficient number of intermediate nodes, we
can search enough space to find the optimal solution.
Two examples of assignment according to permutation are
depicted in Fig. 3, where W is 4. In the figure, numbers
in italic 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 node cannot have any children if wedid. Therefore, we should assign “7” to the next level node,and the remaining position of the root node should be anintermediate 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 weassign it to the root node, and the number of vacant positionsin the tree is incremented by 4. The next number “10” can be
assigned to the root node, and “3” and “5” can be assigned
to the root node. The remaining numbers are assigned to thechildren of the root nodes.
C. Local Search
We use a local search method to improve the performanceof GA. The method finds an unused node vil , i.e., finds anintermediate node that has no child, and swaps vil with a nodethat is the sibling’s child vjl+1 . Figure 4 shows an example ofthis procedure. In the left tree, the intermediate node “int2”
has no child, so it is swapped with “func3”, and the result
is the right part.
D. Crossover and Mutation
We use a crossover operator that does not generate aninvalid chromosome. As described above, a chromosome
is a permutation of numbers; therefore, we use crossover
operators that are developed for the representation. Based on

2008 IEEE Congress on Evolutionary Computation (CEC 2008)

2859

TABLE II NDEX OF D IFFICULTY FOR THE TARGET P HONE (24 KEYS )Fig. 5.

Key Layout of the Target Cellular Phone.

the results of preliminary experiments, we chose CX (Cycle
Crossover) for the crossover operator .
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.
E. 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
use a steady state GA, for which the population size is 100,and the mutation rate is one swap per chromosome.
IV. N UMERICAL E XPERIMENTS
We conducted numerical experiments to confirm the effectiveness of the proposed algorithm. The target was a cellular
phone that is used by one of the authors. The phone [8] has
24 keys as shown in Fig. 5.
The target phone has hardware keys for “E-mail”,“EZweb”, “Phone book”, and “Application”. And there isa “Shortcut”key (cursor down). The root menu thus has thefour submenus corresponding to the the hardware keys.
A. Experimental Data
1) Pointing Time and Decision Time: The index of difficulty for 24 × 24 key pairs was calculated as follows. We
measured the relative coordinates of the center (x, y) of eachkey and measured the width and height of each key. We
calculated the index of difficulty to an accuracy of one digit
after the decimal point. This gave us 28 groups of indexes ofdifficulty as shown in Table I. We named each key, from top
to bottom and left to right, as follows: “App”, “Up”, “Phonebook”, “Left”, “Center”, “Right”, “Mail”, “Down”, “Web”,“Call”, “Clear”, “Power”, “1”, thru “9”, “*”, “0”, and “#”.
We measured the pointing time of one-handed thumb users
for the above 28 groups by recording the tone producedby each key press [1]. There are two ways to measure
the pointing time. Silfverberg et al. measured the time bycounting the number of characters generated by key presses

2860

group
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

ID
3.7
3.6
3.5
3.4
3.3
3.2
3.1
3.0
2.9
2.8
2.7
2.6
2.5
2.4
2.3
2.2
2.1
2.0
1.9
1.8
1.7
1.6
1.4
1.3
1.2
1.1
0.8
0.0

example pairs
from
to
*
Up
0
Up
9
Up
8
Up
8
Right
9
Down
8
Down
6
Right
1
Up
8
Center
1
*
2
Right
1
9
1
0
1
3
2
Center
1
8
2
Call
1
7
Mail
Call
1
5
1
2
2
Clear
Right
Up
1
4
Center
Down
Right
Center
1
1

# of
pairs
2
3
6
8
17
22
25
28
29
29
33
29
29
53
33
20
25
17
21
7
50
16
9
12
21
4
4
24

in 10 seconds [13]. Amant et al. measured the time byrecording the tone produced by each key press [1]. Because
the target has keys that do not generate any character, suchas cursor keys, we measured the time by recording the tone.
Unpaid volunteers participated in the experiment. We
prepared 28 tasks corresponding to the 28 groups. The “Read
Email Message” function of the phone was used during
the tasks, except for the one task (ID=1.4, “2” to “Clear”).
For the exceptional case, the “write memo” function (withnumber mode selected) was used. The participants repeated
the task of pressing the “From” key and the “To” key 10times for each task. The pointing time was calculated bysubtracting the starting time of the tone of “From” from thestarting time of tone of “To.”
We got the following equation for predicting the pointing
time, and the equation is very similar to the one reported by
Silfvergerg et al. [13]1
tpi = 192 + 63 log2 (Ai /Wi + 1) (ms).

(17)

Although the target phone has the ability to select a menu
item by pressing a key that is prefixed to item title, we
assumed that all selections were done by cursor movements.
The target of this experiment was an expert; therefore, weused the following equation for the search/decision time [4]2 :ltsd
i = 80 log2 (n ) + 240 (ms).
1 tp = 176 + 64 log (A /W + 1) (ms).
ii
2i
2 The equation is derived from experiments

display, and is not for a cellular phone.

2008 IEEE Congress on Evolutionary Computation (CEC 2008)(18)

conducted for a computer

TABLE III MPROVEMENT IN AVERAGE SELECTION TIME .
Case
Original
Local Move
Case 1 (W =16)
Case 2 (W =12)
Case 2 (W =9)
Case 2 (W =6)

Tave (ms)
3331
2812
2036
1998
1959
2237

(%)
0.0
15.5
38.9
40.0
41.2
32.8

Ps
454
454
727
541
402
279

Pg
793
793
1259
856
291
173

Ps
584
405
402
396
395
397
405

Pg
448
278
291
300
309
274
260

TABLE IIIE FFECT OF WEIGHTS .
α
0.0
5.0
10.0
20.0
40.0
20.0
20.0

β
0.0
1.0
1.0
1.0
1.0
5.0
10.0

Tave (ms)
1837
1935
1959
1990
2066
2011
2028

(%)
44.9
41.9
41.2
40.3
38.0
39.6
39.1

2) Usage Frequency Data: We gathered usage frequency
data as follows. The first author recorded the daily usage ofeach function for two months, and we generated the usage
frequency data from the record. There were 129 terminal
nodes in the data.
3) Similarity: We assigned three to five words to eachgeneric function according to the users’ manual of the target
phone [8].
B. Results
We conducted the following experiments.
case 1 Typical Usage: This experiment was conducted toassess the typical improvement by the GA. The
maximum width W was 16.
case 2 Limited Breadth: Although breadth is preferable
to depth, pressing a far key or pressing a “Down”
key many times is sometimes tedious. This experiment was conducted to see the effects of limiting
the breadth. In this case, we set W to 12, 9, and 6.
Because GA is a stochastic algorithm, we conducted 50
runs for every test case, and the results shown in Table II and
Table III are averages over 50 runs. The two parameters forweights were set to α = 10.0 and β = 1.0. The maximum
number of fitness evaluations was 100,000.
In Table II, “Local Move” shows the results of a local modification that places menu items according to theirfrequency, i.e., the most frequently used item is placed as
the top item, and so on. As the table shows, the proposed
algorithm can generate menu with shorter average selection
time. Moreover, limiting the breadth give better menus. Thisis partly because the search/decision time is proportional tolog2 (n), where n is the number of items. As the number of
items increases, the search/decision time increases; therefore,
the average selection time increases. Limiting the breadth to
6 gave a longer selection time and smaller penalties.
The original menu (Tave =3331 (ms)) and the best menu
of Case 2 (9 keys) (Tave =1913 (ms)) are shown in Fig. 7 andFig. 8. In the two figures, items and intermediate nodes areshown in 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.
In Fig. 8, items with high usage frequency are placed ona smaller level and on an upper position. For example, themost frequently used “Inbox folder 2” which is placed underthe “Inbox” menu in the original menu, is placed as a childof “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”.
C. Effects of weights
We introduced two weights for the penalties of functional
similarity and of menu granularity. Table III shows the resultsof different weights settings for the case W = 9. The average
selection time increased as we increased α. The table also
shows that the difference in average selection time was larger
than that of the penalty factor of P s . Setting them to zero
gave a shorter selection time, but the penalties were larger.
There is a tradeoff among the average selection time, functional similarity, and menu granularity; therefore, a multiobjective approach might be a more natural formulation.
D. Convergence Speed
Figure 6 shows fitness, average selection time, and two
penalty terms in the best case (W = 9). GA found a fairly
good solution within 50,000 fitness evaluations. The penalty
term of “Functional Similarity” decreased almost monotonically, but the term of “Menu Granularity” oscillated in theearly stage. The average selection time initially decreased
rapidly, but sometimes increased in the middle of iteration
because of the penalty terms.
V. D ISCUSSION AND F UTURE W ORKThe experiments show that the proposed algorithm cangenerate better menu hierarchies for the target phone. Because our targets of are not limited to cellular phones, andthe preliminary results are promising, we will apply thealgorithm to wider varieties of targets such as Web browser
bookmarks.
In this paper, we focused on a static menu as the target;
adaptive/dynamic menu (e.g., [2], [3], [7]) that changes menu
contents depending on usage will be a future target.
The data used in the experiments, especially selection
frequency data, were limited. Therefore, we should gather
a wider variety of usage data and use that to confirm theeffectiveness of the proposed method.
VI. C ONCLUSION
We proposed a GA-based algorithm for minimizing the
average selection time of menu items that considers theuser’s pointer movement time and the decision time. The
preliminary results showed that the algorithm can generate abetter menu structure. The target of the proposed algorithm
is not limited to cellular phones.

2008 IEEE Congress on Evolutionary Computation (CEC 2008)2861

34000Fitness

33500

33000

32500

32000

31500
0

25000

50000

75000

100000

75000

100000Generation
2400
2350
Average Selection Time

2300
2250
2200
2150
2100
2050
2000
1950
1900
0

25000

50000
Generation

600

Functional Similarity
Menu Granularity

Average Selection Time550

[6] G. Francis and C. Rash, “MFDTool(version 1.3): a software tool
for optimizing hierarchical information on multifunction displays,”
USAARL Report No.2002-22, August 2002.
[7] L. Findlater and J. McGrenere, “A comparison of static, adaptive, andadaptable menus,” Proc. CHI 2004, pp.89–96, April 2004.
[8] KDDI: “Manual for CASIO W43CA,”
http://www.au.kddi.com/torisetsu/pdf/w43ca/w43ca torisetsu.pdf,
http://www.au.kddi.com/torisetsu/pdf/w43ca/w43ca kantan.pdf, 2006.
[9] J. I. Kiger, “The depth/breadth trade-off in the design of menudriven user interfaces,” Int. J. Man-Mach. Stud., vol.20, no.2, pp.201–
213,1984.
[10] K. Larson and M. Czerwinski, “Web page design: implication ofmemory, structure and scent for information retrieval,” Proc. CHI
1998, pp.25–32, 1998.
[11] B. Liu, G. Francis, and G. Salvendy, “ Applying models of visual
search to menu design,” Int. J. Human-Computer Studies, no.56,
pp.307–330, 2002.
[12] J.C. Quiroz, S.J. Louis, and S. M. Dascalu, “Interactive evolution of
XUL user interfaces,” Proc. of GECCO 2007, pp.2151–2158, 2007.
[13] M. Silfverberg, I.S. MacKenzie, and T. Kauppinen, “Predicting text
entry speed on mobile phones,” Proc. CHI 2000, pp.9–16, 2000.
[14] E.E. Schultz Jr. and P.S. Curran, “Menu structure and ordering of menu
selection: independent or interactive effects?,” SIGCHI Bull.,vol.18,
no.2, pp.69–71,1986.
[15] 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.
[16] P. Zaphiris, “Depth vs breadth in the arrangement of web links,” Proc.
44th Annual Meeting of the Human Factors and Ergonomics Society,pp.139–144, 2000.
[17] P. Zaphiris, S.H. Kurniawan, and R.D. Ellis, “Age related difference
and the depth vs. breadth tradeoffs in hierarchical online information
systems,” Proc. User Interfaces for All, LNCS 2615, pp. 23–42, 2003.
[18] M. Ziefle and S. Bay, “Mental models of a cellular phone menu.
Comparing older and younger novice users,” Proc. MobileHCI 2004,
LNCS 3160, pp.25–37, 2004.

500
450
400
350
300
0

25000

50000

75000

100000Generation

Fig. 6.

Fitness, Average selection time, Penalty terms.

ACKNOWLEDGMENTS
The authors would like to thank Dr. Fujio Tsutsumi of
CRIEPI for his valuable comments.
R EFERENCES[1] St. Amant, T.E. Horton, and F.E. Ritter, “Model-based evaluation ofcell phone menu interaction,” Proc. CHI 2004, pp.343–350, 2004.
[2] D. Ahlström,“Modeling and improving selection in cascading pulldown menus using Fitts’ law, the steering law and force fields,” Proc.
CHI 2005, pp.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, vol.20, no.3, pp.233–245, 2006.
[4] A. Cockburn, G. Gutwin, and S. Greenberg, “A predictive model ofmenu performance,” Proc. CHI 2007, pp.627–636, 2007.
[5] G. Francis, “Designing multifunction displays: an optimization approach,” Int. J. of Cognitive Ergonomics, vol.4, no.2, pp.107–124,
2000.

2862

2008 IEEE Congress on Evolutionary Computation (CEC 2008)

Folder1

Folder2

Folder2

Folder5

Folder3

Folder3

Folder4
Folder5

Check,New,Mail

Inbox
Check,Mail,New

Folder1

INT1
E-MailFolder0

E-MailINT2
Folder0
Folder4

URL1-2

URL1-6

URL1-3

URL1-3

URL1-4

URL1-4

URL1-5

URL1-11

URL1-6

Shortcut

URL1-7
Folder1

URL1-2
URL1-9

URL1-5

URL1-7

URL1-13

URL1-10

URL1-12

URL1-8

URL1-11

FOLDER1

URL1-8
URL1-9

URL1-12

URL1-10root

URL1-13FOLDER2

Folder2

FOLDER3
Folder3

EZWeb

Favorite Site
root

EZweb
Application

Application

Shortcut

Fig. 7.

Original Hierarchical Menu.

Fig. 8.

Example of an Optimized Menu (W = 9).

2008 IEEE Congress on Evolutionary Computation (CEC 2008)

2863