The pseudocode below is provided for Iterated Local Search solving a minimisation problem. Which line of the code is problematic, and why?

1 s*= GenerateInitialSolution()
2 Repeat
3    s' = applyLocalSearch(s*) // apply hill climbing 
4    s' = perturbSolution(s' ) // make a random move
5    accept = moveAcceptance(s*, s', memory);  // remember best solution found so far
6    if (f(s') < f(s*)) s* = s'; // else reject new solution s'
7 Until (termination conditions are satisfied) 
8 return s* 

Which of the algorithms below is a local search metaheuristic?

You should have observed by now that DBHC is relatively much quicker than SDHC to find a local optimum, however, the amount of time required before each hill climbing heuristic gets stuck in a local optimum varies depending on the selected instance to be solved.

Select the most likely explanation from the following statements that could explain this latter phenomenon.

You may have noticed that in some cases, changing SDHC to accepting non-worsening moves led to a worse performance compared to SDHC accepting improving moves on some problem instances, for example when solving instance 5. Select all of the following explanations that could be correct.

In the experiments so far, we have run each heuristic for a total of 11 trials and found that when given an unbounded computational budget, DBHC outperformed SDHC on average for some instances, and vice versa for other instances.

When comparing the hill-climbing heuristics for solving MAX-SAT instance #11 for a total of 5 seconds, which allows enough time for both methods to reach local optima in all trials, we find that on average DBHC outperforms SDHC.

Try running these experiments again, but this time increase the “TRIALS_PER_TEST” configuration variable in Lab2ExercisesTestFrameConfig to increase the sample size used in the experimentation. Which of the following observations can you now conclude?

We have just stated that we cannot know for certain that SDHC will always outperform DBHC for solving any MAX-SAT problem instance if given enough time. Select all of the instances where it is true that DBHC outperforms SDHC on average (median - the red line on the box plots) when given an unbounded computational budget when using the same experimental seeds and TRIALS_PER_TEST equal to the default 11.

Remember to inspect the progress plots to ensure your RUN_TIME is set high enough in Lab2ExercisesTestFrameConfig!

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?