Web optimisation with
genetic algorithms
Introduction
In this research project we will be investigating the use of genetic algorithms to optimise interactions on a website, specifically where best to place a call-to-action (CTA) button on an image.
Why CTA? The $300m button
An old story, widely shared in the UX community, is that of the $300m button.
In the early 2000s, a large e-commerce site (probably Amazon, but no-one is telling!) conducted a usability study on the placement of their checkout button. The test was really simple: how many people clicked on the button in its new position, compared to how many people clicked on the button in its old position.
The results were startling: the increase in traffic through the new button placement the study demonstrated that $300 million in revenue had been missed, simply because the old button was in the 'wrong' place!
Presentation
First of all check out the presentation to get an idea of what we are researching. In this presentation we give a short introduction to genetic algorithms and how we'd use them in a web setting.
As you'll see from the presentation, the problem space has the following components:
- Identifying our organisms: what are we evolving? In our case, the basic organism is an image with a button placed on it - which we will call the Call-to-Action Organism.
- Identifying candidate attributes: what attributes of an organism can be evolved? In our case, the attributes are the position, size, shape, text and styling attributes of the button.
- Encoding attributes: once we have identified the attributes, how do we encode them as genes in a way that is amenable to evolution?
- Fitness: in order to evolve, the organisms need to be tested against a fitness function - what is that test? In our case, the test is easily defined: click through rate (CTR).
- Breeding: once we have a selected our fittest organisms we breed randomly chosen pairs to create new pairs of organisms. We will also introduce random mutations in order to promote innovation.
- Ending the evolution: when do we decide we have the optimal organism? This can be after a set number of generations, or in our case, a continuing cycle of improvement.
Terminology
Given the above summary, we will use the following terms:
| Term | Definition | Example |
|---|---|---|
| Organism | The class of objects we are evolving | An image with a button superimposed on it |
| Attribute | The qualities of an organism we changing from generation to generation | The fill colour of the button |
| Gene | The encoding of an attribute as a binary representation | Fill colour can be encoded as 24 digit string of 0s and 1s |
| Bit | A 0 or 1 in a gene | 11111000110 |
| Genome | The complete set of an organism's attributes encoded as genes | A 1024 digit string of 0s and 1s |
| Expression | The translation of a gene into the value of an attribute | The gene encoded as 1111 1111 0000 0000 0000 0000 is expressed as the fill colour red |
| Environment | The landscape the organism lives in | A web page designed for people to identify a CTA and click through |
| Constraint | Attributes that are dependent on other attributes or aspects of the environment | Text colour needs to contrast against the colour of its background |
| Viability | The ability of an organism to survive in an environment | A web page is constrained by typography choice and illustration style; a CTA organism that doesn't abide by these constraints isn't considered |
The algorithm
Now we have defined the problem and terminology, our solution - the genetic algorithm - proceeds as follows:
Generation 1
In the first generation we create 1000 organisms, with randomly chosen attributes encoded in binary representations.
Generation n: step 1, select using fitness function
Our fitness function is click-through rate (CTR), so we simply count the number of click-throughs on each button.
After a set number of total click-throughs, we select the top 500 organisms (measured by CTR), and discard the rest. These 500 organisms can be thought of as the selected parents of generation n.
Generation n: step 2, breeding the fittest parents to create offspring
Breeding is through a combination of crossover of pairs of selected parents to create new offspring that inherit characteristics of both parents. These offspring are then given slight mutations to promote innovation.
Crossover
For crossover we take a random pair of parents and "crossover" their genomes:
- We choose a random point to split each parent's genome
- We then swap the ends of the genomes beyond the split point to create two new offspring
- The offspring will replace the 500 organisms we discarded
Mutation
In addition to crossover, we want to introduce a random element of mutation; this is so that there is a chance that innovation can occur - otherwise we may be in danger of shuffling attributes rather than evolving them.
- We choose a random bit (a 0 or 1) in the genome of an offspring
- We 'flip the bit' - if it's a 1 we flip it to a 0 and vice versa
- We replace the old offspring with our slightly mutated offspring
At the end of the selection, crossover and mutation processes, we will have 1000 organisms in generation n: the fittest 500 parents from generation n-1, and 500 offspring with slightly mutated genomes derived from these parents.
Loop to generation n+1 or End?
We then loop this process for as many generations as we wish. Choosing when to end the looping is an optimisation problem in itself, and there are a couple of methods available:
- Identifying consistently high performing organisms: this can be as simple as percentage of total click-throughs
- Choosing an arbitrary number of generations
- Choosing an arbitrary number of total click-throughs over the entire experiment (e.g. whatever number of generations gives us 1m click-throughs, for example)