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?