The best configuration in terms of obtaining the best median performance was either with IOM=1 and DOS=2, or with IOM=2 and DOS=2.

Now that you have finished implementing Iterated Local Search, look closely at the configuration of IntensityOfMutation and DepthOfSearch as specified in the Lab3ExercisesTestFrameConfig class. Select all of the following statements that we know are definitely true without having to perform any experimental analysis.

Given the box-plots for 3 algorithms A, B and C  based on the objective values obtained from 100 trials while solving an instance of a minimisation problem (and no other information), which of the following statement(s) about the search algorithms is definitely true?

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.