8. Local Search¶
8.1. Theory¶
8.2. Project : TSP with Local Search¶
Your goal is to implement methods used in a local search to solve the Traveler Salesman Problem. In the base code given, a solution is represented by a list of integers representing cities. For instance the list [2,0,1] represents the tour going like this : 2 -> 0 -> 1 -> 2.
It is important to differentiate the operations applied index-wise and city-wise. For instance, the twoOpt method in Candidate class is applied index-wise, while the distance method in TSPInstance class is applied city-wise.
8.2.1. Implementation¶
All the files related to this project are in the package localsearch. You have to modify six classes:
Candidate.javaBestSelection.javaBestWithTabuSelection.javaBeamSearchInitialization.javaBeamSearchAppend.javaBeamSearchInsert.javaLKH.java
8.2.1.1. Two Opt¶
The first method to implement is the twoOpt method in Candidate.java. This method takes two indices (index1 and index2) and reverse the cities in the tour from index1 + 1 and index2. For instance, if the tour is [2,0,1,3,4] and index1 = 1 and index2 = 3, the new tour will be [2,0,3,1,4]. This way, a twoOpt between index1 and index2 places the city at index2 as the successor of the city at index1. Note : this methods also updates the total distance (cost) of the tour.
8.2.1.2. Best Selection¶
The most important part of a local search is the neighbor selection. The class FirstSelection.java contains the method getNeighbor that returns the first improving neighbor found among all twoOpt movements possible. You are asked to implement the same method in the class BestSelection.java. This method should return the best improving neighbor found among all twoOpt movements possible. The best neighbor is the one that minimizes the total distance of the tour. If no improving neighbor is found, the method should return the Candidate given in argument.
8.2.1.3. Tabu¶
Tabu is a common metaheuristic used in local search. The idea is to avoid returning to a previous state by forbidding a given move for a given number of iterations. In the BestWithTabuSelection.java class, you are asked to implement the getNeighbor method that returns the best improving neighbor found among all twoOpt movements possible that is not obtained through a tabu move. Once a movement is applied it should be added to the tabu list. Note : the movement tabu is a movement that would reset the solution to it’s previous state. In our case, if we set the city2 to be the successor of city1, the tabu movement is to set the former successor of city1 to be it’s new successor.
8.2.1.4. BeamSearch Initialization¶
Another important component of the local search is the initialization of the solution. In the BeamSearchInitialization.java class, you are asked to implement the getInitialSolution method that returns an initial candidate. To obtain the initial candidate, you need to construct a tour by starting at city 0 and selecting the best city to add to the partial solution. At each iteration you need to only keep p (beamWidth) best partial solution. Next, in BeamSearchAppend.java and BeamSearchInsert.java implement the expand function so that the beamsearch constructs solution only by appending to the end or inserting anywhere is the current partial solution. Following the course naming convention, k = lookAhead = 1.
8.2.1.5. LKH¶
LKH is a strong heuristic to improve an existing solution. This heuristic uses a reference structure as a temporary solution to apply improving move and convert it back to a candidate solution. With the help of the pseudo code, implement the methods in LKH.java. Note the methods findBestC and reversePath are given to help you implement applyLKH
8.2.2. Gradescope¶
On Gradescope, find the written assignment for the project. Part of your assignment requires to report experimental results under the form of a graph.
