For the following investigation, return TRIALS_PER_TEST back to 11 in the interest of your own time. Keeping an increased number of trials may change the results you obtain, but the same learning outcomes will still be achieved if I crafted larger (more difficult) problem instances for you to solve which would just take you longer to complete.

In the implementations of DBHC and SDHC, you were asked to accept a neighbouring solution if that solution strictly improves over the current solution. Try changing this to accept all non-worsening neighbouring solutions and run some further experiments. What conclusions can you draw about the performance of the hill-climbing algorithms when using the different acceptance mechanisms?

If given an unbounded computational budget, which of the hill-climbing heuristics performs the best on average for solving the same MAX-SAT instance #5?

Which of the hill-climbing heuristics perform the best on average for solving MAX-SAT problem instance #5 when given a computational budget of 1 second?

By increasing the number of trials, we are able to draw

different conclusions about the performance of the two hill-climbing heuristics.

What does this tell us about the original setting for the number of trials?

In the previous two questions, we observed that different hill-climbing heuristics can outperform each other depending on the computational budget given. Can we draw the conclusion that Steepest Decent Hill Climbing will always outperform Davis’s Bit Hill Climbing for solving any MAX-SAT problem instance if given enough time?

In the context of the COMP2001 Framework and other frameworks which we will use later in the module, it is common to formulate optimisation problems as minimisation problems where the goal is to minimise some cost or penalty as defined by the objective function. 

Within the COMP2001 framework we will be using a minimisation objective function for the MAX-SAT problem where the aim is to minimise the total number of unsatisfied clauses.

What would be the objective value of a solution to the problem instance (A∨¬B)∧(B∨C)∧(¬A∨¬C) with the representation “110” if we were using the minimisation objective function?

When running task 4, you should have found that the best

solution found for all of the trials had the same objective value. Despite

performing a random walk of the search space, which of the following explains the most likely reason why the

best solution found in each of the trials have the same objective function

value?

In the code for task 4, what would happen if you were to

change `m_seeds` to contain a single seed value? Explain why this is a bad idea

for experimental design.

In the code for task 4, what would happen if you were to change

`m_seeds` to contain three seed values that are all different from each other? You

should debug the code where necessary to reflect upon and explain the effect(s) on:

• The initial solution.

• Which bits are flipped in the representation and

  in which order.

• The best solution found.

• Whether using a different seed would guarantee

  that the best solution found will be different.

When running task 4, you should have found that the best

solution found for all of the trials had the same objective value. If the

solution to any instance of the MAX-SAT problem has the same objective value,

can we say that the solution found is the same?