Assume that a generic Iterated Local Search (ILS) algorithm is implemented embedding the Improving Only (IO) acceptance method, Davis's Bit Hill Climbing (DBHC) for local search controlled by the depth of search (DOS) parameter, random bit-flip for perturbation

controlled by the intensity of mutation (IOM) parameter. These parameters take integer values in the range [0, 10] that correlate to the number of times of calls to DBHC and bit-flip operator before moving on to the next step in the algorithm. For

example, DOS=0 (i.e., DOS is set to 0) indicates that DBHC is not applied, or  DOS=3 (i.e., DOS is set to 3) indicates that DBHC is applied to a solution for 3 passes over that solution, while IOM=3 (i.e., IOM is set to 3) indicates that 3 bit-flips are applied to the incumbent solution. 

Which one of the following options would convert the ILS algorithm into a Random Walk algorithm (randomly sampling the search landscape)?

Assume that a generic Iterated Local Search (ILS) algorithm is implemented embedding the Improving Only (IO) acceptance method, Davis's Bit Hill Climbing (DBHC) for local search controlled by the depth of search (DOS) parameter, random bit-flip for perturbation

controlled by the intensity of mutation (IOM) parameter. These parameters take integer values in the range [0, 10] that correlate to the number of times of calls to DBHC and bit-flip operator before moving on to the next step in the algorithm. For

example, DOS=0 (i.e., DOS is set to 0) indicates that DBHC is not applied, or  DOS=3 (i.e., DOS is set to 3) indicates that DBHC is applied to a solution for 3 passes over that solution, while IOM=3 (i.e., IOM is set to 3) indicates that 3 bit-flips are applied to the incumbent solution.  

Is the following statement TRUE or FALSE?

If  IOM=0 (IOM is set to 0) and DOS=10 (DOS is set to 10), ILS is likely to get stuck at a local optimum.

Assume that a generic Iterated Local Search (ILS) algorithm is implemented embedding the Improving Only (IO) acceptance method, Davis's Bit Hill Climbing (DBHC) for local search controlled by the depth of search (DOS) parameter, random bit-flip for perturbation

controlled by the intensity of mutation (IOM) parameter. These parameters take integer values in the range [0, 10] that correlate to the number of times of calls to DBHC and bit-flip operator before moving on to the next step in the algorithm. For

example, DOS=0 (i.e., DOS is set to 0) indicates that DBHC is not applied, or  DOS=3 (i.e., DOS is set to 3) indicates that DBHC is applied to a solution for 3 passes over that solution, while IOM=3 (i.e., IOM is set to 3) indicates that 3 bit-flips are applied to the incumbent solution. 

Is the following statement TRUE or FALSE?

If IOM=10 (IOM is set to 10) and DOS=0 (DOS is set to 0), ILS becomes a Random Mutation Hill Climbing algorithm.

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!