ASSESSED
G52AIM Lab 2 – Iterated Local Search
1 OBJECTIVES
This is the second assessed lab session and will account for 1/5th (including the
report) of the module’s total coursework mark (5% of the entire module).
1.1
LAB EXERCISE
Implement Iterated Local Search (ILS) embedding “intensity of mutation” and “depth of search” parameters with a single-perturbative random mutation heuristic.
Note that the local search heuristic used by ILS will be that implemented during lab 01 (DBHC); if you did not complete this, you should do so before the lab!
If you modified DBHC to accept equal or improving moves (IE), you should change this back to accept only improving moves (OI).
1.2 REPORT
To be announced at the start of the lab.
2
IMPLEMENTATION [50 MARKS]
2.1 TASKS
YouaregiventwoClasses;IteratedLocalSearch, and RandomMutation,withinwhichyouwillneed to complete the implementation of Iterated Local Search embedding intensity of mutation and depth of search parameters, and a single-perturbative random mutation heuristic. Remember your implementation should perform a single iteration of the respective heuristic method, hence no while(terminationCriterionNotMet) loop is required. Running of your solutions are handled by the Lab_02_Runner Class that is provided for you and the experimental parameters can be configured in Lab02TestFrameConfig. Note also that Lab_02_Runner executes the experiments in parallel (which is ok to do given an iteration-based termination criterion such as that used within this framework) to reduce the time you must wait. Do not be concerned that experiments seem to complete quicker than expected. Your computer may slow down during the experiments due to the high CPU usage and parallelisation. This is normal and is nothing to worry about.
2.1.1 Iterated Local Search
ILS was covered in the lecture on metaheuristics. Below is the pseudocode from the lecture adapted to embed intensity of mutation (IOM) and depth of search (DOS) parameters. Remember that the test framework handles solution initialisation and the outer loop of the search method. Hence only lines 4 to 7 need to be implemented in the runMainLoop() method. For the acceptance criterion, you can use either; accept only improving moves, or accept improving or equal moves. We suggest that you
1 G52AIM Lab 2 – Iterated Local Search
ASSESSED
think about how ILS works and think about whether strict acceptance is necessary or not when deciding which criterion to use.
1 | 𝑠 = generateInitialSolution(); 2 | 𝑠∗ = localSearch(𝑠);
3 | REPEAT
// optional – not used in this case
// syntactic step for below pseudocode – this does not represent an actual operation
4|
5| 6| 7| 8 | 9 |
2.1.2
𝑠 ← 𝑠∗;
2.2
1. 2.
MARKING CRITERION
A correct implementation of Iterated Local Search. A correct implementation of Random Mutation.
[40 marks]. [10 marks].
for( 0 -> iom – 1 ) 𝑠 ← perturbation(𝑠); for( 0 -> dos – 1 ) 𝑠 ← localSearch(𝑠′); 𝑠∗ ← acceptanceCriterion(𝑠∗, 𝑠, memory);
UNTIL( termination conditions are satisfied ); return 𝑠∗;
Single Perturbation Random Mutation
Each solution to a SAT problem is represented by a bit string, for example 0011101010. A single- perturbative random mutation heuristic should flip one bit/variable selected randomly using the in- built experimental random number generator.
1 | 𝑖←𝑟𝑎𝑛𝑑𝑜𝑚∈[0,𝑁]; 2 | 𝑠 ← flip(𝑖, 𝑠);
2.1.3 Importing the required files
Within the Lab 02 source files archive is one folder named after the package which you must copy the containing source files to; within “com.g52aim.lab02” are 4 classes. IteratedLocalSearch.java, RandomMutation.java, Lab_02_Runner.java,andLab02TestFrameConfig.java.Copythesefiles into the package “com.g52aim.lab02”.
2.1.4 Problem with program hanging
On some student’s computers, the program hangs before displaying boxplots/progress plots. Within the ExperimentalSettings Class, there are two variables ENABLE_GRAPHS, and ENABLE_PARALLEL_EXECUTION; Try setting one or both to false if you are experiencing these problems. They can be changed back to true on the lab machines if you wish to analyse these algorithms later.
3 REPORT [50 MARKS]
To be announced at the start of the lab via a “report exercise sheet” on Moodle.
4 FRAMEWORK BACKGROUND
For a single point-based search method, the G52AIM Framework maintains two solutions in memory,
a current solution, and a backup solution. When a SATHeuristic is invoked on a problem, it modifies 2 G52AIM Lab 2 – Iterated Local Search
ASSESSED
the solution in the current solution index (CURRENT_SOLUTION_INDEX) leaving the candidate solution (𝑠) in the CURRENT_SOLUTION_INDEX, and does not modify the backup solution in the BACKUP_SOLUTION_INDEX within the intermediate solution memory state. The move should then either be accepted (𝑠 ← 𝑠) or rejected (𝑠 ← 𝑠) using the respective move acceptance criterion.
Figure 1 – Single Point-based Search in the G52AIM Framework. The dashed arrow represents a solution being copied between solution memory indices using the copySolution(int source_memory_index, int destination_memory_index) method of the SAT problem.
5 IMPLEMENTATION HINTS
Below are some answers to questions which may arise from the implementation of the hill climbing
heuristics.
Where do I find the mutation and local search heuristics?
Both mutation and local search heuristics are created within Lab_02_Runner and are passed into the constructor of the IteratedLocalSearch Class. They are then stored as member variables named mtn and ls respectively.
How do I use different/multiple heuristics within a single search method?
A heuristic h is applied to a solution by calling h.𝑎𝑝𝑝𝑙𝑦𝐻𝑒𝑢𝑟𝑖𝑠𝑡𝑖𝑐(𝑝𝑟𝑜𝑏𝑙𝑒𝑚). Remember SATHeuristics within this framework modify the solution in the CURRENT_SOLUTION_INDEX only. Hence, multiple applyHeuristic calls can be made one after another with each heuristic receiving the candidate solution generated by the previous heuristic.
3 G52AIM Lab 2 – Iterated Local Search
ASSESSED
Figure 2 – Illustration of chaining multiple heuristics in the G52AIM Framework.
How do I: perform a bit flip; get the number of variables; evaluate the solution; etc.
See the G52AIM Framework API for framework specific questions on Moodle!
6 SUBMISSION
As with all future labs, each coursework will comprise a two-part submission:
(i) [50%] your implementation (code) which needs to be submitted within the computing hours at the lab which will be enforced by attendance sheets. If any extenuating circumstances are preventing you from attending the lab, then please contact me.
(ii) [50%] a brief report which needs to be submitted by Tuesday, 3pm following each computing session.
IMPORTANT: No late submissions are allowed. Hence any late submission will receive a mark of 0. It is fine just to return the (i) code and not the report for a partial mark. However, if (i) code is not returned within the computing hours, then the report will not be marked yielding a mark of 0 for that computing exercise.
6.1 IMPLEMENTATION SUBMISSION
Deadline: 18/02/2019 – 15:00
You should submit a single ZIP folder called [username]-lab02-implementation.zip including IteratedLocalSearch.java and RandomMutation.javatoMoodleunderSubmissionareaCW2a. Reminder late submissions or solutions completed outside of the lab will receive a mark of 0, and you will not be able to submit the report section of the coursework.
4 G52AIM Lab 2 – Iterated Local Search
ASSESSED
6.2 REPORT SUBMISSION
Deadline: Thursday 21/02/2019 – 12:00
You should submit a single PDF file called [username]-lab02-report.pdf to Moodle under Submission area CW2b.
7 OUTCOMES
1. You should know how to implement Iterated Local Search.
2. You should understand the effects that varying the intensity of mutation and depth of search
settings have on the search space.
3. You should have an idea how other single point-based metaheuristics can be implemented
within the G52AIM Framework.
IMPORTANT INFORMATION
The labs are assessed exam style sessions. Hence, you are not allowed to complete the coursework outside of the lab session or discuss your solutions with other students during the lab. (You can, of course, ask questions to the lab helpers though!). You should not prepare code in advance of the labs and use it as part of your answer(s). Template code will be provided before the lab including the test framework to run your implementations, and you will be given part completed files where you should provide your answers.
5 G52AIM Lab 2 – Iterated Local Search