Organising a Colour Palette
Colour Models
Colours used in computer graphics are based on a particular model. The model
you pick depends on the range of colours you need in a graphic and whether it is
going to be output to print media or to screen. There are various colour models
available. Some examples are: Black & White, Grayscale, RGB (Red, Green and
Blue), CMYK (Cyan, Magenta, Yellow and Black), and HSB (Hue, Saturation &
Brightness)
In this assignment, we will consider the RGB (Links to an external site.) model. Red,
green, and blue can be combined in various proportions to obtain any colour in the
visible spectrum. In our representation R, G, B can each range from 0 to 1. Where 0
indicates absence and 1 full intensity.
Dataset
You have given 3 datasets with increasing size to support your implementation and
testing:
• 10 colours: col10.txt
• 100 colours: col100.txt
• 500 colours: col500.txt
The files contain rows of three floating-point values. Each row represents a colour
by its red, green, blue coordinates. The first uncommented line is the number of
colours.
You are also given a Python notebook with useful code: colour_startup.ipynb
This notebook includes the code to read the datafile and visualise a sequence of
colours. It also contains some other useful functions to support your assignment.
Solution Representation
To solve this problem, your implementation should encode a candidate solution as
an ordering of indices, not as an ordering of the colours themselves.
To clarify this, let us assume that your dataset has 5 colours (each colour
represented with its RGB coordinates) and it is stored in a list called c. An ordering
of the colours (i.e a candidate solution to your problem) should be encoded as a list
of indices of length 5, where each element in the list is an index in the c list.
For example, a solution encoded as e s = [1, 0, 2, 4, 3], represents the following
ordering of colours c[1] c[0] c[2] c[4] c[3].
What do you need to do?
Your task is to provide a more aesthetically pleasing ordering of a list of colours.
To illustrate what we mean, consider the colour bands in the figure below. The top
band shows an unordered set of colours, while the 2nd and 3rd bands have been
ordered by different algorithms. You can clearly notice the difference between an
arbitrary ordering and an improved ordering.
To complete your task, you are asked to implement 3 different algorithms.
1. Multi-start hill-climbing algorithm
2. Clustering-based algorithm
3. Algorithm of your choice
Below more details for the implementation of each algorithm
1. Multi-start hill-climbing algorithm
How can we formulate this problem as an optimisation problem? One possibility is
to search for an ordering of the given colours where adjacent colours are somewhat
similar. This can be achieved by finding an ordering of colours that minimises the
sum of the distances between adjacent colours, where the distance between two
adjacent colours is computed with the Euclidean distance. This will be the objective
function to evaluate solutions (called evaluate). To facilitate your work, we provide
the implementation of this function, in the given Jupyter
notebook: colour_startup.ipynb
You do not need to implement the function as it is provided. Here an explanation of
what the function does: it computes the sum of the Euclidean distances, between
all pairs of adjacent colours. For example, for a 5 colours list c and the solution s =
[1, 0, 2, 4, 3], and assuming d() is the Euclidean distance, the evaluation function
returns d(c[1], c[0]) + d(c[0], c[2]) + d(c[2], c[4]) + d(c[4], c[3]).
To implement muti-start hill-climbing in a modular way you should first implement a
hill-climbing method as follows:
Hill-climbing
This is the algorithm we have discussed in class and implemented in practical 3 for
the Knapsack problem. It starts from an initial random solution and tries to improve
it iteratively using a mutation operator. Here you can reuse your Hill-climbing code
for the Knapsack problem. Notice, however, that we cannot use the same bit-flip
mutation operator used for the Knapsack problem as the representation in the
colour ordering problem is not a list of binary numbers! Our representation is
instead an ordering (also called a permutation) of integers. Notice that in a
permutation, each integer or index can appear only once.
For a permutation representation, the simplest mutation operator is to swap two
colour indices selected at random. For example, given a solution s = [1, 0, 2, 4, 3],
the solution s' = [1, 3, 2, 4, 0] is a neighbouring solution that swaps the indices at
position 1 and 4. This operator is called swap.
Other possible operators are:
• inversion: this operator works by Inverting (reversing) the ordering
between any two colour indices selected at random. For example, given
the solution s = [1, 0, 2, 4, 3], the solution s' = [1, 3, 4, 2, 0] reverses the
indices between positions 1 and 4
• scramble: this operator works by randomly shuffling (scrambling) the
ordering between any two colour indices selected at random. For
example, given the solution s = [1, 0, 2, 4, 3], the solution s' = [1, 4, 0, 3,
2] scrambles the indices between positions 1 and 4.
The selection of which operator to implement and use is left to your own choice,
you do not need necessarily to implement all of them!
An initial randomly generated solution for the colouring ordering problem is also
different than that of the Knapsack problem. A random solution is a random
permutation or reordering of the colour indexes. The source code provided
illustrates how this can be done in Python (function random_sol).
Multi-start hill-climbing
Once you implemented the hill-climbing function, the multi-start hill-climbing simply
Implements a loop that calls the Hill-climbing algorithm from different initial
solutions. Your function should receive a parameter indicating the number of
repetitions. Here again, you can reuse the code you implemented for the Knapsack
problem.
2. Clustering-based algorithm
Here your solution should consider a clustering algorithm as implemented in the
scikit-learn library. You can use any of the clustering methods available (k-means,
hierarchical, etc).
The idea is to apply the clustering method to the colours dataset, so the colours
will be assigned to a number of clusters. Let us assume your clustering algorithm
produced K groups or clusters. Then you will assemble a solution by ordering the
colours according to their cluster membership. That is, first add all the colours from
cluster 1, then add the colours from cluster 2 and so on up to cluster K.
Notice that within each cluster, the colours will not be ordered, but this is OK. This
algorithms only orders the colours at the level of clusters.
3. Algorithm variant of your choice
Here you’re given the opportunity to design your own algorithm. The general goal is
to try to improve the performance and quality of solutions obtained by Algorithms 1
and 2. This part is left open to your creativity. You can propose variations of
Algorithms1 and 2 by incorporating some of the algorithm ideas and metaheuristics
discussed in the lectures, you can combine methods, you can do your own
research or try your own ideas. Marks will be given for the effort in your research
and implementation, and for the quality of your best-obtained solutions. By "quality"
of solutions, I mean both the subjective appearance and the value obtained using
evaluation function (sum of distances).
What do you need to submit?
You need to submit 3 Jupyter notebooks, one for each Algorithm. The notebooks
will contain your code, some text descriptions and some plots illustrating your
results. There is no page/length limit, but you are encouraged to be concise and
clear in your descriptions.
There is no need to recapitulate the problem or have an introduction. Here
a description of what to include in each of the Jupyter notebooks in addition to
your code. You will also find an indication of the % marks for each part.