<jupyter_start><jupyter_text>Local SearchThe second phase in GRASP involves local search.  This is an entire topic on its own!  Here we will keep things simple and look at basic local search using a **hill-climbing** approachHill climbers are very simple algorithms that iteratively test neighbouring solutions to see if they find any improvement. This local search approach is often very successful at finding reasonably good solutions to a routing and scheduling problem. The major drawback is that hill climbers suffer from getting stuck in a **local optimum** and you can often do better by employing a more sophisticated algorithm.However, you might be surprised at how useful hill-climbers turn out to be when used in combination with other approaches in a multi-start algorithm like GRASP. One of the key benefits of hill climbers is that they are relatively fast (because they are simple). You can even set a time limit to get some of the benefit of local search without greatly extending the execution time of your algorithm.> Although this the approach is called Hill-Climbing in the TSP you are descending a hill to the find the shortest route. The algorithm is the same, but you are maximising -1*objective (or alternatively $\dfrac{1}{objective}$).  Imports<jupyter_code>import numpy as np
import sys<jupyter_output><empty_output><jupyter_text>`metapy` imports<jupyter_code># install metapy if running in Google Colab
if 'google.colab' in sys.modules:
    !pip install meta-py
from metapy.tsp import tsp_io as io
from metapy.tsp.euclidean import gen_matrix, plot_tour

from metapy.tsp.objective import OptimisedSimpleTSPObjective

from metapy.local_search.hill_climbing import (HillClimber,
                                               TweakTwoOpt, 
                                               SimpleTweak)<jupyter_output><empty_output><jupyter_text>Load data and generate cost matrix<jupyter_code>#load file
file_path = 'https://raw.githubusercontent.com/TomMonks/meta-py/main/data/st70.tsp'

#number of rows in the file that are meta_data
md_rows = 6

#read the coordinates
cities = io.read_coordinates(file_path, md_rows)
matrix = gen_matrix(cities, as_integer=True)<jupyter_output><empty_output><jupyter_text>TWEAKS: Simple versus 2-OptHill-Climbing works by iteratively tweaking a solution to search for better neighbouring solutions. `metapy` provides two relatively straightforward tweak operators. `SimpleTweak` swaps the position of two cities at a time while `TweakTwoOpt` reverses a section of the route between two cities. Generally speaking `TweakTwoOpt` will produce better solution<jupyter_code>tour = np.arange(10)
tweaker1 = SimpleTweak()
tweaker1.tweak(tour, 5, 9)
tour
tour = np.arange(10)
tweaker2 = TweakTwoOpt()
tweaker2.tweak(tour, 1, 4)
tour<jupyter_output><empty_output><jupyter_text>Example local search<jupyter_code># Basic First Improvement Hill Climber

# create a tour (full 70 cities)
tour = np.arange(70)
rng = np.random.default_rng(42)

# random init solution (operation in place)
rng.shuffle(tour)

# create TSP objective (negate costs)
objective = OptimisedSimpleTSPObjective(-matrix)

# create Hill climbing algorithm
solver = HillClimber(objective=objective, 
                     init_solution=tour, 
                     tweaker=TweakTwoOpt())

# run the local search
solver.solve()

# output results
print("\n** Hill Climber First Improvement OUTPUT ***")
print("best cost:\t{0}".format(solver.best_cost))
print("best solutions:")
print(solver.best_solutions[0])
fig, ax = plot_tour(solver.best_solutions[0], cities, figsize=(12,9))<jupyter_output>** Hill Climber First Improvement OUTPUT ***
best cost:	-838.0
best solutions:
[63 64 55 10 47 66 53 32 11 59 51  9  4 52  5 40 42 16 20 33 61 38 60 39
 44 24 45 26 67 43 29 19 13 27  7 25 48 54 18  1  6 31  2 41 17  3 23 14
 56 34 68 30 69 12 28 35  0 15 50 49 57 36 46 22 37 58 21 62 65  8]
{'fraction_non_alphanumeric': 0.06798358132375577, 'fraction_numerical': 0.04207285787583376, 'mean_word_length': 4.3853591160221, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 21, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '450744', 'license': 'MIT', 'n_tokens_mistral': 1308, 'n_tokens_neox': 1128, 'n_words': 475, 'path': 'content/02_local_search.ipynb', 'repo_name': 'TomMonks/grasp_examples', 'size': '3898'}