We deal in this work with the problem of automatically generating the style and the layout of web pages and web sites in a real world application where many web sites are considered. One of the main difficulty is to take into account the user preferences which are crucial in web sites design. We propose the use of an interactive genetic algorithm which generates solutions (styles, layouts) and which lets the user select the solutions that he favors according to their graphical representation. Two encoding have been defined for this problem, one linear and fixed length encoding for representing the style, and one variable length encoding based on HTML tables syntax for the layout.
web site design, style, layout, interactive optimization, genetic algorithms
One current issue in web sites design consists in finding an aesthetic looking. We concentrate in this study on the optimization of the site's style, i.e. text and background colors, fonts, etc, and on the optimization of the layout, i.e. the position of the different texts or images on a page. If we assume that the user is not a computer scientist, and that he needs an automatic tool to make him valuable creative suggestions in order to personalize his site, then standard editors can be useless because they fail to catch the user preferences.
We propose the use of an interactive genetic algorithm (IGA) (Dawkins 1986) (Herdy 1997) (Venturini et al. 1997) (see a survey in (Lewis 2000) or in (Takagi 2001)). IGAs are an extended version of genetic algorithms (Holland 1975) where the evaluation is performed by the user. Our algorithm works as follows: 1) it generates solutions (i.e. styles or layouts) called individuals, 2) it lets the user select the individuals that he favors based on their graphical representations, 3) it generates the next population of individuals with a crossover and a mutation operator. In this way, the user drives in an intuitive and interactive manner the genetic search towards satisfying styles or layouts.
Figure 1: Screen shot of an initial population obtained when optimizing the layout of a given web site.
The optimization of the style and the layout are done separately, with different genetic representations of individuals and different operators, but both make use of the same generic IGA. This algorithm consists in the following steps:
Randomly generate an initial population of N individuals (or possibly use an existing style/layout as an initial individual),
Display the individuals (see for instance figure 1),
Possibly Stop if the user is completely satisfied,
Select individual(s) with check boxes,
Generate a new population: keep the Nselect checked individuals for the next generation, discard the others and replace them with newly generated individuals using crossover and mutation.
Go to step 2.
The population size N has been limited to 12 because it is important to display all the individuals on the same screen.
Gene |
Description |
Values |
Color1 | color of the menu's text | (R, G, B) Î [0,255]3 |
Color2 | background color of menu | (R, G, B) Î [0,255]3 |
Color3 | first possible color of text | (R, G, B) Î [0,255]3 |
Color4 | background color for Color3 | (R, G, B) Î [0,255]3 |
Color5 | second possible color of text | (R, G, B) Î [0,255]3 |
Color6 | background color for Color5 | (R, G, B) Î [0,255]3 |
Font | font for page's texts | 9 fonts |
Size | font size | [1,4] |
Bold | style for page's texts | yes/no |
Italic | '' | yes/no |
Underlined | '' | yes/no |
Alignment | '' | centered/left/right |
Bullet | paragraphs start with a bullet | yes/no |
Borders | borders around images | yes/no |
Table 1: The 14 genes which encode the style of a page or site.
We have represented in table 1 the 14 genes that are used to encode the style of a page or site. The random generation of an individual consists in randomly choosing a value for each gene within its set of values. The mutation consists in modifying each gene g with a probability Pmut. The crossover operator is a uniform crossover (Syswerda 1989) which generates one offspring D by randomly choosing each gene values of D either from one parent or the other with a probability of 0.5. We eliminate individuals with similar colors for text and background.
We consider that the user wants to define a page layout for n objects denoted by O1, ..., On that can be images or texts. The layout of a page is represented by an n ×3 HTML table with a variable number of cells, where each cell may have different dimensions and may possibly contain up to 3 objects, and by other genes like cell background colors (chosen among the colors defined previously), objects vertical and horizontal alignments. Since cells can be merged together, a very important variety of layouts can be generated with such a representation (all tables included in a n ×3 table). Two types of constraints apply to this representation:
table constraints: the cells must represent a correct HTML table,
objects/cells constraints: if a cell contains 1, 2 or 3 objects then these objects must be either one text, one image, an image and a text, or two images and a text. In this way, the genetic representation may encode the fact that a text is wrapped around one or two images.
The random generation of an individual consists in randomly placing the n objects in the n ×3 HTML table with randomly generated alignments, colors, etc. Then, randomly selected cells are merged together. The mutation operator consists in regenerating randomly the object location within the n ×3 HTML table, as well as other genes like alignment, color, etc. The crossover operator generates one individual from two parents: it places the objects at a location given either by one parent or the other, and handles the other genes in a similar way. With all these operators, generated individuals do necessarily respect the constraints.
|
|
|
|
|
|
Figure 2: Typical results obtained with 2 texts and 3 images. This illustrates the variety of styles/layouts which can be generated with our tool.
The system described in this paper has been integrated in a large scale software for web sites hosting. When one of the many users wants to define or modify the style/layout characteristics of his site (or of a given page), he may use the IGA among the other possible options (manual edition, predefined models) through his browser's window. This represents one of the first real world application of IGAs (see also (Herdy 1997)). Many different kinds of styles/layouts can be generated according to the user preferences (figure 2).
We have analyzed 51 sessions on a demonstration site. The mean length of a session is 9 minutes (with standard deviation of 11 minutes due to the fact that the user may sometime go away from his computer). The mean number of generations for style and layout optimization are respectively 7.2 and 6.1. The average time needed from one generation to the next one is 48.9 seconds (including network latency, page display and user's evaluation). These data confirm that this tool is intuitive and easy to use because it allows the user to find satisfying results in few minutes.
Several perspectives can be derived from this work like dealing with other kind of electronic documents (from word processors, presentation editors, etc) or like taking into account the possible dependencies that may exist between elements (like for instance, this text must be close to this image and far from this other text).
