Multi-factor user interface components layout problem with genetic algorithm.
Sharma, Dinesh K. ; Peer, S.K.
INTRODUCTION
The well-designed user interface makes an interactive system
effective enabling user to concentrate on their work, exploration, or
pleasure. The ability to perform routine activities quickly,
effortlessly, and without conscious awareness is called automaticity
(Logan, 1988). Automaticity is relevant and important construct for the
study of human-computer interaction in general and for the study of
direct manipulation of interfaces in particular. Some studies show that
the total time required to complete the task is a direct manipulation
interface will be less than in a menu based interface (Lim et al.,
1996).
Within the computer science, there is a growing awareness of the
need for great attention to human factors issues. The business cases for
human factors in computer and information systems are strong as
demonstrated by many successful products whose advantage lay in their
superior user interface. There is a one-to-one relationship between the
facilities layout problem in a manufacturing plant and the user
interface components layout problem in human-computer interface design
(Peer et al., 2004). The quadratic assignment problem (QAP) formulation
for assigning 'n' facilities to 'n' mutually
exclusive locations is the most typical model used in manufacturing or
interactive service systems.
A classical QAP is formulated handling qualitative (subjective)
factor(s) and quantitative (objective) factor(s) to obtain the layouts,
using construction procedure or improvement procedure. The
multi-criteria facilities layout model handles a number of criteria
values associated in the multiple qualitative and quantitative factors
with the objective function of the quadratic assignment problem (QAP).
Harmonosky and Tothero (1992) presented a quadratic assignment model to
handle the multiple qualitative and quantitative factors in the same
manner when applying them into the objective function. Then, a
construction procedure was proposed, in which the pair of facilities
with least composite criterion value is selected to place far apart in
the layout to obtain the initial layouts. The resulting initial layouts
may be improved further by using the improvement procedures. Peer et al.
(2003) used the multi-factor facilities layout model of Sharma and Peer
(2005) in which multiple qualitative and quantitative factors were
handled in different manner separately to obtain the alternate layouts
of the user interface components of the example task under
consideration. Then, the search techniques such as simulated annealing
(Suresh and Sahu, 1993), ant colony optimization technique (Baykasoglu,
2006), genetic algorithm, etc. are used to obtain the best layouts.
Good heuristic techniques are necessary to obtain the best layouts
due to its high computational complexity. Modern heuristic techniques,
namely genetic algorithms (Goldberg, 1989; Michalewicz, 1996), taboo
search (Kaku and Mazzola, 1997), simulated annealing (Baykasoglu and
Gindy, 2001) and ant colony optimization (Baykasoglu et al., 2006), can
be good candidates for this problem. Genetic algorithms (GAs) have been
applied extensively to solve many real-world problems. Conway and
Venkataramanan (1994) examined the suitability of genetic algorithm for
the dynamic layout problem (DLP). Tate and Smith (1995) used a GA to
solve QAP. Suresh et al. (1995) also proposed a GA for obtaining
efficient layouts. Balakrishnan and Cheng (2000) presented a GA for DLP.
Deb et al. (2001) and Deb and Bhattacharyya (2003, 2005) applied GA and
simulated annealing for a facility layout problem (FLP).
In this paper, we present a genetic algorithm approach to obtain
the best layout from the population of the initial layouts of the
multi-factor user interface components layout problem for the example
task under consideration as given in Peer et al. (2003). Then, the final
layouts are compared with that of the improvement procedure for the
reported case under consideration.
The paper is organized into 5 sections. Section 2 presents the
solution procedure of genetic algorithm. The resulting layouts obtained
from the population of initial layouts of the user interface components
layout problem for the example task are presented in section 3. Section
4 reports the computational results and the paper ends with conclusions
in section 5.
SOLUTION PROCEDURE OF GENETIC ALGORITHM
Genetic search technique works with coding variables, since the
coding of variable space discretizes the continuous search space
(Rajasekharan and Pai, 2005). It uses population of points at one time,
which means that it processes number of designs at the same time. It
consists of randomized operators, rather deterministic transition rules
used in traditional optimization methods.
Genetic search technique starts with a set of solutions called
population. The solutions of this population are used to form a new
population with better solution based on their fitness. This procedure
is repeated until the conditions for improvement of best solution are
satisfied. The members in population may be represented by string bits,
arrays, trees, lists or any other valid data structure form. In order to
make use of the fundamental theorem of genetic algorithms, the data
structure of string bits representing the member of population is used
(Conway and Venkataramanan, 1994).
Reproduction operator is used to select chromosomes or parent from
population. The various methods are used to select parent chromosomes,
such as roulette wheel selection, Boltzmann selection, Tournament
selection, Rank selection, and steady-state selection. Reproduction
makes clones of good strings, but does not create new ones.
Then, crossover operator is applied to the mating pool to create
better string by preserving the information of parent strings. Crossover
proceeds in three steps. First, the reproduction operator selects a
random pair of two individual strings for mating, then a cross-site is
selected at random along the string length and the position values are
swapped between two strings. The crossover rate is the probability of
cross over ([p.sub.c]), which varies from 0 to 1. It is the ratio of the
number of pairs to be crossed to some fixed population. If good strings
are not created by crossover, they will not survive too long, because
reproduction will select against those strings in subsequence
generations. That is, the effect of crossover may either be detrimental
or beneficial all the strings in mating pool are not used in crossover,
in order to preserve some of good strings. When the crossover
probability is [p.sub.c], their 100 [p.sub.c] percent strings in the
population are used in the crossover operation.
Finally, mutation is used to modify errors in strings caused in the
previous operations. The mutation operator introduces new genetic
structure in the population randomly modifying some of its building
blocks. The bit-wise mutation is performed bit-by-bit by flipping a coin
with a probability of [p.sub.m]. A number between 0 and 1 is chosen at
random. If the random number is smaller than [p.sub.m], then the outcome
of coin slipping is true, otherwise the outcome is false. If at any bit,
the outcome in true then the bit is altered, otherwise the bit is kept
unchanged. The bits of the strings are independently muted. That is, the
mutation of bit does not affect the probability of mutation of other
bits. Mutation rate is the probability of mutation ([p.sub.m]), which is
used to calculate number of bits to be muted.
The next section of the paper presents the example task under
consideration for the user interface components layout problem and its
resulting layouts.
LAYOUTS OF USER INTERFACE COMPONENTS
There is much literature available, using the facilities layouts
models for the user interface components layout problem (Peer and
Sharma, 2004; Sharma, Peer and Alade, 2005; Peer et al., 2004). It is
involved with the application of construction/improvement procedures to
obtain the layouts of user interface components for the example task
under consideration. In order to obtain the best layout, it is required
to use the search techniques. In this section, genetic search technique
is used to improve the solution of layouts obtained with the
construction procedure for the multi-factor user interface components
layout problem using the Peer and Sharma (2005) model as given in
equations (1) through (4).
Minimize [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)
Subject to: [n.summation over (i=1)] [X.sub.ij] = 1,
j = 1, 2, ..., n (2)
[n.summation over (j=1)] [X.sub.ij] = 1,
i = 1, 2, ..., n (3)
[X.sub.ij] = 0 or 1, [for all] i, j (4)
[R.sub.ik] = [u.summation over (p=1)][[beta].sub.p][R.sub.ikp],
[for all] i, k
Where
[F.sub.ik] = [w.summation over (q=1)][[gamma].sub.q][F.sub.ikq],
[for all]i, k
[[beta].sub.p] = Weight assigned to qualitative factor p
[[gamma].sub.q] = Weight assigned to quantitative factor q
[R.sub.ikp] = Normalized relationship value between components i
and k for factor p
[F.sub.ikq] = Normalized relationship value between components i
and k for factor q
[R.sub.ik] = Combined qualitative factor
[F.sub.ik] = Combined quantitative factor
u = number of qualitative factors
w = number of quantitative factors
n = number of components
i and k indices for components numbers, and j and l are indices for
location numbers.
The combined qualitative factor ([R.sub.ik]), combined quantitative
factor ([F.sub.ik]), composite factor ([A.sub.ik] = [W.sub.1] [R.sub.ik]
+ [W.sub.2] [F.sub.ik]) obtained for [W.sub.1] = 0.2 and [W.sub.2] = 0.8
and the distances ([d.sub.j1]) between locating j and l are given as
shown in the Figure1, for the example task presented in Sharma, Peer and
Alade (2003).
[FIGURE 1 OMITTED]
A sample of 10 layouts and their scores obtained using construction
procedure are given as shown in Figure 2.
In order to apply the fundamental theorem of genetic algorithm, the
data structure (string) representing the member of the population is
defined because of the following reasons (Conway and Venkataramanan,
1994). (1) The objective value of the feasible objective function can
easily be calculated for the string chosen to crossbreed. (2) The first
period layout is related to the second period layout by way of
changeover cost and within by layout quality. That is, any element of
the string is related only to its immediate layout and the two
surrounding layouts. (3) Schema, or sub-strings, which are short, low
order, and have an average fitness will be expected to survive.
Let the string representing the member of the population P is m, n
is the number of components. Then P = [a.sub.11] [a.sub.21] [a.sub.31]
... [a.sub.n1] [b.sub.12] [b.sub.22] ... [b.sub.n2] ... [P.sub.1n]
[P.sub.2n] ... [P.sub.nn] where [a.sub.j1] is the component number in
the location j of population number 1, [b.sub.j2] is the component
number in location j of population number 2 and [P.sub.jm] is the
component number in location j of population number m. The strings are
separated by one place leaving the schema (sub-string) together. For
n=4, m=3, P=2413 4132 3214 is interpreted as component 2 is in location
1 in the population number 1 and so on.
The population size of 10 layouts of user interface components
layouts with 6 components as shown in Figure 2 is considered for the
application of GA search technique to obtain the final layout. Each
layout of 6 components is represented as a string of 6 decimal digits as
follows.
236145 532416 432516 346125 156324
526134 256143 641235 132645 351462
Reproduction operator is used on population to select the
chromosomes for parents to crossover. It is performed with Roulette
wheel selection method (Rajasekaran and Pai, 2005) to choose the strings
of feasible solution as chromosomes. Thus, the pair of strings is
selected from the population according to the distribution of the
relative strength of the strings to the entire strength of the
population.
Then, a cross-site is selected at random along string length and
the strings are split as follows.
236145 532416 432 516 346125 156324
526134 256143 641 235 132645 351462
Next, the sub-strings to the visit of cross-site are swapped as
follows.
236145 532416 432 ab5 132645 351462
526134 256143 c4d 516 346125 156324
Since the cross-site selected for split of the string is the middle
of a single period layout, the stronger of the two strings regains the
partial layout and the weaker fills in the unassigned component
positions, which correspond and are feasible (Conway and Venkataramanan,
1994). Remaining positions are filled by unassigned components which
correspond to their neighboring feasible layouts and then by randomly.
Hence, the 'a' becomes a 6 because the period has a 6 in the
fourth position, which forces the 'b' to become a 1. The 4 is
carried from weaker string to get feasible solution. Similarly, the
'c' becomes 3 because the period has a 3 in the first
position, which forces the 'd' to become 2 and resulting
strings of the population are obtained as follows.
236145 532416 432615 132645 351462
526134 256143 342516 346125 156324
Decimal digits are used to represent the strings in population and
hence, the use of mutation operation does not guarantee the feasible
solution.
Finally, the scores of the layouts in the population are computed
and compared with the least initial score of the layout, in order to
determine the improved layout after the first generation. The basic
steps involved in genetic search technique for the multi-factor user
interface components layout problem are given in Figure 3. The genetic
search technique is repeated for 50 generations and the score of the
final layout is obtained as follows.
[ILLUSTRATION OMITTED]
The percentage of improvement over the least initial layout score
of construction procedure is computed as shown in Figure 4.
[FIGURE 3 OMITTED]
The genetic search technique is used to obtain the best layout for
the populations of construction procedure for different combinations of
weights and compared as given in Table 1. From the results, it is
observed that the solution obtained with genetic search technique is
improved by an average 3.92 percent whereas the same is improved by an
average 2.30 percent with improvement procedure.
COMPUTATIONAL RESULTS
Genetic algorithm is used to evolve the population of initial
solution into optimal solution. In this paper, genetic search technique
is used to obtain the best final layouts from the initial population of
construction procedure for the user interface components layout problem
of 2 by 3 as given in Sharma, Peer and Alade (2003). For each
combination of weights W1 and W2, the population size of 10 layouts is
obtained with construction procedure. The generic search technique is
used for 50 generations to obtain the best layout. The layout obtained
with each generation is compared with that of the least score layout
obtained with the construction procedure. The score of the final layout
obtained with genetic search technique is compared with the least score
layout of construct procedure for all the combinations of weights W1 and
W2 assigned to combined qualitative factor and combined quantitative
factor. It is observed form the results that the solution obtained with
genetic search technique is improved by an average 3.92 percent, whereas
the same is improved by an average 2.30 percent with improvement
procedure. The 'C' program of genetic search technique for
this problem is run on the P-IV system.
CONCLUSIONS
Genetic algorithm is used efficiently to evolve the population of
initial solutions into near optimal solution, once the data structure of
solution is chosen so that the fundamental theorem of genetic algorithm
can be applied. The structure of genetic algorithm is exploited to use
it in parallel processing. This technique is found to be best suited to
evaluate the obtained solution from the initial population of solutions,
and hence the best solution is guaranteed compared to the heuristic
procedure such as improvement procedure of the layout problems that uses
one solution to improve it further. Since, large number of solutions may
be obtained for the different combination of weights W1 and W2 with
genetic search technique; this problem could easily be extended to
interface with a decision support system.
REFERENCES
Balakrishnan, J. & C.H. Cheng (2000). Genetic search and the
dynamic layout problem. Computers & Operations, Research, 27(6),
587-593
Baykasoglu, A. & N.N.Z. Gindy (2001). A simulated annealing
algorithm for dynamic layout problem. Computers & Operations
Research, 28,1403-1426.
Baykasoglu, A., T. Dereli & I. Sabuncu (2006). An ant colony
algorithm for solving budget constrained and unconstrained dynamic
facility layout problems. Omega, 34, 385-396
Conway, D.G. & M.A. Venkataramanan (1994). Genetic search and
the Dynamic facility layout problem. Computers & Operations
Research, 21(8), 955-960.
Deb, S.K., B. Bhattacharyya & S.K. Sorkhel (2001). Hybrid
genetic algorithm for facility layout design under manufacturing
environment. Proceedings of the International Conference on Operational
Research, Kolkata, India, 56-68.
Deb, S.K. & B. Bhattacharyya (2003). Manufacturing facility
layout design based on simulated annealing. Proceedings of the National
Conference on Advances in Manufacturing Systems, Kolkata, India,
117-122.
Deb, S.K. & B. Bhattacharyya (2005). Solution of facility
layout problems with pickup/drop-off locations using random search
techniques. International Journal of Production Research, 43(22),
4787-4812.
Goldberg, D.E. (1989). Algorithms and search optimization and
machine learning (Reading MA: Addison-Wesley). Harmonosky, C.M. &
G.K. Tothero (1992). A multi-factor plant layout methodology.
International Journal of Production Research 30(8), 1773-1789.
Kaku, B.K. & J.B. Mazzola (1997). A tabu search heuristic for
the dynamic plant layout problem. INFORMS: Journal on Computing, 9,
374-84.
Lim, K.H., I. Benbasat & P.A. Todd (1996). An experimental
investigation of the interactive effects of interface style,
instructions, and task familiarity on user performance. ACM Transactions
on Computer-Human Interaction. 3(1), 1-37.
Logan, G. D. (1988). Automaticity, resources and memory:
theoretical controversies and practical implications. Human Factors,
30(5), 583-598.
Michalewicz, Z. (1996). Genetic algorithms + data structures =
evolution programs (Third Edition), Springer-Verlag.
Peer, S.K. & Dinesh K. Sharma (2004). Single objective layout
design of user interface components with multiple qualitative factors.
International Journal of Applied Mathematics and Computing, 14(1-2),
353-363.
Peer, S.K., D.K. Sharma, K. Ravindranath & M. M. Naidu (2004).
Layout design of user interface components with multiple objectives.
Yugoslav Journal of Operations Research, 14 (2), 171-192.
Rajasekaran, S. & G.A.V. Pai (2005). Neural works, fuzzy logic
and genetic algorithms: synthesis and applications. Prentice Hall India
Ltd., Publisher.
Sharma, Dinesh K., S.K. Peer & Hari P. Sharma (2005). Quadratic
assignment formulation for the multi-factor facilities layout problem.
International Journal of Modelling and Simulation. 25(1), 57-66.
Sharma, Dinesh K., S.K. Peer & Julius A. Alade (2003). A multi
factor user interface components layout problem. Journal of Business and
Economics Research, 1(10), 81-92.
Suresh, G. & S. Sahu (1993). Multi objective facility layout
using simulated annealing. International Journal of Production
Economics, 32, 239-254.
Suresh, G., V.V. Vinod & S. Sahu (1995). A genetic algorithm
for facility layout. International Journal of Production Research, 33,
3411-3423.
Tate, D.M. & A.E. Smith (1995). A genetic approach to the
quadratic assignment problem. Computers & Operations Research,
22,73-83.
Dinesh K. Sharma, University of Maryland Eastern Shore
S.K. Peer, K.L.M. College of Engineering for Women
Table 1: Comparison of Results of Genetic Search
Technique with Construction Procedure: Area limited
to 2 rows and 3 columns
Weight Construction Improvement
procedure procedure
[W.sub.1] [W.sub.2] Layout Score Layout Score
0.0 1.0 [5] [4] [3] 2.255 [4] [1] [2] 2.241
[1] [6] [2] [6] [5] [3]
0.2 0.8 [2] [3] [6] 2.319 [3] [6] [5] 2.282
[1] [4] [5] [2] [4] [1]
0.4 0.6 [3] [1] [4] 2.241 [5] [4] [1] 2.225
[5] [2] [6] [3] [6] [2]
0.5 0.5 [4] [6] [5] 2.293 [2] [6] [1] 2.259
[1] [2] [3] [3] [5] [4]
0.6 0.4 [2] [5] [4] 2.317 [5] [4] [1] 2.234
[3] [1] [6] [3] [6] [2]
0.8 0.2 [2] [3] [4] 2.318 [2] [6] [1] 2.234
[6] [1] [5] [3] [5] [4]
1.0 0.0 [3] [2] [1] 2.326 [4] [1] [2] 2.222
[6] [5] [4] [5] [6] [3]
Avg. improved (%)
Weight Improvement Genetic search
procedure technique
[W.sub.1] [W.sub.2] Improvement Layout Score
over
construction
procedure (%)
0.0 1.0 0.62 [1] [2] [5] 2.213
[4] [6] [3]
0.2 0.8 1.60 [6] [4] [3] 2.252
[1] [5] [2]
0.4 0.6 0.71 [5] [2] [3] 2.217
[1] [6] [4]
0.5 0.5 1.48 [2] [6] [1] 2.233
[3] [4] [5]
0.6 0.4 3.58 [5] [4] [3] 2.219
[1] [6] [2]
0.8 0.2 3.62 [4] [5] [1] 2.227
[3] [6] [2]
1.0 0.0 4.47 [1] [6] [2] 2.088
[5] [4] [3]
2.30 Avg. improved (%)
Weight Genetic search
technique
[W.sub.1] [W.sub.2] Improvement
over
construction
procedure (%)
0.0 1.0 2.52
0.2 0.8 2.80
0.4 0.6 1.10
0.5 0.5 2.62
0.6 0.4 4.23
0.8 0.2 3.93
1.0 0.0 10.23
3.92
Figure 2: Layouts and Scores obtained with construction procedure
for the user interface components layout problem.
Layouts Scores
2 3 6 2.319
1 4 5
5 3 2 2.326
4 1 6
5 6 4 2.342
1 3 2
6 1 5 2.365
2 3 4
6 3 2 2.441
5 1 4
4 3 5 2.353
2 6 1
1 3 2 2.352
5 4 6
2 4 1 2.329
6 3 5
5 4 3 2.354
1 6 2
2 6 5 2.321
4 3 1
Figure 4: Percentage of improvement with genetic search technique
over construction procedure for [W.sub.1] = 0.2 and [W.sub.2] = 0.8
Construction procedure Genetic Search technique Improvement (%)
Layout Score Layout Score
5 3 2 2.316 6 4 3 2.252 2.8
4 1 6 1 5 2
