Question $3$ Optimisation

$($a$)$ Give one strength and one weakness of Hill Climbing. Justify your answer.

$[10$ marks$]$

$($b$)$ Consider the following optimisation problem and algorithm design to solve it:

Optimisation Problem

A builder has $N$ possible clients. Each client iin$\{1,$dots,$N\}$ would like the builder to undertake a job that takes $h_i$ hours to complete. The builder wishes to decide which clients to accept over the next $30$ days so as to maximise their income while ensuring that they work no more than $7\mathrm{.}5$ hours per day. This problem can be mathematically formulated as follows:

maximise $f(x)$

subject $tog(x)=\frac{1}{30}({\displaystyle \underset{i=1}{\overset{N}{}}}{x}_i{h}_i)-7\mathrm{.}50$

where $x$ is a vector of size $N,$ and AAiin$\{1,$dots,$N\},x_i=0$ if the builder does not accept job i and $x_i=1$ otherwise; and $f(x)$ is a function that calculates the income.

Simulated Annealing Algorithm Design

Representation: a direct representation of the design variable $x.$ In other words, a vector $x$ of size $N,$ where AAiin$\{1,$dots,$N\},x_i=0$ if the builder does not accept job i and $x_i=1$ otherwise.

Algorithm $1$: Initialisation Procedure.

$,$Input: Number of possible clients $N.$

$,$Output: Candidate solution $x.$

$,x=$ new vector of size $N$;

$,$for $i=1$ to $N$ do

$,,x_i=$ value picked uniformly at random from $\{0,1\}$;

$,$return $x$

Algorithm $2$: Neighbourhood Operator.

$,$Input: Current solution $x$; number of possible clients $N.$

$,$Output: Neighbour $x^{\text{'}}.$

$,x^{\text{'}}=$ copy of $x$;

$,i=$ value picked uniformly at random from $\{1,$dots,$N\}$;

$,x_i^{\text{'}}=1-x_i$;

$,$if $g(x^{\text{'}})>0$ then

$,,x_i^{\text{'}}=0$;

$,$return $x^{\text{'}}$

Are the representation, initialisation and neighbourhood operators correctly designed $($i$.$e$.,$ suitable$)$ for this problem? Assume that we wish to deal with the constraints of this problem based on the design of the algorithm's operators. Justify your answer by explaining either why all three operators are suitable, or what is wrong.

Note:

The problem formulation correctly reflects the intended problem, i$.$e$.,$ you do not need to check whether the problem formulation itself is correct.

You do not need to consider how efficient the design of the operators is$,$ just whether or not it is a correct design for the problem.

It is acceptable for the neighbourhood operator to sometimes generate a neighbour that is the same as the current solution.

$[10$ marks$]$